SOURCE-LINKED INTELLIGENCE

Constant Individual Regret in General Games

arXiv · AI, language, vision and robotics · article · Aug 31, 2026 · UTC

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 hori

Read original source ↗ Open in workspace

recordType

paper

region

Global