# Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 58 references that are in the map.
- First posted on arXiv 6 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)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [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)
- [A new regret analysis for Adam-type algorithms](https://mlsanity.com/paper/2003.09729/) (2020)
- [On Last-Iterate Convergence Beyond Zero-Sum Games](https://mlsanity.com/paper/2203.12056/) (2022)
- [Adaptive extra-gradient methods for min-max optimization and games](https://mlsanity.com/paper/2010.12100/) (2020)
- [Last-iterate Convergence in Extensive-Form Games](https://mlsanity.com/paper/2106.14326/) (2021)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [Solving Large Sequential Games with the Excessive Gap Technique](https://mlsanity.com/paper/1810.03063/) (2018)
- [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)
- [Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria](https://mlsanity.com/paper/2105.12954/) (2021)
- [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)
- [Decomposition of games: some strategic considerations](https://mlsanity.com/paper/1901.06048/) (2019)
- [Corrupted Learning Dynamics in Games](https://mlsanity.com/paper/2412.07120/) (2024)
- [No-regret learning in harmonic games: Extrapolation in the face of conflicting interests](https://mlsanity.com/paper/2412.20203/) (2024)
- [LiteEFG: An Efficient Python Library for Solving Extensive-form Games](https://mlsanity.com/paper/2407.20351/) (2024)
- [A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition](https://mlsanity.com/paper/2504.03432/) (2025)
- [Optimism Without Regularization: Constant Regret in Zero-Sum Games](https://mlsanity.com/paper/2506.16736/) (2025)
- [Zero-Sum Games and Linear Programming Duality](https://mlsanity.com/paper/2205.11196/) (2022)
- [Pointwise Convergence in Games with Conflicting Interest](https://mlsanity.com/paper/2505.15454/) (2025)

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

- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Parallelizing Counterfactual Regret Minimization](https://mlsanity.com/paper/2605.14277/) (2026)
- [Scale-Invariant Fast Convergence in Games](https://mlsanity.com/paper/2602.11857/) (2026)

## Abstract (arXiv)

A considerable chasm has been looming for decades between theory and practice in zero-sum game solving through first-order methods. Although a convergence rate of T-1 has long been established, the most effective paradigm in practice is counterfactual regret minimization (CFR), which is based on regret matching and its modern variants. In particular, the state of the art across most benchmarks is predictive regret matching^+ (PRM^+). Yet, such algorithms can exhibit slower T-1/2 convergence even in self-play. In this paper, we close the gap between theory and practice. We propose a new scale-invariant and parameter-free variant of PRM^+, which we call IREG-PRM^+. We show that it achieves T-1/2 best-iterate and T-1 (i.e., optimal) average-iterate convergence guarantees, while also being on par or even better relative to PRM^+ on benchmark games. From a technical standpoint, we draw an analogy between (IREG-)PRM^+ and optimistic gradient descent with adaptive learning rate. Reflecting this theoretical bridge, we find that the adaptive version of optimistic gradient descent we consider performs on par with IREG-PRM^+. This demystifies the effectiveness of the regret matching family vis-a-vis more standard optimization techniques. Moreover, we extend our analysis beyond zero-sum games to a family of variational inequality problems that includes harmonic games, as well as extensive-form games with fully-mixed equilibria, via a new and intriguing connection between CFR and harmonic games. Unlike prior work in harmonic games, our algorithms do not require knowing the underlying weights by virtue of scale invariance. Under the weighted Minty condition, we show that any algorithm satisfying a scale-invariant RVU property (such as IREG-PRM^+) has constant regret (in self-play) and T-1/2 iterate convergence.