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(1/T)$ last-iterate convergence rate to a Nash equilibrium. While the $O(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 mph{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}(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 mph{worst-case dynamic regret}, providing an exponential improvement over the previous state-of-the-art $O(sqrt(T))$ bound.
