CONSTANT REGRET IN GENERAL GAMES VIA HIGHER-ORDER OPTIMISM

For decades, a central question in game theory and online learning has been whether uncoupled learning algorithms—where players update strategies based only on their own payoffs and observations—can prevent individual regret from accumulating indefinitely in arbitrary multiplayer games. While previous work established sublinear regret bounds (e.g., O(T^1/4) or O(log T)), achieving constant, horizon-independent regret in general-sum games remained an open challenge.

To address this, the authors propose a novel algorithm called Higher-Order Optimism with Discounting (HOOD). HOOD is a variant of the Optimistic Follow-the-Regularized-Leader (OptFTRL) framework. It incorporates three key innovations:

1. Lifted Regularization: The algorithm operates on a "lifted" strategy space that includes the origin, allowing the algorithm to control the positive part of the regret more effectively.
2. Higher-Order Prediction: Instead of using only the previous payoff to predict the next, HOOD uses a discounted (N+1)-th order predictor. This structure leverages the predictability of the game's payoff landscape to dampen oscillations.
3. Geometric Discounting: The predictor uses a specific discount factor based on the number of players, which prevents the higher-order differences from causing the regret bound to grow exponentially with the number of players.

The authors prove that if all players in an N-player finite game with K actions follow the HOOD algorithm, each player's individual regret is bounded by O(N^3 log^2 K) for all time. This bound is uniform over the horizon of play, meaning regret does not grow as the game continues. This result completes a long-standing progression of regret bounds in game theory, moving from O(sqrt(T)) down to O(1).

This paper provides a definitive answer to the question of whether constant regret is possible in general games. By achieving constant regret, the algorithm ensures that the empirical distribution of play converges to the set of coarse correlated equilibria at a rate of O(1/T). This offers a robust theoretical foundation for understanding how decentralized, uncoupled learning can lead to stable outcomes in complex, multi-agent environments without requiring players to know the game's horizon in advance.