Fixed-Budget Best-Arm Identification in Structured Bandits

Understand

Best-arm identification (BAI) in a fixed-budget setting is a bandit problem where the learning agent maximizes the probability of identifying the optimal (best) arm after a fixed number of observations.

• Most works on this topic study unstructured problems with a small number of arms, which limits their applicability.
• We propose a general tractable algorithm that incorporates the structure, by successively eliminating suboptimal arms based on their mean reward estimates from a joint generalization model.
• We analyze our algorithm in linear and generalized linear models (GLMs), and propose a practical implementation based on a G-optimal design.