# Online Double Oracle

arXiv: https://arxiv.org/abs/2103.07780 · HTML: https://mlsanity.com/paper/2103.07780/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 59 references that are in the map.
- First posted on arXiv 13 Mar 2021.

## Builds on (most cited first, 14 of 14)

- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Open-ended Learning in Symmetric Zero-sum Games](https://mlsanity.com/paper/1901.08106/) (2019)
- [Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00583/) (2020)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Real World Games Look Like Spinning Tops](https://mlsanity.com/paper/2004.09468/) (2020)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games](https://mlsanity.com/paper/2006.08555/) (2020)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [XDO: A Double Oracle Algorithm for Extensive-Form Games](https://mlsanity.com/paper/2103.06426/) (2021)
- [Diverse Auto-Curriculum is Critical for Successful Real-World Multiagent Learning Systems](https://mlsanity.com/paper/2102.07659/) (2021)
- [αα-Rank: Practically Scaling α-Rank through Stochastic Optimisation](https://mlsanity.com/paper/1909.11628/) (2019)

## Built on by (most cited first, 18 of 18)

- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [Offline Pre-trained Multi-Agent Decision Transformer: One Big Sequence Model Tackles All SMAC Tasks](https://mlsanity.com/paper/2112.02845/) (2021)
- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games](https://mlsanity.com/paper/2106.04958/) (2021)
- [A Game-Theoretic Framework for Managing Risk in Multi-Agent Systems](https://mlsanity.com/paper/2205.15434/) (2022)
- [Reevaluating Policy Gradient Methods for Imperfect-Information Games](https://mlsanity.com/paper/2502.08938/) (2025)
- [Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2207.06541/) (2022)
- [Measuring the Non-Transitivity in Chess](https://mlsanity.com/paper/2110.11737/) (2021)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [Efficient Policy Space Response Oracles](https://mlsanity.com/paper/2202.00633/) (2022)
- [Is Nash Equilibrium Approximator Learnable?](https://mlsanity.com/paper/2108.07472/) (2021)
- [Online Markov Decision Processes with Non-oblivious Strategic Adversary](https://mlsanity.com/paper/2110.03604/) (2021)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [A Deep Reinforcement Learning Approach for Finding Non-Exploitable Strategies in Two-Player Atari Games](https://mlsanity.com/paper/2207.08894/) (2022)
- [Neural Auto-Curricula](https://mlsanity.com/paper/2106.02745/) (2021)
- [On the Convergence of Fictitious Play: A Decomposition Approach](https://mlsanity.com/paper/2205.01469/) (2022)
- [Achieving Better Regret against Strategic Adversaries](https://mlsanity.com/paper/2302.06652/) (2023)
- [Reinforcement Learning: From Algorithms To Foundation Models](https://mlsanity.com/paper/2607.17560/) (2026)

## Abstract (arXiv)

Solving strategic games with huge action space is a critical yet under-explored topic in economics, operations research and artificial intelligence. This paper proposes new learning algorithms for solving two-player zero-sum normal-form games where the number of pure strategies is prohibitively large. Specifically, we combine no-regret analysis from online learning with Double Oracle (DO) methods from game theory. Our method -- Online Double Oracle (ODO) -- is provably convergent to a Nash equilibrium (NE). Most importantly, unlike normal DO methods, ODO is rationale in the sense that each agent in ODO can exploit strategic adversary with a regret bound of O(√T k log(k)) where k is not the total number of pure strategies, but rather the size of effective strategy set that is linearly dependent on the support size of the NE. On tens of different real-world games, ODO outperforms DO, PSRO methods, and no-regret algorithms such as Multiplicative Weight Update by a significant margin, both in terms of convergence rate to a NE and average payoff against strategic adversaries.