Near-Optimal No-Regret Learning in General Games

Abstract

We show that Optimistic Hedge -- a common variant of multiplicative-weights-updates with recency bias -- attains $\mathrm{poly}(\log T)$ regret in multi-player general-sum games. In particular, when every player of the game uses Optimistic Hedge to iteratively update her strategy in response to the history of play so far, then after $T$ rounds of interaction, each player experiences total regret that is $\mathrm{poly}(\log T)$. Our bound improves, exponentially, the $O(T^{1/2})$ regret attainable by standard no-regret learners in games, the $O(T^{1/4})$ regret attainable by no-regret learners with recency bias (Syrgkanis et al., 2015), and the $O(T^{1/6})$ bound that was recently shown for Optimistic Hedge in the special case of two-player games (Chen & Pen, 2020). A corollary of our bound is that Optimistic Hedge converges to coarse correlated equilibrium in general games at a rate of $\tilde{O}\left(\frac{1}{T}\right)$.

arXiv comment40 pages

References in corpus (9)

• Online Learning with Predictable Sequences
• Optimization, Learning, and Games with Predictable Sequences
• Fast Convergence of Regularized Learning in Games
• More Adaptive Algorithms for Adversarial Bandits
• Learning in Games: Robustness of Fast Convergence
• A Counter-Example to Karlin's Strong Conjecture for Fictitious Play
• Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
• Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games
• The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities

Cited by in corpus (3)

• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
• $O\left(1/T\right)$ Time-Average Convergence in a Generalization of Multiagent Zero-Sum Games