Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits. (arXiv:2105.13017v2 [cs.LG] UPDATED)

We study the problem of best arm identification in linear bandits in the
fixed-budget setting. By leveraging properties of the G-optimal design and
incorporating it into the arm allocation rule, we design a parameter-free
algorithm, Optimal Design-based Linear Best Arm Identification (OD-LinBAI). We
provide a theoretical analysis of the failure probability of OD-LinBAI. Instead
of all the optimality gaps, the performance of OD-LinBAI depends only on the
gaps of the top $d$ arms, where $d$ is the effective dimension of …

arm arxiv budget identification linear minimax