XDO: A Double Oracle Algorithm for Extensive-Form Games

2021-03-11 · NeurIPS 2021 12 · Stephen Mcaleer, John Lanier, Kevin Wang, Pierre Baldi, Roy Fox

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.

📄 PDF Abstract BibTeX arXiv:2103.06426

Code (1)

indylab/nxdo 공식 구현 pytorch

Tasks

FormReinforcement Learning (RL)

Anytime PSRO for Two-Player Zero-Sum Games

2022-01-19 · Stephen Mcaleer, Kevin Wang, John Lanier, Marc Lanctot 외

Policy space response oracles (PSRO) is a multi-agent reinforcement learning algorithm that has achieved state-of-the-art performance in very large two-player zero-sum games. PSRO is based on the tabular double oracle (D…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

Online Double Oracle

2021-03-13 · Le Cong Dinh, Yaodong Yang, Stephen Mcaleer, Zheng Tian 외

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…

Online Learning and Solving Infinite Games with an ERM Oracle

2023-07-04 · Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis 외

While ERM suffices to attain near-optimal generalization error in the stochastic learning setting, this is not known to be the case in the online learning setting, where algorithms for general concept classes rely on com…

Binary Classification

Perturbing Best Responses in Zero-Sum Games

2025-11-16 · Adam Dziwoki, Rostislav Horcik arxiv

This paper investigates the impact of perturbations on the best-response-based algorithms approximating Nash equilibria in zero-sum games, namely Double Oracle and Fictitious Play. More precisely, we assume that the orac…

Reevaluating Policy Gradient Methods for Imperfect-Information Games

2025-02-13 · Max Rudolph, Nathan Lichtle, Sobhan Mohammadpour, Alexandre Bayen 외

In the past decade, motivated by the putative failure of naive self-play deep reinforcement learning (DRL) in adversarial imperfect-information games, researchers have developed numerous DRL algorithms based on fictitiou…

counterfactual Deep Reinforcement Learning Policy Gradient Methods