Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization

Gaussian process (GP) bandit optimization is a powerful framework for black-box optimization of expensive functions. In parallel or asynchronous settings, algorithms must evaluate a batch of query points simultaneously or without waiting for recent results. A fundamental theoretical challenge in these batched settings is that cumulative regret bounds traditionally suffer from a multiplicative degradation factor depending on the batch size Q. To avoid this degradation, existing analyses require an initial phase of uncertainty sampling (US), which is often ineffective in practice. This paper investigates whether this multiplicative penalty on Q can be removed for GP batched Thompson sampling (GP-BTS) without relying on an initial US phase.

The authors develop a novel technical lemma that effectively decouples the batch size Q as an additive term rather than a multiplicative one in the regret upper bound. By combining this technique with an elliptical potential count argument and adapted posterior variance inequalities, the authors analyze the cumulative and simple regret of GP-BTS under both noisy and noiseless feedback settings. For the noiseless setting, they further leverage recent proof techniques developed for sequential GP-UCB to establish significantly tighter bounds.

In the noisy setting, GP-BTS achieves a cumulative regret upper bound of O(Q log^(d+1) Q + sqrt(T) polylog(T)) for squared exponential kernels and sublinear bounds depending on Q^(2nu+d)/(2nu) + T^(2nu+3d)/(4nu+2d) for Matérn kernels. This completely eliminates the multiplicative factor on Q found in previous analyses without requiring any initial US phase. Furthermore, in the noiseless setting, the regret bounds are dramatically improved, growing only logarithmically or polylogynomially with T depending on the kernel smoothness and dimension, showing a much milder dependence on the horizon.