# Bandit optimisation of functions in the Mat'ern kernel RKHS

arXiv: https://arxiv.org/abs/2001.10396 · HTML: https://mlsanity.com/paper/2001.10396/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2020.

## Built on by (most cited first, 30 of 40)

- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage](https://mlsanity.com/paper/2106.03207/) (2021)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2302.01511/) (2023)
- [Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2311.03760/) (2023)
- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [Lenient Regret and Good-Action Identification in Gaussian Process Bandits](https://mlsanity.com/paper/2102.05793/) (2021)
- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)
- [Tighter Confidence Bounds for Sequential Kernel Regression](https://mlsanity.com/paper/2403.12732/) (2024)
- [Instance-Dependent Regret Analysis of Kernelized Bandits](https://mlsanity.com/paper/2203.06297/) (2022)
- [Adaptation to Misspecified Kernel Regularity in Kernelised Bandits](https://mlsanity.com/paper/2304.13830/) (2023)
- [On the Suboptimality of GP-UCB under Polynomial Effective Optimism](https://mlsanity.com/paper/2312.01386/) (2023)
- [Regret Analysis for Randomized Gaussian Process Upper Confidence Bound](https://mlsanity.com/paper/2409.00979/) (2024)
- [Sample-efficient Bayesian Optimisation Using Known Invariances](https://mlsanity.com/paper/2410.16972/) (2024)
- [Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs](https://mlsanity.com/paper/2410.24071/) (2024)
- [Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2507.09828/) (2025)
- [Bayesian Optimistic Optimisation with Exponentially Decaying Regret](https://mlsanity.com/paper/2105.04332/) (2021)
- [On Average-Case Error Bounds for Kernel-Based Bayesian Quadrature](https://mlsanity.com/paper/2202.10615/) (2022)
- [(Private) Kernelized Bandits with Distributed Biased Feedback](https://mlsanity.com/paper/2301.12061/) (2023)
- [On Regret Bounds of Thompson Sampling for Bayesian Optimization](https://mlsanity.com/paper/2603.09276/) (2026)
- [Batched Kernelized Bandits: Refinements and Extensions](https://mlsanity.com/paper/2603.12627/) (2026)
- [Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2608.16492/) (2026)
- [High-Dimensional Simulation Optimization via Brownian Fields and Sparse Grids](https://mlsanity.com/paper/2107.08595/) (2021)
- [Dual Instrumental Method for Confounded Kernelized Bandits](https://mlsanity.com/paper/2209.03224/) (2022)

## Abstract (arXiv)

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 π-GP-UCB algorithm, is the first practical approach with guaranteed sublinear regret for all nu>1 and d ≥ 1. Empirical validation suggests better performance and drastically improved computational scalablity compared with its predecessor, Improved GP-UCB.