mlsanityData to 14 Oct 2026

Adaptively Perturbed Mirror Descent for Learning in Games

arXiv 2305.16610 ↗First posted 26 May 2023cs.GT cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

This paper proposes a payoff perturbation technique for the Mirror Descent (MD) algorithm in games where the gradient of the payoff functions is monotone in the strategy profile space, potentially containing additive noise. The optimistic family of learning algorithms, exemplified by optimistic MD, successfully achieves it last-iterate convergence in scenarios devoid of noise, leading the dynamics to a Nash equilibrium. A recent re-emerging trend underscores the promise of the perturbation approach, where payoff functions are perturbed based on the distance from an anchoring, or it slingshot, strategy. In response, we propose it Adaptively Perturbed MD (APMD), which adjusts the magnitude of the perturbation by repeatedly updating the slingshot strategy at a predefined interval. This innovation empowers us to find a Nash equilibrium of the underlying game with guaranteed rates. Empirical demonstrations affirm that our algorithm exhibits significantly accelerated convergence.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 39 of its 72 references that are in the map. First posted on arXiv 26 May 2023.

Builds on

39 of 72 references.

References · 39

  1. 2017Training GANs with Optimismcited by 217
  2. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  3. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  4. 2017Cycles in adversarial regularized learningcited by 124
  5. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 101
  6. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  7. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  8. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  9. 2014Solving Large Imperfect Information Games Using CFR+cited by 78
  10. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  11. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  12. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 66
27 more
  1. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  2. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
  3. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 61
  4. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
  5. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  6. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  7. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
  8. 2018Bandit learning in concave N-person gamescited by 35
  9. 2022Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalitiescited by 33
  10. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  11. 2020Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Gamescited by 26
  12. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 26
  13. 2021Survival of the strictest: Stable and unstable equilibria under regularized learning with partial informationcited by 23
  14. 2020Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapescited by 21
  15. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  16. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  17. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  18. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  19. 2019Learning Nash Equilibria in Monotone Gamescited by 11
  20. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  21. 2022Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Gamescited by 8
  22. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  23. 2023Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamicscited by 8
  24. 2021Improved Rates for Derivative Free Gradient Play in Strongly Monotone Gamescited by 7
  25. 2013On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averagingcited by 5
  26. 2023Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Mapscited by 4
  27. 2021Frequency-Domain Representation of First-Order Methods: A Simple and Robust Framework of Analysiscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 5; 2026: 1.

9 papers.

  1. 2024COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferencescited by 8
  2. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  3. 2025RSPO: Regularized Self-Play Alignment of Large Language Modelscited by 5
  4. 2025Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approachcited by 5
  5. 2025NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibriacited by 2
  6. 2025Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networkscited by 1
  7. 2023Efficient Last-iterate Convergence Algorithms in Solving Gamescited by 0
  8. 2024Last Iterate Convergence in Monotone Mean Field Gamescited by 0
  9. 2026Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalitiescited by 0