Constant regret in general games via higher-order optimism

arXiv:2609.04113v1 Announce Type: new Abstract: We introduce an uncoupled learning algorithm which, when employed by all players of an arbitrary N-player normal form game with up to K actions per player, guarantees O(N^3log^2 K) individual regret, uniformly over the horizon of play. The proposed algorithm - which we call higher-order optimism with discounting (HOOD) is a variant of optimistic follow-the-regularized-leader (OptFTRL) that combines a discounted (N+1)-th order predictor with entropic regularization over a suitable "lifting" of the game's strategy space. This combination of ingredients is purposefully designed to dampen large oscillations of the induced sequence of play in a controlled manner, removing in this way a key stumbling block of previous attempts to achieve constant regret in general games. Our approach bears several striking similarities to the concurrent - and completely independent - work of Liu, Farina, and Ozdaglar (arXiv:2608.31166), who very recently derived an O(N^{21}log^{4} K) regret bound through the use of higher-order optimism and an exponential moving average estimator.

Related

• Constant Individual Regret in General Games
• When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation
• Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization

Source: arXiv cs.LG | 2026-09-04