Gaussian Process Bandit Optimization with Few Batches

Abstract

In this paper, we consider the problem of black-box optimization using Gaussian Process (GP) bandit optimization with a small number of batches. Assuming the unknown function has a low norm in the Reproducing Kernel Hilbert Space (RKHS), we introduce a batch algorithm inspired by batched finite-arm bandit algorithms, and show that it achieves the cumulative regret upper bound $O^{\ast }(\sqrt{T{\gamma }_T})$ using $O(\log \log T)$ batches within time horizon $T$, where the $O^{\ast }(\cdot )$ notation hides dimension-independent logarithmic factors and ${\gamma }_T$ is the maximum information gain associated with the kernel. This bound is near-optimal for several kernels of interest and improves on the typical $O^{\ast }(\sqrt{T}{\gamma }_T)$ bound, and our approach is arguably the simplest among algorithms attaining this improvement. In addition, in the case of a constant number of batches (not depending on $T$), we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches, focusing on the squared exponential and Matérn kernels. The algorithmic upper bounds are shown to be nearly minimax optimal via analogous algorithm-independent lower bounds.

arXiv commentAISTATS 2022

References in corpus (9)

• Practical Bayesian Optimization of Machine Learning Algorithms
• Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design
• Finite-Time Analysis of Kernelised Contextual Bandits
• Online Learning with Switching Costs and Other Adaptive Adversaries
• High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Regret Bounds for Batched Bandits
• Optimal Order Simple Regret for Gaussian Process Bandits
• Lenient Regret and Good-Action Identification in Gaussian Process Bandits

Cited by in corpus (1)

• Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures