Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
2026-08-17 • Machine Learning
Machine Learning
AI summaryⓘ
The authors look at how well parallel Gaussian process methods work when making decisions in batches. Normally, the known performance measures get worse when the batch size grows, and previous solutions needed an extra step at the start to reduce this problem, which isn't always helpful. They show that one common method can avoid this worsening without that extra starting step. They also find that in situations without noise, the method performs much better, similar to known results for sequential cases.
Gaussian processbandit optimizationregret analysisbatch sizeupper confidence boundThompson samplinguncertainty samplingnoiseless settingnoisy setting
Authors
Shion Takeno, Shogo Iwazaki
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.