A Faster Parameter-Free Regret Matching Algorithm
Authors: Linjian Meng
Youzhi Zhang
Shangdong Yang
Wenbin Li
Tianyu Ding
Yang Gao
Venue: ICLR 2026 Poster (2026)
Keywords: Regret Matching
Parameter-Free
Nash Equilibrium
Primary area: learning theory
TL;DR: We propose the first parameter-free Regret Matching algorithm achieving an  $O(1/T)$ convergence rate in learning Nash equilibra.

Abstract: Regret Matching (RM) and its variants are widely employed to learn a Nash equilibrium (NE) in large-scale games. However, most existing research only establishes a theoretical convergence rate of $O(1/\sqrt{T})$ for these algorithms in learning an NE. Recent studies have shown that smooth RM$^+$ variants, the advanced variants of RM, can achieve an improved convergence rate of $O(1/T)$. Despite this improvement, smooth RM$^+$ variants lose the parameter-free property, i.e., no parameters that need to be tuned, a highly desirable feature in practical applications. In this paper, we propose a novel smooth RM$^+$ variant called Monotone Increasing Smooth Predictive Regret Matching$^+$ (MI-SPRM$^+$), which retains the parameter-free property while still achieving a theoretical convergence rate of $O(1/T)$. To achieve these properties, MI-SPRM$^+$ employs a technology called Adaptive Regret Domain (ARD), which ensures that the lower bound for the 1-norm of accumulated regrets increases monotonically by adjusting the decision space at each iteration. This design is motivated by the observation that the range of step-sizes supporting the $O(1/T)$ convergence rate in existing smooth RM$^+$ variants is contingent on the lower bound for the 1-norm of accumulated regrets. Experimental results confirm that MI-SPRM$^+$ empirically attains an $O(1/T)$ convergence rate.

Published as a conference paper at ICLR 2026
A FASTER BARAMETER-FREE REGRET MATCHING AL- GORITHM
Linjian Meng',2 Youzhi " Yang", Wenbin Li', Tianyu Ding', Yang G
Shanghai Artificial Intelligence Laboratory
2 National Key Laboratory for Novel Software Technology, Nanjing University
Centre for Artificial Intelligence and Robotics, Hong Kong Institute of Science & Innovation, CAS
Jiangsu Key Laboratory of Big Data Security and Intelligent Processing, Nanjing
University of Posts and Telecommunications
5 Microsoft Corporation
menglinjian @ smail.nju.edie edd..cn youzhi.zhang @ cair-cas.org catir-cas.orghhkk. .k, sdyang @ njupt.edu.cn, liwenbin @ nju.edu.cn tianyuding microsoft.com. gaoy nju.edu.cn
ABSTRACT
Regret Matching (RM) and its variants are widely employed to learn a Nash equilibrium (NE) large-scale games. However, most existing research only establishes a theoretical convergence rate of O(I/VT) for these algorithms learning NE. Recent studies have shown that smooth RM+ variants, the advanced variants of RM, can achieve an improved convergence rate of O(1/T). Despite this improvement, smooth RM* variants lose the parameter-free property, i.e., parameters that need to be tuned, a highly desirable feature in practical applications. In this paper, we propose novel smooth RM+ variant called Monotone Increasing Smooth Predictive Regret Matching* (MI-SPRM*), which retains the parameter- free property while still achieving a theoretical convergence rate of O(1TT). To achieve these properties, MI-SPRM* employs a technology called Adaptive Regret Domain (ARD), which ensures that the lower bound for the 1-norm of accumulated regrets increases monotonically by adjusting the decision space at each iteration. This design motivated by the observation that the range of step sizes supporting the ((1/T) convergence rate in existing smooth RM+ variants is contingent on the lower bound for the 1-norm of accumulated regrets. Experimental results confirm that MI-SPRM* empirically attains O(1/T") convergence rate.
INTRODUCTION
Game theory serves as a powerful framework for modeling interactions among multiple agents. A widely studied solution concept in this context is the Nash equilibrium (NE), state where no player can achieve higher payoff by unilaterally deviating from their current strategy. This concept provides insight into the stability of decisions. chosen strategy once equilibrium reached. NE is widely applicable across various fields such as economics, political science, business, and international relations, offering theoretical framework for predicting behavior and optimizing decision-making in complex systems (Osborne, 1994).
player has incentive to deviate from their
To learn NE in real-world games, compared traditional NE learning algorithms like Ficti- tious Play (Brown, 1951), the algorithms based on the regret minimization framework (Zinkevich, 2003), also called regret minimization algorithms, are more popular, particularly given the recent breakthroughs in superhuman game AIs, which rely heavily on this framework (Bowling et al., 2015; Moravčík et al., 2017; Brown and Sandholm, 2018; 2019b; Pérolat et al., 2022). Among regret minimization algorithms, Regret Matching (RM) (Hart and Mas- Mas-Colell, 2000) and its vari- ants (Gordon, 2006; Lanctot et al., 2009; Johanson al., 2012 2; Lanctot, 2013; Tammelin, 2014;
Corresponding authors.

---

Published as a conference paper at ICLR 2026
Brown and Sandholm, 2019a; Farina et al., 2021: Zhang et al., 2022; Xu et al., 2022; Farina et al., 2023; Xu et al., 2024b) stand out in practical applications due to their superior empirical performance compared other regret minimization algorithms,, such as those based on Online Mirror Descent (OMD) (Nemirovskij and Yudin, 1983) or Follow the Regularized Leader (FTRL) (Shalev-Shwartz and Singer, 2007). For example, RM variants are widely used in superhuman Poker AIs (Bowling et al., 2015; Moravčík et al., 2017; Brown and Sandholm, 2018; 2019b), while OMD/FTRL-basd algorithms are not.
Numerous studies have shown that many advanced algorithms based on OMD and FTRL achieve an O(1/T) theoretical convergence rate (Rakhlin and Sridharan, 201 Syrgkanis et al., 2015; Farina et al., 2019; Piliouras et al., 2022; Hsich et al., 2021). Unfortunately, although several advanced RM variants have been proposed, such as Regret Matching* (RM+) (Tammelin, 2014), Discounted Regret Matching (DRM) (Brown and Sandholm, 2019a), and Predictive Regret Matching* (PRM-) (Farina et al., 2021), they only achieve an O(1/vT) theoretical convergence rate.
To address the problem that RM variants only achieve an 0(1/VT) theoretical convergence rate, smooth RM+ variants like Smooth Predictive Regret Matching (SPRM*) (Farina et al., 2023) are introduced. These variants achieve OL/TT) theoretical convergence rate by ensuring that the lower bound for the 1-norm of accumulated regrets consistently exceeds a positive constant. However, smooth RM* variants lose the parameter-free freee property of other RM+ variants like RM+ and PRM*, i.e., no parameters need to be tuned (Grand-Clément and Kroer, 2021), which is a highly desirable feature in practical applications. Specifically, one of the most significant obstacles in using regret minimization algorithms to learn an NE in games is the sensitivity to hyperparameters. As illustrated in our experiments (Section 4), even in the game considered in the original paper of SPRM (Farina et al., 2023), the convergence rate of SPRM* varies significantly depending on the choice of step size ny'_ Specifically, after 10 iterations, SPRM+ (17 = 0.1) achieves a duality gap (the distance to NE; lower is better) that is 10 and 5 times smaller than SPRM* (1 = 0.01) and SPRM+ (n 1), respectively. This sensitivity implies that extensive parameter tuning is required to identify a suitable parameter. In contrast, parameter-fres algorithms eliminate the need for such tuning, allowing the algorithm to directly learn an NE without any tuning of parameters.
To recover the parameter-free free property² for smooth RM+ variants, we propose novel smooth RM+ variant called Monotone Increasing Smooth Predictive Regret Matching* (MI-SPRM*), a parameter-frre algorithm that achieves an O(1TT) theoretical convergence rate. The key insight of MI-SPRM", which enables the simultaneous achievement of the parameter-free property and an OL//T) theoretical convergence rate, is that the appropriate range of step sizes for achieving this rate in SPRM+ depends on the lower bound for the 1-norm of accumulated regrets. Therefore, MI-SPRM+ + employs technology called Adaptive Regret Domain (ARD), which ensures this lower bound monotonically increases by adjusting the decision space at each iteration to achieve an O(1TT) theoretical convergence rate with the parameter- free property.
Furthermore, we evaluate the empirical convergence rate of MI-SPRM+ on the games considered in the original paper of smooth RM+ variants (Farina et al., 2023) and randomly generated two-player zero-sum NFGs. The experimental results show that MI-SPRM+ consistently attains an O(1/T) empirical convergence rate across all evaluated games. More interestingly. MI-SPRM* outperforms all other tested algorithms, including existing RM variants and traditional con-parameter-fres and parameter-free regret minimization algorithms.
2 RELATED WORK
Traditional parameter-free regret minimization algorithms. Although many results about the O(ITT) theoretical convergence rate of traditional regret minimization algorithms based on OMD
Traditional regret minimization algorithms are even more sensitive to parameters than SPRM* as they will diverge without suitable parameters.
2 "eeyond being parameter-fie free, RM* and PRM* + exhibits a property called stepsize- invariance (Chakrabarti et al., 2024), meaning that the algorithm's 's output remains unchanged regardless of the parameter choice. This property is also referred to as strongly parameter-free free -rémmnt and Kroer, 2021). See details in Section 5, In this paper, only focus the parameter-free property since to the best of our knowledge, no algorithm simultancously achieves both (1/T) theoretical convergence and stepsize-invariance.
2

---

Published as a conference paper at ICLR 2026
or FTRL have been proposed, these algorithms are highly sensitive to the choice of parameters. Specifically, as demonstrated in our experiments, these algorithms exhibit an empirical convergence rate of (1/"T) with appropriate parameter tuning, while they either converge very slowly may even diverge when the parameters are poorly chosen. To establish the parameter-free regret minimization algorithms, the most common method is the doubling trick (Auer et al., 1995). However, the doubling trick can only create parameter-free regret minimization algorithms with an Oloog, T/T) convergence rate even if the original regret minimization algorithm theoretically guarantees an O(1TT) convergence rate. Specifically, consider that the original regret minimization algorithm exhibits a regret bound of C' for any number of iterations T, thus implying an (11/T) convergence rate. For a total of T iterations where there exists positive constant M such that 2 < < 2 2M1,,
the cumulative regret resulting from the application of the doubling trick is bounded by ΣM+ C. This summation results in a regret bound of (log, T), leading to a convergence rate of O T/T). To achieve both the parameter-fre free property and theoretical convergence rate of O1/TT), Hsieh et al. (2021) propose an algorithm called Dual Stabilized Optimistic Mirror Descent (DS-OptMD), which achieves this goal by autonomously learning the step size. However, our experimental results reveal that the empirical convergence rate of DS DS-OptMD is significantly slower than OLL/T).
Regret Matching (RM) variants. The key distinction between RM variants and traditional regret minimization algorithms based on OMD or FTRL is that RM variants update within the (subset of the) non-negative orthant, whereas the latter update within the original strategy space of the game (Farina et al., 2021; 2023). These algorithms usually perform numerically better than traditional regret minimization algorithms. However, although many technologies have been proposed to improve these algorithms' empirical convergence rate, these algorithms only achieve an O(1/VT) theoretical convergence rate. To provide an O(1/T) convergence rate to RM+ variants, Farina et al. (2023) propose smooth RM+ variants like Smooth Predictive RM (SPRM). Although smooth RM* variants achieve an O(I/T) theoretical convergence rate, they drop very appealing property in most other RM+ + variants- the parameter-fie free property, which is extremely useful in practice as it avoids fine tuning the parameters.
To the best of our knowledge, we introduce the first parameter-free RM variant that achieves an O(1/T) theoretical convergence rate, named Monotone Increasing Smooth Predictive Regret Matching+ (MI-SPRM+). To achieve both the parameter-free property and a theoretical conver- gence rate of O(1/T), MI-SPRM+ employs ARD, dynamically adjusting the decision space each iteration, while SPRM+ maintains a fixed decision space throughout each iteration (a detailed comparison is shown in Section 4). In addition, unlike DS-OptMD, which theoretically has an O(1/T) convergence rate but empirically demonstrates a much slower convergence rate, MI-SPRM* achieves an (l) convergence rate both in theory and in practice.
3 PRELIMINARIES
Two-player zero-sum normal-form games (NFGs). this paper, we study two-player zero-sum NFGs, which encompass many classic scenarios like Rock-Paper-Scissnne player i E N = {0. }} simultaneously selects an action a; E A, and receives a reward ri a1-:). where A, denotes the action space of player and A is the set of players. We denote the strategy of player i by æ, which is the probability distribution over all actions a, E A,, The set of strategies is denoted as X, which is a (lA,) dimeenssil simplex, i.e., Yz; E X, I; 2 0 and x.) 1, implying ||z:ll2 S ||=;||| = 1. Similarly, the strategy profile is represented by x = [ and the of strategy profiles is denoted as X X, X1. The set X' is compact set because each X' is simplex, which is a compact set. The utility of player i when all players follow the strategy profile æ is given by (x(x) = u, x1-) EageAo Ea, EA, ra a1 (=o(()))) (1(()))))))))))))){{)))) The zero-sum property implies that EIEN uz( 0. The loss gradient for player is denoted by
In these games, each
Ee = -Va, (1 21 -i). We assume that Vax, ar' E X,
Lr - L|
x' 12,
P.
where E- = eT), and L, P fundamental in game solving (Farina et al., 2023; Cai and Zheng, 2023; Cai et al., 2024; 2025). We also use 1) to denote maxiex [At].
> 0 are constants. The assumptions in Eq. (1) are among the most
3

---

Published as a conference paper at ICLR 2026
Nash equilibrium (NE). To solve two-player zero-sum NFGs, common goal is the NE where no player can benefit from deviating unilaterally from this equilibrium. In other words, for any player, her strategy is the best-response to the strategies of others. We use X" to denote the set of NE. As analyzed in Facchinei (2003), if x X", then (er : gap as the metric to measure the distance from strategy profile x to X Precisely, the duality gap of strategy profile is defined as dg(z)
2²i I O, Va; X, We use the duality
DiEN m (L,, x.. zz). If dg(x)) S 8, then Φ is d-approximate NE (6-NE). If and only if xe is a NE, dg(x) 0.
x I x²)
Regret minimization framework. To learn an NE a two-player zero-sum NFG, the most popular algorithms are the algorithms based on the regret minimization framework (Zinkevich, 2003), also called regret minimization algorithms (Zinkevich, 2003; Hart and Mas-Colell, 2000; Nemirovskij and Yudin, 1983; Rakhlin and Sridharan, 2013b; Syrgkanis et al., 2015; Farina et al., 2019; Piliouras et al., 2022; Hsieh et al., 2021; Gordon, 2006; Lanctot et al., 2009: Johanson et al., 2012; Lanctot, 2013; Tammelin, 2014; Brown and Sandholm, 2019a; Farina et al., 2021; Zhang et al., 2022; Xu et al., 2022; Farina et al., 2023; Xu et al., 2024b). In this framework, each player i selects a decision of E X; according feedback received from the game. In games solving, such feedback is set to the loss gradient 1 = e.¹ The goal of regret minimization algorithms is to enable the regret ET a -fxx) x.), Vx, X, to grow sublinearly. After T iterationn, let L' [e); Lij, x' [ag xi), and x= = [mo; a 1.), suppose the social regret Σi (e", x' - a) = Eie (Eg, af ax)) satisfies EL (et x² x) /T < E, Va E X. Then, the time-averaged strategy profile x" El= ø²) /T is an NE. The (1/TT) theoretical convergence rate of the regret minimization algorithms is that Ei x²' x)) /T S O(1/T) after T 2 1 iterations.
Online Mirror Descent (OMD), Among regret minimization algorithms, one of the most classic is OMD (Nemirovskij and Yudin, 1983). Let o(-) : X, - E, OMD generates decisions via
E arg mig ( (ef, x.) + - =B,(,,)))), 11
a;Ex;
where the step size > 0 is constant, (a b) = ((a)= - (bb) (Vo(b), b) is the Bregman divergence associated with (.). In Eq. (2), (-)) can be any strongly convex function.
Regret Matching+ (RM+). To solve real-world games, RM variants are among the most widely used regret minimization algorithms,, as demonstrated by their success in superhuman Poker AIs (Bowling et al., 2015; Moravčík et al., 2017; Brown and Sandholm, 2018; 2019b; Pérolat et al., 2022). In this paper, we focus on RM variants (Tammelin, 2014; Farina et al., 2021; 2023; Meng et al., 2023) since RM+ variants usually outperform vanilla RM (Hart and Mas-Colell 2000; Gordon, 2006; Zinkevich et al., 2007). At each iteration > RM+ updates its accumulated regret 0J via the regret matching* operator: 0
00 P (x:)) (=+))++ where the step size 1 > 0 is a constant, 0 0, a!! = 1/| e (0* 00;; 01) the instantaneous regret, and [:] max(-, 0). From the amalysis in Farina et al. (2021), RM+ is connected to an OMD
x / 1 (t 1) 1), (x') = (²)) (L), x
instance which performs updates in the non-negative orthant and sets ((-) as the quadratic regularizer
(.) = 113/2. Formally, RM+ can be rewritten as
0
0 Eargmin ((-F) (0'), 0:)+ BB (0,, xf 0,ck(A Asi
(3)
where the step size 1) > 0 is constant, and Rdd (vly E Rd y 2 0J. Notably, v--)) is the quadratic regularizer || / implying that Va, b E Rd. (a b) = Bb a) = |a bll3/2.
Predictive Regret Matching* (PRM*). ). To improve the empirical convergence rate of RM+ Farina et al. (2021) propose PRM whose key insight is to make a prediction at each iteration t. PRM + uses the feedback at the last iteration / - as the prediction at the current iteration I. Formally, at each iteration 2 1, the update rule of PRM+
0
0 argmin ((- F C.RRA
00
0.0.)+ (0,,0 at
|0: |]
(4)
0 E Cargmin (( (0') + B (0.0,))))
A.ERlA 20
4

---

Published as a conference paper at ICLR 2026
where the step size 7 0 is a constant, 07 1/|4,1, 0 = 0, x/ 1/14,/, F (0r-))
",="",,;-)11- - the quadratic regularizer defined in Eq. (3). In Eq. (4), F. (6' 1) is the prediction at iteration t. Note that the term (e), x ((---)
( (0*) (L, x { e. 0 10 01-1) 0' = - 0i), and ( is
in O0') (0--)() is |Aylddimensiona vector as E (e; 1 in F (F.-)) (0--1) a [A dimeensional vector (from the definition of et the shape of e is consistent with that of x.). As analyzed in Farina et al. (2021), if 1I
1 -
F' (00))l22 = 0 (D'-) = [F 1FFl11 (0'"));;" (0' and F'(0") = [F' (Y0)) holds, PRM* guarantees that its average strategy profile, xT Eا= x¹ /T, converges an approximate NE with a theoretical convergence rate of O(1/T), where x² = [ao: xi]. However, due to the instability (Farina et al., 2023), i.e., rapid fluctuations of the instantaneous regret (0t) across iterations, this assumption does not hold. Therefore, PRM* only achieves an O(1/vI) theoretical convergence rate. Notably, RM+ and PRM+ are parameter-free free algorithms, as the sequence of strategy profiles they generate remains invariant under any choice of n (Farina et al., 2021; 2023). For further details, refer to Section 5.
Smooth Regret Matching* variants (Farina et al., 2023). Smooth RM+ variants are designed to address the instability of PRM+ and obtain an O(1/T) theoretical convergence rate. Our algorithms are based on Smooth Predictive Regret Matching (SPRM*) (Farina et al., 2023) as SPRM+ is a single-call algorithm, which only calls loss gradients once at each iteration, while other smooth RM* variants are not. To address the instability of PRM+ and achieve an O(1'T') theoretical convergence |..
rate, SPRM* performs updates in the space RR R2R whereas PRM* performs updates in the space R/o.l. This modification ensures [ - (') 1B S 0(1|0-11 0') to reduce the instability. More precisely, Farina et al. (2023) employ the property that || |r (0' FF00") S 0(110-1 - -0 to prove the O1/TT) theoretical convergence rate. See Appendix B for the details of the proof. Formally, the update rule of SPRM+ at iteration / 2 is
1 B. (0, 01), ai= 10:111
0
e {(- F
1,0,)
e
17
2R
(5)
8 eargmin
{(- F. (0') 0,)) 1 7 0
(0,,0)))
where R >>> 0 is constant, the step size 1 > 0s a constant, 0. = 1/|Ai), 0. -1/lAi1, x7
1 1/) F. ((0-1) (e-- - 1 -- (0') = (e), xz) e. 0'-1 10' 1
0: (0:: 0) and v=() is the quadratic regularizer defined in Eq. (3).
4 OUR ALGORITHM
Although SPRM is a powerful algorithm, it is not parameter-free, it requires the fine-tuning of the parameter to achieve an O11TT) theoretical convergence rate. This dependency on parameter tuning diminishes its practical appeal. To avoid the parameter tuning, we propose novel RM+ variant called Monotone Increasing Smooth Predictive Regret Matching* (MI-SPRM*), parameter-free algorithm that achieves an (1 theoretical convergence rate.
MI-SPRM is inspired by the convergence results of SPRM*, which achieves an O1/TT) theoretical convergence rate with 0- < 1 < RCs, where Co =L/ (DD222 4DL" + 4DP2) is a game- dependent constant and R is defined in Eq. (5) (the formal convergence result of SPRM* is detailed in Theorem B) It is evident that for any 1) > O, if R > n/Co, SPRM* guarantees an O11/T) theoretical convergence rate. To achieve this convergence rate with the parameter-free property, a viable approach to adaptively increase the value of R, the lower bound for the 1-norm of accumulated regrets, so that R exceeds 1/ Co. We call this approach Adaptive Regret Domain (ARD).
Existing OMD-based algorithms like DS-OptMD (Hsieh et al., 2021), I), achieve the parameter-free property and an O(1/T)) theoretical convergence rate by adaptively reducing the step size 7j. However, the reduction method employed in DS-OptMD is too conservative, thereby resulting in poor empirical convergence rate, shown in our experiments. In contrast, ARD exploits the convergence property of SPRM* +, which simultancuusly depend on the lower bound of the I-norm of accumulated regrets and the value of 1). Instead of reducing 7, ARD adopts a more aggressive approach for
5

---

Published as a conference paper at ICLR 2026
Algorithm MI-SPRM
1: Initialize: 1,
1, 0. - [A,
1
0: t
[A.]
x f
[A.
ViE
2: x. [ar): æ
3: for 2,,,..., T do
4: E N do
5:
C. = V
-uu (xx (0')(( = :
1 - -
6:
0f arg min
o.ERlAi
lail 2
{ (- 10" 0.)
0.) + (0:, (0.. wt.
10
end for
8:
i E N do
9:
e = - V of (x'), (²') = x1) - E
10:
oc+1 E arg min
|4:11
{ (O') 0:) (0; 0:)}
11:
end for
12:
0-11=
10%-
1,-1:00 111 1 0²
[0]: 01) x² = wi]
13:
(0
Fi (0
}; F (0'~1), F (0') (0') (0')
+1 i | ( F² 1='110' (0' B B) 10 00)
14:
R R²
>
R¹
else
15:
end for
Ec R'= Ei=1
16:
return
x²
increasing the lower bound of the 1-norm of accumulated regrets, maintaining faster empirical convergence rate. Building on ARD, we propose MI-SPRM*, whose updates follow the recursion:
E argmin [c] o, 0,ea|4
( 1--F-- 11=F-1(0'')))) (00-'))..)))))))))))))))) BB. a|= 1001122
0
2n
R RR'+1
if F (0') F 1 11
(6)
0c+1 E Cargmin ( (O'.0 0,E3 Arl
n²+1=
1o 00'-1 1) (6" ,0)
>0,
2x
R
else
where R' 1, 0- 1/| 0 1/1 x, = 11/14,1 F (0r-l)
(L--1
e
(0')
(,,, 1 C. QC-1 = 100- 1 0 3. 0 = -0: 01) 0x
[0/: 0j), F p
[F] (0'-"); FL F 1 (0'-1), FO00") = (');; F1 (0'),, and (b) is the quadratic regularizer. The
pseudocode for MI-SPRM* is in Algorithm 1.
The primary distinction between MI-SPRM+ and SPRM+ lies in the adaptive adjustment of the [4il decision space (denoted as IR n² that MI-SPRM+ performs at each iteration t. This adaptation ensures that the lower bound for the 1 1-norm of accumulated regrets increases monotonically and LA.1, exceeds 1/Co, since Rt serves such lower bound (from the definition of IR 5 and increases monotonically to a constant that exceeds 1/Co. According to these properties, MI-SPRM* obtains the O(1/T) theoretical convergence rate, shown in Theorem 4. See details in Section A.
Theorem 4.1. [Proof is in Section A.J In a two-player zero-sum NFG, if all players employ MI- SPRM* then the weighted average strategy profile _T ( R'=') NE with rate of O(1/T).
converges to an approximate EE R$)
We now discuss whether our MI-SPRM* can be extended to multi culti-player general-sum NFGs extensive-form games (EFGs). Firstly, regarding multi-player general-sum NFGs, it is crucial to clarify that, the complexity of computing a NE for multi-player general-sum NFGs belongs to the PPAD complexity class (Daskalakis polynomial-time convergence to an NE in such games. Our experiments further corroborate that none of the tested algorithms exhibited any convergence NE when applied to multi-player general-sum NFGs. In fact, the original paper of SPRM* (Farina et al., 2023) only provides a social regret bound of (1) for multi-player general-sum NFGs, and does not offer any convergence rate to an NE in such games. As shown in Theorem 1. we establish a similar social regret bound of O(1) for multi-player general-sum NFGs: (E R (e', xr
Discussion,
al., 2009). Therefore, no algorithm
achieve
x))) EE R*) < 0(1). Secondly, for EFGs, the design of
6

---

Published as a conference paper at ICLR 2026
MI-SPRM* can be directly extended to this domain. However, its O(1/T) convergence rate does not hold. Specifically, RM variants are typically integrated with the Counterfactual Regret Minimization (CFR) framework to address EFGs. Unfortunately, to the best of my knowledge, only Clairvoyant CFR (Farina et al., 2023) achieves an ((T convergence rate when learning an NE of EFGs, albeit at the cost of an Ollog T) per-iteration complexity (such complexity of our MI-SPRM* is O(1).. Experimental results show that the combination of MI-SPRM and the CFR framework significantly outperforms other tested algorithms. In fact, such combination demonstrates an (1//T) or even faster empirical convergence rate.
EXPERIMENTS
Configurations. We now evaluate MI-SPRM+ by comparing to RM* (Tammelin, 2014), PRM+ (Fa- rina et al., 2021), SPRM* (Farina et al., 2023), OGDA (Popov, 1980), OMWU (Rakhlin and Sridharan, 2013a), and DS-OptMD (Hsich et al., 2021) (unless otherwise stated). Among them, parameter-free algorithms. Notably, although the
MI-SPRM*, RM+ PRM+, and DS-OptMD update rules for RM+ and PRM* + include the step size 1), the sequence of the strategy profiles x' 2". xx" is referred to as hiepsiz--nvarriane, also known as the strongly parameter-free property in Grand- Clément and Kroer (2021). This is why RM + and PRM+ referred to as parameter-fie frree algorithms. MI-SPRM SPRM+, OGDA, and DS-OptMD achieve an O(1/T) theoretical convergence rate while other tested algorithms only exhibit an O(1/VT) theoretical convergence rate. We use the duality gap as the metric to measure the distance to equilibrium. For non-parameter- (SPRM+ and OGDA), we choose step size y) from (0.01, 0.1 alternating updates. All experiments are conducted on a computer equipped with one Xeon(R) Gold 6444Y CPU and 256 GB of memory.
that they generate remains unaffected by the value of 1) (Farina et al., 2021), which
algorithms 1]. We do not use linear averaging and
Results on convergence rates in two-player zero-sum NFGs. Now, we present the convergence results in two-player zero-sum NFGs. We conduct experiments on the 3 x 3 two-player zero-sum NFGs considered in the original paper of SPRM+ (Farina et al., 2023), whose payoff matrix is [[3, 0. -3,, [O, 3, -4] j0, O, 1]], and randomly generated two-player zero-sum NFGs of varying sizes: [10, 30, 100]. For each size, we generate 60 independent instances to ensure the robustness of our results. Specifically, for each set of 20 instances, the payoff' matrices
drawn from distinet Gaussian distributions. The first group uses a Gaussian distribution with a mean of O and a standard deviation of 1, the second group employs a Gaussian distribution with a mean of 0 and a standard deviation of 10, and the final group uses a Gaussian distribution with a mean of 0 and a standard deviation of 100. We present the average duality gaps across the 20 instances for each group and report the corresponding confidence intervals.
The convergence rates on the x 3 two-player zero-sum NFGs considered in the original paper of SPRM+ (Farina et al., 2023) are demonstrated in Fig. 1. The experimental results demonstrate that SPRM+ is highly sensitive to the step size parameter, with performance variations of up to tenfold depending on the chosen value. In contrast, MI-SPRM+ eliminates the need for parameter tuning and achieves faster convergence rate compared to SPRM+ The con- vergence results on randomly generated two-player zero-sum NFGs are shown in Figs. 2. 4, and 5 (due to page limitations. Figs. and are included in Sec- tion C). MI-SPRM+ achieves an O(1/T) empirical convergence rate across all tested games. Notably, MI-SPRM+ outperforms all other algorithms. Ad- ditionally, our findings indicate that the traditional regret minimization algorithms, such as OGDA and OMWU, are more sensitive compared to RM+ vari- ants. Specifically, in games where payoff matrices are sampled from a Gaussian distribution with mean 0 and standard deviation 1, as well as a Gaussian distribution with mean O and standard deviation 10, OGDA and OMWU only converge when is
105
duality g3e
10
30-1
10
10
10P
132
10
10
101
36
Iterations
MI-SPMM
SPIM (gg-0.3
SPRM (n-0.011
SPAM (g=11
Figure 1: Convergence rates of MI-SPRM* and SPRM+ with different step sizes 7) in the x 3 two-player zero-sum NFGs considered in the original paper of SPRM The duality gaps at iteration lc5 for MI-SPRM SPRM* (n 0.01), SPRM+ (1 = 0.1), and SPRM* (n 1) are 2.6e-5, 3.9e-4, 4.0e-5, and 2. le.4, respectively.
7

---

Published as a conference paper at ICLR 2026
10a
10a
10a
dualit gap
dim=10
104
101
10t
109
104
10a
10a
10a
10a
dinn 30
dually gap
10a
100
10
10
10
10
0
10
10
10
10
10
10:2
10
10
10
10-3
10a
10a
10a
10a
10a
10a
10
107-
10a
10a
10a
10
164
16a
10a
din 50
Quality gep
10
100
10a
10
10a
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10-4
10-3
10
10-9
10-9
10a
10t
10"
10a
10a
10
10a
10:
10a
10a
10
10
10"
10
10a
10
10a
10
10P
101
10a
10
10
10
10a
10a
10a
10'
10
101
10a
101
dine 100
Quality ge0
10a
10a
10a
10"
10
10
0-
10
10-7
10
10
0
10-3
10
10
10
10-1
10
10-
10-1
5
0-5
10"
10
10'
10
10a
10
10"
10
10"
10'
10
10"
10"
10
10'
10'
10"
10
10"
101
10'
10
10
10
llerations
Rerations
iterations
iterations
0.001
0.01
0.1
MI-SPRM
Figure 2: Convergence rates of different algorithms in randomly generated two-player zero-sum NFGs, where payoff matrices are sampled from Gaussian distribution with mean 0 and standard deviation 100. Note that the value 17 only involves the performance of SPRM* and OGDA as other algorithms are parameter-free algorithms.
sufficiently small. In games where payoff matrices are sampled from Gaussian distribution with mean and standard deviation 100, OGDA and OMWU only converges when is 0.001 and the dimension of the game is less than 10.
is important to note that the results in Fig. may exhibit slight scale distortion. In fact, in terms of the average reduction in duality gap, MI-SPRM* demonstrates approximately a 37% improvement compared to + (the best-performing algorithm excluding our MI-SPRM+) This reduction comparable to the 42% improvement in Xu al. (2024a) (which also investigate RM variants). Furthermore, in the games considered in Figs. 2 and 4, MI-SPRM* achieves a remarkable reduction of 92% and 74%, respectively, relative SPRM These reductions significantly surpass the reductions in Xu et al. (2024a).
Moreover, although DS OS-OptMD theoretically guarantees an O(1/T) convergence rate, fails to empirically demonstrate this rate. We argue that this is because it achieves an O(1/T) theoretical convergence rate through adaptive step size reduction. However, substantial number iterations necessary to sufficiently reduce the step size and fully realize the O(1/T) convergence rate. For more detailed discussion on the empirical convergence rate DS-OptMD, refer to the paragraph titled "Results on the dynamics of the values of ! in Section C.
8

---

Published as a conference paper at ICLR 2026
kuhn Poler
Leduc Paker
Liar's Dice (3)
Goafspiel (3)
10a
10"
122
10"1
20-2
10"
10-4
20
10
10: 4-
10-4
10-4
10-4
10-2
10:1
20
10
10a
10
10
104
10a
10a
10a Iterations
10a
100
102
10a
10a
Iterations
Iterttons
Iterations
3-Player kuhn Paker
4-Player kuhn Paker
Liars (4)
3-Player Gootsplel
107
107
10'
10
10-2
10-1
10
10a
20-4
10-4
10-3
10-1
10-4
10
10a
10a
10a Iterations
10
10"
10
16x
10a iterations
16a
10
107
10a
10a
10>
10
100
100
10a
107
10
Iterations
Iterations
SPORR
Figure 3: Convergence rates of different algorithms in standard EFG benchmarks.
Results convergence rates in multi-player general-sum NFGs. We also evaluate the perfor- mance of MI-SPRM*, RM* PRM SPRM* OGDA, OMWU, and DS- OptMD in multi-player general-sum NFGs. The results are show in Section C (Fig. 6). Consistent with theory, algorithm can learn an NE in all tested multi-playe general-sum NFGs. See more details in Section C.
Results convergence rates in EFGs. Now, evaluate the performance of MI-SPRM+ in EFGs. We test on eight instances of four standard EFG benchmarks: Kuhn Poker, Ledue Poker, Liar's Dice, and Goofspiel. These EFGs are implemented using OpenSpiel (Lanctot al., 2019). For Kuhn Poker, we examine the two-player, three-player, and four-player versions, denoted as "Kuhn Poker", "3-Player Kuhn Poker", and "4-Player Kuhn Poker", respectively. In the case of Leduc Poker, only its two-player version is tested due to the size constraints of the three-player variant. For Liar's Dice, OpenSpiel's 's limitations prevent testing of versions with three or more players; therefore, analyze the versions with 3 and 4 sides, denoted as "Liar's Dice (3)" and "Liar's Dice (4)", respectively. Lastly, for Goofspiel, we set the number of cards to and test both the two-player and threc-player versions, referred to as "Goofspiel (3)" and "3-Player Goofspiel (3)". As RM variants are typically integrated with the CFR framework to address EFGs, we integrate MI-SPRM+ with the CFR framework and get MI-SPCFR+. We compare MI-SPCFR* against the combination of SPRM* with the CFR framework, referred to as SPCFR+, and the combination of PRM+ with the CFR framework, known as PCFR + (Farina al., 2021). We do not to compare with other algorithms tested in our NFGs experiments as they consistently underperform MI-SPRM SPRM* and PRM The results are shown in Fig. 3. We observe that MI-SPCFR significantly surpasses SPCFR + in all eight tested games. In addition, although PCFR* + outperforms MI-SPCFR+ in Ledue Poker, MI-SPCFR significantly outperforms PCFR in the remaining seven tested games. Moreover, the experimental results demonstrate that our algorithm achieves an O(1/T) or even faster empirical convergence rate even on multi-player EFGs. Interestingly, while an O(1/T) or even faster empirical convergence rate is observed in multi-player EFGs, such empirical convergence is noted in multi-player NFGs. We hypothesize that this arises due to the unique characteristics of the CFR framework and the tested EFGs Kuhn Poker and Goofspiel. However, this remains open question, provided a theoretical explanation to date.
existing work has
Results runtimes. We compare the runtimes of MI-SPRM+, SPRM+, and DS-OptMD, as shown in Table 1, in randomly generated two-player zero-sum NFGs. For each game dimension, we average the runtimes over 60 instances. Although all three algorithms have the same theoretical per- iteration complexity, O (EieN [A,] log [A::), both MI-SPRM+ and DS-OptMD require parameter learning to achieve their parameter-fe -freeeeerrrreeeeeeeeeeeeeeeeeeee properties, resulting in longer runtimes compared to S Specifically, the runtime of * is approximately 1.5 times that of SPRM*, while DS- OptMD's 's runtime is about 2.5 times longer. We hypothesize that the significantly higher runtime of

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of the runtime (in minutes) between MI-SPRM*, SPRM*, and DS-OptMD for randomly generated two-player zero-sum NFGs. It is important to highlight that theoretical per- iteration complexity for MI-SPRM*, SPRM* and DS-OptMD remains O (ZiEN [A,]] log [A..]
MI-SPRM*
SPRM*
DS-OptMD
dim=10
0.1105=000007
0.075110.0016
0.174610.0007
dim=30
0.1367=000009
0.0858110.007
0.,001
dim=50
0.0012
0.1023+:000066 0.1562++0.0013
0.2462++000005
dim=100
0.0014
0.3717=-0.008
DS- DS-OptMD stems from its requirement for individual parameter learning for each player, a step that circumvented in both MI-SPRM+ and SPRM A key direction for future research is reduce the time required for parameter learning while preserving the parameter-free property.
CONCLUSIONS
In this paper, we investigate parameter-free RM variants. To the best of our knowledge, propose the first parameter- free RM variant that achieves an O(1/T) theoretical convergence rate, named MI-SPRM To achieve the parameter-free property and (1/TT") theoretical convergence rate simultaneouslly MI-SPRM* ensures that the lower bound for the 1-norm of accumulated regrets monotonically increases by adjusting the decision space each iteration. The empirical results indicate that MI-SPRM+ attains an empirical convergence rate of O(1) (1/T)) in all tested games, and MI- SPRM+ outperforms all other tested algorithms, including existing RM variants, and traditional regret minimization algorithms, By combining MI-SPRM* with the CFR framework, we get MI-SPCFR+, which outperforms other classical CFR algorithms like PCFR as shown our experimental results.
ACKNOWLEDGEMENTS
This work is supported by Shanghai Artificial Intelligence Laboratory, 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 Col- laborative Innovation Center of Novel Software Technology and Industrialization, and the InnoHK funding.
REFERENCES
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pages 322-331. IEEE, 1995.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold'en em poker is solved. Science,
2015.
George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-376, 1951.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6774):41844222 2018.
Noam Brown and Tuomas Sandholm. Solving imperfect-information games via discounted regret minimization. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 1829-1836, 2019a.
Noam Brown and Tuomas Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456): 885-890, 2019b.
Yang Cai and Weiqiang Zheng. Doubly optimal no-regret learning in monotone games. In Proceedings of the 40th International Conference Machine Learning, 2023.
10

---

Published as a conference paper at ICLR 2026
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated algorithms for monotone inclu- sion and constrained nonconvex nonexxnconnceeeeee min-man max optimization. In Proceedings of the s1st International Conference Machine Learning, 2024.
Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-War 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.
Darshan Chakrabarti, Julien Grand-Clément and Christian Kroer. Extensive- form game solving via blackwell approachability on treeplexes. In Proceedings of the 38th International Conference on Neural Information Processing Systems, 2024.
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. Communications of the ACM, 52(2):89-97, 2009.
F Facchinei. Finite-dimensional variational inequalities and complementarity problems, 2003.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic regret minimization for extensive- form games via dilated distance-genen generating functions. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 5221-5221 5231,, 2019.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: 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- Wei Lee, and Haipeng Luo. Regret matching+::(n) stability and fast convergence in games. arXiv preprint N.Ki::2305.17000 2023.
Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical PrantticcaPooooraaa Programming, 156(1):59-99) 2016
Geoffrey J. Gordon. No-regret algorithms for online convex programs. In Proceedings of the 19th International Conference on Neural Information Processing Systems, pages 489-496. MIT Press. 2006.
Julien
and Christian Kroer. Conic Blackwell algorithm: Parameter-free convex- concave saddle-point solving. In Proceedings of the 35th International Conference on Neural Information Processing Systems, volume 34, 2021.
Sergiu Hart and Andreu Mas-Colell. simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5): (065):11220 127-11100 2000.
Yu-Guan Hsich, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Conference on Learning Theory, pages 2388-2422, 2021.
Michael Johanson, Nolan Bard, Neil Burch, and Michael Bowling. Finding optimal abstract strategies in extensive-form games. In Proceedings of the AAAI Conference Artificial Intelligence, volume 26, pages 1371-1379, 2012.
Marc Lanctot. Monte Carlo Sampling and Regret Mininization for Equilibrium Computation and Decision- Mariing in Large Extensive Form Games. University of Alberta (Canada), 2013.
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling, Monte carlo sampling for regret minimization in extensive games. Proceedings of the 22nd International Conference on Neural Information Processing Systems, pages 1078-1086, 2009.
Marc Lanctot, Edward Lockhart, Jean-Baptiste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls. Shayegan Omidshafiei, et al. Openspiel: framework for reinforcement learning games, 2019.
Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. arXiv preprint 191../910009952 2019.
11

---

Published as a conference paper at ICLR 2026
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.
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 up no- no-limit poker. Science, 356(6337):508-51) 513-508,,,,, 2017.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Martin Osbore. A course in game theory. MIT Press, 1994.
Julien Pérolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome Comnor, Neil Burch, Thomas Anthony, al. Mastering the game of Stratego with model-free multiagent reinforcement learning. Science, 378(6623):9009996 2022.
Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond time-average convergence: Near- optimal uncoupled online learning via clairvoyant multiplicative weights update. Advances in Neural Information Processing Systems, 35:22258-2222 22269,, 2022.
Leonid Denisovich Popov. A modification of the arrow-hurwitz method of search for saddle points. Mat. Zametki, 287):7777774, 1980.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pages 993-1019, 2013a.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Proceedings the 26th International Conference Neural Information Processing Systems, pages 1066-30744 2013b.
Shai Shalev-Shwartz and Yoram Singer. A primal-dual perspective of online learning algorithms. Machine Learning, 69(2): 2007.
Eric Steinberger. Pokerrl.
2019.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In Proceedingy of the 28th International Conference on Neural Information Processing Systems, pages 2989-2997, 2015.
Oskari Tammelin. Solving large imperfect information games using CFR+. arXiv preprint
arXiv:1407.5042 2014.
Chen-Yo 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 Learning Representations, 2021.
Hang Xu, Kai Li, Haobo Fu, Qiang Fu, and Junliang Xing. Autocfr: learning to design counterfactual regret minimization algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages
2022.
Hang Xu, Kai Li, Haobo Fu, Qiang Fu, Junliang Xing, and Jian Cheng. Dynamic discounted counterfactual regret minimization. Proceedings of the 12th International Conference on Learning Representationss 2024a.
Hang Xu, Kai Li, Bingyun Liu, Haobo Fu, Qiang Fu, Junliang Xing, and Jian Cheng. Mini- mizing weighted counterfactual regret with optimistic online mirror descent. arXiv preprint arXiv:2404. 18911, 2024b.
Hugh Zhang, Adam Lerer, and Noam Brown. Equilibrium finding in normal-form games via greedy regret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9498, 2022.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference Machine Learning, pages 928 928-936. 2003.
12

---

Published as a conference paper at ICLR 2026
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-17225 2007.
13

---

Published as a conference paper at ICLR 2026
A PROOF OF THEOREM 4.1
To prove Theorem 4.1, we introduce Theorem A.1.
Lemma A.1. [Proof is in Section A.1.] In multi-player general-sum NFG, if all players employ MI-SPRM*. then the weighted social regret bound bounded by
21=1 R (f,, x¹ x) S O(1)
T
Σ R
Proof. According to folk theorem, Theorem A.1 implies that the weighted average strategy profile x² (Et= R' R'x')/(E=1 R') converges to approximate NE with a rate of O1//T) since Σ (E' x² x) can be interpreted as the social regret over newly sequence of strategy profiles, x² ...... It completes the proof.
A.1 PROOF OF LEMMA A.
Proof. To prove Theorem A. we first prove that for any initial Rd (defined in Eq. (6) with t= 1), Rs increases monotonically to a constant as + co. By using this property, we show that Σ (' x' - x) S (() for any T 2 1.
Before starting our proofs, introduce Lemmas A.2 and A.3, which are very important for our proofs.
Lemma A.2 (Adapted from Lemma 10 of Wei et al. (2021)). Let A as a convex set and a' arg aegminaeet e (aa,, 9) + +B a)}. Then for any a" E E,A, we have
(a' a', .g) < By .a) (a a') (a,a a), where (-) is the quadratic regularizer defined in Eq. (3).
Lemma A.3 (Proof is in Section A.2), Suppose for all player i, we have
|0:11 and |10|-11 are greater than constant C1
20 | (F'0")=F''00000
( B
C7
where (-) is the quadratic regularizer defined in Eq. (3), and C2 2D(212 + 4DL2 + 4DP?).
Now, we first prove that for initial R! (not only 1), R' increases monotonically to a constant as t - 0o. By using Lemma A.3 with C1 Rt-1 we have (from the update rule of MI-SPRM* as shown in Eq. (6), R² 2 R(-1)
(F'( - p- (0' 11
2C₂
(,, (,' 00))
(R'-132
If R 22-12224 22, we can obtain
1135 (Ri-152
20₂
BB (0
101 +B 00)
20s
(0' 0 (B ++,, 0')
10,
(7)
10' 00- + 00' 0¹). s B 10'
1
) + (0' 0¹) /2 < 0 always holds. There- fore, from Eq. (6) and (7), we have that Rs increases monotonically and once R > 2/ for any t' t-1, R R Therefore, for any R!. RR increases monotonically to constant C3 ast co. Note that C3 2 Maax(R1,24) 2v) max(R1, V8D(2L2 + 4DL2 4DP2)) max(R1,14
implying that |F - FO000-1)113 (0' 00
(since C. 1/ (2L + 4DL2 + 4DP²)) as + co.
Considering the third line of Eq. (6), and using Lemma A.2 with a 0 = 10j; 01. a' のC-1 [ ((+11, a" 0 (o: 0,] and g = - -F FO') = (0'); - (i0)
(in this case, A is
Xiex [Ail 2R which means 0 E XieN (22)) we have
(- (-F'(O'), 0++1 SB, 0') (0, 0(+1) - B. 0¹)
(8)
14

---

Published as a conference paper at ICLR 2026
Similarly, considering the first line of Eq. (6), and using Lemma A.2 with 0r 10:: 01] a'
0¹ 10: 01), a" Q 10 0 and g - F
Fu
10- F (0'-1)] we get
(-Ft-1 p0--1(0011 (00-1) ) 0 t (6 (000+1000 0²) - BB 0t)
B8 0¹)
(9)
Summing up Eq. (8) and (9), and adding (F' (F' F F 1,
00+ 8t) to both sides, we get
(-F"(0"),e (0000))0'' 0) B (0,0") ) B. (0,0 00. - (0 00) - (0',0 00)
(10)
+ (0')
FF' (0'
0 -
For the term (F'), 0¹) we get
(F' (F')0')00) Σ (0'),)) =
1- Σ
(1 (1,0))
EW
iEN
iEN
of 1100 (ell1-(ee,))) (e:
(C)
-0.
10
iNN
(11)
where the last equality is from 2 = 0 (as stated in Eq. (6)). Arranging the terms of Eq. (10) and using the fact in Eq. (11), we have
(0, 1 (0,6")
(12)
F Substituting 0 = R'x, x< E X (note that I E XiEAiRR! 2R) into Eq. (12), we have
< (F 0) + ( 0 0¹) - 00) (0' 0))
-
(= F (0'-1) 110 - B (6++1 ) (B( (13)
FF' (00)) - B
(0' O¹), (0 -B,
where the last inequality comes from (F' (8') (0'), x² = EiEN((( (() x.)) E, x²) = R (e", x²
x) (x; E X, implics (1, z1) = 1, as stated around Eq.
Arranging the terms in Eq. (13), we get
R' x) )
(0-1))
(++1 -O, (0'
(0'
(00 (0 (B' 0*)
(0)) F F
(0
)12
|00 00
(
- 0')
(14)
2
2x2
B
.9)
-I' F (00
B (0' 0
2
B ((++ 00)
Ba (0' (¹)
2
2
where the third inequality from that ab S pt? /2 + x² (2p),, Vb, p, > (here, [0'
Ft-1((t-1)) ())- c= ||@r=1 1'112, and p = 2). and the last equality is from (a b) = 01aa-b11111 (wb()) is the quadratic regularizer as stated around Eq. (6), as well as B, b) = I| -b13/2 if e()
is the quadratic regularizer as stated around Eq. (3)). Summing up Eq. (14) from t = 1 T, we have
T
Σ R'(e' (e' x' x) -B)BB(RR RRT
BB 2 - RR' 2.00))
BB (R'x,,0)))
) -F (0 Ba (0 0T)
T
(p 0')
8,(0",0'-)
Bp (0'.00)
+
2
2
2
2
(0'0000 )0)
By 0 1)
B (0)
(0') -F'
2
2
(15)
where the first line is from that Σt, (Bo (R',z, 0c+1) - B (1t' θ*)) = Bot x, 0T+1)
By (R',,, xr 01) Etz(-B By 0¹) + BB RR'-1 0¹)), and the first inequality is from
15

---

Published as a conference paper at ICLR 2026
that T 2 1 (0)+) (0',)')))))))))))))))))))))))(
-B (000+++100)/- (B,
By (0 022 , / In addition, for the term as (-) is the quadratic regularizer (as stated around Eq. (6)), we get
x, + By x, 0').
(I'' (B x2,0'
|
T Enn -R' RR' (a,
(1= (11))))))
(16)
1-2
||0|12
|
(R-
(
2
where the first equality is from that Bq b) a b ||a
(a. b) + ||6|//2 2 if wb-) is
the quadratic regularizer (as stated around Eq. (3)), as well as the inequality from the facts that
R 2 R (from the update rule of MI-SPRM* as shown in Eq. (6)) and (ax, 0*) 2 (as æ 2
and 0x 2 0). From the fact that for any R², R' increases monotonically to a constant C3 as + 00
(as stated around Eq. (7)), we have (R*)² I CJ. From Eq. (16), well as combining (R*)² < C3
and ||0|| 3 = EiEN'
(eenl/aaa ||0:112 I [V (since | | < as stated around Eq. (1)), we get
T
| 2 2
|10
Σ
- BR BB x,00) (0)))
(R'''''0'0))
(R-))
2 C3/
2
(17)
Then, for the term B (R x. 11 BB RRa x., 0¹),, we have
( x. 0 B₁ (R² x. 0*) 2 BB (R'x,, x. 0¹).
(18)
Let (R'R. x. 11) < C4 with C4 is constant (such C44 must exists since (i) R and 0- are given, as well as (ii) x E X with X' a compact set as stated around (1). Then, combining Eq. (15), (17), and (18), we have
Σ R$ (e'
.x' 2) C3
(19)
T
F' (' 113) (,
T
(O
+ B (,000000)
[ -
Σ
2
2
2
t=1
1=1
To bound the value of (| (I[F((0)) - F (0--10011)1 (B 0²) + ( 01-2))/2, we show that
(I'F'(0)) - Fr (0 >) (B (0, 0¹) (0' 0³ 1)/2) 0 only appears
T, T T2/C2= R
times, where 1-1 is the ceiling integer of number and C2 is defined in Lemma A.3. Formally,
(II (0') ( )13 (B& 0¹) + B (,' (0)' > 0 implies R*+1 = R + 1. Also, we have that once R 2 2 C2, for any t' 2 t 1, R = R (as stated around Eq. (7)). Thus, we have that MI-SPRM only updates the value of R' within T, times (R++1= R + 1) to ensure
R!-1 2 2/C2 since
R'+ + 12VC2 R' 2 2/C2.
Therefore, from the facts that (i) R = Rd only appears T, = 12v/C2 1 times and (ii)
+++1 R + appears and only if (F) 112
(Ba (0', ) 0t 0000))))22)))))))))))))))) 1)))) >
0 (as shown in Eq. (6)). we have that
(0-1))) (
(0', + 0 1)) >
0 only appears T, times. Let these T, times be denoted by the set T, we have
B (0' B (0'
(1'' 10' 11
2
2
(20)
B (e
(0 00)
B (0', 0
[IF"(00)) F (0' |>
where the inequality is from the fact that the time t, which is not included in T, ensures that
F' (0') F(-1(01-1) _ (0', : 0¹) By (0', ()2)) < 0. Continuing from Eq. (20),
16

---

Published as a conference paper at ICLR 2026
have
(8 )²)
(0' 10'000
0'11)
[0' FF (0"
F0" 112
2
2
TET
FF") F 1001000111 10'
GET
KETREN
[1 100
(21)
ETEEN
ΣΣ
ETEEN
BETiEN
EE
where the third inequality comes from that Ya, c, Rd lllaa b c c S 4(1aa]1 + 1
||c|12 + |ld])2), the fourth inequality is from that (e) xf)1 and (e 1 are IA; A:l-dimensional vectors (as stated around Eq. (4)), the fifth inequality
from that D = max [As]. as well as the last inequality comes from the facts that |2 I |æ
1 (as stated around (1) and ΣIEN | ||ell < p2 (Eq,(1)). Combining Eq. (19), (20), (21), and the fact that
( (/)) Cs (Cs is constant and must exists as 0 and 0 are given), Vo X and T 2
we get
Σ Rt' x' x)
8TP + 1) C3W + Ca Css
El= RA
Σ R
finishes the proof.
A.2 PROOF OF LEMMA A.3
Proof. To prove Lemma A.3, we first introduce Lemma A.4.
Lemma A.4. (Proof is in Section A.3) Va, b E Rd ||al]] 2 CD |bb| 2 C1,
|
bo
S
bl12-
From the definition of [FF(('))
11 (0- (as stated aroud Eq. (6)), we
| (()
Σ
| (
icNN'
(22)
(att E --
REN
Continuing from the above equality, we have
(F') 1F
Σ
Σ (2
EEN
Σ (2)A,
(23)
NN
2D 22
<2
11 21| ==11
IEN
17

---

Published as a conference paper at ICLR 2026
where the third line is from the fact that Va, b E R ||a + bll2 - 2||a|12 + 2/16|[2- the fourth line
is from the fact that (ei, x 1 and (e;-), x - } are [A.] -iimennnni vectors (as stated around Eq. (4)), the fifth line is from D = maxee [A,l (as stated around Eq. (1)), and the last incquality is from
-1e00 e" 12 S
Li|x x' (Eq. (I)). For the term EieN Da e)) - (2)
1- ,4 11 we get
Σ EDl(atde) --0--___ 113=
DDl( L.) (m) tx) () (ai - 2
iEN
2DD>
(K(e).e) - (xt 1 e (a) 4)) (a) 4 1)1
2D
Σ
|aat--a - - 11++++11 - - 111
where the first inequality comes from the fact that Va, b E Rd ||a + bl1 - 2| 2|16 Then, we get
-
113
Σ
1111 -i1e -
CEN'
2D
p2 |22|01] 1p/1= 1/+ - -
(24)
IEN
22
p2
|
11
Σ eNN
lle
eg- 11
VEN
where the second inequality comes from |eil
1
|
P (Eq. (I)) with ||
S
| 1or |1? = (as stated around Eq. (I)). Then, continuing from Eq. (24), we have
(lleel e (ai-1 - 112 $2D
>
pa
|
a
1
2D
Σ
lee e
1
NEWV
ENN
<2DP2
||
x
1
2D Le' 11-
(25)
<2DP2
||02 - x
12 2DL 1|1' - -x 212
IEN
=2DP² |
x 11 112 2DL 21 x 1-1 112
where the third inequality is from _ - 1|2 S L æ x' 2|2 (Eq. (1)), the last equality is from
||xe x²-113- = EiEN || - 11.. Combining Eq. (22), (23), and (25), we get
|11 <ADP" _=''=13 113 4DL ||= - x 2 + 2L Ikee
x x'11113
(26)
=(2L² + 4DL + 44D || 11.
Then, get
| 112
KEN
Exex 1ii 110 0
4/21244D1244D
Cf
100 0-11
<D120"-ADL+4DPP
C²
(27)
-0'+0' 0 -0 113
=D@21"44D224DrP
C
1 O'
B
0 0
<2D:211-4D(+44DP))
C7
21 2424 (B' 0') B (O',0'
=4D
0 )).
C7
where the first equality is from ||-² - x1-
E
E ||_ - -13, the third inequality is from
the assumption that | and ||0||] are greater than C₁ with Lemma A.4, the third inequality
[|1
18

---

Published as a conference paper at ICLR 2026
comes from the fact that Va, b R", ||a bll2 Σ 21|a|12 2||b|l (in this case, - and b= O' 0t-1), well the last line from the facts that v(.) is the quadratic regularizer (as
stated around Eq. (6)) and (a, b) = a|a bl//2 2 if +b()) is the quadratic regularizer (as stated around Eq. (3)). Therefore, combining Eq. (26) and (27), we obtain
[|F" (0) 11 113322
2D +4D1 + (Bo(0',0% (') -0-)))
Of
completes the proof.
A.3 PROOF OF LEMMA A.4
Proof. To prove Lemma A.4, we first introduce Lemma A.5.
Lemma A.5. Aroptedrrom Proposition I in Farina et al. (2023)) E RR ||c|] 2 1, ll 2 1,
c 1 S valle f112.
Now, let C e and b Cif, where f E RR ||||| and || 1. conditions, we deduce that
From these
||a|| Ci and ||b|| 2 C₁.
Therefore, clearly, and satisfy the assumptions of Lemma A.4, i... b E Rd 20: ||]|| 2 C₁, and |Bbl| 2 C1. Then, have
b
Cie
Cif
aall
||6|1
||iccla
|Caf
(28)
f
|clli
[f
By Lemma A.5, we have
f
S <vllle- fll2-
(29)
|clli
[f
Additionally, we have
aa bl2- = |C - Ci || Cille fl1
(30)
+ +||c
fll2
C₁ la bll2-
Combining Eq. (29) and (30), we obtain
f
Vd
a bli2.
(31)
|||||
[[]|]
C
2
Finally, combining Eq. (28) and (31), obtain
b
Vd
a - bl12-
|a]]
b1/
C
2
This completes the proof.
19

---

Published as a conference paper at ICLR 2026
B CONVERGENCE RESULT OF SPRM*
Theorem B.1. SPRM* with < <] < R ED12L + + ensures that the average strategy
profile x² = Eiz m" converges to an approximate NE with a rate of (
Proof. We would like to clarify that this proof is adapted from the proof of Theorem 4.2 of Farina et al. (2023). Considering the second line of Eq. (5), and using Lemma A.2 with = 0 = [0] 01
a' 0c+1= [6+1; " a" 0 = 1o: 01] and g F0') F (0'); (O') (here, A
is X AAd 21 implying E XIENRR (ldd), ), we have 211
- 7p( T-FFF(O'), 0++1 0) SBp(0,00) - BB -B, (O 07).
(32)
Similarly, considering the first line of Eq.
(5), and using Lemma A.2 with Or
00 0 a' 0¹ 00: 01]. a' gc+1 10,";;000 o and g = F F
Fo 10t-1); - 1 (0) we get
F(-F* 1 0² - , <B 0³) - (0 0²) (O' 0²).
(33)
Summing up Eq. (32) and (33), and adding (F") F ((t-)) g 0¹) to both sides, we
get
7(FF'(0'), - 0) (B, (0, - (8 "00=,)0), ,0) - (')
+ 1 (0') (0' 0t 00))
From Eq. (11), we have (F'((') 0*) = 0. addition, we have (F' (F'()'). Ra) EiEN((e, a!)1
E, Rx)) = R(" x' - x) (x, E X; implies (1, x.) = 1, as stated around (q) Thus, by setting 0 Ræ (notably, O E XIENIR Adll,
2R ) get
nR(e x²' x)) SB 0¹) - BB (Ra, 0h - (0++ ,0) - (,, (')
(Bt) F² p(-1((0-1)) (, 0h+1 0*),
which implies
Riee' x² x²)
1
By (Ra, (R "0'
0+
00)) +(F'(0')=F" F FF'-((0' 10' ),0+11 1,0++100)
77
1
BB (Rx, 0') -B (Rx, - BB' 86) (1' FF' (8"-1)
(0'
||| 0 -'112
77
1
By (Ro,0 (Rx,0')
By - Rar 3- 00) 33' 86) +2+1
(F' - F (0
110 011
1/
2
2+2+r
+ F' (000) ||0c+1 1'1
$
(IRRe 0'113 11 Ro 0++1
112 11
0'
110 0' 11
21)
41j
1
|ar
0²113 Rax o
12)
1 4n
|10
+|
1 001 +T| ('0) (0000="--1) 10-- 112.
2n
where the third inequality comes from the fact that ab S p (2pp) Vb, c, p > 0 (in this case, b - 2| (00') Ft-1 (0t [|) c
| - 0¹ ||2 and 27)). and the penultimate inequality comes from B& (a. b) I|a bllB/2 (w(-) is the quadratic regularizer as stated around Eq. (5), as well as By (,, b) ||a b113/2 if (b) is the quadratic regularizer as stated around Eq. (3)). Then,
20

---

Published as a conference paper at ICLR 2026
have
R
T
T
T
Ra 0' 1-11111x -Rx 11) t1 D
F
Σ
|10-11-0
-0'12++110
0²13]
21)
4nj
1=1
1=1
1=1
|| RRo
1'112
0
F² (0') -F 10' 2
Σ
(10 1' 110 6'13)
211
1=1 4rj
RRx RRx-0'11 11
F F (0') - 10-
Σ 4rj (10* 0- 11+1000 0'13)
1
1
00
1
00)
21
47
41)
|Rx 1Ro-6'113
F (0') F" (0''))1
( 0
112+110"
0113
10
001
2n
4rj
47
RR 0'
1
F (0')
F0
(0'
0
0
|0 1
2n
81)
4nj
where the third inequality from
1 (1)
0
112
1
0²113)
Σt=
(1
0:
-0--112
100
01 1
0²
12
+
0
0 Then, we have
Rxx 1'1
(e, x) 5
IF' (0') F 10'
100
0-
1101 0011..
1j
81j
Anj
According to the proof of Lemma A.3 (Eq. (26) and the first three lines of Eq. (27)) with C₁ = R (from the update rule of SPRM*, shown in Eq. (5)), we get
Ra
0'1
0
0
R
C x'
x)
D + 4 4
2m
R2
110
21
10 1
8T)
According to above equation, if
D(21² +
4 4DP2)
17
H²
81j
1 R
8D(2L2 + 4DL2 + 4DP2)
then
T
|Rx 0- 112
R
Σ [=1
EL' x
000 0-112.
27
4n
which implies
T
Σ
(e xx
2) 00)), Vo E X.
In other words, we have
Σt, (E x' - x) < 0 1 (
T
which implies an O(1/T) theoretical convergence rate. It completes the proof.
21

---

Published as a conference paper at ICLR 2026
10a
10a
10a
dualit gap
dim=10
104
10
16
105
104
10a
10a
10
104
10a
din 30
duallty gap
10a
100
10
10
10
10
10
10
10
10
10
10
10:3
10
10
10
10
10-3
10a
10a
10a
10a
10a
10a
10
107-
10a
10a
10a
10
16a
16a
10a
din 50
Quality gep
10
10a
10a
10a
10a
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10-4
10-3
10
10-9
10-4
10a
10t
10
10a
10a
10
10a
10:
10a
16a
10
10
10"
10
10a
10
10
10
10P
101
10a
10
10
10
10a
10a
10a
10'
10
101
101
10'
dine 100
Quality gep
10a
10a
10a
10"
10
10-1
10
10
10-7
10
10
0
10-3
10
10-
10
10-1
10-1
10-
10-1
10
10"
10
10'
10
10
10
10"
10
10
10'
10
10"
10"
10
10
10'
10"
10
10"
10
10'
10
10
10
Neerations
Rerations
iterations
iterations
0.001
0.01
MIRMP
Figure 4: Convergence rates of different algorithms in randomly generated two-player zero-sum NFGs, where payoff matrices are sampled from Gaussian distribution with mean 0 and standard deviation 10.
C FULL EXPERIMENTAL RESULTS
Results convergence rates in two-player zero-sum NFGs. We now present the experimental results omitted from Section 5. Specifically, the convergence results for randomly generated two- player zero-sum NFGs, where the payoff matrices sampled from a Gaussian distribution with mean and standard deviation 10, as well as a Gaussian distribution with mean 0 and standard deviation illustrated in Figs. 4 and respectively.
Results on convergence rates in multi-player general-sum NFGs. Now, we evaluate the perfor- mance of MI-SPRM RM P SPRM OGDA, OMWU, and DS-OptMD in multi-player general-sum NFGs. Specifically, we conduct experiments on three-player general-sum NFGs of varying sizes: [10, 30, 50). Due to computational constraints, we do not include results for size 100 as did in wwo-player zero-sum NFGs, since three-player general-sum NFGs of size 100 require computation that is 100 times greater than that for two-player zero-sum NFGs of the same size. For convenience, generate 20 instances for each size, where the payoff matrices are drawn from Gaussian distribution with a mean experiments in two-player zuro NFGs, also test range of Gaussian distributions with varying standard deviations. However, we observe that the results do not differ significantly from those obtained with standard deviation of 1. Consequently, this paper focuses and reports results
and a standard deviation
100. Notably, similar to our
22

---

Published as a conference paper at ICLR 2026
10a
10a
10
10A
dualiy gap
dim=10
104
101
10
16
105
104
10a
10a
10
10a
10a
din 30
dually 9ap
10a
100
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10-3
10a
10a
104
10a
10a
10a
10a
10a
10a
10
107-
10a
10a
10a
10
161
16a
10
din 50
Quality gep
10
100
10a
10
10a
10
10
10
10
10
10
10
10
10
10-
10
10
10
10
10
10-1
10
10-
10-4
10a
10a
10
10a
10a
10
10a
10:
10a
16a
10"
10
10a
10
10a
10
10
10
10P
101
10"
10
10
105
10a
10a
10a
10'
10
101
101
10'
dine 100
Quality gep
10a
10a
10a
10a
10
10-1
0-
10
10-7
10
10
0
10-1
10
10-
10
10-1_
10
10-
10-1
10
10
10"
10
10'
10
10
10
10"
10
10
10'
10"
10"
10"
10
10
10'
10"
10
10"
10
10'
10
10
16
llerations
Rerations
iterations
iteratoon
0.001
0.01
0.1
SPRM
SPAM
Figure 5: Convergence rates of different algorithms in randomly generated two-player zero-sum NFGs, where payoff matrices are sampled from Gaussian distribution with mean 0 and standard deviation 1.
derived from Gaussian distribution with mean of 0 and standard deviation of 1. The results are show in Fig. 6: no algorithm successfully learns an NE all tested tireer general- sum NFGs.
Results on dynamics of the values of R'. To validate our theoretical analysis, we examine the dynamics of Rt over iterations. The results, shown Fig. 7, align well with the theoretical analysis, showing that as the game's s dimension and the standard deviation of the Gaussian sampling increase, converges also increases. Specifically, thcoretical analysis predicts
the final value to which that Rt will converge near C2. which is positively correlated with L, P, and D. As the game's 's dimension increases, D necessarily increases. Similarly, as the standard deviation the Gaussian sampling increases, the maximum standard value of the elements in the payoff matrix also rises, implying an increase in both L and P. This suggests that MI-SPRM* is implicitly learning L and P. Therefore, one of our future directions is apply techniques for adaptively learning unknown Lipschitz constants (Malitsky and Mishchenko, 2019; Ghadimi and Lan, 2016), i.e., L, from the field of optimization to MI-SPRM+. Note that the techniques for adaptively learning unknown Lipschitz constants are related to the unconstrained strategy space while MI-SPRM* is related to the constrained strategy space. Additionally, to investigate why MI-SPRM+ achieves faster empirical convergence rate than DS-OptMD, we also present the dynamics of the step size in DS-OptMD".
'The original paper of DS-OptMD denotes the reciprocal of the step size X i.e., X = 1/nl, where no the step size of player iteration present the average step size for all players.
23

---

Published as a conference paper at ICLR 2026
10
10"
10a
dim-10
Quality
10-1
10
10
10a
10
10a
10t
10
10
10
10
10"
10
10"
10
10
10"
10
10a
102
10
10a
10a
10a
107
10a
10
duality gap
dim- 30
10-1
10
10
10
10
10-3
10"
10t
10a
10a
10"
162
10a
10a
10t
10a
10a
10a
10a
10a
10r
10a
10
102
109
10
10
10a
10
10
102
100
109
Qualty gap
dm-50
10-1
10-1
10-1
10-1
10
10t
10a
10a
10t
105
10a
10t
10*
10r
10t
10t
10
105
100
10t
10
iterations
Iterations 0=
iterations
iterations f7
0.001
0.01
0.1
DS-DPIMD
Figure 6: Convergence rates of different algorithms in randomly generated three-player general-sum NFGs, where payoff matrices are sampled from Gaussian distribution with mean 0 and standard deviation
300
2000
32
260
24
value
26
120
800
10a
100
3.0F
10"
107
102
100
10
10
1.0
10
10"
10'
10P
70
1.0
10
Iterations
Tter attions
iteration Berations
std-1
std- 10
Std-100
Figure 7: Dynamics of R in two-player zero-sum NFGs. The notation "std=x" represents the standard deviation of a Gaussian distribution is x.
as shown in Fig. 8. By comparing the growth rate of Rs in MI-SPRM+ (Fig. 7) with the decay rate of the step size n in DS-OptMD, is evident that Rt in MI-SPRM+ grows significantly faster than the decrease in Therefore, we argue that the faster empirical convergence rate of MI-SPRM compared AS-OOtMDD attributed the step size 1) DS DS-OptMD. Its decay rate is too slow, requiring more iterations than MI-SPRM+ to achieve the O(1/T) convergence rate.
Results on convergence rates in standard EFG benchmarks when quadratic averaging and alternating updates are used. Now, we provide the results convergence rates in standard EFG benchmarks when quadratic averaging and alternating updates are used. Firstly, as did in Section we test eight instances of four standard EFG benchmarks: Kuhn Poker, Ledue Poker, Liar's Dice, and Goofspiel. We compare MI-SPCFR with SPCFR PCFR CFR* and DCFR. The results in Fig. 9 illustrate that, within two-player EFGs, all algorithms demonstrate improved performance when compared to scenarios where quadratic averaging and alternating updates are not used. In addition, it is important to highlight that our algorithm, MI-SPCFR+, outperforms other algorithms
24

---

Published as a conference paper at ICLR 2026
10-1
10'2
30
valle
10a1
205m1
20--00
$00-100
dmm-10
dim-33
dm
100
Figure 8: Dynamics of the step size 7y of DS-OptMD in two-player zero-sum NFGs.
Goofspiel (3)
10"
107
10-4
10
10
10
12
10.9
20-1
12a0
20-3
10"
10
10"
10
10
10
101
10
10
10
10"
10
16
10
10
10"
10
10"
10'
10
Rerations
Iterations
Reralions
iterations
3.Ployer lohhn Polorr
4-Playor luhn Polior
Liar's Dice
3.Playee Goofspiel (3)
2.39
10-1
10
duality
30*
10
30-1
iterations
iterations
Rteraionn
iterations
NISTOR
POr""
DOFt
Figure 9: Convergence rates of different algorithms in standard EFG benchmarks when quadratic averaging and alternating updates used.
Table 2: Final exploitability for the tested algorithms in HUNL Subgames. The lowest exploitability highlighted in red.
CFR
PCFR
SPCER
PDCFR*
MI-SPCFR*
Subgame3
4.64c-4 3.63e-4
5,14c-4 4.15e-4
5.12c-4 4.04e-4
4.35c-4
3.10c-4
Subgame4
3.89e-4
2.70e-4
in 3 of 4 tested games, such as Kuhn Poker, Ledue Poker, and Goofspiel (3). Unfortunately, in multi-player EFGs, the performance of all algorithms may significantly diminish compared their performance without quadratic averaging and alternating updates. For example, in 3-Player Kuhn Poker and 4-Player Kuhn Poker, decreases in performance surpass factor of 1000. In fact, in multi-player EFGs, our algorithm performs similarly to the baseline overall. No single algorithm consistently demonstrates superior performance across most games compared others.
Empirical convergence rates in HUNL Subgames. To assess the performance of our MI-SPCFR+ in addressing real-world games, we also conduct evaluations in HUNL Subgames, which are con- siderably larger than standard IIG benchmarks. Despite the presence of code related to HUNL Subgames Openspiel, we have not successfully executed it. Therefore, we utilize HUNL Subgames implemented by Poker RL (Steinberger, 2019). Precisely, our code is based on the code from Xu et al. (2024b). The code in Xu al. (2024b) supports only Subgame and Subgame 4, so we conduct experiments solely on these two HUNL Subgames. We compare with CFR+ P SPCFR+, and PDCFR We use alternating updates for each tested algorithms. Following the settings in the original version of PCFR (Farina et al., 2021), we employ quadratic averaging for SPCFR* and MI-SPCFR + The results are shown in Table 2: MI-SPCER consistently outperform all baselines in both subgames.
25

---

Published as a conference paper at ICLR 2026
D USE OF LARGE LANGUAGE MODELS
We promise that large language models are used only for editing, e.g. grammar, spelling, word choice.
26


Reviews:
[{"review_id": "V49Rr4arnN", "reviewer": "Reviewer_CnEQ", "summary": "This paper proposes Monotone Increasing Smooth Predictive Regret Matching+ (MI-SPRM+), a novel variant of regret matching (RM) that simultaneously achieves two highly desirable but previously incompatible properties in the RM family:\n\nParameter-free: The algorithm requires no hyperparameter tuning (e.g., step size), making it robust and practical for real-world deployment.\nO(1/T) theoretical convergence rate to Nash equilibrium in two-player zero-sum normal-form games (NFGs).\nTo our knowledge, this is the first RM-based algorithm that attains both properties. Prior smooth RM+ methods (e.g., SPRM+, Farina et al., 2023) achieve O(1/T) convergence but lose parameter-freeness due to their dependence on a carefully tuned step size η. In contrast, classical RM+ and PRM+ are parameter-free but only guarantee O(1/√T) rates.\n\nThe key technical innovation is the Adaptive Regret Domain (ARD) mechanism, which dynamically expands the lower bound of the decision space (i.e., the 1-norm of accumulated regrets) to ensure the conditions for O(1/T) convergence are eventually satisfied—without any user-specified parameters. This approach is conceptually distinct from existing parameter-free methods like DS-OptMD, which adaptively shrink the step size and suffer from slow empirical convergence.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "A rigorous theoretical analysis proving the O(1/T) convergence of the weighted average strategy under MI-SPRM+.\nComprehensive experiments on NFGs and extensive-form games (EFGs), showing that MI-SPRM+ consistently outperforms state-of-the-art baselines—including SPRM+ with optimally tuned η—in both convergence speed and final solution quality.\nEmpirical validation that the algorithm achieves O(1/T) (or faster) rates in practice across diverse game settings.\nOverall, the work makes a clear and meaningful contribution to the regret minimization literature by resolving a concrete limitation in existing RM algorithms, with both theoretical depth and practical relevance.", "weaknesses": "1) Larger-scale game benchmarks: The experiments are conducted on standard small to medium-sized games (e.g., Kuhn/ Leduc Poker, random NFGs). To better demonstrate the algorithm’s scalability and practical relevance, it would be valuable to include results on larger, more challenging domains—such as a heads-up no-limit Texas Hold’em (HUNL) subgame, which is commonly used in recent game-solving literature.\n2) Comparison with state-of-the-art CFR variants: The paper compares MI-SPRM+ against PRM+ and SPRM+, but does not include recently proposed advanced CFR algorithms like DDCFR[1] or PDCFR+[2]. Given that these methods also aim to accelerate convergence in EFGs, a direct comparison would help contextualize the empirical advantage of MI-SPRM+ more convincingly.\n\n[1] Xu Hang,et al. Dynamic discounted counterfactual regret minimization.  ICLR 2024.\n[2] Xu Hang,et al. Minimizing weighted counterfactual regret with optimistic online mirror descent. IJCAI 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pWGfK6fl9r", "reviewer": "Reviewer_VUBu", "summary": "This paper proposes a new variant of regret matching, called Monotone Increasing Smooth Predictive Regret Matching+ (MI-SPRM+), that enjoys a parameter-free setting and achieves an O(1/T) convergence rate. It differs from SPRM+ by (1) eliminating the need of using \\eta, the step size of accumlating regret and (2) introduce an adaptaive scheduling of R^t, a lower bound of the regret values. The authrors also present relevant experimental results.", "questions": "I think MI-SPRM+ is neat and achieving a provable O(1/T) convergence rate is great. My biggest concern is about the experiments on EFG: It would be great if baselines like CFR+ and DCFR is included.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The technical contribution is sound.", "weaknesses": "The experiments lack important baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "T25yavClOp", "reviewer": "Reviewer_G2Xd", "summary": "The paper proposes MI-SPRM$^+$, a smooth RM$^+$ variant that introduces an adaptive regret-domain floor so that the 1-norm of cumulative regrets grows to a level where the standard stability inequality holds. Once the floor is high enough, the scheme behaves like SPRM$^+$ without requiring tuned step sizes. The main theoretical claim is an $O(1/T)$ rate for a weighted average strategy with weights proportional to the domain floor sequence. Experiments include NFGs and EFGs in both two-player and multiplayer settings, and demonstrates favorable performance of the proposed method, when using uniform averaging for the algorithms compared to.", "questions": "1. The theoretical result is based on a weighted average of the iterates, which is not standard in decentralized learning settings. While this doesn’t take away from the result, it would be good to emphasize this in the abstract and intro.\n\n2. Why not include alternation and quadratic averaging for the CFR+/predictive CFR+ baselines, as is standard in the literature? These choices often improve empirical performance substantially on the EFGs you report.\n\n3. In Table 1, are the reported times for a fixed number of iterations (1e5?) or for reaching a fixed duality gap?\n\n4. Given that you run experiments for computing NE in multiplayer games (and use duality gap as the potential function), it might sense to not specify the notation/preliminaries section to use 2 players (even though the theoretical work is focused on the 2p0s setting) and let it be more general (some of the notation is already more general).\n\n5. Why is a proof for $O(1/T)$ of SPRM$^+$ given? Isn't that just restating results from Farina et al?", "limitations": "", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper studies an important problem of trying to design faster parameter-free regret-matching algorithms for equilibrium computation in games and recover parameter-free behavior while keeping the O(1/T) rate associated with smooth RM+ variants. A simple modification to SPRM+ is provided that achieves O(1/T) convergence for weighted average iterates.  \n\n2. The empirical section is broad. The method is tested in both NFGs and EFGs and compares against common RM-style and OCO baselines.", "weaknesses": "1. Notation and presentation need work; there is a lot of inline math in the preliminaries section which makes it difficult to read, and the notation feel excessively verbose.\n2. The experiments only use uniform averaging, which is not particularly interesting from a practical perspective. It is well-established that linear or quadratic averaging should be used, or even the last iterate in some cases.\n3. The experiments do not use alternation. While it is good to test on the simultaneous case to verify the theory, numerical take-aways should most likely be concluded for the alternating variant.\n4. The proposed change does retain parameter-freeness, but it does not retain stepsize-invariance, another property cojectured to be important for RM-based algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OeyNxZXClP", "reviewer": "Reviewer_yD2A", "summary": "This paper introduces a smooth regret matching+ variant called Monotone Increasing Smooth Predictive Regret Matching+ (MI-SPRM+), which retains the O(1/T) convergence guarantee of current SOTA methods, while also being parameter-free. To achieve this, the authors introduce the Adaptive Regret Domain (ARD) method, which relies on the insight that the range of permissible stepsizes depends on the lower bound of the 1-norm of accumulated regrets. MI-SPRM+ dynamically adjusts the decision space after each iteration, ensuring that the lower bound monotonically increases and recovering the O(1/T) convergence property. Experiments show that MI-SPRM+ exhibits the theoretical convergence rate in standard benchmark games, and seems to outperform other existing methods in terms of duality gap.", "questions": "- The authors use the phrasing \"even faster than O(1/T) convergence\" several times in the paper, but this is a strong statement to make, given the lack of theoretical justification. Could the faster convergence be attributed to constant factors? I would suggest changing the wording to avoid confusing readers who might misconstrue the complexity of MI-SPRM+.\n- In Fig 7, we see that for some games, the value of $R^t$ seems to plateau then subsequently grow as the number of iterations increases. Is there some intuition for what this means? Would this imply that the algorithm shifts to a different NE, since the decision space changes after some period of stability?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is fairly well written, and the motivation of reducing the parameters required for tuning (especially for solving large games) is sound.\n- The technical contribution and insight behind the ARD method is strong, resulting in a main theoretical result that successfully obtains strong convergence rates while being parameter free.\n- The experimental results are surprisingly strong, particularly in EFGs, showing faster convergence than all prior approaches. Exploring this behavior is a crucial step for future work.", "weaknesses": "- The algorithm description for MI-SPRM+ is very densely written, and some more intuition would greatly improve the readability of this work.\n- The paper presents a single convergence guarantee for NFGs, but it would be improved if a similar result can be shown for EFGs, even in the non-CFR variant (i.e. MI-SPRM+ directly applied to the sequence form representation of the EFG). If anything, the fact that MI-SPCFR+ seems to outperform SOTA methods makes it all the more compelling to see if there is some theoretical reasoning for this. \n- While the paper shows a comparison between the compute times of the main algorithms implemented, I believe more discussion or experiments could help clarify the relationship between 1) convergence rate in terms of duality gap and 2) compute time required. In particular, it seems that MI-SPRM+ achieves parameter freeness by incurring additional adaptive steps in the process. It is however not made clear to the reader what the computational cost of parameter tuning actually is (for instance in the case of SPRM+). It seems that the parameter tuning for SPRM+ amounted to stepsizes in $\\{0.01, 0.1, 1\\}$ but it is not clear to me if a grid search was performed, and if that would impact the compute times accordingly.\n- The sentence in Line  307: \"Unfortunately, to the best of my knowledge...\" is oddly phrased and could be restructured.\n- \"do\" in Line 48 should be \"are\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)