# Convergence of Regret Matching in Potential Games and Constrained Optimization

arXiv: https://arxiv.org/abs/2510.17067 · HTML: https://mlsanity.com/paper/2510.17067/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 56 references that are in the map.
- First posted on arXiv 20 Oct 2025.

## Builds on (most cited first, 26 of 26)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos](https://mlsanity.com/paper/1703.01138/) (2017)
- [Efficient Regret Minimization in Non-Convex Games](https://mlsanity.com/paper/1708.00075/) (2017)
- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [Regret Matching+: (In)Stability and Fast Convergence in Games](https://mlsanity.com/paper/2305.14709/) (2023)
- [Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms](https://mlsanity.com/paper/2406.10631/) (2024)
- [Alternating Mirror Descent for Constrained Min-Max Games](https://mlsanity.com/paper/2206.04160/) (2022)
- [Learning in Congestion Games with Bandit Feedback](https://mlsanity.com/paper/2206.01880/) (2022)
- [Faster Game Solving via Hyperparameter Schedules](https://mlsanity.com/paper/2404.09097/) (2024)
- [Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent](https://mlsanity.com/paper/2404.13891/) (2024)
- [Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games](https://mlsanity.com/paper/2311.00676/) (2023)
- [Extensive-Form Game Solving via Blackwell Approachability on Treeplexes](https://mlsanity.com/paper/2403.04680/) (2024)
- [General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chess](https://mlsanity.com/paper/2506.01242/) (2025)
- [The Computational Complexity of Single-Player Imperfect-Recall Games](https://mlsanity.com/paper/2305.17805/) (2023)
- [Semi Bandit Dynamics in Congestion Games: Convergence to Nash Equilibrium and No-Regret Guarantees](https://mlsanity.com/paper/2306.15543/) (2023)
- [A Bridge between Polynomial Optimization and Games with Imperfect Recall](https://mlsanity.com/paper/2002.09941/) (2020)
- [Computing Game Symmetries and Equilibria That Respect Them](https://mlsanity.com/paper/2501.08905/) (2025)
- [The Value of Recall in Extensive-Form Games](https://mlsanity.com/paper/2412.19659/) (2024)
- [Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games](https://mlsanity.com/paper/2510.04407/) (2025)
- [On the O(1/T) Convergence of Alternating Gradient Descent-Ascent in Bilinear Games](https://mlsanity.com/paper/2510.03855/) (2025)

## Built on by (most cited first, 2 of 2)

- [Decision Making under Imperfect Recall: Algorithms and Benchmarks](https://mlsanity.com/paper/2602.15252/) (2026)
- [Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling](https://mlsanity.com/paper/2607.25835/) (2026)

## Abstract (arXiv)

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 ε-KKT point after Oε(1/ε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). 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 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^+. Our lower bound shows that convergence to coarse correlated equilibria in potential games is exponentially faster than convergence to Nash equilibria.