PAC Identification of Many Good Arms in Stochastic MultiArmed Bandits
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:9911000, 2019.
Abstract
We consider the problem of identifying any k out of the best m arms in an narmed stochastic multiarmed bandit; framed in the PAC setting, this particular problem generalises both the problem of “best subset selection” (Kalyanakrishnan & Stone, 2010) and that of selecting “one out of the best m” arms (Roy Chaudhuri & Kalyanakrishnan, 2017). We present a lower bound on the worstcase sample complexity for general k, and a fully sequential PAC algorithm, LUCBkm, which is more sampleefficient on easy instances. Also, extending our analysis to infinitearmed bandits, we present a PAC algorithm that is independent of n, which identifies an arm from the best $\rho$ fraction of arms using at most an additive polylog number of samples than compared to the lower bound, thereby improving over Roy Chaudhuri & Kalyanakrishnan (2017) and Aziz et al. (2018). The problem of identifying k > 1 distinct arms from the best $\rho$ fraction is not always welldefined; for a special class of this problem, we present lower and upper bounds. Finally, through a reduction, we establish a relation between upper bounds for the “one out of the best $\rho$” problem for infinite instances and the “one out of the best m” problem for finite instances. We conjecture that it is more efficient to solve “small” finite instances using the latter formulation, rather than going through the former.
Related Material


