# Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization

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

## 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 (most cited first, 30 of 38)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Efficiently Sampling Functions from Gaussian Process Posteriors](https://mlsanity.com/paper/2002.09309/) (2020)
- [A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations](https://mlsanity.com/paper/1805.12168/) (2018)
- [Multi-Information Source Optimization](https://mlsanity.com/paper/1603.00389/) (2016)
- [ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations](https://mlsanity.com/paper/1908.01425/) (2019)
- [The Parallel Knowledge Gradient Method for Batch Bayesian Optimization](https://mlsanity.com/paper/1606.04414/) (2016)
- [Pathwise Conditioning of Gaussian Processes](https://mlsanity.com/paper/2011.04026/) (2020)
- [Multi-objective Bayesian Optimization using Pareto-frontier Entropy](https://mlsanity.com/paper/1906.00127/) (2019)
- [Joint Entropy Search for Maximally-Informed Bayesian Optimization](https://mlsanity.com/paper/2206.04771/) (2022)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Predictive Entropy Search for Bayesian Optimization with Unknown Constraints](https://mlsanity.com/paper/1502.05312/) (2015)
- [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)
- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [Scalable Thompson Sampling using Sparse Gaussian Process Models](https://mlsanity.com/paper/2006.05356/) (2020)
- [Olympus: a benchmarking framework for noisy optimization and experiment planning](https://mlsanity.com/paper/2010.04153/) (2020)
- [Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes](https://mlsanity.com/paper/2110.11665/) (2021)
- [Sequential- and Parallel- Constrained Max-value Entropy Search via Information Lower Bound](https://mlsanity.com/paper/2102.09788/) (2021)
- [Bayesian Optimization for Cascade-type Multi-stage Processes](https://mlsanity.com/paper/2111.08330/) (2021)
- [Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2302.01511/) (2023)
- [Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2311.03760/) (2023)
- [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)

## 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.