Title: Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection,
Abstract: In the Best-$k$-Arm problem, we are given $n$ stochastic bandit arms, each
associated with an unknown reward distribution. We are required to identify the
$k$ arms with the largest means by taking as few samples as possible. In this
paper, we make progress towards a complete characterization of the
instance-wise sample complexity bounds for the Best-$k$-Arm problem. On the
lower bound side, we obtain a novel complexity term to measure the sample
complexity that every Best-$k$-Arm instance requires. This is derived by an
interesting and nontrivial reduction from the Best-$1$-Arm problem. We also
provide an elimination-based algorithm that matches the instance-wise lower
bound within doubly-logarithmic factors. The sample complexity of our algorithm
strictly dominates the state-of-the-art for Best-$k$-Arm (module constant
factors).