# XDO: A Double Oracle Algorithm for Extensive-Form Games

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

## Key facts

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

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Human-level performance in first-person multiplayer games with population-based deep reinforcement learning](https://mlsanity.com/paper/1807.01281/) (2018)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Deep Reinforcement Learning from Self-Play in Imperfect-Information Games](https://mlsanity.com/paper/1603.01121/) (2016)
- [Emergent Complexity via Multi-Agent Competition](https://mlsanity.com/paper/1710.03748/) (2017)
- [Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1811.00164/) (2018)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games](https://mlsanity.com/paper/2006.08555/) (2020)
- [DREAM: Deep Regret minimization with Advantage baselines and Model-free learning](https://mlsanity.com/paper/2006.10410/) (2020)
- [Single Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1901.07621/) (2019)
- [The Advantage Regret-Matching Actor-Critic](https://mlsanity.com/paper/2008.12234/) (2020)
- [Double Neural Counterfactual Regret Minimization](https://mlsanity.com/paper/1812.10607/) (2018)
- [Evolutionary Reinforcement Learning for Sample-Efficient Multiagent Coordination](https://mlsanity.com/paper/1906.07315/) (2019)

## Built on by (most cited first, 30 of 34)

- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [Student of Games: A unified learning algorithm for both perfect and imperfect information games](https://mlsanity.com/paper/2112.03178/) (2021)
- [Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers](https://mlsanity.com/paper/2106.09435/) (2021)
- [Online Double Oracle](https://mlsanity.com/paper/2103.07780/) (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)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [Anytime PSRO for Two-Player Zero-Sum Games](https://mlsanity.com/paper/2201.07700/) (2022)
- [Search in Imperfect Information Games](https://mlsanity.com/paper/2111.05884/) (2021)
- [Efficient Policy Space Response Oracles](https://mlsanity.com/paper/2202.00633/) (2022)
- [Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RL](https://mlsanity.com/paper/2305.17342/) (2023)
- [Fictitious Cross-Play: Learning Global Nash Equilibrium in Mixed Cooperative-Competitive Games](https://mlsanity.com/paper/2310.03354/) (2023)
- [Feasible Adversarial Robust Reinforcement Learning for Underspecified Environments](https://mlsanity.com/paper/2207.09597/) (2022)
- [Co-Learning Empirical Games and World Models](https://mlsanity.com/paper/2305.14223/) (2023)
- [Improving Social Welfare While Preserving Autonomy via a Pareto Mediator](https://mlsanity.com/paper/2106.03927/) (2021)
- [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)
- [Offline Equilibrium Finding](https://mlsanity.com/paper/2207.05285/) (2022)
- [JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2308.04719/) (2023)
- [Accelerate Multi-Agent Reinforcement Learning in Zero-Sum Games with Subgame Curriculum Learning](https://mlsanity.com/paper/2310.04796/) (2023)
- [NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria](https://mlsanity.com/paper/2510.18183/) (2025)
- [ApproxED: Approximate exploitability descent via learned best responses](https://mlsanity.com/paper/2301.08830/) (2023)
- [Online Competitive Information Gathering for Partially Observable Trajectory Games](https://mlsanity.com/paper/2506.01927/) (2025)
- [Data-Augmented Game Starts for Accelerating Self-Play Exploration in Imperfect Information Games](https://mlsanity.com/paper/2605.14379/) (2026)
- [EMAgnet: Parameter-Space EMA Regularization for Policy Gradient Self-Play in Large Games](https://mlsanity.com/paper/2606.23995/) (2026)
- [Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations](https://mlsanity.com/paper/2307.12062/) (2023)

## 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.