Rate-optimal Bayesian Simple Regret in Best Arm Identification
This work addresses the specific problem of optimizing simple regret in Bayesian bandit settings, offering a rate-optimal solution that is incremental relative to prior regret minimization approaches.
The paper tackles the problem of best arm identification in multi-armed bandits by characterizing the rate of Bayesian simple regret under prior continuity conditions, showing it depends on gaps smaller than sqrt(log T/T), and proposes an algorithm that matches the lower bound up to a constant factor, with simulations supporting the theory.
We consider best arm identification in the multi-armed bandit problem. Assuming certain continuity conditions of the prior, we characterize the rate of the Bayesian simple regret. Differing from Bayesian regret minimization (Lai, 1987), the leading term in the Bayesian simple regret derives from the region where the gap between optimal and suboptimal arms is smaller than $\sqrt{\frac{\log T}{T}}$. We propose a simple and easy-to-compute algorithm with its leading term matching with the lower bound up to a constant factor; simulation results support our theoretical findings.