Convergence of Regret Matching in Potential Games and Constrained Optimization
Authors: Ioannis Anagnostides
Emanuel Tewolde
Brian Hu Zhang
Ioannis Panageas
Vincent Conitzer
Tuomas Sandholm
Venue: ICLR 2026 Poster (2026)
Keywords: regret matching
no-regret learning
potential games
constrained optimization
Primary area: optimization
TL;DR: We show that regret matching+ converges quickly to approximate KKT points in constrained optimization while regret matching can take exponential time.

Abstract: Regret matching (RM)---and its modern variants---is a foundational online algorithm that has been at the heart of many AI breakthrough results in solving benchmark zero-sum games, such as poker. Yet, surprisingly little is known so far in theory about its convergence beyond two-player zero-sum games. For example, whether regret matching converges to Nash equilibria in potential games has been an open problem for two decades. Even beyond games, one could try to use RM variants for general constrained optimization problems. Recent empirical evidence suggests that they---particularly regret matching$^+$ (RM$^+$)---attain strong performance on benchmark constrained optimization problems, outperforming traditional gradient descent-type algorithms.

We show that RM$^+$ converges to an $\epsilon$-KKT point after $O_\epsilon(1/\epsilon^4)$ iterations, establishing for the first time that it is a sound and fast first-order optimizer. Our argument relates the KKT gap to the accumulated \emph{regret}, two quantities that are entirely disparate in general but interact in an intriguing way in our setting, so much so that when regrets are bounded, our complexity bound improves all the way to $O_\epsilon(1/\epsilon^2)$. From a technical standpoint, while RM$^+$ does not have the usual one-step improvement property in general, we show that it does in a certain region that the algorithm will quickly reach and remain in thereafter. In contrast, our second main result establishes that RM, with or without alternation, can take an exponential number of iterations to reach a crude approximate solution even in two-player potential games. This represents the first worst-case separation between RM and RM$^+$. Our lower bound shows that convergence to coarse correlated equilibria in potential games is exponentially faster than convergence to Nash equilibria.

Published as a conference paper at ICLR 2026
CONVERGENCE OF REGRET MATCHING IN POTENTIAL GAMES AND CONSTRAINED OPTIMIZATION
Ioannis Anagnostides Carnegie Mellon University ianagnos@ cs cmu. edu
Emanuel Tewolde
Brian Hu Zhang MIT zhangbh@csai 1.mmt.t..... edd
Carnegie Mellon University etewwl de@ cmu edu
Ioannis Panageas
Vincent Conitzer
Tuomas Sandholm" Carnegie Mellon University
University of California, Irvine ipanageae ics. uci edu
Camegie Mellon University University of Oxford conitzer êcs cmb edu
sandho 1m@ es cmu edu
ABSTRACT
Regret matching (RM)-and) and its modern variants -s foundational online algo- rithm that has been at the heart of many AI breakthrough results in solving bench- mark zero-sum games, such as poker. Yet, surprisingly little is known far in theory about its convergence beyond two-player zero-sum games. For example, whether regret matching converges to Nash equilibria potential games has been open problem for two decades. Even beyond games, one could try to use RM variants for general constrained optimization problems. Recent empirical ev- idence suggests that particulllllllyy regret matching* (RM*) (RM*))attain attain strong performance on benchmark constrained optimization problems, outperforming traditional gradient descent-type algorithms.
We show that RM converges to an e-KKT point after (L(ee²)) iterations, estab- lishing for the first time that it is a sound and fast first-order optimizer. Our ar- gument relates the KKT gap the accumulated regret, two quantities that are en- tirely disparate in general but interact in an intriguing way in our setting, so much so that when regrets are bounded, our complexity bound improves all the way to (.(1/e². From a technical standpoint, while RM+ does not have the usual one- step improvement property in general, we show that it does a certain region that the algorithm will quickly reach and remain in thereafter. In contrast, our second main result establishes that RM, with or without alternation, can take an exponen- tial number of iterations to reach crude approximate solution even in two-player potential games. This represents the first worst-case separation between RM and RMF Our lower bound shows that convergence to coarse correlated equilibria in potential games is exponentially faster than convergence to Nash equilibria.
INTRODUCTION
Regret matching is a foundational online algorithm for minimizing regret. It was famously intro- duced by Hart & Mas-Colell (2000), although its conception can be traced much further back to the seminal approachubility framework of Blackwell (1956), which lay the groundwork for online learning and regret minimization. As the name suggests, regret matching prescribes playing each ac- tion with probability proportional to the (nonnegative) regret accumulated by that action. Its appeal lies in its simplicity and scalability, being both parameter free and scale invariant.
Regret matching-ane and modern versions thereof- has been at the forefront of equilibrium computa- tion in massive two-player zero-sum games. A notable variant with strong empirical performance regret matching+ + introduced by Tammelin (2014); the only difference is that it truncates all neg- ative coordinates of the regret vector to zero in every iteration. Even so, this variant is typically far superior than its predecessor, and was central component in AI poker breakthroughs (Bowling
Additional affiliations: Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc.

---

Published as a conference paper at ICLR 2026
et al., 2015; Brown & Sandholm, 2017; 2019;; Moravčík et al., 2017) and more recent superhuman agent for dark chess (Zhang & Sandholm, 2025).
As such, the regret matching family of algorithms has rightfully been the subject of intense study in contemporary research. Much of this focus has been confined to two-player zero-sum games, where minimizing regret translates to convergence of the average strategies to minimax (equivalently, Nash) equilibria (Freund & Schapire, 1999). More broadly, in general-sum games, no-regret algo- rithms guarantee convergence the set of coarse correlated equilibria (Moulin & Vial, 1978)-a more permissive concept than Nash equilibria.
In this paper, examine the convergence of regret matching and its variants in the seminal class of potential games, and, more broadly, nonconvex optimization constrained over a product of sim- plices. Surprisingly little is known about this question even though was identified early on as an important open question in this space (Kleinberg et al., 2009; Marden et al., 2007). Recent empir- ical evidence brings this question to the fore again: Tewolde et al. (2025) showed that the regret matching family-and especially regret matching" aattcisn-atttinss atttains strong performance suite of constrained optimization problems, significantly outperforming gradient descent-type algo- rithms. Yet, there is no theory to suggest that regret matching will even asymptotically converge to approximate KKT points in constrained optimization, which are tantamount to Nash equilibria when dealing specifically with potential games. We fill this gap in this paper.
benchmark
1.1
OUR RESULTS
We analyze the convergence of regret matching (RM) and regret matching (RM+) in the general class of (nonconvex) optimization problems constrained over product of probability simplices. This encompasses as a special case Nash equilibria in potential games when the objective is multilincar. More broadly, to have unifying treatment of both settings, we think of each probability simplex as being controlled by a single player who is observing the corresponding part of the gradient.
We cover both the simultaneous and the alternating version of RM+ whereby players update their strategies one after the other, akin to coordinate descent. Our result for RM+ is summarized below.
Theorem 1.1. RMT converges to an e-KKT point of any optimization problem over a product of simplices after Ox(1/e) iterations.
This theorem confirms that RM+ is a sound and efficient first-order optimizer, lending further cre- dence to the empirical results of Tewolde al. (2025). We hope that Theorem 1.1 will help cement RM+ in the optimization arsenal going forward.
We remark that for potential games and constrained optimization over single simplex, the (1/c/( bound holds no matter how the regrets in (alternating) RM+ are initialized. For constrained opti- mization over multiple simplices-with or without alternation-we obtain the same rate by suitably initializing the regret vectors (Corollaries 3.11 and C.1I); for the usual parameter-free version of RMT in which the regret vectors are initialized at zero, we can only guarantee an inferior bound growing as (1/e²) (Theorem 3.12).
Our argument proceeds by parameterizing the rate of convergence of RM+ as function of the accumulated regret, so much so that if the regret with respect to each individual simplex remains bounded, the rate is improved all the way to T1222
Theorem 1.2. Suppose that the regret of RM* on each individual simplex grows as at most T for some a E [0, 3/2). Then RMT converges to an K-K point after (,(1/2n1-) iterations.
RM+ always guarantees regret growing VT, so Theorem 1.1 is implied by Theorem 1.2. What makes the latter theorem surprising is that, in general, regret is a fundamentally disparate property compared KKT gap: as we point out in Proposition 3.2, a sequence can incur zero regret while having an 2(1) KKT gap in each iteration. Even so, Theorem 1.2 directly relates the KKT gap in terms of the regret. In particular, the asymptoti rate of Theorem 1.1 is a consequence of the fact that RM+ has the no-regret property! In the special case of potential games, regret is known to drive the rate of convergence to coarse correlated equilibria (CCE); Theorem 1.2 shows, for the first time, that regret can also govern the rate of convergence to Nash equilibria. In particular, if convergence to CCE happens at a rate of ((1-a) for some a E [0, 1/2), the rate of convergence to Nash equilibria is slower than T 1=
2

---

Published as a conference paper at ICLR 2026
Regad matching
Regast matching
0.6
0.4
Figure 1: Illustration of our main results: RM+ always converges fast to KKT point while RM can take exponential time even in two-player identical-interee games, constructed in Section
From a technical standpoint, the key challenge is that RM does not have one-step improvement property: even if one initializes RM+ close to KKT point, RM+ can still grossly overshoot. And, of course, it is parameter-free algorithm, so the usual treatment of gradient descent-type algorithms that relies on appropriately tuning the learning rate falls short. In this context, our starting observa- tion is that, at least when the utility function is linear, RM is bound to improve the utility, although the improvement is inversely proportional to the norm of the regret vector (Lemma 3,3). This key property already suffices show that alternating RM+ will converge to Nash equilibria in potential games. For the more challenging setting where the updates are simultaneous or the objective is not multilinear, first show that one-step improvement holds conditional vector being sufficiently large (Lemmas 3.7 and C0).). To conclude the argument, we combine this property with the crucial insight that the l norm of the regret vector is monotonically increasing proportionally to the KKT gap (Lemma 3.8). This means that RM will never get stuck in a cycle: the regret vector would quickly grow in norm, at which point the one-step improvement promised by Lemma 3.7 kicks in.
the norm of the regret
Does RM share the same convergence properties as RM+? As reminder, the only difference that RM refrains from truncating negative regrets to zero. Even so, we find that this seemingly innocuous difference gives rise to an exponential gap the performance RM vis-à-vis RM+, manifested even in two-player identical-interes. games special case of potential games (Figure 1).
Theorem 1.3. There is two-player m X m adentical-interes game where RM, with or without alternation, requires mmm) iterations to converge an m e(1) -ap)-apprximmae Nash equilibrium.
This lower bound holds not just under adversarial initialization, but also when players initially mix uniformly at random, which is the most common initialization in practice.
Theorem 1.3 constitutes the first worst-case separation- let alone exponential between RM and RM+ Indeed, in zero-sum games, it is known that RM and RM both attain rate no faster than 1/2 (Farina et al., 2023), even though RM+ typically performs much better in practice. Theo- rem 1.3 provides further justification for opting for RM+ instead of RM, albeit in a fundamentally different setting.
The basic flaw of RM that underpins Theorem 1.3 is that, with a linear utility, it is not guar- anteed to improve the utility even when has large best-response gap; specifically, as we show in Lemma 3.6, the improvement is conditional gret. But herein lies the problem: it could take many iterations before the regret resurfaces to being positive. What happens in the construction behind Theorem 1.3 that it takes longer and longer- exponentially so so-for the regret of the unique good-enough action to be positive; before then, RM entirely stalled without making any progress. At the same time, RM is guaranteed to converge to the set of coarse correlated equilibria (CCE) at rate of 7 1 simply because it always has the no-regret property. This leads to the following interesting consequence.
a good-enough action having nonnegative
Corollary 1.4. There a class of two-player potential games in which RM converges to an e-CCE in (1/f22 rounds but it takes exp({((1ee) rounds converge e-Nash equilibrium.
3

---

Published as a conference paper at ICLR 2026
To be clear, convergence to CCE is meant in terms of the average correlated distribution of play, whereas convergence to Nash equilibria is in terms of the individual iterates produced by RM.
We defer further discussion on related work to Section A.
2 PRELIMINARIES
We begin by introducing potential games and the more general problem of constrained optimization over a product of simplices (Section 2. I), and then recall regret matching(*)) in Section 2.2.
2.1 POTENTIAL GAMES AND CONSTRAINED OPTIMIZATION
Normal-form games Our first key focus in this paper is potential games, which we rep- resent in the usual normal form. Here, we have n players, each of whom is to select an ac- tion a, from finite set A,, with mi == [A,] and m maxigisn mi. Under a joint ac- tion profile a = (a1...., an) E A X ... x An, each player E [m] receives a payoff given by utility function u, (a1....,,a)) an) + u. an) R with range bounded by 1. A player E [n] can randomize by specifying mixed strategy æ; E A(A.) = {2; E R E Eates x[aa;] = 1}. Player strives to maximize its expected utility, given by (. xr,)
II== B. [ap]. ). A key fact that the expected utility is multi- linear, in that (z........ Fn. (z,, (x-)) for some utility vector (x :) RA that does not Un (, ....................... ag) II xy [a. depend on I;; namely, (x = (E -0 (æ1,... I;-1, 2;+1. Fn). while we Here and throughout, we use the shorthand notation x-; recall that (:.-) denotes the inner product. Further, we use the shorthand notation BRGap,(a;; u;) ==
(E XA, u,(a),...,
m (ar 2;, u.) for the best-response gap.
The predominant solution concept game theory the Nash equilibrium (Nash, 1950).
Definition 2.1. A strategy profile (#)...., x.,) ) E (AA) x ... ((A,) is an e-Nash equilibrium if for any player e [n] and unilateral deviation x E (AA)), u, (z,, S (u,x; +
A standard relaxation of the Nash equilibrium is the coarse correlated equilibrium (Definition B. which can be attained by no-regret algorithms (Proposition B.2). While finding a Nash equilibrium hard even in two-player general-sum games (Daskalakis et al., 2008; Chen et al., 2009), our focus is on potential cemmes--quivalentty congestion games (Monderer & Shapley, 1996).
Potential games This is seminal class that goes back to the work of Rosenthal (1973). The defining property is the admission of global, bndeeeend function the potential whose difference reflects the benefit of any unilateral deviation.
Definition 2.2 (Potential game). An n-player game is potential game if there exists function A1 X x An > such that for any player i E [m] and actions o, of E A4, a E Xx Av,
क p(a a) - a(a,, a u,(a,, a-;) uu(a;, a.))
(1)
A special case of potential game worth noting is identical intteees game, which means that u1 (Z1,..... .x,) = = Un (I),.... .......,,,, for all .i,..., nn In the presence of only two players, this simplifies un (x1 (#1 x2) = (z), Arz) uz (1) 222 for common matrix A A x.
A (mixed) Nash equilibrium in potential games is amenable to (projected) gradient descent, but is likely hard compute when the precision > is exponentially small (Babichenko & Rubinstein, 2021). Our focus will be on algorithms whose complexity is polynomial 1/e.
Constrained optimization More broadly. beyond potential games, we are interested in computing Karush- Tacc--Tucker (ieeer(KK]))) (KKT))poim of function u X' + RR, where X = A(Ai) x.... A(Ar). We
assume that u, which is to be maximized, is differentiable over an open set X プ X and L-smooth, meaning that [/V((x)) Vu(=')]l < L||z-='' 2'112 for all x, x' E X: we recall that ||æ||| = v(z, x) denotes the (Fuclidean) & norm. We make the normalization assumption (xx a/e V n, u(=)))
4

---

Published as a conference paper at ICLR 2026
for all i E [n] and 2, E A(A.). The goal is to minimize the KKT gap, which measure by
KKTGap: & x max x, Vu(x)) E'EX
(R,, vxx)
(2)
A point with small KKT gap per (2) is also referred to as an approximate first-order stationary point, which an approximate fixed point of the (constrained) gradient descent mapping æ + lxxx + [V)())), where 7 I 1/2 and [Ix(-) is (Euclidean) projection mapping. A potential game can be seen as the special case which is multilinear.
2.2 ONLINE LEARNING AND REGRET MATCHING
Moving on, we now introduce RM and RM+ within the framework of online learning. Here, learner interacts with an environment over a sequence T rounds. In each round E [T]. the learner first elects mixed strategy æ (AA). The environment in turn specifies a linear utility function ((t) x + (x, ( for some utility vector u²() E RA;; it is assumed that (9) has range bounded by 1. In the full-feedback setting, (t) is revealed to the learner at the end of the tth round. The performance of the learner in this online environment is evaluated through regret,
Reg
max xt (AEA)
Σ (a' (1) (0).
Two popular algorithms for minimizing regret on the simplex are regret matching (RM) and regret matching* (RM+), formally defined Algorithms 1 and They both prescribe playing an action with probability proportional to the nonnegative regret accumulated by that action. Their only dif- ference is that RM+ always truncates the regret to 0; denotes the all-ones vector, whose dimension is omitted it is clear from the context, and [-] max(0,.) :) is the nonnegative part.
Proposition 2.3 (Zinkevich et al., 2007: Farina et al., 2021). For any sequence of utilities (u(t)) both RM and RMt guarantee that the &2 norm of (x(+) at most v mT..
In particular, for both RM and RM+ Reg!" (2) < |||(0])1|l> s |||r0]tlll S VmT.
Algorithm 1: Regret matching (RM)
Algorithm 2: Regret matching* (RM+)
Initialize cumulative regrets (0) <- 0: Initialize strategy (9) E (AA);
Initialize cumulative regrets y0() == O; Initialize strategy (1) E AAA);;
for 1o-111 1,
1...,,77 .T do
3 for = 1....,, do
Set (()) < (t(++));
Set ( (t-11))
4
if (()) # 0 then
if (())) * then Compute (() x- 0l*) / /100
5
Compute (+)) f- (t) /100
6
else
else
x11) +- (1-1);
a: (1-11)
Output strategy (()) E A(A);
9 Output strategy (1)) A(A);
Observe utility (1) E R-4,
Observe utility (1))) E TR:,A
11
(() (1--1) (t) (x)) u (1)1
(1) [m(((-1) + (n (o(1) (110)]++
Simultancous and alternating updates We are interested in the convergence of RM and RM when used by all players; in the constrained optimization setting, we think of having one player acting on each simplex, in direct correspondence with potential games. In this setting, the sequence of utilities (u,") () given input to player i [n] is determined by the strategies of the other players. If the updates are simultaneous, we have (t) = Vz, (c)())) for each player i E [n]. (In potential games, the potential function & plays the role of u, that u, u, (x In the alternating setting, we go through the players in a round-robin fashion = 1..... n. In the lazy version of the update, for fixed precision 0, we first compute u, V u( the best-response gap of player [n] is already most e, we refrain from updating that player,
(++1) 2.2.) If
5

---

Published as a conference paper at ICLR 2026
u(x))
0.3
0.4
0.5
0.6
0.7
Figure 2:
The example corresponding to Proposition 3.2, demonstrating that having zero regret, let alone sublinear, has no implications concerning convergence terms of KKT gap.
that 2. (t++1) = xz(") Otherwise, the player updates its strategy to z (+++ using ut") We refer to this scheme as e-lazy alternating updates (e-lazy simultaneous updates are defined similarly); one limitation of this lazy variant is that it is not "anytime algorithm."" in that needs to specify the precision beforehand. the more common, non-lazy version alternation, a player is updated regardless of the best-response gap; in the sequel, we obtain convergence results for both variants.
CONVERGENCE OF REGRET MATCHING*
In this section, we analyze the convergence of RM+ in potential games (Section 3.1), and more broadly, constrained optimization (Section 3.2). A central theme in our analysis of RM and RM+ is recurring connection between regret and convergence to KKT points.
Before we proceed, is worth highlighting that, general, the no-regret property is fundamentally different from convergence KKT points in nonconee problems. To begin with, point out that when the underlying function to maximized, u, is concave, then the no-regret property does imply convergence global optimum, from Jensen's 's inequality.
Proposition 3.1 (Under concavity, no-regret implies convergence). Let u be a smooth con- function. u(x(()) Z {))
online algorithm observes the sequence of utilities (Vu(aa(t))) then (T), where Reg(")) (4') the regret of the algorithm per (3). max u(x)) Reg("),
Thus, the algorithm has vanishing average regret, u(x(()) converges to max u(x) (in density). But beyond concave problems, no-regret algorithms do not necessarily guarantee convergence even to KKT point, as we point out below.
Proposition 3.2. For any T E N with = = mod 4, there exists polynomial function in [0, 1] and sequence of points (z such that
the regret of the sequence with respect to (Vu(x!")) is zero, while every point the sequence has an 12(1) KKT gap with respect the function u.
This is based on the 4-cycle 0.6 + 0.7 + 0.4 + 0.3 + 0.6. If the gradients observed at those points are 0.6 + 2, 0.7 - 0.4 + 2, 0.3 + 1, it follows that i) Σ Vu(a:(0) = 0 and ii) Ei= (1()) vu(x("))
O, which in turn implies that this sequence incurs zero regret. But, by construction, the gradients at those interior points have a large magnitude, which in turn implies that the KKT gap large. (That the average is local minimum is coincidental.) polynomial consistent with the above gradients is 90z 29 +416.622 208. 3z leading to Proposition 3.2. We note that the above sequence of iterates not realizable through an algorithm such as gradient descent.
POTENTIAL GAMES
We first analyze convergence in potential games. A key property, which paves the way for The- orem 3.4, is that, for a fixed utility vector, RM* has a one-step improvement property; the lemma below takes the perspective of single, arbitrary player in the game.

---

Published as a conference paper at ICLR 2026
Lemma 3.3 (One-step improvement of RM*). For any r E R:20 and u E RA,,, we define == 7/Imll::
if r 0, (AA) can be arbitrary. rf == [r + u (x) u/ + and x' "11111l),,, then
2 1
(a' x. u) 2 ||r'11
max u(a] - (ar, u
BRGap(æ, u)².
aeA
|r'll
If frr== 00 then (a. u) (x', ,,) 2 max u(a].
The left-hand side of (4) reflects the improvement in utility obtained by updating æ x'; in par- ticular, A u[a] - (ar, u) is the best-response gap of æ with respect to Lemma 3.3 implies that the utility is monotonically to Furthermore, so long as the regret vector is small enough, the improvement is bound to be substantial, being proportional to the squared best-response gap. It is worth noting that Lemma 3.3 holds no matter the initial regret vector subject to Rgo: this invariance always holds for RM (by definition of the update in Algorithm 2), but that is not so for RM (ef. Lemma 3.6).
grreasinng-ullsss the current strategy is already a best response
Convergence in potential games We now employ Lemma 3.3 show that alternating RM quickly converges to approximate Nash equilibria in potential games. Using the fact that the game admits potential (per Definition 2.2), have that for any round t [T), ((x( (f+1) x (
T ................................ 2x ) 2 E |r.""] BRGap, (t) uz (t) 2 (BRGap, (t) (0) > c). where we
used Lemma 3.3 together with the assumption that only players with more than e best-response gap update their strategies. The telescopic summation over t 1,..., T yields
1 BRGap, (x. (B (x, (,,"
&
eJ.
(5)
range
where P Prange denotes the range of the potential function. If in every round t E [T] there is a player
i E [n] such that (aG (1) > we have i 2 Ei my: 2 L where we
( 111 S (/ 12 S mVT (Proposition 2.3). We thus arrive at the following result. used that |||
[mn [mm+ )² rounds
Theorem 3.4. In any potential game, e-lazy alternating RM requires at most 1 1+
converge e-Nash equilibrium. More broadly, if (Ir(")]a 1l2 I C)n, for all [m] and some E [0, 1/21, it requires 1 (C(n.m)Ammp)) rounds, where 3 == 1/1-a.
22
This provides a convergence rate of T-1/4 to Nash equilibria. Notwithstanding Proposition 3.2, an intriguing aspect of Theorem 3.4 is that it connects convergence to Nash equilibria to the regret of RM In particular, RM did have the no-regret property, meaning that ||r:"") could only prove an exponential bound since Σ 1/2 = (log T). At the other end, when each player accumulates constant regret, Theorem 3.4 implies an improved convergence rate of 1/2
Q(t), one
One caveat of lazy alternating RM+ prescribed by Theorem 3.4 is that the desired precision should be known in advance in order to execute the algorithm. We address this limitation in Theorem C.7, where we show that the usual, non-lazy version also converges after (1(c/") rounds, albeit the cost of introducing an additional dependence in the total number of iterations.
Faster rates using discounting Next, we refine Theorem 3.4 through the use of discounted RM+ which means that the regret vector is multiplied by discount factor ft (0, 1] in each round; we spell out DRM* in Algorithm 3. This class of algorithms was introduced by Brown & Sand- holm (2019a), who showed that discounting drastically improves empirical performance sum games. Our next result shows that DRM with geometric discounting, that is, (f) 1 for some time- iimeiinvriian y E (0, 1). attains rate of 1/2 to Nash equilibria in potential games; this is considerably faster than the T- 1/4 rate for alternating RM+ guaranteed by Theorem 3.4. The basic reason is that D geometric maacnnniing-mminaiinnn the norm of the regret vector bounded by /m/y (Lemma C.2 and Corollary C.3), while still enjoying the one-step improvement property. Corollary 3.5. In any potential game, e-lazy alternating DRM with discount factor 7 E (0. 1) requires at most 1 + mDhang rounds to converge to e-Nash equilibrium. 2.4
zero-
7

---

Published as a conference paper at ICLR 2026
To our knowledge, this is the first time that discounting yields provable, worst-case improvement over the bound obtained for non-discounted RM
Regret matching Before we switch gears to the more general constrained optimization setting, it is instructive to examine the behavior of RM. It turns out that one can adjust Lemma 3.3, but with a crucial caveat: the one-step improvement property is now only conditional, as specified below.
Lemma 3.6. For any r E Rg0 and u E RA,, define == =/110lla. where 0 == mmx((r 0): if0 O, E ((A) can be arbitrary. 1f = r u (x,, u) 1 and xr' == 01/10'11,, where O' max(r', (rr, 0) of
O, then (a' x, u)) 2 10'll 100 1 z 110'11 (max u/a] (ar, u)) [r[a] 2 0}, where
a E arg E. u/a'). If = 0. then (x, u (x' u) 2 u[a].
We see that RM's one-step improvement is conditional on the regret accumulated thus far by a best- response action to be nonnegative. This is not artifact of our analysis; it alludes to a fundamental discrepancy between RM and RM+ that will be formally established later on (Theorem 4.4). The main issue with RM can be seen follows. If we consider utility vector (1, 0) and the initial regret vector is, say. (-R, R), it will take RM many iterations prriiionn-pppppttiinnlllll to the magnitude of R > 0-1o finally change strategies, although this will eventually happen with a stationary utility,
3.2 CONSTRAINED OPTIMIZATION AND SIMULTANEOUS UPDATES
We now treat the more general setting where we are maximizing an L-smooth function u.
Single simplex We begin with the special case of a single probability simplex, = (AA). Our first goal is to adapt Lemma 3.3. The key challenge is that RM+ does not have one-step improve- ment, unlike algorithms such as gradient descent (for a small enough learning rate), even if one initializes RM close KKT point. But we observe that if the norm of the regret vector is large Sraugh-having small regrets is an obstacle here, in contrast to Section we are guaranteed a one-step improvement in terms of the value of the function (Lemma 3.7).
x) To do so, we will use the basic quadratic bound, which yields u(x²) 2 u(x) + (Vu(x)), -x) 4 - x' x'1:3: we think of x' as the updated strategy starting from œ. Using slight refinement of Lemma 3.3, we first have the lower bound (æ' - xx, Vu(Φ)) 2 |p. ||r - 1'2 (Lemma C.5).
Also, we observe that | æ'111 S |r--ri -r 1 + |r (Lemma C.6). We are now ready to establish conditional one-step improvement when the regret vector has sufficiently large norm. Lemma 3.7. Let u be an L-smooth function over A(A). For any r E TA with r * O, we define x == 7/1l=l1. Further, let r' = Vu(xx) - (z. Vu(x))1]+ * 0 and x' == +//11//11- If ||r' 2 max(2m, (2m,,mL..), 9mL.), then u(x') - u(x) 2 2| (inax=-EAAA) (ar - x. vu(x)))²
[|rlla
Lemma 3.7 only shows a one-step improvement so long as the norm of the regret vector is large enough. But how can we guarantee that? would seem possible that RM* ends up cycling in perpetuity under regret vector with small norm. The following lemma shows that cannot happen; turns out that maintaining this monotonicity property for the norm of the regret vector crucial for designing an optimal variant of RM+ in zero-sum games (Zhang et al., 2025).
Lemma 3.8. For any RM guarantees [ ||r(t= + (1] where g()) (u( (V)(x(()), x()
is the instantaneous regret vector at round t.
In particular,
| 10 > (11)0-1) 122 l1g (ll 1+12 2 1|-( + (KTG
since 11 KKTGap(z (0)2 That is, not only is the 42 norm of the regret vector nondecreas- ing, but the increase is at least (KTGap((::())) at each round f E [T]. Combining with Lemma 3.7 yields the following.
Theorem 3.9. Let be an L-smooth function in A(A) C Rmm with range Urange and R = max(2m, 9mL.). RM+ requires most 1 (m (mmrrurgg R²)) rounds to reach an KKKTT point.
8

---

Published as a conference paper at ICLR 2026
Simultaneous updates in symmetric potential games We now use Theorem 3.9 to prove conver- gence of simultaneous RM* in symmetric potential games; our earlier result in Theorem 3.4 shows convergence for arbitrary potential games but for the alternating version. The symmetry assumption here means that A1 = Ai = = An = A and un (xc-)) = (2(x22) = ... = Un (x.-)) when .n It is further assumed that all players initialize from the same strategy, that
211 22
the previous property implies that, inductively, it will be the case that x x2 (t) = ... x for
all t under simultaneous updates because players observe exactly the same utility vector. A simple example of this is a two-player game with a common, symmetric payoff matrix A = AT. Then un (1x2) Azz and (21)) = Am the previous assumption is satisfied.
Corollary 3.10. In any symmetric potential game, simultaneous RM+ converges to an e-Nash equi- librium after (,(1/e²) rounds. In particular, if convergence the set of CCE happens rate of T-(1-o), for some a [0, 3/2), the rate of convergence to Nash equilibria no worse than T -
Multiple simplices We now have the necessary tools to analyze the general case where we maxi- mize over product of simplices. Similarly to Theorem 3.4, we run alternating RM thinking of every individual simplex as being controlled by a single player; this is akin to coordinate descent. Corollary 3.11. If u is an L-smooth function in A(A1)
((A,) with range Urange e-lazy alternating RM+ initialized at T [2/m; 9 Lm for each player E [n] requires at m² m Mangg rounds to reach an K-KKT point of u.
most 1+
The proof follows directly from Lemma 3.7 together with telescopic summation. The non-lazy version of RM* admits qualitatively similar bound, following Theorem C.7. Furthermore, a similar bound holds even under simultaneous RM* (Corollary C.11), which follows by extending Lemma 3.7 multiple simplices (Lemma C.10).
One caveat of those results is that the regret vector of each player needs to be initialized at a specific threshold. Our next result addresses this limitation by analyzing the usual parameter-free and scale- invariant version of RM+ at the cost of introducing worse dependence on 1/e.
Theorem 3.12. If u is an L-smooth function in A(A1) x... A(A,) with range Urange- E-lazy alternating (or simultaneous) RM requires at most O (1///) rounds to reach an c-KKT point of u.
4 EXPONENTIAL LOWER BOUNDS FOR REGRET MATCHING
In stark contrast, we show that RM, with or without alternation, can take exponentially many rounds to reach an approximate Nash equilibrium even in two-player adentical-interest games. The underly- ing class of games is based on the one considered by Panageas et al. (2023a), who treated fictitious play. Specifically, for m
4, 6,6.... and & E N we define the matrix Am,k per the recursion
K ++1 0
0
0
44 4
1k + 1
Rmxm Am,k
where A2,
Am A,
k+2
2
1:
k+
0
k+ 0
+
(An illustrative example appears in Section C.2.) For any even dimension m. we define A = Am.o-
with maximum entry 2m 1. Further, we define, for S a1 I m + and 1 S a2 I m
A 0g)
[1 S m and 02 S m;
Biai, 02] =
1/2
if (a: = m + and a2 = 1) or (a) and 02 = m + 1);
(6)
0
otherwise.
The action sets of the two players are A im + 1] As. We assume that RM is initialized at the pure strategy (m + 1, m + 1); Section C.2 shows how to adapt the lower bound when RM is initialized at the uniform random strategy (Corollary C.16), which is more common. We recall that one round includes one update from each player, which for now is assumed to be made in a simultaneous fashion. For payoff &o E N. denote by a (k), (2)) [m] the and column index, respectively, corresponding to k in the matrix A.
We begin by stating basic invariance concerning the behavior of RM when executed the game (6).

---

Published as a conference paper at ICLR 2026
Property 4.1. After the first round both players play the first action. Thereupon, either the players play with probability 1 (k), (2(k)), or, when k is odd, only Player (respectively, Player 2 when k is even) mixes between (k) and a, (k 1] (respectively, (2(K) and a2 + 1)). If a row column stops being played, it will never be played henceforth. An action profile (a1 (k++)) az (2(k+1))
(k),azl az(k)) was played at some previous round. is played with positive probability only if (01 (k)(k),
We prove this property inductively in Section C.2. We take it for granted in what follows.
In accordance with Property 4.1, for h 2 2, we define & to be the first round which the action profile corresponding to payoff played with positive probability and la the last round before the action profile corresponding to payoff k + 1 is played with positíve probability. We then define Th = 2 t + 1 to the number rounds corresponding to the period [x).
We also define (k)
(k)(k)= 2m k' 2 k). These are the rows and columns. respectively. that will be played after the action profile corresponding to k starts being played. The next crucial lemma shows that before an action becomes desirable, it will have accumulated very negative regret in the previous rounds.
k k} and A2(k)
(ay(k)) 2m -
(fe-2) [a1] be the regret of Player I with respect to any action Lemma 4.2. For any even k 2 4, let 1
a1 E (1k).. Then ri [ail < E TYT, Similarly, for any odd 1o 2 5, if (Ts
[az] is
the regret of Player 2 with respect to any action a2 E A2()), T2 (0--2) [ao]
S - -E 1)2i.
At the same time, when action has very negative regret, it will take long time before that action gets played with positive probability, as formalized below.
Lemma 4.3. For any even 2 4, Ta 2 -322 (1 Jaz(k: + 1)]. Similarly, for every odd k 2 5,
T 2-
1"1
" (an (k + 1)]-
By Lemmas 4.2 and 4.3, follows that Tk 2 >K-1 1-1T; for any 2 4. By the inductive basis, 2
know that T3 2 1. As result, Tp T 2 k-2 k-2
2Ts
(k-2) 2
for all i: 2 4.
Moreover, it takes as least T2m-2 rounds to converge to an NE with approximation gap at most 1/2m+2 (Lemma C.15). We thus arrive at the following exponential lower bound.
Theorem 4.4. Simultaneous RM requires m(m)) rounds to converge to a 2m -ash equilibrium in two-player m X m iieentical-interes games.
The same reasoning directly applies to alternating RM.
-Nash equilibrium in Corollary 4.5. Alternating RM requires m m(m) rounds to converge to a 2m
two-player X edenticallinteeee games.
5 FUTURE RESEARCH
Our paper sheds new light on the convergence properties of regret matching(+) in constrained opti- mization problems in general, and potential games in particular. We showed that RM is a sound and fast first-order optimizer; on the flip side, RM can be exponentially slow even in two-player identical- interest games. Several interesting questions remain open. It would be interesting to understand whether RM+, with or without alternation, can experience ((VT) regret in potential games; this is known be the case in zero-sum games (Farina et al., 2023), but remains unclear for the class of potential games. In light of our results, any improvement over the vT barrier would automatically translate into a faster convergence rate to Nash equilibria. Moreover, we have worked exclusively in the full feedback setting: extending our results under stochastic bandit feedback would be natural next step. Finally, does RM asymptotically converge even under alternating updates?
ACKNOWLEDGMENTS
Emanuel Tewolde and Vincent Conitzer thank the Cooperative Al Foundation, Macroscopic Ven- tures and Jaan Tallinn's donor-advised fund at Founders Pledge for financial support. Emanuel
10

---

Published as a conference paper at ICLR 2026
Tewolde is also supported in part by the Cooperative Al PhD Fellowship. Ioannis Panageas is supported by NSF grant CCF-2454115. Tuomas Sandholm supported by the Vannevar Bush Faculty Fellowship ONR N00014-23-1-2877 National Science Foundation grants RI-2312344 and RI-1901403, ARO award W911NF2210266, and NIH award A2401085001.
REFERENCES
Anastasios N. Angelopoulos, Michael I. Jordan, and Ryan J. Tibshirani. Gradient equilibrium in online learning: Theory and applications. arXiv:2501.08330, 2025.
Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1:67-96, 1974.
Yakov Babichenko and Aviad Rubinstein. Settling the complexity of Nash equilibrium in congestion games. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2021.
David Blackwell. An analog of the minmax theorem for vector payoffs. Pacific Journal of Mathe- matics, 6:1-8, 1956.
Avrim Blum, Eyal Even-Dar, and Katrina Ligett. Routing without regret: On convergence to Nash equilibria of regret-minimizing algorithms in routing games. In Proceedings of the ACM Sympo- sium on Principles of Distributed Computing, 2006.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' poker is solved. Science, 347(6218)) 8), January 2015.
Noam Brown and Tuomas Sandholm. Superhuman Al for heads-up no-limit poker: Libratus beats top professionals. Science, pp. eaao1733, Dec. 2017.
Noam Brown and Tuomas Sandholm. Solving imperfect- imperfect-information games via discounted regret minimization. In Conference on Artificial Intelligence (AAAI), 2019a.
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456): 885-890, 2019b.
Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Weiqiang Zheng. Fast last-iterate convergence of learning in games requires forgetful algo- rithms. In Neural Information Processing Systems (NeurIPS), 2024.
Yang Cai, Gabriele Farina, Julien Grand-Clémend Christian Kroer, Chung- Wei Lee, Haipeng Luo, and Weiqiang Zheng. Last-iterate convergence properties of regret-matching algorithms in games. In International Conference on Learning Representations (ICLR), 2025.
Volkan Cevher, Ashok Cutkosky, Ali Kavis, Georgios Piliouras, Stratis Skoulakis. and Luca Viano. Alternation makes the adversary weaker two-player games. In Neural Information Processing Systems (NeurIPS), 2023.
Darshan Chakrabarti, Julien Grand-Clément, and Christian Kroer. Extensive-form game solving via blackwell approachability on treeplexes. In Neural Information Processing Systems (NeurIPS), 2024.
Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Jourmal of the ACM, 2009.
Qiwen Cui, Zhihan Xiong, Maryam Fazel, and Simon S Du. Learning in congestion games with bandit feedback. In Neural Information Processing Systems (NeurIPS), 2022.
Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou. The complexity of computing Nash equilibrium. SIAM Journal Computing, 2008
Aaron Defazio and Konstantin Mishchenko. Learning-rate-- rate-frre learning by d-adaptation. In Inter- national Conference Machine Learning (ICMI), 2023.

---

Published as a conference paper at ICLR 2026
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive Black- well approachability: Connecting regret matching and mirror descent. Conference on Artificial Intelligence (AAAI), 2021.
Gabriele Farina, Julien matching+ stability and fast convergence in games. In Neural Information Processing Systems (NeurIPS), 2023.
Christian Kroer, Chung- Wei Lee, and Haipeng Luo. Regret
Yoav Freund and Robert Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79-103, 1999.
Julien Grand-Clément and Christian Kroer. Solving optimization problems with blackwell approach- ability. Mathematics of Operations Research, 49(2):697-728, 2024.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68: 127-1150, 2000.
Sergiu Hart and Andreu Mas-Coiell. Regret-based continuous-time dynamics. Games and Economic Behavior, 45(2):3553394, 2003.
Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization non-convex games. In International Conference on Machine Learning (ICML), 2017.
Amélie Héliou, Johanne Cohen, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. In Neural Information Processing Systems (NeurIPS), 2017.
Wassily Hoeffding and J. Wolfowitz. Distinguishability of sets of distributions. The Annals of Mathematical Statistics, 29(3):700-718, 1958.
Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is SGD's best friend: A parameter-free free dynamic step size schedule. In International Conference on Machine Learning (ICML), 2023.
Robert Kleinberg, Georgios Piliouras, and Éva Tardos. Multiplicative updates outperform generic
no-regret learning in congestion games: extended abstract. Proceedings of the Annual Sympo- sium on Theory of Computing (STOC), 2009.
Tai- Yu Ma and Philippe Gerber. Distributed regret matching algorithm for dynamic congestion games with information provision. Transportation Research Procedia, 3:3-12, 2014.
Jason R. Marden, Gürdal Arslan, and Jeff S. Shamma. Regret based dynamics: convergence in
weakly acyclic games. In Autonomous Agents and Multi-Agent Systems (AAMAS). 2007.
Linjian Meng, Youzhi Zhang, Zhenxing Ge, Tianpei Yang, and Yang Gao. Asynchronous predictive counterfactual regret minimization* algorithm in solving extensive-form games. 12770 2025.
Dov Monderer and Lloyd S Shapley. Potential games. Games and Economic Behavior, 14(1): 124-143, 1996.
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, May 2017.
H. Moulin and J.-P. Vial. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4):201- 221, 1978.
Tianlong Nan, Shuvomoy Das Gupta, Garud Iyengar, and Christian Kroer. On the (11/T) conver- gence of alternating gradient descent-ascent in bilinear games. arXiv:2510.03855, 2025.
John Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36:48-49, 1950.
Francesco Orabona and Dávid Pál. Coin betting and parameter-free online learning. In Neural Information Processing Systems (NIPS), 2016.
12

---

Published as a conference paper at ICLR 2026
Gerasimos Palaiopanos, loannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In Neural Information Processing Systems (NeurIPS), 2017..
Ioannis Panageas, Nikolas Patris, Stratis Skoulakis, and Volkan Cevher. Exponential lower bounds for fictitious play in potential games. In Neural Information Processing Systems (NeurIPS), 2023a.
Ioannis Panageas, Stratis Skoulakis, Luca Viano, Xiao Wang, and Volkan Cevher. Semi bandit dynamics in congestion games: Convergence to Nash equilibrium and no-regret guarantees. In International Conference on Machine Learning (ICML), 2023b.
Robert W Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2(1):65-677 1973.
Oskari Tammelin. Solving large imperfect information games using CFR+. arXiv: 2014.
Emanuel Tewolde, Brian Hu Zhang, Ioannis Anagnostides, Tuomas Sandholm, and Vince Conitzer. Decision making under imperfect recall: Algorithms and benchmarks. In Uncertuinty in Artificial Intelligence (UAI), 2025.
Andre Wibisono, Molei Tao, and Georgios Piliouras. Alternating mirror descent for constrained min-max games. In Neural Information Processing Systems, 2022.
Hang Xu, Kai Li, Haobo Fu, Qiang Fu, Junliang Xing, and Jian Cheng. Dynamic discounted coun- terfactual regret minimization. In International Conference on Learning Representations (ICLR), 2024a.
Hang Xu, Kai Li, Bingyun Liu, Haobo Fu, Qiang Fu, Junliang Xing, and Jian Cheng. Minimizing weighted counterfactual regret with optimistic online mirror descent. arXiv:2404. 13891, 2024b.
Brian Hu Zhang and Tuomas Sandholm. General search techniques without common knowl- edge for imperfect-information games, and application to superhuman fog of war chess. arXiv:2506.01224 0422, 2025.
Brian Hu Zhang. Ioannis Anagnostides, and Tuomas Sandholm. Scale-invariant regret matching and online learning with optimal convergence: Bridging theory and practice in zero-sum games. arXiv:2510.044000 2025.
Naifeng Zhang, Stephen McAleer, and Tuomas Sandholm. Faster game solving via hyperparameter schedules. S0K.:::2004090097 2024.
Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. Regret minimization in games with incomplete information. In Neural Information Processing Systems (NIPS), 2007.
13

---

Published as a conference paper at ICLR 2026
A FURTHER RELATED WORK
Much of the existing research on regret matching revolves around zero-sum games. Many variants have been proposed over the years to speed up its convergence (Xu al., 2024b; Cai et al., 2025; Chakrabarti et al., 2024; Meng et al., 2025; Farina et al., 2021; Tammelin, 2014; Brown & Sandholm, 2019a). Some notable variations that have considerably improved performance are predictive RM and RM+ (Farina et al., 2021), which rely on predicting the next utility, and discounted RM and RM+ (Brown & Sandholm, 2019a; Zhang al., 2024; Xu al., 2024a), where one dynamically discounts the accumulated regret; in a similar vein, our work shows that a discounted variant of RM* achieves better convergence upper bound than RM+ in our setting (Corollary 3.5). Moreover, alternation is known to speed up performance, at least in sero-sum games (Tammelin, 2014), and has been the subject of much recent research (Wibisono et al., 2022: Cevher et al., 2023: Nan al., 2025). It must be stressed that the focus of all that prior work was on zero-sum games. Constrained optimization a fundamentally different problem. For one, in zero-sum games, is only the average strategy of RM and RM+ that converges, not the last iterate (Farina et al., 2023).
The recent paper of Tewolde et al. (2025) demonstrated that the regret matching family is a formidable first-order optimizer in constrained optimization problems. In particular, their focus was on (single-player) imperfect-recall problems, which are tantamount to general polynomial optimiza- tion problems games are actually reversed in constrained optimization. For example, the predictive versions of RM and RMT generally performed worse than their non-predictive counterparts. One trend that did persist was the superiority of RM+ over RM. It is also worth mentioning an earlier work by Ma & Gerber (2014) that also reported fast empirical convergence in certain class of congestion games. Yet, there was hitherto no theoretical understanding of those algorithms in this setting. The main precursors of our work are the paper of Hart & Mas-Colell (2003), which established asymptotic convergence in discrete time but for somewhat artificial variant of regret matching, and the paper of Marden al. (2007), which analyzed asymptotically a certain variant of regret matching that aggressively discounts the regrets (cf. Corollary 3.5).
product of simplices. Interestingly, many of the trends observed in zero-sum
An interesting result that sheds light on RM and RM+ is by Farina et al. (2021), who showed that RM can be obtained by running follow the regularized leader (FTRL) in a certain lifted space, whereas RM+ can be obtained through mirror descent (MD) in the same space; this is despite the fact that, un- like FTRL and MD, RM and RM+ are both parameter free. On a related note, Cai et al. (2024) showed that only forgetful algorithms-Cae closer to MD than to FTRL- can attain fast last-iterate convergence. Our exponential separation of RM and RM+ echoes their finding, although in different setting and class of algorithms.
Zooming of the RM family, understanding the convergence of no-regret dynamics in potential games has been a popular research topic (Kleinberg et al., 2009; Héliou et al., 2017; Palaiopanos et al., 2017; Panageas et al., 2023b; Cui et al., 2022; Blum al., 2006). Our research also relates to parameter-free optimization; for example, we refer to Ivgi et al. (2023); Orabona & Pál (2016); Defazio & Mishchenko (2023) and references therein.
B FURTHER BACKGROUND
Coarse correlated equilibria For completeness, we provide the definition of a coarse correlated equilibrium (Moulin& & Vial, 1978), which is a relaxation of correlated equilibria (Aumann, 1974). The key connection that relates to our results that if all players in a normal-form game have sublinear regret, the average correlated distribution of play converges to the set of coarse correlated equilibria. In particular, the rate of convergence is driven by the maximum of the players' regrets (Proposition B.2).
Definition B.1 (Coarse correlated equilibrium). Consider an n-player game in normal form. A correlated distribution μ E A(Ai x... An) is an e-coarse correlated equilibrium (CCE) if for any player e [n] and deviation of E A..
ui ulaa....,,. an) (2
( ui ua a-i) -
14

---

Published as a conference paper at ICLR 2026
Proposition B.2. eaec player E [n] observes the sequence of utilities (u:(w (i) the average
correlated distribution of play is an e-CCE with S 1 maxigisn Reg,") (T) where Reg, (T) is the regret of the ith player.
This connection holds for simultaneous updates. It is unclear if and how it can be extended under alternating updates. For the special case of potential games and RMT, which is our main focus here, we are indeed able establish convergence to the set of CCEs even under alternating updates by bounding the path length of the players' strategies (Remark C.9).
Other notions of regret Section 2.2 introduced the usual notion of regret used in online lin- ear optimization. For constrained optimization problem with respect to a differentiable func- tion u. have Reg()) max Ei= ax()), v=u(x<())) This is linearized version of max Ex (u(=') - u(x(")). Minimizing the latter notion is computationally intractable unless one places restrictive assumptions on Hazan et al. (2017) (ef. Angelopoulos et al., 2025) introduced the notion of "local regret," and showed that having sublinear local regret implies that a randomly selected iterate will be approximate stationary point; this is in stark contrast to regret as defined in Section 2.2 (Proposition 3.2).
Discounting Next, we spell out regret matching* with discounting (DRM*; Algorithm 3). The only difference from RM is that the regret vector is multiplied by a discounting coefficient (!)) (0, 1] in every round t [T] (Algorithm 3); the special case where ! I for all t E [2] is RM
Algorithm 3: Regret matching* with discounting (DRM*)
Input: discounting coefficients (a.), ((!) E (0, 1]";
Initialize cumulative regrets (0) = 0;
Initialize strategy (x)) E AAA);
for 1. t= 1,..,,,777 do
Set (()) < (((-1)
if (()) # 0 then Compute (()) + 0 /000
else
20 (1-1))
Output strategy (+) E ((A):
10
Observe utility (1) E TR:,;
11
(() t (r(t)) + ((t) (x(*), u 11)1};
12
C OMITTED PROOFS
This section provides the proofs missing from the main body. We begin by stating simple lemma that bounds the regret of RM* implying Proposition 2.3; we will then adapt to account for dis- counting per Algorithm 3.
Lemma C.1 (Regret vector upper bound). For any time E [T], RM+ guarantees (0
1) 12 (1-()-))
(1 where g()) == (t()) (xx(1) ul0) ) is the instantaneous regret at time t.
Proof. By definition of RMT, (r(t-1), ,),(()))))))) (x) (()) since (t) x (t-11) Thus.
|r [|| + (1) 113 (t-1) (()) 10 (t-11) + (*) 11
(0))
by orthogonality.
As result, the telescopic summation yields || < Σr (lg s mf since (|
(by the assumption that the range of the utilities is bounded by 1). It is worth noting that a similar proof works for RM. We now adapt Lemma C.1 for DRM+
Lemma C.2. For any time &. E (T], DRMt guarantees ||
(1 (1))
15

---

Published as a conference paper at ICLR 2026
Proof. As before, (r(t-1),g") ((("))) (2xt)) ( = 0 since (1)) xr(t11). Thus,
(1) [1(")))1(=((11)) + 11 S (a10)) + 9 1 (a (1))))(10((11) + (1)).
A direct consequence is the following bound on the regret vector. Corollary C.3. For any time E [T], DRM guarantees
10 S (a (2 1 (a "0")
(t-1))
II T==
a 11
In particular, if ()) = 1 - "y for some constant 7 E (0, 1), it follows that || S mm/..
Proof.
The first part of the claim follows by unfolding the bound of Lemma C.2. For the second part, using (7) and the fact that l1g (0) I m for any we have
S 1 || S m ((1 - --- (1 7) (1 - 7)² S m - (1 - 7) 7
(1 (1-
C.I PROOFS FROM SECTION 3
We continue with the proofs from Section 3. We first establish that RM+ enjoys a one-step improve- ment property when the utility is linear.
Lemma 3.3 (One-step improvement of RM*). ). For any r E R: and u E RA,,, we define a == 1/Ilihi ifr r = 0, x E (A) can be arbitrary. If = -rr + u
(c,, ue) + 0 and w' = =r' ='/1lr'll /llr'll,, then
2
1
(x' x. u) 2 ||r'112
max us(a] (or, (ar,
BRGap(æ,, u)).
aEA
|r'll
Ifr' =0 then (x, u) = (x', u) 2 max.E u(a].
Proof. First, if r' 0. it follows that
(x. u I O, where the inequality is to be taken coordinate-wise Since r 2 O, we have (ar, u) 2 ula] for all a E A, as claimed.
We assume r' # 0. Ifr r expressed as
have r' = lu- (ax, 1]] + (4) can then be equivalently
Σ [aa][(u[a] - (x, ue)
maxu(aa - (xx u)
aEA
aEA
which holds since r' (u (n,, u.) 1| So we can assume r * O. We define 5 = r' - r. (4) can be expressed as
Eces (r(a) + oaaa))l(a Edea(r (r(a') + 8la'))
2 Eeesrlalufs
(max.e u(a] (z, u))²
EaEAria
Eaee (rla) 0
Equivalently,
Σ r(aa'] Σ (r(a) + ola))u(a|
Σ r(a] Σ
(rla') + +o(aa))u(aa
a'EAA
acA
aeA
a'EA
Σ d'Ed
r[a']
[maxu(a]= (zx, u)
asA
This in turn is equivalent
En rla'] Σ
8la|u[a|
2 Σ r[a] Σ
8ia'|ulal + Σ r[a'l
max u ja] - (xx, un neA
C'EA
aed
acd
a'EA
a'EA
Σ
8
rla](a ui + Σ
ria']
max - (xc, un)
aEA
a'EA
aEA
a'EA
16

---

Indeed, we consider the two-dimensional problem in which To incur a best-response gap of at most e/2, the player needs to allot a probability mass of at least 1/2 to the second action. In the meantime, the decrement of the first coordinate of p+)) will be at most while the increment of the second coordinate of r(()) will be at most e. But, for the algorithm Published as a conference paper at ICLR 2026
Rearranging,
rla'| Σ ''EA
Σ REA
[[a][u[a]]
(x, u)) 2 Σ
r[a'
(max uFal - (ax, u))
aEA
a'EA
Now, for any a E A such that ula] (z, u other hand, for a E A such that usa] (x, u 0, and the claim follows.
0, it follows that ō|a] u[a] - (xx, u)
2 0; on the
0, we have 8 0|a] S That is, (2((a) (x. u)
We will now show that Lemma 3.3 is, in certain sense, tight. We consider simple linear maxi- mization over the simplex. If the regret vector of RM+ can be initialized arbitrarily, as is the premise in Lemma 3.3, we make the following observation.
Lemma C.4. Consider a utility vector E IAA and some initial regret vector R2 3 (() + O. If (1) = /11/1100011 and = maxxe A u u[aa (zx(1), u) is the initial best-response gap, takes at least [| 11/2 iterations for RM+ to reach point (t with best-response gap at most c/2.
- e, 1) and p(2) = ([)((1)),, 0)-
to terminate, it must be the case that the second coordinate of (f) is at least as large as the first coordinate of p(), leading to Lemma C.4.
Now, given that (xx(0) (1(1), u) e, Lemma C.4 matches the bound obtained for this problem through Lemma 3.3 in the regime where [|r(")] is least large as I/e (so that the norm of (())
within a constant factor of that of (2)), by Lemma C.I).
Taking this argument step further, if we have regret bound of the form |||( [|1 S ||||1 O,))),
which holds when the utility is fixed, Lemma 3.3 implies that 2|[r|| + 4||r|| + +... +....+11ll. ( (1/c/) iterations suffice for RM+ to have best-response gap most when facing fixed utiliiy;; this follows by applying Lemma 3.3 first for all iterations in which the best-response gap is at least 1/2, then for all iterations in which is at least 1/4, and so forth.
Analysis of non-lazy alternating RM In the main body, we used Lemma 3.3 to argue that lazy alternating RM converges in potential games (Theorem 3.4). One caveat of the lazy version of alternation is that it requires knowing the desired precision ahead of time. We will now extend the analysis to encompass the usual version of alternation, albeit at the cost of introducing a further dependence on the iteration bound.
To begin with, we first state a direct refinement of Lemma 3.3 that we rely on; this refinement will also be useful in the more general setting of constrained optimization.
Lemma C.5 (Refinement of Lemma 3.3). Under the preconditions of Lemma 3.3,
1
(x' x. u)
>
||r
r' r'1
||
In particular, (8) implies (4) since ||-rr11 r' 2 (max.e. u[a] 32 by definition r'. The proof of Lemma C.5 is identical to that of Lemma 3.3.
The next elementary lemma shows that, so long as the norm of the regret vector is not too small, closeness in regrets implies closeness in strategies.
Lemma C.6. For RR,, 3 r, r' + let 7/Ilrla and xx ''/l1'/li Then
1
-| 2'11 S ||r 111
|
17

---

Published as a conference paper at ICLR 2026
Proof. The term æ[a] xaaa] can be expressed, for any A, as
r(a] r/[a] EvEA r[a']
|||| (1l0)/"de
Ex'es r'laa]
r(a')) rla -((a]))
||||| |rlb
and the claim follows.
With those two helper lemmas in hand, we are now ready to analyze (non-lazy) alternating RM+ in potential games,
Theorem C.7. In any potential game with utilities in [0,1], alternating RM+ requires most rounds to converge an e-Nash equilibrium, where ö; (xG u ( and 8 = minggin 8,.
625m n "
2
54,
The assumption that 8, > is without any loss in the following sense. The analysis requires that [|:]") 12 > for all i E [n]] and any sufficiently large t. By Lemma 3.8, it suffices a player incurs positive best-response gap some time. In the contrary case, if player always has zero best- response gap, it will always play the same strategy (by definition of RM# in Algorithm 2), thereby reducing potential game with
players. We further remark that, in accordance with Theo- rem 3.4, the bound in Theorem C.7 can be similarly parameterized in terms of the maximum regret incurred by a player. A more pedantic point about Theorem C.7 is that utilities are taken be in [0, 1], while in the rest of the paper we only assume that the range is bounded by 1; this innocuous assumption is used in Claim C.8 below.
Proof of Theorem C.7. By Lemma C.5, the telescopic summation after T rounds yields
Prange Σ a
1
|| (0)
T (1-1)
1 (0)
ri l1g. (9)
(1-1)11
(t-1)
|
max; ||r 111
Since 1|r(0 1|1 S my/ for any player i [m]. it follows that Σ E ||| (e+1) r 12 =
Prrga V VT.
range
As a result, after at most 2 2 rounds, there will be a time such r ( < e2, which in turn implies ||| (1)
that Ei= ||n (1) r ((-1) + Ei= [[(([((]])
rs (t-1) |12. (++1) (1t1))1) r 11 I c for all i E [n]. Now, by assumption, we know that |rr""|
l|2 2 6, > 0
for i E [m]. By the monotonicity property of the regret vector (Lemma 3.8, proven the sequel),
it follows that ||> (6)
2|2 2 6, > 0 for all & E [T+ 1] and E [n]. Consequently, applying Lemma C.6, we have ||=; ((+1) x S 2||r (+ r; 19 /6, S 22/me/6, since || ||1 S /mll ll2. Next, we
will make use of the following simple claim.
Claim C.8. Consider a normal-form game with utilities in [0, 1]. For any two joint strategies (#1...., xn) and (z'...., 2.),, it holds that (x, u. ux 1)lloc Ev | x/y for any player i [m].
Proof. We fix a player i E [n]. We have
(x) - ur(a'>)llo
Σ
uil:s am))
xv II (ig
[ar] II 877
a [ar]]
x
Σ
xx [ap] II Pfyli
II 20ly [aw] 8'
(10)
a
X
x/ 11,,
(11)
where (10) uses triangle inequality together with the assumption that [u,()] < 1. and (11) uses a bound on the total variation distance of product distribution terms of the sum of the total variation distances of its marginals (Hoeffding & Wolfowitz, 1958).
18

---

Published as a conference paper at ICLR 2026
Using this lemma, we now observe that l| u, (o) S Exer 1a || (t+1) x. 2
Eees [|a]{t) (f+1) s 1la I 2 for each i E [n], where δ = sin dz. Furthermore,
in view of the fact that ||r? r, 11 S c, it follows that |//," (x. (0) u ( Sc. Thus,
|| [a) (ar) u, u,( ) = || (1) 11s0 (2 u (t)
+ || uu (x (t) 1000 - 11
1000 + (a, u,
(1) ux(aa
S [u (1) 1100 - (x)
(t)
u (1))
+ 2 2|
(1) u. (2
(12)
4nym m
4n
n 5mm m
S 6 +
S
5
8
8
where (12) follows from the fact that (xr u un u
S
|
|11 1
(3)
un u,( S
llu! (a: since ||x! ||I = 1. We conclude that (ar) xn is an el ///m/m/a) -Nash
equilibrium; rescaling leads to the claim.
O
Remark C.9 (Convergence to CCE under alternating updates). The folk connection linking no- regret learning and coarse correlated equilibria (Proposition B.2) is predicated on the dynamics being executed in a simultaneous fashion. We observe that, in potential games, even alternating RM converges to the set of CCEs in the following sense. Lemma C.6 together with (9) imply that The Cauchy-Schwarz inequality in turn yields
E >i
|
(t+1)
101 Or(vT).
T Σ
2 T
Σ
Σ 1=1
o (++1)
22'1|1 S
((+1) 0 Σ
Σ 12 12= OT(T81))
(13)
1=1
Now, by the fact that RM+ has the no-regret property (Proposition 2.3), maxa/E Et= (a0
2x (t)
u (t) = Or(VT). Further, by Claim C.8 and (13), Σ [u, - u, ( 11m00 S
Σ Ex4s |2 (c-1)
x 11 1 (T(344) As result, we conclude that, for any player i E [n].
Σ (al oi u, (x(""))) (T(3)
max x (AA)).
This implies that the correlated distribution (1/4-1/4) (Proposition B.2); here, i==1 x
-- x. (t) is E-CCE for some
denotes the product distribution induced by
(a (1) ...,....,,)) (9))
Moving on, a further implication of Lemma C.4 is that having a large regret vector can slow down RM Employing discounting, in the form of DRM* (Algorithm 3), addresses this deficiency in potential games, as we prove below. It is worth stressing that while discounting is sensible when employing alternating RM+ in potential games, this is not the case in more general constrained optimization problems; there, having a regret vector with a small norm can impede convergence (cf. Lemma 3.7).
Corollary 3.5. In any potential game, e-lazy alternating DRM with discount factor - 7 E (0, requires at most 1 + m&ning rounds to converge to an e-Nash equilibrium.
2.
Proof. Lemma 3.3 can be directly adjusted for DRM+ the updated strategy x' = <//I''l where r' a/r + u (x. 1)+ + 0, remains the same since we only rescaled the regret vector by a. That is, for any u E IRA.
1 max u [a] (ar, u.) 2
(x' x. u)
|
aEA
The key difference compared to Theorem 3.4 is that we now maintain the invariance ||r!"0112 5 / vn for all E [n]] and E [T] (Corollary C.3). Consequently.
T n
T
1
BRGap, (1) uu (')21 (a." (()) > cf.
range
19

---

Published as a conference paper at ICLR 2026
If in every round / E [T] there is player [n)] such that BRGap, (at (0) x 6, have
@ Prange 2 (v=i(v/mme so T & mobange This concludes the proof.
Unlike RM and DRM, RM only has a conditional one-step improvement because the regret vector can have negative coordinates (ef.
& Kroer, 2024).
Lemma 3.6. For any E R22 and u E RAA, define == 0/10011s where 0 = max((. 0); iʃ0 E ((A) can be arbitrary. Ifr' = r (x, u. and x' 88 81/11'11,, where O' max(r' 0) #
then (x' x, u) 2 1 100' 2 2 [10'l (maX u[a] (xx, u))² [r[a] 2 0}, where
a E arg EA u(a') If = 0, then (a,, u) (x', u) 2 u(a].
Proof. We define = 0' Following the proof of Lemma 3.3, it suffices to show that
2
Σ
0(a') Σ (ul(a (x, u.) 2 Σ
0(a']
max u[a] (ar. [r(a] 2 0). (14)
aEA
a'EAA
acA
e'EAA
For an action a E A, we consider the following cases.
(x. u) 2 O, If usa]
-if r[]] 2 0, we have 8[a] = u[a] (x, u). -If < O, it follows that ô[a] > 0: in particular, ō[a] = 0 if r' s 0 and 8[a]
otherwise. As a result, 5/a] [uaa (z, u)) 2 O.
If u[a]
(x. u) < O.
-if r[a < O. we have 8[a] = 0 since 0la] = 0 = 0'(a). - if r(a] 0. it follows that 8[a] < O. Again, we have ó[a](u[a] (x, u)) 2 0.
Combining those items, (14) follows.
We now turn to the more general setting of constrained optimization. First, combining Lemmas C.5 and C.6 that were proven earlier, we formally show that RM* improves the value of the underlying function provided that the norm of the regret vector not too small.
Lemma 3.7. Let be an L-smooth function over A(A). For any ES with r + O. we define x = "/||=li1 Further, let r' = [r + Vu(x:) (x,, Vu(x)))]+ # and x' 1//10111- If || 2 max Im,L), then u(x') - u(()) 2 श|ा (ma) vu(x)))
Proof. Using the quadratic bound for u, we have
u(x') - u(xx) 2 (Vu(x) x' x)
7 || x 11
1
|r' [|2 ||r r'1l
||r r'1
+
(15)
2
(/r//1
||
9mL
||| - r'112
||| -
r'
(16)
|
2 2
|| r 11.
(17)
2 2|
where (15) uses the one-step improvement property (Lemma C.5) applied for u Vu(æ:) together with Lemma C.6; (16) follows from the fact that ||rl > ||r'|] m 2 ] |r'll since ||| || >
|r'||2 2 2m and (x x' Vu(z))] < 1 for all x' A(AA (per our normalization assumption); and (17) follows from the assumption that ||r/|] > 9mL
To make use Lemma 3.7, we next establish that the & norm of the regret vector under RM is nondecreasing.
20

---

Published as a conference paper at ICLR 2026
Lemma 3.8. For any RM guarantees |120011 || + | where g(
Vu(x(()) (Vu(z!t)) x (00)iii is the instantaneous regret vector round t.
Proof. We have r()) p(l-1) 1) max(g(()) -p((-1)) (element-wise)) so
|r(0) r((-1) 1|2 m (1) - 2 |1gg01/112
Further, (r((-1), p(()) - plt-1)) (n(t-1), max(g()) (t) (((tt)))) 2 ( 0. where we used the fact that r² 2 0, coordinate-wiss wise. Therefore,
| |r(t) (l(-1) + 11
1/2 = |m()) -( || (1( + 2(rl(-1) ,l0) r ((-1))
2 |r 112 + |1|g 1
as claimed.
Armed with Lemmas 3.7 and 3.8, now prove Theorem 3.9.
Theorem 3.9. Let be an L-smooth function in A(A) C R= with range Urange and R
max 9mL}. RM+ requires at most 1 1+ (m Re)) rounds to reach an e- K-KKT point.
Proof. Let Le [T) be the largest / such that || m2m, 9mL} R. By Lemma 3.8,
| 2 || " 2 ||r(-- + KKTGap(=:0));;
80.
KKTGa =
(1 (1) || = | R R².
(18)
1=1
Further, for any 2 Le + 1, we have [|r(001122 2 R since the l norm of the regret vector is nonde- creasing (Lemma 3.8) and | 2 R. Thus, by Lemma 3.7,
() ((t)) - (lot())))) <
Trange
(19)
tmf++1
Combining (18) and (19), together with the fact that ||r(0)112 I mvt.
Σ KKT s 21range R²
This leads the claim.
Next, we use Theorem 3.9 to establish that even simultaneous RM+ converges in symmetric potential games, as long as the players have the same initialization.
Corollary 3.10. In any symmetric potential game, simultaneous RM+ converges to an e-Nash equi- librium after (1/e²) rounds. In particular, if convergence to the set of CCE happens at a rate of T1-1-a), for some [0, 1/2), the rate of convergence Nash equilibria is worse than T- 1- -
Proof. We will argue that simultaneous RM+, under the same initialization, in a symmetric game tantamount to running RM+ with respect to the function ((A) + ((x,.... Φ),, where A = An = A. We first claim that for any a E A.
(0(2 x))
@Φ(1
(20)
Ox(a]
dxy(u
By definition, (( x.,)) is multilinear. Let consider monomial of + of the form
Ma (Zi,..., ....,,,,)),.)))......... = x [a]]
21

---

Published as a conference paper at ICLR 2026
for some joint action an)
Aı ... An. Then
........
a
II (ala'))ale')
Ox(a
[a)aa
a'EAA'
if E A' and otherwise,
(21)
where A' = A'(a) fa' E A: 3i E [n] such that a' = asf and degrees d(a') = Ki E [m] d'Hl for a' A'. Further,
=
im (I......InI dr.(a [a]
II [ararl i a;
otherwise.
In particular,
ima (1.,.... Fn
1{a = a, (afaa(()))1
II d'EA'Maa
(ola'))aa)
[a
As result,
ima (2i...,..., Rn) 0x; [a]
e (((
II (ajaa))dio)) a'EA'\a)
which matches the expression in (21). That is, we have shown that for any E Ai ... x An.
(aa............................. Ox[a]
(21... [x]
Since ( xn,) = EaE X., ((a)ma (x x,,, (20) follows by linearity. Moreover, the symmetry assumption concerning the potential tells us that
@1 )n)
($ Fnn
dx [a]
dz [a]
for any i E [ns]. Combining with (20), we have that for any a A,
@Φ(x (D(x..... 0 19............................ Fn)
E [n].
Ox(a|
de,
Given that RM+ scale invariant, we conclude that simultaneous RM* on the potential game is equivalent to running RM+ on the function A(A) e x + (( x), and the claim follows from Theorem 3.9.
We now turn to the analysis of alternating RM+ in constrained optimization problems over multiple probability simplices. We clarify that when the regret vector is initialized at IRA, r (0) 0, as assumed below, the first strategy must be defined consistently as x; (1) (0) Corollary 3.11. If is L-smooth function in A(Ai) alternating RMF initialized at T max{2 9 m, 1 for each player E [n] requires at most 1 An mm? ? rounds reach c-KKT point of u.
r
((AA) with range Urange- c-lazy
Proof. By Lemma 3.8, it follows that || (1) 2 ||,; (0) l|2 = max L), Following the proof of Lemma 3.7, we have
u( u(x ysi ,
(t+1)
(8) - u( u(x ( x
((+1)
2
(o.". (..))) (zBRGa > c).
2||r 11
22

---

Published as a conference paper at ICLR 2026
As result, the telescopic summation yields
ΣΣ i= 2
(af", ) ( (xR ,u!") e) I Urange
Since ||r/"/11 I myi for all i E [n] and [7], it will take at most 1 + 4m a u / rounds to converge to a point in which all players have at most an e best-response gap, which in turn implics that the KKT gap is at most Ne. Rescaling concludes the proof.
To analyze simultaneous RM+ we adapt Lemma 3.7 as follows.
Lemma C.10. Let u be an L-smooth functionn over A(A1) x ... x (AA)). For any E [n] and ri e Riz0 with r; o O, we define x; == "1/1lr:lla- Further, let r/ = [r, + Va, u(x) (as, Vn, u())())) o
O and æ = ri/ Ir/ll1 If 1|r 2 max (2m4, I,,L) for any i E [ni]. then
u(xx) u(x)) 2 2 maxisisa 11
max (0) - xs. Vn, u(())) ai EA(A))
Proof. Using the quadratic bound for u, we have
u(x') u(x)= 2 (Vu(x), x' - x)) _ 11 - x' x'112
V 2i( (x) xt xz)) - 2 20, x116
1 ||:: r/l12
2 ||, r311
(22)
||r/l|
||rell
||mill
9mn L
|r///11 ||rs
ril1
||r: - -r(ll
(23)
2 2||r
|R?
IV
|1 |r,
r:113)
(24)
2
where (22) uses the one-step improvement property (Lemma C.5) applied for each player i E [n] and
u, == Va, u(x) together with Lemma C.6; (23) follows from the fact that ||rı||ı 2 | m 2
|ll since ||r/l| 2 ||r/l22 2 2m; and (ax; ai, Va, u(x))] S for all a (AA,) (per
our normalization assumption); and (24) follows from the assumption that ||r]] 2 9mn for each i [n].
Similarly Corollary 3.11, we can now show the following concerning simultancous RM
Corollary C.11. If is an L-smooth function in A(A1) x... A(An) with range urange. simul- laneous RMt initialized at r = max maxx22/mm)) (2./m;, 9/mm,) for each player E [n)] requires at most 4n 2o2mp m ulage rounds to reach K-K point of u.
Proof. By Lemma 3.8, it follows that ||r 112 2
||r [|r:0)12 (,,,;;;;;,,,,) By Lemma C.10,
((x(++))) - (²) 2 2n maxisiga [1r
(KKTGap(Zo()))
and the claim follows.
Next, we show how extend the analysis even when the regret vector is initialized at zero, at the cost of incurring a worse dependence on l/e.
Theorem 3.12. If u is an L-smooth function in A(Ai) x... A(Ax) with range Wrange e-lazy alternating (or simultaneous) RM requires most O. (1/e)) rounds reach an KKKTT point of
23

---

Published as a conference paper at ICLR 2026
Proof. We analyze e-lazy simultaneous RM*; the alternating version be treated similarly. If [|r(") l2 2 max max(2m; Im,L] for all players with best-response gap at least 6, we have that u(xel++)) u(x(()) is lower bounded by
(RG u )u (z) uf > c):
(25)
max; ||m
this follows similarly to Lemma C.10 since players with best-response gap below do not update their strategies (under lazy updates). Now, by Lemma 3.8, follows that the total number of rounds in which there is player with at least an best-response gap and ||r 22 < max[2m;, 9m, R₁ is at most Σx= (1 + R2/²).. We will now bound the number of rounds it takes to encounter two such rounds. We observe that, between such rounds, only update players that have least an e best-response gap and ||r
(*) 112 2 Rg By (25), this can continue for at most + 2t /T/2 rounds, where 7' is the total number of rounds it takes for all players to have best-response gap of at most c. That is, $ + 2n
Further, S T Ei= + R2/e),, and the claim
follows by solving in terms of T and rescaling c.
C.2 PROOFS FROM SECTION 4
We conclude with the proofs from Section 4. Below (left figure), we provide an illustrative example of the matrix B, defined earlier in (6), for m The plots in Figure are obtained by running simultaneous RM (left) and alternating RM (right) on this exact game. It is worth pointing out that one could also use staircase instead of pattaalpttttennn shown in the right figure.
1
0
0
0
4
0
+
0
0
9.
0
5
0
10
11
0
0
+
0
0
7
0
0
0
0
10
0
11
0.5
0
Our main goal is to prove the following invariance.
Property 4.1. After the first round both players play the first action. Thereupon, either the players play with probability (a1(k), (z(k)), or. when is odd, only Player (respectively, Player 2 when l is even) mixes between (k) and (kkk 11 (respectively. (z(k) and az(k + 1)). If a row column stops being played, will never be played henceforth. An action profile (a1 (k+ (1k+1). a2((k+1))
played with positive probability only if (ar (k) az(k)) was played at some previous round.
is possible to check the claim for k = 1,2,3,4 by executing RM for a certain number of rounds. In partieular, find that T3 2 5 and T, 20. We proceed by induction in k. Suppose that it holds for all payoff's K,...,K. K. We will show that it holds for x +
Lemma C.12. For any even 2
[ai] the regret of Player 1 with respect - 1YT, Similarly, for any odd + (Tx-2) [a2] S
ri (Tx-2)
any action 01 (k).. Then (tn-2) [an] is the regret of Player with respect to any action a2 A2(k), T2
k 5, r (2)-2) [a2] ((t-))))))))
2ー 1)T,
Proof. Let E Ai (k) and / [k- [ for an even Playing a (k) during [t., tj gives Player utility of 0; this follows from the fact that for any column dg [az(1), a2(3). ......
(3)...... a2(k: (k: 3)}
24

---

Published as a conference paper at ICLR 2026
2)}. it holds that (la)(k). m2] 0, by construction of A. At the same time, Player actually got a utility of at least - 1 for each round in it, f7]. This
{1z(1), (2(2), a2()).......)))..).......) ..... 02(k - 3), a2(k: (k:
means that every time Player updates its regret vector within the time period [4, 17], the regret of
aj decreases by at least I 1. The same reasoning applies for Player 2 when & is odd.
L
Lemma C.13. For any even 2 k 4, Tk 2 -2 (1--1) [a2(k 1)}. Similarly, for every odd _rr (1 [a (k: 1)].
K k 2 5, Tw
Proof. We fix an even h: 2 4. T3 is at least as large as the number of rounds it takes for 02 + 1)
to have nonnegative regret, starting from r2 (Tx 1) [a2(k: k + 1)]. But in every round in [/x, l&] the regret of 02 (A: 1) can increase additively by at most 2. This holds because the utility of Player 2 for
playing a2(k: + 1) is larger than the utility obtained in each round in [i 14] by at most 2. So,
Th 2 - 2-2 ( [a2kk + 1)]1 2 2 (8x-1) (a2 - 1)]. The same reasoning applies when k is odd.
The following upper bound on the regret is crude, but will suffice for our purposes.
Lemma C.14 (Regret upper bound). For any even R. 2 & 2 4, Il G4 11
I 2 2||lm (| |||||+1/ 11o0 +
2 $ $2//2 since || (t2)
I 3. Similarry, for any odd l 2 5, [[[ (2) + I 221112 2 + +2
00
_ f2(k-1)/2 1)/2 since ||
(ts)
1000
M 3.
Proof. The fact that ||r]
(2)
1
(a) Ibx S 3
4 can be shown as part of the basis of the induction. We
make the argument for an even k. From round l. until Player 1 plays an (k)) with probability 1, the
regret of (k) increases by k (kz) (4) [a1 (k)] (k- 1)=(" (d) [a (k- 2)]) 2 ( (k- 2)] and the
(1)
|oi
regret of 01 (k-2) 2) increases by k- lark--1(f (kx) (t) [a, (k)]+ (t) [a (k-2))) 2)) = = [a (k- (k-2)); 2)]; that is, it decreases by x 1 [a, 2)]. Let t' be the first round for which p(t') (ax (I)) 2 p((')(a (k-2) 2)]. It holds that (1))a) (k)) < |||r] (Th + +1 since the regret of an (k) is increasing
by at most in each round and r(() (k - 2)] s [[[r] [|[r((--)) [1] From then onward, the regret of ai (6) is increasing by at most 1/2 while the regret of a (k- - 2) is decreasing by at least 1/2. Thus,
it will take most [2)r(()) [a (k: - 2)]l s ()r(( (ar (k - 2)]l + 1 S 2|[[r(( (1x-a))+ bloc + 1 rounds for the regret of a1 (k- - 2) to be nonpositive. During that time, the regret of a1 (k) can increase by at most [|[r] (Tx 1| 1.
Proof of Property 4.1. If is odd, it suffices to prove that in every round in which Player 1 mixes between a1 (K) and aj (k+ 1), Player 2 plays (x(K) = a2(x+ (x++1 1) with probability 1. Similarly, if is even, it suffices to prove that in every round in which Player mixes between (2(k) and a2 + 1), Player plays an (x) an an(K + 1) with probability 1. Let us analyze the case where x is even; the odd case is similar. When Player starts mixing more and more to a2(1 + 1), it makes the row a1 (K + 2) more attractive for Player 2. By Lemmas 12 and C.13,
K
K 2 T-- S (K- 1)! 2x-2 T4
(K-22 2)!
(a + 2) <
T,
25-3 Ta-
(26)
2
2
At the same time, Lemma 14 implies that Player is mixing between (z(x) and a2 + 1) for at most [1] + Il 2 5 11/22 + 2 rounds. To see this, we observe that it takes at most rounds for the action az 1) to be played with at least the same probability as (z)),, which in turn holds because the regret of az(N + 1) increases by x?2 [a2(k)) while the regret of (2(s) decreases by xx2 [a2(<) (1:)] From then on, the regret of (2((s) decreases by at least 1/2 in each round, so it takes at most (
rounds for it to be nonpositive. We now claim
that, by (26), action a1 (Is + 2) is never played during those rounds. The reason is that since T3 2
and Ti 2 20 (by our inductive basis),
r (1. aa (N + +2)] < -20 (N 1)!
2)! 2
5
2
25

---

Published as a conference paper at ICLR 2026
and in each round the regret of (K + 2) can only increase additively by 2. Since
(
20 (n
1)!
(N 2)
2 + 5
2 > 5- 2(M-1/1/2
Vk 2 4,
the inductive step follows.
The next lemma shows that, under the invariance of Property 4.1, the only way to reach an ap- proximate Nash equilibrium is start playing the actions corresponding to 2m 1, which is the maximum payoff in the matrix.
Lemma C.15. Consider any strategy profile (x1, such that Player only assigns positive prob- ability to actions in {aı (k)), a1 a1(k= + 1}} and Player 2 only assigns positive probability to actions in (az(k), 02(k+ 1)}, where k ++I 1 < 2m 1. Then either Player I or Player 2 has deviation benefit of at least 1/k+2 - "y for any > 0.
Proof. By construction of the game, either a, (k) = a1 (k or (2(k) = ak We can assume that a1 (R) 01 (k++1) 1); the argument when 02 (2(k)) = 02 (k++1) is symmetric. Let be the probability Player 2 places at (= + 1) and 1 - p at (2(k). Suppose that the deviation benefit of each player is most e. The utility of Player under the current strategy profile is k(1 - p) (k 1)p k + p,
while deviating to 02 (k + 1) gives k + 1. So. p > 1 c. Given that k + < 2m - 1, Player
can deviate to 01 (k- 2) obtain utility of p(k + 2) S k ++ptc Combining with the fact that 2 1 - e, this implies 2 1/k42.
Uniform initialization So far, our lower bound assumes that one can initialize RM arbitrarily. A more common initialization prescribes randomizing uniformly at random. In what follows, we point out that the same argument works by considering a different common payoff matrix; namely,
A |aj 02]
if S 01 S m and S a2 S m; if a1 = and m + 1 I 02 S 2m;;
1
3
if m + 1 < 01 S 2m and a2 = 1;
u2]
1 Em
A(a1 dál
2 S
m and m + 1 S 02 2m:
m
1 >x
A/a a2]
if + 1 < 01 < 2m and 2 < 02 S m;
m2 Σ =1 -ag=1 A ab}
if + S 01 S 2m and m + S 02 S 2m.
m
By assumption, x² and x2 are the uniform distributions over [2m]]. We observe that
m
1 (1-- m
3
B Ba1,, 22)
A |ai, a2] + m
+
1
m
m
m
172
Σ
Σ
A Aa1,00)
02)
Σ Σ
A Aa1,ag]
Σ Σ
A [|1 0z] 2m
01
a2=2
02=1
m
m Σ
2
A Aa1 02]
A Aa11,0g]
-
A (ai, 02] 3
a1
0g
01 ag
41 -2
since!
1
Laz=1
A |aa
1, a2]
and Σmy=1 A A[0 a2
1]. In turn, this implies that
(1)
Bxy
(1)
Ear
2m
2m
B [a1, [2]
0. Let u (1)
B and u (1)
(1)
BTx o
(1) We
am
00
have
2m =1
1
Σm m
A(e1 = 1,02]
+ 2m m
1 =
if = 1: if2 < 01 m;
u (o)1
1
Σ =1
A (01, a2)
m Σay=1 A a2)
=0
2)
if + 1 S 01 S 2m.
2m
2m
Since (z) (1))) 0.
if = 1;
r1
(1)
[ai]
if ai < m
if + S a1 < 2m.
2m
26

---

Published as a conference paper at ICLR 2026
Similarly, we have
if = 1;
(1) 12 [22)
if 02 S m;;
if 1m++15m 02 S 2m.
2m
As a result, the second round sees both players playing the first action with probability 1. In view of the fact that Aaa 1, 02] < when I 02 and A/a1,
< 1 when d1 m, we immediately revert to the previous analysis concerning simultancous RM executed on the game described in (6). Thus, we arrive at the following lower bound (by change of variables m' 2m).
Corollary C.16. Simultaneous RM requires m m(m) rounds converge to m++1 -Nash equilibrium in two-player m m uniform random strategy.
games. This holds even when both players initialize at the
27


Reviews:
[{"review_id": "sKreH97YCc", "reviewer": "Reviewer_QJyC", "summary": "This paper studies the convergence behavior of regret matching (RM) and regret matching+ (RM+) in potential games and general smooth objectives over products of simplices. It proves that alternating RM+ converges to an $\\epsilon$-KKT point within $O(1/\\epsilon^4)$ iterations and achieves faster rates when per-simplex regret grows slower than $\\sqrt{T}$. The work establishes a formal link between accumulated regret and stationarity, showing how no-regret learning can yield approximate equilibrium in non-zero-sum settings.", "questions": "Can you expose the hidden constants in your $O(1/\\epsilon^4)$  rate for alternating RM+ and show their dependence on the number of players/actions, Lipschitz constants, and potential range?\n\nBeyond the symmetric setting, how far do your techniques extend to simultaneous RM+? Are there counterexamples where simultaneous RM+ fails to approach $\\epsilon$-KKT?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides the first general-purpose guarantees for RM+ beyond zero-sum settings. The core technical contribution is a careful connection between KKT gap and accumulated regret, which enables non-asymptotic convergence rates for alternating RM+ in nonconvex constrained optimization\n\n- The algorithmic scope is broad: the results cover any smooth objective over a product of simplices, with potential games as a key special case. Proving $O(1/\\epsilon^4)$  convergence to $\\epsilon$-KKT for alternating RM+ is a strong and clean statement\n\n- The lower-bound side demonstrates that plain RM can be exponentially slower than RM+ in potential games explains persistent empirical gaps between the two", "weaknesses": "- While the $O(1/\\epsilon^4)$   guarantee is valuable, it may still be pessimistic relative to practice. The analysis leaves the leading constants implicit and depends on problem parameters (e.g., action-set size, smoothness), which could be large in realistic instance\n\n- The alternating-updates requirement is algorithmically meaningful but differs from the fully simultaneous updates common in large-scale systems\n\n- The theoretical development assumes full-information gradients of a smooth objective on simplices and a normalization of payoff ranges. These are natural for analysis but leave open how the guarantees translate to bandit/partial information, stochastic gradients, or imperfect-recall sampling regimes", "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": "C7v0rYwkpj", "reviewer": "Reviewer_Zjs4", "summary": "This paper studies the behavior of Regret Matching variants in potential games. The two main results are to establish that:\n1. Alternating Regret Matching+ (RM+) has last-iterate convergence to Nash at a T^{-1/4} rate.\n2. Vanilla Regret Matching (RM), with or without alternation, has exponentially slow last-iterate convergence on a certain identical interest game. \n\nTo prove (1), the authors more generally show that alternating RM+ converges to approximate KKT points of (nonconvex) optimization problems over a product of simplices, and they also establish a similar rate of convergence to Nash in *symmetric* potential games under simultaneous RM+.", "questions": "High-level suggestions:\n+ It would be helpful to include some additional related work and discussion on the last-iterate convergence behavior of other families of learning algorithms in potential games (e.g., multiplicative weights / FTRL). See for example [Palaiopanos+2017, Cheung+2020, Anagnostides+2022]. \n\nHigh-level questions:\n+ Can you offer explanation as to where the proof of Theorem 3.4 fails when considering *simultaneous* RM+? Does the one-step improvement property of Lemma 3.3. still hold? In other words, is alternation necessary for Theorem 3.4 to hold?\n\n+ Similarly, for Corollary 3.10, are symmetric initializations necessary for the result to hold?\n\n+ Do you suspect faster convergence rates are achievable using other RM+ variants like predictive RM+, with or without alternation? \n\nLow-level questions/clarifications:\n+ In Proposition 3.1, the left-hand side of the final inequality seems like it should involve the function value of the average-iterate: e.g., $u(\\bar x^T) \\ge \\max_{x} u(x) - R(T)/T$ where $\\bar x^T = \\sum_{t=1}^T x^t/T$. Similarly, Line 265 should be adjusted to make it clear that, for concave u, vanishing average regret implies convergence of the average-iterate (ergodic convergence), and not last-iterate convergence as is currently written. \n\n+ L338: Do you mean to say that it is open whether RM+ can have $o(\\sqrt{T})$ regret in potential games? (we already know RM/RM+ has $O(\\sqrt{Tm})$ regret in general). \n\nOther typos:\n+ L265: extra superscript parenthesis in $u(x^t)$. \n+ L327: seems like bound should read $\\le m \\sqrt{t}$ (lower-case $t$, not $T$). \n\n----- \n\n[Palaiopanos+2017]: \"Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos\", NeurIPS 2017.\n\n[Cheung+2020]: \"Chaos, Extremism and Optimism: Volume Analysis of Learning in Games\", NeurIPS 2020.\n\n[Anagnostides+2022]: \"On Last-Iterate Convergence Beyond Zero-Sum Games\", ICML 2022.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Overall this is a nice work that offers new characterization of the last-iterate convergence properties of regret matching variants beyond zero-sum games. The positive convergence results for (alternating) RM+ for potential games is in contrast to non-convergence results of these algorithms in certain zero-sum games (Lee+2021 and Cai+2025). Establishing the connection between regret and KKT gap is also interesting. In general the paper is well-written and easy to follow. \n\n[Lee+2021]: \"Last-iterate Convergence in Extensive-Form Games\", NeurIPS 2021\n\n[Cai+2025]: \"Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games\", ICLR 2025", "weaknesses": "There are few areas that could improve the presentation: for example, some additional explanations and fixing or clarifying several incorrect statements (see these listed below in Questions).", "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": "U5WHUqX1Xs", "reviewer": "Reviewer_bT7s", "summary": "This paper investigates the convergence properties of Regret Matching (RM) and its popular variant, Regret Matching+ (RM+), in the context of potential games and, more generally, constrained optimization over a product of simplices. The authors provide two main, contrasting results. First, they establish for the first time that an alternating version of RM+ converges to an approximate KKT point in polynomial time, with a rate of O(1/ε⁴), confirming it is a valid first-order optimization algorithm. Second, they show that standard RM, with or without alternation, can require an exponential number of iterations to converge to even a coarse approximate Nash equilibrium in a simple two-player potential game. This provides the first exponential separation between the performance of RM and RM+, offering strong theoretical justification for the empirical preference for RM+ in practice.", "questions": "1.  How do you reconcile the strong empirical performance of RM+ (sometimes outperforming gradient descent, as mentioned in the introduction) with the relatively slow O(1/ε⁴) theoretical convergence rate you establish? Does this suggest that the worst-case instances for RM+ are rare in practice?\n2.  What are the primary technical hurdles to extending your convergence proof for simultaneous RM+ from symmetric games to general potential games? Do you suspect that simultaneous RM+ might fail to converge in the general case, or is the analysis just significantly more challenging?\n3.  Could you provide some higher-level intuition for why the seemingly minor modification of truncating negative regrets (the key difference between RM+ and RM) prevents the algorithm from getting stalled for an exponential amount of time? The paper proves this formally, but an intuitive explanation would be very helpful.\n4.  In Theorem 3.4, the convergence rate for alternating RM+ is parameterized by the growth of the regret. Can you comment on what typical or worst-case regret growth one might expect for RM+ in potential games?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.  The paper tackles a long-standing open problem about the convergence of regret matching in potential games. Establishing the first polynomial-time convergence guarantee for alternating RM+ in this general setting is a major theoretical breakthrough.\n2.  The exponential lower bound for standard RM is a very strong result. It clearly and definitively separates RM from RM+, explaining the performance gap often observed empirically. This separation in potential games is novel and fundamentally different from prior work focused on zero-sum games.\n3.  The paper is very well-written and structured. The introduction does an excellent job of motivating the problem, and the \"Our Results\" section clearly lays out the key contributions and their implications. The main theorems are stated precisely, and the narrative guides the reader effectively through the technical arguments.\n4.  The connection established between the KKT gap and the accumulated regret is intriguing and provides a novel analytical tool. The proof technique for the RM+ convergence, which handles the lack of a standard one-step improvement property, is clever.", "weaknesses": "1.  The proven convergence rate for alternating RM+ is O(1/ε⁴), which is quite slow compared to the O(1/ε²) rate often achievable with standard gradient-based methods for non-convex optimization. While being the first polynomial bound is a great achievement, it would be beneficial to discuss whether this rate is believed to be tight or if it is an artifact of the current analysis.\n2. The positive convergence result for simultaneous RM+ is restricted to symmetric potential games under a symmetric initialization. This is a fairly strong assumption and leaves the more general and arguably more practical case of simultaneous updates in arbitrary potential games as an open question.\n3.  The paper is entirely theoretical. While the introduction cites recent work showing the strong empirical performance of RM+, the paper would be strengthened by including even a small experiment.", "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": "PrlxNIiU2g", "reviewer": "Reviewer_GY2W", "summary": "This paper studies regret matching variants, particularly alternating RM and RM+ and explores the convergence of these algorithms to first order optima in constrained optimization problems and potential games. For computing approximate KKT points, the authors show that alternating RM+ converges after $O(1/\\epsilon^4)$ iterations,  though a $O(1/\\epsilon^2)$ bound can be obtained when the regrets remain bounded. This leverages a novel connection between regret minimization and KKT gaps. Using this result, it is also shown that simultaneous RM+ with symmetric initializations converge to approximate NE with the same complexity as given above. Next, RM is investigated and shown to possess exponential lower bounds, alternation or not. This shows a stark separation between RM and RM+, despite their similarity in terms of the update rule.", "questions": "- Have the authors investigated predictive/smooth predictive RM+ in potential games? Would the $O(1/\\epsilon^4)$ convergence remain in this case, or would there be some acceleration?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The results of this paper are strong, and resolve some open problems in the literature. The separation between RM and RM+ in terms of convergence rate is the first result of its kind.\n- The connection between KKT gap and total regret is to my knowledge novel in this setting and results in an intriguing algorithmic consequence of regret accumulation. Future work exploiting this connection would be very interesting indeed.\n-  The introductory sections are very clear and readable, even if the technical statements are relatively dense. This makes understanding the ideas of the paper much easier, particularly for readers who are not familiar with the material.", "weaknesses": "- While this is not the main point of the paper, perhaps more background and comparison between the convergence of RM+ and other online learning methods like FTRL/Mirror Descent can be added to the main text. This would help readers understand what is known about online learning in potential games, and why the result for alternating RM+ is important. For example, while MWU can exhibit chaotic behavior in potential games, while it seems that alternating RM+ avoids this.\n- The reliance on alternation seems to dissuade the practical use-case of learning in a decentralized, simultaneous environment (e.g. where players do not get to observe the strategies used by other players). Having some more results on the simultaneous case would greatly improve the paper. While it is clear why Lemma 3.3 leads to the alternating convergence result, the paper could do with more discussion on where the proof idea fails for the simultaneous case, or if there are further technical problems that arise.", "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)