A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice
Not on the map. Why?
Abstract (arXiv)
We determine the minimax optimal expected regret in the classic non-stochastic multi-armed bandit with expert advice problem, by proving a lower bound that matches the upper bound of Kale (2014). The two bounds determine the minimax optimal expected regret to be Thetaleft( √T K log (N/K) right), where K is the number of arms, N is the number of experts, and T is the time horizon.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 6 of its 15 references that are in the map. First posted on arXiv 31 Oct 2025.
Builds on
6 of 15 references.
References · 6
- 2013The price of bandit information in multiclass online classificationcited by 24
- 2021Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Gamescited by 18
- 2023Multiclass Online Learnability under Bandit Feedbackcited by 12
- 2013Multiarmed Bandits With Limited Expert Advicecited by 7
- 2023On Interpolating Experts and Multi-Armed Banditscited by 4
- 2024Improved Regret Bounds for Bandits with Expert Advicecited by 3
Built on by
Citing papers per year: 2026: 1.
1 paper.