Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
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.
Related
- Exploration strategies for Gaussian process bandit optimization with inference regret guarantees
- Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
- ISBO: Scalable Spatio-Temporal Bayesian Optimization with Log Gaussian Cox Process Models via the INLA-SPDE Approach
- Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
- Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback
BibTeX
@misc{takeno2026improved,
title = {{Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization}},
author = {Shion Takeno and Shogo Iwazaki},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.16492},
eprint = {2608.16492},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.16492},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
AU - Shion Takeno
AU - Shogo Iwazaki
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2608.16492
UR - https://arxiv.org/abs/2608.16492
AB - 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.
ER -