Uncoupled Learning Dynamics With \(o(\log T)\) Swap Regret In Multiplayer Games

Abstract

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(log^4 (T))\). At the same time, we guarantee optimal \(O(\sqrt\{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 dev

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyanagnostides2022uncoupled

Related papers

• Corrupted Learning Dynamics In Games (2024)0.00
• On The Complexity Of Computing Sparse Equilibria And Lower Bounds For No-regret Learning In Games (2023)0.00
• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• \(\widetilde{o}(t^{-1})\) Convergence To (coarse) Correlated Equilibria In Full-information General-sum Markov Games (2024)0.00
• A Finite-sample Analysis Of Payoff-based Independent Learning In Zero-sum Stochastic Games (2023)0.00
• Near Optimal Convergence To Coarse Correlated Equilibrium In General-sum Markov Games (2025)0.00
• Prediction-aware Learning In Multi-agent Systems (2025)0.00
• Simple Uncoupled No-regret Learning Dynamics For Extensive-form Correlated Equilibrium (2021)6.34