  Confidence bounds are an essential tool for rigorously quantifying the
uncertainty of predictions. In this capacity, they can inform the
exploration-exploitation trade-off and form a core component in many sequential
learning and decision-making algorithms. Tighter confidence bounds give rise to
algorithms with better empirical performance and better performance guarantees.
In this work, we use martingale tail bounds and finite-dimensional
reformulations of infinite-dimensional convex programs to establish new
confidence bounds for sequential kernel regression. We prove that our new
confidence bounds are always tighter than existing ones in this setting. We
apply our confidence bounds to the kernel bandit problem, where future actions
depend on the previous history. When our confidence bounds replace existing
ones, the KernelUCB (GP-UCB) algorithm has better empirical performance, a
matching worst-case performance guarantee and comparable computational cost.
Our new confidence bounds can be used as a generic tool to design improved
algorithms for other kernelised learning and decision-making problems.
