Last-Iterate Convergence of Smooth Regret Matching$^+$ Variants in Learning Nash Equilibria
Authors: Linjian Meng
Youzhi Zhang
Zhenxing Ge
Tianyu Ding
Shangdong Yang
Zheng Xu
Wenbin Li
Yang Gao
Venue: NeurIPS 2025 poster ()
Keywords: Regret Matching$^+$
Last-Iterate Convergence
Nash Equilibrium
Primary area: theory
TL;DR: We investigate last-iterate convergence of Regret Matching$^+$ variants in games satisfying the weak Minty variation inequality.

Abstract: Regret Matching$^+$ (RM$^+$) variants are widely used to build superhuman Poker AIs, yet few studies investigate their last-iterate convergence in learning a Nash equilibrium (NE). Although their last-iterate convergence is established for games satisfying the Minty Variational Inequality (MVI), no studies have demonstrated that these algorithms achieve such convergence in the broader class of games satisfying the weak MVI. A key challenge in proving last-iterate convergence for RM$^+$ variants in games satisfying the weak MVI is that even if the game's loss gradient satisfies the weak MVI, RM$^+$ variants operate on a transformed loss feedback which does not satisfy the weak MVI. To provide last-iterate convergence for RM$^+$ variants, we introduce a concise yet novel proof paradigm that involves: (i) transforming an RM$^+$ variant into an Online Mirror Descent (OMD) instance that updates within the original strategy space of the game to recover the weak MVI, and (ii) showing last-iterate convergence by proving the distance between accumulated regrets converges to zero via the recovered weak MVI of the feedback. Inspired by our proof paradigm, we propose Smooth Optimistic Gradient Based RM$^+$ (SOGRM$^+$) and show that it achieves last-iterate and finite-time best-iterate convergence in learning an NE of games satisfying the weak MVI, the weakest condition among all known RM$^+$ variants. Experiments show that SOGRM$^+$ significantly outperforms other algorithms. Our code is available at https://github.com/menglinjian/NeurIPS-2025-SOGRM.

Last-Iterate Convergence of Smooth Regret Matching Variants in Learning Nash Equilibria
Linjian Meng', Youzhi Zhang"!, Zhenxing Get, Tianyu Ding', Shangdong Yang". Zheng Xu', Wenbin Li", Yang Gao
National Key Laboratory for Novel Software Technology, Nanjing University 2 Centre for Artificial Intelligence and Robotics, Hong Kong Institute of Science & Innovation, CAS Microsoft Corporation
Jiangsu Key Laboratory of Big Data Security and Intelligent Processing, Nanjing
University of Posts and Telecommunications
menglinjian @ smail.nju..du..cm youtuuecnnoouhiiiiiiii youzhi. zhang @ cair-cas.org.hhh cas.org.hk, zhenxingge @ tianyuding @ microsoft.com, sdyang @njupt.edu.en, xuzhenges @ smail.nju. nju.edu.en,
liwenbin @ nju.edu.cn, gaoy @ @nju.edu.cn
Abstract
Regret Matching* (RM+) variants are widely used to build superhuman Poker AIs, yet few studies investigate their last-iterate convergence in learning Nash equilibrium (NE). Although their last-iterate convergence is established for games satisfying the Minty Variational Inequality (MVT), no studies have demonstrated that these algorithms achieve such convergence in the broader class of games satisfying the weak MVI. A key challenge in proving last-iterate convergence for RM* variants in games satisfying the weak MVI is that even if the game's s loss gradient satisfies the weak MVI, RM variants operate on a transformed loss feedback which does not satisfy the weak MVI. To provide last-iterate convergence for RM+ variants, we introduce a concise yet novel proof paradigm that involves: (i) transforming an RM* variant into Online Mirror Descent (OMD) instance that updates within the original strategy space of the game to recover the weak MVI, and (ii) showing last-iterate convergence by proving the distance between accumulated regrets converges to zero via the recovered weak MVI of the feedback. Inspired by our proof paradigm, we propose Smooth Optimistic Gradient Based RM (SOGRM*) and show that it achieves last-iterate and finite-time best-iterate convergence learning an NE of games satisfying the weak MVI, the weakest condition among all known RM variants. Experiments show that SOGRM+ significantly outperforms other algorithms. Our code is available https://githuu. com//nenglinjaa/Neerlrs SOGGM.
Introduction
Nash Equilibrium (NE) is fundamental concept in the field of game theory. Recent advancements in superhuman game AI, are largely attributed to NE learning [Bowling et al., 2015, Moravčík et al., 2017, Brown and Sandholm, 2018, 2019, Pérolat et al., 2022]. Despite these advancements, the most popular algorithms for learning an NE ME-no-regred algorithms, typically achieve only average-iterate convergence, Even in two-player zero-sum matrix games, they are prone divergence cyclic behavior [Bailey and Piliouras, 2018, Mertikopoulos et al., 2018b, Pérolat et al., 2021]. Average- iterate convergence requires strategy averaging, which poses significant challenges in large-scale games where function approximation is used to denote the strategy as a new function has to trained to represent the average strategy [Liu et al., 2023].
Corresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table I: Comparisons between the convergence results of ours and previous studies about RM variants. "2p0s Games", "SM", "SN", and "RS" refer to two-player zero-sum matrix games, strong monotonicity, strict NE, and restarting [Cai et al., 2025], respectively. Games with the MVI cover games with strong monotonicity and two-player zero-sum matrix games. Games with the weak MVI is a super set of games with the MVI. The notations "v" and "o" refer to last-iterate convergence and finite-time best-iterate convergence, respectively. Note that the finite-time best-iterate convergence serves as a basis for deriving the linear last-iterate convergence rate of Restarting SExRM and Restarting SPRM A detailed discussion is provided in Section 2. Notably, the convergence of "SExRM* & SPRM*" in Cai et al. [2025] for two-player zero-sum matrix games refers to convergence a specific point within the set of NEs. This is stronger notion than the convergence concept we adopt (which is also used in Cai et al. [2025] for games with the MVT), where the iterates guaranteed converge to the set of NEs. See details in Section 3.1.
Games with
2p0s Games with SN
2p0s Games
Games with MVI
Cames with Weak MVI
Algorithm
SM
Meng et al. [2023]
RM RM SEARM" & SPRM
V
Cai et al. (2025)
0
v 0
SEXRM" RS-SSPI SPRM
0
0
SEXRM* & SPRM SOGPRM
V
V
/ 0
0
Ours
V
5 0
4 0
1 0
To address the challenges related to averaging, numerous studies consider last-iterate convergence, ensuring iterates converge to NE [Mertikopouloss et al., 2018a, Daskalakis and Panageas, 2019, Tatarenko and Kamgarpour, 2020, Wei et al., 2021, Lee et al., 2021, Cen et al., 2021, Liu et al., 2023, Sokota et al., 2023, Abe al., 2022a.b, 2023, Pérolat al., 2021, 2022, Cai and Zheng, 2023]. These algorithms are based on Online Mirror Descent (OMD) or Follow the Regularized Leader (FTRL). Despite their theoretical appeal, Regret Matching* + (RM+) variants ['Tammelin, 2014, Bowling et al., 2015, Farina et al., 2021, 2023], are more commonly utilized in solving real-world games, as evidenced by their success in superhuman Poker AIs [Bowling et al., 2015, Moravčík al., 2017, Brown and Sandholm, 2018J. The key distinction between RM* variants and FTRL/OMD-based algorithms is that the former updates within the (subset of the) cone of the original strategy space of the game, whereas the latter updates within the original strategy space of the game itself.
Unfortunately, few studies investigate last-iterate convergence of RM variants. The results on last- iterate convergence of RMM variants are restricted to games satisfying strong monotonicity [Meng al., 2023] or broader class of games-those satisfying the Minty Variation Inequality (MVI) (Cai et al., 2025]. Games satisfying the MVT cover several common game types, such as two-player zero-sum matrix games and convex-concave games, along with significant applications like the training of Large Language Models (LLM) [Munos et al., 2023, Wang et al., 2025]. Unfortunately. last-iterate convergence of RM* variants is not established in the broader class of games, such as those that satisfy the weak MVI [Diakonikolas, 2020, Cai and Zheng, 2022, Pethick et al., 2023, Cai et al., 2024]'. The weak MVI is weaker and covers more games than the MVI, including applications like Generative Adversarial Networks (GAN) [Cai and Zheng, 2022]. Therefore, a key question is
Do RM variants achieve last-iterate convergence in learning an NE of games satisfying the weak MVI?
The main challenge in proving last-iterate convergence of RM+ variants in games satisfying the weak MVI is that even if the game's loss gradient satisfies the weak MVI, RM+ variants operate on transformed feedback which does not satisfy Similar to Cai et al. [2025], we focus on smooth RM + variants [Farina et al., 2023], as other RM+ variants (e.g., RM+ [Tammelin, 2014], PRM [Faaina et al., 2021] IJ) diverge even in two-player zero-sum matrix games [Cai et al., 2025].
Contributions. (i) To prove last-iterate convergence for smooth RM+ variants, we introduce a novel proof paradigm: recovering the weak MVI by transforming a smooth RM+ variant into an OMD instance that updates within the original strategy space of the game", then showing last-iterate
'These works and ours, consider games satisfying the weak MVI with P (defined in Section 3) bounded below by negative constant. No prior work has investigated games satisfying the weak MVI with any P -c0. "This transformation is not the equivalence in Farina et al. [2021]. which transforms a RM* + variant into an OMD instance that updates within the cone of the original strategy space, rather than the original strategy space itself. In the OMD instance used in Farina et al. [2021]. the feedback does not satisfy the weak MVI.

---

convergence by proving the distance between accumulated regrets converges to zero via the recovered weak MVI. Our proof paradigm is inspired by the fact: for any smooth RM* variant, its feedback does not satisfy the weak MVI; however, in this corresponding OMD instance, the feedback is the loss gradient of the original games, satisfying the weak MVI, implying the weak MVT is recovered. By using the recovered weak MVI, we show that the distance of smooth RM+ variants to the set of NEs is related to the distance between accumulated regrets, and the latter distance converges to zero. (ii) To show the practical applicability of our proof paradigm, we utilize this paradigm to establish that two existing smooth RM* variants, Smooth Extra-gradient RM (SExRM*) ) and Smooth Predictive RM* (SPRM*), achieve last-iterate in learning an NE of games satisfying the MVI. (iii) Inspired by our proof paradigm, we propose Smooth Optimistic Gradient Based RM* (SOGRM**, ). which achieves last-iterate convergence in games satisfying the weak MVI. (iv) Experimental results show that SOGRM* significantly outperforms other algorithms.
(v) Our proof paradigm yields finite-time best-iterate convergence rates for SEXRM* SPRM and SOGRM* without any modifications.
2 Related Work
Our work primarily focuses on the last-iterate convergence of RM+ variants in learning an NE. Table shows the comparison between our work and the two most relevant literature [Meng et al., 2023, Cai et al., 2025]. (i) Our proof diverges significantly from theirs as they either analyze the dynamics of limit points [Cai et al., 2025] or use the strong monotonicity [Meng et al., 2023]. (ii) The last-iterate convergence results of Meng et al. [2023] and Cai et al. [2025] cannot be extended to games satisfying the weak MVI. Specifically, the results in Meng et al. [2023] need the strong monotonicity, which is a stronger assumption than the MVI (let alone the weak MVI). In addition, the algorithms in Cai et al. [2025], such as SEXRM* and SPRM* do not demonstrate last-iterate convergence in games satisfying the weak MVI. (iii) Cai et al. [2025] have to use another approach to prove the finite-time best-iterate convergence while we employ the same proof paradigm. (iv) The finite-time best-iterate convergence results of Cai et al. [2025] only hold in two-player zero-sum matrix games as their results depend on the definition of the duality gap of these games. In contrast, unite-time best-iterate convergence results hold in games satisfying the weak MVL.
Notably, we establish the finite-time, rather than asymptotic, best convergence rate for both SExRM + and SPRM+, which is very important for establishing the linear last-iterate convergence rate for smooth RM+ variants. Specifically, as shown in Cai et al. [2025], if either SEXRM+ or SPRM achieves the finite-time best-iterate convergence rate in game satisfying monotonicity and the metric subregularity [Wei et al., 2021]. then their RM+ variants employing the restarting: Restarting SExRM* or Restarting SPRM+. exhibit linear last-iterate convergence rate in that game. As mentioned above, we prove the finite-time best-iterate convergence rate of SEXRM* and SPRM+ in games satisfying the MVI, whereas Cai et al. [2025] establish this result only for two-player zero-sum matrix games. In other words, our results regarding the finite- time best-iterate convergence rate of SExRM* and SPRM* extend the linear last-iterate convergence rate of Restarting SExRM* and Restarting SPRM* from two-player zero-sum matrix games to games satisfying monotonicity and the metric subregularity. As we can directly apply the proof steps outlined in Cai et al. [2025] (their Appendix F.4 and G.3), we do not reproduce these details in this paper.
In this paper, we focus on smooth RM+ variants. Our proof paradigm transforms smooth RM+ variant into an OMD instance that updates within the original strategy space of the game. This contrasts with prior work [Liu et al., 2021], which transforms the vanilla RM+ [Tammelin, 2014] rather than a smooth RM+ variant into an OMD instance that updates within the original strategy space. More importantly, our equivalence (transformation) establishes both last-iterate and finite-time best-iterate convergence for smooth RM* variants. In contrast, Liu et al. [2021] fail to demonstrate average-iteral iterate convergence for RM+ by using their equivalence.
S the first RM+ + variant to achieve both last-iterate and finite-time best-iterate convergence in games satisfying the weak MVI. To achieve such convergences. it ensures that the weak MVI can be used after the weak MVI is recovered, which is not achievable by other smooth RM+ + variants. This arises as SOGRM+ performs one prox-mapping operator (defined in Section 3.2) per iteration, whereas other smooth RM+ variants execute two, as detailed in the second and third paragraphs of
"Monotonicity is a stronger assumption than the MVL, as the former guarantees Vx E X and x E X, (ee x - x²) 2 O, whereas the latter ensures 3x Xx, Ve E X, (L" x x²) 2 0 in the games considered in this paper. For more details, see Section 3.
3

---

Section 6. Notably, even with our proof paradigm, establishing these convergences for SOGRM significantly more challenging than for OMD-based algorithms, as discussed in Section 6. For the detailed comparison to Cai et al. [2025], see Appendix A. For the comparison between the convergence results of ours and previous studies about OMD variants in games satisfying the weak MVI, refer to Appendix B.
3 Preliminaries
3.1 Smooth Games
Smooth games. In this paper, we consider smooth games whose strategy space is simplex. We use a; E X; denote the strategy of player i and æ {æ:li E M) to represent the strategy profile, where X, is an (|-Ag] - 1) dimeessoo simplex A A|Ai and N is the set of players. The utility of player d all players follow strategy profile x is -00 < u, (z;, x x.;) < +00, where -i are the players other than i. For any i and the fixed - E X -. u; (3 x: x=-)) is concave function w.r.t. a; E X, Also,
ex = - u. ( x xx-))= -1) is loss gradient. In smooth games, || eed | ll2 S L x 1l2. Vx, x' X, where e" = [e E M1 and L > 0 is a constant. In addition, we assume ||e,T 111 I P for each a positive constant.
player i and strategy æ, where
Nash equilibrium (NE), In NE, for any player, her strategy is the best-response to the strategies of others. No player can benefit by unilaterally deviating from this equilibrium. The notation X denotes the set of NEs. As uz( x)-) is a concave function w.r.t. 2; E x, then Vx=" E X", x E X, the Stampacchia variational inequality (e," x x.) S 0 holds [Facchinei, 2003].
Last-iterate convergence. In this paper, this convergence refers to the behavior where the strategy profiles x' converge to the set of NEs X Note that Cai et al. [2025] define a stronger concept of convergence, known last-iterate convergence of the iterates. In contrast to last-iterate convergence discussed in our paper, last-iterate convergence of the iterates implies that x' converges to a specific point within the set of NEs. Our results and the results in Cai et al. [2025] for games satisfying the MVT do not pertain to last-iterate convergence of the iterates, whereas the results in Cai et al. [2025] regarding SEXRM+ and SPRM+ for two-player zero-sum games do.
Monotonicity, Smooth games with monotonicity are called smooth monotone games, which include many common and well-studied classes of games, such as two-player zero-sum matrix games and convex-concave games [Rosen, 1965]. The most important property of smooth monotone games is monotonicity - x - x') 2 0, Va, x' E X. Monotonicity is the most widely used assumption in existing works about last-iterate convergence. From the definition of the NE, in smooth monotone games, Vz E X" and æ E X, (8", x²) ) 2 O. We do not present the definition of strong monotonicity- stronger assumption than monotonicity-aat as few types of games satisfy it.
Minty variation inequality (MVI). implies that 3x E X", Vo E X, (LT x²) 2 O. Note that the MVI uses 3 rather than V. We provide an example of games that satisfy the weak MVI Appendix J.
weaker assumption than the monotonicity. The MVI
Weak MVL. Some recent works consider a weaker assumption than the MVI called the weak MVI [Diakonikolas, 2020, Cai and Zheng, 2022, Pethick et al., 2023, Cai et al., 2024], which covers more game types. Formally, the weak MVI with p S 0 implies there exists x" E X that ensures
(L0h 2, x²) 2 pl| _ + 2 Vz (Nx(x), E X,
where (x) E (v. x' x) < 0, Va E X is the normal cone of x. If -o0, intuitively, any smooth games satisfy the weak MVI. In Appendix J, we provide a smooth game that satisfies the weak MVI with 0 > p -oo and does not satisfy the MVI. The relations between monotonicity, the MVI, and the weak MVI, is that monotonicity S MVI C weak MVI.
Tangent residual. To measure the distance from a strategy profile to the set of NEs, we employ the tangent residual provided by Cai al. [2022]. Formally, Vx E X, its tangent residual
san (x) = min | + x =1|2-
#ENx(2> (z)
If tan = O, then & is an NE in smooth games. Also, if a is an NE smooth games, y.aa Therefore, lom paan (xx) 0 implies that x converges to the set of NEs. As shown in Cai et al. [2022], the tangent residual an upper bound for the duality gap, a conventional metric that quantifies the distance between strategy profile and the set of NEs (details are in Appendix L).

---

3.2 Regret Matching" and Smooth Regret Matching" Variants
Online convex optimization. Each player i selects a decision æ² via the feedback in this framework. Such feedback is the loss gradient e px¹ in solving smooth games. No-regret algorithms are the algorithms that ensure the regret RTT max EX, Et= (Lt, x -xs) to grow sublinearly, where of is the decision at iteration t.
Online mirror descent (OMD). OMD is traditional no-regret algorithm [Nemirovskij and Yudin, 1983]. Let g.):) : X; - IR, Vt 2 1, OMD generates the decisions via the prox-mapping operator
E arg min (L,,,;) + (z.)) + D ae (2), x!)}
(I)
a,EX,
where ()) ).)) 20 +.... (.), and De (æ. v) Di (x)) (g)
(Vg.t-11 (g) x y) is the Bregman divergence associated with (.). We employ the definition of OMD in Joulani et al. [2017] and Liu et al. [2021], which is a generalization of the standard OMD, to demonstrate the equivalence between smooth RM variants and OMD that updates within the original strategy space of the game. To recover the standard OMD, we can set of = o(-)/n and of for all Z 1, where ((-) is a I-strongly convex regularizer w.r.t some norm in the decision space X, and 7 > 0. The use of this specific OMD form in Eq. (1) is necessary as a RM+ variant can be transformed into an OMD instance that updates within the original strategy space of the game only when using the OMD of this form.
Blackwell approachability framework. RM+ variants are from this framework whose core insight lies in reframing the problem of regret minimization within the strategy space Z as regret minimiza- tion within cone 2) (>z = E Z, À 2 0} [Blackwell, 1956, Abernethy al., 2011, 1, Farina et al., 2021]. Specifically, lly, a regret minimization algorithm is instantiated in cone 2 where its output at iteration & is 0 This corresponds to the strategy z' 0 (' 1) within Z. Given the loss l at l' and subsequently generates 0++1 The pseudocode of all RM+ variants presented in this paper, e.g., SEXRM SPRM*. and SOGRM+, is in Appendix K.
iteration i, the algorithm observes the transformed loss - F = - x 1
Smooth RM+ variants [Farina et al., 2023]. These variants designed to address the instability of PRM+ [Farina et al., 202 1]. e.g., rapid fluctuations of the strategy æ, across iterations. To do that, Farina et al. [2023] enable the decision 0 in Rd instead of IR o in other RM+ variants to obtain the smoothness of the strategy Ø; w.r.t. O, (Lemma 5.4), where R {yly E Rd y 2 0, || 2 1}. We consider two existing smooth RM+ variants, Smooth Extra-gradien, RM+ (SExRM+) and Smooth Predictive RM+ (SPRM*). They algorithm grounded in Blackwell approachability framework. Specifically, they are respectively related to instances of two OMD variants, Optimistic Gradient Descent Ascent (OGDA) [Popov, 1980] and Extra-Gradient (EG) [Korpelevich, 1976], which updates within Rd
the subset of cone X;). The update rule of SEXRM* is
21
0 E arg min (iim((((((0)00))) 0.ER A4
1 Dw 0)),
++1
0
x.
110 110
0t+1 E arg mig ( (( - ( 0)), at
0 0
|10+111
17
and the update rule of SPRM+ is
0
of E arg min (in(((F(((0 (((((() + (0,. -
2+
x;
17
110,ta
(3)
0,+1 E arg minf(- ( 0,) + 1 D (0,, 03), 1+
0++1
|
0.ER|AI A.
where 7) >> 0 and vb(-) is the quadratic regularizer. Unlike RM+ smooth RM+ variants do not enjoy step size invariance [Chakrabarti et al., 2024]. However, empirical evidence demonstrates that RM* does not achieve last-iterate convergence in two-player zero-sum matrix games [Cai et al., 2025].
5

---

4 Our Proof Paradigm
We now introduce our proof paradigm. We only consider smooth RM+ variants, since other RM+ variants, e.g., RM+ and PRM are experimentally shown to diverge even in two-player zero-sum matrix games [Cai et al., 2025]. Our proof paradigm is inspired by this fact: for any smooth RM variant, its feedback does not satisfy the weak MVI; however, in its corresponding OMD instance that updates within the original strategy space of the games, the feedback is the loss gradient of the original games, satisfying the weak MVI. Specifically, our proof paradigm consists of two steps: (i) recovering the weak MVI by transforming smooth RM* + variant into an OMD instance that updates within the original strategy space of the games, and (ii) showing the last-iterate convergence by proving the distance between accumulated regrets converges to zero via the recovered weak MVI.
Phase 1. To recover the weak MVI of a smooth RM+ variant, we transform this smooth RM+ variant into an OMD instance that updates within the original strategy space of the game. To do that, is sufficient to show the equivalence between the update rule defined in Eq. (4) and (5):
2 E arg min! (- (-F)((0)), 0,) + - Db ),))}.
0,ER 1.
(4)
0
0
10:211 F(OO1) (
4 ) ex'
$10% 111
I E arg min ..)) + f(())) + DR, ( "/")), 2,EX.
|00²11 112 (xx)) ha:))) | lla (mne).
(5)
hn(m:)) + fi();)
17
7
where tu. t1, t2 refer to different iterations, 17 > 0. x. = 0 / lla. 6 with 0 E RR/ e is
the loss gradient of player induced by æ:1 -m=] 0:1 /|/00' E M.. and v)))) is the quadratic regularizer.
The intuitive explanation of this equivalence between the update rule defined in Eq. (4) and (5) is that both projecting onto the truncated positive orthant and projecting onto the simplex can be written in a unified way using the max operator, e.g., both update rules in Eq. (4) and Eq. (5) can be expressed as []+= = m=a(-,a 0). Due to page limits, the detailed proof is in Appendix C.
This equivalence is the inherent property of smooth RM+ variants and does not involve the game types. Notably, this equivalence not the equivalence Farina et al. [2021] as the OMD in Farina et al. [2021] updates within (on((X;)) rather than X the original strategy space of the game. The weak MVI is recovered as the feedback in Eq. (5) is the loss gradient of the original game that satisfies the weak MVI. Formally, for the feedback in Eq. (5), there exists an x² E X ensures that
(e*= + z, " x²) 2 plle"= + 2113, Vz E (x*x ) with le = (e E M.. as L is the loss gradient of the original game that satisfies the weak MVI.
Phase 2. The first step in this phase is: establishing relationship between the distance of the strategy profile induced by RM+ variants to the set of NES and the distance between accumulated regrets. Formally, from the first-order optimality of the prox-mi -mpppin operator in Eq. (5), Vzz E X4 we have
+ f(( + V ? Dr. (x/ la
100), x. - xx 20
12 h4 (m + li
V a h a. m3)) 2
KEN
0 to
g g
(6)
bo) 2 0 + -
(2x
7
8h 0 0²
+ y tan (x²²)
< ||ee
2
where x:- /|00/ ||1. the third line is from V a
hx( ++ V 2.2 f=(x())-0)-) /n and
V
/n, as well as the last line is from the definition of the tangent residual. Thus, if we prove ||ee= ft ||2 -> 0 and | - 0/0|/2 - O, we can get that plan (xa2)))) - 0, imply- ing x is an NE. For smooth RM+ variants, we have that - - 1121/ - 0 - 0²

---

which does not hold for other RM* variants, where E is the loss gradient of player induced by i E M. For smooth games satisfying the MVI, we show that for existing smooth RM+ variants, such as SEXRM* and SPRM+ | 0 ||2 -> 0 and | f I|2 -
x²² = [ = 0.2 /=0 1a
(indicating |0 0 222 - 0) as to - oc, implying that x²2 converges to the set of NEs, where t = fo + 1/2 and l2- = 41 + 1/2 (detailed in Eq. (22), (23), and (24)). For smooth games satisfying the weak MVI, we apply the recovered weak MVI to SOGRM* to get | 0'0+2112 ||2 - 0 as tu + oo, proving that x²²² converges to the set of NEs, where l2 = 4u + 1/2 (detailed in Eq. (11)).
Note that to can be any iteration f, while these convergence results hold only as to 00.
5 Application of Our Proof Paradigm: Convergence of SEXRM and SPRM*
To demonstrate the practical applicability of our paradigm, we employ it to establish both last-iterate and finite-time best-iterate convergence of two existing smooth RM variants, namely SExRM* and SPRM+ important to note that while Cai et al. [2025] provide last-iterate convergence guarantees for SExRM* and SPRM+ in learning an NE of games satisfying the MVI, they do not address the finite-time best-iterate convergence.
Theorem 5.1. SEXRM* with O < " < Dİ., or SPRM* with 0 < <π< < EDI., achieves the asymptotic last-iterate convergence and (122)) best-iterate convergence rate in learning an NE of games
+ 4L2. Specifically, p (xen(x++)) + 0 satisfying the MVI, where D = maxieN |Ail and L. = 22
and minrets) plan (xxT+t)))))) S 21))) as t + cc.
To prove Theorem 5.1, we introduce the Theorem 5.2, Theorem 5.3, and Lemma 5.4 (the proof of Theorems 5.2 and 5.3 are in Appendix E and F, respectively).
Theorem 5.2. SEXRM* with 0 < 17 < Tr. ensures 1100 1 - 00112 + 0 and 1 - 0²+ 1|2 + +0
as 1 - x., and minzet4] (10r+ 0- 11 + ||0 0 [1b S Ot)) 11 2 1.
Theorem 5.3. SPRM+ with <1 < EDI..
I ensures 10 - 00112 - 0 and |0 - 0²+ ||2 + 0
as 1 - x., and minretq (1 0r 11 + || - 0 [1b S { 14 2 1.
Lemma 5.4. (Proposition I in Farina et al. [2023]) Va, b E R ll a ||j||
b ll S vdlla bl12- [
Proof Sketch of Theorem 5.1. From the analysis in Section 4, for SEXRM+ and SPRM+, the tangent residual of the strategy profile x++1; is
$ 1l2 + 1 1100 - - 1 110
pan (x 1)
/LI(x +
1)
11
Then, using Lemma 5.4 with @i+1 and b = 0 1, we have
tan (2 +1 SLVD|I - 0 ||2 + _ 00 - g 1/2 + =1 - -0tt1 1/2
From Theorem 5.2 and 5.3 (ll0c - oc+ 1|2 + 0 and 1 0c+1112 + 0), we get plan plan(x)) (x²) + 0 as
t + co. Similarly, we get
(2 <2121100411 - x 1|2 +
2 0e r 1|
By using Lemma 5.4, we get
(r (x < 22 + 7/2
4
(10-11- 0c+ + 11 + 110 - or+ 112)
Thus, from Theorem 5.2 and 5.3 (min-efe (110=t)
0 + ||0 0 (11) < O(t)), we get
that for = arg min (1) | - 0 11 + || - r } 13)
tan (x: sy -110+t2-0011
1r + + -0+++-
s 10
For more details, see Appendix D.

---

6 Our Algorithm: SOGRM*
We prove that SExRM* and SPRM* achieve last-iterate convergence and finite-time best-iterate convergence in games satisfying the MVI. However, they do not achieve such convergences in games satisfying the weak MVI, covering games satisfying the MVI. Inspired by our paradigm, we propose a new smooth RM+ variant called Smooth Optimistic Gradient Based Regret Matching* (SOGRM )), which achieves last-iterate and finite-time best-iterate convergence in games satisfying the weak MVI.
The key insight of SOGRM* is to transform the term related to x' (an NE) to term that only depends on the gap between accumulated regrets across different iterations via the recovered weak MVI, which is pivotal for establishing last-iterate convergence. Specifically, it transforms the penultimate line of Eq. (6) from - + (0 023)/n E Nx to L" + (0 1/1) E eNx(2") by using the second line of Eq. (7) (e.g., 0 0 F b) ( (0)+))) enabling the derivation of - be any iteration t, 1 = to 1/2. and l2 = + 1/2. See details in Eq. (9), (10), (41) and (42).
- 2 + (0 000-001)))))))) 1/,, -/n)="=="' s-pl f // via the weak MVI, where to can
In contrast, for SEXRM+ and SPRM+, the second line of the update rule in SOGRM+ 0
0 (0t- + F corresponds prox-mapping operator (first mentioned in the (0,00)))/))))) Unfortunately, this
text around Eq. (I)): 0 +1 Eargmin Eargming, 0, (), update does not yield -²2 (0"o 0 goot))//Exx(("1)) enabling the weak MVI cannot be used.
Notably, the proof of SOGRM* needs additional techniques compared that of OMD-based algorithms, ie., transforming variables using the definition of the inner product to employ the weak MVI and tangent residual (details in Eq. (9), (10), (38), (39), (41), and (46)) rather than directly transforming variables using equalities as in OMD-based algorithms. The update rule of SOGRM iteration is
0.+
o E arg (( (0., 03), a ++ 0.ER|4 144
100
$
0. 0 0
F) + F.(+tt))))).
The intuition for the update step in Eq. (7) is: SOGRM*, can be viewed as a momentum- based method, conceptually similar to Adam. Specifically, the update in Eq. (7) is equivalent to 0 E arg min
0, (4:1 {( ((-F((0++)) (F)(0++))= F((0+=#)), 0.) + (O,, o(²²)) })}. In this context,
(((0++))- - F.(0-r) acts as a momentum term. More precisely, it represents the trend of change in F, over the two most recent iterations, analogous the "acceleration" of F,, This can be likened to ball rolling down a hill; as acceleration accumulates, its velocity increases, allowing to reach the bottom more swiftly.
S is smooth RM+ variant since operates within the R.A.A.1. the subset of cone(X;;, and updates by facing the adjusted loss vector F,(0") = (4, x/) instead of directly using C. The convergence results of SOGRM* are shown in Theorem 6.1.
Theorem 6.1. In smooth games satisfying the weak MVI with p > 12V3DL." there always exists an (O, =D...) satisfying 1/ + 2e D2 > 0 such that ensures SOGRM+ achieves the asymptotic last-iteran convergence and ( best-iterate convergence rate in learning NE of these games, where D = maxxex |Asl and L,, /2P² + 4L2. Specifically, if all players follow the update rule of SOGRM*, then (x - 0 and minre pan (x +b) S 0 ) co.
"
To prove last-iterate and finite-time best-iterate convergence of SOGRM+, we introduce Theorem 6.2 and Lemma 6.3, whose proofs are in Appendix G and H, respectively.
Theorem 6.2. pf 12/3DL there always exists an E/ 0. 2DL.)
2n2 satisfying 1 2 -2, D2
such that ensures ||0++1 0' as t + co and min | 0 < 0(2), Vt 2 1.
8

---

Lemma 6.3. If all players follow the update rule of SOGRM*, Vx = [zi E M E X,
E(e EN
0
0
++ D2
Σ iEN
0
0 33
2;
Di
17
7
Proof. Now, we prove Theorem 6.1 via our proof paradigm. Firstly, from the equivalence in Section 4 (Eq. (4) can written as the form in Eq. (5)), the update rule of SOGRM+ can written as (see details in Appendix I)
2; E arg min ( (ee- : ,,,,)
++
+ 93 1- (ax,) + D (0,,
0 0.+1 0+ Fi (('-) (
(8)
|10 l1 (xx)), 9: ( + (- ( 110, 111 1 (2;))
0:t 1 (a.)
17
From the first-order optimality of the first prox-mapping operator in Eq. (8), Vo X, we have
(o(+t)+
++
1+ (0r t ,x)) m. - 20 2 0
V
4
(+)
+ D d.
2
Σ
(x +
+
V
+ % - (x/ - V oz! 1 (x²) x2 I3
242) 0.
x.
iEN
Then, have
E
+ 1
++
b)
2 0,
(est
0 g++1
x2
b+b 2 0, (9)
71
iEN
iEN
where the first inequality is from + 4
0:1 -
(x
2 (x²+3) = 0 /n with
+
Va (=t") = 0./n and the second inequality is from Lemma 6.3. According to Eq. (9) and the definition of the normal cone, we have
0' 0
(xxx
(10)
n
where = :1 EV. From the definition of the tangent residual, we obtain
0
,ean (x ++
+) < 1 + +
1l S 110 0++1|12. 1l2.
(11)
"
Combining Eq. (11) and Theorem 6.2 (1
0++1|1 112 + 0). we get pean (x))(x²*)) + 0 as
t + x.. Similarly, from Theorem 6.2 (min,elt) T = arg min ||0 rr+1 12
10+1
0 0 S O(t)), we get that for
1
tan x r +) s - s 0
) / )
These complete the proof.
7 Conclusions
We study last-iterate convergence of RM+ variants in learning an NE of games satisfying the weak MVI. We introduce a concise yet novel proof paradigm to analyze last-iterate convergence of RM* variants. Using this paradigm, we show that two existing smooth RM* variants, such as SExRM and SPRM exhibit last-iterate and finite-time best-iterate convergence in games satisfying the MVI. Building on our proof paradigm, we propose SOGRM+, achieving last-iterate and finite-time best-iterate convergence games satisfying the weak MVI. To the best of our knowledge, this (i) the first last-iterate convergence for RM+ variants in games satisfying the weak MVI, and (ii) the

---

first finite-time best-iterate convergence for RM* variants in games satisfying the MVI or even only the weak MVI. Future directions involve integrating our proof paradigm with other OMD algorithms. such as Reflected Gradient [Hsieh et al., 2019] and composite Fast Extra-Gradieen [Cai et al., 2024], to develop novel RM+ variants that achieve stronger last-iterate convergence.
Limitations. The primary limitation of our paper is the lack of proof for the convergence of RM+ variants within extensive-form games. RM+ variants are typically integrated with the counterfactual regret minimization (CFR) framework [Zinkevich et al., 2007, Farina et al., 2019] to tackle extensive- form games. Establishing convergence in this context is particularly challenging, and addressing this issue constitutes one of our future research directions. The second limitation lies in the fact that our SOGRM* requires larger minimum p for convergence compared to OMD variants, as shown in Appendix B. Nonetheless, it's important to emphasize that we are the first to explore the last-iterate convergence of RM+ variants in games that satisfy the weak MVI.
Acknowledgements
This work is supported in part by the National Natural Science Foundation of China under Grant 62192783, the Jiangsu Science and Technology Major Project BG2024031, the Fundamental Research Funds for the Central Universities (14380128), the Collaborative Innovation Center of Novel Software Technology and Industrialization, and the InnoHK funding.
References
Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, Kentaro Toyoshima, and Atsushi Iwasaki. Last-iterate convergence with full- and noisy-information feedback in two-player zero-sum games. CoRR, abs/2208.008855. 2022a.
Kenshi Abe, Mitsuki Sakamoto, and Atsushi Iwasaki. Mutation-driven follow the regularized leader for last-iterate convergence in zero-sum games. In Proceedings of the 38th Conference Uncertainty in Artificial Intelligence, pages 1-10, 2022b.
Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, and Atsushi Iwasaki. A slingshot approach to learning in monotone games. arXiv preprint arXiv:2305.1661 2023.
Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, pages 27-46. JMLR Workshop and Conference Proceedings, 2011.
Ahmet Alacaoglu, Donghwan Kim, and Stephen J Wright. Extending the reach of first- order algorithms for nonconvex min-max problems with colypooonotooicctyy arXiv preprint M4Xv:22402.00771 2024.
James P. Bailey and Georgios Piliouras. Multiplicative weights update zero-sum games. In Proceedings of the 19th ACM Conference Economics and Computation, pages 321-338 2018.
David Blackwell. An analog the minimax theorem for vector payoffs. 1956.
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)4418-445 2018.
Noam Brown and Tuomas Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456): 885-890, 2019.
Yang Cai and Weiqiang Zheng. Accelerated single-call methods for constrained min-max optimization. In Proceedings of the 11th International Conference Learning Representations, 2022.
Yang Cai and Weiqiang Zheng. Doubly optimal no-regret learning in monotone games. In Proceedings of the 40th International Conference on Machine Learning, 2023.
10

---

Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In Proceedings of the 35th In ternational Conference Neural Information Processing Systems, volume 35, pages 13390--33913 2022.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated algorithms for monotone inclu- sion and constrained nonconvex mennexxxnononcceeee min-max optimization. Proceedings of the slst International Conference on Machine Learning, 2024.
Yang Cai, Gabriele Farina, Julien Grand-Clément Christian Kroer, Chung- Shung-Wei Lee, Haipeng Luo, and Weiqiang Zheng. Last-iterate convergence properties of regret-matching algorithms in games. In Proceedings of the 14th International Conference on Learning Representation, 2025.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pages 27952-27964, 2021.
Darshan Chakrabarti, Julien Grand-Clément, and Christian Kroer. Extensive-form game solving via blackwell approachability treeplexes. In Proceedings the 38th International Conference on Neural Information Processing Systems, 2024.
Yunmei Chen and Xiaojing Ye. Projection onto a simplex. arXiv preprint arXiv: 2011.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference. pages 27:1-27:18, 2019.
Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational incqualities. In Conference on Learning Theory, pages 1428-14511 PMLR, 2020.
Facchinei. Finite-dimensional variational inequalities and complementarity problems, 2003.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Online convex optimization for sequential decision processes and extensive-form games. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 1917-1925, 2019.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approuchability: Connecting regret matching and mirror descent. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 5363-5371, 2021.
Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-War Wein Lee, and Haipeng Luo. Regret matching+::in) stability and fast convergence in games. arXiv preprint arXiv:2305. 14709, 2023.
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, volume 32, 2019.
Pooria Joulani, András György, and Csaba Szepesvári. A modular analysis of adaptive (non-)convex optimization: Optimism, composite objectives, variance reduction, and variational bounds. In In Proceedings of the 30th International Conference on Algorithmic Learning Theory, pages 681-720, 2017.
Vincent Knight and James Campbell. Nashpy: A python library for the computation of nash equilibria. Journal of Open Source Software, 3(30):904, 2018.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Chung-Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. In Proceedings of the 35th International Conference on Neural Information Processing, pages 14293-14305, 2021.
Mingyang Liu, Asuman F. Ozdaglar, Tiancheng Yu, and Kaiqing Zhang. The power of regularization in solving extensive-fore form games. In Proceedings of the 12th International Conference on Learning Representations, 2023,
11

---

Weiming Liu, Huacong Jiang, Bin Li, and Houqiang Li. Equivalence analysis between counterfactual regret minimization and online mirror descent. arXiv preprint arXiv:2110.0461,,20 2021.
Linjian Meng, Youzhi Zhang, Zhenxing Ge. Shangdong Yang, Tianyu Ding, Wenbin Li, Tianpei Yang, Bo An, and Yang Gao. Efficient last-iterate convergence algorithms in solving games, 2023.
Linjian Meng, Wubing Chen, Wenbin Li, Tianpei Yang, Youzhi Zhang, and Yang Gao. Reducing variance of stochastic optimization for approximating nash equilibria in normal-form games. In Proceedings of the 42nd International Conference Machine Learning, 2025.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In Proceedings of the 7th International Conference Learning Representations, 2018a.
Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2703-2717, 2018b.
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(6333):508-51) 2017.
Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, al. Nash learning from human feedback. arXiv preprini arXiv:23 /2000886 2023.
Arkadij Semenovië Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Julien Pérolat, Rémi Munos, Jean- Bean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro A. Ortega, Neil Burch, Thomas W. Anthony, David Balduzzi, Bart De Vylder, Georgios Piliouras, Mare Lanctot, and Karl Tuyls. From Poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In Proceedings of the 38th International Conference on Machine Learning, pages 8525-8535, 2021.
Julien Pérolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome Connor, Neil Burch, Thomas Anthony, al. Mastering the game of Stratego with model-free multiagent reinforcement learning. Science, 378(6623).990-9)) 99600999696999 2022.
Thomas Pethick, Puya Latafat, Panagiotis Patrinos, Olivier Fercoq, and Volkan Cevher. Escaping limit cycles: Global convergence for constrained nonconve--nonconeeee minimax problems. In Proceedings of the 10th International Conference on Learning Representations, 2023.
Thomas Pethick, Joannis Mavrothalassitis, and Volkan Cevher. Efficient interpolation between extragradient and proximal methods for weak mvis. In Proceedings of the 13th International Conference on Learning Representations, 2025.
Leonid Denisovich Popov. A modification of the arrow-hurwitz method of search for saddle points. Mat. Zametki, 28(5):777-784, 1980.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019, 2013.
J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econo- metrica: Journal of the Econometric Society, pages 520-534, 1965.
Samuel Sokota, Ryan D' Orazio, J. Zico Kolter, Nicolas Loizou, Mare Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum sum games. In Proceedings of the 12th International Conference on Learning Representations, 2023.
Oskari Tammelin. Solving large imperfect information games using CFR+. arXiv preprint arXiv:1407.5042, 2014.
12

---

Tatiana Tatarenko and Maryam Kamgarpour Bandit learning in convex non-strictly monotone games. arXiv preprint arXiv:2009.04256 04258, 2020.
Mingzhi Wang, Chengdong Ma, Qizhi Chen, Linjian Meng, Yang Han, Jiancong Xiao, Zhaowei Zhang, Jing Huo, Weijie J Su, and Yaodong Yang. Magnetic mirror descent self-play preference optimization. In Proceedings of the 13th International Conference on Learning Representations, 2025.
Chen-Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In Proceedings of the 9th International Conference on Learning Representations, 2021.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Proceedings of the 20th International Conference on Neural Information Processing Systems, pages 1729 1736, 2007.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We clearly show the assumptions in this paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
We provide the full set of assumptions and a complete (and correct) proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibiliyy
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the information needed to reproduce the main experimental results of this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [No]
Justification:
We will provide the code once this paper is accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (htips//nips.cc/public
guides/CodeSuumiissinpooiiii for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (htips: wtweliicgiiiieeCCeeeeiiiiiiiiiii
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We provide all hyperparameters.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, when testing randomly generated games, report the variances across the game generated by different seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the details of the computer where the experiments are conducted.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///eenppsccccubblllctiicccl
Answer: [Yes]
Justification:
This paper only investigates the convergence of some algorithms.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics. If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper only investigates the convergence of some algorithms.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The code that used is cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswitheode, httpssttthooe.ccc/tttteeee has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: We only use LLM for writing and editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (ttt:///eeaiias.ccccoooereeessss for what should or should not be described.
20

---

Table 2: Comparisons between the minimum value of p of ours and previous studies about OMD
variants games satisfying the weak MVI.
Minimum p
Algorithms
Cai and Zheng [2022]
OMD Variants
12v
Pethick al. [2023]
OMD Variants
2D
Alacaoglu et al. [2024]
OMD Variants
Cai al. [2024]
OMD Variants
Pethick al. [2025]
OMD Variants
Ours
RM Variants
12v3D 223
A Detailed Comparison to Cai et al. [2025]
Now, we provide a detailed comparison to Cai et al. [2025], including the proof techniques, the best-iterate convergence results, the non-finite-time last-iterate convergence results, and the finite-time last-iterate convergence results.
In terms of the proof techniques, our proof paradigm centers recovering the weak MVI, whereas the methods proposed by Cai et al. [2025] focus on analyzing the limit points of iterates or leveraging the definition of the duality gap in two-player zero-sum games, Notably, paradigm is applicable to both best-iterate convergence and last-iterate convergence, in contrast to Cai et al. [2025], who require separate proofs for these two types of convergence.
Regarding the best-iterate convergence results, our results apply to games satisfying the weak MVI, whereas those of Cai et al. [2025] are restricted to two-player zero-sum matrix games. The applicability of our best-iterate convergence results significantly broader than that of Cai al. [2025].
Concerning the non-finite-time last-iterate convergence results, our findings hold for games satisfying the weak MVI. Cai et al. [2025] divide their results into two sections: the first pertains to two-player zero-sum matrix games, while the second addresses broader games satisfying the MVI. Their results exhibit pointwise convergence for two-player zero-sum matrix games, surpassing our own in strength. However, games satisfying the MVI, our results align with theirs, yet ours extend further to include games satisfying the weak MVI.
With respect to the finite-time last-iterate convergence results, mentioned in Section 2, our best- iterate convergence results enable us to extend the finite-time last-iterate convergence findings of Cai al. [2025] from two-player zero-sum matrix games games that concurrently satisfy monotonieity and metric subregularity. This exemplifies one of the advantages of our best-iterate convergence results.
B Comparison between the Minimum Value of p of Ours and OMD variants
We also compare the minimum value of p between our SOGRM+ and previous studies OMD variants in games satisfying the weak MVI, as shown in Appendix B. Focusing on the constrained setting, present this comparison specifically within this context. Although other algorithms accommodate a broader range of p. existing work primarily concentrates on OMD variants. We are the first to explore the last-iterate convergence of RM+ variants in games that satisfy the weak MVI.
C Detailed Proof of the Phase 1 of Section 4
In this section, provide detailed proof for the Phase I of Section 4. Before starting proof, first present the following lemma
Lemma C.1 (Adapted from Theorem 2.2 of Chen and [2011]). For any y E RRd,, the projection of y onto the simplex A is obtained by 1] where 7 exists and is unique.
21

---

Now, we start our proof. Firstly, considering Eq. (4), from the fact that eb(-) is the quadratic regularizer (in other words, Va, b E Rd c E IR. (b)(a) = | //2 Dep (a, = clla b22 we have
0 E arg (- (- 0z) - (0, 0:013
0, 6
1
0 E arg min ( (0 02) +
00 0.011)
21
21
1 10.:012
0 E arg minf( (- (, 01) + 2m
10:12
+
(0: 0,0)
2n
2m
21
Then, we have
- E arg min min(((F((O0)) 0,) - De (0,, 0:²)}
0
0 E arg min (12 0, + 10,12 + 110:0 0!
0
E arg arg ( ( + 10.11 200.0%00
0.ER|A Acl
0
E arg min {{ (-2nF.(0') 20 0,) 10:113)
0 2 E arg min {{ (-21)F((0'²) - 20 0,) 10.11 + 11FF(00') + +0%0133)
Q.ER!! Acl
0 E arg min (n0) + 0 0.113.
0.ER lAcl
0¹1
Since F,(0")
1 Ci, we have
|1001
g a E arg min ( (()))())),) E Anl
0,)
(12)
0 E arg min 1 +
+1l
) 1 - ne: -0,113
1
0,ER 14,
Eq. (12) indicates getting the projection of 0 T 10
4 ne on R!4.l As analyzed
in Section of Farina et al. [2023], Vy E Rd, projecting y to solution of the projection is [z]+ If [1] lla < 1, return the projection of y on simplex. Let
R R if |Ill by|t 1/1 2 1, then the
0 + イ
ne we have
10 to +
0 Ih
e 1-
1 (
11)
0 2
10
(13)
10 +
1
1- -
331
1 17(
11)1-
lh
110
ll
where the top means 11 <
1
1
2 1, the solution
10
10 7
1 and the bottom implies if 11 17(
8¹ 1
1
the solution is the projection of 0 + n [ I|1
-n on simplex. Hence, shown in
Lemma C.I, the closed-fone solution in the case where ||0 + 77 _ 1h e - ne
8 is 10 + ( 10 2 ne -31] where 3 exists and is unique to ensure
22

---

10 + 7
nee - 31]+ in simplex, because (i) B is the term in Lemma C.I,
10 I1,
as well (ii) y exists and is unique. In other words, 8 in Eq. (4) can be obtained via
0-- 0 7 0
111-ne + 2 1, 2 n if || n 1-
10 + (
1 npe:" - f1] if l1 + n 10
1- - 1 < 1,
Secondly, for Eq. (5), we have
x arg (ef) xx)) + f((x;) + Dr. (2,, x
2 E arg min (e)) 2.) + |10%311 (xxx)) 10% (b(x)))) + D Pio0011 ( 2))
m
Since vb) is the quadratic regularizer (in other words, Va, E R& I2 ca((a) clla|1/2.
Dos b) = clla- b bl2/2), we have
la arg min (E. ..) + f((x,) + Dn, (z,,
2,Ex,
0 arg (min(((( (C," ..) + 10 |as112
| 1|1
1 ||
< 11
x - 2:/112)
m
2n
2/)
2n
+a t E arg min (2 .m.) + |10 || 11,,111
110
|| ||,
|10 11 am 21211))
*x,-" arg min (2m 1 .x)) + |10|0 |1 ||=
110.0
11
11
|10.0 || 11++
a,EX.
|= 10
| 2 0
(Z) x"
ca 1 E arg min ( (22) ..) + |10
||
2110 (m,, (2))
(14)
l arg mig (2me) 2 1/ xx)) + |10 |
m,
(ne:
110%0
10 xx:)
+ E arr (2
+ ||x;112)
|10%31|
a
(ne |10%0 a1 axi)
+ 1|,0:113 + ne
10 50
cat E arg minmin miEX
(2
12:)
|10::11
1 1/
net
#xo arg argmin| a.EX.
||
xx:12
| l11
0
net
< E arg min|
||
10 1|:
m;
where the last line from 00 = -10
21 2 (xr
0.0 ). Since X; is simplex, Eq. (14) indicates
10
getting the projection of 0 -
on simplex. Therefore, shown in Lemma C.I, the elosed-form
|0
solution of Eq. (14) is Eq. (15):
0
ne a'1 a'1)
10 al n/
(15)
|00.00 1|1
0
where a' a' is the term in Lemma C.I, as well as (ii) y exists and is unique. In other words, the update rule in Eq. (5) can be written as
Notably, a exists and is unique to ensure
in simplex, because (i)
0 1
1100 h
10 al m
(16)
10 |1
Note that 0²= 0%0, and e: are the same between Eq. (4) and Eq. (5).
23

---

Thirdly, assume in Eq. (16) is
8²1
7/(
if :1 + 1
ne, 1+ 2 1, )
100
10
11
(17)
0
2
if 1 n
0-
)
+1 <1 1,
10
II.
By using Eq. (13), we have 10:0 a1 m | 00-- Therefore, substituting Eq. (17) into Eq. (16), get that the update rule in Eq.
(16) (or Eq. (5)) can be written as (since 10 a1 n 0))))
10
ne
0
(18)
0 I1
100-111
which enables x²² in simplex since ||= I and x 2 0 (the x²² in Eq. (5)). In addition, as mention
in the text around Eq. (15), we have is unique to ensure x/- 10 -al--e21t in simplex. Hence,
100
the value of must be same as Eq. (17) shown! Also, note the x²² in Eq. (4) is obtained via
(19)
10
Therefore, combining Eq. (18) with Eq. (19), we get that the update rule in Eq. (4) is the same Eq. (5). It completes the proof.
D Proof of Theorem 5.1
Proof. Now, we start to prove last-iterate and finite-time best-iterate convergence of SExRM and SPRM Firstly, from the analysis in Section 4 that Eq. (4) can be written as the form in Eq. (5), the update rule of SExRM* can be written as (see details in Appendix I)
+ E arg minn (e), + 9: 2 (ax.) + D - Da (æ,, a)), Hi (a,)
100 (ax;))
x.E:
17
1+1 arg migmin((e (e (et+
( a.) + (axs) + ne- (.:; (x;, x[)];
(20)
E,
110, 1100*111 1 111 (z;)), o; (x:) + (xx;))
100 '11 (xx))
q n2t (x.) q;
- (x)
7)
Similarly, the update rule of SPRM+ can be written as
++ E arg argg mi $ xx)) + de - (a:) + D (z;,)((; x)), (x:)) 110:11
(xxx)
n
att1 arg min (e, 3 2i) + (xx) D D.0a-1a02; w!)}
(
(21)
n,
q 1 (x) = 110 110
2 || (xx;), 0:t-1 (x,1) + (x,) 10 (xx))
Dz (xx) q:
17
The MVI is recovered since the feedback e } Ct, and e are the loss gradients of the original game that satisfy the MVI. Now, we prove that the tangent residual of the strategy profiles af converges to 0. From the analysis in Phase 2 of Section 4, according to the second prox- prox-mapping operator in Eq. (20) and (21), Vx E X. we have
0++ 0r
x 220+))20000002 + 0 0
(er+
exxxx
(22)
From the definition of the tangent residual, obtain
0¹ +++1
y tan (1) < <||et+1
g +
lla
"
< 11tt1 g 1 + 0 r l|2
(23)
<LI|0 1+1 ++ 2|2 + = 10 - 0i - 122 + - 10++ - -0'+1112
24

---

where the last inequality is from the smoothness of the smooth games. Then, using Lemma 5.4 with 0 and b- = 0 we have
pon (xt +1 SLVDII0**! - 0 112 + - 0-
-100 - 0 1/2 + - -100+=-00++ -0'+112
(24)
From Theorem 5.2 and 5.3 (1l0' - - 1 +- 0o. Similarly, we get
112 + 0 and 1 r 1l2 + 0), we get rean (xx) + 0 as
(nlan(a" (1)))()))))))))))))) S llett1 p²+
0' 0
22) pt+l - & 11 +
2 110 -
1
n72
2
<2L x 4+ x
x 212
+
0
0
qp
By using Lemma 5.4, we get (rlan (x 1)² s2L² - -
+
4 173
110 0
+ 1/
4
10:
00+
D2' +
4
(105
0
1 + 110
o 113
772
Thus, from Theorem 5.2 and 5.3 (min
E|| (110
0 1 + 10
r b (12) S O(t)), we get
that for arg min r(( (1 r 11 |
-r
# (2)
pan (x: 1) /o (110 - 0- + | -aal--r+211
1B3
These complete the proof.
E Proof of Theorem 5.2
Lemma E.1. (Proof is in Appendix E.1) Let x' E X" that satisfies the MVI and assume all players follow the update rule of SEXRM*, then for every iteration t 2 1, it holds that ||@ 1 S
110² x² 1/ - DD (10++3- - 002 + 11 0 2 #12 IBB) where D = mmxxie |Ail and
L, /2P² + 4L2.
From Lemma E.I, we have
|10 - x= x= ||0 x=1 112 < -(1 - DL.. (10 -0'122 + +1 1
(25)
Assume (10C*) - 0 12 + | 1 0 + 113) does not converge to 0. Then, from Eq. (25), we have
|10 - 111 -+-1-x111 < 1101 x=11 Σa-
- 0-13 - + 110 - + 113)
In addition, since 1) < D we have (1 nDL,)) > 0. Therefore, as T - xx, 1
ar" 112 S ||0| x=1 Σt= (10 - 112 + 110 - + 113 00, which contracts that
I x² 113 2 0. Therefore, we have (1 - 0¹1 + ||@r+1 g |b] converge to 0 as
t 00.
In addition, from 17 < DI... and Eq. (25), we have
1|0 Σ (11 0²1 + - 0 < 100 x= -1-0|00+11 x 112 (=1
S C,
where C' is a constant which depends on 01, x,, 17. D, and Ly, Therefore, we get
Tiin tET
00'1 (10 - 0'112 + ||00+1 -++ 1 113) Σ -100 + |10
- SC,
which implies
(105+
-0'113 + ||0 - 03+1113) s C.
min EET
25

---

E.1 Proof of Lemma E.1
Lemma E.2. (Proof is in Appendix E.2) Assume all players follow the update rule of SEXRM*, then
for any E RR X1
21" we have
-Dv(000)))
= +n) ()
Substituting 0 = x² x" that satisfie the MVT into Lemma E.2, get
Ds(æ" - (x= 0")
() 1(th)) (26)
S <-n(F((0* ))=² D (6 0 - .00
For the first term of the right- side of Eq. (26), we have
(F((0+)))
Σ
x;)) = -n x -xx) S 0.
(27)
EEN
iEN
where the last inequality is from the definition of MVI (Section 3.1). For the fourth term of the right-hand side of Eq. (26), have
n (( F(0'), 0 2 Sn) Snl ((0++)) 1(0')11210 0 1|2
(28)
InDL,110* - 0' -0- 112,
where the last line is from Lemma 5.2 of Farina et al. [2023] (() F(0')12 - DL
O' 0211,, VO, o' E BRt where D, Ln in Theorem 5.1). Combining Eq. (26), (27), and (28), get
Dp 0 Ds(x",0))
S (o+0 0 (+ ; 0¹) + DDD 1 0'12200 - l|2
S (0+01 1000++11+++)+-000111)+11))))++)) (0'+ 0¹) nDW, (D+(O't), 000)+ Do (((t))
S - (1 - DD,,)), ( 0¹) + (0" 1
where the second inequality is from Va, b E R, ab S pa? 2 b//2p, vp 0 (in this case, |100t - 0'112, = ||0'+1 + ||,, = 1) and ( b) = ||a - -b1//2, Va, b E Rd if v()) is the quadratic regularizer.
E.2 Proof of Lemma E.2
To prove Lemma E.2, we first introduce the following folk theorem (we drop the terms involved æ in Eq. (2) and Eq. (3) since they are not used in the following proofs).
Theorem E.3. The Update rule of SEXRM* can be written as
0++ E
arg min {(-F(0'), 0) 17 -
DEXTEX
14,
21
(29)
a++1 arg min ( (K-F(O++)), -0, 0'))
DEXIENR
and the update rule of SPRM+ can be written as
+ E arg min
((-F(0'-3),0) + De
@EXiENR!A (4g)
(30)
g++1 E arg min {( {(- ((-F(()+))..) 0) + (0, "
1
@ExieNa!Ad
where 1) >> O is the learning rate.
26

---

Considering Eq. (29), and using Lemma G.2 with a = 0", a'= = = a' =0 g -n) b)
(in this case, A is x XIEN
21 [Ail), we have
77 T(=F(0++) 2) 0 0) S (D, (') Dio (0, ( ,0")
(31)
Similarly, with 0¹, a' =0 a-= = 0 and g -n'( get
Dr. (0(+1 + - ( (')) Summing up Eq. (31) and (32), and adding 17 ((()++)) F(OO), 0 - ) 0(01)
7y 7 0 - I
0¹) (
(32)
to both sides, we get
7< ((-F(O*+)) )) 0
0)
<D (0,0") (0, 10)) - Do 00++)
-0 - De ( 0²) + 1,0
F(0)), 0 -
Arranging the terms, we have
(0, - (*,
In(F(( )), 0 - 0) + (F(((())) F - ( ) ( 01) S { 0) + + (F(())) - F(0'), gt+l - -1tt)) - -D D gltb)) - (
-
where the last line comes from (F( 0 = (FEN 0 =
EiEN((E : +b/ 1 e t othy = EiEN(e,
+t , (1, ( 00, 0 =
41 0t 1100
Ei
a l1 (et , b 0. It completes the proof.
100
F Proof of Theorem 5.3
Lemma F.1. (Proof is in Appendix F.I) Let xx E X that satisfies the MVI and 0 < <1- < SDL..' then
for every iteration 2 1, it holds that
100+1 x
1
100 0c+
1
1
-r-
0r
-12
+
15
0
0
|/ 0' 0 112))
+
16
16
16
From Lemma F.I, we have
|
xx
12
1 |0
0
112 < 100º 0 1
16
(33)
1
0
111 -'
0
15
0
0
3 |/ +
0
0
112).
16
16
Assume ||0++1
gr+
112
0 |
112 do not converge to 0. Then, from Eq. (33), we have
|0
11
0 10
12
T
<|00 - x 112 +1
||0|
01-1113
15
--- 3011 112 +
1 - 1 112).
16
16
1=1
Therefore, as T + 00.
10 x
11
+ 16
1
00
0
- 0 0 +
0-
15 Ei= (1 10 0++ 1 0 0 T6
(12)
-0, which contracts that 10 11
10
1 2 0. Therefore, we have 10 0 b 112 1|2 + 110 8 1/ - 0 as t + xo, which implies
||0 1 + 0 and 00 0 0 112 + 0 as t + co. It completes the proof.
In addition, from r < sDt., and Eq. (33), we have
[10 - 0² 1| + 1 g 11 SC
where C' is a constant which depends on 02, 0t, x-, 11, D. and Lu. Therefore, we get
T
Tmin 1ET" (10 - 0'113 + || g 11 Σ (10 - 0411 + 10 - SC,
which implies
(105+
-0'13 1|0+11 - or+ s CC
min EET
27

---

F.1 Proof of Lemma E.1
Lemma F.2. (Proof in Appendix F.2) Assume all players the update rule of SPRM*, then
for any E R X1
21" we have
De(0,0 )-)) (( -
Substituting f = x²x E X that satisfies the MVI into Lemma F.2, we get
Dy(a" - )t)
(-O(F((0+))) )),b)) - Di ( g 11)0 - ) -
(34)
According to the analysis in Section 5, for the first term of the right-hand side of Eq. (34), from Eq. (27), we have
(F((0+)),,;))5))
EN
To simply the fourth term of the right-hand side of Eq. (34), we first introduce Lemma F.3, whose proof is in Appendix F.3. Lemma F.3. Assume all players follow the update rule of SPRM+, then we have
| - $ n/| F(0+*)) F(0 -)12
Therefore, for the fourth term of the right-hand side of Eq. (34), have
(F((+t+)) F(0' )), 0+ 3
Snl =((+=()++)) - ((0'-+)]la 0 + 112
(1)()))))) F(00- )11
where the third line is from Lemma F.3. Then, from Lemma 5.2 of Farina et al. [2023] ( (()) F(0')122 < D 0' 00 E R where D, Lu are defined in Theorem 5.1) and the choice of 1), we have
n (( F(00--))11 DT 0 -0-
1 1 1 S
64
Continuing from Eq. (34), we then have
Do(#", 10*1)- 1
(eth 8²+ 2) (8 10000+10000
0,0') +
1
1
0'-6
64
(o 0 + (0
1
10
++
0
0'
32
32
- -x 101
1
10
0 1
16
1|0 x l1
0
0
15
(1
0² 11
+ 110 -1
16
16
where the last line is from D b) = laa bl./2.
F.2 Proof of Lemma F.2
Considering Eq. (30), and using Lemma G.2 with a 0,, a' -1++1 a" and g (
(in this case, A is !RENRR (Ael), we have
イ F( 0, 0) 5 (0) (0, - (0++ 00))
(35)
*n ( 0 - (0,000') 01+)) - (0 (0))
28

---

Similarly, with = 0", a' = = i, a" 0 and - -F 1), we get
' ( 0 - 0 < Du(0't) 0¹) - Do , (,(0 0²) * = , / - Dv(0++1 0¹) Do ) - -Dr(tt 00)
(36)
Summing up Eq. (35) and (36), and adding 17 (F((tt))) - F(0" 00, -0+t2) - to both sides, we
get
7 ((FF(((+)) 0'+ -0)
SDv(0, (v, 1 (0'+l (' Do Arranging the terms, we have
( 0
(0)))) <n(F(O +), 000 0) + (F(((+)) ( - - Do 0
) (
S --n(F((+t)) 0) (( F(0 :), 0 10t1-100 -00t100th g ( ptt:)) ( 2 O'),
where the last line comes from (F(O*+)), 3 0 = (Fe((F(( b), 0
EiEN a a(tt))1 e 0 o
EiEN
1+ 2 (1, 07 (e,t 00/h3)
0tt
lett
100 010 la - (e , = It completes the proof.
F3 Proof of Lemma F3
To prove Lemma F.3, we first introduce Lemma F.4, which is Lemma 11 of Wei et al. [2021]
Lemma F4. Suppose that v--) satisfies (b, b') 2 |b b- A (a convex set) be related by the following:
b'll for some p 2 1, and let a, a1 02
a1 E arg rigmin((e (a', a'EA
((''.))) 91) + Dz(a', a)}
a2 E aargmin( (a', .2)) + +Dp(a', a)}. a'EA
Then, we have
|a -0222z S l|g1 92llg:
where q 2 and 1 + 9 =
Considering Eq. (30) and substituting a₁ 0c+1, a 0 91 (n 92 -n $) and (p.) = v-() (+(-) is the quadratic regularizer, which satisfies (b, 2 _ b'll)) into Lemma F.4 (in this case, A is XieN have
|10011 g++b 112 S (1) -1 - + +||0 - +h+ 22 S (| F(0* )]1,.
which completes the proof.
G Proof of Theorem 6.2
Lemma G.I. Let xx X" that satisfies the weak MVI and < 1 < 2D
I
then for every iteration
t 2 1, it holds that
T
2p
1 10: 0-1 112
Σ
2n² 12
0 1
|00 x013 +
4
where D = maxie [Ail and L,, /2p² + 4L?.
29

---

From Lemma G.1, we have
T
2 + 2p
1 110 0 0
Σ
2nj D2
10 - -0 - 100 x²12
1 +
(37)
4
Now, we first prove that if 12v3DL," there always exists 0 < 77 <
2DL that ensures
+ 3e 2n/ D > 0. Formally, consider this case where 12/3DL. we can set =
1/(2/3DL.) that ensures
1 2p 2
1
+
12
2
"
3 6
is evident that the expression
32
increases with p if >> 0. We have shown that the expression evaluates
2r
when p 12v3DL. and 1) 2V3DL..
1 2p +
217² D2
2
17
2 3
Therefore, if p>> 12/3DL..
with 1) = 2V3DL.." must hold that
2p - D2 0.
1
In other words, if p 12v3DL then there always exists some 7 2v3DL. (0, 2DL..) such
that
2p
2 + 207² 2 L² > 0.
Assume ||0++1 -01/ do not converge to O. Then, from Eq. (37), we have
2p
2n D2
|100+1 0011 -0
O()),
2 n
which contracts that
T
2p
2 D² || 0-11 < ||0 x²11 +
0 0
-
2
7
1=1
Therefore, | In addition, from
0011 + 0.
1/2 + 2e "
2mj L > 0 and Eq. (37), we have
T Σ
1-1 < 1 x 1 + 1
0
|0+11
C.
2 + 32 2022
Since 0'. 100,00 0- x,, 77 p. D, and L, is fixed, C' must be a constant. Therefore, we get
T
min RET
1
g
3
which implies
C
min 0 IET
T
30

---

G.1 Proof of Lemma G.1
Lemma G.2. (Lemma 10 of Wei et al. [2021]) Let Aas a convex set and a' E arg we la g)+ De a)}, Then for any a" E A.
(a' a S Dela", a) - Do(a", a') - DDpla',
Lemma G.3. (Adapted from Lemma A.2 of Hsieh et al. [2019]) Assume all follers the update rule of SOGRM+, then for any 0₂- E TR
T we have
x
Dv(0, -D. <(0; + -
+' - ..))
Considering Eq. (7) and using Lemma G.2 with a 0 a' = - a x - and =
:), we have
s (1F )) 0f - 2;
++ 1 ) + Dup (a; (+ 00) (a
(tt , , - De .0) (38)
+ S (n )), , -2, + + (0) - , 0,0 + ,+b
x/
where the second line comes from
(
++ (xx
2+ .0
D
s (0) 0
|
12
(x)
1+
.00++
100112
||
+
12
(a)
1+ :
10
1
113
+(0
++
10:111
2
2
2
2
2
= =(0) 0
+ 0 2; $).
Substituting 0, = x E x that satisfies the weak MVI and Eq. (38) into Lemma G.3, and using the
fact that (F((0 3), 0 8)
((e,t)
_ ++
) e
0 r+ b) = 0 (x,++ 0, : $/100 (1 and
+
(F((O++)) ), x xb) = (1e, x
++
8/11 e," "x,," () = 0. we get
(2j 0 Dwlat 0
<00 0 + F, (0 1) 17 F. (0 ()) x - (2) + (0. - (0
t ;,)).
(39)
Since 0:-1 = 0 F ( +) + ( we have
0 - 0,+1
0 0
-(((0-))F((00-1)
F.(OC=b).
(40)
"
n
From Eq. (10), we have
0¹
0
1ltà E (xx
(41)
From the definition of weak MVI ((8T + 2 x²) plle0 + +1112, Va (x) and setting
x = ++ and z or 0 x²+ E eNx 1) (Eq. (41)), we have
(0) 0h+1 x." - t - + 0' 0
e 2 x - x. t1
(42)
0¹ +
2p (0 .²).
< - pnl
1|
"
n
Now, we define c= 2/2 2212 > 0. Combining Eq. (39), (40) and (42), we have
D - D==a="000) 000)s (0 (0 D. Do.
(0 0²) (0
2p
D 00'+100
(D 1000++100+ )D +cD (0 _0)- 2p (o '')
1]
S(1+2))D (10000001_000)11111111)))
(1 26) (0++)
2p +c) (0'+1.0')
(43)
31

---

where the last line comes from D (0'+1 0¹) = (6 (00-1 b) + 2D (0*+ 0*).
By using the fact that 0f- = 0 0
+). Lemma 5.2 of Farina et al. [2023]
(0) - (00))l22 - DD 0' ||2, 00,0'= E E where D, Lu are defined in Theorem 6.1), and
Dv(a, b) = la bll//2 we have
D2 ,
(44)
By using Eq. (44), we get
(0 0²ー s 2D (0 + (0', 0' s 20 ,0) + 22 D' (0'=2, 2,000)
which implics
( 0²) 2 D (0 , - -,-02,20000 0'
(45)
Combining Eq. (43), (44), and (45), we have
Do(a" 1 (v
2p <(1 + Dc) (0 - - (1 2c) (8++2, -120 +
+ 0'))
1
- ( c- (1 + 2c)1 Dz ,0' (1- - 2c)n '0 (
1
20
+ +c) (0'+1 00)
1|
(0' (0000 2)) Telescoping the above inequality, and using = 1/22- 217² have
< r
2p + + + 0*) 4nj ' D
- D2 L3 with ( b) ||a b112/2, we
Σ
2p " 2n2 D2 D2 100011 0² 0 x 4n7 Dr レ 0 0
<100 x
0 - 0 0 112.
where the last line comes from 4r < + (note that e > 0, which implies 2n7² D2 < 3 thus
4rj² D < })-
H Proof of Lemma 6.3
From the definition of Eierle
1-- 1.
0'0 2. xz 222), we have
0 0
1+
1+//
D1 x
7
VEN
0
0 ++
F((0-=)) b) (F((0't)), x; 4t,
IEN
(46)
0 0 u++
(1/- x
1 3 e - (e.+ x (+ + e,t x; x;
1+$
VEN
0 0
3F;
TEN
where the last line is from ((e) xx;
1
++ 0 and
(1e
(+ 2 x, =x; [t1
x
x
0.
32

---

I How to Obtain Eq. (8), (20), and (21) via the Analysis in Section
We now detail how to derive Eq. (8), (20), and (21) from Eq. (7), (2). and (3), respectively. This derivation follows from the analysis provided in Section 4. Specifically, from the analysis in Section 4, we have that V 0 0 0 E | . > 0 and (b)-) as the quadratic regularizer, the update rule in Eq. (47) can be written as the form in Eq. (48).
2
E arg (in((1FF((()) ), 1 (0,,0,00)))) 0,) 1)
2
0
10
1
0,ER
144
(47)
0
e 1 t
10
2 E arg min (1t) x.) + fi( + Du, (2;;
E.Et.
(48)
110 11 (x,), h,(2;) = 110 ||1 (xx)),
h((2;) + f((x;)
where to. t1, to refer to different iterations, x/ = 0 0 11 2/ /1001 1|
Consider the update rule of SOGRM* as shown in the following:
0
0 E arg min((-F;((0=)))
P0, 09),
a
A.ER!A
10 |1
(49)
0 +1 0 F (0' +)++
+ 0 = 0 - 0 = 0 into Eq. (47), we have that Substituting 0 0
0 + 1
0 E arg min(( ((- F.(00'=).. 0,) + "
Do., 03)}
x
D [44)
10
0:-
F((0' 1)
100 l11
which is consistent with the first prox-mapping operator in Eq. (49). Therefore, according to the relationship between Eq. (47) and Eq. (48), we have that the first prox-mapping operator in Eq. (49)
and x; I+
=6 0, 1 / l| can be rewritten as
I+ E arg min (ETT xx) + 9: t- (xx) + D Dee Da---1(20 (2; x;)}. E.EX.
|0001 (w:)) d; (xx)) di
1-2 (xx)) 110, + (x))))
4, 0:0 (
")
n
In this case, (w:)), fe(1x) in Eq. (48) q. (a:)) and qi 2- 1 (2x)). respectively. Therefore, we get Eq. (8).
Consider the update rule of S as shown in the following
0 t
+ E arg min(( () + D 00) x;
0,eRl4 |4,
"
10
(50)
0
0++1 arg miin(-iiniiii min((-F((0)))), 0,) Dv (0;, 03), a
110.+11 |1
0, e
33

---

Substituting 0- -001, 0 -0 - 00 ! into Eq. (47), we have that
0 + E arg min(( ( Fi(0"), 0.) + - (O,, 03) a
0
0.ER Ael
0
OO = 11:111 f E.
which is consistent with the first mraping operator in Eq. (50). Therefore, according to the relationship between Eq. (47) and Eq. (48), we have that the first prox-mapping operator in Eq. (50)
and z; ++
0, / I|a can be rewritten as
a l+ arg min ((g .x2) + qi 1- (x::) + D D a.));
mEEX.
(51)
G: (xx)) + qi 1- (xx) (xc,) 110 3 #112 10 (x;;)
4. ou (xx))
(xx))
1)
11
In this case, hx(x;). fi(x;;) in Eq. (48) are q: (x:) and 9: (æ,), respectively. Similarly, substituting 0-2- = 0.+1 0 = 0 0 = of into Eq. (47), we have that
0 arg min ((- (0 0,) - (0,, 02), at
0 ++ 10
0 0
(0 =
e++
e
110, +
which is consistent with the second prox- mop-iig operator in Eq. (50). Therefore, according to the relationship between Eq. (47) and Eq. (48), we have that the second prox-mapping operator in Eq. (50) and x/ 0++ /||0+++||
||
can be rewritten as
x. ++1 arg (e, x.) gt (xx;) D Dapre- (2; x()}:
..E
(52)
10 (xx)) 9: (x;)) + (xx;) 110--111 (xxz)
0:t (x:))
9:
"
In this case, h (x;),, fi f1x;) in Eq. (48) are of (xx) and (xr)), respectively. Combining Eq. (51) with (52), we get Eq. (20).
Consider the update rule of SPRM+ as shown in the following
0 4+3
0 E arg F + (e,,
2+3
0.ER !4
77
10
(53)
0
ot arg min minm((FF((0**) ((
0,) ))00))
D (0,, 03), 2
0
+
11
Substituting 0 0 0 = 0 0 = 0 into Eq. (47), we have that
o
0t à E arg min(( (((0(=)) +,, + De 03),
1 "
a
1+
D.ER!Ai
100
0.
F:(O'- 1)
2 1
1
which consistent with the first prox-mapping operator in Eq. (53). Therefore, according to the relationship between Eq. (47) and Eq. (48), we have that the first prox-mapping operator in Eq. (53)
34

---

and m; 1+ =0/+3/ /110== || can be rewritten as
++ 4
E arg min (e)
t xx)) + 9i
-- (xi) + so (2 a;),
z;
(54)
|0:|1 (xx)), 9: 0:t (xx)) qi 1- 1- (w:)) 110, (xx))
9. 1
1)
11
In this case, (x;)) f(( in Eq. (48) are (x; and q; (- 2
(z.). respectively. Similarly, substituting 0:²² 0 0000 0 0 of into Eq. (47), we have that
0 100 ++
0-+1 E arg min( ( F: (. ) 0.) + (0, 03), x
0.)
0 0
eg
x+
1 et
110 +
$11
which is consistent with the second prox- mox-mapping operator in Eq. (53). Therefore, according to the relationship between Eq. (47) and Eq. (48), we have that the second prox- mapping operator in Eq. can be rewritten as
(53) and x. f+1
0 /||0++1||
I
xtt E arg arg min (e,+ 1 x.) + (a,)) + D (20, x;)}:
a
(55)
10:111 (xx), q; o (x:)) + of (x;;)
10 1|1 (xx))
0:t 0 (x:)) 9;
"
"
In this case, (x;), fi (ax;) in Eq. (48) are df ( (x.) and (2:). respectively. Combining Eq. (54) with (55), we get Eq. (21).
J Example of Different Game Types
In this section, we provide examples of smooth games that satisfy the MVI and weak MVI, respec- tively. We do not provide the example of smooth games satisfying monotonicity any two-player zero-sum matrix game is a smooth game and satisfies monotonicity. Note that in this section, we focus on two-player normal-form game, whose utility function is convex and represented by payoff matrices. Any two-player normal-forn game is a smooth game. For each two-player normal-foo form game, the utility functions of player 0 and are presented by payoff matrices A and B, respectively. Formally, ux(x)) = ax Ax; and un (x) = x; B nt. which implies Ey = - Az; and e = - -B' an-
J.1 Example of Games Satisfying the MVI
The example is defined as following
0 0
2 0
2
0)
-
B
This game violates monotonicity when
0.1
(0.1
zp
2
0.9
x
0.9
Formally, in this case, have
eT = 0
-2
00)
-2
PT
ex'
0
0)
-0.1)
(-0.1
x²)
0.1
0
0.1
-0.4
which violates monotonicity.
35

---

Now, we show that the provided example satisfies the MVI. An NE of this game (learned by "Nashpy" [Knight and Campbell, 2018]) is
0
)))
oj =
We define the strategies of players as following
21 = (1
a
1 1-b)
where S S and S S The loss gradient E of player is
E =
AAT,
E = -=BBaaa xo.
Formally, for player O, we have
2 0) (1 b = (0)
2b
Ax
1
(00
-26
E6 Ax
0
Similarly, for player we have
0)
B 0
BT x0
2 0
20
0 0
1 1 a
0
-2a
E = - B x
In this case, we have
(26)
22
b - = -ab + 2a + 26 = (-4a 4a + 2)6 + 2a.
(E= x-=x) (²)
+
11
We can find that (-4a+20 + 2)6++ 2a is linear function w.r. given fixed a. If1 1/2 (-4a+2)6++ decreases b increases. Therefore, given 1 2 a 2 1. (-inosssi-AAa2)1) 2a (-40+2)-4 +2a 2) 2 2a 2 0. Similarly, if S a < (-4a + 2)b + 2a decreases decreases. Therefore, given 0 < J. minogbs1 (-4a + 2)6 + 2a = 2a Z 0. Hence, we get -4a + 2b + 2a 2 0, which implies 4ab + 2a + 2b 2 0. Therefore, we get
( x x²) 4ab + 2a + 2h 2 0.
Then, we have x x--2-- x²) 0. Vx X and Ex" E 2", which means the MVI holds in this game.
J.2 Example of Games Satisfying the Weak MVI
The example is defined as following
A = (1 (11 B _ (2 !).
The unique NE of this game (learned by "Nashpy" (Knight and Campbell, 2018]) is
0
x; = (
a
1
This game violates the MII when
0..
00.9
0.3
Φ1 =
0.1
36

---

Formally, in this case, we have
10- (00.9)
(0.3 9) + -(-)
0.7 0)
0.3
00. 0)
-0.02 < 0,
0.3 1)
0.1 1
which violates the MVI.
Now, we show that the provided example satisfies the weak MVI. From Meng et al. [2025], for any smooth game, we have
(x))
max (L", x - x²) S C tan (x) = C1 min (xNx(()
||e + +211,,
æ'EX
where C1 a game deme-dependent constant. Recall the definition of the weak MVI
(e 2 - x²) 2 plleT + = =112, E
Therefore, if we can show that
(C x - -
(1 - (x))²
we can always find p -G ensure the weak MVI holds since Vz E Nxx
(x)" o'ex
(Car"""(((ar"""mm Ci
min
| +2 112- -
x' z'ENx(e)
and
(2, x x²) N 0.
Now, we show that (L", x x²) 2 (x))) holds in this game. We define the strategies of players as following
2o = ))
x1 = (.)
where 0 S a S 1 and 0 S b S
The loss gradient E" of player i is
e = Axi, Ef = - BUZOO x0.
Formally, for player 0, we have
Aa (-,
0 (
( b
1 1 b) -b b 1 - b) (1 2b
(-(1 - 2b) (2b)
-
2b - 1)
-b
c = Axi =
Similarly, for player 1, we have
(1
0
-1)
BT
1
BTuo- x
(1
-1 a
(a-(1
(
-(1 (11 a)
a (
1
a+ (1 (1-
1- a
C = B" x0 =
Now, we show (et x²)) - dg (z))² by showing (et x - x²) + (x))3 2 0 holds. We
first compute (Et, x x²). Formally, we get
a 1 a
0 =
a
x0 x
a
b
0 = -bb
2 - x =
1 1-b)
Next, calculate the dot products
2b -h ))
(C xo - x5) =
22b11 (-o)
= ab a(bb 1) = -3ab + a,
37

---

(0 z1)
-1 -1
1 -
(-b) b(1 a) + 6(1 a = b(2 a).
Combine the results
(E x - x²) = (C0: (60,20 20 - 2/) + (E9, 21 - xq} = -ab + a + 6(2 a).
This simplifies to:
(L x - x²) = -3ab + a + 2b ab = -ab + 2b + a.
Similarly, for (x) maX Ex (L", x x²); we get
max ø'EX
x x²) =fp mo) min 00 60 [1] + (f) m1) (in
which results
max (L", x xx 3--2')=-ab+-4k 20n---2ttamiim-266666 1 (an--b--)-ii(--oo-----a- -i --inb- EEE
Case 1: 1f0 afosbsl 3
(E" x=="""">>> +(r (x))²
= -bbb+bb++++ (-
is obviously if 4ab 2b + 2 0, 44a + 2b (-4ab 4b 1 + 2b 1)²
4ab + 2b + + (-4ab + 2b + aa² 2 Now, we show -4ab + 2b + a 2 0. Formally, we get
-aa 2b + (-4a + 2)6 a.
We can find that (-4a + 2)b + is linear function w.r.t b given fixed a. If 2 2 1 (-4a 2)b decreases b increases. Therefore, given 1 2 2 1. minogbs] (-4a 2 +4 +a -3 2 Similarly, 0 < a < 3. (-4a + 2)b + a decreases as decreases. Therefore, given 0sa< 51. mimogbs3 (-4a (- 2)6
2 0. Hence, we get 4ab + 2b + 2 0, which implies -4ab + a (-4ab 4b 1 2b 1)2 4ab 2b + a + (- 4ab 26 + a)² 0.
Case 2: 1b51,
(E" "="aa""" ((r0))(((0()))))) 1000
= +4
Now, we simplify the expression
- 4ab 26 -a (-4ab +5 1)?
Then,
(-4ab+5b+aa
=16a 2266b2222562211 -ad
So the full expression is
4ab 2b + + 2b2 256² + a² 40ab²² 8a²h 18ab 106 2a + 1.
Therefore, we define
f(a) (1662 8b 1)a² + ( (-406 14b 1)a 256² 86 +
For fa), given fixed b, it is quadratic function with respect to For the term 321 16b + 2, as takes the minimum value when b 61 4'
1 we have that the value of 326² 16b + increases as
b increases when < 1. Therefore, the minimum and maximum values of 32b 166 + 2 when
< S 1 are 32 3
16 + 2 = & and 32 16 + = 18, respectively. As 321² 166 + > 0, for
(a). given fixed so it takes the minimum value in the following case
4002
14b +
326² - 166 + + 2h + 2b 1
2 2b 1
321² 166 +
325² 16b +
321² 16b +
38

---

Algorithm 1 SEXRM
Require: Step size E (0, DI...
1: Initialize: 0: < 1/I EN
2: for 1, 1. do
3: for E do
8. g
4: 0 E arg min
0)),
110 2
5: end for
6: for i E N do
7: 0.+ E arg min
0, eall (onul((FFFF0 F((0+)), 0,) + (0,, 0)), at
0.+1
1
8: end for
9: end for
For the term 862 + 26 L, takes the minimum value when b 10 I 0, we have that the value of
8b² + 26 increases as increases when & S b 5 1. Therefore, the minimum value of 862 + 2/- 1
when 3 < b < 1 is 8 + 2 1 = Combining 812 + 2h 2 5 and 18 2 321² 16b + 2 2 2
g
have
2b
1
1.
325 166 +2 2
Therefore, given a fixed 6, f(a) takes the minimum value when = 1. Therefore, we get
f(1) = 16b² 8b + 1 - 406 14b + 256 - 8b + b² 2b + 0, sbs
Conclusion: Combining the results Case and Case 2, we have
x x +1)000000 (x:) (20)
Therefore, we get Vz Nx)(x),
x P x 1ー-21ー11 (rd(()=))))==
mmxx/e (L" x (--x'))²> -Cynann(C C? min xx
_ 12'+2
se' Ex
2 2-
In addition, from the definition of the normal cone, we have
(z. x²) 2 0, E (x(x)).
Combining the above results, we obtain
( z, x x²) 2 -(r" - + 2122, (x(x),
which means the weak MVI holds in this game with p -C7.
K Pseudocode of RM Variants Mentioned in This Paper
Now, we provide the pseudocode of RM+ variants mentioned in this paper. Specifically, the pseu- docode of SEXRM+, SPRM and SOGRM+ shown in Algorithms 2, and 3, respectively.
L Experiments
Configurations. We conduct experiments on (i) randomly generated two-player pero-sum matrix games with sizes [10, 20,50), 50), (ii) the normal-form representation of two extensive-form games, Kuhn Poker and Goofspiel, (iii) randomly generated three-player zero-sum polymatrix games with sizes [10, 20, 50), (iv) the games presented in Appendix J. and J.2, as well as (v) two Ledue Poker variants. The first three game types satisfy monotonicity [Pérolat et al., 2021]. while the games discussed Appendix
and J.2 satisfy MVT and weak MVI, respectively. The normal-form representations of the two extensive- form games are derived from the open-source code provided by
39

---

Algorithm 2 SPRM*
Require: Step size E (0, SDI...
1: Initialize: 0- 1/lAil. 0: t 1/le
2: for t 1,2.... do
3: for E N do
4: 0. 0
E arg min
0. E ((-F((0- 0:) + (0, 0.)
x,
1-
0
110, 1|
5: end for
6:
for E do
7: gt*1 arg min
8, E f (1-F((+*)),.) (0, 03)), at
0
10:
8: end for
9:
end for
Algorithm 3 SOGRM*
Require: Step size E 0, 2DT...
such that satisfies 1 2e 2012 > 0.
1: Initialize: 0 < 1/ 0 <- ViEN
2: for 2.... do
3: for E E do
4: 0 arg min D.ER la {( (--F((0--)). D0, 0,)
0
2;
110
5: end for
6: for N do
7: 0f+1 o - (0' (0(+))
8: end for
9: end for
Cai et al.
9a5BTasks%51 (2Ftasks)). The payoff matrices for Kuhn Poker and Goofspiel are of sizes [27, 64] and [72. 7808], respectively. The final game type is utilized to explore the performance of smooth RM+ variants in combination with counterfactual regret minimization (CFR) for solving extensive-form games (EFGs). We conduct the evaluation on Ledue Poker variants because PCFR+ the combination of PRM with the CFR framework, is found perform suboptimally in poker games such as Ledue Poker [Farina et al., 2021].
In the randomly generated three-player zero-sum, the payoff matrix for each pair of players is diagonal matrix, with each diagonal element sampled from a standard normal distribution. For randomly generated two-player zero-sum matrix and three-player zero-sum polymatrix games, each element of the payoff matrix is uniformly sampled from [-1, For each game size, we generate 20 instances and report the average duality gaps with variances. The duality gap, rd (æ:), used evaluate the distance NE, defined as ydy (x) = EiEN max,; (eT, x; - x.). As analyzed in Meng et al. [2025], the duality gap involves a lower bound of the tangent residual in smooth games, dd (x) S (z), where C₁ is game- dependent constant. Thus, if the tangent residual converges to O. the duality gap also converges to O. Due to the difficulty in precisely calculating the tangent residual, we do not use it as the metric. We compare smooth RM variants (SExRM+. SPRM and SOGRM*) with existing RM* variants (ExRM PRM and RM*), as well traditional last-iterate convergence OMD based algorithms- OGDA, EG, and OG* For initialization, we set 0; to 1 / and O for smooth and other RM+ variants, respectively. For OGDA, EG, and OG, the initial strategy the uniform strategy. For all tested algorithm, we use simultaneous updates since to our knowledge, the theoretical analysis of last-iterate convergence is based on simultancous updates. All experiments are performed on machine with an 19- 1991KK CPU and 128 GB memory.
*OGDA and OG are diffeernt algorithms. OGDA is an instance of Optimistic OMD [Rakhlin and Sridharan, 2013] where the regularizer is the Squared L2 norm. The meaning of "optimistic" varies in different papers. Using the terminology in Hsich et al. [2019]. OGDA is PEG and OG is OG.
40

---

101
10
10
10
1073
10a4
13a4
10
10
10-1
10
10-7
10
10
10
10
10
dine
10-1
10-
10-1
10-1
10
10"4
10-5
10"0
10
10"
101
13t
307
107
10F
15"
30
10a
10.
12
100
30
10"
104
10
191
oustt gi
10
10:
10:
10:1
10-1
10-
10-1
10
10
10P
15a
30
15
30
10t
10
10
10
104
10
15
30
10
10
307
10
35
10'
10
30
Eierationns
Seral
Ierations
SEtRRe*
SPRM
SDGEM
EXPM
RM
OGDA
->6-
DC
05
Figure 1: Performance of different algorithms on 10 x 10 (top), 20 x 20 (middle), 50 50 (bottom)
randomly generated two-player zero-sum matrix games.
107
10
101
131
Kalm
10-1
10
3.0
100
10
10
301
109
10-
10
101
10-
101
10-1
10
100
107
101
101
101
ougie gip
10-
10-7
10-7
10-3
10-1
10-3
10-
10-1
10-1
10-4
10-1
10
10a
30
10"
10
101
10
10
10"
10
104
101
15"
207
10"
107
101
10
122
10'
10a
107
Iteration
Rersdons
RoFazions
forations
SEanIe*
SPIM
SDGRM
Extl
1900"
OGDA
-X6
BG
06
Figure 2: Performance of different algorithms on Kuhn Poker (top) and Goofspiel (bottom).
Convergence performance on randomly generated two-player zero-sum games. The results are shown in Figure 1, smooth RM+ variants generally achieve at least similar performance compared to other algorithms. Specifically, OGDA, EG, and OG underperform relative to their smooth R.M counterparts (SPRM* SExRM* and SOGRM respectively) and are more sensitive parameters. For larger values (7) and = 10), OGDA, EG, and OG consistently diverge, while smooth RM+ variants maintain last-iterate convergence. Additionally, consistently achieve comparable performance to their corresponding non-smooth RM+ variants, namely P and ExRM respectively. Under optimal parameter settings, SPRM and SExRM significantly outperform PRM and ExRM+, respectively. More importantly, we find that our algorithm, SOGRM+. exhibits the fastest convergence rate and shows the least sensitivity to parameter changes. Moreover, for the reason why SOGRM* allows large 7 compared to other RM variants, we hypothesize that arises because our proposed algorithm, SOGRM* performs only a single prox- mrx-mapping operator per update step, unlike other smooth RM* algorithms, which involve two prox-mapping operations at each iteration (the prox-mapping operator introduced Section 3). The mrox-mapping operator in smooth RM+ variants involves a projection onto the simplex at some time (not always), which may lead significant changes in 0 depending on the choice of n, See more details in Appendix M.
observe that SPRM+ and SExRM
41

---

101
101
10
10P
10a
10-1
10
2.0
10
10
10
10.
10:1
10"4
10-4
10
10
10
10
10
10
10
10
10
10
2013
19
10:7
10
10-3
10-3
10-3
10-2
10-41
107
101
307
107
16F
169
30
109
10'
12
15
30
101
101
101
100
107
107
100
105
5/3
10-2
10-2
10
10
10
10
10
10
10F
12"
301
10
13F
10
102
10'
12F
105
10'
15t
307
10"
105
307
10
127
10"
15t
30
Hlerationss
Reral
ferations
SEERM
SPAM
SOGRM
ExPM
PRM
RM
0GD4
EG
0G
Figure 3: Performance of different algorithms on 10 x 10 (top), 20 x 20 (middle), 50 50 (bottom)
randomly generated three-player zero-sum polymatrix games.
36
18-1
26-1
13-
20-
3--
30-1
33-4
30-1
36
16
127
107
597 39'
187
127
157
39
127
157
30th
327
307
18"
107
Iterations
Iterationns
Berations
Feeaations
SEXRM
SPIM
SOGRM
ExiM
PRM
RM
OGDA
EG
Figure 4: Performance of different algorithms on the game satisfying the MVI provided in Ap-
pendix J.1. Notably, this games is very small, e.g., only two actions for each player.
Convergence performance on the normal-form representation of Kuhn Poker and Goofspiel. The results are shown in Figure 2. OGDA, EG, and OG exhibit poorer convergence performance and higher sensitivity to hyperparameters compared to their corresponding smooth RM+ variants (SPRM SExRM+, and SOGRM*, respectively). Moreover, observe that OG fails to converge in Goofspiel for any set of parameters. We hypothesize that this is due to the significantly larger scale of Goofspiel compared to the other games tested, requiring OG rate v) for convergence. In contrast, SOGRM* demonstrates lower sensitivity to hyperparameters, consistently exhibiting convergence across all parameter settings.
much smaller learning
Convergence performance on randomly generated three-player zero-sum polymatrix games. The experimental results are shown in Figure 3. Consistent with the results in Figure and Figure 2, the smooth RM+ variants generally exhibit superior convergence performance and reduced sensitivity to hyperparameters compared to their corresponding OMD algorithms. However, we also observe that the OG tends to diverge significantly when 7 2 1. contrast, SOGRM consistent with previous experimental findings, demonstrates low sensitivity to parameters and retains strong convergence even for 2 1.
Convergence performance on the games presented in Appendix J.1 and J.2. The experimental results are shown in Figures 4 and 5. Specifically. Figures and 5 are related the performance on the games that satisfy the MVI and weak MVI, respectively. Since these games are too small, all algorithms converge quickly. Note that we cannot test on larger games that only satisfy the MVI or weak MVI. This is because we need to prove that the game satisfies the MVI or weak MVI while failing to meet monotonicity, As shown Appendix even for games with only two actions for each player, this proof is quite challenging.
42

---

1011
36"0
37
10"1
30
307
207
13t4
L0
100
30"
10"
16
Itorations
Iterations
Rorations
Itarations
R-
G-
SEARM
SOGRM
Figure 5: Performance of different algorithms on the game satisfying the weak MVI provided in Appendix J.2. Notably, this games is very small, e.g., only two actions for each player.
Lodac Touer
14'
10
10/4
1910
107
120
127
100
18
37
127
327
36"
Laoue Fotee 10) erabbry
10p
12
10E
10
157
J6T
Do 15
Reratoos
Figure 6: Performance of different algorithms on Ledue Poker and Ledue Poker (5).
Convergence performance on Ledue Poker variants. RM+ variants are commonly integrated within the CFR framework to tackle EFGs. Consequently, evaluate the performance of our algorithm. SOGRM+, when combined with the CFR framework. This integrated method is referred as SOGCFR+ To validate its efficiency, SOGCFR is compared against algorithms that PCFR + SPCER+ and SExCFR + the combinations of CFR framework with PRM SPRM and SEXRM+ respectively. The Ledue Poker variants we tested are Ledue Poker and Ledue Poker (5). In Leduc Poker (5), the number of ranks is 5, whereas in Leduc Poker, is 3. The experimental results are shown in Figure 6. We observe that SOGCFR demonstrates superior robustness to varying step sizes compared to SPCFR+ and SEXCER+
M Discussion of the Reason Why SOGRM Allows Large 7) Compared to Other RM Variants
For the reason why SOGRM+ allows large compared to other RM variants, we hypothesize that arises because our proposed algorithm, SOGRM* performs only a single prox-mapping operator per update step, unlike other smooth RM+ algorithms, which involve prox-mapping operations at each iteration (the first occurrence the prox-mapping operator is in the introduction of OMD, Section 3).
Specifically, the mrx-mapping operator in smooth RM variants (such as SExRM* SPRM* and SOGRM*) involves a projection onto the simplex at some time [Farina et al., 2023] (not always as OMD algorithms), which may lead to significant changes in depending on the choice of In contrast, the update rule of SOGRM* (in the second line) omits this prox-mapping operator and instead relies solely on simple addition and subtraction operations. As result, the initial parameter Og may become negligible compared to the term (F). Thus, the values of 0 in
43

---

Table 3: The sequence of strategies generated by SExRM*
wta-0.01----
Steration
10,00,,0, 0.100000, 0,100000, O. 10000, O. 1000000, 100000 O. 0.100000, 0.100000, 0.100000, 00000000
iteration
[0.098431, 0.100056, 0.109717, 0.1064,,, 0,096661, 0.001065, 0.094224, 0.101697, 0.107110, 0.09406)
iteration 100
115888, 0.047936, 0.172965, 0.159585, 0,078784, 0,017979, O. 0.083801, 0.116942, 0.204308, 0.021778)
iteration 1000
[0.247108, 0.000000, 0.114474, 0.070481, 0,000000, 0.000000 O. 0.88866,, 0.185139, 0.298941, 0.000000
iterat.ion 10000
(0.289960, 0.000000, 0.144571, 0.049592, 0,024870, 0,0000,, O. 0808079,, 0.148601, 0.284808, 0.000000)
100000
[0.277022, 0.000000, 0.141075, 0.066758, 0.011324, 0.000000, 0.081305, 0.152016, 0.280411, 0.000000]
sta-0.1--...--.
iteratiion
10.300000, 0.100000, 0.100000, O. 10100000, 100000, 100000, O. 100000, 0.100000, 0.100000, 0.100000]
1teration 10
[o. 11538, 0.045286, 0.170913, O. 1585114,, 0,080181, 0,018597, O. 0.085E33, 0,117780, 0,205713, 0.0213753
iteration 100
[0.244506, 0.000000, 0.121762,, 0.065840, 0,000000, 0.000000, 080998, 0-180917, 0.290000, 0.000000]
iteratioo 1000
[0.271157, 0.000000, 0.144291, 0.052641, 0.017717, 0.000000, O. 0804227, O. 0.145175, 0. 0.284811, 0.000000
iteration 10000
10.271794, 0.000000, 0.142475, O. 0,054832, 0.012436, 0.00000, 083277, 0.150790, 0.284463, 0.000000]
1terstion 100000
[o. 271776, 0.000000, 0.142474, 0.054823, 0.012477, 0.000000 O. 0.08226, O. 0.150734, 0. 0.286490, 0.000000]
sta-I---
iterstion
[0. 100000 0.100000, 0.100000, O. 100000, O. 100000, 100000 O. 100000, O. 0.100000, 0.100000, 00000000]
iteratiion 10
[o. 15.250230, 0.000000, 0.161786, 0.057503, 000000 000000, 0,021202, 9.174680, 0.314690, 0.000000]
[o. 27,27217 0.000000, 0.107236, O. 0,031326, O. 0,012106, 0,00000, O. 0.090022, 0.173806, 0 0.300701, 0.000000]
iteration 1000
10.271736, 0.000000, 0.142928, O. 0.068319, 0.012477, O. 0.00000 0,892212, 0.149281, 0.282037, 0.000000]
iterstion
20.2/1/36 0-000000, 0.151669, 0 0.057013, 0.012677, 0.000000, O. 078898,, 9. 0.148728, 0. 0.201409, 0.000000]
itaration 100000
10.271736, 0.000000, 0.142670, O. 0,059823, 0.012077, O. 000000, 083326,, 0.180734, 0,290190, 0.000000]
eta-10--ee
iteration
[o, 100000, 0.100000, 0.100000, O. 100000, O. 100000, 100000 O. 100000 O. 100000, O. 0010000, 100000
iteration
[0.299329, 0.000000, 0.000000, 0.000992, 0,02938,, 0,00000, O. 153818, 197011 0.310061, 0.000000]
1terstion 100 [o. 267800, 0.000006, 0.142353, 0.054206, O. 0.019992, O. 000000 O. 0.088032, 0.178121, O. 0.270836, O. 0.00000]
iterstion 1000
20,20200, 0.000000, 0.142674, 0.069823, 006611, 000000 0888722,, 1187777 0.299029, 0.000000]
iteration 10000
[o. 27008, 0000000, 0.142070, 0.052923, 0.013262, O. 000000, 0808289, 1.1111,, O. 263207 0.000000]
iterstion 100000
[0. 280386, 0.000000, 0.142676, 0.056828, 0.006B91, 0,000000, O. 0.0966E, 0.118, 0.301383, 0.000000)
SOGRM are likely to vary in direct proportion to 1j, and the resulting strategy x; = 0 will exhibit a more stable behavior with respect to changes in 1). Therefore, for different values of the sequence of strategies generated by SOGRM* exhibits small differences. Moreover, when n is small, Theorem 6.1 guarantees thatthe sequence of strategies produced by SOGRM* converges to the set of NE. Consequently, SOGRM* permits the use of larger 1) values compared to other algorithms.
To validate our statement, as demonstrated in Appendix L., we conducted evaluations on 20 randomly generated 10-dimensional two-player zero-sum matrix games. Specifically, analyzed the strategies of Player 0 output by SEXRM* SPRM+, and SOGRM+ at iterations 1, 10, 100, 1000, and 10,000. averaged the strategies across the 20 instances. The results clearly show
To mitigate randomness, that for different values of the sequence of strategies generated by SOGRM+ exhibits minimal variation. Notably, when 1) and the number of iterations 2 1000, the strategies produced by SOGRM* are nearly identical across different values of This behavior is not observed in the other two RM* + variants.
44

---

Table 4: The sequence of strategies generated by SPRM
Stam0.01----..
iterstion
10000, 0.100000, 0,100000, O. 1010000, 10000,0, O. 100000 0,100000, 0.100000, 0.100000, 0.100006]
iterstion 10
090491, 0.100056, 0-109718, 108064 O. 0900811, 0,091065, 0.09224, 0.101197, 0.10/110, 0.099196]
iteration 100
[0.115090, 0.067986, 0.172965, O. 0.189685, 0,078764, 0.017872, 0,063001, 0161691,, 0,20630,, 0.021776]
Steration 1000
10.247107, 0.000000, 0.110070, 0.070CB1, 0,00000, 00000, O. 0,0828E,, 0.186139, 0.299941, 0.000000
iterstion 10000
(0.289360, 0.000000, 0.166571, 0.043592, 0,024870, 0,000000, 080807,, 0.105601, 0.2BIBLO, 0.000000)
iteration 100000
10727722,, 0.000000, 0.141078, 0.066768, 0.011329, 0,00000, 0.001394, 0.152016, 0.200811, 0.000000]
1ta=0_1--------..
itcration
[0. 10000, 0.100000, 0.100000, O. 1000000, O. 100000, 100000 O. 100000, O. 0.00000,, 0.10000C, 0.100000
iteration 10
10.310372, 0.045123, 0.170807, 0.189184, 0800206, 01011,,,, 06066TL1, 0.11776,, 0.206911, 0.021236]
iteration
264321,, 0.000000, 0.121177, 0.065578, 0,00000, 0,000000, O. 08988, 0.1802E3, 0. 0989683, 0.000000
iteration 1000
(0.271172, 0.000000, 0.144289, 0,052646, 0.017681, 0,00000, 0.086166, 0.145199, 0.284817, 0.000000
iteration 10000
[0.271786, 0.000000, 0.142475, 0.054831, 0.012437, 0,000000 O. 0838275, 0.150721, 0.284465, 0.000000]
Iteration 100000
(0.271736, 0.000000, 0.142670, 0.054923, 0.012077, 00000,, 083266,, 0.150734, 0.290080, 0.000000
Steration
10,00,,00, 0.100000, 0.100000, O. 10000, 0. 10000, 100000 O. 100000 100000 0000000, 100000
iteration
[0.237656, 0.000000, 0.000000, O. 0.000000, 0,000000, 0,00000, 236226, 0.203216, 0.322808, 0.000000
iteration 100
(0.277597, 0.000000, 0.137955, 0.053723, 0,009448, O. 000000 0,085151, 0.122804, 0.315621, 0.000000
iteration 1000
[0.261815, 0.000006, 0.142474, O. 0.054825, 0.019802, 0.000000 0.088261, 0.188105, 0.288779, 0.000000]
steration 10000
[0. (8.285631, 0.000000, 0.142474, 0. 0.054823, 01613000 000000 O. 0,B6E,,, 0.180080, 0.270984, 0.000000
iteration 100000
10.288516, 0.000000, 0.142474, 0.054828, 0.015538, 0.00000, 0.072873, 0.173694, 0.274082, 0.000000)
cta-10-------.
iteration [o. 100000, 0.100000, 0.100000, 0.000000, 100000, 100000, O. 100000, 0.100000, 0.100000, 0.10000)
iteration
227514, 0.000000, 0.000000, O. 0.000000, 0,085267, 0.000000, O. 172873, 0.28855,, 0.275688, 0.000000
Iteration 100
0.000000, 0.138079, 0.053706, 0.000000, iteration [0. 272122,,, 0.000000, 0.142474, 0.054823, 0,013019, 0,00000, O. 0836622, 0.145232, 0.288666, 0.000000)
0.122853, 0.318094, 0.000000]
itaration 10000
185285000, 0.000000, 0.142474, 0.054823, 0.018434, 000000, O8DE0S, 0.180184, 070707 0.000000)
iteration 100000
[o. 2674674, D. 0000000, 0.142474, O. 0508522, O. 0.015058, 000000, O. 0.079488, O. 1817776, 0.278027, 0.000000]
45

---

Table 5: The sequence of strategies generated by SOGRM
Stam0.01----..
iteration
10000,,,,, 0.100000, 0,100000, O. 1010000, 10000, O. 100000 0,100000, 0.100000, 0.100000, 0.100006]
iterstion 10
090099, 0.100078, 0.108764, O. 1010522 O. 090983, 0.091863, 0.096790, 0.101526, O. 0.106359, 0.096076]
iteration 100
[0.115373, 0.049576, 0.172920, O. 05188112, 0,078077, 0.010314, 0,063767, 0.117009, 0,20326,, 0.022001]
Steration 1000
20.247102, 0.000000, 0.110000, 0.070508, 0,00000, 0,0000 O. 0,082918, 0.185222, 09999949, 0.000000
iterstion 10000
(0.289351, 0.000000, 0.166571, 0.043631, 0.026661, 0,00000, 08080,60, 0.145696, 0.280880, 0.000000
iteration 100000
10/277113, 0.000000, 0.141079, 0.066768, 0.011326, 0,00000, 0.001001, 0.152020, 0.200009, 0.000000]
1ta=0_1--------.
itcration
[0. 10000, 0.100000, 0.100000, O. 1000000 O. 100000, 100000 O. 100000, O. 0.100000, 0.10000C, 0.100000
iteration 10
[o. 109635, 0.050B11, 0.168679, 1519994, 0808209,, 02023266, 067661,, 0.11709C, 091900 0.026326]
iteration
[o. 26406, 0.000000, 0.121463, 0.066806, 0,00000, 0,000000, O. 0888862,, 0.190912, 0.298127, 0.000000
iteration 1000
(0.271160, 0.000000, 0.144287, 0.052636, 0.017740, 0.00000, 0.08407, 0.145153, 0.284977, 0.000000
iteration 10000
[0,271800, 0.000000, 0.142475, 0.054831, 0,012428, 0,000000 O. 0838271, 0.150721, 0.284465, 0.000000]
Iteration 100000
(0.271736, 0.000000, 0.142670, 0.054923, 0.012077, O. 000000 0832666, 0.150734, 0.290080, 0.000000
Steration
100000 0.100000, 0.100000, O. 10000, 0. 10000, O. 100000, O. 100000, 100000 000000 100000
iteration
10.543554, 0.000000, 0.000000, 0.019366, 0,081302, 0,050507, 185077, 0.274010, 0.246277, 0.010868)
iteration 100
(0.272928, 0.000000, 0.142018, 0.055096, 0,011850, O. 000000 O. 0,079330, 0.152486, 0.287385, 0.000000
iteration 1000
[0.271736, 0.000006, 0.142474, 0.054823, 0.012477, 0.000000, 0.083287, 0.150733, 0.284480, 0.000000
steration 10000
(0.271736, 0.000000, 0.142474, 0.054823, 0.012477, 0. 00000, O. 0.38226,, 0.150734, 0.286090, 0.000000
iteration 100000
[0.271736, 0.000000, 0.142474, 0.054828, 0.012477, 0.00000, 0.883266, 0.150734, 0.284490, 0.000000
sta-10-------.
iteration [o. 100000, 0.100000, 0.100000, 00000000, 100000 100000, O. 100000, 0.100000, 0.100000, 0.10000)
iteration
[o. 13045, 0.013191, 0.080858, O. 134699, 0.000882, 0.016938, O. 0404220, 0.176526, 0.271009, 0.013515)
Iteration 100
06.8678 0.000000, 0.142787, 0.053852, 0.014896, iteration [0. 27.77,,,,, 0.000000, 0.142474, 0.054823, 0.012477, 0,00000, O. 0833266, 0.156734, 0.284490, 0.000000)
0.150829, 0.288519, 0.000000]
itaration 10000
20.27, 0.000000, 0.142474, 0.054823, 0.012477, 0.00000,, 0808286, 0.150734, 284400, 0.000000)
steration 100000
[o. 271736, 00000000, 0.142474, O. 0508522, 0.012477, O. 0.00000, O. OR086, O. 150734, O. 082844 0.000000]
46


Reviews:
[{"review_id": "uOvyNBltcT", "reviewer": "Reviewer_fkfR", "summary": "The authors propose a systematic method for proving convergence (both last-iterate and best-iterate rate) of smooth Regret Matching+ variants to the set of Nash equilibria in smooth concave games satisfying the weak Minty Variational Inequality (w-MVI). They leverage this method to prove convergence of two known algorithms under MVI, and of a newly-proposed algorithm under w-MVI. Experiments show that the newly-proposed algorithm outperforms existing ones.\n\nMore specifically:\n- The w-MVI -- the weakest condition among those assumed to prove convergence of RM+ variants -- loosely means that the game's loss gradient \"points sufficiently away\" from the equilibrium. The key challenge in leveraging the (weak) MVI to prove convergence is that RM+ variants update in (a subset of) the cone of original strategies, taking as input a *transformed* loss gradient which does not fulfil the (weak) MVI. The question then becomes how to recover the (weak) MVI.\n\n- To do so the authors recast a smooth RM+ instance as a generalised Online Mirror Descent instance updating in the strategy space itself and operating on the original loss gradient of the game, which does fulfil the (weak) MVI (Eqs. 4-5).\n\n- This reformulation allows to upper-bound a certain notion of distance between a strategy generated by a smooth RM+ variant and the set of Nash equilibria by the distance between consecutive iterates generated by the algorithm (Eq. 6).\n\n- The (weak)-MVI is then leveraged to show that said distance between consecutive iterates generated by the algorithm converges to zero for sufficiently small learning rates (Theorems 5.2, 5.3, 6.2).\n\n- This allows to prove last-iterate convergence and best-iterate convergence rate for existing RM+ variants under MVI (Theorem 5.1), and for the newly-proposed algorithm under w-MVI (Theorem 6.1).\n\nAn important characteristic of the newly-proposed algorithm is that it performs a single prox-map call per iteration (in the auxiliary step), while the main update step relies on a simple sum between the auxiliary iterate and the difference between transformed losses (Eq. 12).", "questions": "### Major\n- You do a lot of work to recast a RM+ instance as an OMD instance, where the (weak) MVI holds. Why not work with OMD in the first place then?\n- I find it interesting that the equivalence between a RM+ variant and an OMD variant can be established only for the generalized OMD of Joulani et al. and Liu et al. (Eq. 1), with a time-dependent Bregman term and an additional time-dependent regularization term. Why is this the case? More specifically:\n\t- what can you say about RM+ variants under other regularizers than the quadratic one? (line 194)\n\t- could the time-dependent $f_i$ and $h_i$ terms in eq. 5 (generalized OMD) be effectively captured by a fixed, non-quadratic regularizer in a standard OMD setting, or is their time-dependence crucial in establishing the equivalence with RM+?\n\t- In which sense are exactly the updates given by Eqs. 4 and 5 *equivalent*? I have not gone through the details of Appendix A, but it seems reasonable that $(4) \\implies (5)$. However, I do not see how it can be $(5) \\implies (4)$, since $(5)$ depends on the iterates generated by $(4)$ (as one cannot recover univocally $\\theta_i^t$ from $x_i^t$). Can you elaborate on this?\n- Can you provide further motivation / intuition / discussion around the design of the main update step of your algorithm (second line of eq 12)? In particular, it might be useful to add in the body a brief pointer to appendix I and J, where you conjecture that the relatively larger $\\eta$ allowed by your algorithm is related to the single prox-map call per step.\n- Can you see a generalization of your framework to smooth games played on generic convex compact sets (as opposed to the particular case of the simplex)?\n- Can you provide a counter-example of a game not fulfilling the w-MVI, in which your algorithm does not converge?\n\n\n### Minor\n- line 119: inconsistency on the dimension of $\\mathcal{X}_i$\n- l. 124, add comment on the fact that the upper bound $P$ on losses comes wlog\n- l. 128, consider making explicit mention to the Stampacchia variational inequality\n- l. 138, consider giving a more classical reference for monotone games, as [1]\n- l. 141: monotone games always admit a unique NE [1, 2]\n- l. 146: \"we provide an example...\" seems to fit better in the following paragraph\n- l. 679: the game admits also bottom-right -- $((0,1), (0,1))$  --  as pure, non-strict NE. \n- The argument \"in games satisfying the (weak) MVI the feedback of RM+ does not satisfy the (weak) MVI\" appears throughout the paper a few times (e.g. lines 6-9, 53-55, ...). The phrasing is not immediately clear at a first read; consider rephrasing it, for example along the lines of \"even if the game's loss satisfies the (weak) MVI, RM+ operates on a *transformed* loss which does not satisfy it\", or analogue.\n- a few minor typos and syntactical issues (e.g. *\"is the players\"* line 121,  *\"at sometimes\"* lines  801, 843, *\"such that that ensures\"* line 305, etc. )\n\n---\n[1] Rosen JB (1965) Existence and Uniqueness of Equilibrium Points for Concave N-Person Games. _Econometrica_ 33(3):520–534.\n\n[2] Mertikopoulos P, Zhou Z (2019) Learning in games with continuous action sets and unknown payoff functions. _Math. Program._ 173(1–2):465–507.", "limitations": "- The authors acknowledge the fact that the notion of convergence employed assures to reach the set of Nash equilibria - where the iterates may wander rather than settling at a specific point (Caption of Table 1)\n- The authors are encouraged to highlight further limitations of their work.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- investigating the convergence to Nash equilibria under the weak MVI is a challenging and worthy research project to pursue. The proposed algorithm is the first RM+ variant to achieve both last-iterate and finite-time best-iterate convergence to the set of NE under the weak Minty variational inequality.\n- experiments show that the proposed algorithm significantly outperforms existing ones across a variety of settings; displays a relatively low sensitivity to hyper-parameters; and allows for a relatively big learning rate.\n- the proposed proof paradigm seems flexible and powerful; it can be employed to show both last-iterate convergence and best-iterate convergence rate across a variety of RM+ settings. It stems from a novel combination of existing techniques, and it lends itself to fruitful applications from the community.\n- the authors exhibit a fine understanding of the problem, and accurately cite the related existing literature upon which their work is based.\n- the claims are technically sound and well-supported by detailed proofs.\n- the paper is well structured and organised. It provides in a nutshell a zoom-in from the setting of online convex optimization to that of smooth RM+ variants that can bring on board also a reader unfamiliar with the literature; it presents the proof paradigm in a concise way; and it applies it effectively.\n\n\n### Weaknesses\n- The main update step of the proposed algorithm (second line of Eq. 12) would benefit from further motivation / intuition / discussion (cf question below)\n- the authors do not address possible weaknesses or limitations of their setting\n- there are throughout a few minor typos and syntactical issues", "was_revised": true, "final_justification": "The authors have addressed all of my questions. I thereby confirm my rating.", "rebuttal": "**To Reviewer fkfR**\n\n\n\nWe sincerely thank you for your feedback and insightful comments.\n\n\n\n**Q1: Why not work with OMD in the first place then?**\n\n**A:** The primary reason is that there is no OMD instance capable of updating in the same manner as RM+ variants. Specifically, as mentioned in **Q2.3**, there exists a transition from $(4) \\to (5)$, but not from $(5) \\to (4)$. In other words, to obtain the strategy for the next iteration, we must use the update rules of RM+ variants instead of those of OMD.\n\n\n\n**Q2.1: what can you say about RM+ variants under other regularizers than the quadratic one?**\n\n**A:** This is a interesting idea. However, we have not yet tested the algorithm under these conditions. We will consider this as one of our future research directions.\n\n\n\n\n**Q2.2: Is the time-dependence of $f_i$ and $h_i$ crucial in establishing the equivalence with RM+?**\n\n**A:** Yes, you are correct. To establish the equivalence between OMD and RM+ variants, $f_i$ and $h_i$ must vary with time.\n\n\n\n**Q2.3: In which sense are exactly the updates given by Eqs. 4 and 5 equivalent? It seems reasonable that $(4) \\to (5)$. However, I do not see how it can be $(5) \\to (4)$?**\n\n**A:** You are correct that the transformation is unidirectional: $(4) \\to (5)$ holds, while $(5) \\to (4)$ does not. In fact, the term \"equivalence\" used in Liu et al. 2022 is not entirely precise. Therefore, in Section 1 Introduction, we use the term \"transformation\" instead of \"equivalence.\"\n\n\n\n**Q3: Can you provide further motivation / intuition / discussion around the design of the main update step of your algorithm (second line of eq 12)?**\n\n**A:** The intuition for the update step in Eq. (12) is: our proposed algorithm, SOGRM+, can be viewed as a momentum-based method, conceptually similar to Adam. Specifically, the update in Eq. (12) is equivalent to\n\n$${{\\theta}}^{t+\\frac{3}{2}}\\_i \\in \\arg min\\_{{{\\theta}}\\_i \\in \\mathbb{R}^{|A\\_i|}\\_{\\geq 1}} \\{ \\eta \\langle  -{{F}}\\_i({{\\theta}}^{t+\\frac{1}{2}}) - ({{F}}\\_i({{\\theta}}^{t+\\frac{1}{2}}) -  {{F}}\\_i({\\theta}^{t-\\frac{1}{2}}), {{{{\\theta}}}}\\_i\\rangle + D\\_{\\psi} ({{{{\\theta}}}}\\_i, {{{{\\theta}}}}^{t+\\frac{1}{2}}\\_i) \\}$$\n\nIn this context, ${{F}}_i({{\\theta}}^{t+\\frac{1}{2}}) - {{F}}_i({\\theta}^{t-\\frac{1}{2}})$ acts as a momentum term. More precisely, it represents the trend of change in ${{F}}_i$ over the two most recent iterations, analogous to the \"acceleration\" of ${{F}}_i$. This can be likened to a ball rolling down a hill; as acceleration accumulates, its velocity increases, allowing it to reach the bottom more swiftly.\n\nThe formulation in Eq. (12) is primarily to reserve the structural similarity with the update rules of SExRM+ and SPRM+ in Eq. (2) and (3).\n\n\n\n**Q4: Can you see a generalization of your framework to smooth games played on generic convex compact sets (as opposed to the particular case of the simplex)?**\n\n**A:** To extend to generic convex compact sets, we can modify Phase 1 of our proof paradigm. We can utilize the definition of the cone (line 178) rather than the equivalence (or transformation) used in this paper. Specifically, we do not prove whether $(4) \\to (5)$ holds, while obtain the third line of Eq. (6) using the cone's definition.\n\n\n\n**Q5: Can you provide a counter-example of a game not fulfilling the w-MVI, in which your algorithm does not converge?**\n\n**A:** We can provide examples of games not fulfilling the $\\rho$-weak MVI in Theorem 6.2, where our algorithm does not converge. Specifically, in some randomly generated two-player general-sum normal-form games, our algorithm does not converge. According to Theorem 6.2, our algorithm is guaranteed to converge if $\\rho > -\\frac{1}{12\\sqrt{3}D\\sqrt{2P^2+4L^2}}$. Therefore, these multi-player normal-form games inherently do not meet the $\\rho$-weak MVI criteria stipulated by Theorem 6.2.\n\nSpecifically, for such a randomly generated two-player general-sum normal-form game, each player has 20 actions. The payoff matrix for each player is generated using the following python code:\n\n```\nimport numpy as np\nimport random\n\nnp.random.seed(3)\nrandom.seed(3)\nPlayer_0_payoff_matrix = np.random.random(size=(20,20))*2-1\nPlayer_1_payoff_matrix = np.random.random(size=(20,20))*2-1\n```\n\n\n\n**L1: The authors are encouraged to highlight further limitations of their work.**\n\n**A:** We agree with you that a more explicit discussion of limitations would strengthen the paper. From our perspective, beyond the limitations discussed in our paper, the most significant limitation lies in the absence of proof regarding the convergence of RM+ variants within extensive-form games. Typically, RM+ variants are integrated with the counterfactual regret minimization (CFR) framework to address extensive-form games. This constitutes one of our future research directions. Moreover, it should be clarified that proving convergence within extensive-form games presents considerable difficulty."}, {"review_id": "wsz0iLYG44", "reviewer": "Reviewer_R6vq", "summary": "This paper studies the last-iterate convergence properties of Regret-Matching+ (RM+) based algorithms in games. Recent works have established that in two-player zero-sum matrix games (1) the non-convergence of several popular variants, including RM+, alternating RM+, and PRM+; (2) last-iterate convergence of several smooth variants of RM+, including ExRM+ and SPRM+, where the decision set is truncated to ensure Lipschitzness of the regret operator. This paper's main contribution is to extend the convergence results of ExRM+ and SPRM+ to games satisfying the MVI condition, a class of games that encompasses two-player zero-sum games as a special case. This paper presents a new analysis framework based on (1) an equivalence between the RM+ type updates on the truncated positive orthant and the OMD type update on the simplex; (2) a proximity measure to Nash equilibria called tangent residual that upper bounds the duality gap. Using the new analysis framework, this work also generalizes the Optimistic Gradient (OG) algorithm to an RM+ based algorithm called SOGRM+, which has best-iterate convergence rates and asymptotic convergence to the set of Nash equilibria even in games with a weak MVI condition.", "questions": "1. Can you provide some intuition behind the equivalence between (4) and (5)? \n2. It is mentioned as future work that \"Future directions involve integrating our proof paradigm with other OMD algorithms, such as Reflected Gradient [Hsieh et al., 2019] and composite Fast Extra-Gradient [Cai et al.,2024], to develop novel RM+ variants that achieve stronger last-iterate convergence.\" Why does the current proof paradigm not directly extend to the Reflected Gradient or the composite Fast Extra-Gradient algorithm? Is it possible to use the equivalence between (4) and (5) to give RM variants of these two algorithms? If not, what might be the obstacles?\n\n\nMinor comment:\n1. \"As shown in Meng et, al. [2025], the tangent residual is as an upper bound for the duality gap, $\\dots$\". In this sentence, \"as\" is redundant. Besides, the fact that tangent residual upper bounds the duality gap is proved in Lemma 2 in [Cai et. al., 2022], where they refer to the duality gap as the total gap function.", "limitations": "Yes (partially). The authors provide the assumptions of their theoretical results, but do not give an explicit discussion on the limitations of their approach.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n1. This work studies the convergence properties of regret matching (RM)-type algorithms. This is an important question since regret matching (RM)-type algorithms (integrated with the CFR framework) are popular in practical game-solving. Although the average-iterate convergence rates of RM-type algorithms have been extensively studied, their last-iterate convergence properties have only been studied recently, and results are limited to the two-player zero-sum games setting. This work extends the convergence properties of the recently proposed smoothed RM+ variants, including ExRM+ and SPRM+, from two-player zero-sum games to general concave games that satisfy the MVI condition. \n2. This paper proposes an interesting proof paradigm that is based on (1) an equivalence between the RM+ type updates on the truncated positive orthant and the OMD type update on the simplex; (2) a proximity measure to Nash equilibria called tangent residual that upper bounds the duality gap. The main difficulty for analyzing RM-type algorithms is that the regret operator, unlike the gradient operator, may not be monotone or even satisfy MVI. The new proof paradigm overcomes this difficulty by translating the RM updates back to OMD updates on the simplex; thus, nice properties of the gradient operator can be used. Moreover, this proof paradigm is quite flexible, as the paper also extends another OMD-type algorithm, the Optimistic Gradient (OG) algorithm, to an RM-type algorithm called SOGRM+. The original analysis of OG can be reused to prove that SOGRM+ converges under weak MVI. \n\nWeakness:\n1. This paper's presentation could be improved. One particular example is the proof paradigm, which is the main technical contribution of the paper. It is claimed that the smooth RM+ variant can be transformed into an OMD instance, and an equivalence of the two updates is presented. However, in the main body,  there is no further explanation on why the equivalence holds or the intuition behind the equivalence. The OMD in equation (5) is also non-standard as it has both $f$ and $h$, making it unclear why (5) is equivalent to (4). Since this proof paradigm lays the foundation for subsequent analysis, a more detailed discussion would be helpful.", "was_revised": true, "final_justification": "I thank the authors for the response that addressed my questions. It would be helpful to add the intuition that both projecting onto the simplex and projecting onto the truncated positive orthant can be written in a unified way using the max operator. This would help the reader understand the equivalence between the RM+ update (4) and the OMD update (5).\n\nI maintain my rating after reading other reviewers' discussions on the weaknesses mentioned: the proof paradigm works for weak MVI, but only for a smaller range of problems; the guarantee would degenerate to MVI as the diameter of the set becomes very large.", "rebuttal": "Thank you for your positive and encouraging feedback on our work.\n\n\n\n**Q1: Can you provide some intuition behind the equivalence between (4) and (5)?**\n\n**A:**  The intuitive explanation is straightforward—both update rules in Eq. (4) and Eq. (5) can be expressed as a $[\\cdot]^+ = \\max(\\cdot, 0)$ operation. Specifically, Eq. (4) is represented as Eq. (18) in Appendix A, while Eq. (5) corresponds to Eq. (20) in Appendix A. The update rules in Eq. (18) and Eq. (20) feature the $[\\cdot]^+$ operation, even encompassing terms such as ${\\theta}_i^{t_0}$ and $-\\eta \\ell^{t_1}_i$ within the square brackets.\n\n\n\n**Q2: Why does the current proof paradigm not directly extend to the Reflected Gradient or the composite Fast Extra-Gradient algorithm? Is it possible to use the equivalence between (4) and (5) to give RM variants of these two algorithms? If not, what might be the obstacles?**\n\n**A:** There are no obstacles. By using our proof paradigm, we can get $r^{tan}(x^{t_2}) \\leq \\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2$ for RM variants of these two algorithms. \n\nThe main challenge lies in proving $\\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2 \\to 0$ after deriving $r^{tan}(x^{t_2}) \\leq \\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2$. The proof of $\\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2 \\to 0$ is not part of our proof paradigm as $\\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2 \\to 0$ is the inherent nature of the specific algorithm.\n\n\n**L1: The authors provide the assumptions of their theoretical results, but do not give an explicit discussion on the limitations of their approach.**\n\n**A:** In addition to the limitations mentioned in in our paper, the most significant limitation lies in the absence of proof regarding the convergence of RM+ variants within extensive-form games. Typically, RM+ variants are integrated with the counterfactual regret minimization (CFR) framework to address extensive-form games. This constitutes one of our future research directions. Moreover, it should be clarified that proving convergence within extensive-form games presents considerable difficulty."}, {"review_id": "l6DTeLsPO7", "reviewer": "Reviewer_FFZt", "summary": "This paper investigates Regret Matching like algorithms in the context of Minty Variational Inequalities and weak Minty variational inequality.\nThey start considering a new analysis in the MVI setting of algorithm that already appeared in the literature like Smooth Extra-gradient RM+ (SExRM+) and Smooth Predictive RM+ (SPRM+). The new analysis crucially relies on a new reduction from RM+ to OMD whioch allows to show last iterate convergence to Nash exploiting the variational characterization of it.\nOf particular importance in the reduction is that the feedback used by the algorithm satisfies the MVI condition.\n\nUsing this new reduction, the authors introduce. a new algorithm Smooth Optimistic Gradient Based Regret Matching+ (SOGRM+) which is shown to achieve last iterate convergence in the weak MVI setting for large enough $\\rho$.Moreover a finite time rate is proven for the best iterate.", "questions": "In equation 6, how do you make sure that h is differentiable in $x^{t_2}_i$ and $x^{t_0}_i$ ?\n\nCan you please relate more with the existing literature in the weak MVI setting. It would be useful to include a table with other existing results in particular to compare the range of $\\rho$ ?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "***Strengths***\nThe paper is well written and easy to follow. It is nice that you could include proof sketches in the main text.\n\n***Weaknesses***\n\nNothing major, but the minimum $\\rho$ depends on the inverse of the maximum number of actions $D$ and on $L_u$. The authors should comment on the fact that the range tolerated by other algorithms is bigger up to $\\rho > -1/2$ ( see for example https://openreview.net/pdf?id=Y7slJZPGCy ).", "was_revised": true, "final_justification": "My score remains unchanged.\n\nI thank the authors for sending a table comparing the different ranges allowed for $\\rho$. Hope this can be includer in the final version.", "rebuttal": "Thank you for your positive assessment and helpful suggestions.\n\n\n\n**Q1: In equation 6, how do you make sure that h is differentiable in $x^{t_2}_i$ and $x^{t_0}_i$?**\n\n**A:** To begin with, the function $h_i(x_i)$ is defined as $h_i(x_i)=\\frac{\\Vert \\theta^{t_0}_i \\Vert^2_2}{\\eta}\\psi(x_i)$, where $\\frac{\\Vert \\theta^{t_0}_i \\Vert^2_2}{\\eta}$ is a constant. The term $\\psi(x_i)$ is the quadratic regularizer $\\Vert x_i \\Vert^2_2$ that is differentiable for any $x_i \\in \\mathbb{R}^n$. Consequently, $h$ is differentiable with respect to both $x^{t_2}_i$ and $x^{t_0}_i$.\n\n\n\n**Q2:  It would be useful to include a table with other existing results in particular to compare the range of $\\rho$?**\n\n**A:** Thank you very much for your suggestion. We think adding this table will greatly improve the clarity of our paper. This table is provided below. Given that we focus on the constrained setting, we only present the comparison within this context. Although we acknowledge that other algorithms tolerate a broader range of $\\rho$, existing work primarily focuses on OMD algorithms. We are the first to investigate the last-iterate convergence of RM+ variants in games that satisfy the weak MVI. \n\n|                         |              Minimum $\\rho$              |  Algorithms  |\n| :---------------------: | :--------------------------------------: | :----------: |\n|  Cai and Zheng (2022)   |         -$\\frac{1}{12\\sqrt{3}L}$         | OMD Variants |\n|  Pethick et al. (2023)  |             -$\\frac{1}{2L}$              | OMD Variants |\n| Alacaoglu et al. (2024) |              -$\\frac{1}{L}$              | OMD Variants |\n|    Cai et al. (2024)    |             -$\\frac{1}{2L}$              | OMD Variants |\n|  Pethick et al. (2025)  |              -$\\frac{1}{L}$              | OMD Variants |\n|          Ours           | $-\\frac{1}{12\\sqrt{3}D\\sqrt{2P^2+4L^2}}$ | RM+ Variants |\n\nAdditional References:\n\n1. Ahmet Alacaoglu, Donghwan Kim, and Stephen J Wright. Extending the reach of firstorder algorithms for nonconvex min-max problems with cohypomonotonicity. arXiv preprint arXiv:2402.05071, 2024.\n2. Pethick, Thomas, Ioannis Mavrothalassitis, and Volkan Cevher. \"Efficient Interpolation between Extragradient and Proximal Methods for Weak MVIs.\" *The Thirteenth International Conference on Learning Representations*, 2025."}, {"review_id": "e3DDkUj0ow", "reviewer": "Reviewer_ihpx", "summary": "This paper studies several variants of smooth regret matching+ variants for learning NE in a class of games that satisfy MVIs. In the case of SExRM+ and SPRM+, two known algorithms from the literature, the authors provide last and best-iterate convergence results to the set of NE in games with the MVI property. Furthermore, a variant of RM+ called Smooth Optimistic Gradient-Based (SOGRM+) is proposed, and is shown to converge in the last and best-iterate sense to the set of NE in weak MVI games, a superset of MVI games. The key technique used to prove these results is showing that these RM+ variants can be transformed into instances of a general online mirror descent paradigm, which allows the authors to use tools from OMD literature to derive the convergence results.", "questions": "- In [1], they used the tangent residual not only as a proxy for the distance to NE, but also as a method to create a potential function for the dynamics, thus showing last iterate convergence. Would it be possible to extend similar ideas to the set of games with the MVI/weak MVI property (i.e., deriving a potential function as a function of the tangent residual)? More broadly, what properties of the tangent residual can be studied to give more results compared to the standard duality gap?\n\n- In the experiments section of Appendix I, it is stated that all existing works on RM+ variants focus on simultaneous updates. However, in Cai et al 2025 it is shown that alternating RM+ may cycle instead of converging to the NE. I would be curious to know if your proof technique can be used to study alternating variants SExRM+/SPRM+/SOGRM+ in games with MVI/weak MVI and potentially show last/best iterate convergence.\n\n[1] Cai, Yang, Argyris Oikonomou, and Weiqiang Zheng. \"Finite-time last-iterate convergence for learning in multi-player games.\" Advances in Neural Information Processing Systems 35 (2022): 33904-33919.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper shows strong last iterate convergence results for a broader class of smooth games than was previously known, alongside the introduction of SOGRM+. The method of transforming the RM+ variants into an instance of OMD is useful and could be of independent interest. Overall, I find this paper introduces some useful ideas and does a good job substantiating them with both theory and experiments.\n\nSome weaknesses: the overall presentation of the paper is quite cluttered. The flow of the paper could be improved if some of the details from Section 5 are moved to the appendix and SOGRM+ is instead given more priority, given that the proof technique seems to be the same and the class of games studied is wider.\n\n_Edit: I erroneously mentioned that the main algorithm was left to the appendix, but actually the SOGRM+ update rule is in the main text. Apologies for that. However, my point that the paper is cluttered remains true, and a pass for formatting would greatly improve the readability of the paper._\n\nOne potential weakness in the results is that in Cai et al 2025, they show last/best iterate convergence in iterates (i.e. pointwise convergence), whereas the results in this paper pertain to convergence to the set of NE (in the case of MVI games). This seems to indicate that the results of Cai et al 2025 are stronger in the case of last-iterate convergence, since they also show this via the duality gap rather than the tangent residual. I feel a more comprehensive discussion and comparison of the results of this paper in relation to Cai et al 2025 would be helpful to clarify these points, and to emphasize that the best-iterate results of this paper are indeed new.\n\nOverall, while the paper has some issues with clarity of exposition, I believe the proof idea and usage of tangent residuals is interesting and thus would consider this paper a borderline accept.", "was_revised": true, "final_justification": "- The authors have adequately addressed my concerns about comparisons to prior work by Cai et al.\n- Other reviewers have brought up the potential issues of weak MVI property, namely that it might not be an interesting class inherently, or that the presence of $\\rho$ leads to complications/incomparability with existing algorithms.\n- I will maintain my borderline assessment because while the theoretical results are nice (smooth RM+ to OMD reduction, last iterate convergence under weak MVI property), there were no concrete arguments that weak MVI (and not MVI) games are an interesting class worth studying.", "rebuttal": "We appreciate the your valuable time and constructive suggestions.\n\n\n\n**W1:  the main algorithm proposed (SOGRM+) is left to the appendix.**\n\n**A:** We would like to clarify that while the pseudocode and some proofs related to its convergence are in the appendix for space considerations, the core elements—including the main update rules for SOGRM+ and the associated convergence proofs—are presented in the main body of the paper (Section 6, lines 269-319).\n\n\n\n**W2: I feel a more comprehensive discussion and comparison of the results of this paper in relation to Cai et al. (2025) would be helpful.**\n\n**A:** Thank you for this valuable suggestion. Here is a more detailed comparison with Cai et al. (2025):\n\n- In terms of proof techniques, our proof paradigm centers on recovering the weak MVI, whereas the methods proposed by Cai et al. (2025) focus on analyzing the limit points of iterates or leveraging the definition of the duality gap in two-player zero-sum games. Notably, our paradigm is applicable to both best-iterate convergence and last-iterate convergence, in contrast to Cai et al. (2025), who require separate proofs for these two types of convergence.\n\n- Regarding best-iterate convergence results, our results apply to games satisfying the weak MVI, whereas those of Cai et al. (2025) are restricted to two-player zero-sum matrix games. The applicability of our best-iterate convergence results is significantly broader than that of Cai et al. (2025).\n\n- Concerning non-finite-time last-iterate convergence results, our findings hold for games satisfying the weak MVI. Cai et al. (2025) divide their results into two sections: the first pertains to two-player zero-sum matrix games, while the second addresses broader games satisfying the MVI. Their results exhibit pointwise convergence for two-player zero-sum matrix games, surpassing our own in strength. However, in games satisfying the MVI, our results align with theirs, yet ours extend further to include games satisfying the weak MVI.\n- With respect to finite-time last-iterate convergence results, as mentioned in Section 2 Related Work, our best-iterate convergence results enable us to extend the finite-time last-iterate convergence findings of Cai et al. (2025) from two-player zero-sum matrix games to games that concurrently satisfy monotonicity and metric subregularity. This exemplifies one of the advantages of our best-iterate convergence results.\n\n\n\n**Q1: In [1], they used the tangent residual not only as a proxy for the distance to NE, but also as a method to create a potential function for the dynamics, thus showing last iterate convergence. Would it be possible to extend similar ideas to the set of games with the MVI/weak MVI property?**\n\n**A:** Extending these ideas is feasible. The primary challenge lies in identifying an appropriate potential function for RM+ variants, a problem that remains unsolved in existing research. It is noteworthy that Cai et al. (2025) and the first author of the work you referenced as [1] are the same individual. However, Cai et al. (2025) also have not succeeded in this endeavor, highlighting the inherent difficulty in discovering a suitable potential function for RM+ variants.\n\n\n\n**Q2:  What properties of the tangent residual can be studied to give more results compared to the standard duality gap?**\n\n**A:** The primary advantage of using the tangent residual over the standard duality gap lies in simplifying the proof process when proving last-iterate convergence for algorithms based on the prox-mapping operator (defined in line 166). Specifically, as shown in Eq. (5), from the update rules of the prox-mapping operator and the definition of the tangent residual, we get that the gap between variables at different iterations (such as the gap between $\\ell$ and $\\theta$ at different iterations in Eq. (5)) serves as an upper bound for the tangent residual. To establish convergence to the NE, it suffices to demonstrate that this gap converges to zero, simplifying the proof process. In contrast, using the standard duality gap does not achieve this simplification.\n\n\n\n**Q3:  It is stated that all existing works on RM+ variants focus on simultaneous updates. I would be curious to know if your proof technique can be used to study alternating variants SExRM+/SPRM+/SOGRM+ in games with MVI/weak MVI and potentially show last/best iterate convergence.**\n\n**A:** We sincerely apologize for any lack of clarity in our original statement. Our intended statement (lines 783-785) is that current research on last-iterate convergence concentrate on simultaneous update schemes, not that all work on RM+ itself is limited to this setting.\n\nRegarding the extension to alternating updates, our proof paradigm itself would require minimal modification. The main challenge lies in proving $\\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2 \\to 0$ after deriving $r^{tan}(x^{t_2}) \\leq \\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2$ using our proof paradigm. Notably, the proof of $\\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2 \\to 0$ is not part of our proof paradigm as $\\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2 \\to 0$ is the inherent nature of the specific algorithm."}, {"review_id": "cS1vwwjBeI", "reviewer": "Reviewer_PiGs", "summary": "This paper study the convergence rates of Smooth PRM+ and ExRM+ under the assumption that the games satisfy the Minty condition, providing new results pertaining to *iterate* convergence, going beyond previously obtained results in Cai et al. 2025 pertaining to *duality gap* convergence. It also introduces a new algorithm (SOGRM+) that also converges under the weak Minty condition.", "questions": "* Can the idea of the authors be extended beyond smoothness?\n* Cai et al. 2025 also obtain rates using a restarting algorithms, but no last-iterate convergence rates for ExRM+ and SPRM+. You also don’t give rates. Do you think that this is an inherent limitations of your analysis (and the one in Cai et al.) ?\n* I would recommend the authors to devote less space to equations in the main body and explain more the intuition behind their algorithms.", "limitations": "Yes.", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 1, "strengths_and_weaknesses": "**Strengths:** convergence of an algorithm in a new setting (weak MVI)  \n\n**Weaknesses:** \n- weak MVI vs. MVI: is the weak MVI condition an interesting setting? Can the authors provide some actual applications that satisfy weak MVI but not MVI, beyond the simple 2 player non-zero sum game from section G.2?\n- I find their version of OMD quite confusing; it is quite heavy notationally, and the authors fail to convince me that this framework is necessary (instead of the usual OMD formulation).\n- The paper is not well written, and I am not sure what can be done in that regards. Several sentences are hard to read and to understand. To me this is a crucial issue. Top conferences should only accept well-written papers. Some examples: \n\nlines 63 - 65: “the feedback is the loss gradient of the original games, satisfying the weak MVI, implying the weak MVI is recovered. By using the recovered weak MVI, […]”\n\nLines 109: “it ensures that the weak MVI can be used after the weak MVI is recovered,”\n\nl161 : “No-regret algorithms are the algorithms, which ensures the regret R = [XXX] to grow sublinearly”\n\nl272: “However, they do not achieve such convergences in games satisfying the weak MVI, covering games satisfying the MVI”\n\n* \n* To my understanding, none of the “technology” used in this paper is new. The main methodological tool (RM+ to OMD reduction, in the same space) is the same as Liu et al 2021. The convergence based on tangent residuals follows from the analysis in [0]. The authors mention obtaining the best-iterate convergence rates as one of their contributions. But as they themselves acknowledge in lines 88-100, this follows from the analysis in Cai et al. 25, verbatim.\n\n  [0] Yang Cai, Argyris Oikonomou, andWeiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In Proceedings of the 35th International Conference on Neural Information Processing Systems, volume 35, pages 33904–33919, 2022.\n\n* l252: this is the proof of what statement? \n* l754: broken references", "was_revised": true, "final_justification": "I thank the authors for responding to my questions. I am satisfied with some responses, but for others, the authors did not answer precisely/adequately. Please find more details below. My evaluation remains similar.\n\n**W1.** My question was about a precise application where games naturally/always satisfy weak MVI and not MVI. The authors only responded with general applications of multiplayer normal-form games.\n\n**W2.** Thanks for the clarification. It's worth adding more discussion in the paper on this, I guess.\n\n**W3.** I have provided a few examples in my original review. It is not my job as a reviewer to do this work of listing/finding typos. This is usually done before the review process. There are several tools available nowadays to proofread papers for punctuation issues, grammatical mistakes, etc.. \n\n**W4.** I understand the response of the authors as confirming that the main results of their paper follow from the analysis of Liu et al. (2021) (RM+ -> OMD) to get their reduction (Smooth RM+ -> variants of OMD) and the results in Cai et al. 2022 (tangent residual analysis) for their convergence results. Combining two great papers for analyzing algorithms can make for a decent paper, but the significance of the contribution does not convince me. I leave it to the area chair to judge this.\n\n**W5.** Thanks for the clarification.", "rebuttal": "We thank you for your time and for providing feedback that will help us improve our manuscript.\n\n\n\n**W1: Is the weak MVI condition an interesting setting? Can the authors provide some actual applications that satisfy weak MVI but not MVI, beyond the simple 2 player non-zero sum game from section G.2?**\n\n**A:** Intuitively, as $\\rho$ decreases, the number of multi-player general-sum normal-form games that the games satisfying the weak MVI encompasses increases. Multi-player general-sum normal-form games have numerous applications, such as:\n\n- Political science, where they are used to model diplomatic relations and strategies between countries.\n- Network and communication systems, where multiple service providers may need to allocate bandwidth or other resources.\n\n\n\n**W2: I find their version of OMD quite confusing; it is quite heavy notationally, and the authors fail to convince me that this framework is necessary.**\n\n**A:** In fact, we utilize the general adaptive OMD as outlined in Joulani et al. (2017). This form extends the traditional OMD to encompass a broader range of algorithms, which is crucial for transforming RM+ variants into an OMD instance. Only by employing the general adaptive OMD can the RM+ variants be transformed into an OMD instance that updates within the original strategy space of the game. In contrast, using the traditional OMD prevents the RM+ variant from being converted into such an instance. \n\n\n\n**W3: The paper is not well written. Several sentences are hard to read and to understand.**\n\n**A:** We are deeply sorry for this. Could you provide us with more details, such as the specific point you find unclear? We would be more than happy to address any questions or concerns you may have.\n\n\n\n**W4: The main methodological tool (RM+ to OMD reduction, in the same space) is the same as Liu et al 2021. The convergence based on tangent residuals follows from the analysis in [0].**\n\n**A:** We acknowledge that our research is built upon these foundational works. However, we wish to clarify that our core novelty lies not in inventing new low-level tools, but in constructing a novel, unifying proof paradigm that uniquely combines and extends these tools to solve a more challenging and general problem that was previously unaddressed. \n\nIn addition, our transformation substantially differs from that of Liu et al. (2021). While they convert RM+ to OMD, we transform smooth RM+ variants to OMD, which is fundamentally distinct and significantly more complex, as detailed in Appendix A. Moreover, our transformation establishes both last-iterate and finite-time best-iterate convergence for smooth RM+ variants. In contrast, Liu et al. (2021) do not even achieve average-iterate convergence for RM+ using their transformation, as indicated in the bottom right corner of page 6 of their paper: “be deduced from Lemma 2.2, but not from Theorem 3.5.”\n\nLastly, the tangent residual, serves solely as a metric for assessing the distance to the set of NEs. This is quite standard practice. For instance, Cai et al. (2024), along with other works [1] and [2], employ the tangent residual in their proofs as a metric for assessing the distance to the set of NEs.\n\n\n\nAdditional Reference:\n\n[1] Bot, Radu Ioan, Dang-Khoa Nguyen, and Chunxiang Zong. \"Fast Forward-Backward splitting for monotone inclusions with a convergence rate of the tangent residual of $ o (1/k) $.\" *arXiv preprint arXiv:2312.12175* (2023).\n\n[2] Cai, Yang, Argyris Oikonomou, and Weiqiang Zheng. \"Tight last-iterate convergence of the extragradient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities.\" *arXiv preprint arXiv:2204.09228* (2022).\n\n\n\n**W5: The authors mention obtaining the best-iterate convergence rates as one of their contributions. But as they themselves acknowledge in lines 88-100, this follows from the analysis in Cai et al. 25, verbatim.**\n\n**A:** \n\n- Firstly, we would like to clarify that our approach to proving best-iterate convergence is fundamentally different from the approach used by Cai et al. in 2025. We use our novel proof paradigm, while they rely on the definition of the duality gap for two-player zero-sum games (line 85). Therefore, their results are confined to two-player zero-sum games, whereas our results hold in games satisfying the weak MVI.\n- Secondly, our statement in lines 99-100 is that when we establish the linear last-iterate convergence for Restarting SExRM+ and Restarting SPRM+ in games that satisfy both monotonicity and metric subregularity via our best-iterate convergence, we can directly use the proofs for Restarting SExRM+ and Restarting SPRM+ from Cai et al. (2025). This is precisely the advantage of our best-iterate convergence. Through it, we extend the linear last-iterate convergence results for Restarting SExRM+ and Restarting SPRM+ in Cai et al. (2025) from two-player zero-sum games to games that satisfy both monotonicity and metric subregularity.\n\n\n\n\n\n**W6: this is the proof of what statement?**\n\n**A:**  We sincerely apologize for the missing reference here. This is the proof of Theorem 5.1. As mentioned in line 245, to prove Theorem 5.1, we introduce Theorem 5.2, Theorem 5.3, and Lemma 5.4. We also show that the proofs of Theorems 5.2 and 5.3 can be found in the Appendix, while Lemma 5.4 is derived from Farina et al. 2023.\n\n\n\n**Q1: Can the idea of the authors be extended beyond smoothness?**\n\n**A:** The answer is yes. This is because our proof paradigm itself is not related to smoothness. Specifically, as shown in Section 4 Our Proof Paradigm, smoothness is only used to prove the specific algorithm convergence of $\\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2 \\to 0$. The proof of $\\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2 \\to 0$ is not part of our proof paradigm as $\\Vert \\ell^{t_2} - \\ell^{t_1} + \\frac{\\theta^{t_0} - \\theta^{t_2}}{\\eta}\\Vert_2 \\to 0$ is the inherent nature of the specific algorithm.\n\n\n\n**Q2: Cai et al. (2025) also obtain rates using a restarting algorithms, but no last-iterate convergence rates for ExRM+ and SPRM+. You also don’t give rates. Do you think that this is an inherent limitations of your analysis (and the one in Cai et al.) ?**\n\n**A:** You raise a profound question that touches upon the frontier of current research. We argue this is not an inherent limitation of our analytical framework, but rather an open challenge. \n\nTo provide a finite-time last-iterate convergence rate, a feasible approach is to construct a potential function as demonstrated by Cai et al. (2022). This involves setting the potential function as an upper bound for the tangent residual and proving the finite-time last-iterate convergence rate of the the potential function. This is not an inherent limitation of us. We just did not find a suitable potential function.\n\nFurthermore, we clarify that the finite-time last-iterate convergence rate in Cai et al. (2025) is restricted to two-player zero-sum games, representing only a subset of the games we consider. Also, as mentioned in our responses to W5, we extend the finite-time last-iterate convergence rate in Cai et al. (2025) from two-player zero-sum games to games that satisfy both monotonicity and metric subregularity."}]

Author rebuttal:

Meta-review: This paper studies the last-iterate convergence properties of Regret-Matching+ (RM+) based algorithms in games. Recent works have established that in two-player zero-sum matrix games (1) the non-convergence of several popular variants, including RM+, alternating RM+, and PRM+; (2) last-iterate convergence of several smooth variants of RM+, including ExRM+ and SPRM+, where the decision set is truncated to ensure Lipschitzness of the regret operator. This paper's main contribution is to extend the convergence results of ExRM+ and SPRM+ to games satisfying the MVI condition, a class of games that encompasses two-player zero-sum games as a special case. This paper presents a new analysis framework based on (1) an equivalence between the RM+ type updates on the truncated positive orthant and the OMD type update on the simplex; (2) a proximity measure to Nash equilibria called tangent residual that upper bounds the duality gap. Using the new analysis framework, this work also generalizes the Optimistic Gradient (OG) algorithm to an RM+ based algorithm called SOGRM+, which has best-iterate convergence rates and asymptotic convergence to the set of Nash equilibria even in games with a weak MVI condition.

There were active discussions during the rebuttal phase, and the majority of the reviewers believe that the contributions here are sufficient to merit the acceptance of this paper. While this paper received a negative review, the authors during the response have clarified the majority of the concerns raised by the reviewer. The lingering concerns of the reviewer, from my perspective, are either a little bit subjective or not a cause for a strong rejection of this paper. I hence recommend the acceptance of this paper.

The proof paradigm proposed in this work is also a nice addition, which is appreciated by a couple of reviewers, and helps connect different algorithms.

Nevertheless, I suggest the authors update their paper based on the constructive feedback they have received from several reviewers to make the presentation of this work clearer and more accessible to a broader audience. One of the comments in writing shared by two reviewers who gave positive ratings is that the exposition/presentation is rather cluttered and would benefit from removing some of the technical stuff from the main body, while providing more intuition, elaboration, and a clear bird-eye view in the main text.

In the new version, the authors should also discuss a potential limitation: their result may not always produce comparable results to OMD, as the parameter $\rho$ could be in a smaller range. This issue was brought up during the internal discussion stage.
Decision: Accept (poster)