mlsanityData to 7 Oct 2026

Sharper Guarantees for Misspecified Kernelized Bandit Optimization

arXiv 2605.05967 ↗First posted 7 May 2026cs.LG math.OC stat.MLcited by 0

Not on the map. Why?

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.

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

Builds on

21 of 32 references.

References · 21

  1. 2017On Kernelized Multi-armed Banditscited by 348
  2. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  3. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  4. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  5. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  6. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  7. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  8. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  9. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  10. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  11. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 38
  12. 2017Spectral Mixture Kernels for Multi-Output Gaussian Processescited by 29
9 more
  1. 2020Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programmingcited by 28
  2. 2023On the Sublinear Regret of GP-UCBcited by 25
  3. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  4. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 16
  5. 2018Online learning with kernel lossescited by 12
  6. 2024Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPscited by 4
  7. 2023Does Sparsity Help in Learning Misspecified Linear Bandits?cited by 3
  8. 2020On the Estimation of Derivatives Using Plug-in Kernel Ridge Regression Estimatorscited by 2
  9. 2025Robust Bayesian Optimisation with Unbounded Corruptionscited by 1

Built on by

Not cited yet.