Constant Regret in Finite Games via Higher-Order Optimism

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 finite games.