mlsanityData to 14 Oct 2026

Doubly Optimal No-Regret Learning in Monotone Games

arXiv 2301.13120 ↗First posted 30 Jan 2023cs.LG cs.GTcited by 14

Not on the map. Why?

Abstract (arXiv)

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 O(frac1√T) last-iterate convergence rate to a Nash equilibrium. While the O(frac1√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 O(√T) regret in the adversarial setting under smooth and convex loss functions and (ii) the optimal O(frac1T) 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 O(log T) individual worst-case dynamic regret, providing an exponential improvement over the previous state-of-the-art O(√T) bound.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 31 of its 61 references that are in the map. First posted on arXiv 30 Jan 2023.

Builds on

31 of 61 references.

References · 31

  1. 2017Training GANs with Optimismcited by 217
  2. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  3. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  4. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 143
  5. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 131
  6. 2017Cycles in adversarial regularized learningcited by 124
  7. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 101
  8. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  9. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  10. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  11. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  12. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 76
19 more
  1. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  2. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  3. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
  4. 2020Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitiescited by 61
  5. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
  6. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  7. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  8. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
  9. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  10. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  11. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 32
  12. 2020Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Gamescited by 26
  13. 2020Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapescited by 21
  14. 2022From Halpern's Fixed-Point Iterations to Nesterov's Accelerated Interpretations for Root-Finding Problemscited by 20
  15. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 20
  16. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  17. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
  18. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  19. 2018Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Gamescited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 1; 2025: 4; 2026: 6.

14 papers.

Sort:

By area:

  1. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  2. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  3. 2025Incentivizing Truthful Language Models via Peer Elicitation Gamescited by 9
  4. 2024COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferencescited by 8
  5. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  6. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 4
  7. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  8. 2025Convergent Q-Learning for Infinite-Horizon General-Sum Markov Games through Behavioral Economicscited by 2
  9. 2026ALIGN: Aligned Delegation with Performance Guarantees for Multi-Agent LLM Reasoningcited by 2
  10. 2026Optimal Alternating Regret for Online Learning and Gamescited by 2
  11. 2026Minimax Last-Iterate Convergence in Matrix Games with Observed Actionscited by 1
  12. 2025Computing Pure-Strategy Nash Equilibria in a Two-Party Policy Competition: Existence and Algorithmic Approachescited by 0
2 more
  1. 2026Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalitiescited by 0
  2. 2026Thompson Sampling for Learning in Zero-Sum Gamescited by 0