SOURCE-LINKED INTELLIGENCE

Constant regret in general games via higher-order optimism

arXiv · AI, language, vision and robotics · article · Sep 3, 2026 · UTC

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

Read original source ↗ Open in workspace

recordType

paper

region

Global