# Constant Individual Regret in General Games

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 26 references that are in the map.
- First posted on arXiv 31 Aug 2026.

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

- [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)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Acceleration through Optimistic No-Regret Dynamics](https://mlsanity.com/paper/1807.10455/) (2018)
- [Stable-Predictive Optimistic Counterfactual Regret Minimization](https://mlsanity.com/paper/1902.04982/) (2019)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [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)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Faster Rates for No-Regret Learning in General Games via Cautious Optimism](https://mlsanity.com/paper/2503.24340/) (2025)
- [Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games](https://mlsanity.com/paper/2506.05005/) (2025)
- [Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games](https://mlsanity.com/paper/2207.08426/) (2022)

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

- [Constant regret in general games via higher-order optimism](https://mlsanity.com/paper/2609.04113/) (2026)
- [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)

Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retain a polylogarithmic dependence on the horizon. We remove this dependence for every finite N-player normal-form game under full-information feedback. We introduce ECHO-OFTRL: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average. The algorithm is deterministic and fully uncoupled. If mmax denotes the largest action-set size, then, simultaneously for every horizon T≥1, it guarantees that each of the N players in the game incurs regret upper bounded by O(textrmpoly(N, log mmax)). Our algorithm leverages a new form of optimism inspired by modern filter design.