Multi-Agent RL: Self-Play and Solution Concepts

This builds on Multi-Agent RL: Markov Games and Centralized Training, 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.

This is the mechanism behind the case studies in the 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.

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 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.¹ 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.²

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.³

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:

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,

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:

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 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.

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$.

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.⁵ 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.⁶ 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.⁷

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.⁸ 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.