Universal Regret Lower Bounds for Kernel Bandits: A Near-Optimality Theoretical Breakthrough

Background: Kernel Bandits and Regret Analysis

The Kernel Bandit problem is one of the central problems in sequential decision-making and Bayesian optimization. It studies how to iteratively optimize an unknown function — with bounded norm in a given Reproducing Kernel Hilbert Space (RKHS) — under noisy feedback. This class of problems has broad applications in hyperparameter tuning, experimental design, and recommendation systems, since real-world objective functions are often not directly observable and can only be approximated through a limited number of noisy queries.

A key quantity in regret analysis for such algorithms is the maximum information gain $\gamma_T$. It characterizes the upper limit on how much information an algorithm can gather about the unknown function through $T$ rounds of interaction. In many ways, $\gamma_T$ nearly determines the fundamental difficulty of the kernel bandit problem.

Reproducing Kernel Hilbert Spaces (RKHS) form the mathematical foundation of kernel bandits. Intuitively, an RKHS is a function space induced by a kernel $k(x, x')$, where the "smoothness" of each function can be measured by its norm $|f|_k$. The choice of kernel determines the shape of the function space: the squared exponential kernel corresponds to infinitely smooth function classes, while the Matérn-$\nu$ kernel corresponds to $\nu$-times differentiable function classes — the smaller $\nu$ is, the "rougher" the function class. Kernel bandits assume the target function $f$ satisfies $|f|_k \leq B$, a prior constraint on function complexity that is also the fundamental reason algorithms can learn from limited observations.

Regret measures the cumulative loss of an algorithm over $T$ rounds of interaction: $R_T = \sum_{t=1}^T [f(x^) - f(x_t)]$, where $x^$ is the global optimum and $x_t$ is the algorithm's query point at round $t$. The goal of minimax regret analysis is to determine: in the worst case, how much regret must any algorithm necessarily incur? This is precisely the significance of lower bound research.

The Gap in Existing Theory

The best known regret upper bounds, ignoring logarithmic factors, scale as $\sqrt{T\gamma_T}$. For certain specific kernels — such as the squared exponential and Matérn kernels — researchers have derived lower bounds that nearly match the upper bounds, establishing near-optimality in those specific settings.

However, the problem is this: a lower bound for general kernels has been missing. This means the community has been unable to determine the extent to which those elegant $\sqrt{T\gamma_T}$ upper bounds are near-optimal in any general sense. In other words, while the theory is complete for certain specific kernels, an unknown gap between upper and lower bounds may exist for broader kernel classes. This gap has limited our overall understanding of the fundamental difficulty of kernel bandit problems.

The maximum information gain $\gamma_T$ is formally defined as the maximum mutual information obtainable when selecting $T$ points from a Gaussian process with kernel $k$: $\gamma_T = \max_{A \subset \mathcal{X}, |A|=T} I(y_A; f_A)$. It essentially characterizes the "learnability" of the kernel-induced function space under $T$ observations. The growth rate of $\gamma_T$ varies dramatically across kernels: for the squared exponential kernel, $\gamma_T = O((\log T)^{d+1})$, growing extremely slowly; for the Matérn-$\nu$ kernel, $\gamma_T = \Theta(T^{d/(2\nu+d)})$, growing polynomially in $T$, faster as $\nu$ decreases. This difference directly drives the enormous variation in difficulty across kernel bandit problems, which is precisely why $\gamma_T$ is called the "central quantity" for measuring problem hardness.

Core Contribution: A Universal Lower Bound

This paper fills the aforementioned theoretical gap. For non-constant continuous kernels on compact domains, the authors establish a universal minimax regret lower bound:

$$\Omega\left(\sqrt{T\gamma_T / \log T}\right)$$

This result proves, in a broadly general sense, that existing upper bounds are near-optimal up to logarithmic factors. Its value lies not in targeting any specific kernel, but in its universality — as long as the mild conditions of "compact domain," "non-constant," and "continuous" are satisfied, the lower bound holds.

A Two-Sided Interpretation of the Logarithmic Factor

The paper further investigates the nature of the $\log T$ factor appearing in the lower bound, arriving at an illuminating conclusion:

• In the general case, this logarithmic factor is unavoidable. That is, it is not an artifact of the proof technique, but an intrinsic part of the problem's hardness.
• But under certain specific conditions, it can be removed. This means that for kernels satisfying these conditions, the upper and lower bounds can be matched more tightly.

This layered characterization — "unavoidable in general, removable in special cases" — yields a more refined description of kernel-dependent problem hardness.

Minimax lower bound proofs typically employ a "hard instance construction" strategy: carefully constructing a family of hard-to-distinguish functions within the hypothesis space, such that any algorithm inevitably accumulates a certain amount of regret on this family. For kernel bandits, the challenge lies in constructing hard instances within the RKHS ball that are tightly coupled to the geometric structure of the kernel — which is precisely the technical reason universal lower bounds have been difficult to establish. For specific kernels (such as the Matérn kernel), researchers can exploit the concrete spectral properties of that kernel to construct instances; for general kernels, a more abstract construction framework is needed. The paper's technical breakthrough lies here: the authors found a unified construction method that relies only on the mild condition of "continuous and non-constant," allowing the lower bound to hold across specific kernel boundaries.

Exact Optimal Scaling Results

The most striking corollary of the paper is that for several important kernel classes, the minimax optimal rate is precisely determined to be $\Theta(\sqrt{T\gamma_T})$ — meaning the upper and lower bounds match within constant factors, rather than merely logarithmic factors. These kernels include:

• Matérn-$\nu$ kernels with $\nu \in (0, 2)$
• $\gamma$-exponential kernels with $\gamma \in (0, 2)$
• Certain piecewise polynomial kernels

For these kernels, the hardness of the kernel bandit problem is fully characterized. This is a strong result: in algorithm theory, matching upper and lower bounds to within constant factors is uncommon — typically only logarithmic-factor matching is achievable.

Significance and Impact

From a theoretical perspective, this work advances the regret analysis of kernel bandits from the "specific kernel" level to the "general kernel" level. It not only answers the long-standing open question of whether existing upper bounds are near-optimal, but also reveals the intrinsic structure of problem hardness through a refined analysis of the logarithmic factor.

For researchers working in Bayesian optimization, online learning, and sequential decision-making, this universal lower bound provides a clear theoretical benchmark: the regret of any new algorithm cannot break through the $\Omega(\sqrt{T\gamma_T/\log T})$ barrier. This both delineates the boundary for algorithm design and provides a unified reference frame for evaluating the optimality of existing algorithms.

Of course, the paper's conclusions rest on rigorous mathematical assumptions (compact domains, continuous non-constant kernels, etc.), and their value is primarily theoretical. For practical applications, these results offer more of a confidence that "existing methods are already close to the theoretical limit" rather than direct engineering improvements.