The Power of Regularization in Solving Extensive-Form Games
Authors: Mingyang Liu
Asuman E. Ozdaglar
Tiancheng Yu
Kaiqing Zhang
Venue: ICLR 2023 poster (2023)
Keywords: Game Theory
Optimization

Abstract: In this paper, we investigate the power of {\it regularization},  a common technique in reinforcement learning and optimization, in solving extensive-form games (EFGs). We propose a series of new algorithms based on regularizing the payoff functions of the game, and establish a set of convergence results that strictly improve over the existing ones, with either weaker assumptions or stronger convergence guarantees. In particular, we first show that dilated optimistic mirror descent (DOMD),  an efficient variant of OMD for solving EFGs, with adaptive regularization can achieve a fast $\tilde O(1/T)$  last-iterate convergence in terms of duality gap and distance to the set of Nash equilibrium (NE) without uniqueness assumption of the NE. Second, we show that regularized counterfactual regret minimization  (\texttt{Reg-CFR}), with a variant of optimistic mirror descent algorithm as regret-minimizer, can achieve $O(1/T^{1/4})$ best-iterate,  and $O(1/T^{3/4})$ average-iterate convergence rate for finding NE in EFGs. Finally, we show that \texttt{Reg-CFR} can achieve asymptotic last-iterate convergence, and optimal $O(1/T)$ average-iterate convergence rate, for finding the NE of perturbed EFGs, which is useful for finding approximate  extensive-form perfect equilibria (EFPE). To  the best of our knowledge, they constitute the first last-iterate convergence results  for CFR-type  algorithms, while matching the state-of-the-art average-iterate convergence rate in finding NE for non-perturbed EFGs. We also provide numerical results to corroborate the advantages of our algorithms.

Published as a conference paper at ICLR 2023
THE POWER OF REGULARIZATION IN SOLVING EXTENSIVE-FORM GAMES
Mingyang Liu'! Asuman Ozdaglar 2, Tiancheng Yu 2, Kaiqing Zhang 'Inttitute for Interdisciplinary Information Sciences, Tsinghua University 2LIDS, EECS, Massachusetts Institute of Technology
University of Maryland, College Park
"liumy19 19 9mmails ts tsinghua. edu. cn
2 {{a (asuman, (uuc)@mi edd
kkat i q ng@ undd edu
ABSTRACT
In this paper, investigate the power of regularization, common technique in reinforcement learning and optimization, in solving extensive-form games (EFGs). We propose series of new algorithms based regularizing the pay- off functions of the game, and establish set of convergence results that strictly improve over the existing ones, with either weaker assumptions or stronger con- vergence guarantees. In particular, we first show that dilated optimistic mirror descent (DOMD), an efficient variant of OMD for solving EFGs, with adaptive regularization can achieve a fast ((1/T) last-iterate convergence in terms of du- ality gap and distance to the set of Nash equilibrium (NE) without uniqueness assumption of the NE. Second, we show that regularized counterfactual regret minimization (Reg-CFR), with variant of optimistic mirror descent algorithm regret-minimizen, can achieve O(1/T2/4) best-iterate, and ((1/T5/4) average- iterate convergence rate for finding NE in EFGs. Finally, we show that Reg-CFR achieve asymptotic last-iterate convergence, and optimal O(1/T) average- iterate convergence rate, for finding the NE of perturbed EFGs, which is useful for finding approximate extensive-form perfect equilibria (EFPE). To the best of our knowledge, they constitute the first last-iterate convergence results for CFR- type algorithms, while matching the ofate-of-the-art average-iterate convergence rate in finding NE for non-perturbed EFGs. We also provide numerical results to corroborate the advantages of our algorithms.
INTRODUCTION
Extensive-form games (EFGs) are widely used in modeling sequential decision-making of multiple agents with imperfect information. Many popular real-world multi-agent learning problems can be modeled as EFGs, including Poker (Brown and Sandholm, 20188] 2019b), Scotland Yard (Schmid) al. 2021). Bridge (Tian et al. (2020), cloud computing (Kakkad al. 2019 and auctions (Shubik) 1971. etc. Despite the recent success of many of these applications, efficiently solving large-scale EFGs still challenging.
Solving EFGs typically refers to as finding a Nash equilibrium (NE) of the game, especially in the two-player zero-sum setting. In the past decades, the most popular methods in solving EFGs arguably eegret-minimization based methods, such counterfactual regret minimization (CFR) Ziikevvich et al. 2007) and its variants (Tammelin al. 2015 Brown and Sandholm, 2019a). By controlling the regret of each player, the average of strategies constitute an approximated NE in two-player zero-sum games, which is called average-iterate convergence (Zinkevich et al. 2007 Tammelin et al. 2015 Farina et al. 2019a).
However, averaging the strategies can be undesirable, which not only incurs more computation Bowling al. 2015) (additional memory and computation for the average strategy), but also intro-
Alphahetical Order

---

Published as a conference paper at ICLR 2023
duces additional representation and optimization errors when function approximation is used. For example, when using neural networks to parameterize the strategies, the averaged strategy may not be able to be represented properly and the optimization object can be highly non-convex. Therefore, it is imperative to understand if (approximated) NE can be efficiently solved withoul average, which motivates the study of
convergence. In fact, the popular CFR-type algorithms mentioned above only enjoy average-iterate convergence guarantees so far (Zinkevich et al.) [2007] Tammelin ct al. 2015 Farina al. 2019a), and it unclear if such a last-iterate convergence is achievable for this type of algorithms.
The recent advances of Optimistic Mirror Descent (Rakhlin and Sridharan 2013 Mertikopoulos
et al.] [219 Wei et al. [202]] Cai et al. 2022) shed lights on how to achieve last-iterate convergence for solving normal-form games (NFGs), strict sub-class of EFGs. The last-iterate convergence
in EFGs has not received attention until recently (Bowling et al., 2015 Farina et al. 2019c; Lee et al. 202T). Specifically, BBoliigg et al. (2015) provided some empirical evidence last-iterate convergence for CFR-type algorithms, while Farina et al. (2019c) empirically proved that OMD enjoyed last-iterate convergence in EFGs. Lee et al. (2021) proposed an OMD variant with the first last-iterate convergence guarantees in EFGs, but the solution itself might have room for im- provement: To make the update computationally efficient, the mirror map needs to be generated through dilated operation (see $ for more details); and for this case, the analysis in [Lee et al.. ( requires the NE to be unique. In particular, an important and arguably most well-studied in- stance of OMD for no-regret learning over simplex, i.c., the optimistic multiplicative weights update (OMWU) (Daskalakis and Panageas, 2019; Wei et al. (022I), cannot be shown to have explicit last- iterate convergence rate so far, without such a uniqueness condition, even for normal-form games. Anagnostides et al.] (2022) can only guarantee an asymptotic last-iterate convergence rate without uniqueness assumptior Indeed, it left as an open question in (Wei et al. 2021 if the uniqueness condition is necessary for OMWU to converge with an explicit rate for this strict sub-class of EFGs, when constant stepsize is used.
In this paper, we remove the uniqueness condition, while establishing the last-iterate convergence for Dilated Optimistic Mirror Descent (DOMD) type methods. The solution relies on exploiting the power of the regularization techniques in EFGs. Our last-iterate convergence guarantee is not only for the convergence of duality gap, a common metric used in the literature, but also for the actual iterate, i.e., the convergence of the distance to the set of NE. This matches the bona fide last-iterate convergence studied in the literature, e.g., Daskalakis and Panageas| (2019); Wei et al. (202T), 1), and such a kind of last-iterate guarantee is unknown when the mirror map is either dilated or entropy- based. More importantly, the techniques we develop can also be applied to CFR, resulting in the first last-iterate convergence guarantee for CFR-type algorithms. We detail our contributions as follows.
Contributions. Our contributions are mainly four-fold: (i) We develop new type of dilated OMD algorithms, an efficient variant of OMD that exploits the structure of EFGs, with adaptive regulariza- tion (Reg-DOMD), and prove an explicit convergence rate of the duality gap, without the uniqueness assumption of the NE. (ii) We further establish a last-iterate convergence rate for dilated optimistic multiplicative weights update to the NE of EFGs (beyond the duality gap as in Cen et al. (2021b), for the NFG setting), when constant stepsize is used. This also moves one step further towards solving the open question for the NFG setting, about whether the uniqueness assumption can be re- moved to prove last-iterate convergence of the authentic OMWU algorithms with constant stepsizes (Daskalakis and Panageas| 2019) Wei et al. 202T). (iii) For CFR-type algorithms, using the reg- ularization technique, we establish the first best-iterate convergence rate of O(1/T2/4) for finding the NE of non-perturedd EFGs, and last-iterate asymptotic convergence for finding the NE of per- turbed EFGs in terms of duality gap, which is useful for finding approximate extensive-form perfect equilibrium (EFPE) (Selten, 1975). (iv) As a by-product of our analysis, we also provide faster and optimal rate of O(I/T) average-iterate convergence guarantee in finding NE of perturbed EFGs (see formal definition in 1) while also matching the state-of-the-aar guarantees for CFR-type algorithms in finding NE for the non-perturbed EFGs in terms of duality gap (Farina et al., 2019a).
Technical challenges. We emphasize the technical challenges we address as follows. First, by adding regularization to the original problem, RDMDDOMD will converge to the NE of the regularized
A recent result (Anagnostides et al. 2022 Theorem 3.4) also gave best-iterate convergence result with rate, hut only asymptotic convergence result for the last iterate.
2

---

Published as a conference paper at ICLR 2023
Require
Algorithm
Games
Duality Gap
Iterate
NE Unique
Daskalakis and Panageas 2019)
OMWU
Asymptotic
Yes
OMWU
O(ITT) (G)
Wei et al
2021
NFGs
OGDA
Lincar (L)
No
Cen al.
2021b
Reg-OMWJ
Õ(1/T)
No
O(1/T) (G)
Lee et al. (2021
DOMWU
Yes
EFGs
Linear (L)
Reg-DOMD (Ours)
Reg-DOMNU
Õ(1T))
Reg-DOGDA
Table 1: Comparisons between our methods and previous last-iterate convergence methods. (D)OMWU refers to (Dilated) Optimistic Multiplicative Weights Update (Daskalakis and Panageas 2019 and (DJOGDA refers to (Dilated) Optimistic Gradient Descent Ascent (Daskalakis et al.
2018 Liang and Stokes 2019; Mokhtari al.) 2020). And Reg-DOMNU (Reg-DOGDA) refers to
DOMWU (DOGDA) with regularization. The fifth column Iterate refers to the Euclidean distance
to NE. (G), (L) refer global convergence rate and local convergence rate, respectively.
Algorithm
Regret Minimizer
Last
Average
CFR
RM
Zinkevich et al.
2007
(Hart and Mas-Colell
2000
O(1/VT)
CFR+
RM+
No
NE
Tammelin et al.
2015
Tammelin et al. 2015
Stable Predictive
Optimistic FTRL
CFR (Farina et al.
2019a
Syrgkanis al.
2015
O(1/73/4)
Reg- (Ours)
Reg- DS 1DSD-pt.-MMM Mpt.MD
Best-Iterate
NE of Perturbed EFG
CFR+
RM+
No
O(1/VT)
Farina et al.
2017
Tammelin al. 2015
Asymptotic
O(1/
Reg-CFR (Ours)
DDn-DDSOptM
Last-Iterate
Optimal
Table We show the performance of CFR-type algorithms in finding NE and NE of perturbed EFG (see 14.1). The fourth column Last and the fifth column Average represent last-iterate convergence and average-iterate convergence individually. Note that we here view Best-Itere Iterate as some conver- gence guarantee similar to (but slightly weaker than) the last-iterate ones.
problem, instead of that of the original one. By controlling the regularization, one can readily obtain convergence guarantee of the regularized algorithm in of duality gap. as inCenn al. (2021b) for NFGs. However, it is highly non-trivial to connect back to the iterate convergence. We achieve so by proving relationship between the distance the NE set and the duality gap (See Lemma D.6 for the complete proof).
Second, it is challenging to obtain last-iterate convergence guarantees in CFR-type algorithms, since the regret minimizer in each information set cannot synchronize with the other regret minimizers, and they operate independently. Hence, unlike OMD, the individual iterates (not the average) ob- tained from these independent regret-minimizers may reach an NE of the game asynchronously. For the same reason, it is also challenging to extend the fast-rate no-regret learning results from NFGs (over simplex) to EFGs under the CFR framework.
We provide a detailed related work discussion Appendix to compare work with the literature.
Here we provide Table and Table
2 PRELIMINARIES
Notation. We use 2; to denote the i-th coordinate of vector and ||>||p to denote its p-norm. By default, we use || x to denote the 2-norm || 2- We use A, to denote the m 1 dimension probability simplex (ac 10m E N4 1). and sometimes omit the subseript m when
3

---

Published as a conference paper at ICLR 2023
it is clear from the context. For any convex and differentiable function d its associated Bregman divergence is defined as (u(u, v) == v(()) (v()) - (Vb(v), ,0 u v). Finally, we use I[((u) u) to denote the projection of u to a convex set C with respect to Euclidean distance.
Bilinear optimization problem. Strategies in two-player zero-sum extensive-form games with perfect recall can be interpreted in sequence-form (Von Stengel 1996). Thus, finding the Nash equilibrium reduces to solving a bilinear saddle-point problem,
min max øER yEy
Ay
(2.1)
where X' C. R y C Ry are the decision sets for min/max players called treeplexes (to be defined next). In sequence-fore form representation, 3; denotes the probability of reaching node i in the treeplex when only counting the uncertainty incurred by the min-player, and yi can be interpreted similarly. The matrix A E [-1, 1-1.1 M where Ai,j denotes the payoff of the max-player when the min-player reaches i and max-player reaches j. Nash equilibria are just the solutions to Eq (2.1). We define 3 X x y to denote the set of NE, which always convex for two player zero-sum game.
For convenience, we use P = M + N to denote the dimension of problem (2.I). and concatenate the sequence form for both players by defining == [z, y) E := X' x y and the gradient of the bilinear form (2.1) by defining F(z) == (Ay. - A x). By re-normalizing A. we can assume [[ without loss of generality.
Treeplex and dilated regularizer. The structure of sequence-form is enforced implicitly by the treeplexes which we define formally here:
Definition 2.1 (Hoda al. (2100). Treeplex is recursively defined as follows:
1. Each probability simplex is a treeplex.
2. The Cartesian product of multiple treeplexes is treeplex.
3. The branching of two treeplexes is treeplex. where for integers m,n >> O. the branching of two treeplexes 2, C RR.. 2g C R2 on index i E (1,2...,, defined as
Z Z2 {u,, U v) u Z1, 2 22).
(2.2)
See an illustration of treeplex in Figure ! of Appendix A The simplexes in the treeplex specify the decision points for both players, which also called information sets in the EFG literature (Zinkevich et al. 2007: Tammelln et al. 2015) Farina et al., 2019a). The collection of information sets in treeplex Z is denoted H- For any h E 7- use Sr denote the indices in Z belonging to decision point h and hit) to denote the information set that index belongs to. That is, hii) h if and only if 2g. We (h) denote the index of the parent variable of and H. = {h E H. [oh)) = i}. For simplex Z, the parent of the only information set H. does not exist and we use (h)
denote it. And when applying Cartesian product on multiple treeplexes, it will not change the parent of any information set. When we branch two treeplexes, that is 2 Zz, then the parent of all information set h E 7 with oh) 0 will be updated to o (h) = For convenience, we use Nn to denote the slice of z with indices in Ω, Let Cn Max [Sa]] denote the maximum number of indices in each individual information set. For convenience, we define vector q E R.P with & = 2 2/2z(((0)) for any i. In the EFG terminology, 9t. E ( the slice of in information set h, is the probability distribution of actions in information set
The treeplex structure motivates natural dilation operation to generate regularizers that leads to efficient computation in EFGs (Hoda et al. 2010). For any strongly-convex base regularizer d defined simplex, the dilated regularizer is defined
(z) == Σ anzo(N)3)
2h (Z(())
(2.3)
hERE
where (h) is the probability of reaching the parent variable of information set h. And on is the th element of vector R
| which is some hyper-parameter according of to
4

---

Published as a conference paper at ICLR 2023
guarantee that 2 is 1-strongly convex with respect 2-norm (Hoda et al. 2010 Kroer et al. 2020, i.c., D (21, x2) 2 21 =2ll?. Two common base regularizers are the negative entropy
4 Entropy (p) = E; pi log p; and the Euclidean norm d Euclidean (p) P. where p E A is probability distribution.
Finding NE and regret minimization. Given strategy in sequence form, there are two criteria to evaluate the performance:
the Euclidean distance to the set of NE [1 =||,
the duality gap maxsez F(z) (z 2)
When one or both of the above quantities are close to zero, we find an approximate NE. A common approach to minimize duality gap is by regret minimization, where define the (external) regret of the min-player as
T R = ((s)))
T min Σ #eX t=1
(2.4)
where 4 is the loss function at iteration t and x; is the output of the regret minimizer at iteration t. Regret of the max-play sax-elayer can be defined similarly.
When regret is growing sublinearly with respect to T', the average regret is converging to zero (hence the name no-regret). The following Nash folklore theorem implies that the average strategy will converge to NE.
Lemma 2.2. For a bilinear zero-sum game where 13" (2x) -1- = x. Ay, the duality gap of the average strategy ( E Bt Et yt) is bounded by (R). RT)/TT
REGULARIZED DILATED OPTIMISTIC MIRROR DESCENT (REG-DOMD)
3.1 SOLVING A REGULARIZED PROBLEM
To obtain faster convergence rate for OMD algorithms, we will solve the NE of the regularized problem below (and thus strongly convex-concate as an intermediate step. In the literature (McK- elvey and Palfrey 1995), the solution the regularized problem is called the quantal-response equilibrium (QRE), when the regularizer eh is entropy:
min max AAA T 2 =EX yEy
(3.1)
where r E (0, is the weight regularization and 2 is a strongly-conver regularizer. Thanks to the strong convexity of أه Eq (3.1) has a unique NE, denoted by 2 For t = 1,2, ... the update rule of optimistic mirror descent for the regularized problem (3.l. which we refer to as -DOMD can be written as
= argmin (z, F(z - (2)) + D (z, 2c) 2E2
17
(3.2)
2 = argmin (z, F(z)) + ~ (2.) + D (2,
zE2
where we set 2n 2 as uniform strategy, i.e., t0)
is uniform distribution in A and r
the stepsize. The Dilated Optimistic Mirror Descent (DOMD) (Lee et al. 2021) now becomes a special case when O. We call the update rule (3.2) Regularized Dilated Optimistic Multiplicative Weights Update (Reg-DOMw)) DOMWU) when the base regularizer فن is negative entropy, and Regularized Dilated Optimistic Gradient Descent Ascent (Reg-DOGDA) when A Euclidean norm.
As desired, 2 converges to , at linear rate for any fixed т.
Theorem 3.1. With S 8P. 7 S 1 and 2 being a 1-strongly convex function with respect to the 2-norm, RDg-DOMD guarantees that D (2 2 $ (1 - '/' D (2 2,) for any t 2 when initialize 2p 2,.
5

---

Published as a conference paper at ICLR 2023
The results in Theorem 3.1 are for general dilated regularizers, and apply to the regularized version of two representative algorithms, Reg-DCMWU and Req-DOGDA, as studied in Lee et al. (202I). The detailed proof is postponed to Appendix [
We sketch the proof below.
Proof sketch of Theorem 3.1 When v² 3 is a I-strongly convex function with respect to 2-norm and 1) S SP then for any E 2 and & 1, we have
yTp 2 (z) 1TT (zx) + (z))) ( (zt - z)
(3.3)
7 = (ze, Zx) + (1 D (2, 2 (z, Zl+1)= (2(41,
1 w (2,, zt-1);
8
which is adapted from the standard OMD analysis (Rakhlin and Sridharan 2013), but for the regu- larized problem. See Lemma C.2 for the proof.
Taking =- x in Eq 3.3). we have
7 Dus (2 2,) (21
(1 - ( (z+, 2,) D a (z, (2, 2141) D Du (2(11,1; 2,)
(211
2 mmp (z)) - nT (z+) + F)(1)) [ - x7) 0
(3.4)
where (i) follows by definition of 2,7.
Letting 0++1 Dup (z+, 20+1) + Dup (2++1, inequality 3.4 can be written as
3 D (Zz, (21 {g D (2, z1-1) S (1- 17),,
1411 S (1 - 77)
2
(3.5)
where the second inequality comes from 1yT In S
This justifies the linear convergence.
In the existing work Wei et al. (2021); |) Lee et al. (2021) without regularization, i.c., when 0. the above argument cannot guarantee the linearly shrinking property of O, With the unique NE assumption, one prove some "slope" in the original bilinear objective which implies convergence rate (Lee et al. 2021]] Lemma 15). It was unclear such an assumption can be removed.
explicit
Here, the regularization technique enables us avoid such assumption. See more detailed and technical discussion below Lemma D.5
3.2 FROM THE REGULARIZED PROBLEM TO THE ORIGINAL. PROBLEM
Intuitively, the weight of regularization 7 is sufficiently small, NE for the regularized problem should be close the NE of the original problem (2.1 In the following we formalize this intuition and show how Theorem 3.1 implies a last-iterate guarantee.
We shrink the weight of regularization 7 follows: TD at the beginning and run Reg-DOMI in episodes. In each episode, we update the parameters z, and 2+11 for ((1/r) iterations so that the duality gap of 2, will be lower than ((r) according to Lemma D. and Theorem 3.1] Then, we will shrink 7 by one half and start the next episode from scratch. Notice that although is changing, the stepsize keeps fixed/constant, which differs from Hsieh et al. (202I), where the stepsize adaptive.
First initialize To for some hyper-
Theorem 3.2. With the shrinking algorithm described above, the duality gap satisfies max 1))+1) (a
2) I O(?) for t = I...... Moreover, we have an iterate con- vergence rate of || - II (2)+ s O(!)
In practice, we use an adaptive weight-shrinking rule proposed in Appendix A which is motivated by Yang et al. 2020).
Note that Theorem 3.2 applies for both Reg-DOMWU and Req-DOGDA. To the best of our knowl- edge, this is the first result obtain convergence rate for duality gap and the distance to the NE set in EFGs without the unique NE assumption, when the mirror map is generated through a dilated operation (Lee et al. 2021)

---

Published as a conference paper at ICLR 2023
Technical overview. We briefly sketch the intuition behind the proof and defer the full details to Appendix [ To prove the duality gap guarantee, first notice that in the regularized problem, &n has small duality gap thanks to the last-iterate guarantee in Theorem 3.1 So we only need to argue that the duality gap of 2, in the original problem is also small, which turns out to be (
However, this argument does imply small distance to the NE set, because the distance between z, and x" is unknown. Instead, we need the result that the lower-bound of the "slope" of the duality gap strictly positive, i.e., for any 2, we have m Fz)) (z =²) c|| for some constant с > 0. Moreover, compared to existing "slope" results (Gilpin et al. 2008 Wei et
(z)
max, F(z) 2021 we provide a stronger one when the regularizer entropy since we prove that z') 2 c - I1.. when z' is restricted to subset of 2 (see Lemma D.6
Due to the regularization, our dependence on the EFG size P is quite mild. There's only a P|| |/sc dependence on the EFG size for the duality gap convergence result (1) (||x|] is usually O(P2) regard- ing the specific type of dilation (Hoda al. 2010, Kroer et al. | 2020 Farina et al.T(20TT). which can
be found in Appendix D The convergence rate of the distance to the NE set of the original problem depends on the slope e, which also depends on the reward matrix.
4 REGULARIZED COUNTERFACTUAL REGRET MINIMIZATION (Reg-CFR)
Counterfactual regret minimization is the most widely used solution framework in EFGs in the past decades, and has achieved many successes including defeating the professional human player in Texas Hold'em em (Brown and Sandholm 2018 2019b). Through the framework, the (global) regret of the EFG in (2.4 can be minimized by minimizing the local regret in each information set separately.
To describe the regret decomposition framework in its full generality, we first introduce some addi- tional notation. (²(z) is the value at the treeplex rooted at information set h of the player h belongs to when both players play according to 2. For any H. W>(z) can be recursively defined as
(x) = Σ di ((Ag): + Σ wh + Tax (gh)
SENA
MEH:
strategy on information set h(i) (it lies in a simplex due the definition of treeplex in Definition 2.1) and on is the hyper-parameter defined in Eq (2.3). For h E H², wh (z) can be defined similarly.
where q: = =z/20(A(0)) E Amorol
the (conditional-forg)
The local loss (gn): pasl
IR at any information set h H2 can be defined by
1. (g)h = (v)( ) + (an))(am))) (qr), where (²) ((Ay): +
Σ wh
WER;
Notice that w* is a scalar while V (z) (z) is a vector. Furthermore, the two quantities can be related to each other by W* =otk)
Zh_ [^(2) + Tan
The local difference at information set h is just (4.(g)) Σl= 1 (g:.)) - Σí= the (qx) and the
local regret R4tt == maxq. Eo, C/ (q.). The following decomposition implies that the global regret can be controlled by the sum of local regrets:
Lemma 4.1 (Laminar regret decomposition (Farina et al. 2019b)). For any 21, 22, Zr, 2 E Z
and 7 2 0, we have
Gf(()= (F(E)) 2) + (2)) T (z))
Σ NEA
zo(h) G/ 2h
20(h)
(4.1)
R$ max Gf(
Σ Rt)
max 2E2
2
where R is the sum of the regret of min-player and max-player defined in Eq (2.4 instantiated with 4((x)= = (F(z), + (x). The proof is postponed to Appendix E Hence, by minimizing R/. at each information set h H2 R4 will also be minimized. By Temma 2.2 the average
7

---

Published as a conference paper at ICLR 2023
strategy will converge to NE when 0. In fact, when O, the average strategy will converge to the corresponding NE of the regularized problem x; according to a stronger version Lemma 2.2 (Theorem 3; Farina et al. 2019b). For completeness, provide the formal version as Lemma R.3
To describe our main results in full generality, we introduce the notion of perturbed EFGs before diving into the algorithm and analysis.
4.1 PERTURBED EXTENSIVE-FORE GAME AND EXTENSIVE-FORM PERFECT NASH EQUILIBRIUM
Although NE specifies a natural notion of optimality in EFGs, an NE strategy is not necessarily behaving reasonably in information sets that it will not reach almost surely. To avoid this issue, stronger and refined notion of equilibirum, extensive- Selten (1975), which takes every information into consideration by perturbing the EFG to force the players to reach every information set. We formally introduce the definitions below.
perfect equilibria, has been proposed in
Definition 4.2. For any y 2 0, a p-perturbed EFG is an EFG with a yy-peruurbed treeplex 2 := X7 x y7 which restricts that qi Rach(t)) 7 for any z 2n and index i. An extensive-form
perfect equilibrium is limit point of ? 77-0 where 2 is the NE of the y-perturbed EFG.
The simplest instance of 7-perturbed treeplex is a 7-perturbed probability simplex A where all entries have probability larger than 7. Since the standard EFG is just a perturbed EFG with ; 0. we will only describe our results in 7-perturbed EFG to keep the argument unified and general, and only translate our result to the y = 0 case when necessary. Correspondingly, we use 2 denote the Nash equilibrium of the regularized game in Eg (3.1) when (z. y) E Z", When y > 0, 2 is empirically used as an approximation that 20* could been seen as an approximation of EFPE in terms of duality gap (See Lemma F.4 for more details about this approximation, which might be of independent interest).
the EFPE Kroer et al. 2017 Farina
2017). We prove
4.2 MAIN RESULT
Given the regret decomposition in Lemma 4.1 we instantiate the regret minimizer in each informa- tion set by the regularized version of the Dual Stabilized Optimistic Mirror Descent algorithm (Hsieh) ct al. 2021 ),, i.e., Reg- DS -----D-OOppp Mp. The DS-OptMD algorithm (Hsieh et al.) 2021) achieves con- stant regret in two player zero-sum NFGs, which to the best of our knowledge, is the state-of-the-ar result that achieves this desired property. Hence, we develop our local regret minimizer based on this algorithm. For any information set h E H and & 2. T, the full update rule of our proposed algorithm, Regularized Counterfactual Regret Minimization (Reg -CFR), follows
9t.h = argmin (z"(z=))) )) + Tar VN 1,h:: 9n) + X Dea (qh. 1c-1,A)
qi EA ltal
+ +2, 1) (qn. q1.1o)
(4.2)
3.+4.1- h = argmin (v"(z,_)) + Tap V (qr,)), 9h) + X Dea (qu, 9t,h),
where the adaptive stepsize is defined by X = 8h and 2 is a hyper-parameter. 8 := ||v (=++g) 4h ( is the variation of value function and qt =1,o(h)) Again, for any h E 2 90.A = 9g.x are intialized uniform distribution in A With the adaptive stepsize in Reg-DS--pppe
Se.b
we no longer need to tune the stepsize for each individual information set.
Reg-CFR enjoys a desirable last-iterate convergence guarantee of the actual iterate as follows: Theorem 4.3. Consider the case when т In 7-perturbed EFGs, if we use Euclidean norm as the regularizer ف in Reg-CFR, then 1 D (22 21) < C. where C,, is some positive variable depending on y. As result,
When 7 0 and < Tal C, is constant which implies asymptotic last-iterate convergence to 27.* in terms of Bregman distance.
8

---

Published as a conference paper at ICLR 2023
When y 0, C, I O(T implying (TT33/4) best-iterate convergence rate 2, in terms of Bregman distance.
To the best of our knowledge, under the regret decomposition framework, although some CFR-type algorithms, like CFR+ Tammelin al. 2013). have been empirically observed to have last-iterate convergence (Bowling et al.) 2015). there is no theoretical justifications for them in the literature yet. Our results appear to the first establish the provable best- and last-iterate convergence results under the regret decomposition framework of CFR. Even in terms of empirical performance, our algorithm Reg- CFR can achieve faster last-iterate convergence rate comparing to previous ones. More interestingly. by applying regularization to CFR (Zinkevich et al. 2007) and CFR+ (Tammelin ct al. 2013), we empirically show that regularization can improve the last-iterate performance. We will discuss them in Appendix B
Significance of last-iterate convergence for CFR. We believe that Theorem 4.3 paves the way for more tractable CFR-type algorithms with funetion approximation in large-scale EFGs like Texas Hold'em, em. Previously, although Brown and Sandholm (2018) 2019b) achieved super-human level performance in Texas Hold' em, they utilized domain-specific abstraction techniques (Ganzfried and Sandholm 2014 Brown et al., 2015), which will merge the similar nodes in Texas Hold' em into one make the total number of nodes tractable. However, the existing abstraction methods are highly restricted to the poker games. Therefore, it is crucial to design algorithms with function approximation to do such abstraction in an end-to-end manner.
Currently, the average-iterate -tterae convergence of CFR is an obstacle to using function approximation. In the seminal work Deep-CFR (Brown al., 2019). the authors trained an additional network to maintain the average policy, which caused additional approximation errors. In the subsequent work (Steinberger 2019, Steinberger et al. 2020), to get the average policy, they stored the networks at every iteration on disk and sampled one randomly to follow. Though sampling successfully elim- inates the additional approximation error, given that it takes at least 10 iterations to converge in large poker games, storing all networks disk is not tractable for large games like Texas Hold' Hold'em. em.
we can easily run CFR with function approximation since we only need to take the best model during learning due to the best-iterate guaranted"
With Theorem 4.3
A direct consequence of the theorem above is the following corollary.
Corollary 4.4. For any desired duality gap e, we can set O(e). The best-iterate convergence to the NE z" when convergence z = the NE of the 7-perturbed EFG, both terms of duality gap.
0 would be O77-1/1). When >> 0, we will still have asymptotic last-iterate
Remark 4.5 (Technical challenges in showing best-iterate convergence for CFR-type algorithms). Although OMD achieves last-iterate convergence (Daskalakis and Panageas 2019 Wei et al. 2021) and fast average-iterate convergence (Rakhlin and Sridharan 2013 Syrgkanis et al. 2015), )) applying
OMD as local regret minimizer in the CFR framework does not enjoy those results since the loss function for the regret minimizer depends on the global strategy in the treeplex which is not totally controlled by the local regret minimizer as in the NFGs. Therefore, the local regret minimizer could be seen as deployed in changing environment where the previous results do not apply.
Moreover, as by-product, we find that the average strategy produced by Reg-CFR is also superior comparing to the previous variants of CFR algorithms to our best knowledge. Notice that when picking T = 0, the algorithm will converge to the NE = the 7-perturbed EFG.
Theorem 4.6. Consider the case when 7 2 0 and the regularizer is Fuclidean norm. In 7-perturbed EFGs with 7 > 0 and + S 2|]a] the average strategy output by Reg-CFF converges to 27"* with convergence rate O(1/T), which is the optimal rate. In the original EFG with = 0, the average strategy output by Reg-CFR converges to 2 with convergence rate O(1/33/4)
To the best of knowledge, Reg-CFR is the first CFR-type algorithm that achieves the theoret- ically optimal average-iterate convergence rate (1/TT) when > 0 (for both 7 > 0 and 7 = 0). Furthermore, it maintains the current state-of-the-arr average-iterate 011/T3/4) convergence rate established by Farina al. (2019a) in the original EFG where 7 = 0.
In fact, found that just taking the last iterate is good enough empirically. This part can he referred to Figure and Figure

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
T.Y. was supported by NSF CCF-2112665 (TILOS AI Research Institute). A.O and K.Z. were sup- ported by MIT-DSTA grant 031017-00016. K.Z. also acknowledges support from Simons-Berkeley Research Fellowship. The authors also thank Suvrit Sra for the valuable discussions.
REFERENCES
loannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games, arXiv preprint arXiv:2203. S.Ki::223..20566, 2022.
James P. Bailey and Georgios Piliouras. Multiplicatiie weights update in zero-sum games. In Éva Tardos, Edith Elkind, and Rakesh Vohra, editors, Proceedings of the 2018 ACM Conference Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 321-338. ACM, URL
2018. doi: 00.1145522111663329233... 3219235
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up Limit Hold' em poker is solved. Science, 347(6218) 2015.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up up no-limit poker: Libratus beats top professionals. Science, 359(6374):418-424 2018.
Noam Brown and Tuomas Sandholm. Solving imperfect-infformaionn games via discounted re- gret minimization. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-Firys Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances Artificial Intelligence, EAAI 2019, Hon- olulu, Hawaii, USA. January 27 February 1, 2019, pages 1829-1836, AAAI Press, 2019a. doi: 10.1609/aaii. w33001333333300 13000013311100 1829. URL htt / 0t00:/00/a//1111//aaaaa......... 33011829
16090/66199a300 v33101.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 885-890, 2019b.
Noam Brown, Sam Ganzfried, and Tuomas Sandholm. Hierarchical abstraction, distributed equi- librium computation, and post-processing, with application to a champion no-limit texas hold' em agent. In Workshops at the twenty-ninth AAAI conference on artificial intelligence, 2015.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret min- imization. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference fornia, USA, volume 97 of Proceedings of Machine Learning Research, pages 793-802. PMLR, 2019. URL SRRL:ttt:/p/occeddingg
Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Cali-
mlr www.prressvvvv /
http://////oo///loo http//bownll11mmm html
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Tight last-iterate convergence of the extragra- dient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities. arXiv preprint arXiv:2204. 22220228... 2022.
Shicong Cen, Chen Cheng. Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2021a.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for com- petitive games with entropy regularization. In Marc Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrIPS 2021. December 6-14, 2021, virtual, pages 27952- 27964, 2021b. URL Ittptt: htttts::/prroeeedingg www.eiinnnnnnnunnunne... ips hcc//paper/2221/heee eb1 051188890000 2d44299d5addeeceee wtw.://aaaaaaa.cccoooooooeeea/aa Abst.rtt.btttttt.t......... html
Constantinos Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In Avrim Blum, editor, 10th Innovations in Theoretical Com- puter Science Conference, ITCS 2019, January 10-12. 2019, San Diego California, USA, vol- ume 124 of L.Pless, pages 27:1-27:18. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019.
10

---

Published as a conference paper at ICLR 2023
doi: 10.430/LIPtcs./TSS.211922 URL 2019.27
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canadu, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
URL Settps://openreee .et.teiwweeeee..e.......... http://www.eeeeooumeeeeeeeeee
Gabriele Farina and Nicola Gatti. Extensive-form perfect equilibrium computation in two-player games. In Satinder Singh and Shaul Markovitch, editors, Proceedings of the Thirty-First AAAI Conference Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pages 502-508. AAAI Press, 2017. URL http: http:///aaaa.rgg////// .org/ooggss.............. www.///neeeeeeo..oooooooeo.ea.sw index. whppppppppaa AAAT/
vttp:////www//4223333 14423
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Regret minimization in behaviorally- constrained zero-sum games. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning. ICML. 2017, Sydney, NSW, Australia, 6- 11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1107-1116. PMLR, 2017. URL
mir httpp///e/////faaaaaaaaaaaaaaa
Gabriele Farina, Christian Kroer, Noam Brown, and Tuomas Sandholm. Stable-predictive opti- mistic counterfactual regret minimization. International conference on machine learning. pages 1853-1862 PMLR, 2019a.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Online convex optimization for se- quential decision processes and extensive-form games. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019. The Thirty-Fire Innovative Applications of Artificial In- telligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February 2019, pages 1917-1925. AAAI Press, 2019b. doi: 10. v3t0:/aa...300011310111111 //doi. 1111111.1199/ae 1609/aaa1 v33101 33011917
URL https:
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive-form games via dilated Distance-generating functions. Advances in neural information processing systems, 32, 2019c.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Regret circuits: Composability of regret minimizers. In International conference on machine learning, pages 1863-1872. PMLR, 2019d.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Better regularization for sequential deci- sion spaces fast convergence rates for nash, correlated, and team equilibria. EC '21: Proceedings of the 22nd ACM Conference Economics and Computation, 2021.
Sam Ganzfried and Tuomas Sandholm. Potential-aware imperfect-reeall abstraction with earth mover's distance in imperfect-informatiis games. In Proceedings of the AAAI Conference Artificial Intelligence, volume 28, 2014.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, ICMI, 2019, 9-15 June 2019, Long Beach, Cali- fornia, USA, volume 97 of Proceedings of Machine Learning Research, pages 2160-2169, PMLR, 2019. URL BtRLttttpp/ppceeeiiii
mlr.. www.pprsspee......... / wwt.////eee9....... html
Andrew Gilpin, Javier Pena, and Tuomas W Sandholm. First-order algorithm with (In (1/=)) convergence for-equilibrium in two-person zero-sum games. 2008.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127-1150) 2000.
Samid Hoda, Andrew Gilpin, Javier Peña, and Tuomas Sandholm. Smoothing techniques for
computing Nash Equilibria sequential games. Math. Oper. Res., 35(2):99-511) 2010. doi:
10.1287/moor. 1e.11100..000 140.0 wtt.hhtts://ddem .aroiioorg//io 100 1287 moor. 1ww.or..1100000 1100. 0452

---

Published as a conference paper at ICLR 2023
Josef Hofbauer and Ed Hopkins. Learning in perturbed asymmetric games. Games and Economic Behavior, 52(1):133 152, 2005.
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in con- tinuous games: Optimal regret bounds and convergence to Nash Equilibrium. In Conference Learning Theory, pages 2388-2422. PMLR, 2021.
Vishruti Kakkad, Hitarth Shah, Reema Patel, and Nishant Doshi. A comparative study of applica- tions of game theory in cyber security and cloud computing. Procedia Computer Science, 155: 680-685, 2019.
Christian Kroer, Gabriele Farina, and Thomas Sandholm. Smoothing method for approximate extensive-form perfect equilibrium. In Proceedings of the Twenty-Sixth International Joint Con- ference Artificial Intelligence, IJCAI-17, pages 295-301, 2017. doi: 10.24966/ijcaa.2011742. URL
09..1..2493932 2017/44
Christian Kroer, Kevin Waugh, Fatma Kiliç-KKazzun and Tuomas Sandholm. Faster algorithms for extensive-form game solving via improved smoothing functions. Mathematical Programming, 179(1):3854477, 2020.
Harold W Kuhn. simplified two-person poker. Contributiooss to the Theory of Games, 1(17)): 97-103, 1950.
Chung-Wa Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence extensive-fom games. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jen- nifer Wortman Vaughan, editors, Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 14293-14305, 2021. URL https : http::///ooooeeeeeeeeemom ngs www.inuuip.... cc/ paper
1ew.://11111111111aaaaa03333 7d558le
Abstract aab.aaaaa..bbbs.sa-attttra..... .tml
Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Ar- rificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 1441-1449, PMLR, 2021. URL http::/proceeding/ .m.r. press v130//ei220. html
Stefanos Leonardos, Georgios Piliouras, and Kelly Spendlove. Exploration-exploitaee in multi- agent competition: convergence with bounded rationality. Advances Neural Information Pro- cessing Systems, 34:26318 21-26118-6633,, 2021.
Tengyuan Liang and James Stokes. Interaction matters: A note non-asymptotic local conver- gence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 907-915. PMLR, 2019.
Richard D McKelvey and Thomas R Palfrey. Quantal Response Equilibria for normal form games. Games and economic behavior, 10(1):6-33) 1995.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvári, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6820 6829, PMLR, 2020. URL htLhhtt::/// /olL:tttp//pprceeeinng
mlr. www.ppeessssv...
v/l 9/mm///..... mwmmmmm12000 html
Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM- SIAM Symposium Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2717. SIAM, 2018. doi: 11377119778111175501112722 URL https://
doi. doi.org// 10. 1111/11111. 978161117753111177777
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan- Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in auddle-point problems: Go- ing the extra (gradient) mile. In 7th International Conference on Learning Representations,
12

---

Published as a conference paper at ICLR 2023
ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https: // //openeeview wwwp:/wwwwwwi..ee/eeeeeeeeeeeeee htt.:/oooon2.---.ce
Peter Bro Miltersen and Troels Bjerre Sørensen. Computing a quasi-perfect equilibrium of two- player game. Economic Theory, 42(1):175-11,, 2010.
Aryan Mokhtari, Asuman E. Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intel- ligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], vol- ume 108 of Proceedings of Machine Learning Research, pages 1497-1507, PMLR, 2020. URL http::/prrcceddinn mwr. prwss wttp://s/ww111mmomttaaaa.aa htt////oottttaaa.aa html
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2003.
Yurii E. Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM J. Optim., doi: 10.1 10.13775105262340042222
16(1):235-243) 2005.
URL https://dos Sttps::/ddi.orr/II.. org/10.
Julien Perolat, Remi Munos, Jean- lean-Baptiste Lespiau. Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, al. From poincaré currence to convergence in imperfect information games: Finding equilibrium via regularization. In International Conference on Machine Learning, pages 8525-8535. PMLR, 2021.
Georgios Piliouras, Lillian Ratliff, Ryann Sim, and Stratis Skoulakis. Fast convergence of optimistic gradient ascent in network zero-sum extensive form games. arXiv preprint arXiv:2207 08826, 2022.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning. and games with pre- dictable sequences. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceed- ings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 3066-3074, 2013. URL
ppaper/2133/hatt/
Abstt html
Martin Schmid, Matej Moravcik, Neil Burch, Rudolf Kadlec, Josh Davidson, Kevin Waugh, Nolan Bard, Finbarr Timbers, Marc Lanctot, Zach Holland, et al. Player of games. arXiv preprint
11X.v:211..03178, 2021.
R. Selten. Reexamination of the perfectness concept for equilibrium points in extensive games. Int. J. Game Theory, 4(1):25-55, mar 1975. ISSN 0020-7276. doi: 10. 10.10//0/00076 URL https: org/ /10 100.00000/00/1110000000000000
Martin Shubik. The dollar auction game: A paradox in noncooperative behavior and escalation.
Journal of conftict Resolution, 15(1):109-111, 1971.
Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: opponent modelling in poker. In Proceedings of the Twenty- First Conference on Uncertainty in Artificial Intelligence, pages 550-558, 2005.
Eric Steinberger. Single deep counterfactual regret minimization. CoRR,
2019.
URL htRl:tttp://aaxlv.oog////////// 07621
Eric Steinberger, Adam Lerer, and Noam Brown. DREAM: deep regret minimization with advantage baselines and model-free learning. CoRR, abs/2006. 10410, 2020. URL httpss://axxiz
org/abs/2000 2006. 10410
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence regu- larized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
13

---

Published as a conference paper at ICLR 2023
Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving Heads- Up Limit Texas Hold' em. In Qiang Yang and Michael Wooldridge, editors, Proceedings of the Twenty- Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Ar- gentina, July 25-31, 2015, pages 645-652. AAAI Press, 2015. URL http::/ijcca .org/
Acstract/157097
Yuandong Tian. Qucheng Gong, and Yu Jiang. Joint policy search for multi-agent collaboration with imperfect information. Advances in Neural Information Processing Systems, 33: 13:19931-19942 2020.
Karl Tuyls, Katja Verbeeck, and Tom Lenaerts. A selection-mutation model for q-learning multi- agent systems. In Proceedings of the second international joint conference on Autonomous agents and multiagent systems, pages 693-700, 2003.
Bernhard Von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):20-246, 1996.
Chen-Yo Yu Wei, Chung- Wei Lee, Mengxiao Zhang. and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In 9th International Conference on Learning Repre- sentations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL
https://cpenrevil .ee.tt/weeeeeeeeee..e....e..ee.e http///rrmmmeeeee ?dd-xx 7vn5_r
Wenhao Yang, Xiang Li, Guangzeng Xie, and Zhihua Zhang. Finding the near optimal policy via adaptive reduced regularization in mdps. CoRR, abs/2011.00213 2020. URL https:
/21111111110 110011.0000 00213
Martin Zinkevich, Michael Johanson, Michael H. Bowling, and Carmelo Piccione. Regret min- imization in games with incomplete information. In John C. Platt, Daphne Koller, Yoram Singer, and Sam T. Roweis, editors, Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference Neural Information P Processing Systems, Vancouver, Brilish Columbia, Canada, December 3-6, 2007, pages 1729-1736. Curran Asso- ciates, Inc., 2007. URL http:pppee//...oeenni....ooor/ neur. ips. cc httpppaapee/200///sstttt. DB9363BB6E0L00bbb112299922331333 Abstssstttte-bttaattttt.
14

---

Published as a conference paper at ICLR 2023
Supplementary Materials for "The Power of Regularization in Solving Extensive-Form Games"
A OMITTED DETAILS
Here present some details omitted in the maintext.
A.1 RELATED WORK
Regularization. In reinforcement learning, regularization has been widely used to accelerate con- vergence and encourage exploration (Tuyls et al., 2003 Geist et al.) 2019 Cen et al. 202 Mei cct al. 2020). In game theory, regularization can be used to turn the bilinear objective in normal- form games into strongly-conver convex-stronglyy 2021b). However, Hofbauer and Hopkins (2005) only gave asymptotic convergence to the NE of the regularized game under the best-response dynamics and [Cen et al. (2021b) only provided con- vergence of OMWU to the original NE in terms of duality gap. Similar ideas could be dated back to the smoothing techniques led by Nesterov (2003). This way, the linear convergence rate to the saddle point of the new objective can be guaranteed. Letting the regularization be small, the solution the regularized problem can be close to the NE of the original problem, in terms of duality gap (Cen et al. 2021b). In contrast, we aim to show the convergence in terms of not only the duality gap, but also the distance to the NE set (of the original problem), and for the more complicated setting of EFGs. The idea of using regularization in learning in games has also been explored re- cently in various different settings (Perolat et al. 2021 Leonardos et al. (02T). Specifically, Perolaa et al. [2021); Leonardos et al. (2021) study continouus-nne -ime dynamics and establish convergence to NE, either only gave rate to the NE of the regularized game, or only guaranteed asymptotic con- vergence to the NE of the original game, using techniques based on Lyapunov arguments. Instead, our focus was on discrete-ting convergence rates for both duality gap and iterate-distance. Finally, we note that the framework of CFR (for solving EFGs) was not investigated in these recent works.
one (Hofbauer and Hopkins 2005 Cen al.,
optimistic mirror-descent algorithms with constant stepsizes, with
Last-iterate convergence. Finding the NE in EFGs could be formulated as finding the saddle point of a bilinear objective function. While mirror descent diverges in simple cases (in terms of the last-iterate) (Mertikopoulos et al., 2018] Bailey and Piliouras 2018), its optimistic version receives great success in finding the saddle point, enabling both faster and last-iterate convergence guaran- tees (Rakhlin and Sridharan] 2013) Mertikopoulos et al. 2019 Lei et al. 2021 Daskalakis et al.) 2018 Mokhtari et al., (2020). However, these previous works either only consider the case without constraints (which do not apply to the NFG/EFG setting), or provide only asymptotic convergence without explicit rate. Recently, with the unique NE assumption, Daskalakis and Panageas (2019)
gives asymptotic last-iterate convergence result for OMWU in NFGs. Wei et al. (2021) further improves the result by showing that both OMWU and OGDA converge to the NE with global sub- linear convergence rate O(1/T)) and a local linear convergence rate in NFGs. Among them, OMWU requires the unique NE assumption. Very recently, Cai et al. 2022) provides a tight last-iterate con- vergence for OGDA. Finally, Lee et al. (202T) extends the result of OMWU from NFGs in Wei al. (2021) to EFGs, and still requires the unique NE assumption. Concureent to our submission, we are aware of Piliouras et al. (2022), which studies network zero-sum EFGs with last-iterate conver- gence rate guarantees, also without the unique NE assumption. However, the regularizer therein for the OMD update rule is neither dilated nor entropy- which makes the algorithm less scalable than the one we study, with dilated and entropy- based regularizer, see Lee al. (2021) for a related discussion.
Counterfactual regret minimization (CFR). CFR-type algorithms are based on the idea that the regret in EFG could be decomposed into the local regret of each information set. By minimizing the local regret, the global regret will be minimized and the algorithms will achieve average-iterate convergence thereby. Recent work Farina et al. (2019a) utilizes the progress in the aforementioned optimistic methods, and achieves faster average-iterate convergence rate of O(1/73/4) in EFGs.
15

---

Published as a conference paper at ICLR 2023
However, since CFR-type methods rely the regret decomposition that breaks the structure of the strategy, up to now no CFR (and variant) algorithms are able to inherit the optimal rate optimistic algorithms have enjoyed in NFGs, to the best of our knowledge. Also, due to the decomposition, although [Bowling et al. (2015) has found that the last iterate of CFR+ (Tammelin et al. 2015), variant of CFR, converges empirically, no CFR-type algorithm have the last-iterate convergence guarantee theoretically.
Extensive-form perfect equilibrium and perturbed EFGs. Nash equilibrium in EFGs does not have any guarantec at the places with zero probability to reach when all players follow the NE. Therefore, in reality when players make an error that leads to an impossible state in the NE, still following the NE may be suboptimal. The concept of extensive- been proposed to resolve the issue (Selten 1975). To find the EFPEs, Miltersen and Sørensen (0100; Farina and Gatti (2017) formulate the problem as linear programming (LP), which is not tractable for large EFGSs Kroer et al. (2017) and Farina et al. (2017) extend the first-order method (Nesterov] 2205) and CFR to the perturbed extensive-form game (Selten 1975) (which can be used for finding approximate EFPEs), where players have small probability choosing to act randomly at every information set. Both of the results do not have last-iterate convergence.
perfect equilibria has thus
A.2 A GRAPHICAL ILLUSTRATION OF TREEPLEX
For better understanding of the structure of treeplex, we show the treeplex of the player who moves first Kuhn Poker in Figure]]
Jack
Queen
King
Check
Raise
((h2)
a (h,)
Check
Fold
Cleck Fddd
fh
Figure 1: Treeplex of the player who moves first in Kuhn Poker, say player x. The blue circle denotes the chance node and the grey triangles denote the indices in This is the place where Cartesian product is applied to. And the squares denote the information sets of player x, which are the simplexes. The purple arow the place applied Branching once structure as Jack under Queen & King. The dotted square represented the indices belongs to information set h1 and he and the red line represents the parent index of h and h2.
1). We omit the same
The treeplex is built up from simplexes (2 each under different private card). Here's how the treeplex is built up.
Branching: A1 1/2-
Cartesian Product: Cartesian product of 3 similar treeplexes under Jack, Queen & King individually.
And the whole game of Kuhn Poker is shown in Figure
16

---

Published as a conference paper at ICLR 2023
Jack, Queen
Jack,
King. Queen
Check
Raise
Check
Raise
Check
Fold
Check
Fold
Figure 2: The full game tree of Kuhn Poker. The yellow nodes belong to the player who moves first and the purple nodes belong to other player. The blue node the chance node which dealt private cards for each player. The first line is the private card for the player moving first and the second line is for the other player. The game tree under different private card composition are same only plot the first-move player get Jack and the second-move player get Queen.
A.3 PSEUDOCODE OF THE ADAPTIVE
ALGORITHM
Here's 's the practical version of adaptively shrinking т framework mentioned in
3.2
Algorithm Adaptive Weight-Shrinking
1: T + To
2: 87 <- maxx F(zo) (20 - z') + Toy) - Top/ (z²)
3: 20, 21 Uninform Strategy
4: for t 1,,,
5: Zr, 2.41 Reg--eMMD(( (2:
6: if maxx' F(2)) (z) 2') + 2 (2)))(2)) 1 & then
7:
+
8:
6, + max F(2.) T (z: - z') + Tu/ (2,) Tx)
9:
2: < 2,+1
10: end if
end for
Notice that this framework can also applied to Reg-CFR by simply changing Reg-DOMD to Reg-CFR.
A.4 EXPERIMENT ENVIRONMENTS
Kuhn Poker (Kuhn) 1950). In Kuhn Poker, there are two players and three cards, Jack, Queen and ng. And at beginning, each player should place chip into the pot and then private card will be dealt to each player. And each player call, raise fold in each round. If player call, then she should ensure that each player contributes equally to the pot. a player raise, she should put more chip in the pot than the other. If player fold, then the other player takes all the chips in the pot. There will be at most raise in the game. And a betting round ends when both players call one of them fold.
After the game ends and nobody folds, the two players reveal their private cards and the one with higher rank takes all the chips in the pot.
17

---

Published as a conference paper at ICLR 2023
Last-Iterate (Kuhn
Last-Iterate
CFR
CFR www
Reg-CFR, 15 x=
Reg.DOMWU, r- 0.0, 25.0
Dual Cap log10
logio
Reg-DOMWU,
Reg DOGDA ==0.0,
CFR
CFR+
Reg-CFR. 05.x
VVVVV
Nog-DOMMU,, T 0.0.
Reg-DOMWU,
Reg D0E-DO T- 0-
Reg-DOGDA -- 00..1
200
400
609
300
1000
20000
40000 60000
BOUDO
100000
TimeStep
TimeStep
Figure 3: The last-iterate convergence result in Kuhn Poker (left) and Ledue Poker (right). CFR Zinkevich et al. 2007). CFR+ (Tammelin et al. 2015) are tested as baselines. We can see that the last-iterate performance Reg DOMWU and Reg-Reeg-ooo DDOGDA much better than their versions when 0.
Regret (Kuhn Paker))
Regret (Loduc Poker)
CFR
350
CFR
CFR. 0.00001
300
CFR. 0.001
y= 0.001
y=R+,y=0.00
Reg. r- 0.0 -
250
Reg-CFR, r- 0.0, 1... 0.0
CF 0.0001, 1. 0.000
Req-CFR, 1= 05. 1.0. 0.001
Regret
Regret
150
TimeStop
TimeStop
Figure 4: The regret upper- m ΣnENR (N) Rd. in Kuhn Poker (left) and Ledue Poker (right). The regret of Reg-CFR is constant while that of CFR is increased in O(VT). The regret of CFR+ is much lower than OVVT) but not constant, which matches previous empirical result (Tammeln et al. 2015).
Ledue Poker (Southey et al., 2005). Leduc Poker is similar to Kuhn Poker. It has 6 cards, three ranks ((J, Q, K}) with two suits ([a, b)) each. There are betting rounds in Ledue Poker, each round admits two raises. The player who raises should place more chip in the first round and chips in the second. If the game ends and nobody folds, then the players reveal their private cards. The one who has the same private card as the public card wins. If nobody has the same private card as the public card, then the one with higher rank wins. Otherwise the game draws and the two players share the pot equally.
B EXPERIMENT RESULTS
Beyond sharp theoretical guarantees, regularized algorithms EFG also have superior performance in practice, which showcase in this section through numerical experiments in Kuhn Poker (Kuhn) 1950) and Leduc Poker (Southey et al. 2005). The details of the experiment setup are illustrated in Appendix A
The results are shown in Figure 3 for the last-iterate convergence duality gap. We used grid search to find the best parameters for each algorithm. The algorithms Reg-DOMWU, Reg-DOGDA,
18

---

Published as a conference paper at ICLR 2023
Last-Iterate (Kuhn
Last-Iterate
CFR
CFR+
0.9
www
-05
CFR w/ 0.01
CFR+ w/ req. 0,005
-0.5
MWW
Dual Cap log10
-1.0
CFR
-15
-1.5
CFR w/ 0.0001
CFR w/ reg, r- 5e 06
-2.0
-24
-3.0
200
400
600
300
1000
20000
40000
60000
80000
120000
TimeStep
TimeStep
Figure 5: The last-iterate convergence results of CFR and CFR+, in Kuhn Poker (left) and Leduc Poker (right). We can see that with regularization, the last iterate produced by CFR and CFR+ significantly outperforms the original version without regularization.
Average age (Kuhn Poker)
Average (Leduc Poker)
-05
OFR+
CFR w/ reg, 0=00
-1.0
Gap log10
CFR
Gap
-15
CFR
CFR w/ r= 0.0001
reg.
-24
-25
TimeStop
TimeStep
Figure 6: The average-iterate convergence results of CFR and CFR+, in Kuhn Poker (left) and Ledue Poker (right). We can see that by adding additional regularization, the average- iterate convergence still competitive with the original version.
Reg-CFRad A
CFR all apply the adaptive weight-shrinking framework proposed as Algorithm |
in Appendix
As shown in Figure 4 we show the regret upper-bound maXgez ΣneH* (o) R4 We can see that Reg-CFR has constant regrer even in non-pert EFG practice.
Morcover, we further empirically show that regularization is also helpful for CFR and CFR+. That is, with RM and RM+ as local regret minimizers, adding regularization still helps the algorithm for the details. To minimize the regret of a convex but non-linear loss function (ax)),, we feed (Vl,(x;), æx)) into RM and RM+ as the loss function. See FFaina et al. 2019d $2.1) for more details. Moreover, the average-iterate convergence rate of this regularized version is still competitive with the original version. See Figure 6 for details.
enjoy last-iterate convergence. See Figure for
Figure 7 illlustrates the duality gap of average iterate. We can that Reg Reg-CFR is faster than CFR in both environments and has a comparable performance with CFR+ smaller environments like Kuhn Poker.
Figure & illustrates the maximum cumulative regret across all information sets, conditioned on reach- illustratltsssttsss ing that information set. This is also used as metric in Farina et al. (2017); Kroer et al. (2017). This metric can be used to measure the "closeness" to EFPEs. We can see that with y > 0, ReR-eCCP significantly outperforms CFR and CFR- in finding EFPEs.
19

---

Published as a conference paper at ICLR 2023
Average
Average (Leduc
-0.5
CFR
CFR+
CFR, 0=0.001
-10
CRR+, y- 0.001
=e y=
Dual logio
Req:CFR, 0.0001, 10
CFR+
-15
y=
C= 0.000
-2.
Reg-CFR, r= 0.0. 10000=000000000000..0.. y=0
Reg-CFR,
-25
200
400
609
300
1000
20000
40000
60000
80000
100000
TimeStep
TimeStep
Figure 7: The duality gap of average iterate in Kuhn Poker (left) and Leduc Poker (right).
Regret (Kuhn Poker)
Max Re gret (Leduc Poker)
0.0
CFR CFR+
y 0.001
-05
CFR+, 0.001
Reg-CFA, - 0.0. 1100-1000000 y-
Regret (cglo
-1.
Reg-CFR, 0.0001 00000
Regret log10
CFR+
CFR, y=
-15
CFR+.y-0.000
Reg-CFR, CFR, 1.t.kr==.000000001000....
Reg-CFR, - y 0.001
-20
-0.4
-25
200
400
600
800
1000
20000
40000
60000
80000
100000
TimeStep
TimeStep
Figure 8: The maximum cumulative regret across all information sets, conditioned on reaching that information set. We test our algorithm in both Kuhn Poker (left) and Ledue Poker (right).
C PROOF OF THEOREM 3.1
Lemma C.I. For any S and E Z, the NE of the regularized problem Eq 33. satisfies that
F(z) (z z,) - (x,) + Tab (2) 2. 0.
(C.1)
Lemma C.2. Consider the update rule in Eq (3.2 When v/ satisfies Eq C.6 with p 2 and
7 S 8p. then for any 2 E and 2 1, we have
2 (2x) + Fzz)) (z+ 2) S(1 (z,
D (z, 2x+1)
7
- (2141, 21)
Dus (Zt, 2x) + o (Z1,
8
Proof of Theorem
3.1 Taking z = = in Lemma C.2 we have
7
1 Dao (21, 21) + Due (Ze, (Z1, (11)))1)
(1 (1-n5) D (2 21) a (2 E(41) DØ (2 21)
(2)
2 - nTu n (z
+ Ff( (z1 - =;,) 2 0,
(C.2)
where (i) is by Lemma C.I
20

---

Published as a conference paper at ICLR 2023
Letting O++1 D (2,, 2t+1) + D p (Z(+1, 21), inequality C.2 can be written
7
7 -T)) 22 211)
0411 5(1 177 )
D w (Z 2
21
8
8
(C.3)
< 17T )
where the second inequality comes from 1y7 S 1) S 1 As result,
(0z(2,, & 1+11 S 1 = - (1=-))'D
(C.4)
where the last equation is satisfied when we initialize zo = E
Lemma C.3. F(z) is P-Lipschitz for any 2 E Z. That is, for any x, x' E 2, we have
[F((z) F(=')I < Pllz z'1l-
(C.5)
Proof.
IF(=)- =
- (x'12 ||A 2'12 = Pllar x 113
Ply v'l
sv
P|lz </lllz z'11?
<P| z'11-
Lemma C.4. Let C be convex set and i argmin ec (( g -V (u)) D (ū), u)
where v is strongly-convex function in C. Then for any u2 E C, 7 E [0. 11. > 0.
q (ui) ( (n u2.9) < (1 (1-1r) (u2, u) - Dwo bc (u2, un ) -(1-1)T) ve (u u.
Proof. Plug in the definition of Bregman divergence D Duc(ui, = (5((2))) - 1/((2) (Vi (u), un - u), the right-hand side of is equal to,
(T) jar (rz u) D
Pa (u2, u1) (1 (T) pe (u),
= (T)( (uz) - (w) (V (u), u2 - u))
+ ( (-vf (uz) + ((1) + (V))( U2 - -u1)
(u1),
+ (1 - yT)( -b (ui) + 10 (u) + (V
u²)
m - (uz) + (u,) (1 (1-17)V V U2 -21)
2nr (u1) 177 18 (u2) + n , u2.
n
where (i) by the first order optimality of u1, i.e.,
(ng + (wr)(u)) - - V (u)) (u2 - un) 2 0.
Lemma C.5. Suppose that ef is 1-strongly convex function with respect to p-norm in C such that
D&c (x, x') 2 || x'112
(C.6)
for some p 2 1, and u. u1 ug are members of a convex set such that,
11 argmin (u', 91 V (u)) Dec (u', uu)] w'ec
(C.7)
U2 = argmin ( (u', ,2 + VVbl (u)) + Dac (u', u.). w'Ec
Then we have,
[u1 uzllp < | 92 lg
(C.8)
where q 2 1 and ! p
+ 1 =
21

---

Published as a conference paper at ICLR 2023
Proof. By the first-order optimality of u1, U2, U2, we have
(g) + Vile (u)) - (1 - Vv (2)) (u2 - u1) 2 0,
(C.9)
(g2 + V (u2) (1 vv0 (u) -u2) 2 0. Summing up and rearranging the terms,
(u2 W1 91 - 92) (V)))))= V V (u2), u2)
(C.10)
To bound the right-hand side of inequality CC. By the lower bound of Bregman divergence (C.6) we have
1
(V u1 - -u2) 2 (un) - (1((2)) +
(ui)
un
22
1
2
(V u2 - -ui) 2 (u2) - ( + 2 _e
u2 l|.
Summing them up we have
(Vy - (u))) uu - u2) 2 ||uu - u211
Combining with inequality CC
U2 11 91 (2) 2 || u2l1z
(C.11)
Finally, by Hölder's inequality,
U22 41.91 92) S U1 u2l1p 1191 92llg:
and as a result |mu]
u2lpp
lp
9g 92ll, as claimed.
Proof of Lemma
C.7
By definition of NE, we have
F(z) (z x7) x7)
x-
+ Ay + x Ay;)
-( x; Ay + TV² (v) + xx Ayy + (x)) -(12(( (x) + 2 (z))
2 xt Ayy + TW/ (y+) + x Ay; + TT) - -()2 (x) + 2² (g)
=T() - T (z).
Proof of Lemma
C.2 Plug u ã,, Un 2 u2 = 2, = F(zz), ve = 6² into Lemma C.4
? (2++1) m ( - 2, (z)))) < (1-nT) D (z, 2x - D 22 (z,
(2++1, 2t).
Plug u- = 2,, Un = Zt, U2 = 21 = F (z 1) and vc 2ي² into Lemma C.4 2 (2.)-17rv) (E+1) 2 F ((z--1)
)) < (1-1r) ) 2 (2 2.) De (Ze+1, 2,) 32)-(11-77)))) (21, 21).
Summing them up and adding (F(z:) F F(z 1), 2, - 2(+1) 1) to both sides, we have
(2)) 2 (2) + (F()), 2t =) <( m)) D v (z, 2,) D (z, 24+1) - Duo (Z141, 2t)
(1 77) D u (ze, 2.) (F((z)) F(z 1), 2
It remains bound the last term, which is (x.) F(zz- 1), 2t 2,41)
S <n/|ar - - ||7Ay, - -y..-1l ill + nlly - T111ll ||7Ax, - nAx=11
(9)
< (1]Ayy - 1 + ||A
11
(40)
< 21) 121
(iv) 1
$ 32
|z 1| <
1 (||z) -
1
- 22-1133 < (Doz (zi, 2:) + Doz (Zt, 1)-1))
1 8
16
where (i) is by Hölder's inequality, (ti) is by Lemma C.5 with p q 2, (iti) is by Lemma C.3 and (iv) is by 7 < 8F
The proof of the claim is completed by putting everything together.
22

---

Published as a conference paper at ICLR 2023
D PROOF OF THEOREM 3.2
Firstly, we will prove that the approximate NE of the regularized problem is close to the NE of the original problem in terms of duality gap.
Lemma D.1. For any and 2, have
max
F(z) (z 2) 2 2TCB + 2P 2 Dzz(2,
(D.1)
2
where Cg is the upper- upper-bound bound of the regularizer 2/²
Proof.
max F(z) [z) (z- max o REZ
Aÿ 5 Ay; (2,) - (2)
ZE2
TU² (2,) +T=2(3) + (a x;) Aÿ w Aly; y)}
< max a; Aÿ - T Ay + TV (z;) - Tv) (2)} 262
max (-T0) (2 T 2 (z x Aÿ + ā A y)} (D.2)
8E2
(0)
20 2TCB + | x + 1, 111
(1)
2TTCB + 2P| - -
S2rCB + 2P D (zt z)
where (i) is because of the definition of x and |2 1 for any E Z. (tt) is by | S <P| 1l. lly villi vPly yŁ and + b - 2 + + 62. On is the upper-bound of
the regularizer 2 It would be P||a/||> log Co for entropy regularizer and Plalax for Euclidean Ca
regularizer, where Co = max [4,1-
A direct consequence of the lemma is that for any > O, we can set 40p then af- ter 2(loge-log4P) 2 (=) 2(log e- log 4P) +log (2) .1) iterations, ån produced by
log(1-r) Reg-DOM will satisfies that
2
max ( Ay - T A.r) S + 2P 2E2
D Se (D.3)
16P2 22 (z) 21)
by Theorem 3.1
Proof of Theorem 3.2
Sublinear convergence rate of duality gap.
For any 6, the number of iterations that the duality gap reach is no larger than 4CB 21llo lng +l) 2 (L) by the discussion above. Therefore, while duality gap reach- ing fR, the number of iterations performed so far is no larger than
k
4Cn 2* -2 c + 2k log 2 + 2 log 4P + log Di (2 21)
60
A=U
log co K logg2 + log 4P + log a (2, 21)
(D.4)
<4Cn2K+2
=Ō(16))
Iterate convergence.
From the proof of Theorem 5 in Wei al. (2021) have the following lemma.
23

---

Published as a conference paper at ICLR 2023
Lemma D.2 (Proved in Theorem 5 of Wei al. (2021)). Consider bilinear zero-sum game. When X, are polytopes, we have maxgey x' Aÿ - P 2 c c| IIx (a)]l (p mingex Ay 2 e|ly - IIy- (y)li for some constant e > where Ix. (z) (Iy (y)) is the projection of a (z) to the NE set X ()²*) of the min-player (max-player).
Let p = mingex maxyey x' Ay the game value.
Then, since the treeplex is polytope by definition, we have
max
F(2:) (2) 2) max x, #EZ
Ay
min x
Aÿ:
NE
xE
20( -
II
(it) - 11 (0e1))
(D.5)
X
2c
II (2)) 2'
where the last inequality comes from va+b I va + Vb. Therefore, || - I12 (2.)
<
max F (z: 2) (
Notice that comparing to the results in Gilpin et al. (2008) : Wei et (2021). our slope result (Lemma D.6 is based on different techniques. In Lemma we prove that maxgev (II. (z)) Aÿ-p
Cor x IIx- (a))l where V* (a=) S y when a E Fr and F, S X contains all possible iter- ates generated by DOMWU. That is, our result is stronger than the existing results, when the algorithm D Moreover, our result can be viewed as an extension of (Lee et al. 2021 Lemma 14) to the non-unique NE cases. Given that (Lee et al., 202T Lemma 14) plays an critical role in proving the last-iterate convergence with unique NE assumption, Lemma [.6] may be useful when proving last-iterate convergence in EFGs without unique NE assumption and regularization.
D.1 COMPLEMENTARY SLACKNESS
This part of discussion similar the one in Lee et al. 2021). From Definition 2.1 we have
vh H
Σ iED
yi Yo(h),
yo
(D.6)
which can be written compactly Eyy = ey where Ey E [((2)(+))x and ey = O,.., 0) I Except the first row of Ey where there's on index 0 and 0 other- wise, all other rows have 1 on index (h) and -1 on all E Ωr Therefore, for any fixed æ, the objective of be written
max x T Ay yEy Eyy Cy,, y 2
(D.7)
whose dual problem
min T
(D.8)
s.t. E 2 A
where eJg- go since ey 01,
Remind that the primal formulation of the original problem
min max Ay yEY
s.t. ExE: = ex, 8 2 y 2 0.
(D.9)
Eyy = Ey,
In fact, here we only require that the regularization is entropy make Lemma D.7 hold.
24

---

Published as a conference paper at ICLR 2023
Therefore, every solution y" of the original problem would be solution of the following problem.
min 90
#EA
(D.10)
s.t. Eyg2A's ExT = ex a 2 0.
The dual of this one is
max fo w f
(D.11)
s.t. E S Ay Eyy = ey 0.
Note that X ," are the optimal solution of Eq (.10) and Eq (.II.. By complementary slackness, for any optimal solution pair "n"g""), (y", )) we have slackness variables w" E RM s R so that
f w Ay
Ejg A æ w 2 0 8 20
(D.12)
n y o S =0 0
where @ denotes the element-wise product.
As direct consequence, have the following lemma.
Lemma D.3. For any optimal solution pair (a:", "e"",)), 99),, (y", f of Eq (D10) and Eq (D.11) we have
Σ fh + (Ay"); -h(( vi supp(X*))
Σ Ih + (Ay"), 2 fh( Vi g supp(X*)
KEH.
(D.13)
Σ 9h + (AT xx'); = gh(0)
Vi E supp())))
hEH,
Σ 9h + (A T x ) S 9 vi & supp())))
ΛER,
where supp(æ) denotes the support set of vector and supp(C) Uaec supp(æ) denotes the support set of convex set
Proof. Since (EXf), Sh(o EnEH, fh by definition of E, from Eq (D.12). we have
Σ fh 5h+ (Ay") = w + Fho 2 Fa
(D.14)
heHt
For any i where there's x E X' and x > 0, from x= @ w" = 0, we have w 0. Thus, the above inequality takes the equality. So the first two lines of Lemma D.3 are proved. Similarly, can prove the last two lines.
We further introduce the following definitions. Definition D.4.
p TT Ay"
PS(x") {y y is pure strategy, T Ay = p}
PS(y") = {æ: x is pure strategy, x. Ay = =p}
V"(x") -C(PS(w"))
(D.15)
V*(y") = C(PS(y"))
supp(æ) (i:r; 0}
supp(C) = {i: Dx E C, x; > 0}
where C(S) denotes the minimum convex set covering all points in S.
A fact from the definition is that Vy V*(*",,, TT Ay p and Var (*()", Ayy =p.
25

---

Published as a conference paper at ICLR 2023
Lemma D.5. (*(",, (yy") not empty for any x² X", yn y
Proof. For any E X E y", f so that supp(æ) C supp(2**) and (f", .y" is pair of optimal
solution of Eq D.11 we have
x Ay Σ x:(Ay')
Zailfie
-E fi)
BEHL
Σ J Σ
I;
E
(D.16)
NE
iESh
NEH* 1#0
Σ
Σ
f
ME
hEM* 1oy0
-50- =
where the second equality is because supp(æ:) S supp(X()) and Lemma D.3 The fourth equality comes from the fact that Σien, [(())- Therefore, V*(r") is not empty for any y E > Similarly, (*x* is not empty for any x" E X
When assuming unique NE as in Lee et al. 2021 the second line and the fourth line in Lemma D.3 will be strictly larger than and strictly less than by strict complementary slackness. The discussion in Lemma D.S turns out to be if and only if supp(æ) supp(X'),, we have x "Ay" which
strengthen our conclusion here.
D.2 CONNECTION BETWEEN DUALITY GAP AND ITERATE DISTANCE
Lemma D.6. The constants Cz Cy defined below satisfy that Cz. Cy > 0.
(ar II x (a:))
Ay
C inf øe X yEV v (a))
max
x
Ix (x))
(D.17)
x [AAlI 1y- (1) y)
Cy
inf
Dc yEJ = Tly- (v))
IIy (1)l
where
F, = (ø| E X,W Vi E supp(XX") x; 2 <an)
(D.18)
F, (uly y, Vi supp()") y: )
and Gait is some game dependent constant defined Lemma D.7
Proof. Define the set X² = (a|æ E Xx 1x. (x) 2 cau). In the following, we will show that only need consider E X" instead of F, X". Formally will prove that for any x E Fz X², we have x' E X' so that
Ix. (x)) T x
(x' | - -I1x (x'))l
II. (x')) Ay
Vy,
(D.19)
(x)]
The claim trivially holds X". Otherwise, let x' [xxx + | 11x- (m)] (x
cail
(x))
For any element that x; 2 I (m); 2 0, we know that x/. 2 0.
For elements that [xx(x)); > x; 2 we can ensure that supp(X'*), which means that
1x (x); > 2 edi since x E Fz \, x² Therefore, we have x > 1 (w); |z. -Ix (x)
I [=]] 2 [xx; cdil 2 0. Also, for any h E H.²
26

---

Published as a conference paper at ICLR 2023
Σ iEf
Edil
Σ
Ts + (1
<dil
Σ iEst x
II xx)
x
I (x)ll iEsn
| IIx (z:)
(o(h)) + (1 - | Ixxx (x)
(2))(())
(D.20)
[xx(())]
x-
(b))
Therefore, a' E X and we can conclude that x' E X" since IIx- (a)) = IIx (x=).
Moreover, since x² Ix (a) and IIx (a)) are parallel and Ixx (a:)
I1x- we
conclude that Eq D.19) is satisfied. Because X' is closed, we can define
IIx (a)
Ay
min
max
xEX' yEV- (Ix (m))
Ixx (x)]
(D.21)
x
T ATA(Iy- (1) y)
c
min
max
vEV" =E (Iy (v))
lyy [ly.(v)) (v)ll
with the inequality that c2 Cg > O.
2 d and Cy by by the discussion above. Then, we will prove that
Firstly, we will prove that 2 2 0. If cg < 0, then it says that there's 's some so that
min eey (v))
x' Ay >
(D.222
which implies that for any x" X", T Ay p. And it contradicts with the definition of X
cg = O, then for some y $ y"
a: A (v) y) O.
(D.23)
EV (v))
Let P denote all pure strategies of x. If PS PS* then v*[[I- (y)) X. Eq (D.23) implies that mingex x Ay = so that y y But this contradicts with the definition that yr
PS(y") + PS* we define
min {a Ay p). {(y") ær DEPSSPS(y
(D.24)
And we can prove that Ely') E (0, 2M]. The lower bound is directly from Lemma D.3 and the upperbound is from the assumption A that Vy E y, Alyll
1.
Let y' = -Iy- (v) + EaIx~ (w)) have
fly (v)) E V. For any pure strategy E PS \ PS(y"), we
2N-M
x T Ay' = A II (z) [0)
x xT (v) y²))
y"
""
A (I) - || [I 1'll2
y'
"'
(D.25)
EQI (v))
2x
(v)
M
y-
2p
where the last inequality comes from the definition of E(TIy- (v)) in Eq (D.44. For any pure strategy E PPS(y"), we have
ETIl-- (v)
x Ag =x
A
(I(
2N M x T AAy
II (v)
y
y
I[
(v)
(D.26)
y
p.
27

---

Published as a conference paper at ICLR 2023
Therefore, mingex T Ay' 2 p since any a X is linear combination of pure strategies. And it implies that y' & y is also a maximin point, contradicting with the definition of y
So, cy and so does d'.. And further have that Cz1 Cy > 0.
Lemma D.7. For any t 1,2, ..., and supp(2"), and 1) S 2, 2 Gdil where eau is some game-dependent constant.
1 8P. Reg-DOMWU ensures that
Proof. By Lemma C.2
Reg-DOMI satisfies
(TT)(()) (2) 1T (2,) + (z)))
(zz (z: - 2) 5(1-(r))
- DDs (z, - -Doe (z, (2.11)
7
x (2(41,
D p (Z 2x) Da (11)
8
(D.27)
Pick 2 =x such that supp(z") supp(2*)) (note that such E 2 must exist since 2 is
convex). Then, we have
(x") - (2)) Snru) mTO (zt) + (2)) (z1 - x²)
5(1 - nT) (x",)) - D Duz , .2(11)
(D.28)
7
Dus (2 21)
Duz f (Z11 22) + (21
8
where the first inequality comes from F(21) T x²) = xi Ay - x Ay 2 0 by definition of NE, And it further implies that
Dez (z", 2041) D (Z141, 21) 5(1 17) Dus (2)) Duu (Ze: z1-1)
D 22 (Zts 2i) + Dus (Ze, 20-1) mT 2 + 2
{1 mT) Dez (2", 2.) D uu (Ze: 21
D (Ze, 21) + Des (2,, (21, 22-1)) m/ (z*)
2
(D.29)
when ypr 1 1 3
When 7 = 0, we have
D (x 2x4, S D + +x1=(21,2)) 20) Duo (x=,,,))1
(D.30)
And when > 0, we have
(== 2411 S (1 - 17 D (z", (21) -2) S Duz(2", (2²)..
(D.31)
Therefore, for any E supp(Z*) = supp(zz),
o log q1+1,
< Σ of log
= D 2z (2", 22+1) Σ 2n log
q0+1
<D u (2" ,2,) 22()2*) - Σ an log
(D.32)
Σ 2n log 1 v (x")
<2P || log Ch
where the last inequality comes from the fact that 21 is initialized as a uniform strategy. Therefore,
log Cn
1 2 exp (-2Plaal)
(D.33)
min:esupp(Z*) 2?
28

---

Published as a conference paper at ICLR 2023
for any i supp(2*). And we further have
2411 -+110((())) 4441
=( (++1,)((())) 4+1,
(D.34)
log Cn ccxp -2222||<<|lo min:esupp(2")) 2i
=ddiil > 0,
completing the proof.
E PROOF OF LEMMA 4.1
Our regret decomposition framework follows the laminar regret decomposition (Farina et al., 2019b), which is a more general case of the original counterfactual regret minimization (Zinke- vich ct al. 2007). The second part of Lemma 4.1 the boundedness of regret, also appears in (Farina al. 2019b Theorem 2). But here we use Lemma
prove which is more concise.
Lemma E.1 (First part of Lemma 4.1 The difference satisfies that GZ Ehenz Zo(N) (z) for any E 2 and 2 0.
Proof. We define the scalar subtree value S (z) recursively,
(x) = Σ ((Au))) + Σ
st (z)) + ~
(E.1)
k'EH:
For terminal nodes, Hi will be empty set and thus (t) Eiea, (((y))): + Fann)((a)))
By definition, for any 2 E 2", we have
Gz(() Σ (F(22), 21) + (1)) Σ ((F(2)), (x))
(z)) Σ Σ (z)
(E.2)
AeMo
heHo
(z)) -
Σ Sh (z)
ho
m=]
where Ho (h: h H ((h) 0} is the of information at the root of treeplex. Note that 2 = 2,, x 27, x x 2r.,. where Ho {hr, h2,..., hm). Then, the inequality in the second line simply by expanding the definition of (/(()) (z) from the recursive manner.
29

---

Published as a conference paper at ICLR 2023
We further define G
Et= (z))
-E-= (z). Then,
GT,eub(2
(2)
T
T
St
(2))
Σ (z)
1=1
T
S (2+)
(Ayr)) + TanN + ++.+
Σ
Σ
S (z)
tml
N'EH, tml
T
T
Σ
S (z1)
Σ (Aye): + TanN~ + Σ
Σ
Sh (z1)
Ghi' (Za(()))
q:
1=1
MEH;
[=1
T
Σ
4 ((Ag))++ Σ
(z1)) + (q.)))
Σ q:
Σ
G (2)
iE
WEH:
iEQs
MEEH
G (m)) +
Σ
q: Σ
(2)
MEH,
(E.3)
where (i) comes from Et= (z) (z) = =t==E S (z.) Cla (2).
By applying it recursively, we will get for any 2 E 2%
Σ
z0(N) Bo(n) (gn),
(E.4)
hEH
which completes the proof.
Lemma E.2
(Second part of Lemma
4.1 The
regret
satisfies
that
R
S
m ΣnENz R/ for any 7 2 0.
Proof. By Lemma
E.1 we have
21 G+
R
max GZ( SEZ
max
Σ
20(1) Ro(())
ZE2
WE
S max Z
Σ
Zo(
max E
(g))
MEW
Σ ZO(N) R4J
max 2
hE
which completes the proof.
F PROOF OF THEOREM 4.3 AND THEOREM 4.6
F.1 PROOF OF LEMMA
Lemma F.1. For any information set h E 2 gn E pn, and r S 2/|a| Reg-CFR guarantees
(gh))) S Dos (gh. (1.1) + ( (x( | ant Σ Dus (qh. qe.h)
(R1)
T
| (z(+1) - (v 1)12
+
q g,4 -4- 1.a1
\
8
30

---

Published as a conference paper at ICLR 2023
Proof. By Lemma F.
1d ( 1 (41) Tan Tan (qh))
$ <A1 taa) Dii (9h 91.h) 2/ D 91+1N + (A7+1 - DD) (qh, 91
-A - tan (ig 91.1) - \
D (qr+1.h: 9r+1h
2
(gr,h 9:- (p.hh (Ni Dus (a
M
(2++g) Vhh (2, 90+ - q
Daa (q441 (0+111900++)))) go+g,)))
2
T
70k
Dusa (qhn 9t.h)
(F2)
By the strong convexity of v.
19 91- -t-3.a1l
$2 924
+ 2 21, - j.all
(F3)
<4D (1 at,)) + 4D20 (gr,ns 20-2,1)
Also,
X/ D (9
(V (2 1:4
-0+111)
VV' (h 1)1
\/
M Dua (g I--
bllaut 1,
21/
2
2
(F44
(z++))) - (x(
2X
(z++))) (=(
X\
where the second inequality is by Young's ' inequality.
1 2
Therefore, with Tay S 1 -
(9)))
T
=Σ [ (2((2)))) 1 - qn) + Tran (c -onn))
1=1
< < (1++1 Tak Du (gr: 91.1)
| (2 - vhh (2, 4)11
1
X 1llll10 -1--4.111 T0hh
2/2
8
N1+1 Pas (qh, q1,h)) +1 -V* -V²(2)))1 11
||V (2+4 4³h (z, (2,-3)1² })1
1 -t- -0t-gaal?)
-0th Σ
D Des (gn, qt.r);
x
(F.5)
which completes the proof.
For simplicity, we use constant h as the maximum value of D D (qh. 91,k) in information set h. D Dun (gh, q1.h) ) is upper-hounded since Uıhh is initialized uniform distribution in Ajaal-
31

---

Published as a conference paper at ICLR 2023
F.2
PROOF OF THEOREM 4.3
By Lemma E. we have
0 S G7 Gf (27'
(1)
G7 FT
3,5 (1))
where the first incquality is by definition of =7*"
Now by Lemma F.I taking qı 9
T
(1*(
5 Σ
(M++MM* (zz) - (=4)))
(1)
X/2
AEN
2
A/ 8
T
9 - 9:- 91-3.1113))
TCk
Σ tmm
Dus (a 9c.)))
where constant M is the maximum value of D (gh, 41,b) in information set h. Duaa (gh: 91,h) is upper-bounded since qi,h initialized as uniform distribution Ajo.)-
By rearranging the terms, we have
T
Σ Daz (27 ze)
0n2 Dus (ith qch) S C2
(F.)
2-22
where (i) is by the expanded form of the (dilated) Bregman divergence Dui (see Lemma F.8 for detailed proof) and the constant Cy is defined by
|V [
Vh (21-1))
c= Σ (,)(()) hEM
( M (Zg) (z())1 -V+)))
Σ
X/
t=2
/
100 41- 2.2
(F.7
Non-perturbed EFG best-iterate convergence. To bound the quantity Mh
I|V* (+- in C, (other parts of C, have been already bounded by con- stant), we introduce the following Lemma, whose proof is postponed to F.5
Ei=
Lemma F.2. Consider update-rule in Eq 4.2h. For any h H by taking T Reg-CFR satisfies that
||V (Z++3)
VM 1)
\ Mh Σ
OT(
(F8)
X
t=2
where constant Mh the maximum value of Do (gh, .1 information set
By Lemma F2 we know that Ciyy SO(TA), which is
D poz (z) (((T)) O(T
(F.9)
Therefore, there exists l' E (2, 22.,....?? T).
D (2, 2x) < O
(F.10)
7
So, Ze converges to z with convergence rate -T-
32

---

Published as a conference paper at ICLR 2023
Perturbed EFG asymptotic last-iterate convergence. and 1
From the form of constant C.. Eq (..
1, we have
(1*()
(x
C
Σ h
26t (1((h)
(A4+1 21th + (2g) (x))1)
t= X
1
g 90- 9.1l
(F.11)
where constant M is the maximum value of D&a (gh, (1,h) in information set h.
We will prove that C, 01)) when 7 > By the Lipschitz property of (=) (see Lemma for full proof), we have
F.10
| (2++ - V V' (2, 1)1l S(L2
Σ
11 1.4 9t-1.a1l)""
WEM
<PL L3
Σ
119 1.11 - -9:- -9-22,1ll*
(F.12)
<P
(1)) ae+ 9 4.1
hE
where the last inequality is because
7 for any i by definition of 7-perturbed EFG so that
(Ax(3)
Z 2 2_. Since (0)0()) S 1,
Σ NEW
(.( 90- - 91- 4.-1
PLZ 7 T,o(h) (o( (z(+4) - V (Z.-2))1??
(F.13)
for any h H2.
Plugging inequality FF13 to equation F11). we have
C < Σ (To (zz) (24))l
7p
+ Σ T(((h)
| (2++))
(z, 1)117)
16P2 L3
hEHz
[1+(()))3)
Vh -v (2=²
7P
Σ hE
V
(5._,1113) 1)11²)
(M)))))
16P2
(F.14)
As result, it remains to bound the following two quantities in Eq F.15 and Eq F. separately by some constant:
T
M11 M Σ
| (2(4g) - 1² (2-
(F.15)
t=2
vh (z,- 2y1l
(|(((()+)))) Va (z1_
(F.16)
2=
where we use ::= 16P2L3 for convenience.
For Eq F115
since
24
V VK+ Et of where of -1
// (z,- -111 we can get
T
h
+
8h < Mrh + 5th Mr
8h
Σ
8
Σ 5 (F.17)
1=2
1=2
33

---

Published as a conference paper at ICLR 2023
where the second inequality comes from va I
va vb and f is quadratic function with upper-bounded As for Eq F. we discuss the two possible cases separately.
negative coefficient on the quadratic term. Therefore, it is upper- bounded by a constant.
When o M < +o0, then Ei=1 [VV V² (21-)))) +oo from definition of X that Eq (.1 is bounded by constant.
When lim X/ too, then must have t' minet 1/2 S t). Therefore, Eq F.16 is bounded by Et= [IV* - (z +o0.
Therefore,
T Σ
0(1)
Daz 21)
(F.18)
so that 2, converges asymptotically to 2?
Proof of Corollary 4.4
By Lemma
D.I we know that when T 4Cn we will get
max F(z)) 2) O(e) 2P Des (27, 21).
(F.19)
ZEZ
Using Theorem the proof is done.
F.3 PROOF OF THEOREM 4.6
We first state a stronger version the folklore theorem here (Theorem 3 Farima et al. 2019b). to provide gurantees for average iterate below.
Lemma F.3. For EFG where 1 (xx) x Ay, + (x), -x, Ay TO (y),
the saddle point residual maXsez F(z) (z 2) + TD(x) (2) of the average strategy
ET Bt ET v:) bounded by +*²
Non Non-perturbed EFG average-iterate convergence. From Lemma E.2 and Lemma F.1 by taking argmax ENERE RRt, we have
R < Σ R4
hEH²
1 Mh +1/V((z)) (2(2))1 Σ || - -x (F.20)
< Σ
Sa(
2/
he 1-1
where the last inequality is by Lemma F22 and constant Mh is the maximum value of D (qh, gi in information set h. Therefore, by Lemma R3 the average iterate enjoys O +) convergence rate in terms of duality gap.
Perturbed EFG average-iterate convergence. By taking qr
& Ka(k)
where 2
argmax=e2: Σneue Ro(n) R4, from Lemma F.1 we have
R
Σ Zo(1) 1/j
NEW
Σ
2a(1))
( (N Arh + ([g) (=(x)))1?
(F211)
|| [1+ )
(M, 1|
Σ (o(
1 j.n -:- g.-g.a11?
2/
34

---

Published as a conference paper at ICLR 2023
where constant M is the maximum value of D (qh, 91,h) in information set h.
Follow the same analysis in F.2 we will get RT S O(1) which means the duality gap converges with convergence rate ( by Lemma
F3
F.4 APPROXIMATE EXTENSIVE-FORI PERFECT EQUILIBRIA
To illustrate why the NE of 2 for some fixed y > is a good approximation to the extensive-form perfect equilibria, we propose the following lemma.
Lemma F.4. The approximate NE x of a 7-perturbed EFG is an approximation of the EFPE in terms of duality gap. That is,
max F( ( (= - 2)
max F(=?) 2) y/2
(F.22)
2E
where z is an infinitely small perturbed treeplex whose NE exactly EFPE.
Proof. For any _0, we can define z' 2 as
4 (1 (1-7(9m(0)) (h(()) ((((()
+ 7.
(F:23)
Then, we will use induction to prove that || - 2o S yp. Note that we will use ane(i) == {i, (h(i)), a (M()) ...,t'} where o (N((z') = 0 to denote the set of ancestors of index i in the treeplex. Firstly, for index which satisfies that (h())) = 0, we have
II (11 (1-n/ShnnnD) +7)
M (/2 9: + + S 7/2 jEane(i)
II
(F.24)
jEane(i)
Then, assume that we already prove that ([]aane(o(((())) (a1 >1Rnn))Des + 7)
II (E)) Ør I (Cr(b(()) for an index where Co(k(o) = = (EEnn((((((O) [S(ce)). then
II ((1 (1- (11-)/9mm))))s + +7)
II qj jEanc(i)
jEanc(t)
2 (11 - 710000))) + +7)
II (E(nc(((h(O))
- (C II
jEene(s)
= --1lnt
II
4 +
II --(Ca(M()) (11 -11- (11))2200))) + +7)
jEane(i)
jEanc(i)
2 (1 + Co(n(o))
and similarly, we have the upperbound 7(1 + Co(h(o))) Therefore, we have | 2/ SpP.
Therefore, for y argmax geyo Deyo TT Aÿ where z" = ())) is approximate NE in 7- perturbed EFG, we have
TT Ay = A r + (y -2)
=T Ay' TT A(y -y')
(F.25)
< max TT Ağ + ||A x [1 y Pm
which implies that
max F(2?) 2) 28
max F(2T)T((2 (27 2) >1>T>>11 11 --1loo + AlA 1| 2'1lo0 SE
max EE
(x -2) 7p2
where the last inequality comes from [(z)]lbo & for any Z.
35

---

Published as a conference paper at ICLR 2023
F.5 PROPERTIES OF Req-DS-OptMl 4.2
We first prove some standard results in DS- DS-OptMD Hsieh et al. 2021) when adding regularization. Lemma F.S. For any convex set C and uo, E C, consider the update rule
U1 argmin (ū1.g g v (u)) D1 ge (ū1, u) + (22 D1) (ū1, un)}
RjEC
where jf is strongly convex function in C. Then for any u2 C,
TV/ (u1) - (u)) + (g. u1 - -22)
SA1((1 ) (uz, u) Dude (uz2, u1) - -
D -D
(F.26)
A1
+ +A2 (D (uz, - Duc (u22, u1) - Dyc uo)))
Proof. Since
g ( (9- A1 1 (w) -A)V 01 + (ar((rn) (F:27)
u1 = argmin
X1
by first-order optimality condition,
g V2 - (1 - (p) -(22 (1) (u2 u2) 2 0.
(F.28)
A1
Notice that
A1((1 21
I D (u2, u) Dio (1) ui) 1)) 1 ) (2)c(u,)))
Xi
(F.29)
(vol(u)) - -(1 Ve)e - 222 - U1 - (2)((22) + (u))
=A1
de
and
(D2 A1) be (u2, uo) Doie Ducc(ug u1) Dase (u1, un))
(F.30)
=(h2 A1) (V Vylc (2o), U2 - -u1)
Sum them up.
A1 - T D (u2, us) - Des (uz, u1) - -11- x1 D (ui,
T
X1
(A2 >1i (u22
(uz, uo) - D (21, (i12,1)) -Dye (2, un))
do ( A1
X, v (z)) - -Ox2 (n) u2 u1
(F31)
TV. (uz) + +
2 (g. u2) - T (uz) ) + (
where the last equation comes from Eq F.28)
Lemma F... Consider the update rule Eq 44.pp. For any information set h E H.2. gh. E A/2n1 and
t 1,2, ..., T. we have
tan v (q.+ - -an + (2 }), getg.n - -qi)
5(x - Tan) ua (gh - 1
D (gh, q(41n)) + (2% - ( (qh: q1.k)
(F.32)
(vM - (2, (=r-g), 1. 4+11h) N/1 D (gtt1,h: I0+g.1)
- -2 Ton) 1 (.
36

---

Published as a conference paper at ICLR 2023
Proof.
Plug U1 91+1, U2 9t+14: (z 21 xpc =a into Lemma C.4
Ta (
Tane (g++in) + (v
9 40+11)
<X (11
T0h (g:+1A
Dua ( 1,,, 10+2m1
Tath X/.
D (1++ J. (rah))
X
(F.33)
Plug 11 gc+1,h, U2 qr.g 1/ (2 ).d1 X/, A2 No N VC an a into Lemma F5
To o (qt+1,,) ( | (2 f): 91+1, 1-1111--111 -9h) 9/h)
<Ap(11 T0h Dii 9t,h) - D (q 9-+1,h) - (1 T0hh ) v ( (et+1, 9t,))
(F:34)
X
Xi
+ (A/+1
XD 9h, q1 Da (qh, 9411k) Dess (qt+1nh 91,1))
F.33) and Eq F.34 up, then adding ( (V - V (2 9c+ 9411.)
By summing Eq on both sides.
Tan (1+ 1.1h Tan - (qh) + V (z 9 -9hh
(2(44)
+ X2 (1
Tan
Des (g qt,b)) ( Dej (1 (9++1,199+++.) (11
Tah
Dris (q g(h)))
2/ Tai) (qh: Tc.h) Dua (qh: 10+1A) (1 -aak
2
+ X²((1
(9- 9t.h1))
(91-1,h1
Xp
A/
+ Mai (D (qh, 91 - Day (qn, q(+1,n) - Dea (g++1,ks q1,1.)
V (x(+3) ) - (2, 1): Ut+ 2.h - 9c+1,)
+ (2 - -Tax)
) مay (qh, 9(,h) No.1 D&A (gh, 9(+1,1) + (N/+1 DD (gh, 91.)) D ( (q 9e+ ( gc+g,h)
(X} -Tan Dan))pps (g t. qt,1).
By the two lemmas above, we can prove that the update of Reg-DS-OpiMD 4.2 is stable. Lemma F.7 (Stability of Reg-Ds-OptMin For any 1,2, ..., when r A is Euclidean norm, Reg-CFR satisfies that
Ci M
Ci X
q. 9.-4.m
quhll S
19 3.h qc.bll S
(F:35)
for some constant C1.
Proof. Consider the update rule Eq (4.2), by first-order optimality, for any H², we have
VV (z((z))) + X V (g..)) - (1 - A (>) v (q).))
9:-3.h - qth1) 20
(F.36)
(v"(zzg)) }) + x V (g. (gr - - qt. - -0-3.1) 20.
Add them up.
1/ V qq, ).1) - XV (q..)) + (2; - ((L (1- 9u.)) -
(F.37)
UMl (2(-4) V4 (2,- 4), 41 -1-1 9t.h
37

---

Published as a conference paper at ICLR 2023
Since A 1-strong convex with respect to 2-norm, we have
1
ب (q 2.n)) & (q.a))
V (qrn). 9t- -9t,h)
+
9:
1.h 4r.h
2
(F.38)
1
~ (qt,h)
v ( ).a)
V 9: 3.1,, qch - 9 -
+
9 2.1 q
2
Add them up then we will get,
V (qc (.hn (g,h).)) 90- -qrih 2 11q-- 3.1h -qr,all
(F.39)
Therefore.
M 11 1,4 - 1t.1l1 + (A - 1 ( (V (g),) - V 91- - -q.ii)
1/ (.1) - X (9 + (2 ( 9,0, - - 90.11)
(F.40)
(z( - V* (z ()= -1 4chh
(z=-g) v (z g)(l 111 11.1
And by definition,
S =
1 ( 2/
- (x, -)]])))l
(F.41)
so that
X 4 9t 1.4 qe,n < (I (g),)) (V) (z)-)))1-111-
(F.42)
which implies that
((1) X/_
1 1.. qr,al -
(F.43)
since V is bounded by constant when e is Euclidean norm. And [V"(==))) - (z
also bounded by constant since both the regularizer and [z)() are bounded. At the same time, directly from update rule Eq
+ V (qun), +22 Dus u (q a1,n) s (v + -V (V qthh
(F.44)
which implies that
X/
1 gr.nl2 S X1 D (1:4 (t.h) < ( V/ (2 (2 2
V (grn)) Arn ac+
(z, -V (q.,))l ||qr, - get
<0(1) |9r, - g
(F.45)
Hence, we have
19+ - qi,bll 0(1)
X
Proof of Lemmal F.2 By Lemma F.10
C
|| v² (z +)12 < (L2 Σ 11q+ -q-
p2 L3
(2 b
)2
hE#2
where the last inequality is by and Lemma F.7 and
Ci
1g+ 3.6 4: 1e-g.all $ |1q J.n ge.all + |1qe,
4, -.- 5
38

---

Published as a conference paper at ICLR 2023
Then, by letting T have
(1
(2
\ T
M th + Σ
2
t=2
P2 M
T
P213.9
T +
Σ
(1 1
(X
<0(1) V + T. T +0)
sO(T)),
which completes the proof.
F.6 AUXILIARY LEMMAS FOR Reg-CFR
In this section, we prove some auxiliary lemmas for Reg-CFR, We begin with the expanding form of the Bregman divergence generated by the dilated Euclidean norm.
Lemma F.8. When (q) = Σ, g. we have
(21, = Σ
an
21,h 22,
11 22)
Σ hEH
(1) Daa (qi,n, 92,1). (FA6)
2
21))(h)
EEM
Proof. Firstly, we can write 2 the form
zt Σ Ejernco 2j
(2) Σ (th(s)
(F.47)
(x)
then
will be
0z;
2
2%
2
an((i))
29:
Σ
q
(F.48)
Ozi
EjeRno Zj
Σ jEDncs) 23) 2
2
kE
kERx()
where 9: Sech(o))
And by the definition of Bregman divergence, we have
D (21, 22) = (211((x))))) - (z2) - 2
21 - 22)
ah((t)
21, 21,1(91.5 -242, + Σ (2
kE
(F.49)
(t((s)
22, - 292.5 +
Σ
(2
2
kEfA())
Notice that
292,i
Σ
(2,6)
Σ
21,1101, 292.i) Σ 21
Σ
42.k
2
kEBaco
ieh
kEDaCO
Σ
2,,o (0, -211, + 21.0(h(())
Σ
2
12.k
iE
kEDwC
Σ
(1,a - -2.1)²
iR
(F.50)
Similarly, we will get EiEn, 29, 242 EvEr ( 0. Therefore, D (z1, x2)
Σnenz 2 21,0 21.000) 22.0(h)
#1A
#2.1 12.
39

---

Published as a conference paper at ICLR 2023
Lipschitz continuity of (z) Here will show that V0 is Lipschitz continuous with respect to q. We first show that x is in a Lipschitz continuous manner with respect to q.
Lemma E99. In y perturbed treeplex 2" with y 2 0, for any 2, 2' E 2", we have
> 2'1
L1
Σ NER
1 4
(F.51)
for some game-dependent constant L1-
Proof. We first consider the base case when 27 is r-pertuutd simplex, where Eq F.51 is satisfied with L1 = since Q 2.
We consider the two basic operator, Cartesian product and branching, in the definition of treeplex (see Definition 2.1 details). We want to prove that both of them keep smoothness, that is, Eq
(F.TT) remains satisfied after applying the operation multiple treeplexes where Eq (F.T) is satis- fied.
Firstly, for Cartesian product if Eq
F.51 2
is satisfied for 27, 22 ..... 2 then for any z X x 2% we have
(z1, ø2, .... 2m); x = (zí: x22 .... z
E
= 2
x
2
z 2'11 S 2 211
1
Σ
1 L L1
Σ
qu - -kll..
(F.52)
im
hEM
Notice that abuse the notation 2 and H here to denote the set of all information sets in 2 and Z
To be convenient, let define the branching of m perturbbed treeplexes 2,, Z2 ....,
22....., 27, and 7- perturbed simplex A% be - = {(p P1 #1 #2 Pm Zm) p E 47 2; E 2 }. It's easy to see that it is equivalent to using the original branching operator for times in bottom-up manner.
Suppose for any Zi. x E 2, = - 2111 S Li EnEn=. |1
+ P.a.l- For z = (p.
Pm Zm), z'=
) = (p', .I 21 22222. zmm) E 2",
m
||z - 2'11 - Σ
l1: - p,2 + 1-p-pp-' -p'll
(F:53)
1=1
And we have
||:zz 11/2/11 = =1 p;z{) (piz) - (p:z1-r(z.) p324))
<lpp, x1)l + [ppp -1))=111
(F:54)
= || =/Il + lp; 1/1 -|=/||
<| = + |_7|. 1p-p'll
where the fourth inequality is by Z? C | Therefore,
(1 + P222 ... + Pm - (p/12) + 1/22/ ... + pm
||z
x111 +
|z," + 1)1pp-pi p'll
(=1
1=1
m
(F.55)
<
11 d'a'll + (P+ - p'l
1=1
2
< <max L1, Lg Lm, P P+13
Σ 1lqn
g
NER
where the third line is by the inductive assumption and the fourth line is by definition of 7 and q. Therefore, recursively applying Eq F.52 and Eq (F55)).
we will have for any z, z' E n
2'1l
L
Σ
Ig q''ll
(F.56)
hER
40

---

Published as a conference paper at ICLR 2023
where we take L1 P 1.
Finally, since both operator keeps the smoothness, by induction, we know that for any treeplex Eq F.51 is satisfied.
Now we can prove that (²) Lipschitz continuous with respect to q.
Lemma F.10. When شf is Lp-LLipschtz continuous, that is, (x))) of (x')l I Tp]lar arll for
any x' E A?, and ( (a)) is upper-bounded by constant C for any E A7, then for any
2, z' E 2 and h E H. we have
(=) S La
Σ | dill hEH
(F.57)
where L2 is game-dependent constant.
Proof. Here we consider h H and h E H- can be addressed similarly.
(z) (M
Σ
((A(y - +'1i+++ Σ
| (z) w (0))
MEH.
Σ
[18 y'111 + Σ
I (z) (ec) (w(()')))
(F.58)
x
NEH;
(Plly) s Σ
| (z) W (2'))
MEH.
where the second inequality is because each entry of A is in [-1, 1] and the last inequality is by ly 211l1 - vPlly y'll-
(²)z)= w'
((an. V²h (=)) + (qn)) ((dh. 1* (x'))
ran (
(gh. v* (z)) (dh, (2)) + Tax 1 (q:) (qh)
(qh. V4 (2) (=())) + (gh - tho v (x')
qn - 9hil
(F.59)
|g (z) (2)) + 1lqn d'lll (1 + 7 Lp
2/11l
(A(y 701++ Σ Σ |w (z) wh (z')
iE M MEW,
P(1 + 7 |||||
+ |gh q + =||a|| Lp 1gn qí ll-
Here (1) is by Hölder's inequality. (ii) is by |/ || = 1 and ||V*(=)|| < |lyl| + P I
P|llT| C.). By recursively applying this inequality, we have
[w*()) - (='))) A1y + P(1
Σ hERz
|| - dhill + +|
Σ
||gn d'll (F.60)
hEHz
Notice that
A - 1 S Plyy - y'll < p2lly y'll S I p2
Σ |/
A'll
(F.61)
heHz
where the first inequality is because A E [-1, MxN and the third incquality is by Lemma F9 Therefore,
MxN
41

---

Published as a conference paper at ICLR 2023
(x) - (=')
<P'L Σ 11 - + P CB)
Σ
q L +
+ Lp Σ
l1qn l
hE
NERZ
hEME
=L3
1 d II
(F.62)
where L3 = L1 + P(1 + T + +
+
And back to Eq FF58
have
[z) v* SCB PII 2111 + I.P.L. L3
Σ
1 -
NEH
SP(LiCn L3)
Σ
| q
(F.63)
hEM
=L2
Σ
11gh L l1:
where the second inequality comes from Lemma
F.
G CONCLUSIONS AND FUTURE WORK
In this paper, we investigate the regularization technique, widely used one in reinforcement learn- ing and optimization, in solving EFGs. Firstly, we prove that Reg-DOMD can achieve the first result of last-iterate convergence rate to the NE without the unique NE assumption, for dilated OMD-type algorithms with constant stepsizes, in terms of both duality gap and the distance to the set of NE. We further prove that by solving the regularized problem, CFR with Reg-DS-OptMD as regret mini- mizer, which called Reg-CFR, asymptotic last-iterate convergence in finding approximate extensive-form perfect equilibria. These results constitute the first last-iterate convergence results for CFR-type algorithms. Furthermore, have shown empirically that for CFR and CFR+, solving the regularized problem can achieve better last-iterate performance, further demonstrating the power regularization in solving EFGs. We leave it for future work to study its explicit convergence rate.
achieve best-iterate convergence result in finding NEs and
42


Reviews:
[{"review_id": "w11aRUE4UW", "reviewer": "Reviewer_M1He", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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": "", "summary_of_the_paper": "The paper analyzes EFG when a regularization term is inserted in the game setting and it comes up with the first last-iterate convergence results for CFR type algorithms, in contrast to existing results on the average iterate convergence. It provides new algorithms with considerably low complexity and proves rigorously their guarantees.", "summary_of_the_review": "Overall it seems a rigorous paper, but the focus is on Algorithmic Game Theory, without complete instantiation to Learning Theory (to my opinion) in order to make a clear impact there. A better fit might be SAGT or EC conference.", "strength_and_weaknesses": "S: The problem is well motivated, the paper is well written and the proofs seem ok from a first read.\n\nW: The impact of the paper as a 'Learning Representations' result needs to be more investigated. The impact on EFG seems to be there, but it is not sufficiently and explicitly linked to a Learning task. There are some experiments in the supplement, but they remain in the setting of a game, rather than Learning/Inference/Prediction. \nTherefore the results seemingly lie mainly in the area of Algorithmic GT, and the insertion of the regularizer is not shifting the study necessarily to Learning Theory (given the scope of ICLR).  \n\nW2: A 'discussion' section would be more illuminating at the end of the main paper. \nThe ending of the paper seems a little 'abrupt' in terms of summing up the achieved complexity.\n\nW3: In general, the goal of the main submission document is to discuss the theorems, like the authors are doing in page 7, and not emphasize the proofs if space is limited. For example Lemma 1 and Corollary 4.4. could be placed in the Supplement allowing for more discussion in its place. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pJPqh5ciy9S", "reviewer": "Reviewer_KrJP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study regularized extensive-form games (EFGs). They show that various algorithms achieve last-iterate convergence guarantees on such games. Then, the authors use the fact that for small amounts of regularization the solution to the regularized problem is also an approximate solution to the original problem. ", "summary_of_the_review": "Fundamentally, I think that this paper mistakes what the research community was trying to achieve by looking for last-iterate convergence guarantees. All the previous literature that the authors cite tries to show last-iterate convergence of OMWU, DOGD, DOMWU, etc, for various cases of bilinear saddle-point problems (matrix games, EFGs, etc). Indeed, there, it is an open problem how to deal with the issue of requiring uniqueness in order to get convergence when using entropy regularization. The authors do not provide a resolution to this problem though: the authors provide a *different* algorithm which yields last-iterate convergence by solving a regularized problem. This approach was already known to yield last-iterate guarantees (e.g. in Cen et al. 2021). OMWU and Reg-OMWU are not the same algorithm, yet the authors repeated conflate these algorithms in the abstract and introduction, thereby giving the misleading impression that they resolve an open problem.\n\nHere is an example of an incorrect claim:\n\n> we first show that dilated optimistic mirror\ndescent (DOMD), an efficient variant of OMD for solving EFGs, with adaptive\nregularization can achieve a fast Oe(1/T) last-iterate convergence in terms of duality gap without the uniqueness assumption of the Nash equilibrium (NE).\n\nThe authors show a quite different result: they show that last-iterate convergence occurs in a strong-convex-strongly-concave game, due to the fixed amount of regularization. It was known that such last-iterate guarantees are possible; the uniqueness assumption specifically is trying to deal with last-iterate convergence of the *standard* DOMD algorithm. We already knew from Nesterov smoothing (which should be cited! The authors cite the excessive gap technique paper, but not the original Nesterov smoothing paper) that you can add strong-convex regularization to a problem and get better guarantees. \n\nA minor note here, by the way, is that Wei et al already show last-iterate linear-rate convergence of OGDA in EFGs: their result is for any bilinear saddle-point problem with polyhedral decision sets. It's just that their result requires $\\ell_2$ as the regularizer, and thus does not allow dilated regularizers.\n\nGiven the present way that the paper is presented, I am leaning towards rejecting the paper, especially because the authors are already aware of these issues and chose not to address them in their revised paper (see ethics concern below). I will say that I actually think the results are pretty nice when viewed simply as results about a different algorithm, and they could arguably be accepted from that perspective. In that case, I would expect the discussion of the obtained results to be more in line with how Cen et al. present their results: they readily acknowledge that their results are on regularized problems, and thus are not directly comparable to the goal of showing last-iterate results for DOMWU/OMWU/etc.\n\nI do have a few questions for the authors:\n\n* Am I correct that in Theorem 3.2, the algorithm completely resets for every $\\epsilon$? In particular, if I wanted to get a particular level of precision, I would not actually run this restarting algorithm at all, but instead pick my desired $\\epsilon$ and simply start the algorithm at that $\\epsilon$?\n* For the second statement in Theorem 3.2, is this a property of regularizing with the entropy regularizer, or is it a specific property of Reg-DOMWU? In particular, suppose I solve the entropy-regularized problem with some other algorithm and obtain an iterate guarantee. Can your result be used to directly bound the iterate distance in the original problem? I don't really see why such a property should be specific to running DOMWU on the regularized problem.", "strength_and_weaknesses": "Strengths:\n\n* The authors provide a useful set of results around the performance of CFR/DOMWU/DOGDA on strongly-convex strongly-concave saddle EFGs. This is indeed useful work, and I think it deserves publishing.\n* The results on CFR seem particularly nice, and less similar to existing results by e.g. Cen et al.\n* The $1/t$ iterate convergence in Theorem 3.2 was surprising to me. It seems like a nice result. Unfortunately I was brought in as a last-minute reviewer and did not have time to verify this claim.\n\nWeaknesses:\n\n* The authors mischaracterize the existing literature and open problem on last-iterate convergence guarantees. It is not that surprising that one can get last-iterate guarantees without uniqueness when solving a regularized EFG. This is in some sense already known since the same thing occurs in NFGs, and strongly-convex strongly-concave saddle-point problems more generally. \n* The related work discussion is extremely limited in the body of the paper. Many ideas existed already, but those papers are either not cited or only discussed vaguely in the appendix. Nesterov smoothing and the excessive gap technique in particular stand out in this regard. Also, Cen et al. also showed quite similar results for NFGs, which somewhat makes the present paper overselling. I also feel strongly that there should be existing literature on last-iterate convergence in strongly-convex strongly-concave saddle-point problems more broadly, in the first-order methods literature.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NnRd3ry9EJ3", "reviewer": "Reviewer_D4YS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_paper": "The paper investigates the impact of regularization in solving extensive-form games (EFGs). It shows that after adding the regularization terms to different pay-off functions, several convergence  results could be achieved with either improved convergence rate or weaker assumptions. More specifically, for the dilated optimistic mirror descent, the regularized version can achieve a fast O(1/T ) last-iterate convergence in terms of duality gap without the uniqueness assumption of the Nash equilibrium (NE). For the counterfactual regret minimization, adding regularization term helps get the first last-iterate convergence results for CFR type algorithms.", "summary_of_the_review": "Overall I think the paper result is interesting and meaningful in further improving the state of the art works by add specific regularization terms. But it would be better to clearly build the connection between this work and the previous work in using the regularization term to really show that the effort is not trivial or incremental.", "strength_and_weaknesses": "Strength:\n  The paper shows the impact of adding specific regularization terms to different algorithms in solving extensive-form games, which either improves the convergence rate or has weaker assumptions than before.\n\nWeakness:\n   There has been some previous work like Cen et al. (Reg-OMWU) in exploring the usage of regularization term. Since it's in the same line of work (trying to get benefits by adding regularization), the paper did not explain if there is any connection between the results in this paper and the previous work results. More specifically, the most importance step to achieve all the results presented in the paper is to connect the regularized update back to the original un-regularized problem with iterate convergence. Although the work in Cen et al. is for NFGs, I am not quite sure if the extension to EFGs is incremental or challenging. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "M8q1ogEPcf", "reviewer": "Reviewer_r8KK", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper investigates the problem of learning a NE in two-players zero-sum games via no-regret algorithms. While most of the state-of-the-art algorithms guarantee convergence in terms of average strategies, existent methods that guarantee last-iterate convergence require strong assumptions like the uniqueness of the NE. In the present work, the authors provide regularization methods that allow to achieve last-iterate convergence without such assumptions. The first algorithm they propose is a regularized version of Online Mirror Descent that optimizes a strongly convex objective directly on the whole strategy polytope of the player. In the second part of the paper, the authors rely on the laminar regret decomposition to decompose the regret in additive terms at each information set to be minimized separately, claiming convergence of such method to a perfect equilibrium. The authors provide proofs of convergence with associated convergence rates. Finally, an experimental evaluation to support the theoretical claims is presented.", "summary_of_the_review": "Overall, the paper is well written, even though is quite hard to follow. The technical results are interesting, but not exceptional. I also have some concerns on a claim in the paper, namely that related to the coverage to EFPE.", "strength_and_weaknesses": "STRENGTHS\n\n1) The problem of designing last-iterate convergent no-regret algorithms is interesting and it is receiving a lot of attention from the literature.\n\n2) The paper is well written.\n\nWEAKNESSES\n\n1) The paper is hard to follow as it comes as a list of results, which are indeed related, but require the adoption of different perspectives and techniques, making the reader uncomfortable. \n\n2) Theorem 3.1 is rather straightforward to derive, since it directly follows from the results in [Cen et al. 2021b]. Am I right? The other results require a straightforward application of some well-known techniques, such as the laminar-regret decomposition by Farina et al. 2019.\n\n3) I have some concerns about the claim that the Reg-CFR algorithm converges to an EFPE. In particular, as far as I am concerned, the key technical result to prove this is Lemma F.3, but this only predicates on the duality gap. This should be related to the distance to a Nash equilibrium of the game, but it does not say anything about convergence to EFPE (since in zero-sum games all the Nash equilibria, including EFPEs, have the same value that is the value of the game). Am I right or am I missing something?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster