mlsanityData to 7 Oct 2026

Online Double Oracle

arXiv 2103.07780 ↗First posted 13 Mar 2021cs.AI cs.GTcited by 18

Not on the map. Why?

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.

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

Builds on

14 of 59 references.

References · 14

  1. 2017A Unified Game-Theoretic Approach to Multiagent Reinforcement Learningcited by 265
  2. 2018Mean Field Multi-Agent Reinforcement Learningcited by 202
  3. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  4. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  5. 2019Open-ended Learning in Symmetric Zero-sum Gamescited by 96
  6. 2020Game-Theoretic Multiagent Reinforcement Learningcited by 92
  7. 2013Follow the Leader If You Can, Hedge If You Mustcited by 68
  8. 2020Real World Games Look Like Spinning Topscited by 66
  9. 2019α-Rank: Multi-Agent Evaluation by Evolutioncited by 50
  10. 2020Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Gamescited by 47
  11. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  12. 2021XDO: A Double Oracle Algorithm for Extensive-Form Gamescited by 34
2 more
  1. 2021Diverse Auto-Curriculum is Critical for Successful Real-World Multiagent Learning Systemscited by 24
  2. 2019αα-Rank: Practically Scaling α-Rank through Stochastic Optimisationcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 6; 2023: 1; 2024: 2; 2025: 1; 2026: 1.

18 papers.

Sort:

By area:

  1. 2021Modelling Behavioural Diversity for Learning in Open-Ended Gamescited by 39
  2. 2021Offline Pre-trained Multi-Agent Decision Transformer: One Big Sequence Model Tackles All SMAC Taskscited by 32
  3. 2024A Survey on Self-play Methods in Reinforcement Learningcited by 26
  4. 2021Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Gamescited by 14
  5. 2022A Game-Theoretic Framework for Managing Risk in Multi-Agent Systemscited by 13
  6. 2025Reevaluating Policy Gradient Methods for Imperfect-Information Gamescited by 13
  7. 2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
  8. 2021Measuring the Non-Transitivity in Chesscited by 10
  9. 2024Policy Space Response Oracles: A Surveycited by 10
  10. 2022Efficient Policy Space Response Oraclescited by 8
  11. 2021Is Nash Equilibrium Approximator Learnable?cited by 4
  12. 2021Online Markov Decision Processes with Non-oblivious Strategic Adversarycited by 3
6 more
  1. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  2. 2022A Deep Reinforcement Learning Approach for Finding Non-Exploitable Strategies in Two-Player Atari Gamescited by 3
  3. 2021Neural Auto-Curriculacited by 2
  4. 2022On the Convergence of Fictitious Play: A Decomposition Approachcited by 2
  5. 2023Achieving Better Regret against Strategic Adversariescited by 0
  6. 2026Reinforcement Learning: From Algorithms To Foundation Modelscited by 0