cs.LGNov 17, 2026

Virtual Double Oracle: Faster Convergence by Leveraging Strategies That Were Watching All Along

Authors: Ruilan Wang, Francisco Aristi Reina, Katerina Papadaki

Organizations: Department of Mathematics, London School of Economics, London, UK

Abstract

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(kln⁡k/T)O(\sqrt{k\ln k/T}) rate, where TT is the number of learning rounds and kk 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)O(\sqrt{k/T}) exploitability over the discovered population as it grows, provided the cumulative cost of adding strategies is at most linear in kk, 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

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

May 27, 2026

Global Policy-Space Response Oracles for Two-Player Zero-Sum Games

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.
May 13, 2026

When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation

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×22\times 2 setting a new O~(T−1/2){\widetilde 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.
May 13, 2026

Offline Two-Player Zero-Sum Markov Games with KL Regularization

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)\widetilde{\mathcal{O}}(1/n) convergence rate under unilateral concentrability, improving over the standard O~(1/n)\widetilde{\mathcal{O}}(1/\sqrt{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)\widetilde{\mathcal{O}}(1/n) statistical rate up to a vanishing optimization error of order O~(1/T)\widetilde{\mathcal{O}}(1/\sqrt{T}) in the number of self-play iterations TT.