Practical Algorithms for Best-K Identification in Multi-Armed Bandits
This addresses a fundamental problem in sequential decision-making with applications in recommendation systems, clinical trials, and other areas where adaptive sampling is needed.
The paper tackles the Best-K identification problem in multi-armed bandits, where the goal is to identify the K arms with the largest means with high confidence. The authors propose new practical algorithms that achieve nearly optimal sample complexity bounds and outperform state-of-the-art algorithms in practice.
In the Best-$K$ identification problem (Best-$K$-Arm), we are given $N$ stochastic bandit arms with unknown reward distributions. Our goal is to identify the $K$ arms with the largest means with high confidence, by drawing samples from the arms adaptively. This problem is motivated by various practical applications and has attracted considerable attention in the past decade. In this paper, we propose new practical algorithms for the Best-$K$-Arm problem, which have nearly optimal sample complexity bounds (matching the lower bound up to logarithmic factors) and outperform the state-of-the-art algorithms for the Best-$K$-Arm problem (even for $K=1$) in practice.