Adaptive MultipleArm Identification
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:722730, 2017.
Abstract
We study the problem of selecting K arms with the highest expected rewards in a stochastic narmed bandit game. This problem has a wide range of applications, e.g., A/B testing, crowdsourcing, simulation optimization. Our goal is to develop a PAC algorithm, which, with probability at least $1\delta$, identifies a set of K arms with the aggregate regret at most $\epsilon$. The notion of aggregate regret for multiplearm identification was first introduced in Zhou et. al. (2014), which is defined as the difference of the averaged expected rewards between the selected set of arms and the best K arms. In contrast to Zhou et. al. (2014) that only provides instanceindependent sample complexity, we introduce a new hardness parameter for characterizing the difficulty of any given instance. We further develop two algorithms and establish the corresponding sample complexity in terms of this hardness parameter. The derived sample complexity can be significantly smaller than stateoftheart results for a large class of instances and matches the instanceindependent lower bound up to a $\log(\epsilon^{1})$ factor in the worst case. We also prove a lower bound result showing that the extra $\log(\epsilon^{1})$ is necessary for instancedependent algorithms using the introduced hardness parameter.
Related Material


