High-Dimensional Experimental Design and Kernel Bandits

Abstract

In recent years methods from optimal linear experimental design have been leveraged to obtain state of the art results for linear bandits. A design returned from an objective such as $G$-optimal design is actually a probability distribution over a pool of potential measurement vectors. Consequently, one nuisance of the approach is the task of converting this continuous probability distribution into a discrete assignment of $N$ measurements. While sophisticated rounding techniques have been proposed, in $d$ dimensions they require $N$ to be at least $d$, $d\log (\log (d))$, or $d^2$ based on the sub-optimality of the solution. In this paper we are interested in settings where $N$ may be much less than $d$, such as in experimental design in an RKHS where $d$ may be effectively infinite. In this work, we propose a rounding procedure that frees $N$ of any dependence on the dimension $d$, while achieving nearly the same performance guarantees of existing rounding procedures. We evaluate the procedure against a baseline that projects the problem to a lower dimensional space and performs rounding which requires $N$ to just be at least a notion of the effective dimension. We also leverage our new approach in a new algorithm for kernelized bandits to obtain state of the art results for regret minimization and pure exploration. An advantage of our approach over existing UCB-like approaches is that our kernel bandit algorithms are also robust to model misspecification.

References in corpus (10)

• A Tutorial on Bayesian Optimization
• The Parallel Knowledge Gradient Method for Batch Bayesian Optimization
• Finite-Time Analysis of Kernelised Contextual Bandits
• Best-Arm Identification in Linear Bandits
• Fast Randomized Kernel Methods With Statistical Guarantees
• Gamification of Pure Exploration for Linear Bandits
• On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions
• Corruption-Tolerant Gaussian Process Bandit Optimization
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits
• Refined bounds for randomized experimental design

Cited by in corpus (6)

• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Pure Exploration in Kernel and Neural Bandits
• Nearly Optimal Algorithms for Level Set Estimation
• Corruption Robust Active Learning
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits
• Collaborative Pure Exploration in Kernel Bandit