# Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2025.

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

- [Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret](https://mlsanity.com/paper/2602.06348/) (2026)
- [Constant Individual Regret in General Games](https://mlsanity.com/paper/2608.31166/) (2026)
- [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 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 introduce Cautious Optimism, a framework for substantially faster regularized learning in general games. Cautious Optimism, as a variant of Optimism, adaptively controls the learning pace in a dynamic, non-monotone manner to accelerate no-regret learning dynamics. Cautious Optimism takes as input any instance of Follow-the-Regularized-Leader (FTRL) and outputs an accelerated no-regret learning algorithm (COFTRL) by pacing the underlying FTRL with minimal computational overhead. Importantly, it retains uncoupledness, that is, learners do not need to know other players' utilities. Cautious Optimistic FTRL (COFTRL) achieves near-optimal OT(log T) regret in diverse self-play (mixing and matching regularizers) while preserving the optimal OT(√T) regret in adversarial scenarios. In contrast to prior works (e.g., Syrgkanis et al. [2015], Daskalakis et al. [2021]), our analysis does not rely on monotonic step sizes, showcasing a novel route for fast learning in general games. Moreover, instances of COFTRL achieve new state-of-the-art regret minimization guarantees in general convex games, exponentially improving the dependence on the dimension of the action space d over previous works [Farina et al., 2022a].