# On the Sublinear Regret of GP-UCB

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 14 Jul 2023.

## Builds on (most cited first, 17 of 17)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015)
- [Collapsing Bandits and Their Application to Public Health Interventions](https://mlsanity.com/paper/2007.04432/) (2020)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Gaussian Process bandits with adaptive discretization](https://mlsanity.com/paper/1712.01447/) (2017)
- [Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS](https://mlsanity.com/paper/2005.04832/) (2020)
- [Streaming kernel regression with provably adaptive mean, variance, and regularization](https://mlsanity.com/paper/1708.00768/) (2017)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [Synthetically Controlled Bandits](https://mlsanity.com/paper/2202.07079/) (2022)
- [Instance-Dependent Regret Analysis of Kernelized Bandits](https://mlsanity.com/paper/2203.06297/) (2022)

## Built on by (most cited first, 26 of 26)

- [On Safety in Safe Bayesian Optimization](https://mlsanity.com/paper/2403.12948/) (2024)
- [Tighter Confidence Bounds for Sequential Kernel Regression](https://mlsanity.com/paper/2403.12732/) (2024)
- [Multi-Armed Bandits with Network Interference](https://mlsanity.com/paper/2405.18621/) (2024)
- [Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm](https://mlsanity.com/paper/2410.23498/) (2024)
- [Lower Bounds for Time-Varying Kernelized Bandits](https://mlsanity.com/paper/2410.16692/) (2024)
- [On the Suboptimality of GP-UCB under Polynomial Effective Optimism](https://mlsanity.com/paper/2312.01386/) (2023)
- [Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds](https://mlsanity.com/paper/2508.01681/) (2025)
- [No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/2510.20725/) (2025)
- [Vector-valued self-normalized concentration inequalities beyond sub-Gaussianity](https://mlsanity.com/paper/2511.03606/) (2025)
- [Differentially Private Kernelized Contextual Bandits](https://mlsanity.com/paper/2501.07046/) (2025)
- [Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2505.23673/) (2025)
- [Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning](https://mlsanity.com/paper/2406.15250/) (2024)
- [A variational approach to dimension-free self-normalized concentration](https://mlsanity.com/paper/2508.06483/) (2025)
- [No-Regret Algorithms for Safe Bayesian Optimization with Monotonicity Constraints](https://mlsanity.com/paper/2406.03264/) (2024)
- [Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning](https://mlsanity.com/paper/2502.07715/) (2025)
- [In-Context Reinforcement Learning through Bayesian Fusion of Context and Value Prior](https://mlsanity.com/paper/2601.03015/) (2026)
- [Safe Bayesian Optimization for Complex Control Systems via Additive Gaussian Processes](https://mlsanity.com/paper/2408.16307/) (2024)
- [Asymptotic Performance of Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2505.13012/) (2025)
- [Kernel conditional tests from learning-theoretic bounds](https://mlsanity.com/paper/2506.03898/) (2025)
- [Symmetry-Aware Bayesian Optimization via Max Kernels](https://mlsanity.com/paper/2509.25051/) (2025)
- [Practical Global and Local Bounds in Gaussian Process Regression via Chaining](https://mlsanity.com/paper/2511.09144/) (2025)
- [A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback](https://mlsanity.com/paper/2604.25025/) (2026)
- [Sharper Guarantees for Misspecified Kernelized Bandit Optimization](https://mlsanity.com/paper/2605.05967/) (2026)
- [Regret-Based (ε,δ)-optimal Stopping Criteria for Bayesian Optimization](https://mlsanity.com/paper/2605.22561/) (2026)
- [Learning Kernel-Based MDPs from Episodic Preferential Feedback](https://mlsanity.com/paper/2605.23650/) (2026)
- [Exploration strategies for Gaussian process bandit optimization with inference regret guarantees](https://mlsanity.com/paper/2610.16187/) (2026)

## Abstract (arXiv)

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 yield 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 a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel k. Applying this key idea together with a largely overlooked concentration result in separable Hilbert spaces (for which we provide an independent, simplified derivation), we are able to provide a tighter analysis of the GP-UCB algorithm.