Faster Rates for No-Regret Learning in General Games via Cautious Optimism

Abstract

We establish the first uncoupled learning algorithm that attains O(n log2 d logT) per-player regret in multi-player general-sum games, where n is the number of players, d is the number of actions available to each player, and T is the number of repetitions of the game. Our results exponentially improve the dependence on d compared to the O(n d logT) regret attainable by Log-Regularized Lifted Optimistic FTRL introduced by Farina, Anagnostides, Luo, Lee, Kroer, and Sandholm [2022], and also reduce the dependence on the number of iterations T from log4 T to logT compared to Optimistic Hedge, the previously well-studied algorithm with O(n logd log4 T) regret shown by Daskalakis, Fishelson, and Golowich [2021]. Our algorithm is obtained by combining the classic Optimistic Multiplicative Weights Update (OMWU) with an adaptive, non-monotonic learning rate that paces the learning process of the players, making them more cautious when their regret becomes too negative.