Constant Individual Regret in General Games
2026-08-31 • Machine Learning
Machine LearningComputer Science and Game Theory
AI summaryⓘ
The authors developed a new method called ECHO-OFTRL that helps multiple players learn to play a game well without needing to know others' strategies. Unlike earlier methods, their approach avoids a common big growth in error over time, keeping each player’s mistakes very low even after many rounds. They do this by combining an existing learning technique with a special averaging process inspired by signal filters. Their algorithm works for any number of players and action choices, and it guarantees a small, predictable regret (or error) for each player.
no-regret dynamicsnormal-form gamesuncoupled dynamicsoptimistic follow-the-regularized-leader (OFTRL)exponential moving average (EMA)regret boundsdecentralized learningfilter designgame theoryalgorithmic learning
Authors
Mingyang Liu, Gabriele Farina, Asuman Ozdaglar
Abstract
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 \emph{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 $m_{\max}$ denotes the largest action-set size, then, simultaneously for every horizon $T\geq1$, it guarantees that each of the $N$ players in the game incurs regret upper bounded by $O(\textrm{poly}(N, \log m_{\max}))$. Our algorithm leverages a new form of optimism inspired by modern filter design.