Related papers: Constant Individual Regret in General Games

Constant Individual Regret in General Games

URL: http://arxiv.org/abs/2608.31166v1
Date: Mon, 31 Aug 2026 17:59:16 GMT
Title: Constant Individual Regret in General Games
Abstract summary: 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.
Score: 27.786964046329455
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Uncoupled no-regret dynamics provide a decentralized route to equilibrium, but prior guarantees for individual regret retain a polylogarithmic dependence on the horizon. We remove this dependence for every finite $N$-player normal-form game under full-information feedback. We introduce \emph{ECHO-OFTRL}: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average. The algorithm is deterministic and fully uncoupled. If $m_{\max}$ denotes the largest action-set size, then, simultaneously for every horizon $T\geq1$, it guarantees that each of the $N$ players in the game incurs regret upper bounded by $O(\textrm{poly}(N, \log m_{\max}))$. Our algorithm leverages a new form of optimism inspired by modern filter design.

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)
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)
Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
We study online finite-horizon Markov Decision Processes with adversarially changing loss and aggregate bandit feedback (a.k.a full-bandit)<n>Under this type of feedback, the agent observes only the total loss incurred over the entire trajectory, rather than the individual losses at each intermediate step within the trajectory.<n>We introduce the first Policy Optimization algorithms for this setting.
arXiv Detail & Related papers (2025-02-06T12:03:24Z)
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)
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 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)
Uncoupled Learning Dynamics with $O(\log T)$ Swap Regret in Multiplayer Games [121.50979258049135]
We show that when all players follow our dynamics with a emphtime-invariant learning rate, the emphsecond-order path lengths of the dynamics up to time $T$ are bounded by $O(log T)$. Our proposed learning dynamics combine in a novel way emphoptimistic regularized learning with the use of emphself-concordant barriers.
arXiv Detail & Related papers (2022-04-25T03:20:16Z)
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.