Counterfactual Credit Assignment in Multi-Agent RL: A Worked Derivation

A team wins. The shared reward is +1. Every agent's gradient gets the same number, so the agent who stood still learns exactly as much as the agent who saved the episode.

That is the failure this article fixes. Attribution is not a property of the outcome; it is a property of a comparison. Our job is to make the comparison formal, name what it holds fixed, and find where it stops being trustworthy.

If you have not yet built the intuition for why shared rewards create an attribution problem, start with the credit assignment concept piece first. Here we assume you already know the problem exists and want the machinery.

Why the Shared Return Cannot Attribute Anything

Set up the standard cooperative case. There are $N$ agents. At each step the environment is in state $s$, the agents choose a joint action $a = (a_1, \dots, a_N)$, and the environment returns a single scalar reward $r$ shared by everyone. Over an episode, the team collects one return $R$.

Now look at the policy-gradient weight. For a joint policy $\pi(a \mid s)$, the update for agent $i$'s parameters $\theta_i$ is proportional to

$\nabla_{\theta_i} \log \pi_i(a_i \mid \tau_i) \cdot R.$

The term $R$ is identical for every agent. It does not depend on $i$. So the update tells agent $i$ "that was good" or "that was bad" without ever telling it how much of it was you. With one team return, the gradient carries zero information about relative contribution.

The missing object is a per-agent signal that isolates one agent's effect while everything else is held constant. Two families of methods produce that signal, and they are not the same comparison. A counterfactual baseline resamples one agent's action while holding the rest of the joint action fixed. A difference reward removes the agent and compares the team outcome with and without it. Both are counterfactual, but they hold different things fixed and answer different questions. The derivation below is the action-resampling baseline; the removal form appears later as a contrast.

Notation and the Joint-Action Setup

Define the symbols before we use them.

• $s$: the state.
• $a = (a_1, \dots, a_N)$: the joint action. Agent $i$'s own action is $a_i$.
• $a_{-i}$: the joint action of every agent except $i$. So $a = (a_i, a_{-i})$.
• $Q(s, a)$: the joint action-value — expected return from $s$ when the team takes joint action $a$ and then follows the joint policy.
• $\pi(a \mid s) = \prod_i \pi_i(a_i \mid \tau_i)$: the joint policy, factored into per-agent policies over each agent's action-observation history $\tau_i$.
• $R$: the realized team return for the episode actually run.
• $R_{-i}$: the counterfactual return obtained when agent $i$'s contribution is removed.

The marginal-contribution signal is the difference:

$\Delta_i = R - R_{-i}.$

Read the sign carefully, because it is a real learning signal and not a bug:

• $\Delta_i > 0$: agent $i$ improved the outcome.
• $\Delta_i \approx 0$: agent $i$ was redundant — the team would have done about as well without it.
• $\Delta_i < 0$: agent $i$ made things worse.

That last case is the one people flinch at. A negative $\Delta_i$ is not an error; it is the environment telling agent $i$ that its action cost the team, and it should be pushed away from.

The Counterfactual Baseline, Derived Step by Step

The marginal-contribution form asks "what if we removed this agent?" The baseline form asks a slightly different question: "what if this agent had chosen differently?" Both start from the same joint action-value.

Start with $Q(s, a)$, the value of the joint action the team actually took. We want to know what agent $i$'s action was worth relative to its alternatives. So define the counterfactual baseline:

$b(s, a_{-i}) = \sum_{a'_i} \pi_i(a'_i \mid \tau_i) \, Q\big(s, (a_{-i}, a'_i)\big).$

Read this slowly. We hold the state $s$ and the other agents' actions $a_{-i}$ fixed. We let agent $i$'s action range over every alternative $a'_i$, weight each by how likely agent $i$'s own policy was to pick it, and average the resulting joint values. The baseline is the value agent $i$ would expect on average, given the rest of the team's behavior.

The per-agent advantage is then

$A_i = Q(s, a) - b(s, a_{-i}).$

This is the signal that replaces the shared return. It measures how much better the realized joint action was than agent $i$'s average alternative.

Now the step that makes this a baseline and not an arbitrary subtraction. In the policy-gradient estimator, we replace $R$ with $A_i$:

$\nabla_{\theta_i} \log \pi_i(a_i \mid \tau_i) \cdot A_i.$

Subtracting $b$ does not change the expected gradient, provided $b$ does not depend on the sampled action $a_i$ in the current rollout. Here is why. The expectation of the score term is zero:

$\mathbb{E}_{a_i \sim \pi_i}\big[\nabla_{\theta_i} \log \pi_i(a_i \mid \tau_i) \cdot b(s, a_{-i})\big] = 0,$

because $b$ is constant with respect to the sampled $a_i$ and the score function integrates to zero over the policy. So we can subtract it for free — in expectation. What we buy is variance reduction: the multiplier $A_i$ is centered around zero instead of being a raw positive return, so updates for redundant agents shrink toward nothing.

Note: The independence condition is the load-bearing assumption. The baseline must be measurable with respect to randomness external to agent $i$'s current action. If the baseline secretly depends on the action agent $i$ just took, the subtraction is no longer free and you have introduced bias.

What Is Actually Held Fixed

This is the most misread part of the method, so make the conditioning explicit.

Held fixed:

• the state $s$,
• the other agents' actions $a_{-i}$,
• the environment dynamics,
• the reward function.

Not held fixed:

• agent $i$'s action is resampled,
• everything downstream of that action is allowed to change.

The consequence is precise. The comparison answers "what would this rollout look like if agent $i$ had chosen differently?" It does not answer "what would the team score be without agent $i$?" Those are different questions with different answers.

The marginal-contribution form ($R - R_{-i}$) removes the agent. The baseline form resamples the agent's action. Removing an agent changes the team's composition; resampling its action changes only its choice. When you want to know whether a role was worth having, ask the removal question. When you want to know whether a specific decision was good, ask the resampling question.

Picture a two-branch tree growing from a shared state. The trunk holds $s$, $a_{-i}$, the dynamics, and the reward. The two branches are the realized joint action and the counterfactual. Everything above the fork is shared; everything below it is what you are comparing.

A Worked Example With Numbers

Take two agents, each with two actions $\{0, 1\}$, and a joint reward that depends on both. Suppose the current policy is uniform, so $\pi_1(a'_1) = 0.5$ for each action. The realized joint action is $a = (1, 1)$, and the critic gives us these joint values:

Agent 1's advantage. Hold agent 2's action at $a_2 = 1$. Agent 1's alternatives are $a'_1 = 0$ and $a'_1 = 1$:

$b(s, a_{-1}) = 0.5 \cdot Q(s, (0,1)) + 0.5 \cdot Q(s, (1,1)) = 0.5 \cdot 3 + 0.5 \cdot 6 = 4.5.$

$A_1 = Q(s, (1,1)) - 4.5 = 6 - 4.5 = 1.5.$

Agent 2's advantage. Hold agent 1's action at $a_1 = 1$. Agent 2's alternatives are $a'_2 = 0$ and $a'_2 = 1$:

$b(s, a_{-2}) = 0.5 \cdot Q(s, (1,0)) + 0.5 \cdot Q(s, (1,1)) = 0.5 \cdot 4 + 0.5 \cdot 6 = 5.0.$

$A_2 = 6 - 5.0 = 1.0.$

Both advantages are positive, and they do not sum to the team advantage. That is the point where intuition usually breaks. There is no conservation law here: the advantages are two separate comparisons against two separate baselines, not a decomposition of one team quantity.

Now change the table so the same team outcome splits the agents' signals. Keep $Q(s, (1,1)) = 6$, but set $Q(s, (0,1)) = 7$ and $Q(s, (1,0)) = 4$. Recompute:

$b(s, a_{-1}) = 0.5 \cdot 7 + 0.5 \cdot 6 = 6.5, \quad A_1 = 6 - 6.5 = -0.5.$

$b(s, a_{-2}) = 0.5 \cdot 4 + 0.5 \cdot 6 = 5.0, \quad A_2 = 6 - 5.0 = 1.0.$

Same team outcome, opposite signs. Agent 1's action was worse than its average alternative; agent 2's was better. The shared return of 6 could never have told you that.

From Signal to Update

The per-agent update substitutes $A_i$ for the shared return:

$\theta_i \leftarrow \theta_i + \alpha \, \nabla_{\theta_i} \log \pi_i(a_i \mid \tau_i) \, A_i.$

The practical consequence is the whole reason to do this. An agent that was redundant in a rollout gets $A_i \approx 0$, so its update is near zero. It stops being reinforced for free-riding on teammates who did the work. An agent that hurt the team gets a negative multiplier and is pushed away from that action.

The cost is that computing $b(s, a_{-i})$ requires a critic that can evaluate joint actions the team never actually took. That is why the method is normally paired with centralized training: the critic sees the full joint action during learning, even though each agent acts on local information at execution.

Where the Attribution Breaks

The signal is only as good as the counterfactual it is built on. Three assumptions carry the weight.

The critic must generalize to joint actions never taken. The baseline is an expectation over agent $i$'s alternatives, and most of those alternatives were never sampled. If the critic cannot estimate their values, the baseline is a guess dressed as an expectation. This is the most common silent failure: the arithmetic is correct and the attribution is fiction.

The counterfactual must be well-defined. In tightly coupled tasks, resampling one agent's action can produce a state the environment never reaches, or a joint action with no coherent meaning. If the counterfactual is not a real possibility, the comparison is comparing nothing.

The signal attributes marginal, not causal, contribution. Correlated agents can each look redundant while the pair is essential. If agent 1 and agent 2 always act together, then holding one fixed while resampling the other will show near-zero advantage for both — even though removing both would collapse the team. Marginal contribution is not causal contribution.

Two more failure modes worth naming. When the action space is large, the expectation over $a'_i$ is estimated from few samples and the baseline becomes high-variance. And when contributions are genuinely non-separable, a single-agent baseline will misattribute; multi-level or subset-based formulations that reason over groups of agents are the honest answer there.

When to Use a Counterfactual Baseline

The decision rule is short.

Use it when roles are distinguishable and the joint action-value is learnable. The comparison is then meaningful and cheap. Use it when the team reward is sparse and the shared-return gradient is too coarse to separate agents.

Do not use it when the critic cannot evaluate counterfactual joint actions — you will get confident, wrong attribution. Do not use it when the action space makes the expectation too noisy to estimate. And do not use it as a substitute for value decomposition when the real requirement is decentralized greedy action selection; that is a different constraint with a different solution.

The three are not competitors so much as answers to different questions. Pick the one whose held-fixed set matches the question you actually need answered.

The Next Move

Attribution is a comparison, and the comparison is only as good as the critic that evaluates the counterfactual. That single sentence is the whole article.

So do not stop at reading the derivation. Take the four-cell table above, change one number in it, and recompute both advantages. Watch them flip sign. Then change the reward coupling so the two agents' contributions become correlated, and watch the baseline report both as redundant even though the pair is essential. That is the boundary of the method, and you will understand it far better from the arithmetic than from any paragraph describing it.

Run the numbers. Change the coupling. Watch the signal betray the assumption.