Credit Assignment

The formal mathematical framework for modeling sequential decision-making under uncertainty. An MDP is defined by a tuple (S, A, P, R, γ):

• S: A finite set of environmental states
• A: A finite set of actions available to the agent
• P(s'|s,a): The state transition probability function
• R(s,a): The immediate reward function
• γ: The discount factor (0 ≤ γ ≤ 1) that weights future rewards

The Markov property asserts that the future depends only on the current state and action, not on the history. This property is what makes the credit assignment problem mathematically tractable—it bounds the temporal horizon over which causality must be traced.

A family of algorithms that learn by bootstrapping—updating estimates based on other learned estimates. TD learning is the primary mechanism for temporal credit assignment in model-free RL.

TD(0) Update Rule: V(s) ← V(s) + α[R + γV(s') - V(s)]

The term R + γV(s') - V(s) is the TD error, which quantifies the difference between the predicted return and the actual observed return plus the bootstrapped future value. This error signal propagates credit backward through time, allowing the agent to update its value estimates for states that occurred many steps before a reward was received.

TD(λ) extends this by using eligibility traces to assign credit across multiple timesteps simultaneously.

The practice of augmenting the environment's sparse reward signal with dense, intermediate rewards to accelerate learning. This directly addresses the credit assignment challenge by providing more frequent feedback.

Potential-Based Shaping: F(s,s') = γΦ(s') - Φ(s)

Where Φ is a potential function over states. This formulation is policy-invariant—it does not alter the optimal policy while dramatically reducing the temporal distance between actions and feedback.

• Domain heuristics: Distance-to-goal metrics in navigation
• Curiosity bonuses: Rewards for visiting novel states
• Subgoal completion: Intermediate rewards for partial task achievement

Poorly designed shaping rewards can introduce unintended behavioral biases, making this a delicate engineering discipline.

A mechanism that bridges TD learning and Monte Carlo methods by maintaining a decaying memory of recently visited states. Eligibility traces solve the temporal credit assignment problem by marking states as 'eligible' for updates when a reward is later received.

Accumulating Trace: e(s) = γλ e(s) + 1 if s is current, else γλ e(s)

• λ = 0: Equivalent to one-step TD learning (short credit horizon)
• λ = 1: Equivalent to Monte Carlo methods (full episode credit)
• 0 < λ < 1: Balances bias and variance in credit assignment

The trace decays exponentially with time, implementing a recency heuristic—actions closer to the reward receive more credit. This is biologically inspired by synaptic plasticity in neural circuits.

A method for computing the advantage function in policy gradient algorithms that explicitly controls the bias-variance tradeoff in credit assignment. Proposed by Schulman et al. (2016).

GAE(λ) Estimator: Â_t^GAE = Σ(γλ)^l δ_{t+l}

Where δ_t = r_t + γV(s_{t+1}) - V(s_t) is the TD residual.

• λ = 0: High bias, low variance (one-step advantage)
• λ = 1: Low bias, high variance (Monte Carlo returns)

The parameter λ controls how far back in time credit is propagated. GAE is the standard advantage estimator in Proximal Policy Optimization (PPO) and is critical for stable training in continuous control tasks like robotic manipulation and autonomous vehicle routing.

In Multi-Agent Reinforcement Learning (MARL), the credit assignment problem becomes exponentially harder due to non-stationarity and partial observability. Each agent must determine which of its own actions contributed to a shared team reward.

Key Approaches:

• Difference Rewards: Compute an agent's marginal contribution by comparing global reward to a counterfactual baseline
• COMA (Counterfactual Multi-Agent Policy Gradients): Uses a centralized critic to compute a counterfactual baseline for each agent
• Value Decomposition Networks (VDN): Decompose the joint Q-function into a sum of individual agent Q-functions
• QMIX: Extends VDN by allowing non-linear monotonic mixing of agent utilities

This is directly applicable to heterogeneous fleet orchestration and multi-echelon inventory optimization, where warehouse agents, routing agents, and procurement agents must coordinate.