Bayesian Fixed-Budget Best-Arm Identification
This work addresses the problem of efficiently identifying optimal arms under budget constraints for Bayesian bandit algorithms, offering theoretical guarantees that are incremental over prior methods.
The paper tackles the fixed-budget best-arm identification problem in Bayesian bandits by proposing a Bayesian elimination algorithm and deriving an upper bound on its misidentification probability, which is the first distribution-dependent bound in this setting and nearly matches a lower bound for 2-armed cases.
Fixed-budget best-arm identification (BAI) is a bandit problem where the agent maximizes the probability of identifying the optimal arm within a fixed budget of observations. In this work, we study this problem in the Bayesian setting. We propose a Bayesian elimination algorithm and derive an upper bound on its probability of misidentifying the optimal arm. The bound reflects the quality of the prior and is the first distribution-dependent bound in this setting. We prove it using a frequentist-like argument, where we carry the prior through, and then integrate out the bandit instance at the end. We also provide a lower bound on the probability of misidentification in a $2$-armed Bayesian bandit and show that our upper bound (almost) matches it for any budget. Our experiments show that Bayesian elimination is superior to frequentist methods and competitive with the state-of-the-art Bayesian algorithms that have no guarantees in our setting.