# Sharper Guarantees for Misspecified Kernelized Bandit Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 32 references that are in the map.
- First posted on arXiv 7 May 2026.

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

- [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)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [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)
- [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)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (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)
- [A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance](https://mlsanity.com/paper/2010.13997/) (2020)
- [Spectral Mixture Kernels for Multi-Output Gaussian Processes](https://mlsanity.com/paper/1709.01298/) (2017)
- [Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programming](https://mlsanity.com/paper/2004.11408/) (2020)
- [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)
- [Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency](https://mlsanity.com/paper/2310.15351/) (2023)
- [Online learning with kernel losses](https://mlsanity.com/paper/1802.09732/) (2018)
- [Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs](https://mlsanity.com/paper/2410.24071/) (2024)
- [Does Sparsity Help in Learning Misspecified Linear Bandits?](https://mlsanity.com/paper/2303.16998/) (2023)
- [On the Estimation of Derivatives Using Plug-in Kernel Ridge Regression Estimators](https://mlsanity.com/paper/2006.01350/) (2020)
- [Robust Bayesian Optimisation with Unbounded Corruptions](https://mlsanity.com/paper/2511.15315/) (2025)

## Abstract (arXiv)

Existing guarantees for misspecified kernelized bandit optimization pay for misspecification through kernel complexity: in generic offline bounds, the misspecification level varepsilon is multiplied by √deff, where deff is the kernel effective dimension, while in online regret bounds, the corresponding penalty is √γn,nvarepsilon, where γn is the maximum information gain after n rounds of interaction. In this work, we show that, for a large class of kernels, the misspecification amplification can be reduced to logarithmic or polylogarithmic growth. In the offline setting, we first prove high-probability simple-regret bounds whose misspecification term is governed by a spectral Lebesgue constant. This yields logarithmic amplification for one-dimensional monotone spectra and polylogarithmic amplification for multivariate Fourier-diagonal product kernels. In the online setting, we modify a domain-splitting algorithm and prove a cumulative regret bound of widetildemathcal O(√γn n+nvarepsilon) under mild localized eigendecay assumptions, removing the extra √γn factor from the misspecification term. The common principle is localization: spectral localization controls the Lebesgue constant of the offline approximation operator, while domain splitting implements the spatial analogue of this mechanism in the online setting, preventing local misspecification errors from being amplified globally.