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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 45 references that are in the map.
- First posted on arXiv 19 Sep 2026.

## Builds on (most cited first, 21 of 21)

- [Self-Play Preference Optimization for Language Model Alignment](https://mlsanity.com/paper/2405.00675/) (2024)
- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences](https://mlsanity.com/paper/2404.03715/) (2024)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Distortion of AI Alignment: Does Preference Optimization Optimize for Preferences?](https://mlsanity.com/paper/2505.23749/) (2025)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [Faster Rates for No-Regret Learning in General Games via Cautious Optimism](https://mlsanity.com/paper/2503.24340/) (2025)
- [Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Games](https://mlsanity.com/paper/2506.05005/) (2025)
- [Multiplayer Nash Preference Optimization](https://mlsanity.com/paper/2509.23102/) (2025)
- [Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization](https://mlsanity.com/paper/2608.04149/) (2026)
- [Constant Individual Regret in General Games](https://mlsanity.com/paper/2608.31166/) (2026)
- [Optimal Alternating Regret for Online Learning and Games](https://mlsanity.com/paper/2608.24731/) (2026)
- [Constant regret in general games via higher-order optimism](https://mlsanity.com/paper/2609.04113/) (2026)
- [A Logarithmic Regret Bound for Optimistic Hedge in General-Sum Games](https://mlsanity.com/paper/2609.19677/) (2026)

## Abstract (arXiv)

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 On,d(1) individual regret in general-sum games with n players and d=(d1,ldots,dn) actions, under expected loss-vector feedback. As a corollary, its time-averaged play enjoys an On,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.