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

Ruilan Wang, Francisco Aristi Reina, Katerina PapadakiarXiv 2026 · arXiv

TL;DR

Virtual Double Oracle (VDO) accelerates the convergence of population-based game solvers by realizing that newly discovered strategies don't have to start from scratch. By leveraging a "bilinear identity," VDO initializes new strategies with the weights they would have earned if they had been "watching" the opponent's play from the very beginning, improving theoretical convergence rates and empirical performance in games like Poker and Goofspiel.

What Problem Does This Paper Address?

In large-scale two-player zero-sum games (like StarCraft or complex Poker variants), the space of possible strategies is too vast to search entirely. Researchers use "population-based" methods like Double Oracle (DO) or PSRO, which maintain a small subset of strategies and iteratively expand it by adding "best responses" to the current population.

A recent advancement, Online Double Oracle (ODO), uses Multiplicative Weights Updates (MWU) to learn how to play within this expanding population. However, ODO has a hidden inefficiency: every time a new strategy is discovered, the algorithm resets the weights of all strategies to a uniform distribution. This "uniform reset" essentially treats the newcomer as a blank slate and ignores the learning progress made in previous rounds. The authors argue that this reinitialization is a major bottleneck, both theoretically (adding a $\sqrt{\ln k}$ factor to regret) and practically.

Methods

The authors introduce Virtual Double Oracle (VDO) and its practical variant, Discounted VDO (dVDO). The core innovation lies in the bilinear identity: in these games, a strategy’s total historical loss can be perfectly reconstructed just by knowing its utility against the opponent’s time-averaged strategy.

  • VDO: Instead of a uniform reset, VDO performs a "virtual reinitialization." It calculates what weight a new strategy would have had if it had been part of the population since round one, based on the opponent's actual historical play. This preserves a single, continuous learning trajectory even as the strategy set grows.
  • dVDO: The authors observed that pure VDO can sometimes "over-concentrate" weight on a single strategy that performed well early on, making the learner too rigid. dVDO introduces a discount factor ($\beta$) to moderate this historical preference, providing a "soft" version of the virtual initialization.
  • Three-Axis Framework: The paper helpfully categorizes population expansion into three independent design choices: when to expand, what to add (the oracle), and how to integrate (the reinitialization). VDO specifically optimizes the third axis.

Datasets

The researchers evaluated their methods on a variety of standard game-theoretic benchmarks:

  • Gaussian Matrix Games: Randomly generated payoff matrices of sizes 25, 50, 100, and 250.
  • Imperfect-Information Games: Kuhn Poker, Leduc Poker (including a larger Leduc-8 variant), and Liar’s Dice.
  • Goofspiel-4: A card game involving bidding and strategy.
  • Colonel Blotto: A classic resource allocation game.

Key Insights and Ideas

  • "Strategies were watching all along": This is the paper's central intuition. A best-response strategy is chosen because it beats the opponent's past play; VDO simply formalizes this by giving that strategy the "credit" it deserves from the start.
  • Removing the $\ln k$ penalty: Theoretically, uniform resets force the learner to pay a "prior cost" every time the population grows. By using virtual history, VDO improves the exploitability rate from $O(\sqrt{k \ln k / T})$ to $O(\sqrt{k/T})$.
  • Reinitialization as a First-Class Citizen: Most prior work focused on the Oracle (how to find new strategies). This paper shows that how you introduce those strategies to the existing team is just as critical for fast convergence.

Key Results

  • Faster Convergence: In Kuhn Poker, VDO and dVDO reached near-zero exploitability significantly faster than ODO. In Leduc Poker, VDO achieved the lowest mean exploitability among all MWU-based methods.
  • Better Populations: The authors measured Restricted-NE Exploitability (RNE), which looks at the quality of the discovered strategy set itself. VDO/dVDO consistently discovered higher-quality populations than uniform-reset methods.
  • Robustness to Approximation: The benefits of VDO held up even when using "approximate" best responses (simulating a Reinforcement Learning oracle), which is the standard setup for modern PSRO applications.
  • Optimal Discounting: While the best $\beta$ varied by game, dVDO with a moderate discount (e.g., $\beta=5$ or $\beta=50$) often outperformed both the uniform reset ($\beta=\infty$) and the pure virtual history ($\beta=1$).

Limitations and Future Work

  • Hyperparameter Sensitivity: There is currently no theoretical way to determine the optimal discount factor $\beta$ in advance; it must be tuned or selected via hindsight, which the authors acknowledge as a limitation for practitioners.
  • Two-Player Zero-Sum Constraint: The theoretical guarantees and the bilinear identity rely on the two-player zero-sum structure. Extending this to multi-player or general-sum games remains an open challenge.
  • Exact Payoffs: The current theory assumes exact payoff evaluations. In many real-world RL scenarios, payoffs are estimated via noisy simulations, which might affect the stability of the virtual weight reconstruction.

For those interested in implementation, the authors have released their code at github.com/ruilan-wang/vdo-reproducibility.

Summary updated

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(\sqrt{k\ln k/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(\sqrt{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.
BibTeX
@misc{wang2026virtual,
  author = {Ruilan Wang and Francisco Aristi Reina and Katerina Papadaki},
  title = {{Virtual Double Oracle: Faster Convergence by Leveraging Strategies That Were Watching All Along}},
  year = {2026},
  eprint = {2611.22806},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22806},
}
Figure