Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that non-adaptive random sampling of query points in GP-based Bayesian optimization achieves order-optimal posterior variance bounds and, via the REDS algorithm with domain shrinking, order-optimal cumulative regret in noise-free and noisy settings, resolving a COLT open problem with ~15-100x runtime speedups.
Problem
GP-based (kernel-based bandit) Bayesian optimization needs an order-optimal noise-free regret algorithm (an open COLT problem), and prevailing methods are computationally expensive because they must optimize non-convex acquisition functions at each step.
Approach
Replace adaptive acquisition-based query selection with open-loop uniform random sampling over the (shrinking) domain; prove universal sup-norm posterior variance concentration bounds for random designs in RKHS via operator spectrum concentration, and combine with domain shrinking (REDS).
Key results
- REDS achieves noise-free cumulative regret of order max{T^{(3-beta)/2},1} (up to logs), closing the gap and resolving the COLT open problem.
- REDS runtime on Branin/Hartmann-4D/Hartmann-6D is 0.32s, 0.47s, 1.19s versus BPE 29.84s, 38.45s, 119.71s and GP-ThreDS 4.37s, 7.59s, 19.33s (about 15x over GP-ThreDS and 100x over BPE).
- REDS regret is comparable to BPE and GP-ThreDS across the three benchmarks, with noisy regret O~(sqrt(T gamma_T)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use REDS instead of GP-ThreDS | Bayesian optimization · Branin, Hartmann-4D, and Hartmann-6D | runtime (seconds): ~15× speed-up | Helped |
| Use REDS instead of BPE | Bayesian optimization · Branin, Hartmann-4D, and Hartmann-6D | runtime (seconds): ~100× speed-up | Helped |
| Use REDS instead of BPE and GP-ThreDS | Bayesian optimization · Branin, Hartmann-4D, and Hartmann-6D | cumulative regret | No clear effect |
| Use random exploration instead of maximum posterior variance sampling | GP-based Bayesian optimization · Noisy and noise-free feedback | worst-case posterior variance | No clear effect |
Surprising findings
- Uniform random sampling matches the worst-case posterior variance rates of maximum posterior variance sampling, which is known to be order-optimal.
Limitations
- Noisy-regret analysis requires additional assumptions (discretization and bi-Lipschitz level set regularity).
- Empirical evaluation is limited to three synthetic benchmark functions with T=1000.
Experimental setup
Datasets: Branin Hartmann-4D Hartmann-6D
Benchmarks: Branin Hartmann-4D Hartmann-6D
Metrics: cumulative regret running time (seconds)
Baselines: BPE GP-ThreDS
Builds on: GP-UCB GP-ThreDS BPE Mercer's theorem
Closest papers by meaning
- Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance (ICML 2025 · similarity 0.91)
- Stopping Bayesian Optimization with Probabilistic Regret Bounds (NeurIPS 2024 · similarity 0.90)
- Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.90)
- Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization (NeurIPS 2025 · similarity 0.90)
- Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits (NeurIPS 2025 · similarity 0.90)
- Bayesian Analysis of Combinatorial Gaussian Process Bandits (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.