Optimistic hedge achieves lower regret in multiplayer games
A Logarithmic Regret Bound for Optimistic Hedge in General-Sum Games
Computer Science and Game Theory
Summary
This work looks at how players can get better at making decisions in games where multiple people compete and cooperate. It shows that a specific learning method called Optimistic Hedge can learn faster and make fewer mistakes over time compared to previous approaches. The authors prove this by using a new mathematical analysis that allows the method to use a larger learning step. This improvement means players’ average strategies stabilize closer to an equilibrium faster than before.
What this means in practice
- •For multiagent system designers: Design algorithms for many-agent environments with faster convergence to stable strategies in games featuring complex interactions.
- •For online platform engineers: Improve adaptive algorithms for user interactions by reducing long-term decision regret in multi-user settings.
A theory result. No direct application yet.
Authors
Junsoo Ha
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.