Bandits with many optimal arms

Abstract

We consider a stochastic bandit problem with a possibly infinite number of arms. We write $p^{\ast }$ for the proportion of optimal arms and $\Delta$ for the minimal mean-gap between optimal and sub-optimal arms. We characterize the optimal learning rates both in the cumulative regret setting, and in the best-arm identification setting in terms of the problem parameters $T$ (the budget), $p^{\ast }$ and $\Delta$. For the objective of minimizing the cumulative regret, we provide a lower bound of order $\Omega (\log (T)/(p^{\ast }\Delta ))$ and a UCB-style algorithm with matching upper bound up to a factor of $\log (1/\Delta )$. Our algorithm needs $p^{\ast }$ to calibrate its parameters, and we prove that this knowledge is necessary, since adapting to $p^{\ast }$ in this setting is impossible. For best-arm identification we also provide a lower bound of order $\Omega (\exp (-cT{\Delta }^2{p}^{\ast }))$ on the probability of outputting a sub-optimal arm where $c>0$ is an absolute constant. We also provide an elimination algorithm with an upper bound matching the lower bound up to a factor of order $\log (T)$ in the exponential, and that does not need $p^{\ast }$ or $\Delta$ as parameter. Our results apply directly to the three related problems of competing against the $j$-th best arm, identifying an $\epsilon$ good arm, and finding an arm with mean larger than a quantile of a known order.

arXiv commentSubstantial rewrite and added experiments. Accepted for NeurIPS 2021

References in corpus (9)

• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• On Explore-Then-Commit Strategies
• Black-box optimization of noisy functions with unknown smoothness
• Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
• Simple regret for infinitely many armed bandits
• Sample complexity of partition identification using multi-armed bandits
• The True Sample Complexity of Identifying Good Arms
• Polynomial Cost of Adaptation for X -Armed Bandits
• On Regret with Multiple Best Arms