Multi-Agent RL

Why Does This Exist?

Single agent theory assumes a stationary world: same state, same action, same odds. Add a second learner and the assumption dies. Your rival updates overnight, so the move that scored yesterday gets punished today. Traffic, trading floors, robot fleets, and team games all live here.

Multi agent RL, building on stochastic games from Shapley (1953) and Littman (1994), studies exactly this: several policies learning at once in one shared state. The headline problem is non-stationarity, and the headline fix is centralized training with decentralized execution, CTDE. Start with Markov games for the formalism, see CTDE in action in MADDPG, and sort out reward structures in cooperative vs competitive settings.

The one idea you need first

A Markov decision process has one agent, states, actions, transition odds, and rewards. MARL keeps the shape but the transition and each reward depend on the joint action of all $N$ agents: $P(s' \mid s, a_1, \dots, a_N)$ and $R_i(s, a_1, \dots, a_N)$. Everything that follows comes from that one change.

Think of It Like This

How It Actually Works

A Markov game is the tuple $(N, S, \{A_i\}, P, \{R_i\}, \gamma)$: $N$ agents, shared state $S$, one action set $A_i$ each, joint transitions $P$, one reward function $R_i$ each, discount $\gamma$. Three reward patterns cover most work: fully cooperative with one shared reward, zero sum with $R_1 = -R_2$, and mixed general sum where interests partly align.

Why independent learning wobbles

Agent $i$ maximizes $R_i$, but $R_i$ moves with everyone else's actions. From agent $i$'s seat the world looks non-stationary: identical local histories lead to different rewards on different days because a partner explored or a rival adapted. The Markov property fails from each agent's local view, and single agent convergence proofs fail with it. Independent Q-learning runs one learner per agent anyway and often oscillates or collapses, which the worked example below shows numerically.

The CTDE fix

Centralized training with decentralized execution splits the problem across time. In training, each agent gets a centralized critic that sees the global state plus every agent's action, which removes the ambiguity about who caused what. In MADDPG (Lowe and colleagues, 2017), each actor still maps only its own local observation to its action. At deployment the critics are deleted and actors run on local views alone. Training is stable because the critic conditions on the joint action; execution is practical because actors need no radio link to each other.

Worked example

Two partners each pick A or B. Team payoffs: $R(A, A) = 10.0$, $R(B, B) = 5.0$, anything mixed pays $0.0$. Discount $\gamma = 0.95$, terminal next state so value math is just the reward.

A centralized critic tracks $Q_1(s, A, A) = 7.0$. Both agents play A, the team banks $r = 10.0$, and with critic step size $\alpha = 0.10$:

Now the independent learner, which sees only its own move. Suppose the partner explores B half the time. Then the expected payoff of playing A is $0.5 \times 10.0 + 0.5 \times 0.0 = 5.0$, exactly equal to the safe $5.0$ from always playing B. The independent agent cannot tell a bad choice from a partner's bad day, while the centralized critic can because it conditions on both moves. The diagram draws this joint action and the $7.0$ to $7.3$ step.

Code

This snippet replays the worked example: the centralized critic step and the independent learner's blurred expectation.

1def critic_update(q: float, reward: float, alpha: float) -> float:2    """One centralized critic correction toward the team reward."""3    return q + alpha * (reward - q)4
5
6def independent_expectation(p_partner_a: float) -> float:7    """Expected payoff of playing A when the partner plays A with prob p."""8    return p_partner_a * 10.0 + (1.0 - p_partner_a) * 0.09
10
11print(f"central Q={critic_update(7.0, 10.0, 0.10):.4f}")  # -> central Q=7.300012print(f"E[R|A]={independent_expectation(0.5):.4f}")  # -> E[R|A]=5.000013print(f"E[R|B]={5.0:.4f}")  # -> E[R|B]=5.0000

The critic climbs to $7.3$ on hard evidence, while the independent view ties $5.0$ to $5.0$ and learns nothing about which move was at fault.

Watch Out For

The Quick Version

• MARL puts several learners in one shared state, so each agent's world shifts as the others update.
• Joint transitions and per agent rewards define the Markov game; unilateral optima stop existing.
• Independent single agent algorithms wobble because one agent cannot separate its mistakes from its partners' exploration.
• CTDE steadies training with critics that see the joint action, then deploys actors on local observations only.
• Cooperative teams fight credit assignment, competitors fight cyclic forgetting, and both need the joint view to learn cleanly.

What to Read Next

• Markov Games
• Multi-Agent DDPG (MADDPG)
• Cooperative vs. Competitive Environments