Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies learning algorithms in zero-sum extensive form games. While there has been a huge amount of interest in recent years in understanding the convergence of learning algorithms to Nash equilibria in continuous or normal form  zero-sum games, this has not extended as much to extensive form games. This paper makes use of prior works that allows such games to be formulated as a bilinear zero-sum games over action sets known as treeplexes that capture the sequential nature of the actions in the game. The authors then analyze the family of Optimistic Online Mirror Descent (OOMD) algorithms in such games due to their strong last-iterate guarantees in normal form games. In particular they first show that counterfactual regret minimization can diverge in extensive form games (using rock-paper-scissors as an example) before showing that OOMD algorithms with strongly convex regularizers enjoy last iterate convergence. The authors again invoke prior works to give convergence rates for vanilla GDA, give new convergence rates for vanilla optimistic multiplicative weights, and then provide a new analysis of the last-iterate convergence for a previously proposed algorithm known as Dilated Optimistic Multiplicative Weight Update which is specialized to the structure of a treeplex (and therefore actually implementable).
main_review: This paper gives last iterate convergence (and evens some rates) in extensive form games, and though these results are not necessarily surprising given the formulation of extensive form games as bilinear games over polytopes, these results are--- to the best of my knowledge--- new and relevant to the literature. Furthermore, the paper is well written and easy to follow, and the analysis is well explained.

One main place where this paper could be improved I believe is in the preliminaries. Though I understand the space constraints require the authors to cut down some exposition, I think this paper would benefit greatly from a more in depth introduction to extensive form games and how they differ from normal form games (rather than jumping straight into the bilinear formulation and treeplexes). Indeed, the lengthy definition of a treeplex seems less important than introducing the concept of an extensive form game (especially since--- as the authors note--- this class of games is much less common in the learning literature). Furthermore, the actual structure of a treeplex (i.e., branching, parent variables, etc.) does not seem to be integral to the analysis. Also, the definition and exposition surrounding dilated optimistic GDA can also be moved to an appendix since there are no tangible results associated to the algorithm as far as I can see. I think these changes would make the paper much more self-contained.

Another question I have is in the constants in the convergence rates. Do your results capture the dependence on the `depth' (for lack of a better word) of the treeplex, or is this quantity completely hidden in the constants? I'm curious about how the computation of a Nash equilibrium in extensive form games scales with the number of stages in the game.


limitations_and_societal_impact: The authors discuss some of the limitations of their work in the appendix (namely in the difficulties in provided similar rates for the dilated OGDA algorithm). Furthermore the authors discuss the benefits of the dilated algorithms over vanilla algorithms for normal form games.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper appears to be the first to achieve last iterate convergence in extensive form games. Last iterate convergence results have recently been established for optimistic gradient descent algorithms on bilinear saddle point problems. This paper extends these results to extensive form games, which is a nontrivial extension. The authors provide solid theory and experiments to support the claim. 

main_review: I think this is a very strong paper. Last iterate convergence in extensive-form games has been an open problem in this field for some time, and I am happy to see it finally tackled. I wasn’t able to find an error in any of the theory. I was excited to see the very impressive performance on Kuhn poker in the experiments. I think this paper will open up a lot of future work, for example combining this approach with neural networks. I could see future versions of this method surpassing CFR as the go-to extensive form NE solver. One downside is that the techniques are exactly the same as in a recent past paper which solves bilinear constrained optimization problems but just applied to extensive form games, but from my understanding this application is nontrivial so I think the paper is still strong.    

limitations_and_societal_impact: This work is mainly theoretical so I think the authors have adequately addressed the societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers last-iterate convergence of Optimistic Online Mirror Descent in zero-sum perfect-recall extensive-form games. It includes a proof for a general case that the last iterate must convergence in the limit, and specific convergence rates for three particular choices of regularizer function based on commonly used choices of negative entropy and the Euclidean norm -- with inclusion of a fourth result that follows from prior work. The authors provide an experimental comparison of these four OOMD methods with two variants of a popular baseline algorithm, CFR.

--- after discussion ---
There was one issue raised, but there was also a proposed connection so my opinion remains positive and largely unchanged.
------
main_review: The results in this paper are novel, to the limits of my knowledge. I agree with the authors that similar results in prior work assume simplex decision sets, or standard entropy / Euclidean norm regularizer functions that are computationally inconvenient in large extensive form games. The similarity of those conclusions does not trivialize this work: they do not immediately apply to sequential decision making problems.

I found the details to be clearly laid out and reasonably easy to follow, given the paper is largely a theoretical analysis. There were only a few issues that might be addressed, listed below.

The paper does not introduce VOGDA, VOMWU, DOGDA, or DOWMU as novel algorithms. Are they new, strictly speaking, but the authors consider them obvious instantiations of existing OOMD framework using existing common regularizers? Are they previously explored from other work, which should be cited? For example, citation [16] seems at a glance to be looking at DOGDA. The current situation where the provenance is left unclear is awkward. Claim them, or give credit.

I found myself unsure of what conclusions to draw from the experimental section. Why not compare the last-iterate algorithms compared to the last-iterate solution from the CFR+ variants? What is the reader intended to draw from the CFR+ w/ RM+ line? Even more generally, is the reader intended to reach the conclusion that the theoretical analysis is empirically visible, even in some cases where uniqueness of eq'm does not hold? If so, how are they expected to do so, when the step size was too large in one experiment? Or is the reader being sold on the OOMD algorithms (which may or may not be new to this paper) as a method for solving games?

Can a reduced subset of the algorithms be run for longer on Leduc poker to use the theoretically justified step size?  Given the experiments apparently run in under an hour on standard PC hardware, getting two orders of magnitude more steps in four days seems quite reasonable.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors prove the last-iterate convergence of several optimistic algorithms in two-player zero-sum extensive-form games with perfect recalls (by considering the treeplex formulation). In particular, they show that the last iterate of Dilated Optimistic Multiplicative Weight Update (DOMWU) converges geometrically when the Nash equilibrium is unique.
main_review: **Post rebuttal**  
The authors have addressed my concerns, so I have raised my score accordingly. I agree with the other reviewers that proving last-iterate convergence for extensive-form games is an important contribution.

=======================================================================================================

My main concern is that the proof of Theorem 4 is wrong. The authors claim that $\mathbf{z_t}$ converges after showing that $||\mathbf{z}_{t+1}-\mathbf{z}_t||^2\rightarrow 0$, which is clearly wrong. I do not think there is a simple way to fix this error, and thus to evaluate the paper I rather focus on the remaining results (and the proofs thereof seem to form the real technical part of the work).

Without diving into the appendix, I assume all the other results presented in this work are correct (at least the arguments presented in 6.2 and 6.3 seem quite reasonable). Then, I believe the real contribution is in proving that DOMWU converges geometrically to the Nash equilibrium when the latter is assumed to be unique. This provides an efficient algorithm for finding Nash equilibrium of an EFG. The introduction of these algorithms is without doubt also an important contribution if they had never been considered by the community before. (They are quite straightforward to derive from existing methods, but the effectiveness of these methods is demonstrated in the experimental section.)

I also encourage the authors to explain in more detail the treeplex formulation. I did not find it easy to relate it to the usual definition of an extensive-form game. Providing an example, perhaps in the appendix for those games considered for the experiments, will surely help.

limitations_and_societal_impact: The limitations of the work are discussed in the paper.
review_title: null

Meta-review: The reviewers were unanimously positive about the paper, and the rebuttal addressed all major concerns that remained; we are happy to recommend acceptance. Please make sure to implement the issues identified in the review process in the updated version of the paper. 
Decision: Accept (Poster)