# Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2013.

## Built on by (most cited first, 30 of 50)

- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [GIBBON: General-purpose Information-Based Bayesian OptimisatioN](https://mlsanity.com/paper/2102.03324/) (2021)
- [Joint Entropy Search for Multi-objective Bayesian Optimization](https://mlsanity.com/paper/2210.02905/) (2022)
- [Differentially Private Federated Bayesian Optimization with Distributed Exploration](https://mlsanity.com/paper/2110.14153/) (2021)
- [Sample-Then-Optimize Batch Neural Thompson Sampling](https://mlsanity.com/paper/2210.06850/) (2022)
- [Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes](https://mlsanity.com/paper/2110.11665/) (2021)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2302.01511/) (2023)
- [The Vizier Gaussian Process Bandit Algorithm](https://mlsanity.com/paper/2408.11527/) (2024)
- [An Efficient Batch Constrained Bayesian Optimization Approach for Analog Circuit Synthesis via Multi-objective Acquisition Ensemble](https://mlsanity.com/paper/2106.15412/) (2021)
- [Lenient Regret and Good-Action Identification in Gaussian Process Bandits](https://mlsanity.com/paper/2102.05793/) (2021)
- [Bayesian Optimization under Stochastic Delayed Feedback](https://mlsanity.com/paper/2206.09341/) (2022)
- [Graph Neural Network Bandits](https://mlsanity.com/paper/2207.06456/) (2022)
- [Batch Bayesian Optimization for Replicable Experimental Design](https://mlsanity.com/paper/2311.01195/) (2023)
- [Gaussian Max-Value Entropy Search for Multi-Agent Bayesian Optimization](https://mlsanity.com/paper/2303.05694/) (2023)
- [Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel](https://mlsanity.com/paper/2102.13382/) (2021)
- [Adversarial Attacks on Gaussian Process Bandits](https://mlsanity.com/paper/2110.08449/) (2021)
- [Preference-based Pure Exploration](https://mlsanity.com/paper/2412.02988/) (2024)
- [Kolmogorov-Smirnov Test-Based Actively-Adaptive Thompson Sampling for Non-Stationary Bandits](https://mlsanity.com/paper/2105.14586/) (2021)
- [TS-RSR: A provably efficient approach for batch Bayesian Optimization](https://mlsanity.com/paper/2403.04764/) (2024)
- [RAGSys: Item-Cold-Start Recommender as RAG System](https://mlsanity.com/paper/2405.17587/) (2024)
- [Regret Analysis for Randomized Gaussian Process Upper Confidence Bound](https://mlsanity.com/paper/2409.00979/) (2024)
- [Bayesian Calibration for Activity Based Models](https://mlsanity.com/paper/2203.04414/) (2022)
- [Certified Multi-Fidelity Zeroth-Order Optimization](https://mlsanity.com/paper/2308.00978/) (2023)
- [System-Aware Neural ODE Processes for Few-Shot Bayesian Optimization](https://mlsanity.com/paper/2406.02352/) (2024)
- [Active Learning for Level Set Estimation Using Randomized Straddle Algorithms](https://mlsanity.com/paper/2408.03144/) (2024)
- [Batched Kernelized Bandits: Refinements and Extensions](https://mlsanity.com/paper/2603.12627/) (2026)
- [Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes](https://mlsanity.com/paper/2110.02248/) (2021)

## Abstract (arXiv)

In this paper, we consider the challenge of maximizing an unknown function f for which evaluations are noisy and are acquired with high cost. An iterative procedure uses the previous measures to actively select the next estimation of f which is predicted to be the most useful. We focus on the case where the function can be evaluated in parallel with batches of fixed size and analyze the benefit compared to the purely sequential procedure in terms of cumulative regret. We introduce the Gaussian Process Upper Confidence Bound and Pure Exploration algorithm (GP-UCB-PE) which combines the UCB strategy and Pure Exploration in the same batch of evaluations along the parallel iterations. We prove theoretical upper bounds on the regret with batches of size K for this procedure which show the improvement of the order of sqrt{K} for fixed iteration cost over purely sequential versions. Moreover, the multiplicative constants involved have the property of being dimension-free. We also confirm empirically the efficiency of GP-UCB-PE on real and synthetic problems compared to state-of-the-art competitors.