mlsanityData to 14 Oct 2026

Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization

arXiv 2507.09828 ↗First posted 13 Jul 2025stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Bayesian optimization is a powerful tool for optimizing an expensive-to-evaluate black-box function. In particular, the effectiveness of expected improvement (EI) has been demonstrated in a wide range of applications. However, theoretical analyses of EI are limited compared with other theoretically established algorithms. This paper analyzes a randomized variant of EI, which evaluates the EI from the maximum of the posterior sample path. We show that this posterior sampling-based random EI achieves the sublinear Bayesian cumulative regret bounds under the assumption that the black-box function follows a Gaussian process. Finally, we demonstrate the effectiveness of the proposed method through numerical experiments.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 27 of its 58 references that are in the map. First posted on arXiv 13 Jul 2025.

Builds on

27 of 58 references.

References · 27

  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. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  5. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  6. 2023Unexpected Improvements to Expected Improvement for Bayesian Optimizationcited by 149
  7. 2016Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Roboticscited by 134
  8. 2014Bayesian Optimization with Unknown Constraintscited by 109
  9. 2017Constrained Bayesian Optimization with Noisy Experimentscited by 104
  10. 2018A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizationscited by 99
  11. 2022Joint Entropy Search for Maximally-Informed Bayesian Optimizationcited by 55
  12. 2021High-Dimensional Bayesian Optimisation with Variational Autoencoders and Deep Metric Learningcited by 54
15 more
  1. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  2. 2022Joint Entropy Search for Multi-objective Bayesian Optimizationcited by 45
  3. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  4. 2014Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameterscited by 31
  5. 2021Sequential- and Parallel- Constrained Max-value Entropy Search via Information Lower Boundcited by 23
  6. 2018Tight Regret Bounds for Bayesian Optimization in One Dimensioncited by 20
  7. 2022Distributionally Robust Bayesian Optimization with varphi-divergencescited by 16
  8. 2023Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Boundscited by 16
  9. 2023Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Boundscited by 16
  10. 2022Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimizationcited by 15
  11. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
  12. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  13. 2022Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimizationcited by 6
  14. 2025On the convergence rate of noisy Bayesian Optimization with Expected Improvementcited by 4
  15. 2020Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholdingcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026On Regret Bounds of Thompson Sampling for Bayesian Optimizationcited by 3
  2. 2026Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Boundscited by 2
  3. 2026Towards Regret Guarantees for One-Step Lookahead Bayesian Optimizationcited by 0
  4. 2026Principled Design of Expected Improvement for Continuous Simulation Optimizationcited by 0