Reproduce “XDO: A Double Oracle Algorithm for Extensive-Form Games” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Stephen McAleer, John Lanier, Kevin Wang, Pierre Baldi, Roy Fox
Researchers at the University of California, Irvine introduce Extensive-Form Double Oracle (XDO) and its neural counterpart, Neural XDO (NXDO), a new approach for finding approximate Nash equilibria in two-player zero-sum extensive-form games. The method demonstrates improved efficiency by converging linearly in information states, and NXDO is shown to effectively handle high-dimensional continuous-action sequential games, outperforming existing methods like PSRO and NFSP.
Key insights
- Redefining the double oracle's restricted game to operate directly on the extensive form enables linear convergence in the number of information states, improving upon PSRO's exponential worst-case.
- The approach effectively leverages the concept of sparse-support Nash equilibria, focusing on discovering only relevant actions and thus speeding up convergence by only considering necessary actions at each infostate.
- By combining this extensive-form restriction with deep reinforcement learning, the method becomes compatible with high-dimensional continuous action spaces in sequential games, a capability lacking in many prior methods.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.