Metraipolis › archive › dc_e69af2b1b243
Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation — arXiv:2611.07078
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.07078
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-06T14:43:43.470Z
- SHA-256 of the archived text
bea1414036d8d5314564f5a1131939ea585f43d877f0a997072c1e8540095ac1- Stable URL of this page
https://metraipolis.com/documento/dc_e69af2b1b243
How to cite
Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation — arXiv:2611.07078 — arXiv (en), https://arxiv.org/abs/2611.07078 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e69af2b1b243 (Metraipolis archive dc_e69af2b1b243, sha256 bea1414036d8d5314564f5a1131939ea585f43d877f0a997072c1e8540095ac1)
BibTeX
@misc{dce69af2b1b243,
title = {Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation — arXiv:2611.07078},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.07078},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e69af2b1b243; sha256 bea1414036d8d5314564f5a1131939ea585f43d877f0a997072c1e8540095ac1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07078. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Optimistic Hedge, a multiplicative weight update with one step of extrapolation, is one of the most natural regret-minimizing dynamics for games, and characterizing its regret has been a longstanding open question. Daskalakis, Fishelson and Golowich proved that if all $m$ players in a finite general-sum game follow Optimistic Hedge with a fixed learning rate, each player's regret is polylogarithmic in the horizon $T$. Subsequently, Ha showed that an appropriate choice of learning rate makes each player's regret bounded independently of $T$. This bound, however, is non-constructive and its dependence on the number of actions $n$ is not explicit, leaving open whether Optimistic Hedge can achieve a constant regret bound which is polynomial in the size of the game. We show that the answer hinges on the number of players. In two-player games, there is a learning rate for which Optimistic Hedge guarantees $O(n\log n)$ regret independent of the horizon. In three-player games, however, no such bound is possible: for any learning rate up to an absolute constant and for sufficiently large horizon $T$, there is a game with $n$ actions per player in which some player's regret is $2^{\Omega(n)}$, and more generally, for every $m\ge3$ we construct $m$-player games in which some player's regret is $2^{\Omega(mn)}$; for learning rates above $2^{-\Omega(mn)}$, that player's regret even grows linearly in $T$. Our upper bound is based on a temporal approximation framework for the analysis of Optimistic Hedge. Starting from the variance-based RVU bound of Daskalakis et al., we approximate the losses over time-localized windows by well-behaved functions, whose total variation is a small fraction of their cumulative variance. In $m$-player games, the same framework gives a significantly simplified proof of the recent $O(\sqrt{m}\log n\log T)$ regret bound due to Ha.
Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2611.07078 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:20:12.604Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).