Deep Multiagent RL for Games

Gabriele Farina

MIT

1 / 46

What makes extensive-form games tractable?

They are convex games

When represented using sequence-form strategies.

In two-player zero-sum games we can solve them via the convex optimization problem

The sets and are convex polytopes. The payoff is bilinear.

Gradient ascent in sequence-form space will work.

2 / 46

How do we scale to large games?

Bowling et al. Figure 2: historical growth from about 100000 unique information sets in 2003 to more than 10 trillion in 2014, with SFLP, CFR, and CFR+ phases.

Unique information sets after removing symmetries. Historical results through 2014.

Bowling, Burch, Johanson & Tammelin (2015), Heads-up Limit Hold’em Poker is Solved, Fig. 2.

Go

A Go board covered with black and white stones.

Stratego

Go photo: Elena Popova / Unsplash. Stratego board: Sokota et al. (2026), Fig. 2a.

3 / 46

How should we approach large games?

Two directions

1. “Deepify” game theory

Can we learn best responses and regrets?

Neural fictitious play · ESCHER · Deep CFR

2. “Game-theorify” deep RL

Can we make self-play policy gradients converge?

Policy gradient · PPO · MMD

↑ We start here

4 / 46

“Deepifying” game-theoretic algorithms

First direction

Keep fictitious play, double oracle, CFR, ... but approximate the expensive step with a neural network.

5 / 46

Idea 1: learn best responses

Use deep RL to approximate the best response.

Algorithm 1 Fictitious play

while do

end while

return

Algorithm 2 Double oracle

while do

end while

return

Same expensive primitive: best response

How accurately—and how quickly—can deep RL solve it?

Lanctot et al. (2017), PSRO.

6 / 46

Idea 2: learn counterfactual regrets

CFR computes a local learning signal at each information set .

Deep CFR: learn regrets, then apply regret matching

Fit predictions proportional to cumulative regrets.

Brown et al. (2019), Deep CFR, §4. If all predictions are nonpositive, select an action with the largest prediction.

7 / 46

Three examples

NFSP

Fictitious play + deep RL

Learn a best-response policy and fit a separate average-policy network from a reservoir of behavior.

PSRO

Response oracles + deep RL

Grow a population of policies and use a meta-solver to mix them in an empirical game.

Deep CFR

CFR + deep learning

Fit sampled counterfactual advantages and the average strategy without a complete tabular representation.

Heinrich & Silver (2016), NFSP; Lanctot et al. (2017), PSRO; Brown et al. (2019), Deep CFR.

8 / 46

Pros and cons of deepified game-theoretic approaches

Clear theoretical foundations.

The outer algorithm specifies what each approximation must achieve.

−

Learning a strong best response is expensive.

−

Growing and evaluating a policy population costs memory and simulation.

−

Even exact fictitious play and double oracle can require many outer iterations.

Can we just do gradient ascent and not think?

This leads us toward self-play policy gradients.

Slow-convergence examples: Wang (2025), fictitious play; Zhang & Sandholm (2024), double oracle.

9 / 46

How should we approach large games?

Two directions

1. “Deepify” game theory

Can we learn best responses and regrets?

Neural fictitious play · ESCHER · Deep CFR

2. “Game-theorify” deep RL

Can we make self-play policy gradients converge?

Policy gradient · PPO · MMD

↑ We now turn here

10 / 46

“Game-theorifying” deep reinforcement learning

Second direction

Let’s start from algorithms designed to scale, and modify them.

11 / 46

Choice I: out with sequence-form, in with behavioral

Sequence-form strategies are constrained and can get very small.

As much as they are the source of tractability, they are the first to go. Instead, we insist on behavioral strategies (“policies”): a probability distribution at each information state.

In fact, our policy net will output logits :

12 / 46

A nonlinear parametrization of the strategy

The parameters determine action probabilities, which multiply along each player sequence.

Two main questions:

1. Will (stochastic) gradient ascent still work? and

2. how should we estimate the gradient?

13 / 46

Is there hope for gradient ascent?

For a fixed opponent, the objective is concave in the sequence-form strategy, but not in the parametrization that we picked... We can think of this as hidden concavity.

The objective is secretly concave

For suitable policy parametrizations, a large best-response gap implies a large first-order improvement signal: gradient domination.

14 / 46

Example of gradient domination: PŁ condition

Polyak–Łojasiewicz (PŁ) condition

Nonconcave objective J(theta)=-theta squared minus three sine squared theta. Its global maximum is zero at theta=0. At theta=2.2, a vertical arrow marks the objective gap, and an orange tangent marks the nonzero local slope.

Can the gradient vanish while the objective gap is positive?

No: every stationary point is globally optimal.

Karimi, Nutini & Schmidt (2016), §2; Kalogiannis & Farina (2025).

15 / 46

Why does gradient ascent converge?

Assume is -smooth, attains , and satisfies PŁ with .
Take .

1. Smoothness: one step makes progress.

2. PŁ condition: the gradient controls the objective gap.

Hence, geometric convergence—even without concavity

Exact ascent on one fixed, unconstrained objective. Self-play requires additional arguments. Karimi, Nutini & Schmidt (2016), Theorem 2.1, maximization form.

16 / 46

PŁ ⇐⇏ Strong Convexity

Left: J(theta)=-theta squared minus three sine squared theta, with positive-curvature parts in orange. Right: J double prime(theta)=-2-6 cos(2 theta), which becomes positive and equals four at pi/2, proving nonconcavity.

Nonconcave, globally smooth, and gradient dominated

PŁ holds with . Step size gives a global geometric bound on the objective gap.

Karimi, Nutini & Schmidt (2016), §2.2 give as a nonconvex PŁ example. Here converts it to maximization; figures are drawn from the analytic formulas.

17 / 46

What can we prove?

[KF25] Regularized policy gradient in imperfect-information EFGs

In finite two-player zero-sum extensive-form games with perfect recall, suitable alternating updates converge in the last iterate to an -Nash equilibrium, with polynomial iteration and sample complexity.

Independent tabular behavioral policies.
Explicit exploration, truncated policies, and suitable Euclidean or entropy regularization.
Direct, softmax, and natural policy-gradient variants.

Kalogiannis & Farina, NeurIPS (2025), Theorems 3.1 & 3.3.

18 / 46

Choice II: Which gradient estimator?

Begin with a single decision: .

Choose any proposal with full support. Sample .

Importance weights

Low-prob. actions carry a large correction . Which distribution should we choose?

Srinivasan et al. (2018), actor-critic policy optimization; score-function estimation: Williams (1992).

19 / 46

Uniform exploration?

In self-play, we also control the opponent. We can choose both exploration policies.

Theory suggests a uniform strategy: minimize the largest importance weight.

But uniform exploration is a bad idea at the scale where you need deep RL.

Why?

Learn on the distribution we expect to encounter

Uniform play visits unlikely states. On-policy sampling is desirable to spend resources on parts of the decision space that are important/expected during play.

The minimax bound is for one decision. Trajectory corrections multiply. On-policy sampling still needs exploration for coverage.

20 / 46

Policy gradient estimator: REINFORCE

1. Recall our sequence-form reach Let list our own information-set/action pairs along a generic path.

2. Turn own reach into a full trajectory probability

be a terminal path,
our payoff
our own trajectory
is the fixed opponent/chance factor
is the full path probability

3. Differentiate log probability: the trajectory score

4. Use to differentiate expected payoff

REINFORCE: terminal return × trajectory score

Unbiased, but one noisy terminal return weights every decision’s score.

Finite perfect-recall game; positive policy probabilities; opponent and chance held fixed. Williams (1992); Srinivasan et al. (2018), §§2.2, 4 and Appendix E.

21 / 46

Policy gradients with a learned critic

REINFORCE is correct but noisy. We can use standard ideas to reduce variance

From REINFORCE to Actor-Critic

So we can write

The same expected gradient, using action advantages

We also learn an estimate of (directly or via ): the critic. The policy is the actor.

Srinivasan et al. (2018), §4; Sutton & Barto, Ch. 13; GAE; Ataraxos: Methods and Supplementary §S3.4.

22 / 46

Summary: the RL toolbox

Behavioral policies let us tap into the RL toolbox

Behavioral strategies make path probabilities products. We can then use scores (log probs) to obtain a nice estimator and tap into standard RL solutions

We can then use TD()/GAE to “blend” multiple estimators and try to reduce variance

We can think of the resulting algorithm as a form of CFR with Q values in place of counterfactual values.

Perhaps reassuring us that we have not strayed too far...

However, both players are updating. Will their current policies converge?

Sutton & Barto (2018), Chs. 6, 12; Schulman et al. (2016), GAE; Srinivasan et al. (2018), §4 and Appendix E.

23 / 46

Exact gradients can still cycle

Even exact tabular methods can cycle (it is the average strategies that converge to the set of equilibria)

Matching pennies, . Exact gradients with simultaneous updates.

24 / 46

Choice III: add regularization to force convergence

Add attraction toward a full-support reference policy .

Annealing

A fixed positive induces a regularized equilibrium. To approach the original game’s equilibrium, a popular approach is to reduce regularization (“anneal”) over time

Sokota et al. (2023), Magnetic Mirror Descent; extensive-form entropy needs the corresponding game-specific analysis.

25 / 46

What changes when we add a magnet?

Exact matching-pennies example with a biased, fixed reference policy. A fixed positive KL weight changes the equilibrium we converge to.

26 / 46

Summary: three choices for self-play

A scalable recipe

Choice I: behavioral policies and logits.

Choice II: on-policy values and policy-gradient estimates.

Choice III: regularization to stabilize self-play; reduce its bias with a controlled schedule.

How well does this work in practice?

Do the resulting policies have low exploitability?

27 / 46

Reevaluating policy gradient methods

Figure 2 from Rudolph et al. comparing final exploitability distributions across five benchmark games and seven deep reinforcement-learning methods.

Lower exploitability is better. Boxes: tuning / evaluation. Axis: square-root scale.

Policy gradients perform surprisingly well

Across 7,000 runs on five benchmarks, MMD, PPO, and PPG matched or exceeded the tested game-theoretic deep RL methods.

Rudolph et al., Reevaluating Policy Gradient Methods for Imperfect-Information Games (2026). ICLR 2026, arXiv v4, 27 May 2026.

28 / 46

How much entropy regularization?

Figure 7 from Rudolph et al. showing mean and median exploitability versus entropy coefficient, compared with common PPO defaults.

Pooled over 2D5F Liar’s Dice, 3×3 Dark Hex, 3×3 Abrupt Dark Hex,
Phantom Tic-Tac-Toe and Abrupt Phantom Tic-Tac-Toe. Green: mean; purple: median; gray: interquartile range.

The usual PPO defaults use too little entropy here

In these sweeps, entropy coefficients around 0.05-0.2 worked best on average. Common PPO defaults were 0-0.01. The best coefficient depends on the game.

Rudolph et al. (2026), Fig. 7. Red dashed lines: common PPO defaults.

29 / 46

Decision-time planning (DTP)

Can we spend more computation at decision time to improve the policy?

30 / 46

Decision-Time Planning

Blueprint policy Start from the trained network

→

DTP Spend extra simulation to refine policy

→

Improved policy Then play the new policy

Update-Equivalent Search [SFW+24]

Instead of using gadgets and subgame solving, do something very simple: spend the DTP budget to estimate higher quality Q-values (starting from the posterior distribution of the state), and then do one last policy gradient step

We will see an evaluation of this idea in Stratego.

Sokota et al. (ICLR 2024), update-equivalence; Sokota et al., Nature (2026).

31 / 46

Stratego

32 / 46

Hidden pieces, long horizons

Nature Figure 2a: the starting Stratego board from the red player's perspective. Red piece identities are visible and blue piece identities are concealed.

a. Secret setups. Each player knows its own pieces.

Nature Figure 2b: a later Stratego position with a blue piece attacking the red Bomb on a4, indicated by a green arrow. Some blue piece identities have been revealed by earlier battles.

b. A battle reveals both piece types and captures at least one.

Sokota et al., Nature (2026), Fig. 2a–b.

33 / 46

Stratego before Ataraxos

Before 2022, Stratego was one of the last iconic board games without expert-level AI.

2022: DeepMind’s DeepNash. R-NaD and self-play, without DTP. 42 wins in 50 ranked Gravon games (84%).

2023: World Championship demo. 19 wins, 9 losses. It lost to most of its highest-ranked opponents, including Pim Niemeijer.

A large compute commitment

1,024 TPU nodes for roughly 2–3 months.
Estimated training-run cost: US$3–4.5 million at 2025 prices.

Screenshot of the Science masthead, article title and authors for Perolat et al., Mastering the game of Stratego with model-free multiagent reinforcement learning, published 1 December 2022.

DeepMind’s DeepNash. Science, 2022.

Perolat et al., Science (2022); Sokota et al., Nature (2026), Contextualization vis-à-vis DeepNash.
Cost: TPU v3 rental estimate based on an author’s recollection; actual expenditure and total R&D budget were not reported.

34 / 46

Ataraxos (2026)

Screenshot of the Nature masthead, title, authors and publication date for Scalable decision-making for games of imperfect information, published 30 September 2026.

Self-play policy gradients + DTP against top humans.

Sokota et al., Nature (2026).

35 / 46

Ataraxos learns where to put the pieces

Top of Nature Extended Data Figure 1: the decoder-only setup transformer maps a prefix of placed pieces to outcome, entropy, and next-piece predictions.

Extended Data Fig. 1: setup policy.

A policy over entire setups

Place 40 pieces autoregressively. Predict outcomes and entropy while learning the setup distribution.

Two self-play processes learn together: setups determine the initial boards; move policies determine the outcomes used to train both.

Sokota et al., Nature (2026), Methods and Extended Data Fig. 1.

36 / 46

Ataraxos learns how to move

Bottom of Nature Extended Data Figure 1: an encoder-only transformer produces an outcome prediction and move logits from dot products of source-square queries and destination-square keys.

Extended Data Fig. 1, bottom. A source–destination dot product defines each move logit.

A scalable behavioral policy

Board features become move logits and value estimates. Damped self-play trains the network; DTP refines its policy at test time.

Sokota et al., Nature (2026), Extended Data Fig. 1.

37 / 46

Ataraxos learns what the hidden pieces might be

Nature Extended Data Figure 4: a transformer encoder processes the observed board; tokens for hidden opponent pieces feed an autoregressive transformer decoder, which predicts a distribution over piece types at each hidden square.

Extended Data Fig. 4: the belief network.

Encode the player’s information state. Decode a distribution over hidden piece types one at a time.

Train on final-policy self-play, using true hidden piece types as supervised labels.

From beliefs to DTP

Sample plausible hidden boards. Average rollout values for each candidate move.

Sokota et al., Nature (2026), Methods: belief modelling and DTP; Extended Data Fig. 4.

38 / 46

Ataraxos: decision-time planning

Nature Extended Data Figure 2d: Elo versus H100-seconds per move for decision-time planning at depths of 10 or 40 ply and 200 or 1000 rollouts. All four settings improve on the dotted baseline for the same policy network. Error bars are 95 percent confidence intervals.

More computation at decision time improves play

The policy network is fixed; DTP refines its decisions.
40 ply · 1,000 rollouts: 1.26 seconds per move on one H100.

Sokota et al., Nature (2026), Extended Data Fig. 2d. Bars: 95% confidence intervals. Dotted line: move network without DTP.

39 / 46

How strong is Ataraxos?

Pim Niemeijer: the most decorated Stratego player

4 world championships · 15 Dutch championships · 2 online world championships
More than 600 weeks ranked world #1.

85%

Effective win rate against Pim Niemeijer

15 wins · 1 loss · 4 draws

95%

World Championship attendee demo

38 wins · 2 losses · 0 draws

1.26 s

Average time per move on one H100

40-ply · 1,000-rollout DTP

Across the 20-game evaluation, Pim could adapt. Ataraxos kept its strategy fixed.

Accolades and evaluation: Sokota et al., Nature (2026), Evaluation and Extended Data Fig. 2; International Stratego Rating: Pim Niemeijer.

40 / 46

Recovering from difficult positions

All 20 evaluation games against Pim Niemeijer. The critic predicts effective win probability as each game progresses. Blue marks eventual wins, orange the loss and purple draws. Games 13 and 14 recover from low midgame forecasts to a win and a draw.

Critic predictions over all 20 games.

Sokota et al., Nature (2026), Fig. 3 and Methods: Play Style. Original figure reflowed to 5 × 4 panels.

41 / 46

How much did training cost?

1/500

Approximate compute cost

1/30

Approximate self-play games

1/100

Approximate training examples

Ataraxos relative to DeepMind’s DeepNash, as estimated in the paper. Ataraxos trained its RL networks on 16 H100s for one week and its belief network on 4 H100s for four days.

The improvement is also in sample efficiency

Far fewer games and training examples. The systems were evaluated against humans; no direct match was possible.

Sokota et al., Nature (2026), training-cost comparison; Perolat et al. (2022). Compute costs use 2025 price estimates.

42 / 46

Exponential moving average of parameters

Keep a smoothed copy of the policy network.

Evaluate the smoothed network

Ataraxos used for setup and move networks.

The map from parameters to policies is nonlinear: averaging parameters is generally different from averaging strategies.

Sokota et al., Nature (2026), Supplementary Information, setup and move training.

43 / 46

Conclusions

44 / 46

Main takeaways

(1) Policy gradient methods in imperfect-information games

can be put on solid theoretical footing, and seem to perform very well

(2) Entropy plays an important role

Compared to vanilla PPO, you need more. Other imperfect-information-specific tricks seem to help, for example Q-boosting (“GAE falls short” paper)

(3) DTP plays well with policy gradient

One approach that we found useful is just to perform one additional tabular update on the policy using high-quality Q values (“Update-equivalent search” used by Ataraxos)

Reevaluating Policy Gradient; Ataraxos; GAE falls short.

45 / 46

Questions?

Gabriele Farina

gfarina@mit.edu

Stratego: github.com/AtaraxosAI/stratego

46 / 46