Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization
Abstract
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.
Cite
Text
Takeno et al. "Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization." Transactions on Machine Learning Research, 2025.Markdown
[Takeno et al. "Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization." Transactions on Machine Learning Research, 2025.](https://mlanthology.org/tmlr/2025/takeno2025tmlr-regret/)BibTeX
@article{takeno2025tmlr-regret,
title = {{Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization}},
author = {Takeno, Shion and Inatsu, Yu and Karasuyama, Masayuki and Takeuchi, Ichiro},
journal = {Transactions on Machine Learning Research},
year = {2025},
url = {https://mlanthology.org/tmlr/2025/takeno2025tmlr-regret/}
}