  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.
