Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm
  Identification in Structured Bandits
Nicolas Nguyen Imad Aouali András György Claire Vernade
We study the problem of Bayesian fixed-budget best-arm identification (BAI)
in structured bandits. We propose an algorithm that uses fixed allocations
based on the prior information and the structure of the environment. We provide
theoretical bounds on its performance across diverse models, including the
first prior-dependent upper bounds for linear and hierarchical BAI. Our key
contribution is introducing new proof methods that result in tighter bounds for
multi-armed BAI compared to existing methods. We extensively compare our
approach to other fixed-budget BAI methods, demonstrating its consistent and
robust performance in various settings. Our work improves our understanding of
Bayesian fixed-budget BAI in structured bandits and highlights the
effectiveness of our approach in practical scenarios.