A General Ω̃(√(T γT)) Lower Bound for Kernel Bandits
Abstract
The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain γT. In particular, the best existing upper bounds scale as √(TγT) up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general Ω(√(TγT/log T)) minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly Θ(√(TγT)) (i.e., within constant factors) for the Matérn-ν kernel with ν∈ (0,2), γ-exponential kernel with γ∈ (0,2), and certain piecewise-polynomial kernels.
Related
- A Multidimensional Hilbert-Type Integral Inequality with the General Nonhomogeneous Kernel and Multiple Lower Limit Function
- Risk-Sensitive Non-Parametric and Kernel Bandits
- Follow the Perturbed Leader for Linear Bandits: √T Regret over General Action Sets
- A sharp bound for sampling widths in the uniform norm: kernel D-optimal designs and oversampling
- An explicit lower bound for the unit distance problem
BibTeX
@misc{ma2026general,
title = {{A General $\widetildeΩ(\sqrtT γ_T)$ Lower Bound for Kernel Bandits}},
author = {Chenkai Ma and Jonathan Scarlett},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11082},
eprint = {2610.11082},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11082},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A General Ω̃(√(T γ_T)) Lower Bound for Kernel Bandits
AU - Chenkai Ma
AU - Jonathan Scarlett
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11082
UR - https://arxiv.org/abs/2610.11082
AB - The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain γ_T. In particular, the best existing upper bounds scale as √(Tγ_T) up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general Ω(√(Tγ_T/log T)) minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly Θ(√(Tγ_T)) (i.e., within constant factors) for the Matérn-ν kernel with ν∈ (0,2), γ-exponential kernel with γ∈ (0,2), and certain piecewise-polynomial kernels.
ER -