# A Logarithmic Regret Bound for Optimistic Hedge in General-Sum Games

arXiv: https://arxiv.org/abs/2609.19677 · HTML: https://mlsanity.com/paper/2609.19677/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2026.

## Built on by (most cited first, 1 of 1)

- [A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games](https://mlsanity.com/paper/2609.22839/) (2026)

## Abstract (arXiv)

Can simple no-regret dynamics attain smaller regret in self-play than against arbitrary adversaries? In n-player general-sum games, Daskalakis et al. 2021 proved an O(nlog dilog4 T) individual regret bound for Optimistic Hedge, which improves upon the classical O(√ T) adversarial regret bound. In this work, we show that Optimistic Hedge with a constant step size can further achieve O(√ nlog dilog T) individual external regret under expected loss-vector feedback. The time-averaged play consequently enjoys a coarse correlated equilibrium gap O(√ nlog dlog T/T), where d=maxi di. The improvement comes from a larger admissible step size η=Theta(1/(√ nlog T)). Our analysis proves factorial bounds on high-order differences of probability-weighted pairwise loss gaps, then applies finite-difference interpolation in a fixed Euclidean norm. These estimates sharpen the analysis of Daskalakis et al. 2021 and yield a logarithmic regret bound.