Faster Rates for No-Regret Learning in General Games via Cautious Optimism
This work addresses the challenge of efficient no-regret learning in multi-agent systems, offering significant improvements in regret bounds for game theory applications, though it is incremental as it builds on existing optimistic methods.
The paper tackles the problem of achieving faster per-player regret rates in multi-player general-sum games by introducing a learning algorithm that combines Optimistic Multiplicative Weights Update with an adaptive, non-monotonic learning rate, resulting in an O(n log^2 d log T) regret bound, which exponentially improves dependence on d and reduces dependence on T compared to prior methods.
We establish the first uncoupled learning algorithm that attains $O(n \log^2 d \log T)$ 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 \log T)$ regret attainable by Log-Regularized Lifted Optimistic FTRL [Far+22c], and also reduce the 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 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.