An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits

Abstract

This paper proposes near-optimal algorithms for the pure-exploration linear bandit problem in the fixed confidence and fixed budget settings. Leveraging ideas from the theory of suprema of empirical processes, we provide an algorithm whose sample complexity scales with the geometry of the instance and avoids an explicit union bound over the number of arms. Unlike previous approaches which sample based on minimizing a worst-case variance (e.g. G-optimal design), we define an experimental design objective based on the Gaussian-width of the underlying arm set. We provide a novel lower bound in terms of this objective that highlights its fundamental role in the sample complexity. The sample complexity of our fixed confidence algorithm matches this lower bound, and in addition is computationally efficient for combinatorial classes, e.g. shortest-path, matchings and matroids, where the arm sets can be exponentially large in the dimension. Finally, we propose the first algorithm for linear bandits in the the fixed budget setting. Its guarantee matches our lower bound up to logarithmic factors.

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
• An Efficient Bandit Algorithm for Realtime Multivariate Optimization
• Optimal Best Arm Identification with Fixed Confidence
• Best-Arm Identification in Linear Bandits
• Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime

Cited by in corpus (10)

• Combinatorial Pure Exploration with Full-Bandit or Partial Linear Feedback
• Improved Algorithms for Agnostic Pool-based Active Classification
• Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits
• Pure Exploration in Kernel and Neural Bandits
• Experimental Design for Regret Minimization in Linear Bandits
• Nearly Optimal Algorithms for Level Set Estimation
• Learning to Actively Learn: A Robust Approach
• Price of Safety in Linear Best Arm Identification
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits