Finding All $\epsilon$-Good Arms in Stochastic Bandits

摘要: The pure-exploration problem in stochastic multi-armed bandits aims to find one or more arms with the largest (or near largest) means. Examples include finding an {\epsilon}-good arm, best-arm identification, top-k arm and all means above a specified threshold. However, of has been overlooked past work, although arguably this may be most natural objective many applications. For example, virologist conduct preliminary laboratory experiments on large candidate set treatments move into expensive clinical trials. Since ultimate efficacy is uncertain, it important identify candidates. Mathematically, all-{\epsilon}-good identification presents significant new challenges surprises that do not arise objectives studied past. We introduce two algorithms overcome these demonstrate their great empirical performance large-scale crowd-sourced dataset 2.2M ratings collected by New Yorker Caption Contest as well testing hundreds possible cancer drugs.