mlsanityData to 7 Oct 2026

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

arXiv 2305.14709 ↗First posted 24 May 2023cs.GT cs.LGcited by 13

Not on the map. Why?

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.

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

Builds on

20 of 38 references.

References · 20

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 228
  3. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  4. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  5. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  6. 2014Solving Large Imperfect Information Games Using CFR+cited by 78
  7. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  8. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 56
  9. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  10. 2019Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functionscited by 25
  11. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  12. 2019Correlation in Extensive-Form Games: Saddle-Point Formulation and Benchmarkscited by 23
8 more
  1. 2018Online Convex Optimization for Sequential Decision Processes and Extensive-Form Gamescited by 21
  2. 2019Stable-Predictive Optimistic Counterfactual Regret Minimizationcited by 21
  3. 2018Revisiting CFR+ and Alternating Updatescited by 19
  4. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  5. 2022Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descentcited by 15
  6. 2021Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solvingcited by 4
  7. 2022Solving optimization problems with Blackwell approachabilitycited by 4
  8. 2022Clairvoyant Regret Minimization: Equivalence with Nemirovski's Conceptual Prox Method and Extension to General Convex Gamescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 6; 2026: 3.

13 papers.

Sort:

  1. 2024Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descentcited by 7
  2. 2023Last-Iterate Convergence Properties of Regret-Matching Algorithms in Gamescited by 5
  3. 2025General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chesscited by 5
  4. 2026Agents That Certify Their Own Exploits: Confidence-Scheduled Restricted Responses for Safe Opponent Exploitationcited by 4
  5. 2025Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Gamescited by 3
  6. 2025Convergence of Regret Matching in Potential Games and Constrained Optimizationcited by 2
  7. 2024Optimistic Thompson Sampling for No-Regret Learning in Unknown Gamescited by 1
  8. 2025Faster Game Solving via Asymmetry of Step Sizescited by 1
  9. 2025Approximating Nash Equilibria in General-Sum Games via Meta-Learningcited by 1
  10. 2023Efficient Last-iterate Convergence Algorithms in Solving Gamescited by 0
  11. 2025Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformationcited by 0
  12. 2026Decision Making under Imperfect Recall: Algorithms and Benchmarkscited by 0
1 more
  1. 2026GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replaycited by 0