  We consider the problem of optimising functions in the reproducing kernel
Hilbert space (RKHS) of a Mat\'ern kernel with smoothness parameter $\nu$ over
the domain $[0,1]^d$ under noisy bandit feedback. Our contribution, the
$\pi$-GP-UCB algorithm, is the first practical approach with guaranteed
sublinear regret for all $\nu>1$ and $d \geq 1$. Empirical validation suggests
better performance and drastically improved computational scalablity compared
with its predecessor, Improved GP-UCB.
