Bandits with many optimal arms
Rianne de Heide, James Cheshire, Pierre Ménard and Alexandra Carpentier
Bandits with many optimal arms
Rianne de Heide, James Cheshire, Pierre Ménard and Alexandra Carpentier
Advances in Neural Information Processing Systems 34 (2021): 22457-22469 arxiv proc poster
What is this paper about?
This paper studies stochastic bandits with a possibly infinite collection of arms and a positive proportion of optimal arms. It characterises learning rates for both cumulative regret and best-arm identification and gives matching or near-matching algorithms.
Summary
We consider a stochastic bandit problem with a possibly infinite number of arms. We write p* for the proportion of optimal arms and Δ for the minimal mean gap between optimal and sub-optimal arms. We characterize optimal learning rates in both cumulative regret and best-arm identification in terms of the budget, p* and Δ. For cumulative regret we give a lower bound and a UCB-style algorithm with a matching upper bound up to logarithmic factors, and show that knowledge of p* is necessary for adaptation. For best-arm identification we give an exponential lower bound on the probability of outputting a sub-optimal arm and an elimination algorithm whose upper bound matches it up to a logarithmic factor in the exponent. The results also apply to related quantile and good-arm identification problems.