mlsanityData to 14 Oct 2026

Constant Individual Regret in General Games

arXiv 2608.31166 ↗First posted 31 Aug 2026cs.LG cs.GTcited by 3

Not on the map. Why?

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.

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

17 of 26 references.

References · 17

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 233
  3. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  4. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  5. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  6. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  7. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  8. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  9. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  10. 2018Acceleration through Optimistic No-Regret Dynamicscited by 22
  11. 2019Stable-Predictive Optimistic Counterfactual Regret Minimizationcited by 21
  12. 2021Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Updatecited by 20
5 more
  1. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  2. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  3. 2025Faster Rates for No-Regret Learning in General Games via Cautious Optimismcited by 10
  4. 2025Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Gamescited by 7
  5. 2022Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Gamescited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Constant regret in general games via higher-order optimismcited by 2
  2. 2026Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimismcited by 0
  3. 2026A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Gamescited by 0