{"ID":23475001,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19677","arxiv_id":"2609.19677","title":"A Logarithmic Regret Bound for Optimistic Hedge in General-Sum Games","abstract":"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(n\\log d_i\\log^4 T)$ individual regret bound for Optimistic Hedge, which improves upon the classical $O(\\sqrt T)$ adversarial regret bound. In this work, we show that Optimistic Hedge with a constant step size can further achieve $O(\\sqrt n\\log d_i\\log T)$ individual external regret under expected loss-vector feedback. The time-averaged play consequently enjoys a coarse correlated equilibrium gap $O(\\sqrt n\\log d\\log T/T)$, where $d=\\max_i d_i$. The improvement comes from a larger admissible step size $η=Θ(1/(\\sqrt n\\log 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.","short_abstract":"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(n\\log d_i\\log^4 T)$ individual regret bound for Optimistic Hedge, which improves upon the classical $O(\\sqrt T)$ adversarial regret bound. In this wor...","url_abs":"https://arxiv.org/abs/2609.19677","url_pdf":"https://arxiv.org/pdf/2609.19677v1","authors":"[\"Junsoo Ha\"]","published":"2026-09-17T04:24:45Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}