High-Dimensional Experimental Design and Kernel Bandits
This work addresses a bottleneck in high-dimensional experimental design and kernel bandits for researchers and practitioners in machine learning, offering a more efficient method when N is small relative to d, though it is incremental as it builds on existing rounding techniques.
The paper tackles the problem of converting continuous probability distributions from optimal experimental design into discrete assignments when the number of measurements N is much less than the dimension d, such as in RKHS settings. It proposes a rounding procedure that removes dependence on d, achieving nearly the same performance guarantees as existing methods, and applies it to kernel bandits to obtain state-of-the-art results in regret minimization and pure exploration with robustness to model misspecification.
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.