Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
Not on the map. Why?
Abstract (arXiv)
In two-player zero-sum games, the learning dynamic based on optimistic Hedge achieves one of the best-known regret upper bounds among strongly-uncoupled learning dynamics. With an appropriately chosen learning rate, the social and individual regrets can be bounded by O(log(mn)) in terms of the numbers of actions m and n of the two players. This study investigates the optimality of the dependence on m and n in the regret of optimistic Hedge. To this end, we begin by refining existing regret analysis and show that, in the strongly-uncoupled setting where the opponent's number of actions is known, both the social and individual regret bounds can be improved to O(√log m log n). In this analysis, we express the regret upper bound as an optimization problem with respect to the learning rates and the coefficients of certain negative terms, enabling refined analysis of the leading constants. We then show that the existing social regret bound as well as these new social and individual regret upper bounds cannot be further improved for optimistic Hedge by providing algorithm-dependent individual regret lower bounds. Importantly, these social regret upper and lower bounds match exactly including the constant factor in the leading term. Finally, building on these results, we improve the last-iterate convergence rate and the dynamic regret of a learning dynamic based on optimistic Hedge, and complement these bounds with algorithm-dependent dynamic regret lower bounds that match the improved bounds.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 20 of its 33 references that are in the map. First posted on arXiv 13 Oct 2025.
Builds on
20 of 33 references.
References · 20
- 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 233
- 2023Nash Learning from Human Feedbackcited by 224
- 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
- 2015Fast Convergence of Regularized Learning in Gamescited by 150
- 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedbackcited by 144
- 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 131
- 2018More Adaptive Algorithms for Adversarial Banditscited by 114
- 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
- 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 76
- 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
- 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
- 2020Hedging in games: Faster convergence of external and swap regretscited by 57
8 more
- 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
- 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 49
- 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
- 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
- 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 10
- 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
- 2024Corrupted Learning Dynamics in Gamescited by 4
- 2025Can Reinforcement Learning Solve Asymmetric Combinatorial-Continuous Zero-Sum Games?cited by 2
Built on by
Citing papers per year: 2026: 2.
2 papers.
- 2026Constant regret in general games via higher-order optimismcited by 2
- 2026Scale-Invariant Fast Convergence in Gamescited by 1
- 2026Constant regret in general games via higher-order optimism3 Sep 2026
- 2026Scale-Invariant Fast Convergence in Games12 Feb 2026