mlsanityData to 7 Oct 2026

Hedging in games: Faster convergence of external and swap regrets

arXiv 2006.04953 ↗First posted 8 Jun 2020cs.GT cs.DScited by 57

Not on the map. Why?

Abstract (arXiv)

We consider the setting where players run the Hedge algorithm or its optimistic variant to play an n-action game repeatedly for T rounds. 1) For two-player games, we show that the regret of optimistic Hedge decays at tildeO( 1/T 5/6 ), improving the previous bound O(1/T3/4) by Syrgkanis, Agarwal, Luo and Schapire (NIPS'15) 2) In contrast, we show that the convergence rate of vanilla Hedge is no better than tildeOmega(1/ √T), addressing an open question posted in Syrgkanis, Agarwal, Luo and Schapire (NIPS'15). For general m-player games, we show that the swap regret of each player decays at rate tildeO(m1/2 (n/T)3/4) when they combine optimistic Hedge with the classical external-to-internal reduction of Blum and Mansour (JMLR'07). The algorithm can also be modified to achieve the same rate against itself and a rate of tildeO(√n/T) against adversaries. Via standard connections, our upper bounds also imply faster convergence to coarse correlated equilibria in two-player games and to correlated equilibria in multiplayer games.

Key facts. Cited by 57 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 12; 2023: 8; 2024: 12; 2025: 7; 2026: 10.

57 papers.

Sort:

By area:

  1. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  2. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  3. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  4. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  5. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  6. 2022No-Regret Learning in Time-Varying Zero-Sum Gamescited by 36
  7. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  8. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 30
  9. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  10. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
  11. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  12. 2021Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Updatecited by 20
38 more
  1. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  2. 2021How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agentscited by 17
  3. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  4. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  5. 2022Online Prediction in Sub-linear Spacecited by 16
  6. 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
  7. 2023Regret Matching+: (In)Stability and Fast Convergence in Gamescited by 13
  8. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 12
  9. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  10. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 11
  11. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9
  12. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 9
  13. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 7
  14. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 6
  15. 2023Playing Large Games with Oracles and AI Debatecited by 5
  16. 2024The complexity of approximate (coarse) correlated equilibrium for incomplete information gamescited by 4
  17. 2024Corrupted Learning Dynamics in Gamescited by 4
  18. 2024No-regret learning in harmonic games: Extrapolation in the face of conflicting interestscited by 4
  19. 2026Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularizationcited by 4
  20. 2022Near-Optimal Phi-Regret Learning in Extensive-Form Gamescited by 3
  21. 2026Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedbackcited by 3
  22. 2026Constant Individual Regret in General Gamescited by 3
  23. 2023Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Gamescited by 2
  24. 2023Taming the Exponential Action Set: Sublinear Regret and Fast Convergence to Nash Equilibrium in Online Congestion Gamescited by 2
  25. 2024Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Gamescited by 2
  26. 2024On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Gamescited by 2
  27. 2025Optimism Without Regularization: Constant Regret in Zero-Sum Gamescited by 2
  28. 2025Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Gamescited by 2
  29. 2026Optimal Alternating Regret for Online Learning and Gamescited by 2
  30. 2026Constant regret in general games via higher-order optimismcited by 2
  31. 2022Unified Policy Optimization for Continuous-action Reinforcement Learning in Non-stationary Tasks and Gamescited by 1
  32. 2024Optimistic Thompson Sampling for No-Regret Learning in Unknown Gamescited by 1
  33. 2024Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Gamescited by 1
  34. 2025Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Gamescited by 1
  35. 2026Scale-Invariant Fast Convergence in Gamescited by 1
  36. 2021Uncoupled Bandit Learning towards Rationalizability: Benchmarks, Barriers, and Algorithmscited by 0
  37. 2022Learning Rationalizable Equilibria in Multiplayer Gamescited by 0
  38. 2022Learning in Multi-Player Stochastic Gamescited by 0

50 most cited of 57 All 57 (JSON)