Multi-Agent Credit Assignment

In a cooperative multi-agent system, a shared reward r(t) is emitted after a joint action u is taken. The fundamental question is: which agent's action caused the reward? This is an extension of the temporal credit assignment problem into a structural dimension. Unlike single-agent RL where the challenge is linking current actions to future rewards, multi-agent systems must also resolve inter-agent reward contamination. A positive outcome might be entirely driven by Agent A, but Agent B receives the same reinforcement signal, reinforcing potentially irrelevant or even detrimental behaviors. This structural noise scales combinatorially with the number of agents, making naive independent learning highly unstable.

This method applies the Shapley value from cooperative game theory to decompose the joint Q-function Q_tot(s, u) into per-agent credit assignments. The Shapley Q-value for agent i is the weighted average of its marginal contribution across all possible coalitions of other agents:

Φ_i(s, u) = Σ_{C ⊆ N \ {i}} |C|!(|N|-|C|-1)! / |N|! [Q(s, u_C ∪ {i}) - Q(s, u_C)]

This satisfies four key axioms:

• Efficiency: The sum of all Shapley Q-values equals the joint Q-value
• Symmetry: Agents with identical marginal contributions receive equal credit
• Linearity: Credit is additive across composed tasks
• Null Player: An agent contributing nothing receives zero credit

The primary computational bottleneck is the exponential number of coalitions, requiring Monte Carlo sampling approximations in practice.

A policy gradient method that uses a centralized critic to compute a counterfactual baseline for each agent. The key innovation is the advantage function:

A_i(s, u) = Q(s, u) - Σ_{u_i'} π_i(u_i' | o_i) Q(s, (u_{-i}, u_i'))

This baseline marginalizes out agent i's specific action by averaging over all actions it could have taken, weighted by its current policy. The resulting advantage isolates the unique contribution of the chosen action u_i relative to the agent's default behavior. Critically, COMA uses a single centralized critic that outputs a Q-value for every possible joint action, avoiding the need for multiple forward passes. This makes it scalable to discrete action spaces but computationally prohibitive for continuous control.

A class of methods that train a separate reward redistribution network to transform the sparse global reward into dense, agent-specific proxy rewards. The redistribution network learns to predict r_i(t) = f(s_t, u_t, R_global) such that the sum of redistributed rewards equals the original global reward. This is trained by minimizing the temporal difference error of the agents' policies under the redistributed rewards. The key advantage is that the redistribution network can learn to assign negative rewards to agents whose actions were detrimental, even when the global reward is positive. This provides richer feedback than structural decomposition methods alone and can capture non-linear credit interactions that additive models miss.

A counterfactual credit assignment method that isolates an agent's individual contribution by subtracting the team reward when the agent takes a default action from the actual team reward. This explicitly answers: 'How much better did we do because of agent i's specific action?'

• Formula: D_i = R(s, a) - R(s, a_i', a_-i)
• Key benefit: Removes noise from other agents' actions
• Challenge: Requires a simulator or model to estimate the counterfactual baseline

A game-theoretic credit assignment approach that computes the marginal contribution of each agent to every possible coalition of other agents. The Shapley value is the weighted average of these marginal contributions, providing a mathematically fair distribution of the joint Q-value.

• Fairness axiom: Satisfies efficiency, symmetry, and additivity
• Computational cost: Exponential in the number of agents
• Approximation: Monte Carlo sampling of coalitions is used in practice

Techniques for rendering the joint behavior of multiple agents to diagnose coordination failures. Includes overlaying individual saliency maps, plotting agent trajectories, and visualizing communication graphs.

• Attention maps: Show which other agents an agent attends to
• Trajectory plots: Reveal emergent roles and formations
• Communication graphs: Display message passing between agents