mlsanityData to 7 Oct 2026

XDO: A Double Oracle Algorithm for Extensive-Form Games

arXiv 2103.06426 ↗First posted 11 Mar 2021cs.GT cs.AI cs.LGcited by 34

Not on the map. Why?

Abstract (arXiv)

Policy Space Response Oracles (PSRO) is a reinforcement learning (RL) algorithm for two-player zero-sum games that has been empirically shown to find approximate Nash equilibria in large games. Although PSRO is guaranteed to converge to an approximate Nash equilibrium and can handle continuous actions, it may take an exponential number of iterations as the number of information states (infostates) grows. We propose Extensive-Form Double Oracle (XDO), an extensive-form double oracle algorithm for two-player zero-sum games that is guaranteed to converge to an approximate Nash equilibrium linearly in the number of infostates. Unlike PSRO, which mixes best responses at the root of the game, XDO mixes best responses at every infostate. We also introduce Neural XDO (NXDO), where the best response is learned through deep RL. In tabular experiments on Leduc poker, we find that XDO achieves an approximate Nash equilibrium in a number of iterations an order of magnitude smaller than PSRO. Experiments on a modified Leduc poker game and Oshi-Zumo show that tabular XDO achieves a lower exploitability than CFR with the same amount of computation. We also find that NXDO outperforms PSRO and NFSP on a sequential multidimensional continuous-action game. NXDO is the first deep RL method that can find an approximate Nash equilibrium in high-dimensional continuous-action sequential games. Experiment code is available at https://github.com/indylab/nxdo.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). Builds on 21 of its 40 references that are in the map. First posted on arXiv 11 Mar 2021.

Builds on

21 of 40 references.

References · 21

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  4. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  5. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  6. 2017Counterfactual Multi-Agent Policy Gradientscited by 733
  7. 2018QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 697
  8. 2020Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 475
  9. 2017A Unified Game-Theoretic Approach to Multiagent Reinforcement Learningcited by 265
  10. 2018Human-level performance in first-person multiplayer games with population-based deep reinforcement learningcited by 260
  11. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  12. 2016Deep Reinforcement Learning from Self-Play in Imperfect-Information Gamescited by 153
9 more
  1. 2017Emergent Complexity via Multi-Agent Competitioncited by 117
  2. 2018Deep Counterfactual Regret Minimizationcited by 102
  3. 2014Solving Large Imperfect Information Games Using CFR+cited by 78
  4. 2020Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Gamescited by 47
  5. 2020DREAM: Deep Regret minimization with Advantage baselines and Model-free learningcited by 36
  6. 2019Single Deep Counterfactual Regret Minimizationcited by 20
  7. 2020The Advantage Regret-Matching Actor-Criticcited by 17
  8. 2018Double Neural Counterfactual Regret Minimizationcited by 16
  9. 2019Evolutionary Reinforcement Learning for Sample-Efficient Multiagent Coordinationcited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 9; 2023: 7; 2024: 3; 2025: 4; 2026: 4.

34 papers.

Sort:

By area:

  1. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  2. 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
  3. 2024A Survey on Self-play Methods in Reinforcement Learningcited by 26
  4. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  5. 2021Student of Games: A unified learning algorithm for both perfect and imperfect information gamescited by 22
  6. 2021Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solverscited by 21
  7. 2021Online Double Oraclecited by 18
  8. 2022A Game-Theoretic Framework for Managing Risk in Multi-Agent Systemscited by 13
  9. 2025Reevaluating Policy Gradient Methods for Imperfect-Information Gamescited by 13
  10. 2022Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Gamescited by 11
  11. 2024Policy Space Response Oracles: A Surveycited by 10
  12. 2022Anytime PSRO for Two-Player Zero-Sum Gamescited by 9
22 more
  1. 2021Search in Imperfect Information Gamescited by 8
  2. 2022Efficient Policy Space Response Oraclescited by 8
  3. 2023Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RLcited by 7
  4. 2023Fictitious Cross-Play: Learning Global Nash Equilibrium in Mixed Cooperative-Competitive Gamescited by 6
  5. 2022Feasible Adversarial Robust Reinforcement Learning for Underspecified Environmentscited by 4
  6. 2023Co-Learning Empirical Games and World Modelscited by 4
  7. 2021Improving Social Welfare While Preserving Autonomy via a Pareto Mediatorcited by 3
  8. 2022A Deep Reinforcement Learning Approach for Finding Non-Exploitable Strategies in Two-Player Atari Gamescited by 3
  9. 2021Neural Auto-Curriculacited by 2
  10. 2022Offline Equilibrium Findingcited by 2
  11. 2023JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Gamescited by 2
  12. 2023Accelerate Multi-Agent Reinforcement Learning in Zero-Sum Games with Subgame Curriculum Learningcited by 1
  13. 2025Online Competitive Information Gathering for Partially Observable Trajectory Gamescited by 1
  14. 2025NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibriacited by 1
  15. 2026Data-Augmented Game Starts for Accelerating Self-Play Exploration in Imperfect Information Gamescited by 1
  16. 2026EMAgnet: Parameter-Space EMA Regularization for Policy Gradient Self-Play in Large Gamescited by 1
  17. 2023ApproxED: Approximate exploitability descent via learned best responsescited by 0
  18. 2023Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbationscited by 0
  19. 2024FM3Q: Factorized Multi-Agent MiniMax Q-Learning for Two-Team Zero-Sum Markov Gamecited by 0
  20. 2025The Hidden Game Problemcited by 0
  21. 2026Reinforcement Learning: From Algorithms To Foundation Modelscited by 0
  22. 2026Evolving in the Agent Jungle via History-Informed Opponent Awarenesscited by 0