Optimistic Hedge achieves constant regret in multiplayer games
A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games
Computer Science and Game TheoryMachine Learning
Summary
The paper looks at whether simple learning strategies can keep errors low when players learn by playing games against each other. The authors show that a well-known method called Optimistic Hedge can keep its mistakes from growing over time, even in complex multiplayer games with many possible actions. Their proof uses advanced math and shows that this learning method performs steadily no matter how long the game lasts. This means the players’ strategies quickly become stable and predictable, which is useful for understanding how learning works in competitive settings.
What this means in practice
- •For game developers: Design game AI that learns stable strategies quickly in multiplayer games using Optimistic Hedge with guaranteed performance limits.
- •For multi-agent system engineers: Build algorithms where multiple agents learn to cooperate or compete with stable outcomes irrespective of game length.
A theory result. No direct application yet.
Authors
Junsoo Ha
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.