Doubly Optimal No-Regret Learning in Monotone Games
share
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 𝒪(1/√(T)) last-iterate convergence rate to a Nash equilibrium. While the 𝒪(1/√(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 𝒪(√(T)) regret in the adversarial setting under smooth and convex loss functions and (ii) the optimal 𝒪(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 𝒪(log T) individual worst-case dynamic regret, providing an exponential improvement over the previous state-of-the-art 𝒪(√(T)) bound.
READ FULL TEXT