Towards Optimal and Efficient Best Arm Identification in Linear Bandits
arXiv:1911.01695
Abstract
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.
References in corpus (7)
- On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
- lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
- Optimal Best Arm Identification with Fixed Confidence
- Best-Arm Identification in Linear Bandits
- Fully adaptive algorithm for pure exploration in linear bandits
- Sequential Experimental Design for Transductive Linear Bandits
- Contextual Bandits with Latent Confounders: An NMF Approach
Cited by in corpus (4)
- Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners
- Combinatorial Pure Exploration with Full-Bandit or Partial Linear Feedback
- Best Arm Identification in Graphical Bilinear Bandits
- Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation