Doubly Optimal No-Regret Learning in Monotone Games

Abstract

We consider online learning in multi-player smooth monotone games. Existing algorithms have limitations such as (1) being only applicable to strongly monotone games; (2) lacking the no-regret guarantee; (3) having only asymptotic or slow $ O(\frac{1}{\sqrt{T}}) $ last-iterate convergence rate to a Nash equilibrium. While the $ O(\frac{1}{\sqrt{T}}) $ rate is tight for a large class of algorithms including the well-studied extragradient algorithm and optimistic gradient algorithm, it is not optimal for all gradient-based algorithms. We propose the accelerated optimistic gradient (AOG) algorithm, the first doubly optimal no-regret learning algorithm for smooth monotone games. Namely, our algorithm achieves both (i) the optimal $ O(sqrt{T}) $ regret in the adversarial setting under smooth and convex loss functions and (ii) the optimal $ O(\frac{1}{T}) $ last-iterate convergence rate to a Nash equilibrium in multi-player smooth monotone games. As a byproduct of the accelerated last-iterate convergence rate, we further show that each player suffers only an $ O(\log T) $ individual worst-case dynamic regret, providing an exponential improvement over the previous state-of-the-art $ O(sqrt{T}) $ bound.