This paper analyzes the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al, 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, Srinivas et al proved that the regret vanishes at the approximate rate of $O(1/\sqrt{t})$, where t is the number of observations. To complement their result, we attack the deterministic case and attain a much faster exponential convergence rate. Under some regularity assumptions, we show that the regret decreases asymptotically according to $O(e^{-\frac{\tau t}{(\ln t)^{d/4}}})$ with high probability. Here, d is the dimension of the search space and tau is a constant that depends on the behaviour of the objective function near its global maximum.

通过分析高斯过程臂带问题，针对确定性观察结果，运用分支限定算法攻击了确定性情况并获得了更快的指数收敛率，显示出后悔随着时间推移而按高概率下降，估计呈现O（e ^ - tau * t / (ln t)^（d/4））的结果，其中d是搜索空间的维度，tau是目标函数在其全局最大值附近的行为所依赖的常数。

具有确定性观测的高斯过程赌博机的指数遗憾界