Towards Optimal and Efficient Best Arm Identification in Linear Bandits
This work addresses an incremental improvement in bandit algorithms for researchers in machine learning, focusing on computational efficiency and sample complexity.
The paper tackles the problem of best arm identification in linear bandits by proposing a new algorithm that generalizes LUCB, showing optimal sample complexity for cases with two and three arms and indicating favorable performance in numerical comparisons.
We give a new algorithm for best arm identification in linearly parameterised bandits in the fixed confidence setting. The algorithm generalises the well-known LUCB algorithm of Kalyanakrishnan et al. (2012) by playing an arm which minimises a suitable notion of geometric overlap of the statistical confidence set for the unknown parameter, and is fully adaptive and computationally efficient as compared to several state-of-the methods. We theoretically analyse the sample complexity of the algorithm for problems with two and three arms, showing optimality in many cases. Numerical results indicate favourable performance over other algorithms with which we compare.