  Policy Space Response Oracles (PSRO) is a deep reinforcement learning
algorithm for two-player zero-sum games that has empirically found approximate
Nash equilibria in large games. Although PSRO is guaranteed to converge to a
Nash equilibrium, it may take an exponential number of iterations as the number
of infostates grows. We propose Extensive-Form Double Oracle (XDO), an
extensive-form double oracle algorithm 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 1-2
orders of magnitude smaller than PSRO. In experiments on a modified Leduc poker
game, we show that tabular XDO achieves over 11x lower exploitability than CFR
and over 82x lower exploitability than PSRO and XFP in the same amount of time.
We also show that NXDO beats PSRO and is competitive with NFSP on a large
no-limit poker game.
