In the kernelized bandit problem, a learner aims to sequentially compute the
optimum of a function lying in a reproducing kernel Hilbert space given only
noisy evaluations at sequentially chosen points. In particular, the learner
aims to minimize regret, which is a measure of the suboptimality of the choices
made. Arguably the most popular algorithm is the Gaussian Process Upper
Confidence Bound (GP-UCB) algorithm, which involves acting based on a simple
linear estimator of the unknown function. Despite its popularity, existing
analyses of GP-UCB give a suboptimal regret rate, which fails to be sublinear
for many commonly used kernels such as the Mat\'ern kernel. This has led to a
longstanding open question: are existing regret analyses for GP-UCB tight, or
can bounds be improved by using more sophisticated analytical techniques? In
this work, we resolve this open question and show that GP-UCB enjoys nearly
optimal regret. In particular, our results directly imply sublinear regret
rates for the Mat\'ern kernel, improving over the state-of-the-art analyses and
partially resolving a COLT open problem posed by Vakili et al. Our improvements
rely on two key technical results. First, we use modern supermartingale
techniques to construct a novel, self-normalized concentration inequality that
greatly simplifies existing approaches. Second, we address the importance of
regularizing in proportion to the smoothness of the underlying kernel $k$.
Together, these new technical tools enable a simplified, tighter analysis of
the GP-UCB algorithm.

本文解决了若干向来未解的开放性问题，提供了超线性收敛速度，证明了 GP-UCB 算法在大多数流行核函数上具有最优回报，且证明了简化版本的自标准化集中不等式和超鞅技术是关键技术工具。