Convergence of Regret Matching in Potential Games and Constrained Optimization
Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang, Ioannis Panageas, Vincent Conitzer, Tuomas Sandholm · 2025
Read Convergence of Regret Matching in Potential Games and Constrained Optimization by Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang, Ioannis Panageas, Vincent Conitzer, Tuomas Sandholm (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-17067.txt.
Introduction
Ioannis Anagnostides and five co-authors study a classic learning rule for games in this 2025 paper. The rule, regret matching, shifts play toward moves that would have done better. It drove big wins in poker, yet its math beyond two-player duels stayed unclear. A plus form of the rule also shines on hard limit tasks.
The authors prove the plus form reaches a near-best point under limits quite fast. Bounded regret can make that speed even better. By contrast, the plain rule can take vastly longer in some shared-payoff games. That gap is the first of its kind shown for these rules. The work gives the plus form a firm base as a solver.
Catalog record
| CREATOR | Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang, Ioannis Panageas, Vincent Conitzer, Tuomas Sandholm |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-17067
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convergence of Regret Matching in Potential Games and Constrained Optimization Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang, Ioannis Panageas, Vincent Conitzer, Tuomas Sandholm 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 + \texttt{RM}^{+} ) —attain strong performance on benchmark constrained optimization problems, outperforming traditional gradient descent-type algorithms. We show that alternating RM + \texttt{RM}^{+} converges to an ϵ \epsilon -KKT point after O ϵ ( 1 / ϵ 4 ) 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 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 ϵ ( 1 / ϵ 2 ) O_{\epsilon}(1/\epsilon^{2}) . From a technical standpoint, while RM + \texttt{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 sharp contrast, our second main result establishes a lower bound: 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 + \texttt{RM}^{+} . Our lower bound shows that convergence to coarse correlated equilibria in potential games is exponentially faster than convergence to Nash equilibria. 1 Introduction Regret matching is a foundational online algorithm for minimizing regret . It was famously introduced by Hart and Mas-Colell 2000 , although its conception can be traced much further back to the seminal approachability framework of Blackwell 1956 , which lay the groundwork for online learning and regret minimization. As the name suggests, regret matching prescribes playing each action 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—and modern versions thereof—has been at the forefront of equilibrium computation in massive two-player zero-sum games. A notable variant with strong empirical performance is regret matching + , introduced by Tammelin 2014 ; the only difference is that it truncates all negative coordinates of the regret vector to zero in every iteration. Even so, this variant is typically far superior than its predecessor, and was a central component in AI poker breakthroughs [ Bowling et al. 2015 , Brown and Sandholm 2017 , Brown and Sandholm 2019b , Moravčík et al. 2017 ] and a more recent superhuman agent for dark chess [ Zhang and 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 and Schapire 1999 ] . More broadly, in general-sum games, no-regret algorithms guarantee convergence to the set of coarse correlated equilibria [ Moulin and Vial 1978 ] —a more permissive concept than Nash equilibria. In this paper, we 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 simplices. Surprisingly little is known about this question even though it was identified early on as an important open question in this space [ Kleinberg et al. 2009 , Marden et al. 2007 ] . Recent empirical evidence brings this question to the fore again: Tewolde et al. 2025a showed that the regret matching family—and especially regret matching + —attains strong performance on a benchmark suite of constrained optimization problems, significantly outperforming gradient descent-type algorithms. 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. 1.1 Our results We analyze the convergence of regret matching (\texttt{RM}) and regret matching (\texttt{RM}^{+}) in the general class of (nonconvex) optimization problems constrained over a product of probability simplices. This encompasses as a special case Nash equilibria in potential games when the objective is multilinear. More broadly, to have a 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 mostly focus on the alternating version of \texttt{RM}^{+} , whereby players update their strategies one after the other, akin to coordinate descent. Our main result for \texttt{RM}^{+} is summarized below. Theorem 1.1 . Alternating \texttt{RM}^{+} converges to an \epsilon -KKT point of any optimization problem over a product of simplices after O_{\epsilon}(1/\epsilon^{4}) iterations. This theorem confirms that \texttt{RM}^{+} is a sound and efficient first-order optimizer, lending further credence to the empirical results of Tewolde et al. 2025a . We hope that Theorem 1.1 will help cement \texttt{RM}^{+} in the optimization arsenal going forward. Our argument proceeds by parameterizing the rate of convergence of \texttt{RM}^{+} as a 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 T^{-1/2} . Theorem 1.2 . Suppose that the regret of \texttt{RM}^{+} on each individual simplex grows as at most T^{\alpha} for some \alpha\in[0,\nicefrac{{1}}{{2}}] . Then \texttt{RM}^{+} converges to an \epsilon -KKT point after O_{\epsilon}(1/\epsilon^{\nicefrac{{2}}{{1-\alpha}}}) iterations. \texttt{RM}^{+} always guarantees regret growing as \sqrt{T} , 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 to KKT gap: as we point out in Proposition 3.2 , a sequence can incur zero regret while having an \Omega(1) KKT gap in each iteration. Even so, Theorem 1.2 directly relates the KKT gap in terms of the regret. In particular, the non-asymptotic rate of Theorem 1.1 is a consequence of the fact that \texttt{RM}^{+} has the no-regret property! In the special case of potential games, regret is known to bound the rate of convergence to coarse correlated equilibria ; Theorem 1.2 shows for the first time that regret can also dictate the rate of convergence to Nash equilibria. On a similar vein, a further important consequence of Theorem 1.2 is that, in symmetric potential games, simultaneous \texttt{RM}^{+} converges under a symmetric initialization. Corollary 1.3 . Simultaneous \texttt{RM}^{+} converges to an \epsilon -Nash equilibrium of any symmetric potential game. Furthermore, if convergence to CCE happens at a rate of T^{-(1-\alpha)} , for some \alpha\in[0,\nicefrac{{1}}{{2}}] , the rate of convergence