mlsanityData to 14 Oct 2026

Open Problem: Tight Online Confidence Intervals for RKHS Elements

arXiv 2110.15458 ↗First posted 28 Oct 2021stat.ML cs.LG math.STcited by 13

Not on the map. Why?

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.

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

17 of 25 references.

References · 17

  1. 2017On Kernelized Multi-armed Banditscited by 352
  2. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 192
  3. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  4. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  5. 2020Neural Thompson Samplingcited by 128
  6. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  7. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  8. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  9. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  10. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  11. 2020Scalable Thompson Sampling using Sparse Gaussian Process Modelscited by 39
  12. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
5 more
  1. 2014Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameterscited by 31
  2. 2018Regret bounds for meta Bayesian optimization with an unknown Gaussian process priorcited by 31
  3. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 31
  4. 2017Gaussian Process bandits with adaptive discretizationcited by 21
  5. 2020Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHScited by 16

Built on by

Cited by year

Citing papers per year: 2022: 4; 2023: 7; 2024: 1; 2025: 1.

13 papers.

Sort:

  1. 2023On the Sublinear Regret of GP-UCBcited by 26
  2. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  3. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  4. 2023Delayed Feedback in Kernel Banditscited by 10
  5. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  6. 2022Provably and Practically Efficient Neural Contextual Banditscited by 6
  7. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
  8. 2022Instance-Dependent Regret Analysis of Kernelized Banditscited by 5
  9. 2023Adaptation to Misspecified Kernel Regularity in Kernelised Banditscited by 5
  10. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  11. 2023On the Suboptimality of GP-UCB under Polynomial Effective Optimismcited by 4
  12. 2025Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stabilitycited by 2
1 more
  1. 2023Kernel ε-Greedy for Multi-Armed Bandits with Covariatescited by 0