---
title: "Multi-Agent RL: Markov Games and Centralized Training"
module: Modern Deep Reinforcement Learning
moduleNumber: 5
lessonNumber: 13
order: 513
summary: >
  With more than one learning agent in an environment, each
  agent's world becomes non-stationary because the others are changing too. This
  lesson builds the Markov-game generalization of the MDP, diagnoses non-stationarity
  as the central obstacle, shows why the naive baselines fail, and develops the
  dominant fix — centralized training with decentralized execution (MADDPG, VDN, QMIX).
  A companion lesson takes up self-play, the landmark game-playing systems, and the
  equilibrium concepts that define what "solved" means.
topics: [Deep RL]
sources:
  - book: Sutton & Barto
    ref: "Ch. 3 — Finite Markov Decision Processes (the single-agent baseline generalized here)"
  - book: Grokking Deep RL
    ref: "Ch. 12 — Actor-critic methods (the DDPG core MADDPG extends)"
---

Every method up to here assumed the agent was **alone**. The environment had fixed
dynamics: take an action, the world responds according to $p(s' \mid s, a)$, and that
transition kernel never changes. That assumption is what lets the Bellman equation have
a fixed point and lets Q-learning converge. It is also false the moment a second learning
agent shares the world. A market has many traders, a road has many drivers, a game of Go
has an opponent — and each of them is _also_ adapting. When the others change their
behavior, they change the dynamics _you_ face. The fixed environment that grounds
single-agent [MDPs](/reinforcement-learning/foundations/markov-decision-processes)
dissolves.

This is a different problem, with its own
mathematical object (the Markov game), its own central pathology (non-stationarity), and
its own dominant algorithmic paradigm (centralized training, decentralized execution).
This lesson builds all three. A
[companion lesson](/reinforcement-learning/modern-deep-rl/multi-agent-rl-part-2) then
turns to the setting where multi-agent RL has produced its strongest results —
**self-play**, the engine behind AlphaGo, OpenAI Five, and AlphaStar — and the
equilibrium concepts that define what "solved" means.

## The setting: Markov games

The single-agent MDP is a tuple $(\mathcal{S}, \mathcal{A}, p, r, \gamma)$. The
multi-agent generalization keeps the state and the discount but gives every agent its own
action set and its own reward. It is called a **Markov game** (or **stochastic game**),
introduced by Shapley in 1953, decades before MDPs were standard.[^shapley]

> **Definition (Markov game).** A Markov game with $N$ agents is a tuple
> $(\mathcal{S}, \{\mathcal{A}_i\}_{i=1}^N, p, \{r_i\}_{i=1}^N, \gamma)$ where
> $\mathcal{S}$ is the state space, $\mathcal{A}_i$ is agent $i$'s action set, the joint
> action is $\mathbf{a} = (a_1, \ldots, a_N) \in \mathcal{A}_1 \times \cdots \times
> \mathcal{A}_N$, the transition kernel $p(s' \mid s, \mathbf{a})$ depends on the **joint**
> action, and each agent has its own reward $r_i(s, \mathbf{a})$. Agent $i$ follows a
> policy $\pi_i(a_i \mid s)$ and maximizes its own expected return
> $\mathbb{E}[\sum_t \gamma^t r_i(s_t, \mathbf{a}_t)]$.

Two features of that definition carry all the weight. First, the transition depends on the
**joint** action $\mathbf{a}$, not on any single agent's action: where the world goes next
is determined by what everyone does together. Second, each agent has a **separate** reward
$r_i$, and those rewards need not agree. The relationship between the rewards is what
carves the field into three regimes.

$$
% caption: The three reward regimes of a Markov game, set by how the per-agent rewards
% $r_i$ relate. Cooperative agents share one reward; competitive (zero-sum) agents have
% rewards that cancel; mixed games have both aligned and opposed interests.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=32mm, minimum height=17mm, align=center, font=\scriptsize},
  root/.style={draw, thick, minimum width=30mm, minimum height=10mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[root, draw=acc, text=acc] (r) at (0,1.8) {Markov game};
  \node[box] (co)  at (-4.8,-0.6) {cooperative\\all r-i equal\\(shared goal)};
  \node[box] (mi)  at (0,-0.6)    {mixed\\r-i partly aligned\\(teams, markets)};
  \node[box, draw=red, text=red] (cm) at (4.8,-0.6) {competitive\\r-i sum to zero\\(one wins, one loses)};
  \draw[->, acc, thick] (r) -- (co);
  \draw[->, acc, thick] (r) -- (mi);
  \draw[->, acc, thick] (r) -- (cm);
\end{tikzpicture}
$$

In a **cooperative** game every agent receives the same reward, $r_1 = \cdots = r_N$, and
the team succeeds or fails together — a fleet of warehouse robots, players on one side of a
match. In a **competitive** (two-agent, zero-sum) game the rewards cancel, $r_1 = -r_2$, so
one agent's gain is the other's loss — chess, Go, a pursuit. Most real settings are
**mixed**: partly aligned, partly opposed, like traders who all want liquidity but each
want the better price, or autonomous cars that share the goal of avoiding collisions but
compete for the merge. The single-agent MDP is the degenerate case $N = 1$.

### A worked matrix game: coordination and its traps

Even the simplest one-state Markov game exposes the difficulties. Consider the
**stag hunt**, a two-player cooperative-leaning game where each player chooses to
hunt Stag ($S$) or Hare ($H$). A stag needs both hunters; a hare can be caught
alone. The payoff table (identical rewards, a cooperative game) is

| player 1 \\ player 2 | Stag | Hare |
| --- | --- | --- |
| **Stag** | $(4, 4)$ | $(0, 3)$ |
| **Hare** | $(3, 0)$ | $(3, 3)$ |

Hunt stag together and both get $4$ — the best outcome. But if one hunts stag and
the other defects to hare, the stag hunter gets $0$ (the stag escapes) while the
defector still bags a hare for $3$. There are **two** pure Nash equilibria here:
$(S, S)$ with payoff $4$ each, and $(H, H)$ with payoff $3$ each. Both are
self-consistent — at $(H, H)$, unilaterally switching to stag drops you from $3$ to
$0$, so no one deviates — yet one is strictly better for everyone. This is the
crux of multi-agent learning that single-agent RL never faces: even with _identical_
rewards and full cooperation, independent learners can converge to the safe,
worse equilibrium $(H, H)$, because reaching the good one requires the risky belief
that your partner will also pick stag. The problem is not conflicting incentives;
it is **coordinated equilibrium selection**, and no single agent controls it.

$$
% caption: The stag-hunt payoff structure. Two pure Nash equilibria exist: the
% payoff-dominant (Stag, Stag) worth 4 each, and the risk-dominant (Hare, Hare)
% worth 3 each. Independent learners often converge to the safe (Hare, Hare)
% because unilaterally choosing Stag risks the 0 payoff if the partner defects.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  cell/.style={draw, minimum width=20mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{grn}{HTML}{1F9D4D}
  \node[cell, fill=grn!12, draw=grn] (ss) at (0,0)   {(4, 4)\\best, risky};
  \node[cell] (sh) at (2.1,0) {(0, 3)};
  \node[cell] (hs) at (0,-1.5) {(3, 0)};
  \node[cell, fill=acc!10, draw=acc] (hh) at (2.1,-1.5) {(3, 3)\\safe};
  \node[anchor=east, font=\scriptsize] at (-1.3,0)    {P1: Stag};
  \node[anchor=east, font=\scriptsize] at (-1.3,-1.5) {P1: Hare};
  \node[anchor=south, font=\scriptsize] at (0,0.75)   {P2: Stag};
  \node[anchor=south, font=\scriptsize] at (2.1,0.75) {P2: Hare};
  \node[grn, anchor=west, font=\scriptsize] at (3.2,0)    {Nash (payo\/f\/f-dominant)};
  \node[acc, anchor=west, font=\scriptsize] at (3.2,-1.5) {Nash (risk-dominant)};
\end{tikzpicture}
$$

## Non-stationarity: the moving target

Here is the difficulty that everything downstream is built to address. From the vantage
point of one agent, the others are _part of the environment_. Their policies determine how
the world responds to that agent's actions. But the others are **learning**, so their
policies keep changing — which means the environment that agent $i$ faces keeps changing
underneath it. The transition and reward that agent $i$ effectively experiences,
marginalizing out the others' actions,

$$
p_i(s' \mid s, a_i) \;=\; \sum_{\mathbf{a}_{-i}} p(s' \mid s, a_i, \mathbf{a}_{-i}) \prod_{j \neq i} \pi_j(a_j \mid s),
$$

depend on the other agents' policies $\pi_j$ through the product $\prod_{j\neq i}\pi_j$.
When those policies change, $p_i$ changes. The environment is **non-stationary** from any
single agent's local view, and non-stationarity breaks the guarantee that props up every
single-agent method: the Markov property no longer holds for agent $i$ in isolation,
because the best prediction of the future now depends on the hidden, drifting policies of
the others, not on the state alone.[^lowe]

> **Definition (Non-stationarity).** From the perspective of a single agent in a
> multi-agent system, the environment's effective dynamics $p_i(s' \mid s, a_i)$ and reward
> change over time because the other agents' policies $\{\pi_j\}_{j \neq i}$ are themselves
> being learned. A value function or replay transition that was accurate under the old
> $\{\pi_j\}$ becomes stale once the others update — the target the agent is chasing moves
> as the agent chases it.

The figure shows the pathology. Agent 1 is fitting a value function to its
environment. But that environment is defined partly by agent 2's policy, and while agent 1
climbs toward the optimum, agent 2 shifts the optimum by learning. Agent 1 is aiming at a
target that its opponent's learning keeps relocating.

$$
% caption: The moving-target problem. Agent 1 (blue) descends toward the best response to
% agent 2, but each time agent 2 updates its policy the optimum moves, so agent 1's path
% never settles — it chases a target that recedes as it learns.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{grn}{HTML}{1F9D4D}
  % axes: agent-1 policy space
  \draw[black, ->] (-0.2,0) -- (9.4,0) node[anchor=north east, text=black] {agent 1 policy};
  \draw[black, ->] (-0.2,0) -- (-0.2,3.4) node[anchor=south east, text=black] {agent 1 loss};
  % three successive loss bowls (as agent 2 keeps changing them)
  \draw[black, thin] (0.2,2.9) parabola bend (1.4,0.55) (2.6,2.9);
  \draw[black, thin] (2.8,2.9) parabola bend (4.0,0.55) (5.2,2.9);
  \draw[acc, very thick] (5.6,2.9) parabola bend (6.8,0.55) (8.0,2.9);
  % moving optima
  \fill[grn] (1.4,0.55) circle (2.4pt);
  \fill[grn] (4.0,0.55) circle (2.4pt);
  \fill[grn] (6.8,0.55) circle (2.4pt);
  \node[grn, anchor=north, font=\scriptsize] at (1.4,0.42) {opt 1};
  \node[grn, anchor=north, font=\scriptsize] at (4.0,0.42) {opt 2};
  \node[grn, anchor=north, font=\scriptsize] at (6.8,0.42) {opt 3};
  % arrows: the optimum recedes as agent 2 updates
  \draw[->, red, thick] (1.9,0.85) to[bend left=18] node[midway, above, font=\scriptsize, text=red] {agent 2 updates} (3.5,0.85);
  \draw[->, red, thick] (4.5,0.85) to[bend left=18] (6.3,0.85);
\end{tikzpicture}
$$

Non-stationarity is why you cannot simply run single-agent RL per agent and expect the
guarantees to survive. A replay buffer, the device that makes DQN and DDPG sample-efficient,
becomes actively harmful: a transition stored when the other agents behaved one way no
longer reflects how they behave now, so it teaches the agent about a world that no longer
exists. Every design decision below is, at bottom, a way to cope with this one fact.

## The naive baselines

Before the modern paradigm, two obvious approaches bracket the design space. Both fail in
instructive, opposite ways.

### Independent learning

The simplest thing to do is ignore the problem: give each agent its own single-agent
algorithm — its own Q-network, its own DDPG — and let it treat every other agent as part of
the environment. This is **independent Q-learning** (IQL) or, with policy gradients,
independent learners.[^tan] Each agent $i$ learns $Q_i(s, a_i)$ as if it were alone.

The appeal is that it is trivial to implement and, empirically, it **often works** — enough
that it remains a standard baseline. The problem is that it comes with **no convergence
guarantee**. Each agent's environment is non-stationary (the section above), so the Bellman
target each agent regresses toward is a moving one; nothing forces the coupled learning to
settle, and it can oscillate or diverge. Independent learning is the "ignore it" strategy:
frequently fine, never provably fine.

### Centralized control

The opposite extreme takes the non-stationarity away by refusing to have multiple agents at
all. Treat the whole system as **one** agent whose action is the joint action $\mathbf{a} =
(a_1, \ldots, a_N)$, and learn a single policy over that joint action space. Now the
environment is a genuine MDP again — there is only one learner, so nothing is
non-stationary — and every single-agent guarantee returns.

The catch is the size of the joint action space. If each of $N$ agents has $|\mathcal{A}|$
actions, the joint space has $|\mathcal{A}|^N$ — it grows **exponentially** in the number of
agents. A team of ten agents with ten actions each has $10^{10}$ joint actions to evaluate
per state. Worse, centralized control assumes a central controller with access to every
agent's observations at execution time, which many settings forbid: a robot swarm acts on
local sensors, a player sees only its own screen.

$$
% caption: The two naive extremes. Independent learners (left) each run a local algorithm
% and see a non-stationary world with no convergence guarantee; a central controller
% (right) restores stationarity but must search a joint action space of size
% $|\mathcal{A}|^N$, exponential in the number of agents.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  ag/.style={circle, draw, minimum size=8mm, inner sep=0pt, font=\scriptsize},
  big/.style={draw, thick, minimum width=30mm, minimum height=15mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % --- left: independent ---
  \node[ag, draw=acc, text=acc] (a1) at (0,1.0) {A1};
  \node[ag, draw=acc, text=acc] (a2) at (1.4,-0.2) {A2};
  \node[ag, draw=acc, text=acc] (a3) at (-1.4,-0.2) {A3};
  \node[anchor=north, text=black, font=\scriptsize] at (0,-1.4) {independent:};
  \node[anchor=north, text=black, font=\scriptsize] at (0,-1.9) {N learners, no guarantee};
  \draw[<->, black, dashed] (a1) -- (a2);
  \draw[<->, black, dashed] (a1) -- (a3);
  \draw[<->, black, dashed] (a2) -- (a3);
  % --- right: centralized ---
  \begin{scope}[xshift=6.4cm]
    \node[big, draw=red, text=red] (c) at (0,0.0) {central controller\\action = (a1,...,aN)};
    \node[anchor=north, text=black, font=\scriptsize] at (0,-1.4) {centralized:};
    \node[anchor=north, text=black, font=\scriptsize] at (0,-1.9) {joint space grows as A-to-the-N};
  \end{scope}
\end{tikzpicture}
$$

Independent learning scales but does not converge; centralized control converges but does
not scale. The dominant modern paradigm is a hybrid that takes the good half of each.

## Centralized training, decentralized execution

The two hard constraints apply at **different times**. During
**training** — offline, in simulation, on your own hardware — you can afford a global view:
you control the whole simulator and can hand any component all the agents' observations and
actions. During **execution** — when the trained agents act in the real deployment — each
agent may only see its own local observation, and must act on that alone. So separate the
two phases. Use the global view where it is free (training) and demand only local
information where it is required (execution). This is **centralized training with
decentralized execution** (CTDE), the paradigm that organizes almost all of modern deep
multi-agent RL.[^ctde]

> **Definition (Centralized training, decentralized execution).** A training scheme in
> which a **centralized critic** (or value function) is given the full joint information —
> the global state $\mathbf{x}$ and every agent's action $(a_1, \ldots, a_N)$ — and is used
> only to compute learning targets during training. Each agent's **actor** $\pi_i(a_i \mid
> o_i)$ conditions only on that agent's local observation $o_i$, so at execution time the
> centralized critic is discarded and the agents act independently from local observations.

$$
% caption: The two phases of CTDE. At training time (left) a centralized critic
% reads the global state and every agent's action, so its learning target is
% stationary; at execution time (right) the critic is discarded and each actor runs
% on its own local observation alone. The global view is used only where it is free.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  ag/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\scriptsize},
  cr/.style={draw, minimum width=30mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % training
  \node[ag, draw=acc, text=acc] (t1) at (-0.9,0.9) {A1};
  \node[ag, draw=acc, text=acc] (t2) at (0.9,0.9)  {A2};
  \node[cr, draw=red, text=red] (crit) at (0,-0.9) {central critic (sees all)};
  \draw[->, red] (t1) -- (crit); \draw[->, red] (t2) -- (crit);
  \node[black, anchor=north, font=\scriptsize] at (0,-1.6) {TRAINING: global view};
  % divider
  \draw[black, dashed] (2.4,-1.9) -- (2.4,1.6);
  % execution
  \begin{scope}[xshift=5.4cm]
    \node[ag, draw=acc, text=acc] (e1) at (-0.9,0.9) {A1};
    \node[ag, draw=acc, text=acc] (e2) at (0.9,0.9)  {A2};
    \draw[->, black] (-0.9,0) -- (e1.south) node[anchor=north, pos=0, font=\scriptsize, text=black] {o1};
    \draw[->, black] (0.9,0) -- (e2.south) node[anchor=north, pos=0, font=\scriptsize, text=black] {o2};
    \node[black, anchor=north, font=\scriptsize] at (0,-1.6) {EXECUTION: local obs only};
  \end{scope}
\end{tikzpicture}
$$

The centralized critic is what defeats non-stationarity. A critic that sees every agent's
action $Q_i(\mathbf{x}, a_1, \ldots, a_N)$ faces a **stationary** learning target: if you
know what all agents did, the environment's response is fixed, so the moving-target problem
disappears from the critic's point of view. The actors stay decentralized because they need
to run without the others' information at test time. Training gets the global view; execution
gets the local constraint.

### MADDPG

The canonical CTDE algorithm is **multi-agent DDPG** (MADDPG), from Lowe et al. (2017).[^lowe]
It takes the [DDPG](/reinforcement-learning/modern-deep-rl/continuous-control) actor-critic
and gives each agent a centralized critic. Agent $i$ has a decentralized deterministic actor
$\mu_i(o_i)$ that sees only its own observation, and a centralized critic
$Q_i(\mathbf{x}, a_1, \ldots, a_N)$ that sees the global state and **all** agents' actions.

$$
% caption: The MADDPG architecture. Each agent's actor mu-i acts on its own local
% observation o-i (decentralized execution), while a centralized critic Q-i sees the
% global state x and every agent's action a-1..a-N (centralized training). At test time the
% critics are dropped and only the local actors remain.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  act/.style={draw, minimum width=22mm, minimum height=11mm, align=center, font=\scriptsize},
  crit/.style={draw, minimum width=40mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % actors row (decentralized)
  \node[act, draw=acc, text=acc, thick] (m1) at (-3.4,0) {actor mu-1(o-1)};
  \node[act, draw=acc, text=acc, thick] (m2) at (0,0)    {actor mu-2(o-2)};
  \node[act, draw=acc, text=acc, thick] (m3) at (3.4,0)  {actor mu-N(o-N)};
  % local obs in (label to the left of each short arrow to avoid overlap)
  \draw[->, black] (-3.4,1.25) -- (m1.north) node[anchor=east, pos=0, text=black, font=\scriptsize] {o-1};
  \draw[->, black] (0,1.25) -- (m2.north) node[anchor=east, pos=0, text=black, font=\scriptsize] {o-2};
  \draw[->, black] (3.4,1.25) -- (m3.north) node[anchor=east, pos=0, text=black, font=\scriptsize] {o-N};
  % centralized critic below
  \node[crit, draw=red, text=red] (q) at (0,-2.6) {centralized critic Q-i(x, a-1,...,a-N)};
  % actions feed critic
  \draw[->, red, thick] (m1.south) -- (q.north west) node[midway, left, font=\scriptsize] {a-1};
  \draw[->, red, thick] (m2.south) -- (q.north) node[midway, right, font=\scriptsize] {a-2};
  \draw[->, red, thick] (m3.south) -- (q.north east) node[midway, right, font=\scriptsize] {a-N};
  % global state into critic
  \node[anchor=west, text=black, font=\scriptsize] at (3.2,-2.6) {+ global state x};
  \draw[->, black] (3.15,-2.6) -- (q.east);
  % gradient back to actor i (example: to mu-2)
  \draw[->, red, thick, dashed] (q.west) to[out=180,in=-90] node[midway, left, font=\scriptsize, text=red] {grad-a Q} (m1.south west);
\end{tikzpicture}
$$

The training rules are DDPG's, lifted to the joint view. The critic for agent $i$ regresses
toward a bootstrapped target computed from the **target actors of all agents**, so the value
is conditioned on everyone's next action:

$$
y \;=\; r_i + \gamma\, Q_i^{\,\mu'}\!\big(\mathbf{x}', a_1', \ldots, a_N'\big)\Big|_{a_j' = \mu_j'(o_j')},
\qquad
\mathcal{L}(\phi_i) = \mathbb{E}\big[(Q_i(\mathbf{x}, a_1, \ldots, a_N) - y)^2\big].
$$

Each actor is improved by the deterministic policy gradient through **its own** centralized
critic — the critic that already accounts for the others' actions — while every other agent's
action is held fixed at what the buffer recorded:

$$
\nabla_{\theta_i} J \;=\; \mathbb{E}\!\left[\nabla_{\theta_i} \mu_i(o_i)\;\nabla_{a_i} Q_i(\mathbf{x}, a_1, \ldots, a_N)\big|_{a_i = \mu_i(o_i)}\right].
$$

Because the critic conditions on the joint action, its target is stationary even though
each actor is changing — that is precisely how CTDE removes non-stationarity. The single
change from DDPG is the critic's input: local $Q(s, a)$ becomes joint
$Q_i(\mathbf{x}, a_1, \ldots, a_N)$.

```algorithm
caption: $\textsc{MADDPG}$ — centralized-critic actor-critic for $N$ agents
input: for each agent $i$: actor $\mu_{\theta_i}$, centralized critic $Q_{\phi_i}$
initialize targets $\theta_i', \phi_i'$ for all $i$; empty shared replay buffer $\mathcal{D}$
for each step do
  for each agent $i$ do
    select $a_i \gets \mu_{\theta_i}(o_i) + \mathcal{N}$ // local obs, exploration noise
  execute joint action $\mathbf{a}$, observe $\{r_i\}$, next state $\mathbf{x}'$
  store $(\mathbf{x}, \mathbf{a}, \{r_i\}, \mathbf{x}')$ in $\mathcal{D}$
  sample a minibatch of joint transitions from $\mathcal{D}$
  for each agent $i$ do
    $a_j' \gets \mu_{\theta_j'}(o_j')$ for all $j$ // target actors of every agent
    $y \gets r_i + \gamma\, Q_{\phi_i'}(\mathbf{x}', a_1', \ldots, a_N')$
    $\phi_i \gets \phi_i - \eta\,\nabla_{\phi_i}\,(Q_{\phi_i}(\mathbf{x}, a_1, \ldots, a_N) - y)^2$ // centralized critic
    $\theta_i \gets \theta_i + \eta\,\nabla_{\theta_i}\, Q_{\phi_i}(\mathbf{x}, \ldots, \mu_{\theta_i}(o_i), \ldots)$ // local actor
  soft-update every $\theta_i', \phi_i'$
```

MADDPG works across all three regimes — cooperative, competitive, and mixed — because each
agent keeps its own reward $r_i$ and its own critic; nothing assumes the agents agree. In
the paper's environments (a set of particle worlds with predators, prey, and communication)
it learns coordinated and competitive behaviors that independent learners cannot.

### Value factorization for cooperation

When the game is purely **cooperative** — all agents share one team reward — a different and
cheaper idea applies. The team wants to learn one joint value $Q_{\text{tot}}(\mathbf{x},
\mathbf{a})$, but that object is exponential in $N$ (the centralized-control problem again),
and at execution time each agent must still pick its action from its **own** local value.
The fix is to **factorize** the joint value into per-agent pieces and require the
factorization to be consistent with greedy local action selection.

**Value Decomposition Networks** (VDN) take the simplest factorization: the joint value is
the **sum** of per-agent utilities.[^vdn]

$$
Q_{\text{tot}}(\mathbf{x}, \mathbf{a}) \;=\; \sum_{i=1}^{N} Q_i(o_i, a_i).
$$

The point of the sum is a property called **decentralizability**: the joint action that
maximizes the sum is the one each agent gets by maximizing its own $Q_i$ locally,
$\arg\max_{\mathbf{a}} Q_{\text{tot}} = (\arg\max_{a_1} Q_1, \ldots, \arg\max_{a_N} Q_N)$.
So the team can be trained centrally on $Q_{\text{tot}}$ (regressing it toward the shared
Bellman target) yet executed decentrally, each agent taking $\arg\max_{a_i} Q_i$ from its
own local observation. The sum is a strong assumption, though: it forces each agent's
contribution to be independent of the others.

**QMIX** relaxes the sum to any **monotonic** combination.[^qmix] It keeps the property that
lets local greedy action selection agree with the global argmax while allowing far richer
joint values. The requirement is that $Q_{\text{tot}}$ be **monotonically increasing** in
each agent's $Q_i$:

$$
\frac{\partial Q_{\text{tot}}}{\partial Q_i} \;\geq\; 0 \quad \text{for all } i.
$$

Monotonicity is exactly enough to guarantee $\arg\max_{\mathbf{a}} Q_{\text{tot}} =
(\arg\max_{a_i} Q_i)_i$ — if raising any agent's local value can never lower the team value,
then everyone maximizing locally maximizes the team. QMIX realizes this with a **mixing
network** that combines the per-agent $Q_i$ into $Q_{\text{tot}}$ using weights produced by a
**hypernetwork** from the global state, with the weights constrained non-negative to enforce
monotonicity. VDN is the special case where the mixer is a plain sum.

$$
% caption: Value factorization for cooperation. VDN sums the per-agent utilities Q-i;
% QMIX combines them through a monotonic mixing network whose non-negative weights come
% from a hypernetwork reading the global state x. Both guarantee that local argmax over
% each Q-i matches the global argmax over Q-tot.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  q/.style={draw, minimum width=17mm, minimum height=10mm, align=center, font=\scriptsize},
  mix/.style={draw, minimum width=44mm, minimum height=11mm, align=center, font=\scriptsize},
  top/.style={draw, thick, minimum width=26mm, minimum height=10mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % per-agent Q
  \node[q, draw=acc, text=acc] (q1) at (-3.0,0) {Q-1(o-1,a-1)};
  \node[q, draw=acc, text=acc] (q2) at (0,0)    {Q-2(o-2,a-2)};
  \node[q, draw=acc, text=acc] (q3) at (3.0,0)  {Q-N(o-N,a-N)};
  % mixing network
  \node[mix] (mx) at (0,-1.9) {monotonic mixing network};
  \draw[->, acc, thick] (q1.south) -- (mx.north west);
  \draw[->, acc, thick] (q2.south) -- (mx.north);
  \draw[->, acc, thick] (q3.south) -- (mx.north east);
  % hypernetwork weights from global state
  \node[q, draw=red, text=red] (hyp) at (5.4,-1.9) {hypernet(x)};
  \draw[->, red, thick, dashed] (hyp.west) -- (mx.east) node[midway, above, font=\scriptsize, text=red] {weights $\ge$ 0};
  % Q-tot out
  \node[top, draw=red, text=red] (qt) at (0,-3.7) {Q-tot};
  \draw[->, thick] (mx.south) -- (qt.north);
\end{tikzpicture}
$$

**A worked factorization.** Take two agents each with actions $\{0, 1\}$ and a true
joint value that rewards _matching_: $Q_{\text{tot}}(0,0) = Q_{\text{tot}}(1,1) = 2$,
$Q_{\text{tot}}(0,1) = Q_{\text{tot}}(1,0) = 0$. Can VDN's sum $Q_1(a_1) + Q_2(a_2)$
represent this? It would need $Q_1(0)+Q_2(0) = 2$ and $Q_1(1)+Q_2(1) = 2$ but
$Q_1(0)+Q_2(1) = 0$ and $Q_1(1)+Q_2(0) = 0$. Adding the first two gives $4$; adding
the last two gives $0$; but both sums equal $Q_1(0)+Q_1(1)+Q_2(0)+Q_2(1)$, a
contradiction ($4 \ne 0$). So VDN _cannot_ represent this coordination payoff — the
sum forces each agent's contribution to be independent of the other's, exactly the
wrong assumption when the reward depends on agreement. QMIX's monotonic mixer, whose
weights come from the global state, can (the state-conditioned mixing breaks the
additivity). This is the **representational limit** VDN pays for its simplicity, and
why QMIX dominates it on coordination-heavy benchmarks.

But QMIX has its own limit, and it recurs. Monotonicity
forbids representing any payoff where an agent's _best_ action depends on what the
others do in a non-monotone way — the classic failure is **relative
overgeneralization**, where the safe action looks best on average across the
partner's choices even though a coordinated risky action is globally optimal, and
QMIX's monotonic mixer collapses onto the safe action. This is the QMIX-level echo
of the stag hunt: the factorization structure can bias learning toward the
risk-dominant equilibrium.

The trade is scope for cost. MADDPG handles competitive and mixed games at the price of a
full joint-action critic per agent; VDN and QMIX handle only cooperative games but factor
the joint value into cheap per-agent pieces, so they scale to more agents and are the
standard choice for cooperative benchmarks like the StarCraft multi-agent challenge.

### Counterfactual credit assignment (COMA)

Value factorization answers "how do we get decentralized greedy actions from a
joint value?" A different question, just as central to cooperation, is the
**multi-agent credit-assignment problem**: when the whole team shares one reward and
the team does well, _which agent's action deserves the credit?_ An agent that did
nothing useful still sees the high team reward and reinforces its idle behavior.

**COMA** (Counterfactual Multi-Agent policy gradients, Foerster et al. 2018) solves
this with a **counterfactual baseline**.[^coma] It keeps a centralized critic
$Q(\mathbf{x}, \mathbf{a})$ and, for each agent $i$, computes how much better the
action $a_i$ agent $i$ actually took was than the average over all the actions it
_could_ have taken, holding every other agent's action fixed. The counterfactual
advantage is

$$
A_i(\mathbf{x}, \mathbf{a}) \;=\; Q(\mathbf{x}, \mathbf{a})
\;-\; \sum_{a_i'} \pi_i(a_i' \mid o_i)\, Q\bigl(\mathbf{x}, (a_i', \mathbf{a}_{-i})\bigr).
$$

The subtracted term marginalizes out agent $i$'s own action while freezing the
others', so it isolates $i$'s _individual_ contribution from the team's shared
outcome. Because the critic is centralized (it sees $\mathbf{x}$ and all actions),
this counterfactual is cheap to compute — one forward pass per alternative action —
and it removes the confound that makes shared-reward policy gradients so noisy.
COMA is the credit-assignment counterpart to QMIX's action-selection factorization:
both are CTDE, but one factors the value and the other factors the _blame_.

$$
% caption: The counterfactual baseline in COMA. To assign credit for the shared
% team reward, agent i's advantage compares the actual joint value against the
% expected value if agent i had instead sampled a different action from its own
% policy, holding the other agents' actions fixed. This isolates one agent's
% contribution from the team outcome.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bar/.style={draw, minimum width=8mm}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (-0.2,0) -- (8.6,0) node[anchor=north, black, font=\footnotesize] {agent i alternative actions};
  \draw[->, black] (0,-0.2) -- (0,3.6) node[anchor=east, black, font=\footnotesize] {joint value Q};
  % bars for alternatives
  \foreach \x/\h in {1.0/1.4,2.2/2.0,3.4/1.1,4.6/2.6,5.8/1.7,7.0/1.3} \fill[acc!35] (\x,0) rectangle (\x+0.7,\h);
  % the actual action taken
  \fill[acc] (4.6,0) rectangle (5.3,2.6);
  \node[acc, anchor=south, font=\scriptsize] at (4.95,2.6) {action taken};
  % baseline (policy-weighted average)
  \draw[red, thick, dashed] (0.6,1.65) -- (8.2,1.65);
  \node[red, anchor=west, font=\scriptsize] at (7.4,1.9) {counterfactual baseline};
  \draw[->, red, thick] (5.6,1.68) -- (5.6,2.55) node[midway, right, font=\scriptsize] {advantage};
\end{tikzpicture}
$$

## Where this leaves us

Multi-agent RL is a genuinely different problem, and the pieces now assembled say why.
The **Markov game** generalizes the MDP by giving every agent its own actions and
reward; **non-stationarity** is its central pathology, because each agent's environment
includes the others, who are themselves learning, so the ground never stops moving; and
the **naive baselines** — independent learners and a single joint learner — fail on
exactly that, one by ignoring the non-stationarity and the other by drowning in the
exponential joint action space.

The dominant fix is **centralized training with decentralized execution**: let a critic
see everything during training so it faces a stationary target, but keep each agent's
executed policy dependent only on its own local observation. MADDPG, VDN, and QMIX are
three points on that design — a centralized critic per agent, and two ways of factoring
a joint value so decentralized greedy actions still maximize it.

CTDE handles cooperation and mixed settings. The purely competitive case has its own
engine — an agent that generates its own curriculum by playing against copies of
itself — which produced the landmark game-playing systems, and raises the question of
what "solved" even means once there is an opponent. Self-play, those systems, and the
equilibrium solution concepts continue in
[Multi-Agent RL: Self-Play and Solution Concepts](/reinforcement-learning/modern-deep-rl/multi-agent-rl-part-2).

[^shapley]: **Shapley (1953)**, "Stochastic Games," _Proceedings of the National Academy of Sciences_ — introduces the stochastic (Markov) game, a state process controlled jointly by several players each with their own payoff, generalizing both matrix games and, in the single-player case, what would later be formalized as the MDP.
[^lowe]: **Lowe, Wu, Tamar, Harb, Abbeel, Mordatch (2017)**, "Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments," _NeurIPS_ — MADDPG: a decentralized deterministic actor per agent with a centralized critic conditioned on the joint action $Q_i(\mathbf{x}, a_1, \ldots, a_N)$, which makes each critic's target stationary and so addresses the non-stationarity that breaks independent learning; demonstrated on cooperative, competitive, and mixed particle environments.
[^tan]: **Tan (1993)**, "Multi-Agent Reinforcement Learning: Independent vs. Cooperative Agents," _ICML_ — the independent-learners baseline, in which each agent runs its own Q-learning and treats the others as part of the environment; effective in practice but without convergence guarantees under the resulting non-stationarity.
[^ctde]: The centralized-training / decentralized-execution framing is developed across **Lowe et al. (2017)** (above) and **Foerster, Assael, de Freitas, Whiteson (2016)**, "Learning to Communicate with Deep Multi-Agent Reinforcement Learning," _NeurIPS_ — using centralized information during training while constraining execution to each agent's local observation.
[^vdn]: **Sunehag et al. (2018)**, "Value-Decomposition Networks For Cooperative Multi-Agent Learning," _AAMAS_ — VDN: factor the team value as $Q_{\text{tot}} = \sum_i Q_i(o_i, a_i)$, so that a local $\arg\max$ over each $Q_i$ recovers the global $\arg\max$ over $Q_{\text{tot}}$, allowing centralized training and decentralized greedy execution in cooperative games.
[^qmix]: **Rashid, Samvelyan, de Witt, Farquhar, Foerster, Whiteson (2018)**, "QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning," _ICML_ — QMIX generalizes VDN's sum to any mixing that is monotonic in each agent's $Q_i$ ($\partial Q_{\text{tot}}/\partial Q_i \geq 0$), realized by a hypernetwork-parameterized mixing network with non-negative weights, preserving the local-global $\arg\max$ consistency while representing far richer joint value functions.
[^coma]: **Foerster, Farquhar, Afouras, Nardelli, Whiteson (2018)**, "Counterfactual Multi-Agent Policy Gradients," _AAAI_ — COMA: a centralized critic plus a counterfactual baseline that marginalizes out one agent's action while fixing the others', isolating that agent's contribution to the shared team reward and taming multi-agent credit assignment.