Research map / Bandits and online learning / Online convex optimization and games
Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows numerically that RM+ variants (RM+, alternating RM+, PRM+) fail to converge in last iterate on a 3x3 game, and proves last-iterate convergence for smoothed ExRM+ and SPRM+ (asymptotic, 1/sqrt(t) best-iterate, and linear with restarts).
Problem
Last-iterate convergence of regret-matching algorithms (RM+ and variants) for two-player zero-sum matrix games; their regret operator is non-Lipschitz on the full orthant and non-monotone.
Approach
Views smoothed RM+ variants (ExRM+, SPRM+) as extragradient/optimistic-gradient methods for a variational inequality with a non-monotone regret operator that satisfies the Minty condition; proves iterate convergence by characterizing the geometric structure of limit points (they lie on rays through the equilibrium set with equal norms), and adds restarts for linear rates.
Key results
- RM+, alternating RM+ and PRM+ keep duality gap around 1e-1 after 1e5 iterations on a 3x3 game with unique NE, while alternating PRM+, ExRM+ and SPRM+ reach machine precision within about 1e3 iterations.
- ExRM+ and SPRM+ are proven to converge in iterates (last-iterate) with O(1/sqrt(T)) best-iterate duality-gap rate.
- Restarted variants RS-ExRM+ and RS-SPRM+ achieve linear last-iterate convergence rates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ExRM+ instead of RM+ | RM+-based matrix-game solving · 3×3 matrix game | duality gap: on the order of 10^{-1} even after 10^5 iterations -> machine precision after 10^3 iterations | Helped |
| Use SPRM+ instead of RM+ | RM+-based matrix-game solving · 3×3 matrix game | duality gap: on the order of 10^{-1} even after 10^5 iterations -> machine precision after 10^3 iterations | Helped |
| Use alternating PRM+ instead of RM+ | RM+-based matrix-game solving · 3×3 matrix game | duality gap: on the order of 10^{-1} even after 10^5 iterations -> machine precision after 10^3 iterations | Helped |
| Use RM+, alternating RM+, or PRM+ without smoothing or extragradient updates | RM+-based solving · 3×3 matrix game | duality gap: on the order of 10^{-1} even after 10^5 iterations | Hurt |
| Use PRM+ or alternating PRM+ | RM+-based game solving · Kuhn poker | duality gap | Mixed |
| Use EG instead of the other compared algorithms | Game-solving algorithms · Goofspiel | duality gap: achieves machine precision | Helped |
| Use ExRM+, SPRM+, or EG instead of RM+, PRM+, or alternating RM+ | Game-solving algorithms · 25 random matrix games (10,15) | duality gap: vastly outperform | Helped |
| Use alternating PRM+ instead of the other compared algorithms | Game-solving algorithms · 25 random matrix games (10,15) | duality gap: outperforms all other algorithms | Helped |
| Use OG on random matrix games | Game-solving algorithms · 25 random matrix games (10,15) | duality gap | Hurt |
| Add restarting based on the halving-distance trigger | ExRM+ · Matrix games | duality gap: linear last-iterate convergence | Helped |
| Add restarting based on the halving-distance trigger | SPRM+ · Matrix games | duality gap: linear last-iterate convergence | Helped |
Surprising findings
- Vanilla RM+ and PRM+ fail to converge in iterates even on a game with a unique Nash equilibrium.
- Alternating PRM+ shows fast last-iterate convergence empirically despite no known theoretical guarantee.
Limitations
- Analysis restricted to matrix games; extension to extensive-form games via CFR is open.
- No concrete rate for non-restarted ExRM+ and SPRM+ last-iterate convergence.
- Alternating PRM+ has no theoretical guarantee.
Experimental setup
Datasets: 3x3 matrix game Kuhn poker (normal form) Goofspiel (normal form) random matrix games (10x15)
Benchmarks: 3x3 matrix game Kuhn poker Goofspiel random 10x15 matrix games
Metrics: duality gap
Baselines: RM+ alternating RM+ PRM+ alternating PRM+ EG OG
Builds on: Regret Matching+ Extragradient method Optimistic gradient Predictive RM+ Metric subregularity
Closest papers by meaning
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.93)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.91)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.91)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.91)
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.90)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.