# Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 33 references that are in the map.
- First posted on arXiv 4 Aug 2026.

## Builds on (most cited first, 15 of 15)

- [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)
- [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)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [A Closer Look at Small-loss Bounds for Bandits with Graph Feedback](https://mlsanity.com/paper/2002.00315/) (2020)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [Corrupted Learning Dynamics in Games](https://mlsanity.com/paper/2412.07120/) (2024)
- [Comparator-Adaptive Phi-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games](https://mlsanity.com/paper/2505.17277/) (2025)
- [Scale-Invariant Fast Convergence in Games](https://mlsanity.com/paper/2602.11857/) (2026)

## Built on by (most cited first, 4 of 4)

- [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)
- [Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism](https://mlsanity.com/paper/2609.16751/) (2026)
- [A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games](https://mlsanity.com/paper/2609.22839/) (2026)

## Abstract (arXiv)

Swap regret governs the rate at which uncoupled learning dynamics converge to correlated equilibria in multiplayer general-sum games. Under full-information feedback, the best previous guarantee when every player follows the same dynamics grows logarithmically in the horizon T. We construct uncoupled dynamics under which every player incurs only O(nm2√log mlog T) swap regret, where n is the number of players and m bounds the number of actions per player. To our knowledge, this is the first sublogarithmic individual guarantee in this setting, and it implies that the time-averaged product distribution of play is an O(nm2√log mlog T/T)-approximate correlated equilibrium. The key algorithmic choice is to combine the Blum--Mansour reduction with optimistic follow-the-regularized-leader using a hybrid regularizer that separately weights negative Shannon entropy and the log-barrier: the entropy controls the optimistic prediction error, whereas the log-barrier controls the transition-matrix movement through its Bregman divergence. A new sensitivity theorem for stationary distributions of Markov chains, which involves neither mixing parameters nor the smallest transition probability, transfers this control to the played strategies and yields a simpler analysis without local-norm or self-concordance arguments. The guarantee is preserved by an adversarially robust variant that additionally ensures O(nm2√log mlog T+√mTlog m) swap regret against arbitrary utility sequences, and by a horizon-free variant that requires no prior knowledge of T.