Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian
  Regret Bounds
Shion Takeno Yu Inatsu Masayuki Karasuyama Ichiro Takeuchi
Among various acquisition functions (AFs) in Bayesian optimization (BO),
Gaussian process upper confidence bound (GP-UCB) and Thompson sampling (TS) are
well-known options with established theoretical properties regarding Bayesian
cumulative regret (BCR). Recently, it has been shown that a randomized variant
of GP-UCB achieves a tighter BCR bound compared with GP-UCB, which we call the
tighter BCR bound for brevity. Inspired by this study, this paper first shows
that TS achieves the tighter BCR bound. On the other hand, GP-UCB and TS often
practically suffer from manual hyperparameter tuning and over-exploration
issues, respectively. To overcome these difficulties, we propose yet another AF
called a probability of improvement from the maximum of a sample path (PIMS).
We show that PIMS achieves the tighter BCR bound and avoids the hyperparameter
tuning, unlike GP-UCB. Furthermore, we demonstrate a wide range of experiments,
focusing on the effectiveness of PIMS that mitigates the practical issues of
GP-UCB and TS.