# Open Problem: Tight Online Confidence Intervals for RKHS Elements

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 25 references that are in the map.
- First posted on arXiv 28 Oct 2021.

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

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Scalable Thompson Sampling using Sparse Gaussian Process Models](https://mlsanity.com/paper/2006.05356/) (2020)
- [Corruption-Tolerant Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2003.01971/) (2020)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [Regret bounds for meta Bayesian optimization with an unknown Gaussian process prior](https://mlsanity.com/paper/1811.09558/) (2018)
- [On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2008.08757/) (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)

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

- [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)
- [Delayed Feedback in Kernel Bandits](https://mlsanity.com/paper/2302.00392/) (2023)
- [Sample Complexity of Kernel-Based Q-Learning](https://mlsanity.com/paper/2302.00727/) (2023)
- [Provably and Practically Efficient Neural Contextual Bandits](https://mlsanity.com/paper/2206.00099/) (2022)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)
- [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)
- [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)
- [Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability](https://mlsanity.com/paper/2512.20368/) (2025)
- [Kernel ε-Greedy for Multi-Armed Bandits with Covariates](https://mlsanity.com/paper/2306.17329/) (2023)

## Abstract (arXiv)

Confidence intervals are a crucial building block in the analysis of various online learning problems. The analysis of kernel based bandit and reinforcement learning problems utilize confidence intervals applicable to the elements of a reproducing kernel Hilbert space (RKHS). However, the existing confidence bounds do not appear to be tight, resulting in suboptimal regret bounds. In fact, the existing regret bounds for several kernelized bandit algorithms (e.g., GP-UCB, GP-TS, and their variants) may fail to even be sublinear. It is unclear whether the suboptimal regret bound is a fundamental shortcoming of these algorithms or an artifact of the proof, and the main challenge seems to stem from the online (sequential) nature of the observation points. We formalize the question of online confidence intervals in the RKHS setting and overview the existing results.