Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
The 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.

main_review: 
############################
Some Concerns/weakness

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

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

- 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? 
Also, 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]

- 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].

- how to extensive this method to extremely large game, such as Texas Hold'em, which is impossible to compute the exploitability?

- missing some key related works like [5, 6, 7].

[1] Lazy-CFR: fast and near optimal regret minimization for extensive games with imperfect information.

[2] Regret Minimization via Novel Vectorized Sampling Policies and Exploration.

[3] Solving imperfect-information games via discounted regret minimization

[4] Deep counterfactual regret minimization

[5] Double Neural Counterfactual Regret Minimization.

[6] Single deep counterfactual regret minimization

[7] The advantage regret-matching actor-critic


############################
Questions


- what's the meta-Nash Equilibrium? I cannot find its definition, however, it seems very important for readers to understand this paper.
In line 147, the paper says "each iteration a meta-NE $\pi^{*,t}$ is computed ... ", it's not very clear.

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

############################
some issues/typos 

- line 165-166: In XDO, the population induces a different restricted game, and therefore a different population meta-NE, than in PSRO

- line 176-177: When player i adds action ai in infostate si, this adds to the restricted game previously excluded infostates of the form ...


limitations_and_societal_impact: How to extend this work to extremely large game?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

The 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.
main_review: ==== Motivation

Double 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.

However, 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.

==== Presentation

Overall, the submission is well-organized and nicely written. Specific comments are below.

The 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.

The 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.

“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.

Figure (3b) What does the ES part of MCCFR-ES mean?

==== Main Comments

The 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?

The 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?

While 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.

The 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).

XDO 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.

How is PSRO being implemented in the experiments? I.E., is it pipeline PSRO or something else?

========

I 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.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.


--- after discussion period ---
In 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.
------
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.

My 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.

For 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.

As 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.

There are a number of specific issues listed below:

It 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 ..."

Notation: 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)

"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.

"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."

The 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?

"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?

"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.

"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"?

"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?

While 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?

Why 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.

"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.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: Merits

1. The paper is very easy to read and well written. 

2. XDO seems to have some promise in practice, demonstrating improved performance when combined with NFSP and CFR.

Weaknesses

1. 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?

2. 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.

4. 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. 
limitations_and_societal_impact: Adequately addressed.
review_title: null

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)