Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
This work addresses the sample efficiency challenge in identifying top-performing arms for applications like recommendation systems, though it is incremental as it builds on prior lower bound and algorithm frameworks.
The paper tackles the Best-k-Arm problem in stochastic bandits by deriving a novel lower bound on instance-wise sample complexity and providing an elimination-based algorithm that matches this bound within doubly-logarithmic factors, strictly dominating state-of-the-art methods.
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).