Constant regret in general games via higher-order optimism

• URL: http://arxiv.org/abs/2609.04113v1
• Date: Thu, 03 Sep 2026 17:16:13 GMT
• Title: Constant regret in general games via higher-order optimism
• Abstract summary: 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.
• Score: 21.642749388029525
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce an uncoupled learning algorithm which, when employed by all players of an arbitrary $N$-player normal form game with up to $K$ actions per player, guarantees $O(N^3\log^2 K)$ individual regret, uniformly over the horizon of play. The proposed algorithm - which we call higher-order optimism with discounting (HOOD) is a variant of optimistic follow-the-regularized-leader (OptFTRL) that combines a discounted $(N+1)$-th order predictor with entropic regularization over a suitable "lifting" of the game's strategy space. This combination of ingredients is purposefully designed to dampen large oscillations of the induced sequence of play in a controlled manner, removing in this way a key stumbling block of previous attempts to achieve constant regret in general games. Our approach bears several striking similarities to the concurrent - and completely independent - work of Liu, Farina, and Ozdaglar (arXiv:2608.31166), who very recently derived an $O(N^{21}\log^{4} K)$ regret bound through the use of higher-order optimism and an exponential moving average estimator.

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 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)
• 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)
• Faster Rates for No-Regret Learning in General Games via Cautious Optimism [46.462843198107144]
  We establish the first uncoupled learning algorithm that attains $O(n, d log T)$ per-player regret in multi-player general-sum games.<n>Our results exponentially improve the dependence on $d$ compared to the $O(n, d log T)$ regret attainable by Log-Regularized Lifted Optimistic FTRL.
  arXiv  Detail & Related papers  (2025-03-31T17:25:33Z)
• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  We show that when a pure strategy Nash equilibrium exists, $c$ becomes zero, leading to an optimal instance-dependent regret bound.<n>Our algorithm also enjoys last-iterate convergence and can identify the pure strategy Nash equilibrium with near-optimal sample.
  arXiv  Detail & Related papers  (2025-02-24T20:20:06Z)
• Near-Optimal $\Phi$-Regret Learning in Extensive-Form Games [85.78272987312343]
  We establish efficient and uncoupled learning dynamics so that the trigger regret of each player grows as $O(log T)$ after $T$ repetitions of play. This improves exponentially over the prior best known trigger-regret bound of $O(T1/4)$.
  arXiv  Detail & Related papers  (2022-08-20T20:48:58Z)
• 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)
• Near-Optimal No-Regret Learning in General Games [31.293412884145066]
  We show that Optimistic Hedge attains $rm poly(log T)$ regret in multi-player general-sum games. A corollary of our bound is that Optimistic Hedge converges to coarse correlated equilibrium in general games at a rate of $tildeOleft(frac 1Tright)$.
  arXiv  Detail & Related papers  (2021-08-16T06:53:02Z)

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.