mlsanityData to 14 Oct 2026

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

arXiv 2310.15351 ↗First posted 23 Oct 2023cs.LG stat.MLcited by 17

Not on the map. Why?

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.

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

16 of 60 references.

References · 16

  1. 2016Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimizationcited by 699
  2. 2017On Kernelized Multi-armed Banditscited by 352
  3. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 192
  4. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  5. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  6. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  7. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  8. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  9. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  10. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
  11. 2020Convergence Guarantees for Gaussian Process Means With Misspecified Likelihoods and Smoothnesscited by 30
  12. 2020Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programmingcited by 28
4 more
  1. 2018Online learning with kernel lossescited by 12
  2. 2020Regret Bounds for Noise-Free Kernel-Based Banditscited by 11
  3. 2019Efficient Batch Black-box Optimization with Deterministic Regret Boundscited by 8
  4. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 6; 2026: 6.

17 papers.

Sort:

By area:

  1. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
  2. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  3. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  4. 2024Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Explorationcited by 8
  5. 2024Tighter Confidence Bounds for Sequential Kernel Regressioncited by 8
  6. 2024Near-Optimal Algorithm for Non-Stationary Kernelized Banditscited by 8
  7. 2024Transition Constrained Bayesian Optimization via Markov Decision Processescited by 7
  8. 2025Distributionally Robust Active Learning for Gaussian Process Regressioncited by 3
  9. 2026Batched Kernelized Bandits: Refinements and Extensionscited by 3
  10. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  11. 2026Improved Regret Analysis for Parallel Gaussian Process Bandit Optimizationcited by 1
  12. 2024Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomnesscited by 0
5 more
  1. 2025DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Banditscited by 0
  2. 2025Differential Privacy in Kernelized Contextual Bandits via Random Projectionscited by 0
  3. 2026Sharper Guarantees for Misspecified Kernelized Bandit Optimizationcited by 0
  4. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0
  5. 2026Exploration strategies for Gaussian process bandit optimization with inference regret guaranteescited by 0