# Regret Matching+: (In)Stability and Fast Convergence in Games

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 38 references that are in the map.
- First posted on arXiv 24 May 2023.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions](https://mlsanity.com/paper/1910.10906/) (2019)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarks](https://mlsanity.com/paper/1905.12564/) (2019)
- [Online Convex Optimization for Sequential Decision Processes and Extensive-Form Games](https://mlsanity.com/paper/1809.03075/) (2018)
- [Stable-Predictive Optimistic Counterfactual Regret Minimization](https://mlsanity.com/paper/1902.04982/) (2019)
- [Revisiting CFR+ and Alternating Updates](https://mlsanity.com/paper/1810.11542/) (2018)
- [Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games](https://mlsanity.com/paper/2202.00237/) (2022)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)
- [Solving optimization problems with Blackwell approachability](https://mlsanity.com/paper/2202.12277/) (2022)
- [Clairvoyant Regret Minimization: Equivalence with Nemirovski's Conceptual Prox Method and Extension to General Convex Games](https://mlsanity.com/paper/2208.14891/) (2022)

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

- [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)
- [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)
- [Agents That Certify Their Own Exploits: Confidence-Scheduled Restricted Responses for Safe Opponent Exploitation](https://mlsanity.com/paper/2607.28520/) (2026)
- [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)
- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Optimistic Thompson Sampling for No-Regret Learning in Unknown Games](https://mlsanity.com/paper/2402.09456/) (2024)
- [Faster Game Solving via Asymmetry of Step Sizes](https://mlsanity.com/paper/2503.12770/) (2025)
- [Approximating Nash Equilibria in General-Sum Games via Meta-Learning](https://mlsanity.com/paper/2504.18868/) (2025)
- [Efficient Last-iterate Convergence Algorithms in Solving Games](https://mlsanity.com/paper/2308.11256/) (2023)
- [Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation](https://mlsanity.com/paper/2509.13653/) (2025)
- [Decision Making under Imperfect Recall: Algorithms and Benchmarks](https://mlsanity.com/paper/2602.15252/) (2026)
- [GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay](https://mlsanity.com/paper/2609.11923/) (2026)
- [IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence](https://mlsanity.com/paper/2610.19016/) (2026)

## Abstract (arXiv)

Regret Matching+ (RM+) and its variants are important algorithms for solving large-scale games. However, a theoretical understanding of their success in practice is still a mystery. Moreover, recent advances on fast convergence in games are limited to no-regret algorithms such as online mirror descent, which satisfy stability. In this paper, we first give counterexamples showing that RM+ and its predictive version can be unstable, which might cause other players to suffer large regret. We then provide two fixes: restarting and chopping off the positive orthant that RM+ works in. We show that these fixes are sufficient to get O(T1/4) individual regret and O(1) social regret in normal-form games via RM+ with predictions. We also apply our stabilizing techniques to clairvoyant updates in the uncoupled learning setting for RM+ and prove desirable results akin to recent works for Clairvoyant online mirror descent. Our experiments show the advantages of our algorithms over vanilla RM+-based algorithms in matrix and extensive-form games.