# Adaptation to Misspecified Kernel Regularity in Kernelised Bandits

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 52 references that are in the map.
- First posted on arXiv 26 Apr 2023.

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

- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2008.08757/) (2020)
- [Corralling Stochastic Bandit Algorithms](https://mlsanity.com/paper/2006.09255/) (2020)
- [Uniform Generalization Bounds for Overparameterized Neural Networks](https://mlsanity.com/paper/2109.06099/) (2021)
- [Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS](https://mlsanity.com/paper/2005.04832/) (2020)
- [Optimization of Smooth Functions with Noisy Observations: Local Minimax Rates](https://mlsanity.com/paper/1803.08586/) (2018)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [Uncertainty quantification using martingales for misspecified Gaussian processes](https://mlsanity.com/paper/2006.07368/) (2020)
- [Smooth Bandit Optimization: Generalization to H"older Space](https://mlsanity.com/paper/2012.06076/) (2020)
- [Polynomial Cost of Adaptation for X -Armed Bandits](https://mlsanity.com/paper/1905.10221/) (2019)
- [Continuum-Armed Bandits: A Function Space Perspective](https://mlsanity.com/paper/2010.08007/) (2020)

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

- [Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal](https://mlsanity.com/paper/2410.10384/) (2024)
- [Consequences of Kernel Regularity for Bandit Optimization](https://mlsanity.com/paper/2512.05957/) (2025)
- [Kernel ε-Greedy for Multi-Armed Bandits with Covariates](https://mlsanity.com/paper/2306.17329/) (2023)
- [Online Sharp-Calibrated Bayesian Optimization](https://mlsanity.com/paper/2605.10572/) (2026)
- [No-Regret Bayesian Optimization with Finite-Library Input-Warped Kernels](https://mlsanity.com/paper/2609.02993/) (2026)

## Abstract (arXiv)

In continuum-armed bandit problems where the underlying function resides in a reproducing kernel Hilbert space (RKHS), namely, the kernelised bandit problems, an important open problem remains of how well learning algorithms can adapt if the regularity of the associated kernel function is unknown. In this work, we study adaptivity to the regularity of translation-invariant kernels, which is characterized by the decay rate of the Fourier transformation of the kernel, in the bandit setting. We derive an adaptivity lower bound, proving that it is impossible to simultaneously achieve optimal cumulative regret in a pair of RKHSs with different regularities. To verify the tightness of this lower bound, we show that an existing bandit model selection algorithm applied with minimax non-adaptive kernelised bandit algorithms matches the lower bound in dependence of T, the total number of steps, except for log factors. By filling in the regret bounds for adaptivity between RKHSs, we connect the statistical difficulty for adaptivity in continuum-armed bandits in three fundamental types of function spaces: RKHS, Sobolev space, and H"older space.