# Consequences of Kernel Regularity for Bandit Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 5 Dec 2025.

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

- [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)
- [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)
- [A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance](https://mlsanity.com/paper/2010.13997/) (2020)
- [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)
- [Smooth Bandit Optimization: Generalization to H"older Space](https://mlsanity.com/paper/2012.06076/) (2020)
- [Continuum-Armed Bandits: A Function Space Perspective](https://mlsanity.com/paper/2010.08007/) (2020)
- [Adaptation to Misspecified Kernel Regularity in Kernelised Bandits](https://mlsanity.com/paper/2304.13830/) (2023)

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

- [Open-Ended Task Discovery via Bayesian Optimization](https://mlsanity.com/paper/2605.07572/) (2026)
- [A General widetildeOmega(√T γT) Lower Bound for Kernel Bandits](https://mlsanity.com/paper/2610.11082/) (2026)

## Abstract (arXiv)

In this work we investigate the relationship between kernel regularity and algorithmic performance in the bandit optimization of RKHS functions. While reproducing kernel Hilbert space (RKHS) methods traditionally rely on global kernel regressors, it is also common to use a smoothness-based approach that exploits local approximations. We show that these perspectives are deeply connected through the spectral properties of isotropic kernels. In particular, we characterize the Fourier spectra of the Mat'ern, square-exponential, rational-quadratic, γ-exponential, piecewise-polynomial, and Dirichlet kernels, and show that the decay rate determines asymptotic regret from both viewpoints. For kernelized bandit algorithms, spectral decay yields upper bounds on the maximum information gain, governing worst-case regret, while for smoothness-based methods, the same decay rates establish H"older space embeddings and Besov space norm-equivalences, enabling local continuity analysis. These connections show that kernel-based and locally adaptive algorithms can be analyzed within a unified framework. This allows us to derive explicit regret bounds for each kernel family, obtaining novel results in several cases and providing improved analysis for others. Furthermore, we analyze LP-GP-UCB, an algorithm that combines both approaches, augmenting global Gaussian process surrogates with local polynomial estimators. While the hybrid approach does not uniformly dominate specialized methods, it achieves order-optimality across multiple kernel families.