XDO: A Double Oracle Algorithm for Extensive-Form Games
Authors: Stephen Marcus McAleer
John Banister Lanier
Kevin Wang
Pierre Baldi
Roy Fox
Venue: NeurIPS 2021 Poster (2021)
Keywords: Double Oracle
Two-player zero-sum games
Reinforcement Learning

Abstract: 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.

XDO: A Double Oracle Algorithm for Extensive-Form Games
Stephen McAleer
John Lanier
Department of Computer Science University of California, Irvine smcaleer@uci edu
Department of Computer Science University of California, Irvine jblanierQuci edu
Kevin A. Wang Department of Computer Science University of California, Irvine kevinvang@kovinnang us
Pierre Baldi
Department Computer Science University of California, Irvine pfbaldi@ics uci.edu
Roy Fox
Department of Computer Science University of California, Irvine royf@uci..o edu
Abstract
Policy Space Response Oracles (PSRO) is reinforcement learning (RL) algo- rithm for two-player zero-sum games that has been empirically shown to find approximate Nash equilibria in large games. Although PSRO is guaranteed converge to an approximate Nash equilibrium and can handle continuous actions, it may take an exponential number of iterations 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 guar- anteed 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 Ledue poker, we find that XDO achieves an approximate Nash equilibrium in a number of iterations an order of magnitude smaller than PSRO. Experiments on 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 sequential multidimensional continuous-actio action game. NXDO the first deep method that can find an approximate Nash equilibrium in high-dimensiionll continuous-action seguential games. Experiment code available at phttts : :/te:t//gttte com/ indyinnnyydddddda
1 Introduction
Policy Space Response Oracles (PSRO) (Lanctot et al., 2017) is reinforcement learning (RL.) method for finding approximate Nash equilibria (NE) large two-player zero-sum games. Methods based on PSRO have recently achieved state-of-the-an art performance on large zero-sum games such as Starcraft (Vinyals al., 2019) and Stratego (McAleer al., 2020). One major benifit of PSRO versus other deep RL methods for two-player zero-sum games is that it is naturally compatible with games that have continuous actions. The only other deep RL method
two-player
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

compatible with continuous actions, self play, is not guaranteed to converge to a Nash equilibrium even in small games like Rock Paper Scissors. Despite the empirical success of PSRO, in the worst case, PSRO may need to expand all pure strategies in the normal form of the game, which grows exponentially in the number of information states (infostates). The reason for this that PSRO based on the Double Oracle algorithm for normal-form games (McMahan et al. 2003), and a mixture of normal-form pure strategies is an inefficient representation of extensive-form policies.
In this work, we propose new double oracle algorithm, Extensive-Form Double Oracle (XDO), that designed for extensive-fomi (sequential) games. Like PSRO, XDO keeps a population of pure strategies. At every iteration, XDO creates restricted game by only considering actions that are chosen by at least one strategy in the population. This restricted game is then approximately solved via an extensive-form game solver, such as Counterfactual Regret Minimization (CFR) (Zinkevich et al. 2008) or Fictitious Play (FP) (Brown 195T). to find a meta-NE, which extended to the full game by taking arbitrary actions at infostates not encountered in the restricted game. Next, best response (BR) to the restricted game meta-NE is computed and added to the population. XDO can be viewed as version of PSRO where the restricted game allows mixing population strategies not only at the root of the game, but at every infostate.
XDO is guaranteed to converge to an approximate NE in number of iterations that is linear in the number of infostates, while PSRO may require a number of iterations exponential in the number of infostates. Furthermore, on a worst-case family of games for the lower bound on the number of PSRO iterations, we show that XDO converges
number of iterations that does not grow with the number of infostates, and grows only linearly with the number of actions at each infostate.
We also introduce neural version of XDO, called Neural XDO (NXDO). NXDO be used in games that are large enough to benefit from the generalization over infostates induced by neural-network strategies. NXDO learns approximate BRs through any deep reinforcement learning algorithm. The restricted game consists of meta-actions, each selecting a population policy to play the next action. This restricted game is then solved through any neural extensive-form game solver, such as NFSP (Heinrich & Silver 2016) or Deep CFR (Brown et al. 2019). In our experiments, we use PPO (Schulman et al.. (017) or DDQN (Van Hasselt et al.[[2166 for the approximate BR and NFSP as the restricted game solver. Although convergence guarantees may not apply in such cases, like PSRO, NXDO compatible with continuous action spaces.
In games with a large number of actions, NXDO and PSRO effectively prune the game tree and outperform methods such as Deep CFR and NFSP, which cannot be applied at all with continuous actions. Additionally, because PSRO might require an exponential number of pure strategies, NXDO outperforms PSRO on games that require mixing over multiple timesteps. To demonstrate the effectiveness of our approach on these types of games, we run experiments on two sets of environments. The first, m- m-Clone Ledue, is similar Ledue poker but with every call, fold, and bet action duplicated m times. The second, the Loss Game, is sequential continuous-action multidimensional optimization game which agents simultaneously adjust parameters to maximize or minimize a complex loss function. We show that tabular XDO greatly outperforms PSRO, CFR, and XFP (Heinrich et al., 2015) on m-Clone Ledue. We also show that NXDO outperforms both PSRO and NFSP on m-Clone Leduc and on the contnuuus-acction Loss Game, where NFSP is provided binned discrete action space.
To summarize, our contributions are as follows:
We present tabular extensive-foo formm double oracle algorithm, XDO, that terminates in linear number of iterations in the number of infostates.
We present neural version of XDO, NXDO, that outperforms PSRO and NFSP on both modified Ledue poker and sequential continuous-action games. NXDO is the first method that can find an approximate NE in high-dimensional continuous-action sequential games.
2 Background
2.1 Extensive-Form Games
We consider partially-observable stochastic games (Hassen et al., 2004) which correspond to perfect- recall extensive-form games (from here on referred to extensive-form games). An extensive-form

---

game progresses through sequence of player actions, and has world state w E W at each step. In an N-player game, A = A x x Ay is the space of joint actions for the players. (w denotes the set of legal actions for player i E N {1,-.. . N) at world state w and a (a1,.... ax) E A denotes a joint action. At each world state, after the players choose a joint action, a transition function T(w, a) E AW determines the probability distribution of the next world state w'. Upon transition from world state w to w' via joint action a, player/ i makes an observation o, = O,(w, a, w'). In each world state w. player receives reward R.(w).
history is sequence of actions and world states, denoted h = (w aa, w² a ................................ w²), where w is the known initial world state of the game. (h) and A,(h) are, respectively, the reward and set of legal actions for player in the last world state of history h. An infostate for player i. denoted by s,, is a sequence of that player's observations and actions up until that time (h) = (af. o ai...., of), Define the set of all infostates for player to I,. The set of histories that correspond to an infostate s; is denoted H((s:) = (h: s((h) = 8;), and it is assumed that they all share the same set of legal actions (h)) (h)).
A player's policy T; is function mapping from an infostate to probability distribution over actions. policy profile π is tuple (Ti...., .T)) All players other than are denoted -i, and their policies are jointly denoted T-z-- A policy for a history h is denoted मं (/) = (,(s(()) and (Th) is the corresponding policy profile. We also define the transition function T(h, ag, x=1) E AW as function drawing actions for -i from -H to form = (a,, a-s) and to then sample the next world state w' from T(u, a), where
the last world state in h.
The expected value (EV) vz. (h) for player i is the expected sum of future rewards for player in history h, when all players play policy profile æ. The EV for an infostate 8; is denoted e,"" (ss) and the EV for the entire game is denoted u, (T)) A two-player zero-sum game has dj (TT) + (2(TT) = 0 for all policy profiles v. The EV for an action in an infostate is denoted uf (s;, a.). A Nash equilibrium (NE) is a policy profile such that, if all players played their NE policy, no player could achieve higher EV by deviating from it. Formally, x* a NE if (T(TT) max (T m=,)) for each player i.
The exploitability e(Tr) of a policy profile ι is defined as e((x) Ene max;; Ua (a --:). A best response (BR) policy (T=;) for player i to policy __; is a policy that maximally exploits -=;; (T-;) = arg max+; v; (T; m-:). An e-best response (e-BR) policy BR, (m= for player i to a policy - is a policy that is at most worse for player i than the best response: uy (BBR(TT)) T-1) > (T (B
a - e. An e-Nash equilibrium (c-NE) is a policy profile æ in which, for each player IT is e-BR to -
normal-form game is a single-step extensive-fome game. An extensive-form game induces a normal-form game in which the legal actions for player are its deterministic policies X siEz, As(s:). These deterministic policies are called pure strategies of the normal-form game. Since each de- terministic policy specifies one action at every infostate, there are exponential number of pure strategies in the number infostates. A mixed strategy is a distribution over a player's 's pure strate- gies. Two policies x! and uł for player i are said to be pallizationeqqiialle strategy profile of the other player, both π. and x?. define the same probability distribution over the states of the game.
if for any fixed
Theorem 1 (Kuhn's Theorem (Kuhn & Tucker 1953). Any mixed strategy in the normal form of
game is realization equivalent to a policy in the extensive form of that game, and vice versa.
3 Related Work
There has been much recent work on con--ame-thcooe multi-agent RL (Foerster et al. 2018 Lowe cet al. 2017 Rashid et al.) 2018 Bansal et al. 2017). Most of this work focuses on games with more than two players such as multi-agent cooperative games or mixed competitvee-cooeeaaiiv scenarios. In cooperative environments. self-play has empirically been shown to find an approximate NE (Lowe et al. 2017 Majumdar et al.) 2020), but can be brittle when cooperating with agents it hasn't 't trained with (Lanctot et al. 2017). Self reinforcement learning has achieved expert level performance on video games (Vinyals et al. 2019 Berner et al. 2019 Jaderberg et al. 2019). but is not guaranteed
converge an approximate NE.
Extensive-form fictitious play (XFP) (Heinrich et al. 2015) and counterfactual regret minimization (CFR) (Zinkevich et al. 2008) extend Fictitious Play (FP) Brown 1951) and regret matching (Hart &

---

respectively, to extensive-form games. Deep CFR (Brown et al. 2019 Steinberger 2019 al. 2018) general method that trains neural network on a buffer of counterfactual
MoleCo 2000
values. However, Deep CFR uses external sampling, which may be impractical for games with large branching factor, such as Stratego and Barrage Stratego. DREAM (Steinberger et al. 2020) and ARMAC (Gruslys et al. 2020) are model-free regret-based deep learning approaches. DREAM and
ARMAC have achieved good results in poker games, but since they are based on MCCFR, like Deep CFR. they will not scale to games with continuous actions.
Our work is related pruning approaches (Brown Sandholm 2013a Brown al. 2017) These
methods start with all actions and sequentially remove actions that have low expected value. XDO instead starts with no actions and sequentially adds actions. Our work also related to methods that automatically find abstractions (Brown & Sandholm, 2015b; Cermák et al. 2017).
Close to our work, Bosansky et al. (2014) develop a sequence-fone double oracle (SDO) algorithm. The SDO algorithm iteratively adds sequence-form BRs to a population and then computes meta- Nash on a restricted sequence-form game where only sequences in the population are allowed. In contrast, XDO iteratively adds extensive-form BRs population and then computes a meta-Nash on a restricted extensive form game where only actions the population are allowed. DO, SDO, and XDO are fundamentally different because they operate the normal form, sequence form, and extensive form, respectively. We give a detailed description of the difference between XDO and SDO in the supplementary materials.
3.1 Neural Fictitious Self Play (NFSP)
Neural Fictitious Self Play (NFSP) (Heinrich & Silver 2016) approximates XFP by progressively training best response against average of all past policies using reinforcement learning. The average policy is represented by a neural network and is trained via supervised learning using a replay buffer of past best response actions. Each episode, both players either play from their best response policy with probability = 0.1 or with their average policy with probability 1 17. This experience then added to the best response circular replay buffer and used train the best response for both players with off-policy DQN. If player plays with their best response policy, the data is also added to the average policy reservoir replay buffer and used train the average policy via supervised learning.
3.2 Policy Space Response Oracles (PSRO)
The Double Oracle algorithm (McMahan et al. 2003) algorithm for finding NE in normal-form games. The algorithm works by keeping a population of policies IT' at time t. Each iteration a meta-Nash Equilibrium (meta-NE) = is computed for the game restricted to policies in 11'. Then, best response to this meta-NE for each player (R, is computed and added to the population
IT = II: O (T))( for (1,2).
Policy Space Response Oracles (PSRO) (Lanctot et al. (017)) approximates the Double Oracle algorithm. The meta-NE computed on the empirical game matrix U given by having each policy in the population II play each other policy and tracking average utility in payoff matrix. In each iteration, an approximate best response to the current meta-NE over the policies is computed via any reinforcement learning algorithm. Pipeline PSRO parallelizes PSRO with convergence guarantees (McAleer et al. 2020
3.2.1 PSRO Hard Instance
A primary issue with PSRO is that it is based normal-form algorithm, and the number of pure strategies in normal- representation of an extensive-fome game exponential in the number of infostates. In contrast, our approach implements the double oracle algorithm directly in the extensive-form game, overcoming this problem and terminating in linear number of iterations the number of infostates. The following example helps illustrate this point.
Consider the game in Figure In this game, first, player chooses which Rock Paper Scissors (RPS) game both players play. After player chooses the RPS game, both players know which RPS game they are playing. Then both players simultaneously play an action that RPS game. There are pure strategies for player 1, denoted RI. Pl, S1, R2, P2, S2. But there are 9 pure strategies for player

---

P1
BR
PP
4
R1
P1
S1
R2
P2
S2
P0
4
PH
Q
0
-1
-1
1
1
0
-1
P
0
-1
1
1
11
1 0
(C)
(a)
(b)
Figure 1: PSRO hard instance. (a) Player first chooses which RPS game both players play, Both players know which RPS game they are playing. Then both players simultaneously make their move. (b) The normal form game. Player has pure strategies. (c) The proportion of PSRO trials that expanded each possible number of pure strategies for player 2. In the majority of trials, PSRO had to expand all possible pure strategies.
2. A pure strategy for player 2 specifies what move they play at each infostate. If player 2 played Rock in the first infostate and Paper in the second, that pure strategy is denoted RP. Note that if we generalize this game by including more RPS games and more actions in each game, the number of pure strategies for player will be ||| where |A] is the number of actions and [Z] is the number of RPS games.
We conduct an experiment where we run PSRO with oracle BRs on this game with a random starting population each time. We find that PSRO expands all row (player 2) pure strategies the majority of the time, expanding all 9 strategies in 122 out of 150 trials. These results are shown in Figure Ic We also find that the column player (player 1) expands all pure strategies in all 150 trials.
Extensive-Form Double Oracle (XDO)
We propose Extensive-Forie Double Oracle (XDO), a double-oracle (DO) algorithm designed for two- player zero-sum extensive-form games (Algorithm I. As in other DO algorithms, XDO maintains population of pure strategies, and in each iteration computes a meta-NE of this population. Then the algorithm finds best response (BR) to the meta-NE and adds it to the population.
In XDO, the population induces a different restricted game, and therefore different population meta-NE, than in PSRO (Lanctot et al. 2017). In PSRO, a restricted normal-form game is induced by the empirical payoff matrix of population lation strategies. In XDO, restricted extensive-form game is induced through a transformation on the original base extensive-form game that restricts the allowed actions each infostate only those suggested by any strategy the population.
XDO uses a tabular method such as CFR (Zinkevich et al., 2008) or XFP (Heinrich et al., 2015) to solve the restricted game. The algorithm terminates after iteration in which neither of the players finds a BR that outperforms the meta-NE. When this happens, the meta-NE policies are approximate BRs to each other in the original game well, and the meta-NE is therefore approximate NE of the original game.
Importantly, at each but the final iteration of XDO, at least one player adds some new action at some non-terminal infostate, because a BR cannot outperform the meta-NE with only restricted-game actions. The number of iterations that XDO takes to terminate is therefore most the number of infostates, including terminal ones. In contrast, the best known guarantec for the number iterations that PSRO takes to terminate (Proposition 2) is exponential in the number of infostates, because PSRO may need to add all pure strategies to the population. Moreover, computing the meta-NE in PSRO may become intractable in later iterations the population size increases, while in XDO is bounded by the unrestricted game.
Formally, XDO keeps a population of pure strategies I time I. Each iteration, restricted extensive-form game is created and NE the restricted game computed. The restricted game is created by taking the original game and restricting the actions every infostate to be only the
5

---

Algorithm XDO
1: Input: initial population II
2:
repeat
3: Define restricted game for IT via eq. 1
4: Get c-NE policy n= of restricted game
5: Find (T. (T for i {1,2]
6: if Uy (BR, (T" a x & (T(T**) e for both i then
7: Terminate
8: I IT; (R.) for (1,2)
actions where there exists a policy in the population IT' that chooses that action at that infostate:
(s:) {a e Ai(s:) 3m, E II; s.t. IT( a) 1}.
An e-NE policy x²* is then computed in this restricted game via tabular method such CFR and is extended to the full game by defining arbitrary actions on infostates not encountered in the restricted game. Next, BRs to this restricted game meta-NE [BR ( and (TT**) are computed via an oracle. These BRs are then added to the population of policies: II III (R.() for i (1,
The algorithm terminates when neither player benefits more than from deviating from the meta-NE to the BR, indicating that the meta-NE is an c-NE also in the original game (Proposition[].
To illustrate how XDO works, we demonstrate simple game in Figure The algorithm starts with empty populations. At the first iteration (left diagram). player I adds a BR that plays Left at the first infostate (the root) and Right the second one. Player simultaneously adds BR that plays Right at their single infostate. The restricted game now consists of only these added actions. At the second iteration (middle diagram), player adds BR that plays Right at both infostates, and player 2's BR still plays Right. The restricted game now includes both actions for the root infostate, but only Right in the meta-NF. Next, in the third iteration (right diagram), player keeps the same BR, while player 2's BR plays Left. In the meta-NE of this final restricted game, player plays Left and Right with equal probability at the first infostate, and player 2 plays Left with probability 0.37 and Right with probability 0.63. Since the BRs to this meta-NE do not add any new actions. XDO terminates, and the Meta-NE the NE for the full game. Note that in this example, most actions are needed to find a NE. In games like this, it would be faster to simply solve the original game from the beginning. However, certain games, such as those in our experiments, have Nash equilibria that only need to mix over small subset of actions (Schmid et al.) 2014), in which case solving the XDO restricted game will be much faster than solving the original game.
4.1 Theoretical Considerations
In this section, we present a theoretical analysis of XDO and compare it with PSRO. Our first proposition states that, when XDO terminates, the final meta-NE of the restricted game is an approximate NE of the full game.
Proposition 1. In XDO with CB-B oracle, let x** be the final c2-NE in the restricted game. Then n* is an (c1 + -2) in the full game.
Proof. Due to limited space, all proofs are contained in the supplementary materials.
The next two propositions show an exponential gap in the known guarantees for the number of iterations in which PSRO and XDO terminate. If each non-terminal infostate allows A different actions, PSRO is guaranteed to terminate in Σ, Al iterations, where Z, is the set of non-terminal infostates for player i, while XDO guaranteed terminate in Σ, [Z, iterations.
Proposition Normal-form DO terminates in at most IL,,, AA((s)) iterations.
Proposition 3. XDO terminates in most Σ, In] iterations.

---

P1
P1
P1
P2
P2
P2
P2
P2
P2
2
2
2
Figure 2: Three iterations of XDO (left to right). In these extensive- game diagrams, player (P1) plays the root, then P2 plays without knowing P1's action, and if both played Left P1 plays another action. Pl's reward is number at the reached leaf. Actions in the restricted game are solid, vs. dashed outside the restricted game. Meta-NE actions are blue, vs. black not in the meta-NE.
Tightness of the guarantees. The guarantees in Proposition 2 and Proposition 3 are tight in the sense that they are achieved in some games, but more nuanced analysis required to identify easier cases where these bounds overestimate the complexity of the algorithms. Both PSRO and XDO often outperform these guarantees and terminate in fewer iterations. A case in which PSRO expands all pure normal-fome strategies of an extensive-fore game is described in the supplementary materials.
XDO can add multiple actions in each iteration. In practice, XDO often outperforms the guarantee of Proposition 3 because it adds multiple actions in each iteration. Here we present and analyze a family of games in which XDO terminates in asymptotically fewer iterations than suggested by the bound in Proposition
-1
4
2
1
4
4
In a generalized matching pennies (GMP) game, both players si- multaneously choose of actions. The payoff player is k-GMP index j between
n 1 if the actions match, or 11 if they are different. game (Figure B) chance node first selects and k, and then the players play the j'th of k identical GMP games. The following proposition provides tighter performance bound for XDO in this case, 2n iterations instead of >,, [Z|| = 22(n++ 1) (there kn terminal infostates for each player). For PSRO on k-GMP, no tighter bound than the 2n indicated by Proposition 2 known.
Figure A 2-GMP game with
3 actions. The chance node selects uniformly at random which generalized matching pennies game is played. Both players know which stage game they play.
Proposition In k-GMP with n actions, XDO terminates in 2n iterations.
Size of the restricted game. The number of iterations each algorithm does not provide the full picture of their performance, since iterations can require vastly different computation times. Intuitively, the restricted game in XDO is much larger than in PSRO when both algorithms have the same population size, because XDO induces extensive-fore restricted game with all discovered actions, while PSRO induces a normal-form restricted game with population policies as actions. However, as both algorithms progress, the XDO restricted game is bounded in size by the original game, while PSRO can induce a game with exponentially many actions.
XDO for sparse-support policies. XDO is useful when the policies in the population do not cover the full original game, because when they do, finding the restricted game meta-NE is as hard as solving the original game. The motivation behind XDO is that, in games where the NE policies are supported by few actions most infostates, XDO has the potential to quickly find these actions and terminate without expanding the full game.
To analyze this behavior, consider the m-clone GMP game, in which there are mmn actions partitioned into equal classes. The actions of the two players are considered a match (with payoff 1 to player 1) they belong to the same class. In (k, m))-cloee GMP, a chance node selects among identical m-clone GMP games. The following proposition states that in (k, -clonene GMP with
7

---

Algorithm 2 NXDO
1: Input: initial population II
2: repeat
3: Define restricted game for IT via eq. (2)
4: Get c-NE policy n= of restricted game via NESP
5: Find (RR((("''" for i {1,2] via DRL
6:
m+ IT (R,(T for (1,2)
classes, XDO terminates after adding most 2n actions for each player, instead of the full game of kmn actions.
Proposition 5. In (ke, mll-looe GMP with n classes, XDO adds at most 2n actions for each player:
PSRO lower bound. Similarly to XDO, PSRO can also outperform the guarantee of Proposition
in certain cases. Generically, however, the linear upper bound on XDO established by Proposition 3
>; [I,], is also a lower bound on the normal-form population size of pure strategies that is needed to support NE in PSRO. To show this, consider perturbed k-GMP game, in which the payoff's in each GMP game are slightly modified to induce & distinct NE. The following proposition establishes
a linear lower bound for PSRO in perturbed k-GMP games.
Proposition 6. There exist perturbed k-GMP games with n actions in which PSRO cannot terminate in fewer than k(n + iterations.
5 Neural Extensive-Fori Double Oracle (NXDO)
Neural Extensive-Food Form Double Oracle (NXDO) extends XDO to large games through deep reinforce- ment learning (DRL). Instead of using oracle best response, NXDO instead uses approximate best responses that are trained via any DRL algorithm, such as PPO (Schulman et al., 2017) or DDQN (Van Hasselt et al. 2016), Instead of representing the restricted game explicitly the set of allowed actions in every infostate, to create its restricted game, NXDO replaces the original game action space with discrete set of meta-actions, each corresponding population policy which the actual action choice is delegated.
Formally, NXDO (Algorithm 2 keeps a population of DRL, policies ITo at time f. Each iteration, restricted extensive-form game is created and a meta-NE. to the restricted game computed. The restricted game has meta-actions at every infostate that pick one policy from the population
Vs; E I AT(s:) 11, []
While the action space differs, the restricted game states, observations, and histories remain the same in the original game. After each player selects meta-action that indicates population policy, an action is sampled from that population policy and used for the world state transition. With m/ mi....,,T, mTl the population policies for player the transition function in the restricted game satisfies
Th a", w0) ΣI m (()
With the restricted game thus defined, an e-meta-NE म TT is computed in this restricted game via DRL. method for finding NE, such as NFSP (Heinrich & Silver 2016) or DREAM (Steinberger ct al. 2020). Approximate BRs BR, (xT5+) and BRg (x to this meta-NE are computed via DRL algorithm. such as PPO DDQN. These BRs then added to the population of policies: 11 = 11 U (x for i E (1,2). Provided that the DRL best responses are sufficiently close to oracle best responses and the inner-loop solver finds sufficiently close approximate NE of the restricted game, NXDO inherits the same convergence properties as XDO. In practice, contemporary DRL methods lack any guarantee of providing approximate NE BRs. Nevertheless, show experimentally that exploitability can decrease through execution of NXDO faster than it does for PSRO and NFSP.
Because the original game action space has no influence on the NXDO restricted game action space, NXDO, like PSRO, is compatible with extremely large and continuous action spaces, provided

---

Leduc
2-Cione Leduc
Oshi-Zumo
XBO (Our))
XnD (lirs)
KBO (lims) 5DC MOOFRIES
20'
500
PSRO
-10
50C
MCCFRIES
CFf
OFR
10
10"
150
1.5
3.0
Rarations
Statos Vistod
1H
States Visted
(b)
(c)
Figure 4: (a) Exploitability in Ledue poker of XDO PSRO. SDO, and XFP with oracle BRs throughout their iterations; (b) Exploitability in 2-Clone Leduc poker as a function of the number of game states visited by XDO, SDO, CFR and MCCFR with external sampling (ES); (c) Exploitability in Oshi-Zumo as a function of the number of game states visited by XDO, SDO, CFR*, and MCCFR-ES
that the deep RL BRs can operate in such an action space well. We demonstrate this capability in Loss Game experiments. in which NXDO and PSRO continuous-action PPO BRs. While no convergence guarantees are known in continuous-actiin games, NXDO and PSRO empirically produce meta-Nash strategies that are hard to exploit in experiments.
drawback of meta-actions that delegate actions population policies is that, as in PSRO, the number of meta-actions grows linearly with the number of iterations. This can eventually make the restricted game harder to solve than the original game. our experiments, however, NXDO achieves significant improvements in exploitability within very small number of iterations, such that the issue of action delegation does not become an obstacle. discrete action space games where is tractable, we also consider variant, NXDO-VA, where the restricted game is explicitly calculated and defined with valid and invalid original -amee actions in the same way as with tabular XDO, using equation (T). Because its restricted game action space size is at most equal to that of the original game, NXDO- VA does not suffer from the aforementioned drawback.
Experiments
Tammelin 2014) for the inner-loop meta-NE solver. We compare XDO with PSRO Lanctot et al. 2017) and
For the tabular experiments,
XDO with an oracle best response (BR) and CFR +
XFP (Heinric et al. 2015),, which use oracle BRs as well. We also compare with CFR + both CFR and XFP we follow the implementations in OpenSpiel (Lanctot et al. 2019). We compare SDO, using the same oracle BR and meta-NE solver XDO. Since CFR XFP, SDO, and XDO are deterministic, we do not plot error bars for these algorithms. For the neural experiments, we use NXDO with NFSP (Heinrich & Silver 2016) as the meta-NE solver and PSRO with FP (Brown) 195 as the meta-NE NE solver. NXDO and PSRO share the same BR configuration, using DDQN (an Hasseli al., 2016) for discrete action spaces and PPO (Schulman et al. 2017) for continuous action spaces. We compare these algorithms on m- m-Clone Ledue poker, Oshi Ouhi-Zumo, and the Loss Game, described the supplementary materials.
and for
6.1 Tabular Experiments with XDO
Finding normal-form meta-NE can be much less efficient and more exploitable than finding an extensive-fome meta-NE. This means that PSRO will often require many more pure strategies to achieve similar level of exploitability SDO, XFP, and PSRO with an oracle BR on Leduc poker. Even after 150 iterations, PSRO remains significantly more exploitable than XDO over 20x fewer iterations than PSRO. In large games where calculating many approximate BRs via reinforcement learning expensive, requiring vastly more iterations can render PSRO infeasible. XFP performs similarly to PSRO in Leduc, as its average policy is equivalent to uniformly mixing population strategies the root of the game. SDO takes more iterations than XDO to achieve low exploitability, because it adds fewer actions to the restricted game per iteration.
XDO. Figure 4a summarizes the results of running XDO,
iterations. XDO achieves exploitability of 0.1 in

---

20-Cione Leduc
2-Dimerssional Loss Garre
16-Dimens onal Loss Game
3.
RX00 (Dund]
Aopmos balortaitty
211
XXD0 (Dars)
Aogins Sxprotaatt
10.0
NADD (furs)
2,6
MXDD VA (Ou's)
PSRD
PSRO
PSRO
NFSP 1000 Action
1.0
NFSP
30
VOS--LORAAction Actions
0.4
2.5
0.
600
3,6 Epcodes
Eptsodes
1m5
1x7
E5600.05
192
(a)
(b)
(c)
Figure 5: (a) Exploitability in 20-Clone Leduc poker of NXDO, NXDO-VA, PSRO, and NFSP as function of episodes gathered; (b and e) Approximate exploitability as a function of episodes gathered in the continuous-action Loss Game of NXDO, PSRO, and NESP (with binned discrete actions).
We compare XDO with SDO, CFR and MCCFR (Lanctot et al. 2009) in 2-Clone Ledue poker. In Figure 4b we plot the exploitability of these algorithms as function of the number of game states visited by the algorithms. Since XFP and PSRO only use BR oracles, we do not include them in this analysis. Since CFR + updates every infostate every iteration, we increase the number of cloned actions, the performance of CFR will deteriorate. In contrast, XDO will tend to not add cloned actions, which allows the inner-loop CFR to expand fewer infostates. These results for XDO are with a deterministic best response oracle. We found that if XDO randomly chose a best response instead, then XDO would still outperform CFR+, but not by as much. The results in Figure suggest that on Oshi-Zumo XDO outperforms SDO, MCCFR, and, to a lesser degree, CFR We do not include XDO with MCCFR as the inner loop solver because did not perform as well XDO with CFR
6.2 Neural Experiments with NXDO
In Figure 5a we compare the exploitability of NXDO and NXDO- VA with PSRO and NFSP on 20-Clone Ledue poker. DDQN is used to train NXDO and PSRO BRs. Similar to the tabular experiments, we find that NXDO outperforms both methods. However, we find that the margin by which NXDO outperforms these methods is smaller than in tabular experiments. This can be attributed to the large proportion of experience required by NFSP to solve the restricted game relative experience spent learning BRs. Training details and an analysis on the proportion of experience spent in the inner vs outer loop of NXDO are included in supplementary materials.
We also test NXDO and PSRO the 2D and 16D continuous- Loss Game, shown in Figures PPO is used to train NXDO and PSRO BRs. In the 2D action space game, we compare to NFSP with binned discrete action space. Because calculating exact exploitability is intractable for the Loss Game, for each algorithm checkpoint, we measure approximate exploitability by training a continuous-action PPO best response against it until saturation and measuring the BR's final mean reward. NXDO outperforms NESP in the 2D game while operating in a continuous action space and outperforms PSRO in the 2D and 16D game which conjecture due to more effective use of population strategies in its restricted game.
Conclusion
PSRO and NXDO are the only existing game-theoretic deep RL methods that can work on large continuous-acto action games. In games where the NE must mix in many infostates, but only small fraction of all actions are in the support of the NE at each infostate, we expect XDO and NXDO to outperform PSRO, because PSRO may require a superlinear, or even exponential number of pure strategies. We also expect XDO and NXDO to outperform CFR and NFSP, respectively, on discrete- -atretee-ationnnoo games where the NE only needs to mix over small fraction of actions. This is because CFR and NFSP scale poorly with the number of actions the game, but XDO and NXDO tend to discover set of relevant actions and ignore actions that are dominated or redundant. We hypothesize that games with these properties are prevalent across a number of domains such as large board games, video games, and robotics applications.
10

---

8 Acknowledgements
The authors would like to thank Mare Lanctot and Julien Perolat for interesting and helpful discussions, and Chinmay Tyagi for help in prototyping related concepts.
Roy Fox's research is partly funded by the Hasso Plattner Foundation.
References
Bansal, T., Pachocki, J., Sidor, S., Sutskever, I., and Mordatch, I. Emergent complexity via multi-agent competition. arXiv preprint arXiv:/710.03745. 2017.
Berner, C.. Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q..
Hashme, S., Hesse, C., et al. Dota 2 with large scale deep reinforcement learning. arXiv preprini arXiv: 1912.06600, 2019.
Bosansky, B., Kiekintveld, C., Lisy, V., and Pechoucek, M. An exact double-oracle algorithm for zero-sum extensive-form games with imperfect information. Journal of Artificial Intelligence Research, 51:829 -262 2014.
Brown, G. W. Iterative solution of games by fictitious play. Activity analysis of production and allocation, pp. 374-376, 1951.
Brown, N. and Sandholm, T. Regret-based pruning in extensive-fomm games. In NIPS, pp. 1972-1980, 2015a.
Brown, N. and Sandholm, Simultaneous abstraction and equilibrium finding in games. In Twenty-fourth international joint conference on artificial intelligence, 50.
Brown, N., Kroer, C., and Sandholm, T. Dynamic thresholding and pruning for regret minimization.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Brown, N., Lerer, A., Gross, S., and Sandholm, T. Deep counterfactual regret minimization. In International Conference on Machine Learning, pp. 793-802, 2019.
Čermák, J., Bošansky, B., and Lisy, V. An algorithm for constructing and solving imperfect re- call abstractions of large extensive-form games. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp- 936-942, 2017.
Foerster, J., Farquhar, G., Afouras. T., Nardelli, N., and Whiteson, S. Counterfactual multi-agent policy gradients. Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Gruslys, A., Lanctot, M., Munos, R., Timbers, F., Schmid, M., Perolat, J., Morrill, D., Zambaldi, V., Lespiau, J.-B., Schultz, J., et al. The advantage regret-matching actor-critic. arXiv preprint arXiv:2008. /2234, 2020.
Hansen, E. A.. Bernstein, D. S.. and Zilberstein, S. Dynamic programming for partially observable stochastic games. In AAAI, volume 4, pp. 709-715, 2004.
Hart, S. and Mas-Coleld A. A simple adaptive procedure leading to correlated equilibrium. Econo- 2000.
metrica, (8(5))1117-11))
Heinrich, J. and Silver, D. Deep reinforcement learning from self-play in imperfcct-informatioon games. arXiv preprint arXiv:1603.01121, 2016.
Heinrich, J., Lanctot, M., and Silver, D. Fictitious self-play play in extensive-form games. In International Conference on Machine Learning, pp. 805-813, 2015.
Jaderberg, M., Czarnecki, W. M., Dunning. I., Marris, L.., Lever, G., Castaneda, A. G., Beattie, C.,, Rabinowitz, N. C., Morcos, S., Ruderman, A., et Human-level performance in 3d multiplayer games with population-based reinforcement learning. Science, 364(6443):859-8888 865, 2019.

---

Kuhn, H. W. and Tucker, A. W. Contributions to the Theory of Games, volume 2. Princeton University Press, 1953.
Lanctot, M., Waugh, K., Zinkevich, M., and Bowling, M. H. Monte carlo sampling for regret minimization in extensive games. In NIPS, pp. 1078-1086, 2009.
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., and Graepel, T. A unified game-theoretic approach to multiagent reinforcement learning. Advances in Neural Information Processing Systems, pp. 4190-4209 2017.
Lanctot, M.. Lockhart, E., Lespiau. J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S.. Timbers, F., Tuyls, K., Omidshafici, S., et al. Openspiel: A framework for reinforcement learning in games, arXiv preprint arXiv: wet.: 09453, 2019.
Li, H., Hu, K., Ge, Z., Jiang. T., Qi, Y., and Song, I.. Double neural counterfactual regret minimization. arXiv preprint arXiv: 12. 10607, 2018.
Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Abbeel, O. P., and Mordatch, I. Multi-agent actor-critic for mixed systems. pp. 1379-6390 2017.
environments. In Advances in neural information processing
Majumdar, S., Khadka, S., Miret, S., Mcaleer, S., and Tumer, K. Evolutionary reinforcement learning for sample-efficient multiagent coordination. In International Conference on Machine Learning, pp. 6651 6651-6660. PMLR, 2020.
McAleer, S., Lanier, J., Fox, R., and Baldi, P. Pipeline psro: A scalable approach for finding approximate nash equilibria in large games. 2020.
McMahan, H. B., Gordon, G. J., and Blum, A. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 536-543, 2003.
Rashid, T., Samvelyan, M., De Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint arXiv: 1485, 2018.
Schmid, M., Moravcik, M., and Hladik, M. Bounding the support size in extensive form games with imperfect information. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.03777 2017.
Steinberger, E. Single deep counterfactual regret minimization. arXiv preprint arXiv: arXiv:1901.00 1901.07621, 2019.
Steinberger, E., Lerer, A., and Brown, N. Dream: Deep regret minimization with advantage baselines and model-free learning. arXiv preprint arXiv:2006. 10410, 2020.
Tammelin, O. Solving large imperfect information games using CFR+. CoRR, abs/1407.5042. 2014. URL http:://axiv..rr owt/:/s////////se/oeoo/oo
abs /400 1t////1000.000 .5422
Van Hasselt, H., Guez, A., and Silver, D. Deep reinforcement learning with double q-learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H.,
Powell, R., Ewalds, T., Georgiev, P., al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)3350-355 2019.
Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. Regret minimization in games with incomplete information. In Advances in neural information processing systems, pp. 1729-1736. 2008.
12


Reviews:
[{"review_id": "bnU8jeyfp-c", "reviewer": "Reviewer_7BdA", "summary": "This paper introduces two variants of the double oracle algorithm for extensive form games, making use of the problem structure to avoid a possibly exponential blowup in problem size in the standard algorithm within the matrix-game setting. The first is a tabular version, with theoretical guarantees, and the second is a version with function approximation for large games. The authors provide results from experiments using both variants.\n\n\n--- after discussion period ---\nIn my opinion, the proposed changes should notably improve the paper -- hopefully making it a clearly acceptable article -- but are too large to assume sight unseen, so that I don't feel I can argue more strongly for acceptance.\n------", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work has a reasonable core: the proposed algorithms modify an existing successful algorithm in an easily understandable way, to address a specific problem.  There are a few issues which I think could be addressed to improve the paper.\n\nMy largest concern is the paper does not give a clear motivation and setting for NXDO. There are fragments of this story scattered throughout the paper, but they aren't tied together in one single place.\n\nFor example, the experimental comparisons given are against NFSP and PSRO. NFSP directly solves games which are too large for tabular methods, but its performance lags behind subsequently developed methods. PSRO has the desirable property that it uses standard RL methods, and solves a simple matrix game. NXDO seems to sit somewhere between these two: NXDO also uses standard RL methods for finding a best respons, but requires a non-tabular function-approximation game-solving method that could be run on the original game, and extra infrastructure for handling restricted games. When should a reader expect this extra effort to be worth it, rather than just directly solving the game with a more complicated method than NFSP? Like DREAM, for example, or ARMAC, or a Deep CFR variant if applicable? Why / when should a reader think it is worth using NXDO on top of one of these methods? Note that I'm not saying this story doesn't exist -- but that the paper should be clearly telling that story.\n\nAs a second example, the paper brings up SDO as related work. It mentions the technical difference of this similar modification of the double oracle algorithm for extensive form games, but makes no further mention of it. Why / when should a reader consider XDO instead? How does it compare? As the closest related work, it should either be compared in the experimental results, or have a very compelling story why it is not compared.\n\nThere are a number of specific issues listed below:\n\nIt is not until page three that it is explicitly made clear that XDO is for two player, zero-sum games. The abstraction and introduction hint at this setting by talking about PSRO being for that class of problems. Don't make readers assume that similarity, make it explicit. It doesn't even require much extra space. E.g., \"We propose Extensive-Form Double Oracle (XDO) for the same setting ...\"\n\nNotation: the DREAM notation used in this paper is describing partially observable stochastic games, as noted in that paper. Extensive form games use an information partition over states rather than a sequence of observation sequeunce, and this is a non-trivial difference without restricting consideration to games that have perfect recall. Extensive form games specify terminal state utility, rather than the POSG transition reward. This POSG notation also does not mention terminal states: important for considering sum of future reward, and computing a best response (which is a hard computation in POSGs without restrictions: e.g., https://wiki.control.fel.cvut.cz/mediawiki/images/0/0f/Bp_2020_kubicek_ondrej.pdf)\n\n\"The SDO algorithm iteratively adds sequence-form BRs to a population and then computes a meta-Nash on a restricted sequence form game where only sequences in the population are allowed. In contrast, XDO iteratively adds extensive-form BRs to a population\". This explanation isn't clear, and should be re-worded. Taking the words literally, there is no clear functional difference here between a best-response policy in sequence form and a best-response policy as a behaviour strategy. Looking at the SDO paper, the difference appears to be that it adds a single sequence -- not a complete policy -- and also uses the default policy within the meta-Nash computation.\n\n\"While we don’t rule out future work extending SDO to large games via neural networks, this is outside the scope of this current paper.\" This phrasing left a negative impression with me: maybe remove the idea of ruling out future work? Something like \"Similarly extending SDO to large games via neural nets is one possible direction for future work.\"\n\nThe related work section paints a good picture of the surrounding research landscape. It would, however, be helpful to include some short summary of why the reader might want to or need to consider XDO. As positive example of this, the paper notes that Deep CFR might be impractical for games with a large branching factor, and PSRO's normal-form representation might grow exponentially in the game size. Most other related work just mentions some difference without stating any of the consequences.  Why might the reader consider XDO over XFP, CFR, DREAM, ARMAC, pruning approaches, or SDO?\n\n\"The number of iterations that XDO takes to terminate is therefore at most the number of infostates.\" How are terminal states going to be added to the basic POSG formulation? Do terminal states correspond to an infostate? If yes, this quoted statement is correct. If no, what happens with policies at terminal infostates given the current definition of policy?\n\n\"To speed up XDO, we start the algorithm with high value of the epsilon parameter that controls the meta-NE approximation quality, and decrease epsilon by half every time the exploitability of the meta-NE in the original game is less than the current epsilon.\" Include this in the Algorithm 1.\n\n\"XDO is useful when the policies in the population do not cover the full original game, because when they do, finding the restricted game meta-NE is as hard as solving the original game.\" I initially misread this sentence. Simplify to something like \"because when they do, finding\" -> \"otherwise finding\"?\n\n\"While no convergence guarantees are known in continuous action space games, NXDO and PSRO empirically produce meta-Nash strategies with low exploitability in our experiments.\" This statement should be phrased in terms of being difficult to exploit, in order to match the actual experiments: NXDO and PSRO did well against a well-trained Deep RL opponent, exploitability wasn't measured. Also -- are these numbers actually low? What does an exploitability of ~2 in the 2D loss game represent?\n\nWhile XDO can't be used on the large games, NXDO could be used on the small games. Why not include NXDO results for Figure 3?\n\nWhy the switch from linear-log to linear-linear plots for the loss games? Either match the format of the other plots, or be very clear about the different in the caption, and justify this different choice in the text.\n\n\"NXDO outperforms NFSP in the 2D game while operating in a continuous action space and outperforms PSRO in the 2D and 16D game due to more effective use of population strategies in its restricted game.\"  This statement should be softened. The conclusion about why NXDO outperforms PSRO is a totally reasonable conjecture, but it's still a conjecture: it's not impossible that it's because the different game and NFSP solution method just happen to produce a better strategy.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "TgzCDSsGKvy", "reviewer": "Reviewer_nx7U", "summary": "This paper presents an extensive-form double oracle (XDO) algorithm to learn an approximate Nash equilibrium for extensive-form game. The authors provide both tabular and neural versions of XDO and evaluate their methods on several tony games.\nThe main contribution of this paper is that it conducts the iteration on an restricted game so that the computation is linear over the number of infostates. This idea is interesting, however, the whole paper is not well written. I listed some concerns, questions and suggestions in the following. Hope it help.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n############################\nSome Concerns/weakness\n\n- This paper is not well written. Some paragraphs are very difficult to follow. There are some key notations or concepts are not well defined before used, which are listed in the following questions.\n\n- It seems that Algorithm 1 is not consistent with the method presented in section 4. For example, in line 192-195, the author said: \"To speed up XDO, we start the algorithm with high value of the $\\epsilon$ parameter that controls the meta-NE approximation quality, and decrease $\\epsilon$ by half every time the exploitability of the meta-NE in the original game is less than the current $\\epsilon$.\" However, i cannot find the $\\epsilon$ reduction in algorithm 1.\n\n- in line 196-209, the author introduces the process of adding action into the restricted game as illustrated in figure 1. It seems one of the most important novelties in this paper. It's expected this method only needs to maintain a portion of information sets when reaching an $\\epsilon$ Nash equilibrium. The number of maintained infosets is highly depended on the given $\\epsilon$. The figure 3 shows the exploitability over the number of visited states. Does the visited states refer to information sets or the one of states from some information sets? \nAlso, the baselines compared in this paper are so weak, you can find some strong baselines like lazy-cfr [1], vectorized cfr [2], linear cfr [3]\n\n- the author said external sampling is the limitation in Deep CFR[4], i  think it's not true. Because it's not expensive to change the external sampling by some more cheaper sampling method, like robust sampling or vectorized sampling in [2].\n\n- how to extensive this method to extremely large game, such as Texas Hold'em, which is impossible to compute the exploitability?\n\n- missing some key related works like [5, 6, 7].\n\n[1] Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect information.\n\n[2] Regret Minimization via Novel Vectorized Sampling Policies and Exploration.\n\n[3] Solving imperfect-information games via discounted regret minimization\n\n[4] Deep counterfactual regret minimization\n\n[5] Double Neural Counterfactual Regret Minimization.\n\n[6] Single deep counterfactual regret minimization\n\n[7] The advantage regret-matching actor-critic\n\n\n############################\nQuestions\n\n\n- what's the meta-Nash Equilibrium? I cannot find its definition, however, it seems very important for readers to understand this paper.\nIn line 147, the paper says \"each iteration a meta-NE $\\pi^{*,t}$ is computed ... \", it's not very clear.\n\n- what's the restricted game? what's the difference between the standard game and the restricted game? I can find some related descriptions about restricted game in line 166-169, but it's not clear enough.\n\n############################\nsome issues/typos \n\n- line 165-166: In XDO, the population induces a different restricted game, and therefore a different population meta-NE, than in PSRO\n\n- line 176-177: When player i adds action ai in infostate si, this adds to the restricted game previously excluded infostates of the form ...\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "How to extend this work to extremely large game? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "TgRyD6CAZFD", "reviewer": "Reviewer_2oEE", "summary": "The paper presents \"extensive-form double oracle\" (XDO), an extension of the double-oracle algorithm to extensive-form games. They demonstrate that, unlike normal-form double oracle, XDO converges in at most linearly many iterations. They also introduce a neural version of their algorithm, and compare it experimentally to prior techniques, exhibiting significantly stronger performance in various games compared to some known techniques.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Merits\n\n1. The paper is very easy to read and well written. \n\n2. XDO seems to have some promise in practice, demonstrating improved performance when combined with NFSP and CFR.\n\nWeaknesses\n\n1. I feel that, overall, the paper is not very novel, especially when compared to SDO which is a very similar idea. I would have liked to see more elaboration on the difference between XDO and the existing techniques SDO and PSRO. For example, when does XDO do better or worse than SDO, in both theory and practice?\n\n2. In some cases, it seems that NXDO seems to simply delegate most of the work of game solving to the meta-NE algorithm. For example, if a game has small branching factor, then the NXDO meta-game will very quickly basically become identical to the original game, in which case NXDO has achieved practically nothing.\n\n4. It is unclear how NXDO stacks up against more recent deep RL-based methods such as DREAM, REBEL, and ARMAC. The paper should give experiments making such comparisons. While NXDO+NFSP (by which I mean NXDO with NFSP as the meta-NE solver) seems to outperform NFSP by itself, it is unclear to me whether this will continue to hold true when the meta-solver is more powerful, e.g., if NXDO+REBEL will significantly outperform REBEL. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "1LVg7lLNoLi", "reviewer": "Reviewer_pMFZ", "summary": "The submission proposes an extensive-form double oracle algorithm (XDO). In contrast to PSRO, which solves for a meta-Nash over the normal-form game induced by its population of strategies, XDO solves for a meta-Nash in a restricted extensive-form game induced by the population. The submission proves that XDO at most requires the number of information states iterations to yield a Nash, in contrast to PSRO, which may require an exponential number in the number of information states. It also proposes a mechanism for scaling XDO with function approximation (NXDO), wherein the action space is set to population of strategies at each information state, at each iteration.\n\nThe submission presents tabular experiments on Leduc poker, where XDO outperforms PSRO and XFP in terms of the number of iterations and on 2-Clone Leduc and Oshi Zumo, where XDO outperforms MCCFR and CFR in terms of the number of states visited. It also presents experiments with function approximation on 20-Clone Leduc, and a 2 and 16 dimensional loss game, where NXDO outperforms PSRO and NFSP in terms of the number of episodes.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "==== Motivation\n\nDouble oracle, as well as fictitious play, have gained traction among deep RL practitioners via the policy space response oracle (PSRO) framework. Among the reasons that the PSRO framework is attractive because it offers a very scalable, model-free approach to approximating Nash equilibria in two-player zero-sum extensive-form games, contrasting counterfactual regret minimization (CFR), which, while successful in smaller games, requires white box access to the model and is difficult to scale.\n\nHowever, as noted by the submission, an undesirable property of PSRO is that it may an exponential number of iterations in the number of information states to converge. Thus, the line of research taken by the submission is well motivated.\n\n==== Presentation\n\nOverall, the submission is well-organized and nicely written. Specific comments are below.\n\nThe submission suggests that its notation is taken from DREAM. While this may be true, it is readily apparent that the submission’s (and DREAM’s) notation is adapted from factored observation stochastic games. It appears that DREAM failed to cite the factored observation stochastic game paper, despite adapting its notation, so I do not fault the submission for its own omission. However, I do think it would be more appropriate to attribute the notation to factored observation stochastic games than to DREAM, and would like to see the submission make that change.\n\nThe submission suggests that it is using extensive form games. In fact, factored observation stochastic games, as used by the submission, are equivalent to partially observable stochastic games, which are only capable of representing a strict subset of extensive form games. While the extensive-form games that are excluded from this subset are not important for the contribution of the submission, it does make the presentation a bit confusing (the algorithm is stated to be for extensive-form but the game formalism is not actually extensive form). Perhaps the best way to handle it is to add a note clarifying that the formalism corresponds to timetable, perfect recall extensive form games.\n\n“In cooperative environments, self-play has empirically been shown to find an approximate NE”. Nitpick: I might be a bit more careful here — some self-play algorithms have theoretical guarantees of convergence (e.g. policy gradients with centralized value functions). Nevertheless, SPARTA, a search algorithm that can only improve policies that are not at a Nash equilibrium, has been shown to offer large benefits in some cases.\n\nFigure (3b) What does the ES part of MCCFR-ES mean?\n\n==== Main Comments\n\nThe related work discusses an existing algorithm sequence-form double oracle. If I understand correctly, the difference between SDO and XDO is that, at a particular information state, SDO includes an action in the restricted game only if there exists a member of the population that can play to that information state AND takes that action in that information state, whereas XDO includes the action if any member of the population takes that action at that information state, even if that information state is not reachable by that member of the population. Is this correct? If so, is there any reason we would expect XDO to outperform SDO? If not, I would appreciate an elaborate explanation regarding the precise differences, as this seems to be an important point from my perspective. In any case, it seems like SDO is an important baseline for XDO. Is there a reason it was not included in the tabular experiments?\n\nThe submission states that is does not provide error bars because XDO is deterministic with an oracle best response. How much does the performance change based on the oracle best response’s tie breaking procedure?\n\nWhile I can appreciate that each of figures 3a, 3b, and 3c offer interesting information, none of them seem like an exactly fair comparison. In figure 3a, as the submission notes, each of these algorithms requires potentially different amounts of computation per iteration. In figures 3b and 3c, if I understand correctly, the computation cost of the best response calculation is not included. It may be informative to include some experiments measuring exploitability as a function of time.\n\nThe submission states that XDO tends not to add cloned actions. It’s not clear to me why this should be the case, unless the best response is specifically inclined to break ties in favor of non-cloned actions (which would feel a bit artificial).\n\nXDO is of interest simply by virtue of its relationship to PSRO and DO, and by virtue of its linear convergence property. However, as a matter of marketing, it is unclear to me whether the submission is suggesting that XDO is competitive in a tabular regime (if so, it is missing comparisons to competitive tabular solvers), or whether NXDO is competitive in a function approximation regime. If the latter, it seems like having the action scale in the population size is highly undesirable in games that would require large populations. While NXDO-VA removes this requirement, it would seem to require evaluating every member of the population at each relevant information state to determine which action space to use, which is also highly undesirable.\n\nHow is PSRO being implemented in the experiments? I.E., is it pipeline PSRO or something else?\n\n========\n\nI think the submission is well-motivated and well-written. I am open to raising and look forward to hearing the authors' thoughts on the comments above.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents two algorithms extensive-form double oracle (XDO) and a a neural version NXDO, for solving two-player zero-sum games. The technique is clearly inspired by Policy-Space Response Oracles (PSRO): the main algorithmic novelty is casting the meta-game as an iteratively-built extensive-form game rather than normal-form, which allows for greater scale. Experiments demonstrate XDO and NXDO's better empirical convergence when the action space is arbitrarily modified to add nonsensical actions, which supports the motivation. The paper also presents some significant and novel theoretical results on double-oracle and XDO/NXDO, including an example where double oracle (along with vanilla PSRO) realizes its worst case of exponential iterations, while XDO is guaranteed to terminate in linear number of iterations.

There are several criticisms, the main one being that of the focus of the contribution is not on NXDO or its applicability in continuous-action games. I agree that this is easily fixed without (too) substantial modification to the text and does not require further review. On the point of novelty given SDO, as indicated in the response, the distinction between XDO and SDO is that one operates in sequence-form space (SDO) while the other in extensive-form space (XDO/NXDO), the latter being much more convenient to work with. This can be better highlighted in the text. Also, it is not immediately clear that SDO could offer a neural variant for scale as easily as XDO does, which seems aligned with the motivation.

Finally, the paper misses some clearly related work, which should be cited and mentioned in the paper:  Cermak et al. "An Algorithm for Constructing and Solving Imperfect Recall Abstractions of Large Extensive-Form Games", IJCAI 2017.
Decision: Accept (Poster)