Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection

The stochastic multi-armed bandit is a classical and well-studied model for characterizing the explorationexploitation tradeoff in various decision-making problems in stochastic settings. The most well-known objective in the multi-armed bandit model is to maximize the cumulative gain (or equivalently, to minimize the cumulative regret) that the agent achieves. Another line of research, called the pure exploration multi-armed bandit problem, which is motivated by a variety of practical applications including medical trials [Rob85, AB10], communication network [AB10], and crowdsourcing [ZCL14, CLTL15], has also attracted significant attention recently. In the pure exploration problem, the agent draws samples from the arms adaptively (the exploration phase), and finally commits to one of the feasible solutions specified by the problem. In a sense, the exploitation phase in the pure exploration problem simply consists of exploiting the solution to which the agent commits indefinitely. Therefore, the agent's objective is to identify the optimal (or near-optimal) feasible solution with high probability. In this paper, we focus on the problem of identifying the top-k arms (i.e., the k arms with the largest means) in a stochastic multi-armed bandit model. The problem is known as the Best-k-Arm problem, and has been extensively studied in the past decade [KS10, GGL12, GGLB11, KTAS12, BWV12, KK13, ZCL14, KCG15, SJR16]. We formally define the Best-k-Arm problem as follows.