# Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization

arXiv: https://arxiv.org/abs/2608.16492 · HTML: https://mlsanity.com/paper/2608.16492/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 43 references that are in the map.
- First posted on arXiv 17 Aug 2026.

## Builds on (most cited first, 30 of 31)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space](https://mlsanity.com/paper/1706.01825/) (2017)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Scalable Thompson Sampling using Sparse Gaussian Process Models](https://mlsanity.com/paper/2006.05356/) (2020)
- [On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2008.08757/) (2020)
- [Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes](https://mlsanity.com/paper/2110.11665/) (2021)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency](https://mlsanity.com/paper/2310.15351/) (2023)
- [Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2311.03760/) (2023)
- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [On Batch Bayesian Optimization](https://mlsanity.com/paper/1911.01032/) (2019)
- [Regret Bounds for Noise-Free Kernel-Based Bandits](https://mlsanity.com/paper/2002.05096/) (2020)
- [Bayesian Optimization under Stochastic Delayed Feedback](https://mlsanity.com/paper/2206.09341/) (2022)
- [Delayed Feedback in Kernel Bandits](https://mlsanity.com/paper/2302.00392/) (2023)
- [Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits](https://mlsanity.com/paper/2502.19006/) (2025)
- [Efficient Batch Black-box Optimization with Deterministic Regret Bounds](https://mlsanity.com/paper/1905.10041/) (2019)
- [Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Exploration](https://mlsanity.com/paper/2401.17037/) (2024)
- [Tighter Confidence Bounds for Sequential Kernel Regression](https://mlsanity.com/paper/2403.12732/) (2024)
- [Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere](https://mlsanity.com/paper/2602.17940/) (2026)
- [Regret Bounds for Noise-Free Cascaded Kernelized Bandits](https://mlsanity.com/paper/2211.05430/) (2022)
- [Batched Kernelized Bandits: Refinements and Extensions](https://mlsanity.com/paper/2603.12627/) (2026)

## Built on by (most cited first, 1 of 1)

- [Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization](https://mlsanity.com/paper/2610.19925/) (2026)

## Abstract (arXiv)

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.