Search papers, labs, and topics across Lattice.
This paper introduces a novel uncoupled learning algorithm called higher-order optimism with discounting (HOOD) for $N$-player normal form games, achieving an individual regret bound of $O(N^3\log^2 K)$. The algorithm combines a discounted $(N+1)$-th order predictor with entropic regularization, effectively dampening oscillations in play sequences, which has hindered previous approaches to constant regret. The results not only improve upon existing regret bounds but also align closely with concurrent work, highlighting the robustness of higher-order optimism in game-theoretic contexts.
Achieving $O(N^3\log^2 K)$ individual regret in general games could redefine strategies for multi-agent learning dynamics.
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^3\log^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.
