Gaussian Process Bandit Optimization with Few Batches
This addresses the problem of efficient batch-based optimization for researchers in machine learning and optimization, offering a simpler algorithm with theoretical guarantees, though it is incremental in improving regret bounds.
The paper tackles black-box optimization using Gaussian Process bandits with few batches, achieving a near-optimal cumulative regret bound of O*(√Tγ_T) with O(log log T) batches, improving on prior bounds and showing minimax optimality for specific kernels.
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γ_T})$ using $O(\log\log T)$ batches within time horizon $T$, where the $O^\ast(\cdot)$ notation hides dimension-independent logarithmic factors and $γ_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}γ_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.