Bandit optimisation of functions in the Matérn kernel RKHS

Abstract

We consider the problem of optimising functions in the reproducing kernel Hilbert space (RKHS) of a Matérn 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\ge 1$. Empirical validation suggests better performance and drastically improved computational scalablity compared with its predecessor, Improved GP-UCB.

arXiv commentIncluded an errata highlighting an omission in the proof of lemma 1 and pointing to a fix in the author's thesis; the omission does not affect the main result

References in corpus (1)

• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Cited by in corpus (7)

• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• Kernel Methods for Cooperative Multi-Agent Contextual Bandits
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Optimal Order Simple Regret for Gaussian Process Bandits
• Approximation Theory Based Methods for RKHS Bandits