Virtual Double Oracle: Faster Convergence by Leveraging Strategies That Were Watching All Along
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 rate, where is the number of learning rounds and 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 exploitability over the discovered population as it grows, provided the cumulative cost of adding strategies is at most linear in , 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
| Algorithm | 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 ∗ | 1 | full historical avg | |
| VDO (ours) | 1 | any | full historical avg |
| Discounted VDO (ours) | any | discounted historical avg |
| 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.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.0218 | 0.0307 | 0.0166 (50) | 0.0362 | – | ||
| Setting | VDO | dVDO ( ) |
|---|---|---|
| Gaussian | 2.7707 | 0.8221 |
| Gaussian | 3.1464 | 0.6582 |
| Gaussian | 3.8767 | 0.7348 |
| Gaussian | 3.9568 | 0.8537 |
| Kuhn poker | 0.7126 | 0.4514 |
| Leduc poker | 1.0270 | 0.3966 |
Nash Equilibrium Computation
Nash equilibrium computation develops algorithms for finding stable strategies in strategic, stochastic, and imperfect-information games.
See all 76 papers