Title: Nonlinear Sequential Accepts and Rejects for Identification of Top Arms in Stochastic Bandits,
Abstract: We address the M-best-arm identification problem in multi-armed bandits. A
player has a limited budget to explore K arms (M<K), and once pulled, each arm
yields a reward drawn (independently) from a fixed, unknown distribution. The
goal is to find the top M arms in the sense of expected reward. We develop an
algorithm which proceeds in rounds to deactivate arms iteratively. At each
round, the budget is divided by a nonlinear function of remaining arms, and the
arms are pulled correspondingly. Based on a decision rule, the deactivated arm
at each round may be accepted or rejected. The algorithm outputs the accepted
arms that should ideally be the top M arms. We characterize the decay rate of
the misidentification probability and establish that the nonlinear budget
allocation proves to be useful for different problem environments (described by
the number of competitive arms). We provide comprehensive numerical experiments
showing that our algorithm outperforms the state-of-the-art using suitable
nonlinearity.