Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
Not on the map. Why?
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.
Key facts. Cited by 1 paper 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
31 of 43 references.
References · 31
- 2017On Kernelized Multi-armed Banditscited by 352
- 2013Learning to Optimize Via Posterior Samplingcited by 256
- 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 192
- 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
- 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
- 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
- 2017Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Spacecited by 76
- 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
- 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
- 2013Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Explorationcited by 50
- 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
- 2020Scalable Thompson Sampling using Sparse Gaussian Process Modelscited by 39
19 more
- 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 31
- 2021Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processescited by 24
- 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
- 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 17
- 2023Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Boundscited by 16
- 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
- 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
- 2019On Batch Bayesian Optimizationcited by 12
- 2020Regret Bounds for Noise-Free Kernel-Based Banditscited by 11
- 2022Bayesian Optimization under Stochastic Delayed Feedbackcited by 10
- 2023Delayed Feedback in Kernel Banditscited by 10
- 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
- 2019Efficient Batch Black-box Optimization with Deterministic Regret Boundscited by 8
- 2024Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Explorationcited by 8
- 2024Tighter Confidence Bounds for Sequential Kernel Regressioncited by 8
- 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
- 2022Regret Bounds for Noise-Free Cascaded Kernelized Banditscited by 3
- 2026Batched Kernelized Bandits: Refinements and Extensionscited by 3
- 2026Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Boundscited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.