Faster Rates for No-Regret Learning in General Games via Cautious Optimism

• URL: http://arxiv.org/abs/2503.24340v1
• Date: Mon, 31 Mar 2025 17:25:33 GMT
• Title: Faster Rates for No-Regret Learning in General Games via Cautious Optimism
• Authors: Ashkan Soleymani, Georgios Piliouras, Gabriele Farina,
• Abstract summary: 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.
• Score: 46.462843198107144
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish the first uncoupled learning algorithm that attains $O(n \log^2 d \log T)$ per-player regret in multi-player general-sum games, where $n$ is the number of players, $d$ is the number of actions available to each player, and $T$ is the number of repetitions of the game. Our results exponentially improve the dependence on $d$ compared to the $O(n\, d \log T)$ regret attainable by Log-Regularized Lifted Optimistic FTRL [Far+22c], and also reduce the dependence on the number of iterations $T$ from $\log^4 T$ to $\log T$ compared to Optimistic Hedge, the previously well-studied algorithm with $O(n \log d \log^4 T)$ regret [DFG21]. Our algorithm is obtained by combining the classic Optimistic Multiplicative Weights Update (OMWU) with an adaptive, non-monotonic learning rate that paces the learning process of the players, making them more cautious when their regret becomes too negative.

Related papers

• 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)
• 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)
• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games.<n>We show that OMWU offers several advantages including logarithmic dependence on the size of the payoff matrix.<n>We prove that a broad class of algorithms that do not forget the past quickly all suffer the same issue.
  arXiv  Detail & Related papers  (2024-06-15T13:26:17Z)
• Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints [21.412085244757336]
  We study the problem of multi-agent reinforcement learning (MARL) with adaptivity constraints. For two-player zero-sum Markov Games, we design a (policy) elimination based algorithm that achieves a regret of $widetildeO(sqrtH3 S2 ABK)$. We prove a batch complexity lower bound $Omega(fracHlog_AK+loglog K)$ for all algorithms with $widetildeO(sqrtK)$
  arXiv  Detail & Related papers  (2024-02-02T03:00:40Z)
• Doubly Optimal No-Regret Learning in Monotone Games [10.760195409078591]
  We propose the first doubly optimal no-regret learning algorithm for smooth monotone games. Our algorithm achieves both (i) the optimal $O(sqrtT)$ regret in the adversarial setting under smooth and convex loss functions and (ii) the optimal $O(frac1T)$ last-iterate convergence rate to a Nash equilibrium.
  arXiv  Detail & Related papers  (2023-01-30T17:55:53Z)
• 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 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.