mlsanityData to 7 Oct 2026

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

arXiv 2503.24340 ↗First posted 31 Mar 2025cs.GT cs.LG math.OCcited by 10

Not on the map. Why?

Abstract (arXiv)

We establish the first uncoupled learning algorithm that attains O(n log2 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 log4 T to log T compared to Optimistic Hedge, the previously well-studied algorithm with O(n log d log4 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.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 11 of its 59 references that are in the map. First posted on arXiv 31 Mar 2025.

Builds on

11 of 59 references.

References · 11

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  3. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 228
  4. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  5. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  6. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  7. 2020Exploration-Exploitation in Multi-Agent Learning: Catastrophe Theory Meets Game Theorycited by 16
  8. 2016The Price of Anarchy in Auctionscited by 11
  9. 2024Policy Space Response Oracles: A Surveycited by 10
  10. 2014A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamicscited by 5
  11. 2023On the Interplay between Social Welfare and Tractability of Equilibriacited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 5.

10 papers.

  1. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 6
  2. 2026Constant Individual Regret in General Gamescited by 3
  3. 2025Comparator-Adaptive Phi-Regret: Improved Bounds, Simpler Algorithms, and Applications to Gamescited by 2
  4. 2026Optimal Alternating Regret for Online Learning and Gamescited by 2
  5. 2026Constant regret in general games via higher-order optimismcited by 2
  6. 2025Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Gamescited by 1
  7. 2025Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Gamescited by 0
  8. 2025Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Gamescited by 0
  9. 2026Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimismcited by 0
  10. 2026A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Gamescited by 0