Last-iterate Convergence in Extensive-Form Games
Year: 2021

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.

heading: 1 Introduction
text: Extensive-form games (EFGs) are an important class of games in game theory and artificial intelligence which can model imperfect information and sequential interactions. EFGs are typically solved by finding or approximating a Nash equilibrium. Regret-minimization algorithms are among the most popular approaches to approximate Nash equilibria. The motivation comes from a classical result which says that in 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-Colell, 2000, Zinkevich et al., 2007]. Counterfactual Regret Minimization (CFR) [Zinkevich et al., 2007] and it variants such as CFR+ [Tammelin, 2014] are based on this motivation.
However, due to their ergodic convergence guarantee, theoretical convergence rates of regretminimization algorithms are typically limited to O(1/ √ T ) or O(1/T ) for T rounds, and this is also the case in practice [Brown and Sandholm, 2019a, Burch et al., 2019]. In contrast, it is known that linear convergence rates are achievable for 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 is to 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 not
35th Conference on Neural Information Processing Systems (NeurIPS 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 FTRL converge fast, a theoretical understanding of this phenomenon is 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 regretminimization 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 a 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 1-strongly-convex 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.

heading: 2 Related Work
text: 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 et al., 2010, Kroer et al., 2020], and CFR methods [Zinkevich et 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, Moravčí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 a 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 O(1/ √ T ) when both players apply regret-minimization algorithms whose regret grows on the order of O( √ T ) [Freund and Schapire, 1999, Hart and Mas-Colell, 2000, Zinkevich et al., 2007]. Moreover, when the players use optimistic regret-minimization 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], CFR-like local optimistic algorithms [Farina et al., 2019a], and optimistic CFR algorithms [Burch, 2018, Brown and Sandholm, 2019a, Farina et al., 2021a]. However, the theoretical results in all these existing papers consider the average strategy, while we are the first to consider last-iterate convergence in EFGs.
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 a lot of attention due to 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, 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 apply to the case of EFGs: Wei et al. [2021] show a 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 practically-important dilated regularizers.

heading: 3 Problem Setup
text: We start with some basic notation. For a vector z, we use zi to denote its i-th coordinate and ‖z‖p to denote its p-norm (with ‖z‖ being a shorthand for ‖z‖2). For a convex function ψ, the associated Bregman divergence is define as Dψ(u,v) = ψ(u) − ψ(v) − 〈∇ψ(v),u − v〉, and ψ is called κ-strongly convex with respect to the p-norm if Dψ(u,v) ≥ κ2 ‖u − v‖ 2 p holds for all u and v in the domain. The Kullback-Leibler divergence, which is the Bregman divergence with respect to the entropy function, is denoted by KL(·, ·). Finally, we use ∆P to denote the (P − 1)-dimensional simplex and [N ] to denote the set {1, 2 . . . , N} for some positive integer N .
Extensive-form Games as Bilinear Saddle-point Optimization We consider the problem of finding a Nash equilibrium of a two-player zero-sum extensive-form game (EFG) with perfect recall. Instead of formally introducing the definition of an EFG (see Appendix A for an example), for the purpose of this work, it suffices to consider an equivalent formulation, which casts the problem as a simple bilinear saddle-point optimization [von Stengel, 1996]:
min x∈X max y∈Y x>Gy = max y∈Y min x∈X x>Gy, (1)
whereG ∈ [−1,+1]M×N is a known matrix, and X ⊂ RM and Y ⊂ RN are two polytopes called treeplexes (to be defined soon). The set of Nash equilibria is then defined as Z∗ = X ∗ × Y∗, where X ∗ = argminx∈X maxy∈Y x>Gy and Y∗ = argmaxy∈Y minx∈X x>Gy. Our goal is to find a point z ∈ Z = X × Y that is close to the set of Nash equilibria Z∗, and we use the Bregman divergence (of some function ψ) between z and the closest point in Z∗ to measure the closeness, that is, minz∗∈Z∗ Dψ(z∗, z).
For notational convenience, we let P = M +N and F (z) = (Gy,−G>x) for any z = (x,y) ∈ Z ⊂ RP . Without loss of generality, we assume ‖F (z)‖∞ ≤ 1 for all z ∈ Z (which can always be ensured by normalizing the entries ofG accordingly).
Treeplexes The structure of the EFG is implicitly captured by the treeplexes X and Y , which are generalizations of simplexes that capture the sequential structure of an EFG. The formal definition is 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.)
Definition 1 (Hoda et al. [2010]). A treeplex is recursively constructed via the following three operations:
1. Every probability simplex is a treeplex.
2. Given treeplexes Z1, . . . ,ZK , the Cartesian product Z1 × · · · × ZK is a treeplex.
3. (Branching) Given treeplexes Z1 ⊂ RM and Z2 ⊂ RN , and any i ∈ [M ], Z1 i Z2 = { (u, ui · v) ∈ RM+N : u ∈ Z1, v ∈ Z2 }
is a treeplex.
By definition, a treeplex is a tree-like structure built with simplexes, which intuitively represents the tree-like decision space of a single player, and an element in the treeplex represents a strategy for the player. LetHZ denote the collection of all the simplexes in treeplex Z , which following Definition 1 can be recursively defined as: HZ = {Z} if Z is a simplex; HZ = ⋃K k=1HZi if Z is a Cartesian product Z1×· · ·×ZK ; andHZ = HZ1 ∪HZ2 if Z = Z1 i Z2. In EFG terminology,HX andHY are the collections of information sets for player x and player y respectively, which are the decision
points for the players, at which they select an action within the simplex. For any h ∈ HZ , we let Ωh denote the set of indices belonging to h, and for any z ∈ Z , we let zh be the slice of z whose indices are in Ωh. For each index i, we also let h(i) be the simplex i falls into, that is, i ∈ Ωh(i). In Definition 1, the last branching operation naturally introduces the concept of a parent variable for each h ∈ HZ , which can again be recursively defined as: if Z is a simplex, then it has no parent; if Z is a Cartesian product Z1 × · · · × ZK , then the parent of h ∈ HZ is the same as the parent of h in the treeplex Zk that h belongs to (that is, h ∈ HZk ); finally, if Z = {(u, ui · v) : u ∈ Z1, v ∈ Z2}, then for all h ∈ HZ2 without a parent, their parent in Z is ui, and for all other h, their parents remain the same as in Z1 or Z2. 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 z0 = 1 for all z ∈ Z (so that zσ(h) is always well-defined). Also defineHi = {h ∈ HZ : σ(h) = i} to be the collection of simplexes whose parent index is i. Similarly, for an index i, its parent index is defined as pi = σ(h(i)), and i is called a terminal index if it is not a parent index (that is, i 6= pj for all j). Finally, for an element z ∈ Z and an index i, we define qi = zi/zpi . In EFG terminology, qi specifies the probability of selecting action i in the information set h(i) according to strategy z.

heading: 4 Optimistic Regret-minimization Algorithms
text: There are many different algorithms for solving bilinear saddle-point problems over general constrained 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 a 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 regret-minimization algorithms enjoy last-iterate convergence, while CFR provably diverges.
Specifically, given a step size η > 0 and a convex function ψ (called a regularizer), OOMD sequentially performs the following update for t = 1, 2, . . . ,
xt = argmin x∈X
{ η〈x,Gyt−1〉+Dψ(x, x̂t) } , x̂t+1 = argmin
x∈X
{ η〈x,Gyt〉+Dψ(x, x̂t) } ,
yt = argmin y∈Y
{ η〈y,−G>xt−1〉+Dψ(y, ŷt) } , ŷt+1 = argmin
y∈Y
{ η〈y,−G>xt〉+Dψ(y, ŷt) } ,
with (x̂1, ŷ1) = (x0,y0) ∈ Z being arbitrary. Using shorthands zt = (xt,yt), ẑt = (x̂t, ŷt), ψ(z) = ψ(x) + ψ(y) and recalling the notation F (z) = (Gy,−G>x), the updates above can be compactly written as OOMD with regularizer ψ over treeplex Z:
zt = argmin z∈Z
{ η〈z, F (zt−1)〉+Dψ(z, ẑt) } , ẑt+1 = argmin
z∈Z
{ η〈z, F (zt)〉+Dψ(z, ẑt) } . (2)
Below, we discuss four different regularizers and their resulting algorithms (throughout, we use notations Φ for regularizers based on Euclidean norm and Ψ for regularizers based on entropy).
Vanilla Optimistic Gradient Descent Ascent (VOGDA) Define the vanilla squared Euclidean norm regularizer as Φvan(z) = 12 ∑ i z 2 i . We call OOMD instantiated with ψ = Φ
van Vanilla Optimistic Gradient Descent Ascent (VOGDA). In this case, the Bregman divergence is DΦvan(z, z′) = 1 2‖z − z
′‖2 (by definition Φvan is thus 1-strongly convex with respect to the 2-norm), and the updates simply become projected gradient descent. For VOGDA there is no closed-form for Eq. (2), since projection onto the treeplex Z is required. Nevertheless, the solution can still be computed in O(P 2 logP ) time (recall that P is the dimension of Z) [Gilpin et al., 2008].
Vanilla Optimistic Multiplicative Weight Update (VOMWU) Define the vanilla entropy regularizer as Ψvan(z) = ∑ i zi ln zi. We call OOMD with ψ = Ψ
van Vanilla Optimistic Multiplicative Weights Update (VOMWU). The Bregman divergence in this case is the generalized KL divergence: DΨvan(z, z ′) = ∑ i zi ln(zi/z ′ i)− zi + z′i. Although it is well-known that Ψvan is 1-strongly convex with respect to the 1-norm for the special case when Z is a simplex, this is not true generally on a treeplex. Nevertheless, it can still be shown that Ψvan is 1-strongly 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 in Eq. (2) have a simple multiplicative form. We emphasize, however, that in general VOMWU does not admit a closed-form update. Instead, to solve Eq. (2), one can equivalently solve a 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 et al., 2010], on the other hand, take the structure into account and allow one to decompose the update into simpler updates at each information set. Specifically, given any convex function ψ defined over the simplex and a weight parameter α ∈ RHZ+ , the dilated version of ψ defined over Z is:
ψdilα (z) = ∑ h∈HZ αh · zσ(h) · ψ ( zh zσ(h) ) . (3)
This is well-defined since zh/zσ(h) is indeed a distribution within the simplex h (with qi for i ∈ Ωh being its entries). It can also be shown that ψdilα is always convex in z [Hoda et al., 2010]. Intuitively, ψdilα applies the base regularizer ψ to the action distribution in each information set and then scales the value by its parent variable and the weight αh. By picking different base regularizers, we obtain the following two algorithms.
Dilated Optimistic Gradient Descent Ascent (DOGDA) [Farina et al., 2019b] Define the dilated squared Euclidean norm regularizer Φdilα as Eq. (3) with ψ being the vanilla squared Euclidean norm ψ(z) = 12 ∑ i z 2 i . Direct calculation shows Φ dil α (z) = 1 2 ∑ i αh(i)ziqi. We call OOMD with regularizer Φdilα the Dilated Optimistic Gradient Descent Ascent algorithm (DOGDA). It is known that there exists an α such that Φdilα is 1-strongly convex with respect to the 2-norm [Farina et al., 2019b]. Importantly, DOGDA decomposes the update Eq. (2) into simpler gradient descent-style updates at each information set, as shown below. Lemma 1 (Hoda et al. [2010]). If z′ = argminz∈Z { η〈z,f〉+DΦdilα(z, ẑ) } , then for every h ∈ HZ , the corresponding vector q′h = z′h z′ σ(h) can be computed by:
q′h = argmin qh∈∆|Ωh|
{ η〈qh,Lh〉+
αh 2 ‖qh − q̂h‖2
} , (4)
where q̂h = ẑhẑσ(h) , Lh is the slice of L whose entries are in Ωh, and L is defined through:
Li = fi + ∑ h∈Hi ( 〈q′h,Lh〉+ αh 2η ‖q′h − q̂h‖2 ) .
While the definitions of q′h and L are seemingly recursive, one can verify that they can in fact be computed in a “bottom-up” manner, starting with the terminal indices. Although Eq. (4) still does not admit closed-form solution, it only requires projection onto a simplex, which can be solved efficiently, see e.g. [Condat, 2016]. Finally, with q′h computed for all h, z
′ can be calculated in a “top-down” manner by definition.
Dilated Optimistic Multiplicative Weight Update (DOMWU) [Kroer et al., 2020] Finally, define the dilated entropy regularizer Ψdilα as Eq. (3) with ψ being the vanilla entropy ψ(z) = ∑ i zi ln zi.
Direct calculation shows Ψdilα (z) = ∑ i αh(i)zi ln qi. We call OOMD with regularizer Ψ dil α the Dilated Optimistic Multiplicative Weights Update algorithm (DOMWU). Similar to DOGDA, there exists an α such that Ψdilα is 1-strongly convex with respect to the 2-norm [Kroer et al., 2020]. 1 Moreover, in contrast to all the three algorithms mentioned above, the update of DOMWU has a closed-form solution: Lemma 2 (Hoda et al. [2010]). Suppose z′ = argminz∈Z { η〈z,f〉+DΨdilα(z, ẑ) } . Similarly to the notation qi, define q′i = z ′ i/z ′ pi and q̂i = ẑi/ẑpi . Then we have
q′i ∝ q̂i exp ( −ηLi/αh(i) ) , where Li = fi − ∑ h∈Hi αh η ln ∑ j∈Ωh q̂j exp (−ηLj/αh)  . 1Kroer et al. [2020] also show a better strong convexity result with respect to the 1-norm. We focus on the
2-norm here for consistency with our other results, but our analysis can be applied to the 1-norm case as well.
This lemma again implies that we can compute q′i bottom-up, and then z ′ can be computed top-down. This is similar to DOGDA, except that all updates have a closed-form.

heading: 5 Last-iterate Convergence Results
text: 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 a simple normal-form game, as formally shown below.
Theorem 3. In the rock-paper-scissors game, CFR (with some particular initialization) produces a 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 ψ is 1-strongly convex with respect to the 2-norm and continuously differentiable on the entire domain, and η ≤ 18P . Then zt converges to a Nash equilibrium as t→∞.
As mentioned, Φvan and Ψvan are both 1-strongly convex with respect to 2-norm, so are Φdilα and Ψ dil α under some specific choice of α (in the rest of the paper, we fix this choice of α). However, only Φvan and Φdilα 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 a much more challenging task.
First of all, note that [Wei et al., 2021, Theorem 5, Theorem 8] already provide a 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 dist2(z,Z∗) = minz∗∈Z∗ ‖z − z∗‖2. For η ≤ 18P , VOGDA guarantees
dist2(zt,Z∗) ≤ 64dist2(ẑ1,Z∗)(1 + C1)−t,
where C1 > 0 is some constant that depends on the game and η.
However, the results for VOMWU in [Wei et al., 2021, Theorem 3] is 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. If the EFG has a unique Nash equilibrium z∗, then VOMWU with step size η ≤ 18P guarantees 12‖ẑt − z
∗‖2 ≤ DΨvan(z∗, ẑt) ≤ C2t , where C2 > 0 is some constant depending on the game, ẑ1, and η.
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 a 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 a unique Nash equilibrium z∗, then DOMWU with step size η ≤ 18P guarantees 12‖zt − z ∗‖2 ≤ DΨdilα(z ∗, zt) ≤ C3(1 + C4)−t, where C3, C4 > 0 are constants that depend on the game, ẑ1, and η.
To the best of our knowledge, this is the first last-iterate convergence result for algorithms with dilated regularizers. Unfortunately, due to 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.

heading: 6 Analysis Overview
text: 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 1]): Lemma 8. Consider the update rules in Eq. (2). Suppose that ψ is 1-strongly convex with respect to the 2-norm, ‖F (z1)− F (z2)‖ ≤ L‖z1 − z2‖ for all z1, z2 ∈ Z and some L > 0, and η ≤ 18L . Then for any z ∈ Z and any t ≥ 1, we have
ηF (zt) >(zt − z) ≤ Dψ(z, ẑt)−Dψ(z, ẑt+1)−Dψ(ẑt+1, zt)− 1516Dψ(zt, ẑt) + 1 16Dψ(ẑt, zt−1).
Note that the Lipschitz condition on F holds in our case with L = P since ‖F (z1)− F (z2)‖ = √ ‖G(y1 − y2)‖2 + ‖G>(x1 − x2)‖2 ≤ √ P‖z1 − z2‖21 ≤ P‖z1 − z2‖,
which is also why the step size is chosen to be η ≤ 18P in all our results. In the following, we first prove Theorem 4. Then, we 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.

heading: 6.1 Proof of Theorem 4
text: For any z∗ ∈ Z∗, by optimality of z∗ we have:
F (zt) >(zt − z∗) = x>t Gyt − x>t Gyt + x>t Gy∗ − x∗ >Gyt ≥ x∗>Gy∗ − x∗>Gy∗ = 0.
Thus, taking z = z∗ in Lemma 8 and rearranging, we arrive at
Dψ(z ∗, ẑt+1) ≤ Dψ(z∗, ẑt)−Dψ(ẑt+1, zt)− 1516Dψ(zt, ẑt) + 1 16Dψ(ẑt, zt−1).
Defining Θt = Dψ(z∗, ẑt) + 116Dψ(ẑt, zt−1) and ζt = Dψ(ẑt+1, zt) +Dψ(zt, ẑt), we rewrite the inequality above as
Θt+1 ≤ Θt − 1516ζt. (5)
We remark that similar inequalities appear in [Wei et al., 2021, Eq. (3) and Eq. (4)], but here we pick z∗ ∈ Z∗ arbitrarily while they have to pick a particular z∗ ∈ Z∗ (such as the projection of ẑt onto Z∗). Summing Eq. (5) over t, telescoping, and applying the strong convexity of ψ, we have
Θ1 ≥ Θ1 −ΘT ≥ 15
16 T−1∑ t=1 ζt ≥ 15 32 T−1∑ t=1 ‖ẑt+1 − zt‖2 + ‖zt − ẑt‖2 ≥ 15 64 T−1∑ t=2 ‖zt − zt−1‖2.
Similar to the last inequality, we also have Θ1 ≥ 1564 ∑T−1 t=1 ‖ẑt+1 − ẑt‖2 since 2‖ẑt+1 − zt‖2 + 2‖zt− ẑt‖2 ≥ ‖ẑt+1− ẑt‖2. Therefore, we conclude that ‖zt− ẑt‖, ‖zt+1− zt‖, and ‖ẑt+1− ẑt‖ all converge to 0 as t → ∞. On the other hand, since the sequence {z1, z2, . . . , } is bounded, by the Bolzano-Weierstrass theorem, there exists a convergent subsequence, which we denote by {zi1 , zi2 , . . . , }. Let z∞ = limτ→∞ ziτ . By ‖ẑt − zt‖ → 0 we also have z∞ = limτ→∞ ẑiτ . Now, using the first-order optimality condition of ẑt+1, we have for every z′ ∈ Z ,
(∇ψ(ẑt+1)−∇ψ(ẑt) + ηF (zt))>(z′ − ẑt+1) ≥ 0.
Apply this with t = iτ for every τ and let τ →∞, we obtain
0 ≤ lim τ→∞
(∇ψ(ẑiτ+1)−∇ψ(ẑiτ ) + ηF (ziτ ))>(z′ − ẑiτ+1) (by the first-order optimality)
= lim τ→∞
ηF (ziτ ) >(z′ − ẑiτ+1) (by ‖ẑt+1 − ẑt‖ → 0 and the continuity of ∇ψ)
= ηF (z∞) >(z′ − z∞) (by z∞ = limτ→∞ ziτ = limτ→∞ ẑiτ )
This implies that z∞ is a Nash equilibrium. Finally, choosing z∗ = z∞ in the definition of Θt, we have limτ→∞Θiτ = 0 because limτ→∞Dψ(z∞, ẑiτ ) = 0 and limτ→∞ ‖ẑiτ − ziτ−1‖ = 0. Additionally, by Eq. (5) we also have that limt→∞Θt = 0 as Θt is non-increasing. Therefore, we conclude that the entire sequence {z1, z2, . . .} converges to z∞. On the other hand, since OOMD is a regret-minimization 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 zt 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.

heading: 6.2 Review for normal-form games
text: 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, a 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 6 and Theorem 7, the normal-form OMWU results assume a unique Nash equilibrium z∗. With this uniqueness assumption and [Mertikopoulos et al., 2018, Lemma C.4], Wei et al. [2021] show the following inequality
ζt = Dψ(ẑt+1, zt) +Dψ(zt, ẑt) ≥ C5‖z∗ − ẑt+1‖2 (6)
for some problem-dependent constant C5 > 0, which, when combined with Eq. (5), implies that if the algorithm’s current iterate is far from z∗, then the decrease in Θt is more substantial, that is, the algorithm makes more progress on approaching z∗. To establish a recursion, however, we need 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 ẑt+1,i can be lower bounded by another problem-dependent constant for i ∈ supp(z∗) [Wei et al., 2021, Lemma 19], where supp(z∗) denotes the support of z∗. This further allows them to lower bound ‖z∗ − ẑt+1‖ in terms of Dψ(z∗, ẑt+1) (which is just KL(z∗, ẑt+1)), leading to
ζt = Dψ(ẑt+1, zt) +Dψ(zt, ẑt) ≥ C6Dψ(z∗, ẑt+1)2, (7)
for some C6 > 0. On the other hand, ignoring the nonnegative term Dψ(zt, ẑt), we also have:
ζt = Dψ(ẑt+1, zt) +Dψ(zt, ẑt) ≥ Dψ(ẑt+1, zt) ≥ 1
4 Dψ(ẑt+1, zt)
2, (8)
where the last step uses the fact that ẑt+1 and zt are close [Wei et al., 2021, Lemma 17 and Lemma 18]. Now, Eq. (7) and Eq. (8) together imply 6ζt ≥ 2C6Dψ(z∗, ẑt+1)2 + Dψ(ẑt+1, zt)2 ≥ min { C6, 1 2 } Θ2t+1. Plugging this back into Eq. (5), we obtain a recursion
Θt+1 ≤ Θt − C7Θ2t+1 (9)
for some C7 > 0, which then implies Θt = O(1/t) [Wei et al., 2021, Lemma 12]. This can be seen as the first and slower stage of the convergence behavior of the algorithm.
To further show a linear convergence rate, they argue that there exists a constant C8 > 0 such that when the algorithm’s iterate is reasonably close to z∗ in the following sense:
max{‖z∗ − ẑt‖1, ‖z∗ − zt‖1} ≤ C8, (10)
the following improved version of Eq. (7) holds (note the lack of square on the right-hand side):
ζt = Dψ(ẑt+1, zt) +Dψ(zt, ẑt) ≥ C9Dψ(z∗, ẑt+1) (11)
for some constant 0 < C9 < 1. Therefore, using the 1/t convergence rate derived in the first stage, there exists a T0 such that when t ≥ T0, Eq. (10) holds and the algorithm enters the second stage. In this stage, combining Eq. (11) and the fact ζt ≥ Dψ(ẑt+1, zt) gives ζt ≥ C92 Θt+1, which, together with Eq. (5) again, implies an improved recursion Θt+1 ≤ Θt − 1532C9Θt+1. This finally shows a linear convergence rate Θt = O((1 + ρ)−t) for some problem-dependent constant ρ > 0.

heading: 6.3 Analysis of Theorem 6 and Theorem 7
text: 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.1 for details.
Next, to 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:
Dψ(z ∗, ẑt+1) ≤ ∑ i∈supp(z∗) (z∗i − ẑt+1,i)2 ẑt+1,i + ∑ i/∈supp(z∗) ẑt+1,i ≤ 3P‖z∗ − ẑt+1‖ mini∈supp(z∗) ẑt+1,i , (12)
and the following for DOMWU:
Dψ(z ∗, ẑt+1) C ′
≤ ∑
i∈supp(z∗)
(z∗i − ẑt+1,i) 2
z∗i q̂t+1,i + ∑ i/∈supp(z∗) z∗pi q̂t+1,i ≤ ‖z∗ − ẑt+1‖1 mini∈supp(z∗) z∗i ẑt+1,i , (13)
where C ′ = 4P‖α‖∞ (see Appendix E.2). We then show a lower bound on zt+1,i and ẑt+1,i for all i ∈ supp(z∗), 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-form update. Instead, we find a simple workaround: by applying Eq. (5) repeatedly, we get Dψ(z∗, ẑ1) = Θ1 ≥ · · · ≥ Θt+1 ≥ 116Dψ(ẑt+1, zt), thus, ζt ≥ Dψ(ẑt+1, zt) ≥ C10Dψ(ẑt+1, zt)
2 for some C10 > 0 depending on Dψ(z∗, ẑ1). Combining this with Eq. (7), and applying them to Eq. (5), we obtain the recursion Θt+1 ≤ Θt − C11Θ2t+1 for some C11 > 0 similar to Eq. (9), which implies Θt = O(1/t) for both VOMWU and DOMWU and proves Theorem 6.
Finally, to 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 2. Specifically, observe that in Eq. (13), the term ∑ i/∈supp(z∗) z ∗ pi q̂t+1,i is the one that prevents us from bounding Dψ(z ∗, ẑt+1)
by O(‖z∗ − ẑt+1‖2). Thus, our high-level idea is to argue that ∑ i/∈supp(z∗) z ∗ pi q̂t+1,i decreases significantly as ẑt gets close enough to z∗. To do so, we use a bottom-up induction to prove that, for any information set h ∈ HZ , indices i, j ∈ Ωh such that i /∈ supp(z∗) and j ∈ supp(z∗), L̂t,i is significantly larger than L̂t,j when ẑt is close to z∗, where L̂t is the counterpart of L in Lemma 2 when computing of q̂t+1. This makes sure that the term ∑ i/∈supp(z∗) z ∗ pi q̂t+1,i is dominated by the other term involving i ∈ supp(z∗) in Eq. (13), which eventually helps us show Eq. (11) and the final linear convergence rate in Theorem 7. See Appendix E.5 for details.

heading: 7 Experiments
text: In this section, we experimentally evaluate the algorithms on three standard EFG benchmarks: Kuhn poker [Kuhn, 1950], Pursuit-evasion [Kroer et al., 2018], and Leduc poker [Southey et 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-evasion (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 Leduc 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
convergence rate in theory, the experiment on Leduc uses a step size η which is much larger than Corollary 5 and Theorem 7 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+) to alternating updates. Analyzing alternation and combining it with optimistic algorithms is a promising direction. We provide a description of each game, more discussions, and details of the experiments in Appendix B.

heading: 8 Conclusions
text: In this work, we 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 et al. [2021b] can likely be analyzed using techniques similar to our analysis of VOMWU and DOMWU, and it would likely lead to a linear rate as with DOMWU, due to its closed-form DOMWUstyle 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 CFRlike 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-based game-solving approaches.
Acknowledgments and Disclosure of Funding
CWL and HL are supported by NSF Award IIS-1943607.

Review summaries:
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. ------

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.  

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