  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 the linear
bandit instance. Complementarily, we present a minimax lower bound for this
problem. The upper and lower bounds show that OD-LinBAI is minimax optimal up
to constant multiplicative factors in the exponent, which is a significant
theoretical improvement over existing methods (e.g., BayesGap, Peace,
LinearExploration and GSE), and settles the question of ascertaining the
difficulty of learning the best arm in the fixed-budget setting. Finally,
numerical experiments demonstrate considerable empirical improvements over
existing algorithms on a variety of real and synthetic datasets.
