Optimistic Hedge regret is O(n log n) for 2 players but exponential for 3, new paper shows
roydanroy · x · 2026-11-07
A new arXiv paper by Yuval Dagan, Nadav Eisen, Liad Erez, and Tomer Koren resolves a long-standing open question on Optimistic Hedge regret bounds. In two-player general-sum games, a suitable learning rate yields O(n log n) regret independent of horizon T; for three or more players, no such bound is possible—there exist games where some player's regret is 2^Ω(n), and for m≥3 players up to 2^Ω(mn). The results, built on a temporal approximation technique, bridge prior polylogarithmic and non-constructive constant bounds.
More from Research
- Google DeepMind shows AI agents accelerating cryptanalysis of encryption schemes — sebkrier · 2026-11-07
- DeepQMC benchmarks excited states of C2 and methylenimmonium against high-level references — FrankNoeBerlin · 2026-11-07
- Noé group releases transferable DeepQMC for excited-state potential energy surfaces in one run — FrankNoeBerlin · 2026-11-07
- Neel Nanda, after supervising 20+ papers, publishes a guide to writing great ML papers — CSProfKGD · 2026-11-07
- Reciprocal rank fusion explained: exact words, vectors, and re-rankers merged into one ranked list — lilyraynyc · 2026-11-07
- CMU paper: one computer-use agent ranks top-3 across four embodied ECCV competitions — wellecks · 2026-11-07