Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
stat.ML, cs.LG
Submitted: 2026-08-17
Updated: 2026-09-16
Comments: 25 pages, 1 figure, Corrected Lemma 4.2 and the regret bounds for the SE kernel in the noiseless setting
License: http://creativecommons.org/licenses/by/4.0/
The gist: This paper studies the regret analysis for parallel Gaussian process (GP) bandit optimization.
Terminology
Abstract
This paper studies the regret analysis for parallel Gaussian process (GP) bandit optimization. The known regret upper bounds for the widely used GP batched upper confidence bound and GP batched Thompson sampling (GP-BTS) suffer from a multiplicative factor with respect to the batch size Q. To avoid this degradation, existing analyses require a polynomial number of uncertainty sampling (US) for Q at the beginning of optimization. However, this initial US phase is often ineffective in practice. This paper shows that the regret upper bound without the multiplicative factor on Q can be achieved without the initial US phase, using GP-BTS as an example. Furthermore, we show much better regret upper bounds in the noiseless setting than in the noisy setting, as in the sequential GP bandit setting.
Sources
- On Batch Bayesian Optimization
- Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
- Gaussian Processes and Reproducing Kernel Hilbert Spaces: Connections and Equivalences
- Efficient Batch Black-box Optimization with Deterministic Regret Bounds
- Batched Kernelized Bandits: Refinements and Extensions
- Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- One Permutation Is All You Need: Fast, Deterministic Feature Importance and Model Stress-Testing
- Online Conformal Prediction for Non-Exchangeable Panel Data
- Deep Time-Series Forecasting in 10 Years: A Survey