Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices

• URL: http://arxiv.org/abs/2609.16751v1
• Date: Tue, 15 Sep 2026 07:27:34 GMT
• Title: Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices
• Abstract summary: 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.
• Score: 6.51943696606773
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games under full-information feedback that achieve constant individual swap regret, independent of the horizon $T$. With $n$ players and at most $m$ actions each, the individual swap regret of every player is $O(\sqrt{n} m \log m \log^{5/2}(nm))$ at every finite horizon. Each player predicts the deviation gains, then uses these predictions to update a row-stochastic transition matrix, and plays its stationary distribution. The proof combines a potential argument exploiting stationarity with a two-scale higher-order prediction analysis, using rooted-tree representations to handle the nonlinear dependence of deviation gains on the stationary distributions. An adversarially robust variant, obtained through a generic common-prefix switching wrapper, preserves the self-play bound up to a universal constant and guarantees individual swap regret at most $7\sqrt{m T \log m}$ in the adversarial setting.

Related papers

• 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)
• Constant Individual Regret in General Games [27.786964046329455]
  We introduce emphECHO-OFTRL: optimistic follow-the-regularized-leader equipped with an EMA cascade for high-order optimism (ECHO)<n>If $m_max$ denotes the largest action-set size, then, simultaneously for every horizon $Tgeq1$, it guarantees that each of the $N$ players in the game incurs regret upper bounded by $O(textrmpoly(N, log m_max))$.<n>Our algorithm leverages a new form of optimism inspired by modern filter design.
  arXiv  Detail & Related papers  (2026-08-31T17:59:16Z)
• Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization [12.597979977402543]
  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.
  arXiv  Detail & Related papers  (2026-08-04T18:58:51Z)
• 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)
• Swap Regret and Correlated Equilibria Beyond Normal-Form Games [62.01542145970044]
  We present a new variant of swap regret for polytope games that we call profile swap regret''<n>Although we show profile swap regret is NP-hard to compute given a transcript of play, we show it is nonetheless possible to design efficient learning algorithms that guarantee at most $O(sqrtT)$ profile swap regret.
  arXiv  Detail & Related papers  (2025-02-27T16:16:26Z)
• 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)
• Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
  We show that regret can be obtained for general convex and compact strategy sets. Our dynamics are on an instantiation of optimistic follow-the-regularized-bounds over an appropriately emphlifted space. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret.
  arXiv  Detail & Related papers  (2022-06-17T12:58:58Z)
• 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)

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.