mlsanityData to 14 Oct 2026

Tight last-iterate convergence rates for no-regret learning in multi-player games

arXiv 2010.13724 ↗First posted 26 Oct 2020cs.LG math.OCcited by 49

Not on the map. Why?

Abstract (arXiv)

We study the question of obtaining last-iterate convergence rates for no-regret learning algorithms in multi-player games. We show that the optimistic gradient (OG) algorithm with a constant step-size, which is no-regret, achieves a last-iterate rate of O(1/√T) with respect to the gap function in smooth monotone games. This result addresses a question of Mertikopoulos & Zhou (2018), who asked whether extra-gradient approaches (such as OG) can be applied to achieve improved guarantees in the multi-agent learning setting. The proof of our upper bound uses a new technique centered around an adaptive choice of potential function at each iteration. We also show that the O(1/√T) rate is tight for all p-SCLI algorithms, which includes OG as a special case. As a byproduct of our lower bound analysis we additionally present a proof of a conjecture of Arjevani et al. (2015) which is more direct than previous approaches.

Key facts. Cited by 49 papers in the map (data through 14 Oct 2026). First posted on arXiv 26 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 10; 2022: 12; 2023: 11; 2024: 6; 2025: 5; 2026: 5.

49 papers.

Sort:

By area:

  1. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  2. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  3. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  4. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  5. 2021Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivitycited by 39
  6. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
  7. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
  8. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  9. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 20
  10. 2023Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamicscited by 20
  11. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 19
  12. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
37 more
  1. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
  2. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  3. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  4. 2023Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditionscited by 14
  5. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  6. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  7. 2023Reward-Consistent Dynamics Models are Strongly Generalizable for Offline Reinforcement Learningcited by 12
  8. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 10
  9. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  10. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  11. 2021Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationscited by 8
  12. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  13. 2024COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferencescited by 8
  14. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  15. 2022Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chainscited by 7
  16. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  17. 2022Perseus: A Simple and Optimal High-Order Method for Variational Inequalitiescited by 5
  18. 2022Transferable Reward Learning by Dynamics-Agnostic Discriminator Ensemblecited by 5
  19. 2022STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Gamescited by 4
  20. 2024Tractable Equilibrium Computation in Markov Games through Risk Aversioncited by 4
  21. 2024No-regret learning in harmonic games: Extrapolation in the face of conflicting interestscited by 4
  22. 2022Solving Constrained Variational Inequalities via a First-order Interior Point-based Methodcited by 3
  23. 2026An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascentcited by 3
  24. 2022Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimizationcited by 2
  25. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  26. 2025Convergent Q-Learning for Infinite-Horizon General-Sum Markov Games through Behavioral Economicscited by 2
  27. 2025Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Gamescited by 2
  28. 2021Towards convergence to Nash equilibria in two-team zero-sum gamescited by 1
  29. 2023Extragradient Type Methods for Riemannian Variational Inequality Problemscited by 1
  30. 2023A Specialized Semismooth Newton Method for Kernel-Based Optimal Transportcited by 1
  31. 2024Configurable Mirror Descent: Towards a Unification of Decision Makingcited by 1
  32. 2024Is Thompson Sampling Susceptible to Algorithmic Collusion?cited by 1
  33. 2025Learning from Delayed Feedback in Games via Extra Predictioncited by 1
  34. 2026Dynamics and Convergences for Markov Coevolutionary Opinion Formation Games in Dynamic Social Networkscited by 1
  35. 2026Accelerated and Stable Convergence with Anchored Generalized Optimistic Methodcited by 0
  36. 2026On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalitiescited by 0
  37. 2026Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalitiescited by 0