Constant Individual Regret in General Games

Uncoupled no-regret dynamics provide a decentralized route to equilibrium. We study horizon-independent individual regret in finite $N$-player normal-form games under full-information feedback. We show that standard Optimistic Hedge has worst-case regret at least exponential in either the number of players $N$ or the largest action-set size $m_{\max }$. This motivates 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. Simultaneously, for every horizon $T\ge 1$, each player in self-play incurs regret upper bounded by $O(N\log m_{\max })$. With a regret-dependent learning rate, it also guarantees regret bounded by the self-play bound plus $O(\sqrt{T\log m_{\max }})$ in the adversarial setting. More generally, we relate the regret bound to the order of the prediction-error filter's zero at one.