Credit Assignment

"The team won, so I was told I did a great job. I had been asleep the entire match. Nobody could prove otherwise, and that is exactly the problem."

A Freeloading Agent on a Winning Team

In the previous section we built cooperative policy-gradient methods (MADDPG, MAPPO) on top of a centralized critic that watches the joint action of every agent. That critic gives us a powerful new lever, and this section is about the most important thing it buys: a way to answer the question each agent is secretly asking. In a fully cooperative Markov game every agent receives the same team reward $r_t$ at every step. An agent improves its policy by pushing up the probability of actions that led to high reward and down the probability of actions that led to low reward. But the shared reward $r_t$ reflects the joint action of the entire team, not the action of any one agent. If the reward was high, was it because of what I did, or because four teammates carried me while I flailed? Without an answer, every agent is trying to learn from a signal that is mostly about other agents' choices, and the learning either stalls or collapses into the lazy-agent failure we are about to make precise.

1. The Lazy-Agent Pathology Beginner

Consider a team of $n$ agents that each receives the identical scalar reward $r_t = R(s_t, a_t^1, \dots, a_t^n)$. Suppose one agent, call it agent $j$, switches to a policy that does nothing useful: it always picks a cheap no-op. If the other $n-1$ agents are competent, the team still gathers reward, so the shared signal agent $j$ sees barely moves when it stops contributing. From agent $j$'s private point of view, working and not working look almost the same in the reward stream, and not working is cheaper. A naive learner will therefore drift toward the no-op. Worse, once several agents reason this way the team collapses, but each individual agent's local view never clearly told it that its own laziness was the cause. This is the lazy-agent (or freeloader) pathology, and it is the multi-agent face of a problem reinforcement learning has always had to confront.

The single-agent version is the temporal credit-assignment problem: when a reward arrives at the end of a long episode, which of the many earlier actions deserves the credit? Reinforcement learning answers that one with value functions and temporal-difference bootstrapping, which propagate credit backward through time. The multi-agent problem is a credit-assignment question along a different axis, not "which of my past actions" but "which of us right now," and value functions over a single agent's history do not address it. We need a mechanism that distributes one shared reward across simultaneous contributors, which is precisely the structural credit-assignment problem.

2. Difference Rewards and the Counterfactual Question Intermediate

The cleanest way to isolate agent $i$'s contribution is to ask a counterfactual: hold everyone else's action fixed, and ask how much worse the team would have done if agent $i$ had instead taken some default action $c_i$ (typically a no-op). That comparison is the difference reward, defined for agent $i$ as

the actual team reward minus the team reward in the counterfactual world where agent $i$ did the default thing and nobody else changed. Two properties make $D_i$ the right signal. First, anything in the reward that does not depend on agent $i$'s action, the part its teammates produced, cancels in the subtraction, so $D_i$ measures only agent $i$'s marginal effect. A freeloader that contributes nothing gets $D_i \approx 0$ no matter how well the team does, and is no longer fooled into thinking the team's success was its own doing. Second, and less obvious, an action that raises agent $i$'s difference reward also raises the true team reward, because the subtracted counterfactual term does not depend on agent $i$'s actual action; so every agent can selfishly climb its own $D_i$ and the team reward climbs with it. This factoredness is what makes difference rewards a sound team-learning signal rather than a heuristic.

The difference reward is the marginal-contribution idea you have already met in cooperative game theory. In Chapter 28 the Shapley value assigned each player a fair share of a coalition's total value by averaging that player's marginal contribution over all orders of joining. The difference reward is exactly a marginal contribution, $v(\text{coalition with } i) - v(\text{coalition without } i)$, evaluated against a single default for the rest of the team rather than averaged over all subsets. Where the full Shapley value averages over every coalition (expensive, $2^n$ terms), the difference reward fixes the others at their observed actions and takes one such marginal. It is the fair-division intuition of Chapter 28 made cheap enough to compute inside a reinforcement-learning inner loop.

3. COMA: A Counterfactual Baseline from the Centralized Critic Advanced

Computing the difference reward exactly needs access to the reward function so we can re-evaluate the counterfactual world, which we usually do not have during learning. Counterfactual Multi-Agent policy gradients (COMA) make the idea practical by estimating the counterfactual with the centralized critic from Section 30.7 instead of the true reward. The critic $Q(s, \mathbf{a})$ already scores the joint action under centralized training. COMA forms a per-agent counterfactual baseline by marginalizing out agent $i$'s action, holding the others fixed, and subtracts it from the realized joint value to get an advantage:

where $\mathbf{a}^{-i}$ is the joint action of everyone except agent $i$ and $\pi^i(\cdot \mid \tau^i)$ is agent $i$'s policy conditioned on its own action-observation history $\tau^i$. The subtracted term is the critic's expected value averaging over what agent $i$ could have done, the learned stand-in for "what the team would have gotten had agent $i$ not made this specific choice." Because the baseline does not depend on the action actually taken, it does not change the expected policy gradient, it only removes the variance and bias that come from the other agents' contributions, which is exactly the difference-reward effect estimated rather than computed. A single forward pass through the centralized critic yields the counterfactual baseline for all of agent $i$'s alternative actions at once, so the method costs one critic evaluation per agent rather than a re-run of the environment.

4. Value Decomposition as Implicit Credit Assignment Intermediate

Difference rewards and COMA attack credit assignment explicitly, by constructing a per-agent signal. The value-decomposition methods of Section 30.6 attack it implicitly. VDN writes the joint action-value as a sum of per-agent components, $Q_{\text{tot}}(s, \mathbf{a}) = \sum_{i} Q_i(\tau^i, a^i)$, and QMIX relaxes the sum to any monotonic mixing of the components. Training optimizes only the joint $Q_{\text{tot}}$ against the shared reward, yet each $Q_i$ emerges as agent $i$'s learned share of the team value. Because the mixing is monotonic, raising any $Q_i$ raises $Q_{\text{tot}}$, so an agent can act greedily on its own component and still improve the team, the same factoredness property the difference reward guarantees by construction. Value decomposition therefore performs credit assignment without ever forming an explicit counterfactual: the architecture forces the network to split the shared reward into additive shares during learning, and those shares are the credit. The lazy-agent pathology is avoided because an agent that never affects $Q_{\text{tot}}$ gets a flat, uninformative $Q_i$ and its greedy action carries no spurious credit from teammates.

5. A Runnable Demonstration Intermediate

The contrast between a naive shared reward and a counterfactual difference reward is sharp enough to see in a few lines of pure Python, with no deep-learning machinery. We build a tiny cooperative team of four agents. Each agent chooses to exert effort or take a no-op. Effort has a gross value but also a cost, charged into the one shared team reward, so the net marginal value of effort is large and positive for agent 0 (it should work) and slightly negative for agents 1 to 3 (they should stay idle). We then train every agent with the same simple policy-gradient update under two credit signals: the naive shared reward handed identically to all agents, and a difference reward that replaces each agent's action with the no-op to measure its marginal effect. The code below runs both and prints the learned probability of effort per agent.

import numpy as np

rng = np.random.default_rng(0)
n = 4                      # agents on the team
contrib = np.array([1.0, 0.1, 0.1, 0.1])   # gross value of each agent's effort
cost = 0.25                # private cost of effort, charged into the TEAM reward
noop = 0                   # the default / no-op action used by the counterfactual
# Net marginal value of effort = contrib - cost. Agent 0 (0.75) should work;
# agents 1..3 (-0.15) should stay on the no-op.
net = contrib - cost


def team_reward(actions):
    # Shared scalar reward: everyone receives this exact same number. Each unit
    # of effort adds its gross value but also charges its cost to the team.
    base = float(np.sum((contrib - cost) * actions))
    return base + 0.3 * rng.standard_normal()   # common team noise


def train(use_counterfactual, steps=8000, lr=0.15):
    theta = np.zeros(n)                          # logits of P(effort) per agent
    for _ in range(steps):
        p = 1.0 / (1.0 + np.exp(-theta))         # effort prob per agent
        actions = (rng.random(n) < p).astype(float)   # sampled joint action
        r = team_reward(actions)                 # ONE shared reward

        if use_counterfactual:
            # Difference reward: replace agent i's action with the no-op and ask
            # what the team reward WOULD have been (the counterfactual baseline).
            advantage = np.empty(n)
            for i in range(n):
                cf = actions.copy(); cf[i] = noop
                base_actual = float(np.sum((contrib - cost) * actions))
                base_cf     = float(np.sum((contrib - cost) * cf))
                advantage[i] = base_actual - base_cf   # agent i's marginal share
        else:
            advantage = np.full(n, r)            # every agent gets the same number
            advantage = advantage - advantage.mean()   # shared-baseline subtraction

        grad = advantage * (actions - p)         # REINFORCE: grad log pi = a - p
        theta += lr * grad
    return 1.0 / (1.0 + np.exp(-theta))


np.set_printoptions(precision=3, suppress=True)
print("net marginal value of each agent's effort  :", net)
print("NAIVE shared reward  -> P(effort) per agent:", train(False))
print("counterfactual/diff  -> P(effort) per agent:", train(True))

net marginal value of each agent's effort  : [ 0.75 -0.15 -0.15 -0.15]

NAIVE shared reward  -> P(effort) per agent: [0.5 0.5 0.5 0.5]
counterfactual/diff  -> P(effort) per agent: [0.999 0.007 0.007 0.008]

The naive learners are stuck at probability $0.5$, an undecided coin flip, because the shared reward is dominated by teammates' and noise contributions that swamp each agent's own small effect; the gradient it produces points nowhere in particular. The counterfactual learners recover the truth almost perfectly: agent 0, whose effort is worth $+0.75$ to the team, learns to work with probability $0.999$, while agents 1 to 3, whose effort costs the team $0.15$ net, learn to stay on the no-op. This is the lazy-agent pathology and its cure in one experiment: the naive signal cannot even tell the useful agent from the useless ones, and the difference reward separates them cleanly. The marginal-contribution view from Chapter 28 is doing all the work.

# EPyMARL: train the COMA counterfactual-baseline learner on a cooperative task
python src/main.py --config=coma --env-config=gymma \
    with env_args.key="lbforaging:Foraging-8x8-3p-2f-v3"
# swapping --config=qmix or --config=vdn switches the credit-assignment
# mechanism without touching the environment or the training loop

6. Why Credit Assignment Is What Lets Large Teams Learn Advanced

The stakes grow with the team. With two agents, the shared reward is a mediocre but workable signal; each agent's action explains roughly half of it. With fifty agents, any single agent's action explains a vanishing fraction of the shared reward, the rest is teammates and noise, and the naive gradient becomes almost pure noise from that agent's point of view. The signal-to-noise ratio of the shared reward, viewed as a per-agent learning signal, degrades as the team grows, which is why naive shared-reward learning that limps along with three agents fails outright with thirty. Good credit assignment restores a per-agent signal whose magnitude does not shrink with team size, because the difference reward and the COMA baseline cancel the teammate contributions rather than averaging over them. This is the real reason credit assignment is not an optional refinement but the enabling condition for cooperative MARL at scale: without it, adding agents adds noise faster than it adds capability, and the team stops learning.

This per-agent signal still has to survive a second difficulty that the next section confronts head-on. Even with a clean credit signal, every agent is learning at once, so the environment each agent faces keeps shifting as its teammates' policies change underneath it. That non-stationarity can corrupt the very counterfactual estimates this section relies on, and managing it is the subject of Section 30.9. Credit assignment tells an agent what its action was worth; non-stationarity asks whether that valuation is still true a thousand updates later.