Fast Convergence of Regularized Learning in Games

Abstract

We show that natural classes of regularized learning algorithms with a form of recency bias achieve faster convergence rates to approximate efficiency and to coarse correlated equilibria in multiplayer normal form games. When each player in a game uses an algorithm from our class, their individual regret decays at $O(T^{-3/4})$, while the sum of utilities converges to an approximate optimum at $O(T^{-1})$--an improvement upon the worst case $O(T^{-1/2})$ rates. We show a black-box reduction for any algorithm in the class to achieve $\tilde{O}(T^{-1/2})$ rates against an adversary, while maintaining the faster rates against algorithms in the class. Our results extend those of [Rakhlin and Shridharan 2013] and [Daskalakis et al. 2014], who only analyzed two-player zero-sum games for specific algorithms.

Cited by in corpus (51)

• Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
• Efficient Algorithms for Adversarial Contextual Learning
• Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Faster Rates for Convex-Concave Games
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games
• Adversarial Generalized Method of Moments
• Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
• From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Learning to Collaborate in Markov Decision Processes
• Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
• Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
• Dynamic Regret of Policy Optimization in Non-stationary Environments
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• Multi-agent online learning in time-varying games
• Human-Level Performance in No-Press Diplomacy via Equilibrium Search
• Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization
• Near-Optimal No-Regret Learning in General Games
• Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium
• Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes
• Hedging in games: Faster convergence of external and swap regrets
• The route to chaos in routing games: When is Price of Anarchy too optimistic?
• Deep Online Convex Optimization with Gated Games
• Last-iterate Convergence in Extensive-Form Games
• Robust Multi-agent Counterfactual Prediction
• Semantics, Representations and Grammars for Deep Learning
• Online Monotone Games
• An Optimistic Acceleration of AMSGrad for Nonconvex Optimization
• No-regret Learning in Cournot Games
• Optimistic and Adaptive Lagrangian Hedging
• Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving
• Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence
• Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information
• Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games
• Learning in Multi-Player Stochastic Games
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning
• A Robust Framework for Analyzing Gradient-Based Dynamics in Bilinear Games
• Solving Zero-Sum Games through Alternating Projections
• Online Learning with Optimism and Delay
• No-Press Diplomacy from Scratch
• Resource Allocation Game on Social Networks: Best Response Dynamics and Convergence
• No-Regret Learning in Unknown Games with Correlated Payoffs
• Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Games
• Uncoupled Bandit Learning towards Rationalizability: Benchmarks, Barriers, and Algorithms