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

• URL: http://arxiv.org/abs/2608.04149v1
• Date: Tue, 04 Aug 2026 18:58:51 GMT
• Title: Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization
• Abstract summary: Swap regret governs the rate at which uncoupled learning dynamics converge to correlated equilibria in multiplayer general-sum games.<n>We construct uncoupled dynamics under which every player incurs only $O(nm2sqrtlog mlog T/T)$ swap regret.
• Score: 12.597979977402543
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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(nm^2\sqrt{\log m\log 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(nm^2\sqrt{\log m\log 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(nm^2\sqrt{\log m\log T}+\sqrt{mT\log m})$ swap regret against arbitrary utility sequences, and by a horizon-free variant that requires no prior knowledge of $T$.

Related papers

• Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices [6.51943696606773]
  We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games.<n>With $n$ players and at most $m$ actions each, the individual swap regret of every player is $O(sqrtn m log m log5/2(nm))$ at every finite horizon.
  arXiv  Detail & Related papers  (2026-09-15T07:27:34Z)
• Constant regret in general games via higher-order optimism [21.642749388029525]
  We introduce an uncoupled learning algorithm which, when employed by all players of an arbitrary $N$-player normal form game, guarantees $O(N3log2 K)$ individual regret.<n>The proposed algorithm is a variant of optimistic follow-the-regularized-leader (FTRL) that combines a discounted $(N+1)$-th order predictor with entropic regularization.
  arXiv  Detail & Related papers  (2026-09-03T17:16:13Z)
• Independent Reinforcement Learning in Discounted Markov Games [5.5438676149999075]
  We show for every fixed discount factor, there is no-time algorithm for inverse-polynomially accurate coarse correlated equilibria in discounted general-sum Markov games.<n>Our algorithm is a emphlayered variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting.
  arXiv  Detail & Related papers  (2026-09-01T00:07:45Z)
• Scale-Invariant Fast Convergence in Games [67.02769061793619]
  We develop learning dynamics that achieve fast convergence while being both scale-free and scale-invariant.<n>For two-player zero-sum games, we obtain scale-free and scale-invariant dynamics with external regret bounded by $tildeO(A_mathrmdiff)$.<n>For multiplayer general-sum games, scale-free learning is enabled also by a technique called doubling clipping, which clips observed gradients based on past observations.
  arXiv  Detail & Related papers  (2026-02-12T11:57:20Z)
• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  We show that alternating RM$+$ converges to an $epsilon$-KKT point after $O_epsilon (1/epsilon4)$, establishing for the first time that it is a sound and fast first-order.<n>Our lower bound shows that convergence to coarse correlated equilibria in potential games is exponentially faster than convergence to Nash equilibria.
  arXiv  Detail & Related papers  (2025-10-20T00:45:47Z)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  An equilibrium can be computed at a fast rate of $O(log T)$ when all players follow the optimistic follow-the-regularized-leader (OFTRL)<n>We present corrupted learning dynamics that adaptively find an equilibrium at a rate that depends on the extent to which each player deviates from the strategy suggested by the prescribed algorithm.
  arXiv  Detail & Related papers  (2024-12-10T02:23:44Z)
• $\widetilde{O}(T^{-1})$ Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games [8.215874655947335]
  We show that an optimistic-follow-the-regularized-leader algorithm can find $widetildeO(T-1)$-approximate iterations in full-information general-sum Markov games within $T$.
  arXiv  Detail & Related papers  (2024-02-02T20:40:27Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  Two-player zero-sum Markov games are arguably the most basic setting in multi-agent reinforcement learning. We develop a learning algorithm that learns an $varepsilon$-approximate Markov NE policy using $$ widetildeObigg. We derive a refined regret bound for FTRL that makes explicit the role of variance-type quantities.
  arXiv  Detail & Related papers  (2022-08-22T17:24:55Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  We show that if all agents in a multi-player general-sum normal-form game employ Optimistic Multiplicative Weights Update (OMWU), the external regret of every player is $O(textrmpolylog(T))$ after $T$ repetitions of the game. We extend their result from external regret to internal regret and swap regret, thereby establishing uncoupled learning dynamics that converge to an approximate correlated equilibrium.
  arXiv  Detail & Related papers  (2021-11-11T01:19:53Z)
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition [38.28925339231888]
  We develop the first algorithm with a best-of-both-worlds'' guarantee. It achieves $mathcalO(log T)$ regret when the losses are adversarial. More generally, it achieves $tildemathcalO(sqrtC)$ regret in an intermediate setting.
  arXiv  Detail & Related papers  (2020-06-10T01:59:34Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.