# Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 60 references that are in the map.
- First posted on arXiv 23 Oct 2023.

## Builds on (most cited first, 16 of 16)

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [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)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance](https://mlsanity.com/paper/2010.13997/) (2020)
- [Convergence Guarantees for Gaussian Process Means With Misspecified Likelihoods and Smoothness](https://mlsanity.com/paper/2001.10818/) (2020)
- [Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programming](https://mlsanity.com/paper/2004.11408/) (2020)
- [Online learning with kernel losses](https://mlsanity.com/paper/1802.09732/) (2018)
- [Regret Bounds for Noise-Free Kernel-Based Bandits](https://mlsanity.com/paper/2002.05096/) (2020)
- [Efficient Batch Black-box Optimization with Deterministic Regret Bounds](https://mlsanity.com/paper/1905.10041/) (2019)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)

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

- [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)
- [Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits](https://mlsanity.com/paper/2502.19006/) (2025)
- [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)
- [Near-Optimal Algorithm for Non-Stationary Kernelized Bandits](https://mlsanity.com/paper/2410.16052/) (2024)
- [Transition Constrained Bayesian Optimization via Markov Decision Processes](https://mlsanity.com/paper/2402.08406/) (2024)
- [Distributionally Robust Active Learning for Gaussian Process Regression](https://mlsanity.com/paper/2502.16870/) (2025)
- [Batched Kernelized Bandits: Refinements and Extensions](https://mlsanity.com/paper/2603.12627/) (2026)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)
- [Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2608.16492/) (2026)
- [Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness](https://mlsanity.com/paper/2402.13182/) (2024)
- [DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Bandits](https://mlsanity.com/paper/2501.19401/) (2025)
- [Differential Privacy in Kernelized Contextual Bandits via Random Projections](https://mlsanity.com/paper/2507.13639/) (2025)
- [Sharper Guarantees for Misspecified Kernelized Bandit Optimization](https://mlsanity.com/paper/2605.05967/) (2026)
- [Learning Kernel-Based MDPs from Episodic Preferential Feedback](https://mlsanity.com/paper/2605.23650/) (2026)
- [Exploration strategies for Gaussian process bandit optimization with inference regret guarantees](https://mlsanity.com/paper/2610.16187/) (2026)

## Abstract (arXiv)

We consider Bayesian optimization using Gaussian Process models, also referred to as kernel-based bandit optimization. We study the methodology of exploring the domain using random samples drawn from a distribution. We show that this random exploration approach achieves the optimal error rates. Our analysis is based on novel concentration bounds in an infinite dimensional Hilbert space established in this work, which may be of independent interest. We further develop an algorithm based on random exploration with domain shrinking and establish its order-optimal regret guarantees under both noise-free and noisy settings. In the noise-free setting, our analysis closes the existing gap in regret performance and thereby resolves a COLT open problem. The proposed algorithm also enjoys a computational advantage over prevailing methods due to the random exploration that obviates the expensive optimization of a non-convex acquisition function for choosing the query points at each iteration.