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-observahle 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, A:(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-thhooe 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-coopeaaiiv 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 (Curs)
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-111)
Heinrich, J. and Silver, D. Deep reinforcement learning from self-play in imperfcct-ifformatioon 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": "opYaiGOvh-K", "reviewer": "Reviewer_1Gab", "summary": "This paper extends the PSRO family to efficiently run in extensive form games. This allows the convergence to be linear in number of infostates, in contrast to the potentially exponentially larger matrix game.\n", "questions": "", "limitations": "", "rating": 7, "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": "I think the paper is a nice and important addition to the PSRO algorithm family. I also appreciate that authors include non-tabular methods. The idea is relatively straightforward, as the algorithm simply expands the extensive form game tree and runs CFR (and there is existing work on DO methods that expand the EFG). The paper also mostly does a good job explaining the ideas.\n \nThe experiments are also non trivial and well done.\n \nI have seen this paper before, and I think there are substantial improvements - more experiments and multiple fixes.\n \nI also like the analysis through the k-GMP and m-clone GMP game\n \nComments:\n> [Abstract] Experiments on a modified Leduc poker game 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.\n  I am not sure this is supported by the experiments. The only related graph I see compares 2-Clone Leduc in terms of states visited, not time. I think states visited makes more sense, the appendix should just match the actual experiment.\n \nMinor:\n> [336] In figure -> In Figure\n> [344] figures -> Figures\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please address.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "auGS0Y9bGA", "reviewer": "Reviewer_6vBM", "summary": "This paper proposes a Double-Oracle adaptation for extensive-form games, called XDO. \nSimilar to how previous work, PSRO, can be viewed as an approximation to the normal-form Double-Oracle, they introduce Neural XDO (NXDO) as an approximation for XDO. \nAuthors prove and experimentally demonstrate on small games that this approach is more computationally efficient, as applying (an approximation of) Double-Oracle to extensive-form games may need many more iterations. \n", "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": "Authors propose XDO as a new algorithm, however I am not entirely convinced of its originality. The algorithm is very closely related to the sequence-form double-oracle (SDO) algorithm, which also claims improved efficiency for similar reasons as XDO does (i.e. small size of supports in each infostate in games). While they somewhat address this in related work, the difference is still unclear to me. \n\n1) What is the difference between \"sequence-form BR\" and \"extensive-form BR\"? I am familiar only with best-response (irrespective of the representation form of the game). Given two restricted games, one for SDO and XDO, would these individual BRs yield different strategies in each case? Can you provide an example that would show the difference?\n2) The SDO algorithm uses temporary leaves and assigns a value to them when the currently added sequences do not lead to a terminal history. Similar problem should probably arise for XDO, so I am not sure if the algorithm is well defined for a game like in https://cw.fel.cvut.cz/b201/_media/courses/be4m36mas/mas_l07_beyond_efgs_2020.pdf slides 8-13. Problem is outlined at slide 12. What value would XDO assign to the temporary leaf, so that the restricted game is well defined and can be solved? \n3) How does XDO deal with chance nodes? Are all actions of chance added to the restricted game? If yes, then I do not think there is a difference between the SDO and XDO algorithms.\n4) If the algorithms are indeed \"fundamentally different\" (L131), please explain why one should prefer XDO vs SDO to make an approximate version of the algorithm (i.e. NXDO vs \"neural SDO\").\n\nThe experimental results with NXDO on small games look very promising for solving large games. Is there a reason why authors did not run NXDO on more challenging games?\n\nOverall, I like this research direction. If I misunderstood the difference between XDO and SDO and authors provide convincing answers to the questions and update the paper accordingly, I am willing to raise the overall score.\n\n\nMore details:\n\n- Proposition 2: I believe this claim should be made about Double-Oracle, not PSRO. Similar to how Algorithm 2 does not have a termination criterion, PSRO also does not necessarily terminate.\n- L121: DREAM [25] and ARMAC [9] are model-free regret-based deep learning approaches.  -- so? What are authors trying to say?\n- L360:  is be a -> is a \n\nSupplementary:\n- L59: all 6 pure strategies -> all 9 ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A well-know drawback of using Double-Oracle algorithms is the cost of computing the (oracle) best responses. This limitation should be more discussed in the work and shown in the experiments (perhaps by stating the running time of the algorithms).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Bm02j5sKV99", "reviewer": "Reviewer_H8Fr", "summary": "The authors propose Extensive-Form Double Oracle (XDO), an extensive-form double oracle algorithm that is guaranteed to converge to an approximate Nash equilibrium in two-player zero-sum extensive-form games. The algorithm extends ides introduced in PSRO to the extensive-form setting in a simple and natural way. In particular, XDO mixes best responses at every information state, which guarantees convergence in a number of iterations which is linear in the number of information states. Moreover, the authors show how to apply XDO within an RL-like framework where best responses at each iteration are estimated through deep RL techniques. The experimental evaluation shows that this approach is promising both in the tabular and in the \"neural\" version.", "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": "I think the paper makes a useful contribution in formalizing how to generalize PSRO to the extensive-form setting. Hovewer, since XDO is a natural extension of PSRO I think the technical contributions of the paper are not particularly exciting. The main value of the work would be giving a clear reference point for other reserachers who want to \"safely\" apply PSRO-like methods to extensive form games.\n\nI think the experimental evaluation could be more convincing if the following items were addressed:\n\n- The game instances used for plot  (a) and (b) are too small to be convincing, and they do not really help in evaluating which is the limit of scalability of XDO. Moreover, it would be better to include a baseling using RM+ (like CFR+).\n- I'm not familiar with Oshi-Zumo so it's difficult to evaluate plot (c). Adding a remark on the dimensions of these games in terms of information states or sequences in the main paper would help when reading the experimental results. If one were ok with exploitability 10^-2, XDO would double the number of states visits. \n\nMinor comments: I would add a remark on the players having perfect recall in Theorem 1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See Main review", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "5ozae752bX", "reviewer": "Reviewer_ae9r", "summary": "This paper introduces XDO and NXDO, algorithms for solving sequential imperfect-information games that are intended to be more scalable for games with very large action spaces. XDO starts by including only a small number of actions in every infostate and alternates between solving the constrained game and adding full-game best response actions to the constrained game. In the limit XDO is guaranteed to converge, and requires a number of iterations that is linear in the number of infostates (rather than exponential, which standard double oracle requires).\n\nNXDO is a related algorithm that uses neural network function approximation. The algorithm maintains a population of candidate policies. At each infostate, the algorithm choose a probability distribution over these candidate policies. Once an equilibrium is computed in this restricted pool of policies, a full-game best response is computed and added to the pool. NXDO also converges, though it could potentially be much slower than traditional solvers because the number of candidate policies could grow extremely large.", "questions": "", "limitations": "", "rating": 5, "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": "## XDO\n\nXDO appears to be quite similar to related work in [1, 2, 3]. The authors highlight the similarity to [1] but not the other work. In particular, SAEF in [2] is quite similar. SAEF starts with a small action abstraction of a game and then repeatedly alternate between solving the abstracted game using CFR and adding high-regret full-game actions to the abstraction.\n\nThroughout the XDO section the authors compare XDO to PSRO, but given that this is a tabular setting with exact best responses, is there any difference between PSRO and DO?\n\nRegarding Figure 3, a lot seems off in these plots. It would be helpful if these plots were in log-log to make the performance easier to see. For Figure 3a, why are you comparing to XFP rather than CFR? For 3b and 3c, what form of CFR are you using? Are you using alternating updates? The convergence rate seems unusually slow. Also, what parameters are you using for XDO?\n\n## NXDO\n\nThe authors clearly show that NXDO is beneficial in certain games. However, the paper does a poor job of describing when NXDO is useful and when it is detrimental. The one discussion of this is when the authors say:\n> a drawback of meta-actions that delegate actions to 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. In our experiments, however, NXDO achieves significant improvements in exploitability within a very small number of iterations, such that the issue of action delegation does not becomes an obstacle.\n\nThis seems to be a function of the games you are testing on though. What happens if you run NXDO on Leduc, for example? What about Leduc with 10 cardsin the deck? I'd expect NXDO to do much worse than NFSP in those cases. In general, I think for a technique like this where it can perform quite poorly in some settings, it's important to present results that clarify where it is useful and where it is harmful. The paper currently doesn't do that and only show experiments where NXDO helps. This is my biggest criticism of the paper.\n\nIntuitively it feels like there should be a way to get the benefits of XDO in a neural algorithm without the shortcomings of NXDO in games like Leduc. The paper appears to briefly discuss this with the mention of NXDO-VA. However, the description of NXDO-VA is very terse and I do not think I understand what the algorithm is.\n\n## Overall\n\nGiven the existence of work quite similar to XDO, I feel that there is not much novelty to XDO and a lot of the novelty in the paper is actually in NXDO. However, NXDO has a major weakness that it could perform much worse than alternative algorithms in games with small action spaces (such as presumably Leduc poker, which only ever has at most 3 actions). The paper would benefit from a thorough investigation where NXDO is helpful and where it is harmful. Ideally, the authors would be able to come up with an algorithm like NXDO that is helpful, or at least not harmful, in all settings.\n\n[1] Branislav Bošansky et al. An exact double-oracle algorithm for zero-sum extensive-form games with imperfect information. Journal of Artificial Intelligence 2014.\n\n[2] Noam Brown and Tuomas Sandholm. Simultaneous Abstraction and Equilibrium Finding in Imperfect-Information Games. IJCAI 2015.\n\n[3] Jiří Čermák, Branislav Bošansky, Viliam Lisy. An algorithm for constructing and solving imperfect recall abstractions of large extensive-form games. IJCAI 2017.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The lack of discussion and experiments regarding limitations of NXDO (and to a lesser extent XDO) is the biggest weakness of the paper. The paper would benefit from a greater investigation of the class of games where NXDO hurts performance and where it helps.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission had a range of scores across reviewers, with votes both for reject and accept. However, there is actually a strong consensus on the strength and weaknesses of the paper. Conceptually, it's a fairly straightforward idea, but one that may be worth exploring in light of the performance of other double-oracle methods. However, all reviewers agreed that it is not a particularly novel direction.

The numerical strength of the approach is not very positive: the authors show good results on games that the authors designed in order to get good performance from their proposed algorithms. On the existing games that were tried, the proposed algorithms had fairly weak performance. At the same time, the reviewers all felt that the authors did a good job experimentally: they tried a good number of small and medium-sized games and show that XDO/NXDO performs poorly in certain settings and quite well in other (somewhat contrived) settings. Thus one could argue that the paper is a pretty good reference point for the method: perhaps the approach is not that useful overall, and this paper lays out that performance in a reasonable way. 
The authors are strongly encouraged to include the additional experiments from the rebuttals. 
Decision: Accept (Poster)