mlsanityData to 14 Oct 2026

Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games

arXiv 2204.11417 ↗First posted 25 Apr 2022cs.GT cs.LGcited by 35

Not on the map. Why?

Abstract (arXiv)

In this paper we establish efficient and uncoupled learning dynamics so that, when employed by all players in a general-sum multiplayer game, the swap regret of each player after T repetitions of the game is bounded by O(log T), improving over the prior best bounds of O(log4 (T)). At the same time, we guarantee optimal O(√T) swap regret in the adversarial regime as well. To obtain these results, our primary contribution is to show that when all players follow our dynamics with a time-invariant learning rate, the second-order path lengths of the dynamics up to time T are bounded by O(log T), a fundamental property which could have further implications beyond near-optimally bounding the (swap) regret. Our proposed learning dynamics combine in a novel way optimistic regularized learning with the use of self-concordant barriers. Further, our analysis is remarkably simple, bypassing the cumbersome framework of higher-order smoothness recently developed by Daskalakis, Fishelson, and Golowich (NeurIPS'21).

Key facts. Cited by 35 papers in the map (data through 14 Oct 2026). Builds on 11 of its 43 references that are in the map. First posted on arXiv 25 Apr 2022.

Builds on

11 of 43 references.

References · 11

  1. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  2. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  5. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  6. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  7. 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 31
  8. 2019Stable-Predictive Optimistic Counterfactual Regret Minimizationcited by 21
  9. 2019Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizescited by 14
  10. 2022Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibriacited by 9
  11. 2022Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamicscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 6; 2024: 5; 2025: 8; 2026: 10.

35 papers.

Sort:

By area:

  1. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 32
  2. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  3. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 24
  4. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  5. 2022Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descentcited by 15
  6. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  7. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  8. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 13
  9. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  10. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 10
  11. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 10
  12. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 10
23 more
  1. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  2. 2024The Real Price of Bandit Information in Multiclass Classificationcited by 7
  3. 2023Playing Large Games with Oracles and AI Debatecited by 6
  4. 2024The complexity of approximate (coarse) correlated equilibrium for incomplete information gamescited by 4
  5. 2024Corrupted Learning Dynamics in Gamescited by 4
  6. 2026Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regretcited by 4
  7. 2026Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedbackcited by 4
  8. 2026Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularizationcited by 4
  9. 2022Near-Optimal Phi-Regret Learning in Extensive-Form Gamescited by 3
  10. 2025Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Gamescited by 3
  11. 2026RCBSF: A Multi-Agent Framework for Automated Contract Revision via Stackelberg Gamecited by 3
  12. 2026Constant Individual Regret in General Gamescited by 3
  13. 2025Comparator-Adaptive Phi-Regret: Improved Bounds, Simpler Algorithms, and Applications to Gamescited by 2
  14. 2025Optimism Without Regularization: Constant Regret in Zero-Sum Gamescited by 2
  15. 2025Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Gamescited by 2
  16. 2026Optimal Alternating Regret for Online Learning and Gamescited by 2
  17. 2026Constant regret in general games via higher-order optimismcited by 2
  18. 2025Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Gamescited by 1
  19. 2026Scale-Invariant Fast Convergence in Gamescited by 1
  20. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Gamescited by 0
  21. 2025Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Gamescited by 0
  22. 2026Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimismcited by 0
  23. 2026A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Gamescited by 0