aiqbench analysis
This paper establishes a significant theoretical breakthrough by proving that plain Optimistic Hedge achieves constant individual regret in general-sum games, effectively eliminating horizon dependence through novel real-analytic recurrence analysis. The result advances the understanding of self-play dynamics and convergence rates for canonical learning algorithms without relying on modified regularization or higher-order prediction techniques.
A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games
arXiv:2609.22839v1 Announce Type: cross Abstract: 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 correlated equilibrium (CCE) gap. Our analysis represents Optimistic Hedge as a real-analytic recurrence on a compact space, which yields an exact finite-order difference relation that eliminates horizon dependence. Our proof hinges on nonconstructive Noetherianity argument of Frisch (1967), so the $(n,d)$-dependence remains implicit.
Abstract: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 correlated equilibrium (CCE) gap. Our analysis represents Optimistic Hedge as a real-analytic recurrence on a compact space, which yields an exact finite-order difference relation that eliminates horizon dependence. Our proof hinges on nonconstructive Noetherianity argument of Frisch (1967), so the $(n,d)$-dependence remains implicit.
Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)
arXiv:2609.22839 [cs.GT]
(or arXiv:2609.22839v1 [cs.GT] for this version)
https://doi.org/10.48550/arXiv.2609.22839 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 226 words
Related coverage
Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
arXiv · Aug 27, 2026
Constant regret in general games via higher-order optimism
arXiv · Sep 4, 2026
Constant Swap Regret in General-Sum Games via Optimistic Transition Matrices
arXiv · Sep 16, 2026
IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence
arXiv · Oct 15, 2026