Abstract

We establish the first uncoupled learning algorithm that attains $O(n \log^2d \log T)$ per-player regret in multi-player general-sum games, where $n$ isthe 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 exponentiallyimprove the dependence on $d$ compared to the $O(n\, d \log T)$ regretattainable by Log-Regularized Lifted Optimistic FTRL [Far+22c], and also reducethe dependence on the number of iterations $T$ from $\log^4 T$ to $\log T$compared to Optimistic Hedge, the previously well-studied algorithm with $O(n\log d \log^4 T)$ regret [DFG21]. Our algorithm is obtained by combining theclassic 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.