mlsanityData to 14 Oct 2026

Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization

arXiv 2606.00956 ↗First posted 31 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

This paper studies theoretical guarantees of a one-step lookahead Bayesian optimization (BO) method. Although the empirical effectiveness of one-step lookahead BO methods, such as entropy search, has been studied extensively, they often rely on computationally intractable approximations, and their regret guarantees remain underdeveloped. Thus, this paper analyzes a one-step lookahead BO method, which we refer to as optimal-point variance reduction (OVR), that requires only posterior sampling and Monte Carlo approximations. We obtain a uniform Monte Carlo estimation error bound over an input domain in an acquisition function computation. Furthermore, we show that the regularized OVR, with a slight modification to facilitate exploration, achieves a vanishing Bayesian expected simple regret upper bound. Finally, we validate the performance of OVR and regularized OVR through numerical experiments.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 38 of its 59 references that are in the map. First posted on arXiv 31 May 2026.

Builds on

38 of 59 references.

References · 38

  1. 2017On Kernelized Multi-armed Banditscited by 352
  2. 2013Learning to Optimize Via Posterior Samplingcited by 256
  3. 2017Max-value Entropy Search for Efficient Bayesian Optimizationcited by 206
  4. 2014Predictive Entropy Search for Efficient Global Optimization of Black-box Functionscited by 204
  5. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  6. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  7. 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 139
  8. 2020Efficiently Sampling Functions from Gaussian Process Posteriorscited by 127
  9. 2018A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizationscited by 99
  10. 2016Multi-Information Source Optimizationcited by 84
  11. 2019ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendationscited by 77
  12. 2016The Parallel Knowledge Gradient Method for Batch Bayesian Optimizationcited by 74
26 more
  1. 2020Pathwise Conditioning of Gaussian Processescited by 64
  2. 2019Multi-objective Bayesian Optimization using Pareto-frontier Entropycited by 57
  3. 2022Joint Entropy Search for Maximally-Informed Bayesian Optimizationcited by 55
  4. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  5. 2015Predictive Entropy Search for Bayesian Optimization with Unknown Constraintscited by 51
  6. 2021GIBBON: General-purpose Information-Based Bayesian OptimisatioNcited by 47
  7. 2022Joint Entropy Search for Multi-objective Bayesian Optimizationcited by 45
  8. 2016Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimationcited by 40
  9. 2020Scalable Thompson Sampling using Sparse Gaussian Process Modelscited by 39
  10. 2020Olympus: a benchmarking framework for noisy optimization and experiment planningcited by 29
  11. 2021Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processescited by 24
  12. 2021Sequential- and Parallel- Constrained Max-value Entropy Search via Information Lower Boundcited by 23
  13. 2021Bayesian Optimization for Cascade-type Multi-stage Processescited by 17
  14. 2023Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Boundscited by 16
  15. 2023Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Boundscited by 16
  16. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
  17. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  18. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  19. 2023Bounding Box-based Multi-objective Bayesian Optimization of Risk Measures under Input Uncertaintycited by 5
  20. 2024Regret Analysis for Randomized Gaussian Process Upper Confidence Boundcited by 4
  21. 2025Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimizationcited by 4
  22. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  23. 2022On the Finite-Time Performance of the Knowledge Gradient Algorithmcited by 3
  24. 2025Distributionally Robust Active Learning for Gaussian Process Regressioncited by 3
  25. 2026On Regret Bounds of Thompson Sampling for Bayesian Optimizationcited by 3
  26. 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spacescited by 2

Built on by

Not cited yet.