On the Suboptimality of GP-UCB under Polynomial Effective Optimism

Wenjia Wang, Xiaowei Zhang

Gaussian process upper confidence bound (GP-UCB) is widely used for sequential optimization of expensive black-box functions. Although many upper bounds on its cumulative regret ha…