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

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.