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

arXiv: https://arxiv.org/abs/2204.11417 · HTML: https://mlsanity.com/paper/2204.11417/

## 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 (most cited first, 11 of 11)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [On Last-Iterate Convergence Beyond Zero-Sum Games](https://mlsanity.com/paper/2203.12056/) (2022)
- [Stable-Predictive Optimistic Counterfactual Regret Minimization](https://mlsanity.com/paper/1902.04982/) (2019)
- [Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes](https://mlsanity.com/paper/1905.04532/) (2019)
- [Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibria](https://mlsanity.com/paper/2202.05446/) (2022)
- [Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics](https://mlsanity.com/paper/2203.14129/) (2022)

## Built on by (most cited first, 30 of 35)

- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022)
- [Efficient Phi-Regret Minimization in Extensive-Form Games via Online Mirror Descent](https://mlsanity.com/paper/2205.15294/) (2022)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games](https://mlsanity.com/paper/2401.15240/) (2024)
- [O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2209.12430/) (2022)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)
- [Multi-Player Zero-Sum Markov Games with Networked Separable Interactions](https://mlsanity.com/paper/2307.09470/) (2023)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [The Real Price of Bandit Information in Multiclass Classification](https://mlsanity.com/paper/2405.10027/) (2024)
- [Playing Large Games with Oracles and AI Debate](https://mlsanity.com/paper/2312.04792/) (2023)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [Corrupted Learning Dynamics in Games](https://mlsanity.com/paper/2412.07120/) (2024)
- [Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret](https://mlsanity.com/paper/2602.06348/) (2026)
- [Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback](https://mlsanity.com/paper/2602.21436/) (2026)
- [Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization](https://mlsanity.com/paper/2608.04149/) (2026)
- [Near-Optimal Phi-Regret Learning in Extensive-Form Games](https://mlsanity.com/paper/2208.09747/) (2022)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [RCBSF: A Multi-Agent Framework for Automated Contract Revision via Stackelberg Game](https://mlsanity.com/paper/2604.10740/) (2026)
- [Constant Individual Regret in General Games](https://mlsanity.com/paper/2608.31166/) (2026)
- [Comparator-Adaptive Phi-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games](https://mlsanity.com/paper/2505.17277/) (2025)
- [Optimism Without Regularization: Constant Regret in Zero-Sum Games](https://mlsanity.com/paper/2506.16736/) (2025)
- [Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2510.11691/) (2025)
- [Optimal Alternating Regret for Online Learning and Games](https://mlsanity.com/paper/2608.24731/) (2026)
- [Constant regret in general games via higher-order optimism](https://mlsanity.com/paper/2609.04113/) (2026)
- [Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games](https://mlsanity.com/paper/2511.02157/) (2025)

## 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).