Improved Regret Bounds for Bandits with Expert Advice
Not on the map. Why?
Abstract (arXiv)
In this research note, we revisit the bandits with expert advice problem. Under a restricted feedback model, we prove a lower bound of order √K T ln(N/K) for the worst-case regret, where K is the number of actions, N>K the number of experts, and T the time horizon. This matches a previously known upper bound of the same order and improves upon the best available lower bound of √K T (ln N) / (ln K). For the standard feedback model, we prove a new instance-based upper bound that depends on the agreement between the experts and provides a logarithmic improvement compared to prior results.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 12 of its 23 references that are in the map. First posted on arXiv 24 Jun 2024.
Builds on
12 of 23 references.
References · 12
- 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
- 2015Online Learning with Feedback Graphs: Beyond Banditscited by 79
- 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
- 2014Nonstochastic Multi-Armed Bandits with Graph-Structured Feedbackcited by 61
- 2015Fighting Bandits with a New Kind of Smoothnesscited by 45
- 2013From Bandits to Experts: A Tale of Domination and Independencecited by 28
- 2013The price of bandit information in multiclass online classificationcited by 24
- 2018Make the Minority Great Again: First-Order Regret Bound for Contextual Banditscited by 17
- 2023On the Minimax Regret for Online Learning with Feedback Graphscited by 8
- 2013Multiarmed Bandits With Limited Expert Advicecited by 7
- 2023On Interpolating Experts and Multi-Armed Banditscited by 4
- 2024Information Capacity Regret Bounds for Bandits with Mediator Feedbackcited by 4
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.