Optimal-Point Variance Reduction For Bayesian Optimization With Regret Guarantee
For practitioners of Bayesian optimization, this work provides a theoretically grounded one-step lookahead method with regret guarantees, addressing the gap between empirical effectiveness and theoretical understanding.
This paper proposes a one-step lookahead Bayesian optimization method called optimal-point variance reduction (OVR) that requires only posterior sampling and Monte Carlo approximations, and shows that a regularized version achieves a vanishing Bayesian expected simple regret upper bound.
This paper studies a one-step lookahead Bayesian optimization (BO) method and its theoretical guarantee. 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 proposes a one-step lookahead BO method called optimal-point variance reduction (OVR), which requires only posterior sampling and Monte Carlo approximations. We obtain a uniform error bound over an input domain for the Monte Carlo estimation in OVR. Furthermore, we show that the regularized OVR, with the slight modification to promote exploration, achieves a vanishing Bayesian expected simple regret upper bound. Finally, we demonstrate the effectiveness of OVR through numerical experiments.