mlsanityData to 7 Oct 2026

Adaptation to Misspecified Kernel Regularity in Kernelised Bandits

arXiv 2304.13830 ↗First posted 26 Apr 2023stat.ML cs.LG stat.MEcited by 5

Not on the map. Why?

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.

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

Builds on

29 of 52 references.

References · 29

  1. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  2. 2018On Lazy Training in Differentiable Programmingcited by 671
  3. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  4. 2017On Kernelized Multi-armed Banditscited by 348
  5. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  6. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  7. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  8. 2016Corralling a Band of Bandit Algorithmscited by 99
  9. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 83
  10. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  11. 2020Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHScited by 74
  12. 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
17 more
  1. 2019Model selection for contextual banditscited by 60
  2. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  3. 2019No-Regret Bayesian Optimization with Unknown Hyperparameterscited by 50
  4. 2020Regret Bound Balancing and Elimination for Model Selection in Bandits and RLcited by 45
  5. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  6. 2021Neural Contextual Bandits without Regretcited by 40
  7. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 29
  8. 2020Corralling Stochastic Bandit Algorithmscited by 23
  9. 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
  10. 2020Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHScited by 16
  11. 2018Optimization of Smooth Functions with Noisy Observations: Local Minimax Ratescited by 14
  12. 2021Pareto Optimal Model Selection in Linear Banditscited by 14
  13. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
  14. 2020Uncertainty quantification using martingales for misspecified Gaussian processescited by 12
  15. 2020Smooth Bandit Optimization: Generalization to H"older Spacecited by 10
  16. 2019Polynomial Cost of Adaptation for X -Armed Banditscited by 9
  17. 2020Continuum-Armed Bandits: A Function Space Perspectivecited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 1; 2025: 1; 2026: 2.

5 papers.

  1. 2024Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimalcited by 6
  2. 2025Consequences of Kernel Regularity for Bandit Optimizationcited by 1
  3. 2023Kernel ε-Greedy for Multi-Armed Bandits with Covariatescited by 0
  4. 2026Online Sharp-Calibrated Bayesian Optimizationcited by 0
  5. 2026No-Regret Bayesian Optimization with Finite-Library Input-Warped Kernelscited by 0