# Faster Rates for No-Regret Learning in General Games via Cautious Optimism

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 59 references that are in the map.
- First posted on arXiv 31 Mar 2025.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [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)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theory](https://mlsanity.com/paper/2012.03083/) (2020)
- [The Price of Anarchy in Auctions](https://mlsanity.com/paper/1607.07684/) (2016)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamics](https://mlsanity.com/paper/1401.3454/) (2014)
- [On the Interplay between Social Welfare and Tractability of Equilibria](https://mlsanity.com/paper/2310.16976/) (2023)

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

- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [Constant Individual Regret in General Games](https://mlsanity.com/paper/2608.31166/) (2026)
- [Comparator-Adaptive Phi-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games](https://mlsanity.com/paper/2505.17277/) (2025)
- [Optimal Alternating Regret for Online Learning and Games](https://mlsanity.com/paper/2608.24731/) (2026)
- [Constant regret in general games via higher-order optimism](https://mlsanity.com/paper/2609.04113/) (2026)
- [Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games](https://mlsanity.com/paper/2511.02157/) (2025)
- [Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games](https://mlsanity.com/paper/2510.16782/) (2025)
- [Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism](https://mlsanity.com/paper/2609.16751/) (2026)
- [A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games](https://mlsanity.com/paper/2609.22839/) (2026)

## Abstract (arXiv)

We establish the first uncoupled learning algorithm that attains O(n log2 d log T) per-player regret in multi-player general-sum games, where n is the number of players, d is the number of actions available to each player, and T is the number of repetitions of the game. Our results exponentially improve the dependence on d compared to the O(n, d log T) regret attainable by Log-Regularized Lifted Optimistic FTRL [Far+22c], and also reduce the dependence on the number of iterations T from log4 T to log T compared to Optimistic Hedge, the previously well-studied algorithm with O(n log d log4 T) regret [DFG21]. Our algorithm is obtained by combining the classic Optimistic Multiplicative Weights Update (OMWU) with an adaptive, non-monotonic learning rate that paces the learning process of the players, making them more cautious when their regret becomes too negative.