Near Instance Optimal Model Selection for Pure Exploration Linear Bandits

Abstract

We introduce the model selection problem in pure exploration linear bandits, where the learner needs to adapt to the instance-dependent complexity measure of the smallest hypothesis class containing the true model. We design algorithms in both fixed confidence and fixed budget settings with near instance optimal guarantees. The core of our algorithms is a new optimization problem based on experimental design that leverages the geometry of the action set to identify a near-optimal hypothesis class. Our fixed budget algorithm is developed based on a novel selection-validation procedure, which provides a new way to study the understudied fixed budget setting (even without the added challenge of model selection). We adapt our algorithms, in both fixed confidence and fixed budget settings, to problems with model misspecification.

References in corpus (8)

• Best-Arm Identification in Linear Bandits
• Gamification of Pure Exploration for Linear Bandits
• Model Selection in Contextual Stochastic Bandit Problems
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
• Pure Exploration with Multiple Correct Answers
• High-Dimensional Experimental Design and Kernel Bandits
• The True Sample Complexity of Identifying Good Arms
• Pareto Optimal Model Selection in Linear Bandits