mlsanityData to 13 Oct 2026

Fast Convergence of Regularized Learning in Games

arXiv 1507.00407 ↗First posted 2 Jul 2015cs.GT cs.AI cs.LGcited by 149

Not on the map. Why?

Abstract (arXiv)

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 tildeO(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.

Key facts. Cited by 149 papers in the map (data through 13 Oct 2026). First posted on arXiv 2 Jul 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 30; 2022: 21; 2023: 24; 2024: 23; 2025: 29; 2026: 22.

149 papers.

Sort:

By area:

  1. 2023Nash Learning from Human Feedbackcited by 223
  2. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
  3. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  4. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 67
  5. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 66
  6. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  7. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 62
  8. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  9. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  10. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  11. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  12. 2022No-Regret Learning in Time-Varying Zero-Sum Gamescited by 36
38 more
  1. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  2. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  3. 2021Online Learning with Optimism and Delaycited by 33
  4. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 32
  5. 2021No-Press Diplomacy from Scratchcited by 31
  6. 2022Causal Imitation Learning under Temporally Correlated Noisecited by 28
  7. 2021Last-iterate Convergence in Extensive-Form Gamescited by 27
  8. 2022Adapting to Online Label Shift with Provable Guaranteescited by 26
  9. 2022Minimax Optimal Online Imitation Learning via Replay Estimationcited by 25
  10. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  11. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
  12. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 23
  13. 2021Survival of the strictest: Stable and unstable equilibria under regularized learning with partial informationcited by 22
  14. 2022A unified stochastic approximation framework for learning in gamescited by 22
  15. 2023Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimizationcited by 22
  16. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  17. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  18. 2021Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Updatecited by 20
  19. 2023Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamicscited by 20
  20. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  21. 2021How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agentscited by 17
  22. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  23. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  24. 2021Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Gamescited by 15
  25. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
  26. 2023Efficient Methods for Non-stationary Online Learningcited by 15
  27. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  28. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  29. 2021Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibriacited by 13
  30. 2023Regret Matching+: (In)Stability and Fast Convergence in Gamescited by 13
  31. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 12
  32. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 12
  33. 2021Contextual Games: Multi-Agent Learning with Side Informationcited by 11
  34. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  35. 2024Gradient-Variation Online Learning under Generalized Smoothnesscited by 11
  36. 2024An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraintscited by 11
  37. 2023Mastering Strategy Card Game (Legends of Code and Magic) via End-to-End Policy and Optimistic Smooth Fictitious Playcited by 10
  38. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 10

50 most cited of 149 All 149 (JSON)