Misspecified Gaussian Process Bandit Optimization
This addresses a critical limitation in kernelized bandit optimization for applications where model assumptions may not hold, offering practical solutions with theoretical guarantees.
The paper tackles the problem of optimizing black-box functions with noisy bandit feedback when the model is misspecified, introducing algorithms like EC-GP-UCB and Phased GP Uncertainty Sampling that achieve minimal performance degradation and optimal dependence on misspecification error, with upper bounds on cumulative regret in terms of ε, time horizon, and kernel.
We consider the problem of optimizing a black-box function based on noisy bandit feedback. Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. They heavily rely on the assumption that the model is well-specified, however, and can fail without it. Instead, we introduce a \emph{misspecified} kernelized bandit setting where the unknown function can be $ε$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS). We design efficient and practical algorithms whose performance degrades minimally in the presence of model misspecification. Specifically, we present two algorithms based on Gaussian process (GP) methods: an optimistic EC-GP-UCB algorithm that requires knowing the misspecification error, and Phased GP Uncertainty Sampling, an elimination-type algorithm that can adapt to unknown model misspecification. We provide upper bounds on their cumulative regret in terms of $ε$, the time horizon, and the underlying kernel, and we show that our algorithm achieves optimal dependence on $ε$ with no prior knowledge of misspecification. In addition, in a stochastic contextual setting, we show that EC-GP-UCB can be effectively combined with the regret bound balancing strategy and attain similar regret bounds despite not knowing $ε$.