Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
Authors: Yang Cai
Gabriele Farina
Julien Grand-Clément
Christian Kroer
Chung-Wei Lee
Haipeng Luo
Weiqiang Zheng
Venue: ICLR 2025 Poster (2025)
Keywords: Last-Iterate Convergence
Minty solution
Regret Matching
Zero-Sum Game
Learning in Games
Primary area: learning theory

Abstract: We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret Matching$^+$ (RM$^+$). Despite their widespread use for solving real games, virtually nothing is known about their last-iterate convergence. A major obstacle to analyzing RM-type dynamics is that their regret operators lack Lipschitzness and (pseudo)monotonicity.
We start by showing numerically that several variants used in practice, such as RM$^+$, predictive RM$^+$ and alternating RM$^+$, all lack last-iterate convergence guarantees even on a simple $3\times 3$ matrix game.
We then prove that recent variants of these algorithms based on a smoothing technique, extragradient RM$^{+}$ and smooth Predictive RM$^+$,  enjoy asymptotic last-iterate convergence (without a rate), $1/\sqrt{t}$ best-iterate convergence, and when combined with restarting, linear-rate last-iterate convergence. Our analysis builds on a new characterization of the geometric structure of the limit points of our algorithms, marking a significant departure from most of the literature on last-iterate convergence. We believe that our analysis may be of independent interest and offers a fresh perspective for studying last-iterate convergence in algorithms based on non-monotone operators.

Published as a conference paper at ICLR 2025
LAST-ITERATE CONVERGENCE PROPERTIES OF REGRET MATCHING ALGORITHMS IN GAMES*
Yang Cai
Gabriele Farina
Julien Grand-Clément HEC Paris
Yale
MIT
yang.cai@yalee.co
gfari @farina@mit.com
seand-clemente ement hhec. fr grand-cl
Christian Kroer
Chung- Wein Lee USC Leechungeuse.com edu
Haipeng Luo
Columbia ck2945@columbia. edu
USC haipengl@usc. edu
Weiqiang Zheng
Yale weiqiang. zheng0yale.
ABSTRACT
We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret Matching* (RM+). Despite their widespread use for solving real games, virtually nothing is known about their last-iterate convergence. A major obstacle to analyzing RM-type dynamics is that their regret operators lack Lipschitzness and (oseudo)moootonie numerically that several variants used in practice, such RM+ predictive RM+ and alternating RM+, all lack last-iterate convergence guarantees even on a simple 3 3 matrix game. We then prove that recent variants of these algorithms based on a smoothing technique, extragradient RM* and smooth Predictive RM enjoy asymptotic last-iterate convergence (without rate), 1/Vi best-iterate convergence, and when combined with restarting, linear-rate last-iterate convergence. Our analysis builds on a new characterization the geometric structure the limit points of our algorithms, marking significant departure from most of the literature on last-iterate convergence. We believe that our analysis may be independent interest and offers fresh perspective for studying last-iterate convergence in algorithms based on non-monotone operators.
We start by showing
INTRODUCTION
Saddle-point optimization problems have attracted significant research interest with applications in generative adversarial networks (Goodfellow et al., 2020), imaging (Chambolle and Pock, 2011), market equilibrium (Kroer et al., 2019), and game-solving (Von Stengel, 1996). Matrix games provide an elementary saddle-point optimization setting, where the set decisions of each player simplex and the objective function is bilinear. Matrix games can be solved via self-play, where each player employs a regret minimizer, such online gradient descent ascent (GDA), multiplicative weight updates (MWU), or Regret Matching (RM+). A well-known folk theorem shows that the average of the strategies visited at all iterations converges to Nash equilibrium, at rate of O(IvVT) for GDA, MWU and RM and at a rate of O(1/T) for predictive variants of GDA and MWU (Syrgkanis et al., 2015; Rakhlin and Sridharan, 2013).
In recent years, there has been increasing interest the last-iterate convergence properties of algorithms for saddle-point problems (Daskalakis and Panageas, 2019; Golowich et al., 2020; Wei et al., 2021; Lee et al., 2021), There are multiple reasons for this. First, since no-regret learning is often viewed plausible method of real-world gameplay, it would be desirable to have the actual strategy iterates converge to an equilibrium, instead of only having the average converge. Secondly,
Authorrs listed in alphahetic order.

---

Published as a conference paper at ICLR 2025
suppose self-play via no-regret learning is being used to compute equilibrium. In that case, iterate averaging can often be cumbersome, especially when deep-learning components are involved in the learning approach, since it may not be possible to average the outputs of neural network. Thirdly, iterate averaging may be slower to converge since the convergence rate is limited by the extent to which early "bad" iterates are discounted in the average. Even in the simple matrix game setting, interesting questions arise when considering the last-iterate convergence properties of widely used algorithms. For instance, both GDA and MWU may diverge (Bailey and Piliouras, 2018; Cheung and Piliouras, 2019), whereas their predictive counterparts. Optimistic GDA (OGDA) (Daskalakis et al., 2018; Mertikopoulos et al., 2019; Wei et al., 2021) and Optimistic MWU (OMWU) (Daskalakis and Panageas, 2019 Lei et al., 2021) converge at linear rate under some assumptions on the matrix games. Furthermore, it has been demonstrated that OGDA and the Extragradient Algorithm (EG) have a last-iterate convergence rate of O(1/VT) without any assumptions on the game (Cai et al., 2022; Gorbunov al., 2022b).
On the other hand, very little is known about the last-iterate convergence properties of RM+ and its variants. This is in spite of the fact that RM+-based algorithms have been used in every case of solving extremely large-scale poker games (Bowling et al., 2015; Moravčík et al., 2017; Brown and Sandholm, 2018), one of the primary real-world instantiations of using learning dynamics to solve huge-scale zero-sum games. Poker games are modeled as extensive-form games (EFGS), a class of sequential games that capture imperfect information and stochasticity. RM+ is a regret minimizer for strategy sets that are probability simplexes, and thus is not directly applicable to EFGs. In order to apply in EFGs, is combined with counterfactual regret minimization (Zinkevich et al., 2007), which enables solving an EFG by instantiating simplex regret minimizers at every decision point. Despite its very strong empirical performance, the last-iterate behavior of any variant of RM is still not understood. It has been found empirically that the last-iterate in RM* combined with CFR (in alternating self play) may achieve better performance than the average iterate (Bowling et al., 2015), but on the other hand the last iterate may diverge even on rock papo-pp---scisoorss (Lee et al., 2021). Moreover, unlike OGDA and OMWU, the predictive variants of RM* do not enjoy a theoretical speed up: Predictive RM+ (PRM+), predictive variant of RM was introduced in Farina et al. (2021) and shown to achieve very good empirical performance in some games. However, still only guarantees 0(1/ (T) ergodic convergence for matrix games (unlike OGDA and OMWU). To address this, Farina et al. (2023) introduce variants of RM+ with O(1/T) ergodic convergence for matrix games, namely, Extragradient RM+ (ExRM+) and Smooth Predictive RM (SPRM+), and show that these algorithms also enjoy strong practical ergodic performance on matrix games.
Overall, while much is known about the last-iterate convergence properties of OGDA, OMWU, and EG, these algorithms are not widely used in real large-scale EFG applications, and very little is known about the last-iterate convergence of the RM+-based algorithms that are used in practice. As a first step toward understanding the last-iterate convergence properties of RM* algoorithsss EFGs, we study both theoretically and empirically the last-iterate behavior of RM+ and its variants for the special case of matrix games. Our main results are as follows.
1. Divergence of RM* We provide numerical evidence that RM+ and important variants of RM+ including alternating RM+ and PRM*, may fail to have asymptotic last-iterate convergence and best-iterate convergence. Conversely, we also prove that RM+ does have last-iterate convergence in very restrictive setting, where the matrix game admits a strict Nash equilibrium (Theorem 1)!
Asymptotic convergence under the Minty condition. Zero-sum game solving with RM+ can be seen solving a variational inequality with non-monotone operator, which we call the regret operator (see Equation (3)). This is a significant departure from the existing results, e.g., for the extragradient algorithm and optimistic gradient monotone games (Cai et al., 2022).
Technical Contribution:
We first show that ExRM and SPRM* exhibit asymptotic last-iterate convergence in the duality gap, enabled by our observation that the regret operator satisfies the Minty condition (see (6)), a condition strictly weaker than monotoiii.,,,,iiciiii. However, con- vergence in the duality gap is weaker than convergence in iterates, the usual form of convergence guarantee for monotone operators. An important benefit of convergence in iterates is that
games and proves its asymptotic convergence (without rate) to the unique equilibrium. Theorem I's proof largely follows from (Meng et al., 2023) with the key observation that the properties of strict NE suffices to adapt the analysis in (Meng et al., 2023) to zero-sum games (not boongllycoovee--tronngyyy
MMeng et al. (2023) studies RM* in strongly weareee-ttoogly-coneeee
games) with strict NE.
2

---

Published as a conference paper at ICLR 2025
ensures the stability of the dynamics, in the sense that the strategies asymptotically stop changing (see Section 4.1 for a detailed discussion). Although the Minty condition is a well-studied concept in variational inequalities (Kinderlehrer and Stampacchia, 2000), it does not generally imply last-iterate convergence in iterates. Nevertheless, we are able to show that both ExRM and SPRM exhibit asymptotic last-iterate convergence in iterates as well. Our proof relies new characterization of the geometric structure of the limit points of the learning dynamics, which may be of independent interest for analyzing last-iterate convergence in other algorithms.
3. Finite-time convergence. We then show a O(1 (1///))-a - for the duality gap for the best iterate after iterations of both algorithms. Building on this observation, we finally introduce new variants of ExRM* and SPRM* that restart whenever the distance between two consecutive iterates has been halved, and prove that they enjoy linear last-iterale convergence.
4. Experiments. We validate the last- convergence of ExRM* and SPRM* (including their restarted variants that we propose) numerically on four instances of matrix games, including Kuhn poker and Goofspiel. We also note that while vanilla RM+, alternating RM+, and PRM+ may not converge, alternating PRM+ exhibits surprisingly fast last-iterate convergence.
2 PRELIMINARIES ON REGRET MATCHING*
Notation. We write 0 for the vector with 0 on every component and 1. for the vector in IR with 1 on every component. We use the convention that 0/0 = (1/d)la- i the simplex: A fa e R4 (I,, 1a) 1). For E IR, we write [x]+ for the positive part of x [x]+ max x), and we overload this notation to vectors component-wise. We use || to denote the l norm.
In this paper, we study iterative algorithms for solving the following matrix game:
min max x AA #EA4 yEAd2
Ad x Ad2 to be the set of feasible pairs of strategies. The duality gap of a pair of feasible strategy (x, v) E Z is defined as DualityGap(z, y) ma x= Ay' een x' Ay. Note that we always have DualityGap(z: y) 2 0. and it is an e-Nash equilibrium of the matrix game (1). When both players of (1) employ regret minimizer, a well-known folk theorem shows that the averages of the iterates generated during self-play converge to a Nash equilibrium (NE) of the game (Freund and Schapire, 1999). This framework can be instantiated with any regret minimizers, for instance, online mirror descent, follow-the- regullaree leader, regret matching, and optimistic variants of these algorithms. We refer (Hazan et al., 2016) for an extensive review on regret minimization. From here on, we focus on solving (1) via Regret Matching* and its variants. To describe these algorithms, is useful define for a strategy the negative instantancous regret vector f(I e) = - r E 1a.² and the normalization operator g R$ x R + 2 such that
for a payaff matrix A E Id Ids, We define
well-known that DuplityGap(r, y) S e implies that the pair (x. y) E 2
A and a loss vector I e Rd.
9(2)
21
22
4 2 = (21, E R x R
||21
|| 11
Regret Matching* + (RM+) and its variants. We describe Regret Matching* (RM*) in Algo- rithm (Tammelin, 2014).² It maintains two sequences: a sequence of joint aggregate payoff's (RC, RC) E Rd IR updated using the instantaneous regret vector, and sequence of joint strate- gies (x (a',y") E directly normalized from the aggregate payoff. The update rules are stepsize-free and only perform closed-form operations (thresholding and rescaling). Predictive RM+ (PRM+, Algorithm 2) (Farina et al., 2021) incorporates predictions of the next losses faced by each player (using the most recent observed losses) when computing the strategies at each iteration, akin to predictive/optimisticc online mirror descent (Rakhlin and Sridharan, 2013: 3; Syrgkanis al., 2015). We describe two popular variants of RM+ and PRM+ Alternating RM+ (Tammelin et al., 2015; Burch
2 Here, can he either dj dz. That is, we overload the notation its domain depends on the inputs. 'Typically, RM* and PRM* are introduced as regret minimizers that return a sequence of decisions against any sequence of losses (Tammelin et al., 2015; Farina al., 2021). For conciseness, we directly present them as self-play algorithms for solving matrix games, as in Algorithm and Algorithm 2.
3

---

Published as a conference paper at ICLR 2025
al., 2019) and Alternating PRM in Appendix A. Using alternation, the updates between the two players are asynchronous, and at iteration f. the second player observes the choice x²+1 of the first player when choosing their own decision yt+!. Alternation leads to faster empirical performance for solving matrix and extensive-form games, even though the theoretical guarantees remain the same as for vanilla RM* (Burch al., 2019; Grand-Clément and Kroer, 2023).
Algorithm 1 Regret Matching" (RM+)
Algorithm 2 Predictive RM (PRM*)
1: Initialize: (Rg. R2) 0, (I ,00) E 2
1: Initialize: (R.. R2) 0, (ro, Vo) E Z
2: for = 0, 1... do
2: for t- = 0, 1,.... do
3: R+++1 R f(xt, Aw')|+
3: R[+1= [ f(x', Ay'))+
4: Ret1 = -[R + [y' , A x x²))
4: RØt = -IRy + [y', , x²)]+
5: geltl,y/t 2 R 1g
5: (x'*1, ,1th)) g( ((R - f(x', Ab")]+, [R]+]
f(y', +
Despite its strong empirical performance, it is unknown if alternating PRM+ enjoys ergodic con- vergence. In contrast, based on the aforementioned folk theorem and the regret guarantees of RM+ (Tammelin, 2014), alternating RM+ (Burch et al., 2019), and PRM* (Farina et al., 2021), the duality gap of the average strategy of all these algorithms goes down at a rate of O(1/ However, we will show in the next section that the iterates (x², yy") themselves may not converge. We also note that despite the connections between PRM+ and predictive online mirror descent, PRM+ does not achieve (1)/T) ergodic convergence, because of its lack of stability (Farina et al., 2023).
Extragradient RM+ + and Smooth Predictive RM+ We now describe two theoretically- faster variants of RM* + recently introduced in Farina et al. (2023). To provide a concise formulation, we first need some additional notation. First, we define the clipped positive orthant A := {u e R4: u 1a, 1} for 1,2 and Z A x A For a point E Zz. often write it as 2 (Rx, Qy) for positive real numbers R and Q such that (x, g(2). Moreover, we define the
operator F: 22- + RR as follows: for 2 E Bz, let (z. y) = g(2) and
[
f(z, Ay) s(u.-
1
Ay T Ay 14
F(2)
(3)
A x + TTTAp Ay 1d,]
Note that F is Lipschitz continuous over Z> with LF v6||A1l,, op max(d1, d2) (Farina et al., 2023).
show in Appendix B. This is because in the expression of F2)) as in (3), x and y are the l normalization of the first and second components of (see the definition of g as in (2)), and the function = - g(2) is badly behaved and may vary rapidly when Z E Rd + is close to the origin. We also write Ilz (w) for the projection onto ZΣ of the vector u: 2zz (u) arg min | 15--ul ul/2. With these notations, Extragradient RM+ (ExRM*) and Smooth PRM+ (SPRM+) are defined in Algorithm 3 and Algorithm 4.
but F is not Lipschitz continuous the larger set R +d
Algorithm 3 Extragradient RM+ (ExRM+)
Algorithm 4 Smooth PRM* (SPRM*)
1: Input: Step size 17 (0, ).
1: Input: Step size 7 E (0, s.
2: Initialize: 20 E Z
2: Initialize: 2 = ② E 2
3: for ( 0, 1.... do
3: for ( = 0, 1,.1... do
4: z -1+1/2 = 1I (a - ())))
4: z' === 11 Zy (w" (2(1))
5: gt+1 -11,, (2 (F(2++112)
5: w++1 I1 (w F((())
ExRM+ is connected to the Extragradient (EG) algorithm (Korpelevich, 1976) and SPRM+ is connected to the Optimistic Gradient (OG) algorithm (Popov, 1980; Rakhlin and Sridharan, 2013) (see Section 4 and Section 5 for details). Farina et al. (2023) show that ExRM and SPRM+ enjoy fast O convergence (for the average of the iterates) for solving matrix games, but since the regret operator F is not monotone, existing results for the convergence of EG and Optimistic Gradient on monotone games Cai et al. (2022) do not apply. and nothing is known about the last-iterate convergence properties of ExRM- and SPRM-..
4

---

Published as a conference paper at ICLR 2025
3 NON-CONVERGENCE OF RM* ALTERNATING RM AND PRM*
In this section, we show empirically that several existing variants of RM+ may not converge in iterates. Specifically, we numerically investigate four Segorithms-RMM alternating RM PRM and alternating PRM+-0n a simple 3 x game matrix A [3. 0, -3], [0, 3, -4], 00, 0, 1]l that has the unique Nash equilibrium (x* y² ([1 12a
2l. al.13. 5 4]). The same instance was also used
in (Farina al., 2023) to illustrate the instability of PRM and slow ergodic convergence of RM* and PRM The results are shown in Figure 1. We observe that for RM alternating RM and PRM the duality gap remains the order of 10 even after 10s iterations, which also suggests that these algorithms do not enjoy any best-iterate convergence properties. Our empirical findings are in line with Theorem 3 of Lee et al. (2021), who pointed out that RM diverges on the rock-paper-see game. In contrast, alternating PRM+ enjoys good last-iterate convergence properties on this instance. Overall, our empirical results suggest that RM* alternating RM* and PRM* all fail to converge in iterates, even when the game has a unique Nash equilibrium, a more regular and benign setting than the general case. To illustrate their non-converging properties, we provide the plots of the last iterates of RM+ alternating RM+ PRM+ after 102 iterations in Appendix C.
We complement our empirical non-convergence results by showing that RM* has asymptotic convergence under the re- strictive assumption that the game has a strict NE, To our knowledge, this is the first positive last-iterate convergence result related to RM In a striet NE (x".y"), ). x² is the unique best-response to y" and vice versa.
RM
alt. RM
PRM
alt. PRM
Duality gop
10
Theorem 1 (Convergence of RM+ to Strict NE). If a ma- trix game has strict Nash equilibrium (x* ,"", RM* (Algo- rithm 1) converges in last-iterate, that is, lim (xx y y²)} (x*, .)")
10-
10
10
10F
10a
10a
10
Number of iterations
The assumption of strict NE in Theorem cannot be weakened to the assumption of a unique, non-strict NE, as our empirical counterexample shows. Despite the isolated positive result given in Theorem 1 (under a very strong assumption that we do not expect to hold practice), the negative empirical results from Figure/ 1 paint bleak picture of the last-iterate conver- gence of unmodified regret-matching algorithms. This sets the stage for the rest of the paper, where will show unconditional last-iterate convergence of SPRM- and ExRM
Figure 1: Duality gap of the current iterates generated by RM PRM+, and their alternating variants on the zero-sum game with payoff matrix A == [[3, 0, 33. [0, -4), [0, 0, 1]]-
4 CONVERGENCE PROPERTIES OF EXRM+
In this section, we study ExRM+, an algorithm proposed by (Farina et al., 2023). Although ExRM lacks the no-regret property in the adversarial setting, understanding its performance is crucial due to its similarity to the important optimization algorithm EG. We show that ExRM+ exhibits favorable last-iterate properties. We start by showing convergence in duality gap, and strengthen the result to
convergence in iterates in Section 4.1. Then, Section 4.2. we provide concrete rate of O(1/VT) for the best iterate, based on which we finally show a linear last-iterate convergence rate using a restarting mechanism in Section 4.3. All omitted proofs for this section can be found in Appendix In Section 5, we study SPRM+ a regret minimizer in adversarial settings, and show similar results.
ExRM* (Algorithm 3) is equivalent to the Extragradient (EG) algorithm of Korpelevich (1976) for solving a variational inequality VI(Zz. F). For closed convex set S S RR" and an operator G S RR", the variational inequality problem VI(S, G) to find z E S, such that (G(=), 2 z²) < 0 for all z' E S. We denote SOL((S, G) the solution set of VI(S, G). For any solution of VI(2z, F), the strategy profile after É normalization (z, y) = g(x) is a Nash equilibrium of the matrix game A. The last-iterate properties of EG are known in several settings, including:
1. If G is Lipschitz and pseudo monotone with respect to the solution set SOL(S, G), i.e.
V z SOL(S, G), V 2 E S, (G(2), z 2²) 2 0
(4)
then iterates produced by EG converge to a solution of VI(S, G?) (Facchinei and Pang, 2003,
Ch. 12);
5

---

Published as a conference paper at ICLR 2025
2. If G' Lipschitz and monotone, i... V2, E (G(z) G ==)=0
(5)
then iterates {2'} produced by EG have 01 (17)) last-iterate convergence such that (G(z"), 2) v ( )1) for all z E S (Golowich et al., 2020; Gorbunov et al., 2022a; Cai et al., 2022).
Unfortunately, these results do not apply directly to our case: although the operator F (as defined in Equation (3)) is LtLLiscchizzcomtinuuu over Z>, it is not monotone even pseudo monotone with respect to (ZL(Zz, F), as we show in Appendix D. However, F satisfies the Minty condition:
3 2² E SOL(ZZ, F), V E Zz. (P'=), 2(66),-220
0.
(6)
The Minty condition is weaker than pseudo monotonicity (4) (note the different quantifiers and for 2* in the two conditions). We now show that F satisfies the Minty condition.
Lemma 1. For any Nash equilibrium 2* E 2. (F()), 2- - az*) 2 0 holds for all a 2 1.
We are now ready to show convergence duality gap for the iterates produced by EXRM which is weaker than convergence in iterates, studied in the next subsection. Our analysis follows from some results in Facchinei and Pang (2003), stated for the case of psendomonotonicity. but extending for the Minty condition.
Lemma 2 (Adapted from Lemma 12.1.10 in (Facchinei and Pang, 2003)). Let 2" E By be a point such that (F(=),= = >²) for all Zz. Let {='} be the sequence produced by ExRM Then
|| 201 ||2¹ - 101 2- (1 n7 11 211 V.
Lemma shows that the sequence {='} is bounded, so it has at least one limit point 1 E Z by compactness.* Using Lemma and minor modifications to the proof of Theorem 12.1.1 in Facchinei and Pang (2003), the next lemma shows that every limit point of {=t) lies in SOL(Zz, F) and thus induces a Nash equilibrium. Moreover, lim; || - - 0 and lim; oo (uulityGap(g(z")) =0.
Lemma 3. Let { be the iterates produced by ExRM*. Then the following holds:
1. lim -12--2+++)
2. If 2 is a limit point of {='), then 2 E SOL((2,F)
3. lim
As shown in Lemma 3, for an operator that only satisfies the Minty condition, classical analysis yields asymptotic convergence in duality gap.
4.1 CONVERGENCE OF THE ITERATES
Convergence in the Duality Gap Does Not Rule Out Cycling. Convergence in the duality gap only implies that the trajectory {2'} converges to the set of solutions but does not guarantee convergence in iterates, i.c., that lim,, z exists and is solution. Even when combined with the conditions lim;- ||2 - 2'+1l || = 0 and lim Duality (aaliitGaap(("))))
0 (Lemma 3), we cannot conclude that the trajectory {z' converges to single point. possible for the trajectory to cycle around the set of Nash equilibria without ever converging to single point. Specifically, these two conditions do not exclude the possibility that the per-iteration iteration movement ||a* 2f+1|| vanishes (c.g., at a rate < 1), while the total movement Σ
O !.) for some
|| diverges to infinity.
Geometric Structure of Limit Points To show the strong last-iterate convergence in the iterate property, we make new observations the structure of the solution set and provide characterizations of the learning dynamics' limit points. First, the sequence {2*} has at least one limit point & e SOL(Zz, F). If is the unique limit point, then {2t] converges to In the next proposition, we provide another condition on the limit point under which {2²} converges.
Proposition If the iterates {2'} produced by ExRM have a limit point 2 such that 2 = az" for z" Z and (equivalently, colinear with pair of strategies), then {2²} converges to 2.
'A limit point of sequence is the limit of one of its subsequences.

---

Published as a conference paper at ICLR 2025
However, the condition of Proposition I may not hold in general, and we empirically observe in experiments that it is not uncommon for the limit point = (Ré, Qû) to have R + Q. To proceed, we will use the observation that the only "bad" case that prevents us from proving convergence of {2t) is that {=*} has infinitely-many limit points (note that the number of solutions [SOL, (2,, F) is indeed
infinite). This is because if [="} has finite number of limit points, then since lim 1=(+1 2'1
o (Lemma 3), it must have a unique limit point (see a formal proof in Proposition 3). In the following, show that it is impossible that {=() has infinitely many limit points, we first prove a lemma showing the structure of limit points of {2*}. We illustrate this lemma in Figure 2.
Lemma 4 (Structure of Limit Points). Let } be the iterates produced by ExRM and z" E Ad x d be any Nash equilibrium of A. If 2 and are Iwo limit points of {=²), then the following holds.
all 1. laz =11 |aa= 2 for all a 2 1.
2. | 2 |
3. (2 8 2) O.
Proof. Let (A; }} be increasing sequence of indices such that {2*1} converges to 2 and (4 E 2} be an increasing sequence of indices such that {2²) converges to E. Let a : {k²} + {4} be a mapping that always maps
Figure 2: Pictorial il- lustration of Lemma 4.
k to a larger index in {4}. i.c. (k;) > kü- Such mapping clearly exists.
Since Lemma 2 applies a=* for any a 2 we get
|aa=" - -1 lim Jaz" - k1 11 N 50000
lim |az" - =o(k))) 12 = =1aa2= - E||?. +0000
12
By symmetry, the other direction also holds. Thus |laz" - =11 = |laz* - E1 for all a 2 Expanding ||a2* 2|| = ||a2" - ž| gives || || = 20 , 8- 2) for all a 2 1. It implies that ||=]|² || and (z", 2 E) = O.
We are now ready to show that } necessarily has unique limit point.
Lemma (Unique limit point). The sequence {=*} produced by ExRM+ has a unique limit point. Proof. For the sake of contradiction, let 2 = =RR Qū) and (Rã, Qÿ) be any two distinct limit points of { We first prove a key equality R + R = Q + Q by considering two cases.
. Case 1: 2 = ( (Rxx Qv') and ă = (Rx', ".::Q(')))))) for Nash equilibrium z' = vv") Part 2 of (Q2 -Q=- "1y Part 3 of Lemma 4 gives (2", 2 - E) = 0 + (i R) = (Q - 11 112. Combining the above two equalities with the fact that 2 # Σ, we get R + R Q=Q++
Lemma 4 gives || ||]|| * (iF2 - -
Case 2: 2 = (Rē, Q0) and ã (Ri, Q2) for different Nash equilibria (é., 9) and (i. 9). Since both (0. 0) and (ë. ÿ) are Nash equilibrium (Lemma 3), we have (λ. ÿ) also a Nash equilibrium by exchangeability of Nash equilibria in zero-sum games. By Lemma 4, we have the following equalities
1. | = |||| |=| ne [2] 22 101 @31101
2. 0 ((. ž) RR| - +Q101 Q(..9)
3. 0 = E -E) -) = R((2, a) [| +QQ 1) - -Q177
4. 0 = ((t, .).2
- --2 = R|| - -( -Q181
Combing the last three equalities gives
e : R|| R(a Ø) = R(ā .) - R| and -c= -(000) Q(0.0) - 2101
Further combining the first equality gives
( + R)c @ ()(-)
= - 2)) + R(R((a
- Q(Q 2101
'We draw =¹ in simplex only simplified illustration 2" should be from the Cartesian product of two simplices instead.
7

---

Published as a conference paper at ICLR 2025
-
c o O, then we get R+R = Q+Q. c = 0, then RR| RR(2, 2)²² and 001001 100 = QQ(0. 0)² gives the equality condition of Cauchy- Schharz inequality and we get 2 ãेt and + Q holds. This completes the proof of
This reduced to Case I where we know R +
R+ R = Q + Q.
Note that R+ - Q must hold for any two distinct limit points & and of {=¹). RR= Q, then 2 = R(2, ú) is colinear with a Nash equilibrium (ś, 9) and by Proposition 1, {2") converges to & and
2 is the unique limit point. If R + Q. argue that & and ă are the only two possible limit points. To see why, let us suppose that there exists another limit point 2 = (Rx, Qy) distinct from and ž.
R = R, then by R + R Q + Q. we know Q= Q. However, R + R = 2R * 2 - Q + Q gives
contradiction to the equality R2 + R
Q + Q we just proved. If R + It, then combing
R + Q + Q. R+ Q R+ R Q+Q
gives --Q--Q--=R-Q-
R. Thus, we have R = ② and it contradicts the assumption
that & Q. Now we conclude that {=') } has most two distinct limit points which means {2") has a unique limit point given the fact that {2²} is bounded and lim, || 2 =
Our main result now follows from Lemma and Lemma 5. To our knowledge, this is the first last- iterate convergence result for variational inequality problem satisfying only the Minty condition. Theorem (Lass-Iteraaee Convergence of Ex Let (=t) be the sequence produced by EXRM then {2"} converges to z" E 2z with g(=*) ) = (o",y") E A x A being a Nash equilibrium.
4.2 BEST-ITERATE CONVERGENCE RATE OF EXRM
We now prove an O( (T)) best-iterate convergence rate of ExRM+. The following key lemma relates the duality gap of a pair of strategies (a*+1, y and the distance || 2=11- Lemma 6. Let {2²} be iterates produced by ExRM* and (x'+), (x*+1,y(*1 g(2 Then QualityGap(=*t 1 12 121==*=-="11
Now combining Lemma and Lemma 6, conclude the following best-iterate convergence rate. Theorem 3. Let {2²} be the sequence produced by ExRM* with initial point z0 Then for any Nash equilibrium 2", any T 2 1, there exists t S T with "0","") = =g(z') and, for n V2LF'
DualityGaple .b') 2|Lr||s"-> /T
Proof. Fix NE 2* From Lemma Ei=o || 2¹12 such that || 1 2111
| This implies that 3 7-1
||-0-21|| 13
We then get the result by applying Lemma 6.
4.3 LINEAR LAST-ITERATE CONVERGENCE FOR EXRM+ WITH RESTARTS
In this section, based on the best-iterate convergence result from the last section, we further provide a simple restarting mechanism under which ExRM+ enjoys linear last-iterate convergence. To show this, we recall that zero-sum matrix games satisfy the following metric subregularity condition.
Proposition 2 (Metric Subregularity (Wei et al., 2021)). Let A Rd be a matrix game. There exists a constant e > 0 (only depending on A) such that for any = (I. E A x Ad, DaalityGap(z, y) c||= 1l2- [2]] where Z* denotes the set of all Nash equilibria.
Together with Theorem 3 (with V2LF we obtain that for any T 2 1, there exists 1 Duplity w²)
such that [1(2", 8²) 11z. [xx e'']ll <
< 24L
|| IIz [2"]]| This inequality
</T
further implies that i > 18 then there exists 5t T such that
1 |2"0 - 11 |=
- II [(0 "|
2
8

---

Published as a conference paper at ICLR 2025
Therefore, after at most a constant number of iterations (smaller than 48 2 ) the distance of the best- iterate 2²") to the equilibrium set 2* is halved compared to that of the initial point. If we could somehow identify this best iterate, then we just need to restart the algorithm with this best iterate the next initial strategy. Repeating this would then lead to a linear last-iterate convergence. The issue in this argument above is that cannot exactly identify the best iterate since [| y²) II [(x', y Ill unknown. However, we use || 3 2*11 as proxy, since
||<=", - 11 [( 3/))))) s/)ll - 1
DualityGap(a' ,') 12 + 1
S
C7
by Lemma 6. This motivates the design of Restarting ExRM+ (RS-EXRM*, Algorithm 5), which restarts for the k-th time || - 201 is less than O ). Importantly, RS-EXRM* does not require knowing the value of c, the constant in the metric subregularity condition, which can be hard to compute. The main result of this section is the following linear convergence rates of RS-EXRM*.
Algorithm 5 Restarting ExRM* (RS-ExRM*)
Algorithm 6 Restarting SPRM (RS-
1: Input: Step size 17 7 (0, p2000.0
1: Input: Step size 1 E (0, 12
2: Initialize: 2" E 2, k =
2: Initialize: 2 = w E 2, =
3: for 0, ... do
3: for ( 0, 1,...... do
4: 1/2 = II (2' - (2
4: x¹ ===10 2 (w² 1/F(=
5: 2tt1_ l1|, 12) 35-1/h (2
5: w 1I 3g (w² F2
6: if || - 2 < p/2² then
6:
if || - 2' 3'11 + l/wet - == < 8//2* then
7:
2(+1 +- g(z ++1 dd x d
7:
2 w + g(w't)) 1) E Adi x A
8:
k+
8: k
Theorem 4 (Linear Last-Iterate Convergence of RS-EXRM* ) Let {2²} be the sequence produced by 1 R with constant step size 17 and let L3 For any 2 1, the iterate (x*, v')
576 g(2") satisfies DualityGap(z", v²) S c c. (1 B) where a (L)
and B = 3 a1+a)
Proof sketch. Let la be the iteration where the k-th restart happens. From the restart condition and Lemma 6, at iteration tg. the duality gap of (z*x, y²*) and its distance to 2 is at most O 22 For iterate / E [4x, [x+1] at which the algorithm does not restart, we can use Theorem 3 to show that its performance is not much worse than that of (x'x, g²*). Then we prove tx+1 f4 is upper bounded by a constant for every k which leads to a linear last-iterate convergence rate for all iterations > 1. O
5 LAST-ITERATE CONVERGENCE OF SPRM+
In this section we study SPRM+ (Algorithm 4), an important variant of RM+ based on OG. For the sake of conciseness, we only state the main results here. The proofs are presented in Appendix G. Theorem 5 (Asymptotic Last-Iterate Convergence of SPRM*). Let {w') } and {2'} be the sequences produced by SPRM*, then {w²} and {z'} are bounded and both converge to z" E Z with g(=*)= = (x*, "e,,"") ))) E Ad: x Adz being a Nush equilibrium of the matrix game A.
Theorem 6 (Best-Iterate Convergence Rate of SPRM+). Let {w²} and {2²} be the sequences produced by SPRM For any Nash equilibrium z², any T 2 1, there exists 1 < t,,' < T such that the iterate g(w").g(2") Ad x Ad satisfy DualityGap(g(u")) < 10
/T and
Duality Gatittyap((((=))) < 18]
VT
We upply the idea of restarting to SPRM* to design new algorithm called Restarting SPRM (RS- SPRM see Algorithm 6) with provable linear last-iterate convergence.
Theorem 7 (Linear Ltst-Iterate Convergence of RSS-PPRM+) ). Let {w*) and {2¹} be the sequences 400. and 3 3[+aa. For t 2 1, the ल²タ
produced by RS-SPRM+ with constant step size n. Let a
iterates g(w"), ), (=²)) E Z satisfy QualityGap(g(ui S c- a (1 - 33 and DupliyGap(g(22)) S
2c a 8)

---

Published as a conference paper at ICLR 2025
RM
alt. RM
PRM
alt. PRM
EXRM
Smooth PRM
BG
0G
3x3 matrix game
Kuhn Poker
Gonfspicl
Random
Dunilly gap
10-
10-1
10
10-10
10a
10-
10a
104
16
10
10a
102
10f
10
10
10a
10
10
10
101
10a
10
10a
10P
Number of iterations
Figure 3: Empirical performances of several algorithms on the 3 matrix game (left plot), Kuhn
poker and Goofspiel (center plots), and random instances (right plot).
6 NUMERICAL EXPERIMENTS
The goal in this section is to verify numerically our theoretical findings from the previous sections, pertaining to the lack of convergence properties of RM+ PRM and to the convergence properties of ExRM and SPRM+ For the sake of completeness, we also show the performances of the extragradient algorithm (EG) and optimistic gradient descent (OG) Cai et al. (2022). We use the 3 x 3 matrix game instance from Section the normal-form representations of Kuhn poker and Goofspiel, as well as 25 random matrix games of size (d,, d2) = (10, 15) (for which we average the duality gaps across the instances and show the associated confidence intervals). More details on the games and on EG and OG can be found in Appendix H. For the algorithms requiring a stepsize (ExRM*. SPRM+ EG and OG), we choose the best stepsizes 1j E {1, 10-1 10 10-3, 10 10-4). We initialize all algorithms at ([Idd) )1d, (1/dg l.g). In every iteration, we plot the duality gap of for RM PRM and alternating PRM the duality gap of g(²") for ExRM the duality gap of ((=") for SPRM*; and the duality gap of 2 in EG and OG. The results are shown in Figure To avoid issues with numerical precisions, we set a lower threshold of 10-10 for the duality gaps displayed in all the figures in this paper, including Figure and the additional numerical results in the appendices. For the small matrix game, alternating PRM+ EXRM and SPRM achieve machine precision after 10s iterations (while other RM--ased algorithms stay around 10-1 as discussed earlier), slightly faster than EG and OG, On Kuhn poker, PRM+ and alternating PRM have faster convergence early, but later all algorithms perform on par (except RM*)). ). On Goofspiel, all algorithms (except RMM ) have comparable performance after 10 iterations, except EG which achieves machine precision. Finally, random instances, the last iterate performance of ExRM SPRM+, and EG vastly outperform RM-, PRM+ and alternating RM- but we note that alternating PRM+ outperforms all other algorithms. OG appears to be slow on these instances. We include additional experiments studying the best-iterate performances in Appendix They corroborate our theoretical findings of O(IvVT) best-iterate convergence rates for ExRM+ (Theorem 3) and SPRM + (Theorem 6).
Overall, these empirical results are consistent with, and validate, our theoretical findings of ExRM and SPRM* That said, understanding the good practical performance of alternating PRM (an algorithm for which neither ergodic nor last-iterate convergence guarantees are known) remains open. We also numerically investigate the impact of restarting for RS-EXRM+ and RS-SPRM (see Appendix H), where we note that both algorithms achieve linear last-iterate convergence (Theorem and 7) and are faster than their non non-restarting counterparts on some instances.
7 CONCLUSIONS
In this paper, we investigate the last-iterate convergence properties of regret-matching algorithms. class of popular methods for equilibrium computation in games. Despite these methods enjoying strong average performance practice, we show that, unfortunately, many practically might not converge. Motivated by these findings, we set out to investigate variants with provable last-iterate convergence, establishing suite of new results by using techniques from the literature on variational inequalities. For restarted variant of these algorithms, we were able to prove, for the first time for regret matching algorithms, linear last-iterate convergence rates. Several questions remain open, including giving concrete rates for (non-restarted) ExRM+, SPRM+, and alternating PRM Another open problem is understanding if our results extend to the case of solving EFGs with RM* via the CFR framework. However, analyzing RM+ behavior in the CFR setup is much more difficult because even in the two-player zero-sum case, the variational inequality characterization must be applied separately every decision point.
variants
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Yang Cai was supported by the NSF Awards CCF-1942583 (CAREER) and CCF-2342642. Gabriele Farina supported by the NSF Award CCF-2443068 (CAREER). Julien Grand-Clément was supported by Hi! Paris and Agence Nationale de la Recherche (Grant 11-LABX-0047), Christian Kroer was supported by the Office of Naval Research awards N00014-22---2588 and N00014-23-1- 2374, and the National Science Foundation awards IIS ISS-2147361 and IIS-2238960. Haipeng Luo was supported by the National Science Foundation award IIS- 1943607. Weiqiang Zheng was supported by the NSF Awards CCF-1942583 (CAREER). CCF-2342642, and Research Fellowship from the Center for Algorithms, Data, and Market Design at Yale (CADMY).
REFERENCES
James Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 321-338, 2018.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' em poker is solved. Science, 347(6218):145-149, 2015.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424, 2018.
Neil Burch, Matej Moraveik, and Martin Schmid. Revisiting efr+ and alternating updates. Journal of Artificial Intelligence Research, 64:429 443, 2019.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1):120-1455 2011.
Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In Conference on Learning Theory, pages 807-834. PMLR, 2019.
Constantinos Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and con- strained min-max optimization. 10th Innovations in Theoretical Computer Science Conference (ITCS), 2019.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis. and Haoyang Zeng. Training gans with optimism. In International Conference on Learning Representations (ICLR), 2018.
Francisco Facchinei and Jong-Shi Pang. Finite-dimension variational inequalities and complemen- farity problems. Springer, 2003.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5363-5371, 2021.
Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, and Haipeng Luo. Re- gret matching+:(in) stability and fast convergence in games. In Annual Conference on Neural Information Processing Systems (NeurIPS). 2023.
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged itcrate in smooth convex-concave saddle point problems. Conference on Learning Theory (COLT), 2020.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, (3(11):139-144, 2020.
11

---

Published as a conference paper at ICLR 2025
Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In Inter- national Conference Artificial Intelligence and Statistics (AISTATS), pages 366-401 6664002. PMLR, 2022a.
Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. In Advances in Neural Information Processing Systems, 2022b.
Julien Grand-Clément and Christian Kroer. Solving optimization problems with blackwell approach- ability. Mathematics of Operations Research, 2023.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy, Nature, 585(7825):357 362, September 2020. doi: 10.1038//41586-000 2649-2644-2 URL https: /ooi org 1038 44188 020-0649-222222
Elad Hazan et Introduction to online convex optimization. Foundations and Trends@ in Optimiza- lion, 2(3-4):15-3325, 2016.
David Kinderlehrer and Guido Stampacchia. An introduction to variational inequalities and their applications. SIAM, 2000.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Christian Kroer, Alexander Peysakhovich, Eric Sodomka, and Nicolas E Stier-Moses. Computing large market equilibria using abstractions. In Proceedings of the 2019 ACM Conference Economics and Computation, pages 745-746, 2019.
H. W. Kuhn. A simplified two-person poker. In Contributions to the Theory of Games, volume 1 of Annals of Mathematies Studies, 24, pages 97-103, Princeton University Press, 1950.
Chung-Was Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. Advances in Neural Information Processing Systems, 34:14293-11305 2021.
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. International Conference Artificial Intelligence and Statistics, 2021.
Linjian Meng, Zhenxing Ge, Wenbin Li, Bo An, and Yang Gao. Efficient last-iterate convergence algorithms in solving games. arXiv preprint arXiv:2308. 2w...308..122... 2023.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle -oiete-pontttt problems: Going the extra (gradient) mile. In International Conference on Learning Representations (ICLR), 2019.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337)-508-511) 2017.
Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28:845-848, 1980.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 2013.
Sheldon M Ross. Goofspiel- the game of pure strategy. Journal of Applied Probability, 8(3): 621-625, 1971.
12

---

Published as a conference paper at ICLR 2025
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems (NeurIPS), 2015.
Oskari Tammelin. Solving large imperfect information games using cfr+ arXiv: 2014.
arXiv preprint
Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up up limit texas hold em. In fwunth-fourth international joint conference artificial intelligence, 2015.
Bernhard Von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220-244) 246, 1996.
Chen-Yi Yu Wei, Chung- Wei Lec, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In International Conference Learning Representations (ICLR), 2021.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. Advances in neural information processing systems, 20, 2007.
CONTENTS
Introduction
2 Preliminaries on Regret Matching
3 Non-convergence of RM*
alternating RM+, and PRM*
Convergence Properties of ExRM
4.1 Convergence of the Iterates
4.2 Best-Iterate Convergence Rate of ExRM
4.3
Linear Last-Iterate Convergence for ExRM with Restarts
8
5
Last-Iterate Convergence of SPRM*
6
Numerical Experiments
10
7 Conclusions
10
A Alternating variants of RM+
14
B Non-Lipschtizness of the regret operator F
14
C Diverging trajectories of RM+ alternating RM and Predictive RM+
14
D Useful Propositions
16
Proof of Theorem
17
13

---

Published as a conference paper at ICLR 2025
F Proofs for Section 4
18
F.1 Proofs for Section
18
F2 Proofs for Section 4.1
19
E3 Proofs for Section 4.2
19
F.4 Proofs for Section 4.3
21
G Proofs for Section
22
G.I
Asymptotic Convergence of SPRM
22
G.2 Best-Iterate Convergence of SPRM+
23
G.3 Linear convergence of RS-SPRM*.
24
H
Additional details on numerical experiments
26
H.1
Extragradient algorithm and optimistic gradient
26
H.2 Game instances
26
H.3 Experiments with restarting...
26
H.4 Experiments with best-iterate convergence
27
A ALTERNATING VARIANTS OF RM+
We describe the alternating variants of RM+ and Predictive RM in Algorithm and Algorithm 8.
Algorithm 8 AAternating Predictive RM* (alt. PRM+)
Algorithm 7 Alternating RM* (alt. RM*)
1: Initialize: (Ro, Rg) = O, (x. gd) E 2
1: Initialize: (Ro, RG) 0, (vo. Ho) 2 for / = 0 1..... do
2: for = 0,1,... do
3: R R
f(x )
3: Rt+1 [R f(x², Ay
4: xt+1 11+1
4: /²1 [R(--1 -fl't -f(a"_Ay')]
[Ab IA
[| 1 -[ust,Au9ttt
5: 1 [Ry + fly', A x(+
5: R = (Rg + fly", A ATx x==
6: y R--1
y H1
[R II
[[R +1(0" AA Taltt
B NON-LIPSCHTIZNESS OF THE REGRET OPERATOR F
Here, we show that the operator defined in (3) not L-Lipschitz continuous over R. 1241+td td2
for any
L > O. Take any point z E A di x A da and let : [[(()) F(z')] Note that by definition of F have F(a 2) F(2) for any a 0. Therefore, [[=)) F(a=')
F(z) F(z')]l
for
any a >> O. yet we can choose a > 0 small enough so that |az - a2'll = a||z 211l < c/LL, which
shows that cannot L-Lipschitz continuous, otherwise we would obtain [[((z)) F(az')) s
Tll az'll < which is contradiction.
C DIVERGING TRAJECTORIES OF RM+ ALTERNATING RM AND PREDICTIVE RM
In this section we plot the last 2000 iterations (out of 10y iterations) of RM alternating RM and Predictive RM+ for solving the matrix game from Figure 1. The results presented in Figure
14

---

Published as a conference paper at ICLR 2025
Figure and Figure 6. Since xa E A we only plot the first two components of o' and similarly for y E A3
RM +
0.15
0.46
0.44
0.10
X 0.42
0.05
0.40
0.00
0.38
0.025 0.050 0.075
0.100 0.125
0.30
0.32
0.34
0.36
X1
V2
(a) z-player.
(b) y-player.
Figure 4: Last 2000 iterates of Regret Matching* after 10 iterations for solving the matrix game from Figure 1.
aAlternating RM*
Alternating
0.125
0.46
0.100
0.44
0.075
0.42
0.050
0.40
0.025
0.38
0.00
0.05
0.10
0.30
0.32
0.34
0.36
V1
(a) player.
(b) y-player.
Figure 5: Last 2000 iterates of Alternating Regret Matching after 10 iterations for solving the matrix game from Figure 1.
Predictive RM
Predictive RM +
0.425
0.10
0.420
0.415
0.05
0.410
0.00
0.405
0.025
0.050
0.075
0.100
0.125
0.325
0.330
0.335
0.340
X1
V1
(a) z-player.
(b) y-player.
Figure 6: Last 2000 iterates of Predictive RM* after 10 iterations for solving the matrix game from
Figure 1.
15

---

Published as a conference paper at ICLR 2025
D USEFUL PROPOSITIONS
Lemma 7 (Solution to VI Corresponds to Nash Equilibrium). If= E SOL(Zz, F), then (z,y) g(z) is a Nash equilibrium of the matrix game A.
Proof. Since SOL(Z,, F) is solution, we have == ==11 (z- nf((2)] for any 1 0. Then by Lemma 11, DualityGap(g(2)) 0. This implies (z, g(z) Nash equilibrium.
In the following two lemmas, we show that the gradient operator of a matrix game is always monotone, whereas its regret operator (used in RM-type algorithm) is not monotone, or even pseudo monotone with respect to the solution set.
Lemma 8 (Gradient Operator is Monotone). For any matrix game A Rdixdo, its gradient operator Adh x A dR x Rds, defined as G(z) = [Ay. - A xi] for each (r, 4) E 2, is monotone.
Proof. For any two point (z, 3) and x' = , we have
(G(2) G(='), 2- - z²) = (xr x') Ay T A(y 1/) (x xz) T A(y 5/) = 0. Thus G is monotone over Z.
Lemma 9 (Regret Operator can be Non-Monotone). There exists a matrix game A E R Rdxxx Z- =1 x A + IR, defined as for each = (Rr, Qy) with
whose regrel operator
I A da
F(E) F( Qv)) [ f(z, Av) [f A x)
| - [-
Ay x Ay 1dj - + Au 1
monotone, or even pseudo monotone w.r. the solution set SOI F).
Proof. We consider matrix A [[3, 1), [4] whose unique Nash equilibrium is (x",y")
(11.0 (1,0T). We define
2 (a, 8) ((0. 10,01 1]::
:5")
Then have
(F(2) F(z'), =- 2/) =- 4 0.
Thus F is not monotone over Zz. Moreover, x' belongs to SOL(Zz, F') and
( - 0.
Thus F is not pseudo monotone with respect to the solution set SOL F). This also proves the
equivalent claim that not all solutions in 30L(2z, F) satisfies the Minty condition (6).
The of this section consists in the proof of Proposition 3.
Proposition 3. Let S C I. be compact convex set and {2* e S} be sequence of points in S such that lim ||2* 2++1 = 0, then one of the following true.
1. The sequence {=t) has infinite limit points.
2. The sequence {z*} has a unique limit point.
Proof. We denote a closed Euclidean ball in R as B(x, sake of contradiction, assume that neither of the conditions satisfied. This implies that the sequence {2*] has a finite number (2 2) of limit points. Then there exists and two distinct limit points é and & such that
-|] (8) For the
16

---

Published as a conference paper at ICLR 2025
1. || -2211 2
2. &1 is the only limit point of {20} within B(21,c/2) n S:
3. & is the only limit point of {=') within B(22, e/2) n.
Given that lim || - = 0, there exists T > such that for any t >> T, 1| - -1--1| S 5 Now since & and 8g are limit points of {z'}. there exists sub-sequences {2²x } and {20} that converges to 81 and 22, respectively. This means that there are infinite points from {2 } within B(&),e/4) S and infinite points from {*²} } within 3(22,c/4) n. However, for > T. there
must also be infinite points from {=*) within the region (B(2), B(3, c/4)) This implies
there exists another limit point within B n S and contradicts the assertion that & is the only limit point within (2,,, e/2) n.
E PROOF OF THEOREM 1
We remark that Theorem I's proof largely follows from (Meng et al., 2023) with the key observation that the properties of strict NE suffices to adapt the analysis in (Meng et al., 2023) to zero-sum games (not sereel--oooeex-stooggy--oooe
games) with strict NE.
Proof of Theorem 1. We will use an equivalent update rule of RM (Algorithm 1) proposed by Farina al. (2021): for all 2 0, zt+1 11 R d2 [= (z*)] where we use z' denote (R²,, J&l)) and F as defined in (3). The step size 17 > 0 only scales the z' vector and produces the same strategies (aat,") E Ad x A } as Algorithm 1. In the proof, we also use the following property of the operator F, which is weaker than Lipschitzness.
Claim 1 (Adapted from Lemma 5.7 in (Farina et al., 2023)). For matrix game A E Rdd xds, let L1 || v /ax(xd, d1, d2) with || == sup Au /1/lll/ u Rd, + 0}. Then for any
2, E R2 d it holds that [[F(z)) - F(z')l - [lll(()) g(2')ll-
For any 2 1, since: 1111 II
n1 d, - (F we have for any E d2
20
e - 211 10 1 - 1 S 0.
- - 1+1 ; - = S 3((2- - _ 2' - +) + (n)((=)) =- -111)
(7)
By three-pone point identity, we have
|| 2 2|2 = 1| - =|| + || - =012 + +2(2* - - ,2- ---23 2²)
< 2/"² - =ll - -11=-1-- =I1 + (( -- (1).
(by (7))
We define k9 argmin 1:2 || - kzz ||. With = = k2z², the above inequality is equivalent to
1| - x22²11 2 + 20
< 112¹ - 202 + 27 (x==(((())))))))))) (=²)),²)))))) - 1||2+11 - z012 + -F(E))
- FF()), - 211)
- (='), ),k²²*
(We use (F())) = =0)
< |1 - N''*1
212 112 + 2n F( 2²) + +|||{(>)) - =( + +2 (((2))(((
(-a2 + 2ab s b²) < $112* - k2201| + (F ) 2² + + , 3¹) - +1 + F(z'), k2z)).
-
Since xz = (x", vx* is a strict Nash equilibrium, by Lemma 10, there exists a constant e > 0 such that
2nx (22'))
2nk ((+t) Ay" (x+)² Agy) < -nnck ((x,, "u",, yy¹ - -2*
S < (x",""= ,y') - z11
17

---

Published as a conference paper at ICLR 2025
where in the last inequality, we use kf by definition. Thus, combining the above two inequalities gives
|| - 11="11² 2=)(F(=))
s $1 112"11 + 2n(F(="), + (v² 2nc) ) ==11?
Using definition of k and choosing < z we have 27cc 1 { > 0 and
La)l(" y²²) =* 1| S || - =-== +2 (== -11=
F(="); 21z(t1). - ketl 112 (n((==))(((())
Telescoping the above inequality for [1, 7) gives
(2nc - 1/ Σ (x)) - =11 || k222 (F(=)((()))))))))))))) 2²) to0
It implies that the sequence {(x', v²)) converges to 2², Moreover, it also gives a O best-iterate convergence rate with respect [1 (<x.8")) - ==1]². -')--=11''
/T
Lemma 10. If a matrix game A has strict Nash equilibrium (x", ,y"), then there exists constant c > O such that for any (I. y) E A x Ad2
x T Ay - (x*) Ay 2 cl (I, -x=","")1" y")]
Proof. Since (a",y") strict, also unique and pure Nash equilibrium, we denote the unit vector x² with it E [di]o and constant C₁ == maxizi e, Ay e,_ Ay >> O. Then, by definition, we have
x Ayy - (x¹) Ayy = Σ
(e]
Ay" c,. An))
in
2
Σ
x|i
Ci
Σ
2
+
Ci
(111 x(i²1)
EvE(a)) 2|1] 1)
2
i
2
4
2
2
+
C1 (1 x 2(11))
(afil E 10,
2
2
x
2
Similarly, denote ej- = x² with jr E [d2] and constant 62 = (x+) Ay maxx (x*)T Aej, we T
get (I*) "Ay" max (x+) Ay 2 1 y 1² Combining the two inequalities above and let
c= 1/2 min( have Ay (x*) Ay cll(,,v) (x* y1 for all (xc, v).
F PROOFS FOR SECTION 4
F.1 PROOFS FOR SECTION 4
Proof of Lemma 1. Let =* = (x*,y" E Ad: x A be a Nash equilibrium of the matrix game, For any z (Rx, Qy) Zz, using (F(z).2) and the definition of Nash equilibrium, have (F(z), az*) (F(z), az*) axx' Ay (x*) Ay) 2 0.
The proof of lemma 3 closely follows that of Theorem 12.1.11 in Facchinei and Pang (2003)
Proof of Lemma 3. From Lemma 2, we know
(1 - n2 13) Σ
1
21
< 1|:0 =² ==1
1=0
'Given a positive integer d, denote the (1,2..... d} by [d].
18

---

Published as a conference paper at ICLR 2025
Since 1 - L O, this implies
x+ - -z" x2/ =0.
lim +00
2
Using Proposition 4, we know that || - -/t+ || I <Irrl2 2-11- Thus
lim 1-000 ||
201
lim 20
++1
+ 3
+ | + =
lim (1+ nbF)) 1
2 - z/ 0.
& is the limit point of the subsequence {ar :t E k}. then we must have
lim z" = ((E))
By the definition of 2 & in Algorithm 3 and by the continuity of F and of the projection, we get
8 = lim (Ex))+o0
2+22= lim 1z [=' -)][=)]]] 12 - A(Er)-oc
This shows that & E SOL(22,
For the third claim, suppose for the sake of contradiction that the sequence (DualityGap(g==") does not converge to 0. Then we know that there exists a subsequence {2 i x} that converges to 2 and DualityGap(g(3)) > 0. But since é limit point of {=*), have (ZL, F)). Then g(2) is Nash equilibrium and DualityGap(g(3) 0. This gives contradiction and we conclude that lim Dualit)Gap(g(2")
F.2 PROOFS FOR SECTION 4.1
Proof of Proposition J. Denote by {=t subsequence of {='} that converges to é. By Lemma 1, the Minty condition holds for 1, so by Lemma {||= - {] is monotonically decreasing and
therefore converges. Since lim || - 2|| lime ||a² - 0, {2²} converges to
2.
Proof of Lemma 4. Let (k; E } be an increasing sequence of indices such that (z* converges to and {4 E 2 be an increasing sequence of indices such that {241 converges to Let : {k/} + {4) be a mapping that always maps k; to larger index in {4}. i.c. (kks k4. Such a mapping clearly exists. Since Lemma 2 applics to az" for any a 2 1, we get
|aa-" - = lim aa
ki ||
lim |az" - xx(()) = ||a2" - =112.
By symmetry, the other direction also holds. Thus |laz*- 21122 = 1la2 - E1| for all 2 1. 2212
Expanding ||a2* 21|² Ila=* 2 gives
|| - ||ا|| 2a(2", --)) 2)) Va 2 1.
implies that ||=] = || and (=* 2 - Σ) = 0.
F.3 PROOFS FOR SECTION 4.2
We will need the following lemma. Recall the normalization operator g R x R + Z such that
for 2 = (21, 22) E R4 x Idd we have g(z) = (z1/1 22 2122211) E Z.
Lemma 11. Let Ad A and 21, 22, 23 Z such that z3 II [2] - (22() Denote (wa, va) 9(2),, then
Eal + 11L 23 - 22 1)) - =|| 21|+1 +2) (||=1
DualityGap(zz, va) == max 33 Ay- d2 zEA41
min T Ays <
1
19

---

Published as a conference paper at ICLR 2025
Proof of Lemma 11. Let 2 argming x² Ays and ğ E argmax, 23 Ay. Then we have
max Ay min x Aya x
2z Aÿ T Ays
-F(((z)),
1 ((21 23 + () (22) - -) (21 - -)((22) 23, =z)))
x (21 + (F((()2)) - mF
(2g = =11 121 - nF (22))
[1 23 ll + npr 1| 22 ||] 23 - Ell
1
Moreover, we have
23 || < 1/ - =1|+11 1|=++==000 =|1 > |23 - =|| +
Combining the above two inequalities completes the proof.
We now show few useful properties of the iterates. Proposition 4. In the same setup of Lemma 2, for any t 1, the following holds.
21 - || =111; 1. || - lt S ||=l|=++
2. | =1'1 s (1
21 s 211 - =111/
Proof of Proposition 4. Using the update rule of ExRM+ and the non-expansiveness of the projection operator 11 [1 []] we have
243
$ 22 -n (2" -nF(z++)))
= = +)) f(>i) S npr 2 - 211
Using triangle inequality, we have
1 2' - 1 2
+ + 21 x=|55 s (1+ nLF) 2 ( -
We are now ready prove Lemma 6.
Proof of Lemma 6. Let 2* be any Nash equilibrium of the game. Since 211 II 12" F (2)+
applying Lemma 11 gives
(1 211l + + 11a 24 [|( 2*||+ 2
DualityGap(a+t1, (..ttaaptttttttt) <
21 2* [1][[12 - -2" +
(nLF S 1 and Proposition 4)
17
3|12+11 1
2z [1((120 2+1|
+ +2)
(Lemma 2)
r7
12 12 ++ - 21
<
(2 and 2* are both in the simplex A x da)
7
which finishes the proof.
20

---

7 Published as a conference paper at ICLR 2025
F.4 PROOFS FOR SECTION 4.3
Proof of Theorem 4. We note that RS-EXRM* always restarts in the first iteration since 1| 201 5 ===1-=11 S V1-12 Let 1 = t < t2 ... be the iterations where the algorithm restarts with VI-02
(ath (otk,y"*. Using Lemma 6 and the restart condition, we know that for any k 2 1,
DualityGap(a** (3*) < 12 - 2t
48
1
7V
1 17 L2p
2
||(x") - -I1--(1** n0th I]| - DualityGap(z* ytth
48
cnyy
LT
2F
Moreover, for any iterate & [ex + 1, 1x+1 - 1]. using Lemma 6, we get
12 12 2 21 12 1l ((x ydd I11
576
1
DualityGap(a', (z)
nV1 1/ T.
cn - 1})
2
Using metric subregularity (Proposition 2), we have for any iterate E [ea +
1,+11111-1111 - 11.
576
1
[|(=', ,'' IIz [(=', w
c
2
If we can prove f-+1 t is always bounded by a constant C 2 1, then to S C(k - 1) + Ck. Then for any 2 1, we have 2 &L and
576
576
576
[|(a", w²) - II [(x*, w -
2 (1 12,3
21 S
2 à $ ( (1
30
Bounding fA+1 ls If (x+1 - 4 = 1, then the claim holds. Now we assume lx+1 4 2 2.
Before restarting, the updates of æt for ts S tt tx+1 - 2 is just ExRM By Lemma 2, we know
4441-4
btt - 2²1²= 11 y²*) ITz [(*x, "('",,"*>]1 )11
1 - L2
It implies that there exists & E [1x, 1++1 2] such that
4 - 21|5 |1 y(t ) 11 (1x 2/ I||
48
VI VI- L2 tt+1 tx -I
cn1( - 122
/x++1 tx - 2h
On the other hand, since the algorithm does not restart in [lx, lx+1 - 2). we know for every E [Lx, 4e.1 - 2).
1 21
VI
L 24+11
Combining the above inequalities gives
482
(1 - 17² (Z,)) 22k+2
4+11 14 11 -1
21
I.
22h
16
482 /4
576
c2 (1
17-
Linear Last-Iterate Convergence
Combing all the above, we get for all f 2 1,
576
(1- 3(1 + أ
DualityGap(a' .1) 5 cn (1
576
|| ,/ - II [(0", (((",,"'') 2212 - 12²
576
1 (1- 3(1 + কলক دل
37u
This completes the proof.
21

---

Published as a conference paper at ICLR 2025
G PROOFS FOR SECTION 5
G.1 ASYMPTOTIC CONVERGENCE OF SPRM
In the following, will prove last-iterate convergence of SPRM+ (Algorithm 4). The proof follows the same idea as that of ExRM+ in previous sections. Applying standard analysis of OG, we have the following important lemma for SPRM*
Lemma 12 (Adapted from Lemma in (Wei et al., 2021)). Let z" E 2> be point such that (F(z), --=) 2 0 for all 2 Zz. Let {2r) and {w*} be the sequences produced by SPRM*. Then for every iteration t 2 0 it holds that
|| - 2" 2=12
1
w + - z²11 & |wo' - -=-1===1-- + +
- 11 (6((
15 16
- =11 -1
+ 1||u =²1))).
16
also implies for any t t2 O,
| - 2² + 1| - 2111 s 21|w0 -2
I| 2' + u 2
11 S
w - -2²1 2111.
Lemma 13. Let } and {w'} be the sequences produced by SPRM*, then
1. The sequences {w²} and {=²} are bounded and thus have at least one limit point.
2. If the sequence {w²} converges to E Σz, then the sequence {z/} also converges to w.
3. If d is a limit point of {w'}. then i SOL(Zz,F) and g( is a Nash equilibrium of the game.
Proof. By Lemma 12 and the fact that w = =-1 we know for any / 0,
1 | 2² 1| w00 1=1
+1 2" +
16
which implies the sequences {w"} } and { are bounded. Thus, both of them have at least one limit point. By Lemma 12, we have
15
w0'l
15
=112 + +1|w² - 2²11²) s 1w0 - ==11/+ 16 1/ 112
32
16
This implies
lim
|
w"
= 0,
lim 1| - =='ll =00-- 1=000
lim
| - x111 =
t0000
If é is the limit point of the subsequence {w" ;t E.). then we must have
lim w = w lim (bEx)++00
w.
(bEx)++00
By the definition of wh in SPRM+ and by the continuity of F and of the projection, we get i lim r+11_ ((xx)+t0
lim llz, [w* [F(2)]] 1l (w (
((E
This shows that d E SOL(Zz,F) F). By Lemma 11, we know g is a Nash equilibrium of the game.
Proposition 5. Let {2²} and {w'} be the sequences produced by SPRM+. If (w²) has limit point v such that út az* for 2* E Add x d and (equivalently, colinear with pair of strategies in the simplex), then {w²} converges to w.
Proof. By Lemma
know the MVI condition holds for w. Then by Lemma 12, {llw u|l2 1 lue - = } monotonitically decreasing and therefore converges. Let ve be the limit of the Te
sequence {w t E x). Using the fact that lim ||w - =11 = O, we know that {llw* - w| also converges and
lim I|w w|| 1-000
Iww x- 111
lim ||w" 0/ 1-000
lim |w' 0|| = 0 [(Ex))000
16
Thus, (w*) converges to ú.
22

---

Published as a conference paper at ICLR 2025
Lemma 14 (Structure of Limit Points). Let { and {w²} be the sequences produced by SPRM Let x" E A x A be any Nash equilibrium of A. If in and are two limit points of { {w" then the following holds.
1. laat 10 = ||a2 =6l² for all 2
2. ||@| ||0l|²
3. (2*, ú ( =0.
Proof. Let {k; 2} be an increasing sequence of indices such that {w" converges to d and {4 E 2} be an increasing sequence indices such that [wi1 converges to w. Let (ki + {4} be a mapping that always maps k; to larger index in {4i). i.e. o(k)) ki Such a mapping clearly exists. Since Lemma 12 applies to a2* for any a 2 and limy-+0o 1/20* zt = O, we get
|laz" u||2 = lim |a=* - 11
1
1|
+
-
16
lim aa= w w((
1|=
(kk))
x (k.) -
w
16
a2 1
By symmetry, the other direction also holds. Thus, |1a2 r²l lla= o01 for all 1.
Expanding ||az- - l|a=* - u5 gives
|| || 2a(=", - Va 2 1.
implies that || ||ا||| and (2*, ú
の) O.
With Lemma 12, Lemma 13, Proposition 5, and Lemma 14, by the same argument the proof for ExRM+ + in Lemma 5, we can prove that [w"} produced by SPRM has a unique limit point and thus converges, shown in the following lemma.
Lemma 15 (Uniqueness of Limit Point). The iterates {w*} produced by SPRM+ have unique limit point.
Thus, Theorem directly follows from Lemma 13 and Lemma 15.
G.2 BEST-ITERATE CONVERGENCE OF SPRM+
Lemma 16. Let {2t} and {w*) be the sequences produced by SPRM* (Algorithm 4). Then
1. (ualityGapgg(uttt) < 5(1l |+ 1²
2. DuplityGap(g(E")) < 9(1 =
Proof of Lemma 16. Since t11 =ITzy [wo ()((2)) by Lemma 11, we know for any 2* 2
DullityGap(o(uott1))) 5 (1/0011 will + nTT | 2 21I[[[ - =0 + 2)
(1 nLr (11wt 2t + 11 2* =11)([[w =*1
(1 (Lw) 211l || -
=11)0(100 - = +
17
5 5(1lw² 2' 211+ || - =01l)
23

---

Published as a conference paper at ICLR 2025
where in the second inequality we uuply ||0==1 - w'll < || - 2f1|| + ||w"" 2'11; in the third
inequality we use || 2011 I || | ==1l by Lemma 12; in the last inequality we use nLF S
and || 11 s 2 since w., x- E Adi x dd
Similarly, since x' 11 (w Ff 11, by Lemma 11, we know for any x" Z
DualityGaplg(z")
(1 - w'll + /DFFl=z - x D|ll2 - -z11 + 2)
19
(1 + 1,bF))) (1ke* - 2111 + 1100 - 2)- M11000 - 2*1| + 1100" - 2111 + 2)
7)
(1 + nLr ) - =111 + 1100 - -z- - -2-1 + +111/000 - -2*1| + 2)
9[[lw* - 2011 + 11:0² - ------11 111
where in the second inequality we apply ||= - ا S 1| - w0ll
+ I|leet -1-11 and || - x- <
||2 w²1 || + I|w² 2: in the third inequality we use 11 2²1 S w -2*1 and |wo 2
2/ 21| 201| by Lemma 12; in the last inequality we use nLF S and | ==* S 2 since
w", 2- E Adi x Ads
Proof of Theorem 6. Fix any Nash equilibrium 2¹ of the game. From Lemma 12, we know that
-2'1 (1wlt1- =01/2+ + 1| =²1²²
16
|| 2=1
15
This implies that there exists 0 S - such that || 211l +
llw0 2011 S
21| -='l
(we
vT
use a + bs 2(a2+ By applying Lemma 16, we then get
DualityGap(guutt)) +1) N 5[1lw² - 211 + || 11)
10 - =11
77
n/
Similarly, using Lemma 12 and the fact that wº =1 1 we know
T
T
(1ww* - =1122 + 1/00 - 11) S
(1/u² - 20 +
- - =1(]² S
16
1| - 211
15
1=
t=
This implies that there exists 0 S t S T such that I|w0" 201l + 11100 - ---=11 '11 -
2|| 0 =I"||
(we use
VT
+ b /2 + b2)). By applying Lemma 16, we then get
DualityCap(g(2')) < 9[Ilw* 2011 + I|w
18 o 2*11
S
77
nVT
G.3 LINEAR CONVERGENCE OF RS-SPRM*
Proof of Theorem 7. We note that Algorithm 6 always restarts in the first iteration = since =0 -0
|mlI
I|10 2 <
32 I 2=2 < 4 3.. We denote 1 = l2 <... ls <... 15
the iteration where Algorithm 6 restarts for the A-th time, i.c., the "If" condition holds. Then by Lemma 16, we know for every the w*t g( 2 = Ad A da and
DualityGap(w**) 5(1110 - 201-1|1 + |1 2 1 II)
40
<
1 2*
7
24

---

Published as a conference paper at ICLR 2025
and by metric subregularity (Proposition 2),
we have
I 1lzz [w** |]| - Duality DualityGap(g(ieg Gap(g(w"))
40
2
Then, for any iteration ty + +15 tx+1 - 1, using Lemma 12 and Lemma 16, we have 5(1lw' x' + |lw
DualityGap(g(ue))
(Lemma 16)
7
10|| 1l [w
(Lemma 12)
400
cn2² 22
Then again by metric subregularity, we also get [lg(ww)) 11 [gw")]] [t + 1, 1,t++1 1]. Similarly, for any iteration tu S S th+1 - 1, using Lemma 12 and Lemma 16, we have
400 for every E
2 2
9(Ilw* =11 + I| 11)
DualityGap(g(22)
(Lemma 16)
18 18/lw/ 112- [w-
(Lemma 12)
720
onj2 22
Then by metric subregularity, also get I19(2*) II ig(25)]ll
400
for every t E [t&, tx+1
1].
Bounding t641 ts Fix any h 2 1. If tx+1 t + 1, then we are good. Now we assume t--1 th
By Lemma 12, we know
f
Σ
[| =21/ + Il|e 2²133 10t
16
This implies that there exists [4x: 1a+1 -2) 2] such that
|| - ='1| + |w=" =111 S 211 1l [w**]]
80
Vha+1 bs
c122
/tet1 - 4
On the other hand, since Algorithm does not restart in [lx, lx+1 (4x (441 - 2).
2). we have for every /
| 2¹11 + Ilwu" - 21
2
Combining the above two inequalities, we get
400
tx 1 1
2212
Linear Last-Iterate Convergence Rates for any & 2 1, we have & 2 [ and
Define C = 1 +
400 24
2
1441
4. Then la S Ck and
400 2-L
400
t
400
DualittGaapg(u")) <
<
enp
3C
cn2
3(1 +
400 1
Using metric subregularity, we get for any / 12 1.
400
lla(w') - 11 [g(ww [)]l <
1
2212
3(1
400 o 7
Similarly, we have for any / 2 1
720
720
(aalityGap(p(()))) <
1
-1((2 - 11 1g(=
5 22
1
on7
3(1 + /
3 +
2
This completes the proof.
25

---

Published as a conference paper at ICLR 2025
H ADDITIONAL DETAILS ON NUMERICAL EXPERIMENTS
H. EXTRAGRADIENT ALGORITHM AND OPTIMISTIC GRADIENT
We describe the extragradient algorithm (EG) and optimistic gradient descent (OG) in Algorithm and Algorithm 10. Recall that the gradient operator gradient operator G' : Z Adi x da defined as (()) = (Ay, - x)) for 2 (z, y)-
R x R
Algorithm 9 Extragradient algorithm (EG)
Algorithm 10 Optimistic gradient descent (OG)
Input: Step size 1) O.
1: Input: Step size 1 >
2: Initialize: 2" E E
2: Initialize: = w
2
3: for t=r:=0 0, 1, ... do
3: for / = 0, 0,1 1.... do
4: 2/-1/2 = IT (= (='))
2² == ll (w' G (z
5: z ztt1 llz (z nG( (2t)12))
w++1 llz (w² ,TG(21))
H.2 GAME INSTANCES
Below we describe the extensive-form benchmark game instances we test in our experiments. These games are solved in their normal-form representation. For each game, we report the size of the payoff matrix in this representation. All the algorithms were coded with Python 3.8.8, and we ran our numerical experiments on a laptop with 2.2 GHz Intel Core i7 and GB of RAM. In this setup, he performance of each algorithm on the instances considered in this paper (see details below) can be computed in a few hours.
Kuhn poker Kuhn poker is a widely used benchmark game introduced by Kuhn (1950). At the beginning of the game, each player pays one chip to the pot, and each player is dealt single private card from deck containing three cards: jack, queen, and king. The first player can check or bet, i.e., putting an additional chip in the pot. Then, the second player can check or bet after the first player's check, or fold/call the first player's bet. After a bet of the second player, the first player still has to decide whether to fold to call the bet. At the showdown, the player with the highest card who has not folded wins all the chips in the pot.
The payoff matrix for Kuhn poker has dimension 27 64 and 690 nonzeros.
Goofspiel We use an innerfecttinooomatiinn variant of the standard benchmark game introduced by Ross (1971). We use 4-rank variant, that is, each player has hand cards with values {1, 2, 3, 4). A third stack of cards with values 2,, 3, 4] (in order) is placed on the table. At each turn, prize card revealed, and each player privately chooses one of his/her cards to bid. The players do not reveal the cards that they have selected. Rather, they show their cards determines which player has played the highest card and should receive the prize card as a result. In case of tie, the prize is split evenly among the winners. After 4 turns, all the prizes have been dealt out and the game terminates. The payoff of each player is computed as the sum of the values of the cards they won.
fair umpire, which
The payoff matrix for Goofspiel has dimension 72 x 7,808 and 562,176 nonzeros.
Random instances. We consider random matrices of size (10, 15). The coefficients of the matrices are normally distributed with mean 0 and variance 1 and are sampled using the numpy. random. norma function from the numpy Python package (Harris et al., 2020). In all figures, average the last-iterate duality gaps over the 25 random matrix instances, and also show the confidence intervals.
H.3 EXPERIMENTS WITH RESTARTING
In this section, we compare the last-iterate convergence performances of ExRM SPRM* and their restarting variants RS-EXRM+ and RS-SPRM+ introduced in Section 4.3 and Section 5. We
26

---

Published as a conference paper at ICLR 2025
present results when choosing stepsize 0.05 in Figure 7 and Figure 8. To better illustrate the linear convergence rate, we use semi-log plot in Figure 8 and plot reference line (1 - 0.002) The numerical results show that both RS-ExRM* and RS-SP RS-SPRM" have linear last-iterate convergence and confirm our theoretical results in Theorem and Theorem 7. Moreover, we also observe that restarting accelerates the convergence in these two examples.
EXRM
Smooth FRM
RS EXRM
Smooth FRM
pasts gatte
Jutn Poker
Goofspiel
101
Doaliy gop
10"
10"1
1077
10
10"
10
Number of itcrations
Figure 7: For stepsize 17 0.05, empirical performances of several algorithms our 3 matrix game (left plot), Kuhn Poker and Goofspiel (center plots) and on random instances (right plot).
ExRM
Smooth PRM
RS ES--EXRM*
RS-Smooth PRM
0.002)
3x3 matrix game
A random 10x15 matrix game
10a
10-2
10
Duality gap
10
10-a
10
10-11
10-10
10-14
10-12
500
1000
1500
2000
2500
4000
6000
8000
10000
Number iterations
Figure 8: The last-iterate convergence rate of ExRM+ and SPRM+ and their restarting variants RS-ExRM and RS-SPRM on the x 3 hard instance and random 10 x 15 matrix game. The step size is 7 0.05 for all algorithms. We also plot the line 0.002) for reference.
H.4 EXPERIMENTS WITH BEST-ITERATE CONVERGENCE
In this section compare the empirical performances of the best-iterate visited by the algorithms studied in this paper. For the sake of completeness we also show the best-iterate convergence of EG and OG. We present our results in Figure 9, where we also show the line associated with //VT for reference. The setup the same as for Figure in Section
27

---

Published as a conference paper at ICLR 2025
RM
alt. RM
PRM
+
alt. PRM
ExRM
Smooth PRM
---
BG
OG
1
3x3 matric game
Kuhn Polerr
Goofspiel
Random
10a
Duality gap
10
10
10"
10
10"
10-1
10
10-7
10-7
10-19
10
10
10"
10t
10
10:
10"
10
16
10a
10
10'
10
10
10
10-18
10
10
10
10"
10
iterations
Figure 9: Empirical best-iterate performances of several algorithms on the 3 x 3 matrix game (left plot), Kuhn poker and Goofspiel (center plots), and random instances (right plot).
28


Reviews:
[{"review_id": "UdIYvdWklf", "reviewer": "Reviewer_dd2U", "summary": "The authors study last-iterate convergence  for Regret Matching + (RM+) algorithm and its recent variants PRM+ (Predictive RM+), ExRM+ (Extragradient RM+) and Smooth Predictive RM+(SPRM+) in two-player zero-sum bimatrix games. They show asymptotic last-iterate convergence of these variants (linear last-iterate with restarts). They also show ($1/\\sqrt{t})$ best-iterate convergence.", "questions": "See Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper is generally well written .\n\n2) They show that RM+ and PRM+ have last-iterate convergence (asymptotically) only in the case of having a strict-NE and provide a numerical example that this assumption is necessary.\n\n3) Moving on to the smooth variants of RM+ introduced in [Farina et al., 2023], they show that the operators corresponding to these algorithms are non-monotone and satisfy only a weak condition known as the Minty condition.\n\n4) Furthermore, they provide structural analysis on the limit points of the dynamics and show last-iterate convergence and this can be extended with additional regularity assumptions (metric-subregularity) and with restarts to show linear last-iterate convergence as well.\n\nReferences:\nFarina, Gabriele, et al. \"Regret matching+:(in) stability and fast convergence in games.\" Advances in Neural Information Processing Systems 36 (2024).", "weaknesses": "1) Their paper is restricted to two-player zero-sum games (bimatrix) games. It would be great to get a clarity as to if these techniques can be extended for general convex-concave games? (And also for general convex sets).\n\n2) Is it possible to obtain asymptotic rates of convergence for the last-iterate analysis shown here?", "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": "", "extra_scores": {}}, {"review_id": "7EnBFDiZdL", "reviewer": "Reviewer_SVSD", "summary": "Learning algorithms for games is one of the fundamental research areas in algorithmic game theory. In this direction the authors of the paper study the (variants of) Regret Matching+ (RM+) algorithms in terms of last/best-iterate convergence.\n\nFirstly, the authors give instances that (variants of) the RM+ algorithm diverges for last/best-iterate convergence even if the Nash equilibrium of the game is unique, so quasi-strict NE. On the other hand, interestingly enough, if there is a unique Nash equilibrium that is strict, so pure NE, they give a Theorem that PM+ converges in last-iterate, but without giving any rate guarantee.   \n\nAfter this analyzing properties of the operator, they give last-iterate convergence and best-iterate convergence for the EXRM+ algorithm giving also convergence rate for the duality gap matching the state of the art O(1/sqrt{t}) for last-iterate algorithms. Similarly, they prove last/best-iterate convergence for the SPRM+ algorithm with same rate of convergence guarantee. Furthermore, they give, in my opinion a very interesting, variant of them that achieves linear last iterate convergence.\n\nFinally the authors give experiments to give evidence for their results.", "questions": "Do you have any insight about the rate of convergence of the result of the Theorem 1? I think this will be a good direction for future work.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "In my opinion I think that the problem of learning algorithms in games is one of the fundamental problems in algorithmic game theory. Thus, the contribution of this paper is significant since not only the authors give results for variants of the RM+ algorithm (a well-known algorithm), but also give nice and novel techniques and directions, such as the algorithms with the restart, that can potentially help the research to go further on the learning algorithms. All these along with the quality of the paper make it a nice piece of research work.", "weaknesses": "My only minor concern is that in Theorem 4 and 7 I think that η must be constant (not function of t) since β must be upper bounded by a constant strictly less than 1 in order to have linear (geometric/inverse exponential) convergence. Thus, I think, if I am correct, that this should be explicitly stated in the Theorems.", "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": "", "extra_scores": {}}, {"review_id": "S8Clk9G11b", "reviewer": "Reviewer_yK8z", "summary": "The paper studies the last iterate convergence of regret matching and its variant in two-player zero-sum games. The results show that RM+ and its predictive variants may not converge, but the extra gradient and optimistic gradient varients can converge.", "questions": "1. Can you elaborate on the motivation behind considering RM+ algorithm in NFGs? Why are they important in NFGs, given that there are convergence algorithms like EG/OG. \n2. How can the results be extended to EFGs?\n3. Is it possible to modify EXRM+ to be no regret? Is SPRM+ no regret? ( i believe OG is no regret, so does this extend to SPRM+?)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The last iterate convergence of RM algorithms is important and the nonconvergence results are new and interesting. The paper is well-written and the results are sound.", "weaknesses": "The main weakness i that RM+ and its variants are mainly applied in EFGs, and so is the paper introduced and motivated. However, the results in the paper only hold for normal-form games. It is hard to be convinced that the results can be extended to EFGs without major revisions, so the motivation to study RM+ in NFGs is insufficient. \n\nThe other major problem is that ExtraRM+ is not no-regret, this somewhat contradicts the purpose of regret-matching.", "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": "", "extra_scores": {}}, {"review_id": "4vbVJryMNi", "reviewer": "Reviewer_QZ5e", "summary": "This paper investigates the last-iterate convergence rate of RM+ algorithms. Firstly, they provide numerical evidence that RM+ and PRM+,may fail to have asymptotic last-iterate convergence and best-iterate convergence. Secondly, they prove that ExRM+ and SPRM+ exhibit asymptotic last-iterate convergence. Lastly, they prove an $O(1/T)$ best-iterate convergence for ExRM+ and SPRM+, and use this best-iterate convergence to introduce new variants of ExRM+ and SPRM+, which achieve linear last-iterate convergence.", "questions": "1. What is the exact difference between \"Convergence of the iterates\" and \"Convergence in the Duality Gap\"? What are the advantages of \"Convergence of the iterates\" compared to \"Convergence in the Duality Gap\"?\n\n2. Why does the first author in prior works use tangent residual to claim \"last-iterate convergence,\" while this paper distinguishes between \"Convergence of the iterates\" and \"Convergence in the Duality Gap\"?\n\n3. Is the claim in the conclusion about \"linear-rate convergence in iterates\" correct?\n\nIf the authors can address my concerns regarding the \"Convergence of the iterates,\" I would be willing to increase my score.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper was previously submitted to ICLR 2024. This paper investigates the convergence of RM+ algorithms, an important topic that has been missing in prior research. It offers valuable insights for future studies. To the best of my knowledge, this is the second paper to explore the convergence properties of RM+ algorithms.", "weaknesses": "1. Although this paper considers a different game from [Meng et al., 2023], its analysis of the convergence of RM+ largely depends on the analysis of the convergence of RM+ in [Meng et al., 2023]. More precisely, the proofs of RM+ convergence in this paper and in [Meng et al., 2023] are identical. The primary novelty of convergence results of RM+ of this paper relative to [Meng et al., 2023] lies in the properties of strict NE. Therefore, the authors should revise the introduction to remove the claim that [Meng et al., 2023] is \"incomparable to our matrix game setting\" and instead explicitly acknowledge that the convergence proof of RM+ of this paper largely depends on [Meng et al., 2023].\n\n2. The second, and most critical, weakness of this paper is the lack of clarity in its explanation of the convergence of the iterates.\n   - Convergence in the Duality Gap indicates that the iterates converge to the set of NE. For solving NE, this is sufficient, as the goal is merely to find one NE.\n   - The metric used in the first author's previous works about the  last-iterate convergence of OMD-based algorithms, Tangent Residual means the upper bound of Duality Gap. In other words, the convergence in the tangent residual means the convergence in the duality gap. Why the convergence in the tangent residual is this sufficient to claim the last-iterate convergence in the earlier works but not in this paper?\n   - In Section 7 Conclusions, the authors claim “linear-rate convergence in iterates.” However, the metric for linear-rate convergence is also the Duality Gap.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)