Last-iterate Convergence in Extensive-Form Games
Authors: Chung-Wei Lee
Christian Kroer
Haipeng Luo
Venue: NeurIPS 2021 Poster (2021)
Keywords: last-iterate convergence
optimistic algorithms
extensive-form games
no-regret learning
two-player zero-sum games
online learning
game dynamics

Abstract: Regret-based algorithms are highly efficient at finding approximate Nash equilibria in sequential games such as poker games. However, most regret-based algorithms, including counterfactual regret minimization (CFR) and its variants, rely on iterate averaging to achieve convergence.  Inspired by recent advances on last-iterate convergence of optimistic algorithms in zero-sum normal-form games, we study this phenomenon in sequential games, and provide a comprehensive study of last-iterate convergence for zero-sum extensive-form games with perfect recall (EFGs), using various optimistic regret-minimization algorithms over treeplexes. This includes algorithms using the vanilla entropy or squared Euclidean norm regularizers, as well as their dilated versions which admit more efficient implementation. In contrast to CFR, we show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast. We also provide experiments to further support our theoretical results.

Last-iterate Convergence in Extensive-Form Games
Chung-Wel Lee University of Southern California leechung@usc.ert edu
Christian Kroer
Columbia University
christian kwoer@columbia edu
Haipeng Luo
University Southern California haipengl@usc.o edu
Abstract
Regret-based algorithms are highly efficient at finding approximate Nash equilibria in sequential games such as poker games. However, most regret-based algorithms, including counterfactual regret minimization (CFR) and its variants, rely iterate averaging to achieve convergence. Inspired by recent advances on last-iterate con- vergence of optimistic algorithms in zero-sum normal-form games, study this phenomenon in sequential games, and provide comprehensive study last-iterate convergence for zero-sum sum extensive-form games with perfect recall (EFGs), using various optimistic regret-minimization algorithms over treeplexes. This includes al- gorithms using the vanilla entropy squared Euclidean norm regularizers, well as their dilated versions which admit more efficient implementation. In contrast CFR, we show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast. We also provide experiments to further support our theoretical results.
1 Introduction
Extensive-form games (EFGs) are an important class of games in game theory and artificial intelli- gence which can model imperfect information and sequential interactions. EFGs are typically solved by finding or approximating Nash equilibrium. minimi-minimizaaionn algorithms are among the most popular approaches approximate Nash equilibria. The motivation comes from classical result which says that two-player zero-sum games, when both players use no-regret algorithms, the average strategy converges to Nash equilibrium [Freund and Schapire, 1999, Hart and Mas- Mas-Colell, 2000, Zinkevich et al., 2007]. Counterfactual Regret Minimization (CFR) [Zinkevich et al., 2007] and it variants such CFR+ [Tammelin, 2014] are based on this motivation.
However, due to their ergodic convergence guarantee, theoretical convergence rates of regret- minimization algorithms are typically limited O(IvVT) or O1/TT) for T rounds, and this also the case in practice [Brown and Sandholm, 2019a, Burch et al., 2019]. In contrast, it is known that linear convergence rates are achievable certain other first-order algorithms [Tseng, 1995, Gilpin et al., 2008]. Additionally, the averaging procedure can create complications. It not only increases the computational and memory overhead [Bowling et al., 2015], but also makes things difficult when incorporating neural networks in the solution process, where averaging is usually not possible. Indeed, to address this issue, Brown et al. [2019] create a separate neural network to approximate the average strategy in their Deep CFR model.
Therefore, a natural idea design regret-minimization algorithms whose last strategy converges (we call this last-iterate convergence), ideally at a faster rate than the average iterate. Unfortunately. many regret minimization algorithms such as regret matching, regret matching+, and hedge, are known
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to satisfy this property empirically and theoretically even for normal-form games. Although Bowling et al. [2015] find that in Heads- Up Limit Hold' em poker the last strategy of CFR+ is better than the average strategy, and Farina et al. [2019b] observe in some experiments the last-iterate of optimistic OMD and FIRL converge fast, theoretical understanding of this phenomenon still absent for EFGs.
In this work, inspired by recent results on last-iterate convergence in normal-form games [Wei et al., 2021], we greatly extend the theoretical understanding of last-iterate convergence of regret- minimization algorithms in two-player zero-sum extensive-form games with perfect recall, and open up many interesting directions both in theory and practice. First, we show that any optimistic online mirror-descent algorithm instantiated with strongly convex regularizer that is continuously differentiable on the EFG strategy space provably enjoys last-iterate convergence, while CFR with either regret matching or regret matching+ fails to converge. Moreover, for some of the optimistic algorithms, we further show explicit convergence rates. In particular, we prove that optimistic mirror descent instantiated with the I-strongly-conee dilated entropy regularizer [Kroer et al., 2020], which we refer to as Dilated Optimistic Multiplicative Weights Update (DOMWU), has a linear convergence rate under the assumption that there is a unique Nash equilibrium; we note that this assumption was also made by Daskalakis and Panageas [2019], Wei et al. [2021] in order to achieve similar results for normal-form games.
2 Related Work
Extensive-form Games Here we focus on work related to two-player zero-sum perfect-recall games. Although there are many game-solving techniques such as abstraction [Kroer and Sandholm, 2014, Ganzfried and Sandholm, 2014, Brown et al., 2015], endgame solving [Burch et al., 2014, Ganzfried and Sandholm, 2015], and subgame solving [Moravcik et al., 2016, Brown and Sandholm, 2019b], these methods all rely on scalable methods for computing approximate Nash equilibria. There are several classes of algorithms for computing approximate Nash equilibria, such as double-oracle methods [McMahan et al., 2003], fictitious play [Brown, 1951. Heinrich and Silver, 2016]. first-order methods [Hoda al., 2010, Kroer et al., 2020], and CFR methods [Zinkevich al., 2007, Lanctot et al., 2009, Tammelin, 2014]. Notably, variants of the CFR approach have achieved significant success in poker games [Bowling et al., 2015, Moravčík et al., 2017, Brown and Sandholm, 2018]. Underlying the first-order and CFR approaches is the sequence-form representation [von Stengel, 1996], which allows the problem to be represented as bilinear saddle-point problem. This leads to algorithms based on smoothing techniques and other first-order methods [Gilpin et al., 2008, Kroer et al., 2017, Gao et al., 2021], and enables CFR via the theorem connecting no-regret guarantees to Nash equilibrium.
Online Convex Optimization and Optimistic Regret Minimization Online convex optimization [Zinkevich, 2003] is a framework for repeated decision making where the goal is to minimize regret. When applied to repeated two-player zero-sum games, it is known that the average strategy converges to Nash Equilibria at the rate of (L/VTT) when both players apply regret-minimizatte whose regret grows on the order of ((VT) [Freund and Schapire, 1999, Hart and Mas-Colell, 2000, Zinkevich et al., 2007]. Moreover, when the players use optimistic regret-miningt pirrettminiizzation algorithms, the convergence rate is improved to O(1/T) [Rakhlin and Sridharan, 2013, Syrgkanis et al., 2015]. Recent works have applied optimism ideas to EFGs, such as optimistic algorithms with dilated regularizers [Kroer et al., 2020, Farina et al., 2019b], CiR-like local optimistic algorithms [Farina et al., 2019a], and optimistic CFR algorithms [Burch, 2018, Brown and Sandholm, 2019a, Farina et al., 202 However, the theoretical results in all these existing papers consider the average strategy, while we are the first to consider last- convergence in EFGs.
algorithms
Last-iterate Convergence in Saddle-point Optimization As mentioned previously, two-player zero-sum games can be formulated as saddle- point optimization problems. Saddle-point problems have recently gained lot of attention due their applications in machine learning, for example in generative adversarial networks [Goodfellow et al., 2014]. Basic algorithms, including gradient descent ascent and multiplicative weights update, diverge even in simple instances [Mertikopoulos et al., 2018 8, Bailey and Piliouras, 2018]. In contrast, their optimistic versions, optimistic gradient descent ascent (OGDA) [Daskalakis et al., 2018, Mertikopoulos et al., 2019, Wei et al., 2021] and optimistic multiplicative weights update (OMWU) [Daskalakis and Panageas, 2019, Lei et al., 2021,

---

Wei et al., 2021] have been shown to enjoy attractive last-iterate convergence guarantees. However, almost none of these results upply the case of EFGs: Wei et al. [2021] show result that implies linear convergence of vanilla OGDA in EFGs (see Corollary 5), but no results are known for vanilla OMWU or more importantly for algorithms instantiated with dilated regularizers which lead to fast iterate updates in EFGs. In this work we extend the existing results on normal-form games to EFGs, including the irappcally-importannt dilated regularizers.
3 Problem Setup
We start with some basic notation. For vector 2, we use 2, denote its i-th coordinate and ||=||> to denote its p-norm (with |||]] being a shorthand for || 22)))). For a convex function v), the associated Bregman divergence is define as (u, v) (0(2) (0v)
(Vv(v), u - v), and y is called s-strongly convex with respect the p-norm if (u, v) > u el holds for all and v in the domain. The Kullback-Leibler divergence, which is the Bregman divergence with respect to the entropy function, is denoted by K).,.-). Finally, we use Ap denote the (P- 1)-dimensionnll simplex and [M] to denote the set {1, 2..,.... N for some positíve integer N.
Extensive-form Games as Bilinear Saddle-point Optimization We consider the problem of finding a Nash equilibrium of two-player zero-sum extensive-form game (EFG) with perfect recall. Instead of formally introducing the definition of an EFG (see Appendix for an example), for the purpose of this work, it suffices to consider an equivalent formulation, which casts the problem as simple bilinear saddle-point optimization [von Stengel, 1996]:
min max x Gy = max min x: T Gy. yEy øEd
(1)
#EX yEy
where G E [111,+1]AMx is a known matrix, and X' C RM and y C RR- are two polytopes called treeplexes (to be defined soon). The set of Nash equilibria then defined as 3 X x y", where Gy and y argmax mingex x Gy. Our goal is find point z E Z = X' x y that is close to the set of Nash equilibria Z and we use the Bregman divergence (of some function vi) between and the closest point in Z to measure the closeness, that is, m (2 2).
X argmin maXyey
For notational convenience, we let P M + N and F(z) (Gy, GT x)) for any z (z,y)= Z c R". Without loss of generality, we assume [F(())lee S for all E Z (which can always be ensured by normalizing the entries of G accordingly).
The structure of the EFG is implicitly captured by the treeplexes X' and V, which are generalizations of simplexes that capture the sequential structure of an EFG. The formal definition as follows. (In Appendix A, we provide more details on the connection between treeplexes and the structure of the EFG, as well as concrete examples of treeplexes for better illustrations.)
Treeplexes
Definition 1 (Hoda al. [2010]. treeplex recursively constructed via the following three operations:
1. Every probability simplex is a treeplex.
2. Given treeplexes ; Zk, the Cartesian product Z, X ... X ZK is a treeplex.
3. (Branching) Given treeplexes Z1 C. R and Z2 C. RN, and any E [M].
2, Zz = {u,, u4 v) M+N u 21, 22)
is treeplex.
By definition, a treeplex is a tree-like structure built with simplexes, which intuitively represents the tree-like decision space of single player, and an element in the treeplex represents strategy for the player. Let 71 denote the collection of all the simplexes in treeplex Z, which following Definition 1 can be recursively defined as: z [2) if Z is simplex; H2 U 2 if Z is Cartesian product 2, x ZK: and 2 = 2 2 if 2 2, i Zg. In EFG terminology, H and H the collections of information sets for player æ and player y respectively, which are the decision
3

---

points for the players, at which they select an action within the simplex. For any h E 2 we let Q2 denote the set of indices belonging to h, and for any 2 E Z, we let yn be the slice of z whose indices are in S2 For each index i, we also let h(i)) be the simplex i falls into, that is, i E aa(0)
In Definition 1, the last branching operation naturally introduces the concept of a parent variable for each h E H which can again be recursively defined as: if 2 is a simplex, then it has no parent; if Z is Cartesian product 2 X the treeplex 2₃ that h belongs to (that is, h E H² finally, if 2 = {(u, u; v) u E Σ1, v E 22}. then for all h E _ without a parent, their parent in 2 u, and for all other h, their parents remain the same as in Z1 or Zz. We denote by (h) the index of the parent variable of h. and let it be 0 if h has no parent. For convenience, we let 2u 1 for all 2 E (so that (h) is always well-defined). Also define H, = {h E H : (h) = i} to be the collection of simplexes whose parent index is i.
Zk. then the parent of h H² is the same as the parent of h in
Similarly, for an index i, its parent index is defined as p; = (h(()),, and i is called terminal index if it is not a parent index (that is, * Pj for all j). Finally, for an element z Z and an index i, we define q: Zp. In EFG terminology, qs specifies the probability of selecting action i in the information set h(t) according to strategy z.
4 Optimistic Regret-minimization Algorithms
There are many different algorithms for solving bilinear suddle-point problems over general con- strained sets. We focus specifically on a family of regret-minimization algorithms, called Optimistic Online Mirror Descent (OOMD) [Rakhlin and Sridharan, 2013], which are known to be highly efficient. In contrast to the CFR algorithm and its variants, which minimize local regret notion at each information set (which upper bounds global regret), the algorithms we consider explicitly minimize global regret. As our main results in the next section show, these global regnet-minimization algorithms enjoy last-iterate convergence, while CFR provably diverges.
Specifically,, given a step size 1) O and a convex function vp (called a regularizer), OOMD sequentially performs the following update for t = 1,2,....
2; argmin (n(2e, Gyt-1) + (zr, }
3441 argmin {n(a,, Gyy)) + Du(a,, }: #Ex
=Ex
17yy.-G G xx-11)+ -Tay---TT-))>>>- + D Dvl Det1 = argmin { (n(v. GT x.) + Des (y: 01
y: = argmin y=y
vEy
with (5i, Φ1) (mo; yo) Z being arbitrary. Using shorthands 2, (æt, y:), 2, (a,, Tt). (z) (xx) + (n)) and recalling the notation F(z) (Gy, -GTx) x). the updates above can be compactly written as OOMD with regularizer 1/ over treeplex 2:
z argmin { (1(2, F(z-1)) + Do (2. 2.41 argmin { (1(2, F(z))) + (2, (2) 2E2
#E2
Below, discuss four different regularizers and their resulting algorithms (throughout, we use notations & for regularizers based on Euclidean norm and vi for regularizers based on entropy).
Vanilla Optimistic Gradient Descent Ascent (VOGDA) Detine the vanilla squared Euclidean norm regularizer as (x) = _ E; xf. We call OOMD instantiated with &i = $ van Vanilla Opti- mistic Gradient Descent Ascent (VOGDA). In this case, the Bregman divergence is Davu (z, (z,z') = fl|z- - 2²112 (by definition x is thus 1-strongly convex with respect to the 2-norm), and the up- dates simply become projected gradient descent. For VOGDA there no closed-form for Eq. (2), since projection onto the treeplex 2 is required. Nevertheless, the solution can still be computed in O(p") log P) time (recall that P is the dimension of 2) [Gilpin et al., 2008].
Vanilla Optimistic Multiplicative Weight Update (VOMWU) Define the vanilla entropy regu- larizer as y (z) Σ, 2, In 2,. We call OOMD with 1é va Vanilla Optimistic Multiplicative Weights Update (VOMWU). The Bregman divergence in this case is the generalized KL divergence: D (z, z') Σ; z In(2//])
2, + z/. Although is well-known that van is 1-strongly convex with respect to the 1-norm for the special case when 2 is a simplex, this is not true generally on treeplex. Nevertheless, it can still be shown that T yan is -ssrrongly convex with respect to the 2-norm; see Appendix C.

---

The name "Multiplicative Weights Update" is inherited from case when X' and Y are simplexes, in which case the updates Eq. (2) have simple multiplicative form. We emphasize, however, that in general VOMWU does not admit closed-form update. Instead, to solve Eq. (2), one can equivalently solve simpler dual optimization problem; see [Zimin and Neu, 2013, Proposition 1].
The two regularizers mentioned above ignore the structure of the treeplex. Dilated Regularizers [Hoda al., 2010], on the other hand, take the structure into account and allow one decompose the update into simpler updates at each information set. Specifically, given any convex function 1 defined over the simplex and weight parameter R the dilated version of & defined over Z is:
Va (2)
Σ On =o( w hER
2/
(3)
(h))
This is well-defined since #n/=0(0; is indeed a distribution within the simplex h (with qi for i Qn being its entries). can also be shown that v/dil is always convex in [Hoda et al., 2010). Intuitively, vall applies the base regularizer & to the action distribution in each information set and then scales the value by its parent variable and the weight ot,. By picking different base regularizers, we obtain the following two algorithms.
Dilated Optimistic Gradient Descent Ascent (DOGDA) [Farina al., 2019b] Define the di- lated squared Euclidean norm regularizer 4dti as Eq. (3) with e being the vanilla squared Euclidean norm (=) Σ; o?? Direct calculation shows Tdiil (z) = 2 Σ, 2: We call OOMD with regularizer d the Dilated Optimistic Gradient Descent Ascent algorithm (DOGDA). It is known that there exists
such that æ is 1-strongly convex with respect the 2-norm [Farina et al., 2019b]. Importantly, DOGDA decomposes the update Eq. (2) into simpler gradient descent-style updates at each information set, shown below.
Lemma (Hoda et al. [2010]. Ifz' argminzez (n(2, + Da }) then for every h E H.
the corresponding vector Th
z can be computed by: =(())
dh = argmin {niggh La) + O'h qh @n qu E.E
(4)
where To
2n_ Eocns'
Ln is the slice of L whose entries are in Sr. and L is defined through:
L Si +
Σ
(gho Ln) + Otk l1gh @
2n
GEH.
While the definitions of q/, and L are seemingly recursive, one can verify that they can in fact be computed in "bottom-up" manner, starting with the terminal indices. Although Eq. (4) still does not admit closed- form solution, it only requires projection onto simplex, which can be solved efficiently, see e.g. [Condat, 2016]. Finally, with g computed for all z' can be calculated in a "top-down" manner by definition.
Dilated Optimistic Multiplicative Weight Update (DOMWU) [Kroer et al., 2020] Finally, de- fine the dilated entropy regularizer yddil as Eq. (3) with & being the vanilla entropy (f(2) = Σ In 2,
Direct calculation shows Ti (z) = Σ, ( In q. We call OOMD with regularizer d the Di- lated Optimistic Multiplicative Weights Update algorithm (DOMWU). Similar to DOGDA. there exists an a such that undil is 1-strongly convex with respect to the 2-norm [Kroer et al., 2020]. Moreover, in contrast to all the three algorithms mentioned above, the update of DOMWU has closed-form solution:
Lemma (Hoda et al. [2010]. Suppose z' argginn ()(2,)) + Dun 2)) Similurly to the notation qs define df = 2//2/, and qr = 2/ppp-- Then we have
de q. exp (-nIT//ma)) where L Si Σ ah In
exp exp(((nT JENn
Kroer et al. [2020] also show a better strong convexity result with respect to the 1-norm. We focus on the 2 2-norm here for consistency with other results, but our analysis can be applied the 1-norm well.
5

---

This lemma again implies that we can compute of bottom-up, and then x' can be computed top-down. This is similar to DOGDA, except that all updates have closed-form.
5 Last-iterate Convergence Results
In this section, we present our main last-iterate convergence results for the global regret-minimization algorithms discussed in Section 4. Before doing so, we point out again that the sequence produced by the well-known CFR algorithm may diverge (even if the average converges to a Nash equilibrium).
Indeed, this can happen even for simple normal-form game, formally shown below.
Theorem 3. In the rock-paper-scissorr game, CFR (with some particular initialization) produces diverging sequence.
In fact, we empirically observe that all of CFR, CFR+ [Tammelin, 2014] (with simultaneous updates), and their optimistic versions [Farina et al., 2021a] may diverge in the rock-paper-scissors game. We introduce the algorithms and show the results in Appendix D.
On the contrary, every algorithm from the OOMD family given by Eq. (2) ensures last-iterate convergence, as long as the regularizer is strongly convex and continuously differentiable.
Theorem 4. Consider the update rules in Eq. (2). Suppose that 1-strongly convex with respect to the 2-norm and continuously differentiable on the entire domain, and 1) S sp- Then z₁ converges to Nash equilibrium as 3C.
As mentioned, T and qa are both 1-strongly convex with respect to 2-norm, under some specific choice of a (in the rest of the paper, we fix this choice of α). However, only Eran and qddil are continuously differentiable in the entire domain. Therefore, Theorem 4 provides an asymptotic convergence result only for VOGDA and DOGDA, but not VOMWU and DOMWU. Nevertheless, below, we resort to different analyses to show a concrete last-iterate convergence rate for three of our algorithms, which is much more challenging task.
Tdill and Tddil
First of all, note that [Wei al., 2021, Theorem 5, Theorem 8] already provide general last-iterate convergence rate for VOGDA over polytopes. Since treeplexes are polytopes, we can directly apply their results and obtain the following corollary.
Corollary 5. Define dist (z, z*) = mingrez: ||2 2==22 For 1 S 87
VOGDA guarantees
dist (zz, 2*) S 64dist ( 21)(1
where C₁ > is some constant that depends on the game and 1J.
However, the results for VOMWU in [Wei et al., 2021, Theorem 3] very specific to normal-form game (that is, when X' and y are simplexes) and thus cannot be applied here. Nevertheless, we are able to extend their analysis to get the following result.
Theorem 6. the EFG has unique Nash equilibrium z", then VOMWU with step size nj S 8P guarantees 1 1| 2 < Dyma (z" 2.2))= S C2 game, E,, and 1-
t where C2 > 0 is some constant depending on the
We note that the uniqueness assumption is often required in the analysis of OMWU even for normal-form games [Daskalakis and Panageas, 2019, Wei et al., 2021] (although [Wei et al., 2021, Appendix A.5] provides empirical evidence to show that this may be an artifact of the analysis). Also note that for normal-form games, [Wei et al., 2021, Theorem 3] show a linear convergence rate, whereas here we only show slower sub-linear rate, due to additional complications introduced by treeplexes (see more discussions in the next section). Whether this can be improved is left as a future direction.
On the other hand, thanks to the closed- form updates of DOMWU, we are able to show the following linear convergence rate for this algorithm.
Theorem 7. If the EFG has unique Nash equilibrium z", then DOMWU with step size 1j S SP guarantees 111= 112 < De (z",zz) =1) S Cs(1 + C1) where C3. C2 > 0 are constants that depend on the game, 21, and 17.

---

To the best of our knowledge, this is the first last-iterate convergence result for algorithms with dilated regularizers. Unfortunately. due technical difficulties, we were unable to prove similar results for DOGDA (see Appendix E for more discussion). We leave that as an important future direction.
6 Analysis Overview
In this section, we provide an overview of our analysis. It starts from the following standard one-step regret analysis of OOMD (see, for example, [Wei et al., 2021, Lemma IJ):
Lemma 8. Consider the update rules in Eq. (2). Suppose that &b is I-strongly convex with respect to the 2-norm, [21) F(*2)l S -||=1 =2ll for all z1, 22 E Z and some L > 0. and rj S ş..
Then for any E Z and any 2 1, we have
o (2)) (z: 2) - D (z. ) ( E++1) - (Eet1,, z1)
15 Dz 2,) + 16 Du z z1-1).
16
Note that the Lipschitz condition on F holds in our case with L = since
[[F(21) - F(z2) = / VI - y2)l1 + GT (x) - x2)1 & Pliz
22 2 P||21 z2ll.
1 in all our results. In the following, we first which is also why the step size is chosen to be 1) I 8/ prove Theorem 4. Then, review the convergence analysis of [Wei et al., 2021] for OMWU in normal-form games, and finally demonstrate how to prove Theorem 6 and Theorem 7 by building upon this previous work and addressing the additional complications from EFGs.
6.1 Proof of Theorem 4
For any x" E 2", by optimality of z² we have:
-x= xx F(z)) T (z+ =²) = x, Gy: x; Gy, + x -y" Gy, 2 x Gy - -x" TTy" = O.
Thus, taking z = =z in Lemma and rearranging, we arrive at
2,(2",22+11
(2" 2,) (2 z1) 15 De (Zt, 2,) To (3, 21-1)
Defining θ = (w 2.) + to (2,, zt-1) 1) and G: = Dup (2++1; 21) Du 2.). we rewrite the inequality above as
0+1 S θ
15 S.
(5)
We remark that similar inequalities appear in [Wei et al., 2021, Eq. (3) and Eq. (4)), but here we pick x² E Z" arbitrarily while they have to pick a particular xt E z (such as the projection of 2, onto z*). Summing Eq. (5) over f, telescoping, and applying the strong convexity of vh, we have
15 T-1
15 T-1
15
θ, 2 - N
4 Σ
Σ
-
2
+|
2,112 N Σ
1| 21 112
16
32
64
Similar to the last inequality, we also have θ Σズ || - 11 since 2|1 11
2||z, 12 2 | - 2.. Therefore, conclude that ||| 2, || 21 and |2141 2n all converge to 0 as - xc. On the other hand, since the sequence {=1, #2. } is bounded, by the Bolzano- -eianrssrsssssss theorem, there exists convergent subsequence, which we denote by ( ,i.: J. Let x = lim,- Zi,- By || 2 - z, || + O we also have 2.0 lim E. Now,
using the first-order optimality condition of 2,41, we have for every z' 2,
(V+($4+) - ( nF(2))) 2441 2 0.
Apply this with t = i, for every and let + xo, we obtain
0 < lim (E,,+))))) (,)(2,,) + nf )). T) 21.+1)
(by the first-order optimality)
= lim (F [T - -2,+1)
(by || - 2ell + 0 and the continuity of V
=nF(Zzo) (z' 2z0)
(by 2,0- = lim 0o Zir = -lim 2,
7

---

This implies that Zoo is Nash equilibrium. Finally, choosing x" Zco in the definition of t we have lim i- O because lim,-xx Du (Zx 2,,)
and lim,->x || 2,, -; = 0. Additionally, by Eq. (5) we also have that Do Or = 0 as O is non-increasing. Therefore, we conclude that the entire sequence { 1 22....} converges to Zoc. On the other hand, since OOMD is segre-minimizzation algorithm, it is well known that the average iterate converges to a Nash equilibrium [Freund and Schapire, 1999]. Consequently, combining the two facts above implies that Ze has to converge to a Nash equilibrium, which proves Theorem 4.
We remark that Lemma 8 holds for general closed convex domains as shown in [Wei et al., 2021]. Consequently, with the same argument, Theorem 4 holds more generally as long as X' and y are closed convex sets, While the argument is straightforward. we are not aware of similar results in prior works. Also note that unlike Theorem 6 and Theorem 7, Theorem 4 holds without the uniqueness assumption for VOMWU and DOMWU.
6.2 Review for normal-form games
To better explain our analysis and highlight its novelty, we first review the two-stage analysis of (Wei et al., 2021] for OMWU in normal-form games, special case of our setting when X' and y are simplexes. Note that both VOMWU and DOMWU reduce to OMWU in this case. As with Theorem and Theorem 7, the cormal-forn OMWU results assume a unique Nash equilibrium x² With this uniqueness assumption and [Mertikopoulos et al., 2018, Lemma C.4), Wei et al. [2021] show the following inequality
S De (2111, + (z 2,) 2 C5 - 2
for some problem-dependen constant Cs > O, which, when combined with Eq. (5), implies that if the algorithm's is current iterate is far from z", then the decrease in O; is more substantial, that is, approaching z". To establish a recursion, however, we need
the algorithm makes more progress to connect the 2-norm back to the Bregman divergence (a reverse direction of strong convexity). To do so, Wei et al. [2021] argue that 2,+1. can be lower bounded by another problem-dependent constant for i E supp(z") ) [Wei et al., 2021, Lemma 19], where supp(=*) denotes the support of z². This further allows them to lower bound ||2 KL(z", 1), leading to
2(+1l in terms of D (2" 2(-1) (which is just
G De (2+11, z1) ) + (z, 2,) 2 ( 2),1)
for some Ce > O. On the other hand, ignoring the nonnegative term Des (Zz, 2r), we also have:
1 G. (2 zx) + (z 2,) 2 D2 z1)=
D De (2c+1,
4
where the last step uses the fact that ε and 2, are close [Wei et al., 2021, Lemma 17 and Lemma 18). Now, Eq. (7) and Eq. (8) together imply 66, 2 20 ( 2 +
(2( 21)² 2
min { (os, 1 0 Plugging this back into Eq. (5), we obtain a recursion
0 S θ C+0++1
for some C7 O, which then implies + O(1/t) [Wei al., 2021, Lemma 12]. This can be as the first and slower stage of the convergence behavior of the algorithm.
To further show linear convergence rate, they argue that there exists a constant C3 > 0 such that when the algorithm's iterate is reasonably close to =" in the following sense:
max || &elli, ||
z, 1111 I Cs.
(10)
the following improved version of Eq. (7) holds (note the lack of square on the right-hand side):
G. =
zi) + (ze, 2,) 2 (=", 2.+1)
(11)
for some constant < Co < 1. Therefore, using the 1/1 convergence rate derived the first stage, there exists To such that when > To. Eq. (10) holds and the algorithm enters the second stage. In this stage, combining Eq. (11) and the fact Ge 2 ( z:) gives
4. > Ca GaO which, together 15
2
with Eq, (5) again, implies an improved recursion 0r+1 S O 32 CgO This finally shows
linear convergence rate θ, O((1 + p) for some problem-dependee constant p > 0.
8

---

6.3 Analysis of Theorem 6 and Theorem 7
While we mainly follow the steps of the analysis of [Wei et al., 2021] discussed above to prove Theorem 6 and Theorem 7. we remark that the generalization is highly non-trivial. First of all, we have to prove Eq. (6) for Z being a general treeplex, which does not follow [Mertikopoulos et al., 2018, Lemma C.4] since its proof is very specific to simplexes. Instead, we prove it by writing down the primal-dual linear program of Eq. (1) and applying the strict complementary slackness; see Appendix E for details.
Next, connect the 2-norm back to the Bregman divergence (which is not the simple KL divergence anymore, especially for DOMWU), we prove the following for VOMWU:
(27 - 1,)
2411 S 3P x- - E1+1ll
D=(z", 2641) S
+
Σ spsupp(=*)
(12)
2+11
mimpes)pp(=") 24+1,
(ESHpp(=*)
and the following for DOMWU:
(= 2
(2)- 21+1,)?
1|2 -2+11111 minppsppp(=") 27 2441,
Σ iESUPP(=*)
Σ (ESupp(=*)
S 0+1.1 S
(13)
C
2, 219441.
where C²= 4 (see Appendix E.2). We then show a lower bound on 24+1,1 and 2 for all d E supp(>"). using similar arguments of (Wei et al., 2021] (see Appendix E.3). Combining Eq. (12)
and Eq. (13) with Eq. (6), we have the counterpart of Eq. (7) for both VOMWU and DOMWU.
Showing Eq. (8) also involves extra complication if we follow their analysis, especially for VOMWU
which does not admit a closed-fome update. Instead, we find a simple workaround: by applying Eq. (5) repeatedly, we get (z", 2 = θ 2 ... 2 0++1 2 1 (E Ze), thus, C. 2 Do (Z 2,) Z I6
( x1 for some C1o > 0 depending on (v 21)). Combining this with Eq. (7), and
applying them to Eq. (5), we obtain the recursion Oc+1 S O Cn O for some Cn > 0 similar to Eq. (9), which implies θ O(1/t) for both VOMWU and DOMWU and proves Theorem 6.
Finally, show a linear convergence rate, we need to show the counterpart of Eq. (11), which is again more involved compared to the normal-form game case. Indeed, we are only able to do so for DOMWU by making use of its closed-form update described in Lemma Specifically, observe that in Eq. (13), the term > Fp. 4t+,, is the one that prevents us from bounding ( 2111 by O[I|=* 2 11). Thus, our high-level idea is to argue that Eiespp(e=)) 2xp I decreases significantly as 2, gets close enough to z². To do so, we use a bottom-up induction to prove that, for any information set h E 22 indices i,j E 94 such that i & supp(z") and j E supp(z"), Le,s is significantly larger than Le,, when 2, is close to x", where L, is the counterpart of L in Lemma 2 when computing of q(+1- This makes sure that the term Eigspp(z-)) 3 411,5 1 is dominated by the other term involving i E supp(z") in Eq. (13), which eventually helps us show Eq. (11) and the final linear convergence rate Theorem 7. See Appendix E.5 for details.
7 Experiments
In this section, we experimentally evaluate the algorithms on three standard EFG benchmarks: Kuhn poker [Kuhn, 1950], Pursuit-evasie evasion [Kroer et al., 2018), and Ledue poker [Southey al., 2005]. The results are shown in Figure 1. Besides the optimistic algorithms, we also show two CFR-based algorithms as reference points. "CFR+" refers to CFR with alternating updates, linear averaging ('Tammelin, 2014], and regret matching+ as the regret minimizer. "CFR w/ RM+ is CFR with regret matching+ and linear averaging. We provide the formal descriptions of these two algorithms in Appendix D for completeness. For the optimistic algorithms, we plot the last iterate performance. For the CFR-based algorithms, we plot the performance of the linear average of iterates (recall that the last iterate of CFR- based algorithms is not guaranteed to converge to a Nash equilibrium).
For Kuhn poker and Pursuit-evasior (on the left and in the middle of Figure 1), all of the optimistic algorithms perform much better than CFR+, and their curves are nearly straight, showing their linear last-iterate convergence on these games.
For Ledue poker, although CFR+ performs the best, we can still observe the last-iterate convergence trends of the optimistic algorithms. We remark that although VOGDA and DOMWU have linear
9

---

GFR
logie
(10
CFR+
VOGDA e0.20
DOMAU c33-4.3
DOGRA win
VOMWU ota-4.4
RM
10810 (E)
-10
VOGDA eta-0
DOSDA 04
DOVMU w2au0
l0gio(E))
VOGDDA sto-0.
DOMNU
RM-
DOGGA eto+0.9
-15
OFRL
0 200
600
800
1000
200
800
800
1000
1000
2000
3000
4000
5000
Figure 1: Experiments Kuhn poker (left), Pursuit-evasion (middle), and Leduc poker (right). A description of each game is given in Appendix B. & maxy 3. Gy min, x: Gyy, is the duality gap at time step 4, where (2t; Vr) the approximate Nash equilibrium computed by the algorithm at time (for the optimistic algorithms, (T,, F.) is (æ,, yr) while for the CFR-based algorithms, (T,, Fi,) is the linear average). The legend order reflects the curve order at the right-moss point. Duc to much higher computation overhead than all the other algorithms, we only run VOMWU on Kuhn poker, the game with the smallest size among the three games. For each optimistic algorithm, we fine-tune step size get better convergence results and show its value in the legends. There is hyperparameter for the CFR-based algorithms. All the experiments are run on CPU in a personal computer and the total computation time less than hour. There no random seed and the results are all deterministic.
convergence rate in theory, the experiment on Ledue uses step size which is much larger than Corollary and Theorem suggest, which may void the linear convergence guarantee. This is done because the theoretical step size takes too many iterations before it starts to show improvement. It is worth noting that CFR+ improves significantly when changing simultaneous updates (that is, CFR w/ RM+) alternating updates. Analyzing alternation and combining it with optimistic algorithms is promising direction. We provide a description each game, more discussions, and details of the experiments in Appendix B.
8 Conclusions
In this work, developed the first general last-iterate convergence results for solving EFGs. Our paper opens up many potential future directions. The recent dilatable global entropy regularizer of Farina al. [2021b] can likely be analyzed using techniques similar to analysis of VOMWU and DOMWU, and it would likely lead to linear rate as with DOMWU, due to its frosed-form DOMWU- style update. Other natural questions include whether it is possible to obtain better convergence rates for VOMWU and DOGDA, whether one can remove the uniqueness assumption for VOMWU and DOMWU, and finally whether it is possible to obtain last-iterate convergence rates for CFR- like optimistic algorithms such as those in [Farina et al., 2021a]. On the practical side, optimistic algorithms with last-iterate convergence guarantees may allow more efficient computation and better incorporation with deep learning-basee based game-solving approaches.
Acknowledgments and Disclosure of Funding
CWL and HI. are supported by NSF Award IIS-1943607.
References
James Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In Proceedings of the 2018 ACM Conference Economics and Computation, 2018.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold'en em poker is solved. Science, 145
10

---

George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-376, 1951.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424, 2018.
Noam Brown and Tuomas Sandholm. Solving imperfect-informatinn games via discounted regret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1829-1836, 2019a.
Noam Brown and Tuomas Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456): 885-890, 2019b.
Noam Brown, Sam Ganzfried, and Tuomas Sandholm. Hierarchical abstraction, distributed equilib- rium computation, and post-processing, with application to a champion no-limit texas hold' em agent. In AAA/ Workshop: Computer Poker and Imperfect Information, 2015.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In International conference machine learning, pages 793-802. PMLR, 2019.
Neil Burch. Time and space: Why imperfect information games are hard. PhD thesis, University of Alberta, 2018.
Neil Burch, Michael Johanson, and Michael Bowling. Solving imperfect information games using decomposition. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
Neil Burch, Matej Moraveik, and Martin Schmid. Revisiting CFR+ and alternating updates. Journal of Artificial Intelligence Research, 64:429-443, 2019.
Laurent Condat. Fast projection onto the simplex and the & ball. Mathematical Programming, 158 (1):575-585, 2016.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min max optimization. Innovations in Theoretical Computer Science, 2019.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations, 2018.
Gabriele Farina, Christian Kroer, Noam Brown, and Tuomas Sandholm. Stable-predictive optimistic counterfactual regret minimization. In International conference on machine learning, pages 1863-1862. PMLR, 2019a.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive- form games via dilated distance-genen generating functions. In Advances in Neural Information Process- ing Systems, pages 5222-5232, 2019b.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive Blackwell approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence. AAAI, 2021a.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Better regularization for sequential decision spaces: Fast convergence rates for nash, correlated, and team equilibria. Proceedings of the 2021 ACM Conference on Economics and Computation, 2021b.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999.
Sam Ganzfried and Tuomas Sandholm. Potential-aware imperfect-recall abstraction with earth mover's distance in imperfect-information games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
Sam Ganzfried and Tuomas Sandholm. Endgame solving in large imperfect-informee games. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pages 37-45. Citeseer, 2015.

---

Yuan Gao, Christian Kroer, and Donald Goldfarb. Increasing iterate averaging for solving saddle-poiie problems. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Andrew Gilpin, Javier Peña, and Tuomas Sandholm. First-order algorithm with (In((1/e) conver- gence for e-equilibrium in two-person zero-sum games. In AAAI, 2008.
Ian Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- tion processing systems, 2014.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5): 127-1150, 2000.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. arXiv preprint urXiv:1603.0112/1 2016.
Samid Hoda, Andrew Gilpin, Javier Pena, and Tuomas Sandholm. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 35(2): 494-512, 2010.
Christian Kroer and Tuomas Sandholm. Extensive-form game abstraction with bounds. In Proceed- ings of the fifteenth ACM conference on Economics and computation, pages 621-638, 2014.
Christian Kroer, Gabriele Farina, and Tuomas Sandholm. Smoothing method for approximate extensive-form perfect equilibrium. Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 295-301, 2017.
Christian Kroer, Gabriele Farina, and Tuomas Sandholm. Robust stackelberg equilibria in extensive- form games and extension to limited lookahead. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Christian Kroer, Kevin Waugh, Fatma Kıline- Karzan, and Tuomas Sandholm. Faster algorithms for extensive-form game solving via improved smoothing functions. Mathematical Programming, 179 (1):385-411 417, 2020.
HW Kuhn. Simplified two-person poker. Contributions to the Theory of Games, pages 97-103, 1950.
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael H Bowling. Monte carlo sampling for regret minimization in extensive games. In NIPS, pages 1078-1086, 2009.
Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang. Last iterate convergence in no-regret learning: constrained min min-max optimization for convex-concat landscapes. The 24nd International Conference Artificial Intelligence and Statisties, 2021.
Brendan McMahan, Geoffrey Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference Machine Learning (ICML-03), pages 536-543, 2003.
Panayotis Mertikopoulos. Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-inth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Panayotis Mertikopoulos, Houssam Zenati, Bruno Lecouat, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations, 2019.
Matej Moravcik. Martin Schmid, Karel Ha, Milan Hladik, and Stephen Gaukrodger. Refining subgames in large imperfect information games. In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limii poker. Science, 356(6337):508-511 2017.
12

---

Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, pages 3066-3074, 2013.
Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: opponent modelling in poker. Proceedings of the Twenty-First Conference Uncertainty in Artificial Intelligence, pages 550-558, 2005.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert Schapire. Fast convergence of regularized learning in games, In Advances in Neural Information Processing Systems, 2015.
Oskari Tammelin. Solving large imperfect information games using CFR+. arXiv preprint
arXiv: 1eXivv/407.555 140710042 2014.
Paul Tseng. On linear convergence of iterative methods the variational inequality problem. In Journal of Computational and Applied Mathematics, 1995.
Robert Vanderbei et al. Linear programming, volume 3. Springer, 2015.
Bernhard Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):200226, 1996.
Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In International Conference on Learning Representations, 2021.
Alexander Zimin and Gergely Neu. Online learning in episodic Markovian decision processes by relative entropy policy search. In Neural Information Processing Systems 26, 2013.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-9998899 936,, 2003.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances neural information processing systems, 20: 1729-1755 2007.
13


Reviews:
[{"review_id": "zB5eJzFchvK", "reviewer": "Reviewer_rJS7", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Post rebuttal**  \nThe 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.\n\n=======================================================================================================\n\nMy 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).\n\nWithout 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.)\n\nI 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the work are discussed in the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "p4jmD-QsTJ", "reviewer": "Reviewer_YFCu", "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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.    \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is mainly theoretical so I think the authors have adequately addressed the societal impact. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "WdLUPK_QecV", "reviewer": "Reviewer_MuPP", "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.\n\n--- after discussion ---\nThere was one issue raised, but there was also a proposed connection so my opinion remains positive and largely unchanged.\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": "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.\n\nI 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.\n\nThe 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.\n\nI 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?\n\nCan 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "DFz2eBAs-kv", "reviewer": "Reviewer_cpq1", "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).", "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": "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.\n\nOne 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.\n\nAnother 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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

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)