Double Oracle (DO) and PSRO approximate Nash equilibria in two-player zero-sum games by iteratively expanding a strategy population with best responses supplied by an oracle. Online Double Oracle (ODO) interleaves multiplicative weights updates (MWU) with population discovery and obtains an O(klnk/T) rate, where T is the number of learning rounds and k is the larger of the two players' final population sizes. We identify the reinitialisation step as an underexplored design choice: at each expansion, MWU-based methods reset newly discovered strategies to a uniform prior. We introduce Virtual Double Oracle (VDO), which exploits a bilinear identity (a strategy's full hindsight loss history collapses to its utility against the time-averaged opponent) to initialise each new strategy with the MWU weight it would have had from the start. We prove that VDO achieves O(k/T) exploitability over the discovered population as it grows, provided the cumulative cost of adding strategies is at most linear in k, a condition supported by our empirical measurements. Discounted VDO (dVDO) moderates historical preferences to reduce over-concentration at reinitialisation. Experiments across matrix games, poker, and Goofspiel show that, with a suitable discount, dVDO can substantially reduce finite-horizon exploitability relative to both VDO and uniform-reset ODO, and can improve the discovered strategy populations.
Figures & tables
Figure 1: Online (top) and restricted-NE (bottom, RNE) exploitability versus BR queries on three imperfect-information games. ODO is the uniform-reset control with the historical BR target; VDO uses β=1 ; dVDO-best is the per-game hindsight choice. Full β sweeps are in Appendix I.2 ; matrix-game baselines and the long-horizon run are in Appendices I.3 and I.5 .
Figure 2: ε -perturbed best responses ( ε=0.1 ). Online (top) and restricted-NE (bottom, RNE) exploitability versus BR queries, with the same baselines as Figure 1 . Of the tested discounts, β=50 gives the lowest mean online exploitability on Leduc and Goofspiel-4. VDO has higher online exploitability than ODO on both games. dVDO-best has the lowest online exploitability and the lowest or tied-lowest RNE on every game.
Figure 3: Sampled-target best responses ( N=10 opponent samples). Online (top) and restricted-NE (bottom, RNE) exploitability versus BR queries, with the same baselines as Figure 1 . dVDO-best is lowest online and lowest or tied-lowest on RNE on all three games; on Leduc and Goofspiel-4, β=50 is the best of the tested discounts online, and VDO has higher online exploitability than ODO.
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Algorithm
β
m(j)
History view
DO [ McMahan et al., 2003 ]
—
∞
restricted-game NE
ODO [ Dinh et al., 2022 ]
∞
1
window-local average
PDO [ Tang et al., 2023 ]
∞
schedule
window-local (CFR, EFG)
FP-style hard-BR limit ∗
→0
1
full historical avg
VDO (ours)
1
any
full historical avg
Discounted VDO (ours)
β≥1
any
discounted historical avg
Appendix
Table 1: Classical algorithms and our contributions across the three axes of population expansion. The β column shows the discount parameter (where applicable), m(j) the BR check frequency, and “History view” the time horizon over which the meta-strategy solver integrates information at each window start. The ODO row reflects the theoretical analysis of Dinh et al. [2022] ( m(j)=1 , window-local average); our experimental ODO baseline uses the same shared protocol (BR target, oracle, window schedule) as VDO/dVDO and differs only in the reinitialisation rule. Convergence rates and bound regimes are stated in Theorems 4 and 7 ; the FP-style hard-BR limit ( β→0 ) is included as a structural extreme of the reinitialisation axis and lies outside our bound.
Figure 4: Kuhn learning-rate sensitivity with normalised training payoffs and per-player discovery. Points show normalised online half NashConv at the final event index (200 events per player), averaged over ten seeds. The curves show ODO, VDO and dVDO at β∈{2,5,10,20,50} .
Figure 5: Fixed- β trajectories on Kuhn, Leduc and Goofspiel-4; each curve is one value of β . RNE panels use the diagnostic defined in Section 5 . ODO ( β=∞ ) is solid orange, VDO ( β=1 ) dashed blue and FP-hardBR ( β→0 ) grey; dVDO runs from light to dark green as β increases from 2 to 50.
Figure 6: Fixed- β trajectories and the FP hard-BR baseline on normalised Gaussian matrices of sizes 25, 50 and 100. Top: online half NashConv; bottom: restricted-NE half NashConv. Each panel uses one fixed matrix and ten trajectories. The horizontal axis indexes each player’s response events; values average the evaluations at the two corresponding events.
Figure 7: Online (top of each panel) and restricted-NE (RNE, bottom of each panel) half NashConv on normalised matrix games with per-player discovery and resets. VDO uses β=1 ; dVDO-best uses β=5 , selected in hindsight from {2,5,10,20,50} by mean online exploitability at the final event index. Each size uses one fixed matrix, ten seeds and 200 events per player.
Figure 8: Discount sensitivity with normalised training payoffs and per-player discovery. Points show the final event index (200 events per player), then average across seeds: ten for Kuhn, Leduc and each matrix size, and five for Goofspiel-4. All metrics are normalised half NashConv. Circles show online exploitability and squares show RNE. On Kuhn, all mean RNE values are below 10−15 , so only online exploitability is shown. The Goofspiel-4 points are the endpoints of the exact-response trajectories in Figure 5 (c).
Figure 9: Online half NashConv versus discount on three fixed normalised Gaussian matrices. Points use the final event index and ten seeds per size. The smallest mean is at β=5 for all three sizes.
Figure 10: Long-horizon comparison on one normalised Gaussian 50×50 matrix, with ten seeds and 3,000 response events per player. Online exploitability is half NashConv. VDO reconstructs with precision ηt , dVDO with ηt/β , and the fixed-precision control with λ=10 , where t counts learning rounds. Only the player adding a new strategy is reinitialised.
Figure 11: Exact best responses on the additional games. Online (top) and restricted-NE (bottom, RNE) exploitability versus BR queries, with the same baselines as Figure 1 .
Figure 12: ε -perturbed best responses ( ε=0.1 ) on the additional games. Online (top) and restricted-NE (bottom, RNE) exploitability versus BR queries, with the same baselines as Figure 1 . The preferred discount moves to β∗=50 on Leduc-8 and Liar’s Dice-5, while Blotto keeps a small discount ( β∗=5 ).
Figure 13: Sampled-target best responses ( N=10 opponent samples) on the additional games. Online (top) and restricted-NE (bottom, RNE) exploitability versus BR queries, with the same baselines as Figure 1 . dVDO ( β∗=50 ) is lowest online on Leduc-8 and Liar’s Dice-5, though on Liar’s Dice-5 its margin over ODO is within the seed spread. Blotto keeps a small discount ( β∗=5 ), and every method reaches an RNE of ≈0 on it.
Game
Oracle
ODO
VDO
dVDO-best ( β∗ )
FP hard-BR
DO
Online exploitability
Kuhn poker
exact
0.00186
0.00182
0.00120 (2)
0.00821
≈0
ε=0.1
0.00391
0.00155
0.000496 (2)
0.00843
–
sampled
0.00243
0.00201
0.000888 (2)
0.00866
–
Leduc poker
exact
0.0142
0.00969
0.00991 (2)
0.0133
0.00481
ε=0.1
0.0218
0.0307
0.0166 (50)
0.0362
–
Appendix
Table 2: Mean normalised half NashConv at response event 200 per player. Bold marks the lowest displayed value among ODO, VDO and dVDO. The dVDO discount in parentheses is selected by mean online exploitability and is used in both halves of the table. DO uses the exact oracle. Values below 10−9 are shown as ≈0 .
Setting
VDO
dVDO ( β=5 )
Gaussian 25×25
2.7707
0.8221
Gaussian 50×50
3.1464
0.6582
Gaussian 100×100
3.8767
0.7348
Gaussian 250×250
3.9568
0.8537
Kuhn poker
0.7126
0.4514
Leduc poker
1.0270
0.3966
Appendix
Table 3: Maximum observed insertion-budget ratio Ci,t/∣Πit∣ with normalised payoffs and global-history best responses. Costs use each method’s reconstruction rate.
The Policy-Space Response Oracles (PSRO) framework scales equilibrium computation to large zero-sum games by iteratively expanding a restricted strategy set using deep reinforcement learning (DRL). A central challenge is to construct, under limited computational budgets, a small strategy population whose induced game well approximates the full game. Existing PSRO variants typically expand the population using best responses to meta-strategies computed from restricted-game payoffs, which can lead to inefficient expansions that provide limited global improvement. We propose to guide population expansion by directly evaluating the post-expansion population quality. Specifically, we adopt Population Exploitability (PE) to measure how well a restricted strategy set represents the full game, and introduce a two-phase exploration--selection framework that explicitly minimizes PE during expansion. We instantiate this framework as Global PSRO, a practical DRL-based algorithm that efficiently generates candidate responses and estimates PE via parameter-sharing conditional neural networks. Experiments across multiple two-player zero-sum games show that Global PSRO achieves lower exploitability and approximates Nash equilibria with significantly fewer policy iterations than prior PSRO methods.
Junyu Zhang, Feihong Yang, Jian Wang +2
Department of Electronic Engineering, Tsinghua University, Beijing, China · Qiyuan Lab, Beijing, China
This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two player zero-sum games. Recent works have identified instances on which the last-iterate of OMWU can converge arbitrarily slowly, but understanding when and why this slow convergence occurs has remained open. In this work, we develop a new analysis framework that gives sharp, quantitative explanations for this behavior. Our analysis is based on viewing the algorithm's dual iterates as an optimistic skew-gradient descent with respect to an energy function. We prove over the dual iterates that energy is dissipative, and by establishing tight bounds on the magnitude of dissipation, our analysis quantifies the geometric bottlenecks that arise when the corresponding primal iterates are close to the simplex boundary. This further translates into a new linear last-iterate convergence rate in KL divergence on games with a unique and interior Nash equilibrium. Compared to prior work, this new rate contains a much sharper dependence on game-specific constants, and we prove this dependence is optimal. Moreover, these geometric insights further translate into new separations on uniform convergence rates for OMWU. On the one hand, we prove constant lower bounds on the uniform best-iterate convergence rate in KL divergence and total variation distance from Nash. On the other hand, we establish for the 2×2 setting a new O(T−1/2) best-iterate rate in duality gap, improving substantially over prior work. Together, this shows in general that uniform convergence rate guarantees do not transfer across different measures of distance to Nash.
John Lazarsfeld, Anas Barakat, Georgios Piliouras +2
We study the problem of learning Nash equilibria in offline two-player zero-sum Markov games. While existing approaches often rely on explicit pessimism to address distribution shift, we show that KL regularization alone suffices to stabilize learning and guarantee convergence. We first introduce Regularized Offline Sequential Equilibrium (ROSE), a theoretical framework that achieves a fast O(1/n) convergence rate under unilateral concentrability, improving over the standard O(1/n) rates in unregularized settings. We then propose Sequential Offline Self-play Mirror Descent (SOS-MD), a practical model-free algorithm based on least-squares value estimation and iterative self-play updates. We prove that the last iterate of SOS-MD attains the same O(1/n) statistical rate up to a vanishing optimization error of order O(1/T) in the number of self-play iterations T.
Claire Chen, Yuheng Zhang, Xinyu Liu +3
1California Institute of Technology. · University of Illinois Urbana-Champaign. · University of Virginia. +2