---
title: "Multi-Agent RL: Self-Play and Solution Concepts"
module: Modern Deep Reinforcement Learning
moduleNumber: 5
lessonNumber: 14
order: 514
summary: >
  A companion to the Markov-games lesson. In the purely competitive setting, an agent
  can generate its own training curriculum by playing against copies of itself —
  self-play, the method behind AlphaGo, OpenAI Five, and AlphaStar. We develop why
  self-play produces an ever-improving opponent, the systems it built, and then the
  equilibrium solution concepts (Nash, correlated, coarse-correlated) that define
  what "solved" means once there is an opponent, closing with PSRO, MAPPO, and the
  language-model-agent frontier.
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)"
---

This builds on
[Multi-Agent RL: Markov Games and Centralized Training](/reinforcement-learning/modern-deep-rl/multi-agent-rl),
which built the Markov game, diagnosed non-stationarity as its central pathology, showed
why independent and joint learners both fail, and developed centralized training with
decentralized execution (MADDPG, VDN, QMIX) as the dominant fix for cooperative and
mixed settings.

That paradigm addresses agents that share or partly share a goal. The purely
competitive, zero-sum case has its own mechanism — and it is where multi-agent RL has
produced its most visible results. This lesson takes up self-play, the systems it
built, and the game-theoretic language for what those systems converge to.

## Self-play as a curriculum

CTDE is the answer for a **fixed** roster of agents trained together. Competitive games
admit a second idea that turns the multi-agent difficulty into an advantage. A two-player
zero-sum game has no external teacher and no dataset of expert play — but the agent can
play **against itself**. Each copy is an opponent exactly as strong as the current agent, so
the difficulty of the training signal tracks the agent's ability. Competition **generates its
own curriculum**.

> **Definition (Self-play).** A training procedure for competitive games in which an agent
> improves by playing against copies of itself (current or past versions). Because the
> opponent's strength tracks the agent's own, self-play produces an automatic curriculum:
> the challenge scales with competence, with no human-designed difficulty ladder and no
> external opponent required.

This is the mechanism behind the case studies in the
[deep-RL case-studies](/reinforcement-learning/deep-rl/case-studies) lesson. TD-Gammon
learned backgammon from self-play in the 1990s; **AlphaGo Zero** and **AlphaZero** learned
Go, chess, and shogi from nothing but the rules and self-play, using the game outcome as the
reward and Monte-Carlo tree search as a policy-improvement operator. There is no opponent
model, no non-stationarity fix, and no CTDE machinery — the second agent simply _is_ the
first agent, and the moving target becomes the training curriculum.

$$
% caption: The self-play loop. The current policy plays games against copies of itself; the
% outcomes train an improved policy; that improved policy becomes the new opponent, and the
% cycle raises the difficulty automatically as the agent gets stronger.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=26mm, minimum height=12mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=acc, text=acc, thick] (pol)  at (0,0)    {current policy};
  \node[box] (play) at (4.6,0)   {play vs. self};
  \node[box] (imp)  at (4.6,-2.4) {train on outcomes};
  \node[box, draw=red, text=red] (new) at (0,-2.4) {improved policy};
  \draw[->, acc, thick] (pol) -- (play) node[midway, above, font=\scriptsize] {generate games};
  \draw[->, thick] (play) -- (imp) node[midway, right, font=\scriptsize] {win / loss};
  \draw[->, thick] (imp) -- (new) node[midway, below, font=\scriptsize] {policy update};
  \draw[->, red, thick] (new) -- (pol) node[midway, left, font=\scriptsize, text=red] {becomes opponent};
\end{tikzpicture}
$$

### Landmark systems

Scaling self-play from board games to real-time, partially observed, multi-agent video games
produced the field's most visible results. Two systems stand out, both from 2019.

**OpenAI Five** learned to play _Dota 2_, a five-versus-five game with long horizons (tens of
thousands of time steps per match), a large continuous-ish action space, and imperfect
information. Five separate LSTM-based policies, one per hero, were trained with large-scale
[PPO](/reinforcement-learning/deep-rl/actor-critic-and-ppo) entirely by self-play, on a
scale of experience equivalent to hundreds of years of play per day. In 2019 it defeated the
reigning world-champion human team.[^five] The five agents shared no explicit
coordination mechanism — each acted on its own observations — yet team play **emerged** from
the shared reward and self-play pressure alone.

**AlphaStar** learned _StarCraft II_, another real-time, imperfect-information game, but with
a wrinkle self-play alone handles badly: a single line of self-play can cycle
through strategies that each beat the last (rock-paper-scissors dynamics) without
ever getting globally stronger. AlphaStar's fix was a **league**: a population of agents
including "main" agents and "exploiter" agents whose job is to find and punish the weaknesses
of the others, so the main agents must become robust to a whole distribution of opponents
rather than to one drifting self-copy. AlphaStar reached Grandmaster level, above 99.8% of
ranked human players.[^alphastar]

The same self-play pressure produces **emergent behavior** even without a game to
win. In OpenAI's hide-and-seek environment, agents in a simple physical world discovered, in
succession, a sequence of strategies and counter-strategies nobody scripted: hiders learned
to build forts by moving boxes, seekers learned to use ramps to jump in, hiders learned to
steal the ramps first, and seekers eventually learned to "box-surf" — exploiting a physics
bug to ride a box over the walls. Each new capability appeared only because the opponents'
improvement made it worth discovering — an **autocurriculum** driven purely by
competition.[^hns]

## Solution concepts: what "solved" means

For a single-agent MDP, "solved" is unambiguous: an optimal policy maximizing expected
return exists. With $N$ agents and conflicting rewards there is no single objective to
maximize — agent $i$ improving may lower agent $j$'s return — so a solution needs a
game-theoretic definition. The central one is the **Nash equilibrium**.

The setting also splits by how the per-agent rewards $R_i$ relate:

| Setting | Reward structure | Solution target |
| --- | --- | --- |
| Cooperative | shared $R_i = R$ for all $i$ | joint-return maximum (CTDE, VDN, QMIX, MAPPO) |
| Competitive (zero-sum, 2-player) | $R_1 = -R_2$ | minimax value; unique equilibrium value |
| Mixed / general-sum | arbitrary $R_i$ | Nash / (coarse-)correlated equilibrium |

> **Definition (Nash equilibrium).** A joint policy $(\pi_1^\ast, \ldots, \pi_N^\ast)$ is a Nash
> equilibrium if no agent can improve its own expected return by unilaterally changing its
> policy while the others hold theirs fixed: for every agent $i$ and every alternative
> $\pi_i$,
> $$
> \mathbb{E}\big[R_i \mid \pi_i^\ast, \boldsymbol{\pi}_{-i}^\ast\big] \;\geq\; \mathbb{E}\big[R_i \mid \pi_i, \boldsymbol{\pi}_{-i}^\ast\big].
> $$
> At a Nash equilibrium every agent is playing a **best response** to the others; the
> configuration is self-consistent, so no one has a reason to move.

A Nash equilibrium is the natural resting point of rational learners: if learning converges
at all, it converges somewhere no agent wants to deviate. Two hard caveats. First, equilibria
need not be **unique** — a game can have many, and different learning dynamics land on
different ones. Second, a Nash equilibrium is only a _fixed point_, not a guarantee that a
learning algorithm **reaches** it; convergence is provable only in special cases (two-player
zero-sum, certain potential games), and general Markov games carry no such guarantee. This is
non-stationarity's theoretical counterpart: the coupling that makes the environment a moving
target also makes the destination ambiguous.

Relaxing the requirement of _independent_ policies gives two weaker but computationally
tractable concepts. A **correlated equilibrium** allows a shared signal $c$ that recommends an
action to each agent; the joint distribution $\sigma$ over actions is a correlated equilibrium
if no agent gains by deviating from its recommendation given $c$. A **coarse-correlated
equilibrium (CCE)** is weaker still: no agent gains by opting out of $\sigma$ before seeing its
recommendation,

$$
\mathbb{E}_{a \sim \sigma}\big[R_i(a)\big] \;\geq\; \mathbb{E}_{a \sim \sigma}\big[R_i(a_i', a_{-i})\big] \quad \forall i,\, \forall a_i'.
$$

Every Nash equilibrium is correlated, and every correlated equilibrium is a CCE; the weaker
concepts are the fixed points that no-regret learning dynamics actually converge to.

For the **two-player zero-sum** case the picture is cleaner. The minimax theorem gives the
game a well-defined value and identifies the equilibrium as the minimax point, where each
player maximizes its worst-case outcome:

$$
v^\ast \;=\; \max_{\pi_1} \min_{\pi_2} \, \mathbb{E}\big[R_1 \mid \pi_1, \pi_2\big] \;=\; \min_{\pi_2} \max_{\pi_1} \, \mathbb{E}\big[R_1 \mid \pi_1, \pi_2\big].
$$

This is where self-play has its strongest justification: in a zero-sum game, best-responding
to yourself drives toward the minimax-optimal strategy — why AlphaZero-style self-play
converges to superhuman play in Go and chess, with no equally clean guarantee in general mixed
games.

## PSRO, MAPPO, and language-model agents

Multi-agent deep RL moved quickly after the systems above, in three directions the
classic MDP-centric text does not reach.

**A game-theoretic training loop: PSRO.** Self-play with a single opponent can cycle
(rock-paper-scissors dynamics); AlphaStar's league was one fix. The general
formulation is **Policy-Space Response Oracles** (Lanctot et al. 2017), which
maintains a _population_ of policies, builds the empirical payoff matrix of the
population playing itself, computes a meta-strategy over it (a Nash or a
diversity-seeking mixture), and trains a new best-response policy against that
meta-strategy before adding it to the population.[^psro] PSRO unifies self-play,
fictitious play, and the double-oracle method under one algorithm, and its
descendants drove the poker and Stratego results below. It is the principled answer
to the question of what self-play should play against.

```algorithm
caption: $\textsc{PSRO}$ — policy-space response oracles
initialize population $\Pi = \{\pi_0\}$ with a random policy
repeat
  for each pair $(\pi_i, \pi_j) \in \Pi \times \Pi$ do
    estimate payoff $M_{ij}$ by simulating $\pi_i$ against $\pi_j$
  solve the meta-game: $\sigma \gets \textsc{Meta-Solver}(M)$ // Nash or diversity mixture
  train a best response $\pi_{new}$ against the mixture $\sigma$ over $\Pi$
  $\Pi \gets \Pi \cup \{\pi_{new}\}$
until the best response gains no payoff over $\sigma$
```

Naive self-play is the special case where $\sigma$ places all weight on the latest policy;
fictitious play is the case where $\sigma$ is the uniform average over $\Pi$.

$$
% caption: The PSRO loop. A growing population of policies plays itself to fill in
% an empirical payoff matrix; a meta-solver computes a mixture (e.g. a Nash) over
% the population; a new best-response policy is trained against that mixture and
% added to the population. Naive self-play is the special case where the mixture
% always puts all weight on the latest policy.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=27mm, minimum height=12mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=acc, text=acc, thick] (pop) at (0,0) {policy population};
  \node[box] (pay) at (4.4,0) {empirical\\payo\/f\/f matrix};
  \node[box] (meta) at (4.4,-2.6) {meta-solver:\\mixture over pop};
  \node[box, draw=red, text=red] (br) at (0,-2.6) {train best response};
  \draw[->, acc, thick] (pop) -- (pay) node[midway, above, font=\scriptsize] {self-play};
  \draw[->, black, thick] (pay) -- (meta) node[midway, right, font=\scriptsize] {evaluate};
  \draw[->, black, thick] (meta) -- (br) node[midway, below, font=\scriptsize] {opponent mix};
  \draw[->, red, thick] (br) -- (pop) node[midway, left, font=\scriptsize] {add to pop};
\end{tikzpicture}
$$

**MAPPO: PPO is a strong multi-agent baseline.** For a period, complex CTDE
value-factorization methods were assumed necessary for cooperative benchmarks. Yu et
al. (2021) showed that **MAPPO** — plain PPO with a centralized value function and a
few implementation details — matches or beats QMIX and its successors on the
StarCraft multi-agent challenge and other cooperative tasks.[^mappo] The lesson
echoes the single-agent one where PPO displaced more elaborate methods: a
well-tuned actor-critic with a centralized critic is a strong default,
and much of the apparent need for specialized machinery was implementation gap.

**Superhuman results in imperfect-information games.** Two-player zero-sum poker fell
to **counterfactual regret minimization** rather than RL proper — Libratus (Brown &
Sandholm 2017) and Pluribus (2019, six-player) — but the CFR / regret-matching
machinery is the imperfect-information cousin of the equilibrium computation this
lesson frames.[^poker] **DeepNash** (Perolat et al. 2022) reached expert human level
at Stratego, a game with an enormous imperfect-information state space, using a
model-free RL method (Regularized Nash Dynamics) that provably converges toward a
Nash equilibrium — a direct realization of the equilibrium-as-solution idea, at a
scale classical game solvers cannot touch.[^deepnash]

**Learned communication and LLM agents.** When agents can send messages, they can
learn a _protocol_: **RIAL/DIAL** (Foerster et al. 2016) showed agents discovering
a discrete communication code through the CTDE gradient itself, backpropagating
through the communication channel during centralized training.[^dial] Most recently,
multi-agent systems built from large language models — debate, negotiation, and
tool-using agent teams — revive these questions (coordination, non-stationarity,
emergent protocols) in a setting where each "agent" is a prompted model rather than
a trained policy, and the Markov-game framing and equilibrium concepts here are the
right framework for reasoning about them.

## The through-line

Multi-agent RL is single-agent RL with the stationary-environment assumption removed, and
almost everything follows from that one change. The Markov game is the object; non-stationarity
is the difficulty; CTDE is the dominant engineering answer — a centralized critic that sees the
joint action to restore a stationary learning target, paired with decentralized actors that
run on local observations (MADDPG for the general case, VDN and QMIX for cooperation). Where
the game is competitive, self-play converts the difficulty into a curriculum, and scaled up
with PPO and population-based training it produced OpenAI Five and AlphaStar. Underneath, the
Nash equilibrium defines what a solution even is — and, unlike the single-agent
optimum, it may be neither unique nor reachable. The lone agent maximizing a fixed reward was
the simple case; the world usually has more than one learner in it.


[^five]: **OpenAI et al. (2019)**, "Dota 2 with Large Scale Deep Reinforcement Learning" — OpenAI Five: five LSTM policies trained by large-scale PPO through self-play, defeating the _Dota 2_ world champions; team coordination emerged from a shared reward without an explicit communication or coordination mechanism.
[^alphastar]: **Vinyals et al. (2019)**, "Grandmaster level in StarCraft II using multi-agent reinforcement learning," _Nature_ — AlphaStar: a league of agents (main agents plus exploiters that target weaknesses) trained by population-based self-play to avoid strategic cycling, reaching Grandmaster level and ranking above 99.8% of human players on the official ladder.
[^hns]: **Baker et al. (2020)**, "Emergent Tool Use From Multi-Agent Autocurricula," _ICLR_ — the hide-and-seek environment, in which competition between hiders and seekers produced a succession of emergent strategies and counter-strategies (fort-building, ramp use, ramp-locking, box-surfing) as an autocurriculum, with no such behaviors rewarded directly.
[^psro]: **Lanctot, Zambaldi, Gruslys, Lazaridou, Tuyls, Perolat, Silver, Graepel (2017)**, "A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning," _NeurIPS_ — Policy-Space Response Oracles: maintain a population, compute a meta-strategy over its empirical payoff matrix, and train a best response against it, unifying self-play, fictitious play, and the double-oracle method.
[^mappo]: **Yu, Velu, Vinitsky, Gao, Wang, Bayen, Wu (2021)**, "The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games," _NeurIPS Datasets and Benchmarks_ — MAPPO: PPO with a centralized value function matches or exceeds specialized value-factorization methods on cooperative benchmarks including the StarCraft multi-agent challenge.
[^poker]: **Brown & Sandholm (2017)**, "Superhuman AI for heads-up no-limit poker: Libratus beats top professionals," _Science_; **Brown & Sandholm (2019)**, "Superhuman AI for multiplayer poker" (Pluribus), _Science_ — counterfactual regret minimization reaching superhuman play in imperfect-information poker, the imperfect-information counterpart of equilibrium computation.
[^deepnash]: **Perolat et al. (2022)**, "Mastering the game of Stratego with model-free multiagent reinforcement learning," _Science_ — DeepNash: Regularized Nash Dynamics, a model-free RL method that converges toward a Nash equilibrium, reaching expert human level at Stratego.
[^dial]: **Foerster, Assael, de Freitas, Whiteson (2016)**, "Learning to Communicate with Deep Multi-Agent Reinforcement Learning," _NeurIPS_ — RIAL and DIAL: agents learn a discrete communication protocol, with DIAL backpropagating through the communication channel during centralized training.