AlphaGo beat Lee Sedol via self-play. Pluribus beat the top human poker pros via CFR. AlphaStar reached StarCraft Grandmaster via a league of agents. Cicero negotiated alliances in Diplomacy at human level. Every superhuman game-playing AI is multi-agent — and the moment you have two learners in the same room, the convergence proofs you grew up with stop working. This is where RL gets strange and beautiful.
Learning Objectives
After this lesson, you will be able to:
Distinguish cooperative, competitive, and mixed multi-agent settings — and pick the right algorithm family for each
Use self-play to train two-player zero-sum agents that converge to Nash equilibria — the recipe behind AlphaGo, AlphaZero, AlphaStar
Apply Counterfactual Regret Minimization (CFR) to imperfect-information games like poker — the math that powers Pluribus and Cepheus
Pick between centralized-critic (MADDPG / QMIX / MAPPO) and independent learners — and know why naive PPO often surprisingly works
Don't worry if "multi-agent" sounds intimidating — once you have one PPO agent working, multi-agent is mostly variations on "let multiple PPO agents play each other and see what falls out". The hard parts are the math of equilibria and the tricks for stability.
The fundamental challenge of multi-agent RL: the environment changes because everyone keeps learning. Agent A's optimal policy depends on Agent B's policy. As B improves, A's previously-optimal policy becomes obsolete. Standard RL convergence proofs (Q-learning, PPO) assume a stationary environment — they don't apply.
Single-agent: P(s′∣s,a) is fixed.Multi-agent: P(s′∣s,a1,a2,…,aN) depends on π−i which is changing.
The non-stationarity problem is why naive Q-learning often diverges in multi-agent settings — and why the workarounds below exist.
For two-player zero-sum games (chess, Go, head-to-head poker), self-play converges to a Nash equilibrium — Tesauro 1995 TD-Gammon was the first major demonstration, and AlphaZero is the modern apotheosis.
The recipe
Initialize agent π_θ
Generate games where π_θ plays against a copy of itself
Train π_θ on the resulting (state, action, outcome) data
Periodically save snapshots; sometimes play against past versions for stability
Repeat
For two-player zero-sum: π1minπ2maxVπ1,π2(s0)=π2maxπ1minVπ1,π2(s0)(minimax theorem)
Population-based self-play (PBT, used by AlphaStar): train multiple agents simultaneously with varied hyperparameters; periodically copy the best to replace the worst. Avoids the chicken-and-egg problem of "learning against a moving target" by maintaining diversity.
What Do You Think?
Two PPO agents are trained via self-play on rock-paper-scissors. After training, they each output approximately 33%/33%/33% probability for each move. Why?
The answer: rock-paper-scissors has a unique Nash equilibrium of uniform random play. Any agent that biases toward one move (say 50% rock) becomes exploitable — the other agent learns to throw paper. Self-play forces both into the equilibrium.
Self-play works beautifully for perfect-information games (chess, Go), but breaks down on imperfect-info games like poker — you can't simply plan with MCTS when you don't know your opponent's cards. Counterfactual Regret Minimization (CFR) (Zinkevich 2008) solves this by tracking how much regret you have for not playing each action at each information set, then biasing future play toward low-regret actions.
Pluribus (Brown & Sandholm 2019) used a variant called MCCFR (Monte Carlo CFR) plus depth-limited search at runtime to play 6-player No-Limit Hold'em — the first AI to beat top humans at multiplayer poker. Cepheus (Bowling 2015) did the same for two-player Limit Hold'em.
For cooperative or mixed-motive settings, the choice is between:
Independent learners (IL): each agent runs PPO/Q-learning on its own observation, treating the others as part of the environment. Simple, scales well. Surprisingly works for many tasks despite the non-stationarity problem.
Centralized training, decentralized execution (CTDE): during training, a critic sees the global state and all actions; at deployment, each actor only sees its local observation. Solves credit assignment in cooperative tasks.
MADDPG centralized critic: Qiπ(x,a1,…,aN)butπi(ai∣oi)(actor uses local obs only)
QMIX (Rashid 2018): factorizes the joint Q-value into per-agent Q-values via a monotonic mixing network — preserves CTDE while allowing decentralized argmax. MAPPO (Yu 2022): just PPO with a centralized value function — surprisingly effective baseline.
Tests · Verify both policies converge to approximately uniform 33%/33%/33% in 2000 steps. The expected reward should converge toward 0 (Nash value of standard RPS).
Multi-agent introduces non-stationarity. Single-agent convergence proofs don't apply because each agent's environment changes as others learn; fixes include centralized critics, self-play, and population-based training
Self-play converges to Nash for two-player zero-sum games. TD-Gammon, AlphaGo, AlphaZero, AlphaStar all rely on this; for multiplayer or imperfect-info, you need CFR or PBT
CFR is the math behind poker AI. Track regret per information set, bias future play toward low-regret actions; powers Cepheus, Pluribus, and most modern poker bots
CTDE (centralized training, decentralized execution) is the dominant cooperative framework — train with a critic that sees everything; deploy with actors that only see local observations
Modern multi-agent LLM systems are emerging. Voyager, CICERO, Constitutional AI debate, multi-agent debate frameworks — fusing RL ideas with LLMs is the 2024-2026 frontier
Interactive Lab
Watch multiple agents interact in cooperative and competitive scenarios — see policies emerge from self-play, observe non-stationarity in real time, and feel why centralized critics stabilize what independent learners cannot.
Why does naive Q-learning often diverge in multi-agent settings even when the environment is otherwise simple?
You now understand the algorithmic backbone of how AI plays games — from chess to poker to StarCraft. Next: offline RL, the paradigm that lets you train agents from logged data without ever touching the environment.