SOURCE-LINKED INTELLIGENCE

A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games

arXiv · AI, language, vision and robotics · article · Sep 19, 2026 · UTC

Can simple learning rules keep their regret bounded in self-play? Recent work achieves constant regret bounds through modified regularization and higher-order prediction. Yet for Optimistic Hedge, arguably the most canonical method in games, the best known individual regret bound remains logarithmic. In this work, we prove that plain Optimistic Hedge with a constant step size can attain $O_{n,d}(1)$ individual regret in general-sum games with $n$ players and $d=(d_1,\ldots,d_n)$ actions, under expected loss-vector feedback. As a corollary, its time-averaged play enjoys an $O_{n,d}(1/T)$ coarse

Read original source ↗ Open in workspace

recordType

paper

region

Global