Source-linked AI summary
Adaptation to Misspecified Kernel Regularity in Kernelised Bandits
Yusha Liu, Aarti Singh
TL;DR
Kernelised bandits face an open question: how well can algorithms adapt when the regularity of the underlying kernel is unknown? This paper studies translation-invariant kernels through Fourier-transform decay and proves an adaptivity lower bound. For Matérn kernels, CORRAL matches that bound in T-dependence except for log factors, connecting adaptivity difficulty across RKHS, Sobolev, and Hölder spaces.
Problem
It is unresolved how well kernelised bandit algorithms can adapt to unknown kernel regularity, which determines the statistical complexity of the associated learning problem.
Source: §1 · pp. 1–2Method
Results
No algorithm can simultaneously achieve minimax-optimal performance in RKHSs with different regularities; for Matérn kernels, CORRAL matches the lower bound in T-dependence except for log factors.
Source: §1 · p. 2Takeaways & Limitations
The results connect statistical adaptivity difficulty across RKHSs, Sobolev spaces, and Hölder spaces.
Source: §1 · p. 2The theoretical results are for one-dimensional domains and translation-invariant kernels, and the study leaves empirical investigation of kernel-regularity adaptivity open.
Source: §7 · p. 9
Abstract
from arXiv · showhide
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.
1 Introduction
This work studies whether kernelised bandit algorithms can adapt to unknown kernel regularity, which controls the complexity of the associated RKHS learning problem. It proves an adaptivity lower bound, shows CORRAL matches it for Matérn kernels up to log factors, and connects the difficulty to Sobolev and Hölder spaces.
1 Introduction
- Unknown function-space complexity makes exploration and exploitation difficult, and minimax adaptivity is not always achievable for cumulative regret.Prior work on simple-regret minimization shows minimax adaptivity can be possible.Source: §1 · p. 1
- Kernel regularity governs RKHS function differentiability and affects minimax regret rates through exponential dependence on T, unlike the polynomial effect of RKHS norm.The paper characterizes regularity by Fourier-transform decay.Source: §1 · p. 2
- No algorithm can simultaneously achieve minimax-optimal performance in RKHSs with different regularities, according to the first lower bound for adaptation to kernel regularity.Regularity is characterized by the decay rate of the kernel’s Fourier transform.Source: §1 · p. 2
- For Matérn kernels, CORRAL (Pacchiano et al., 2020b) with non-adaptive minimax kernelised bandit algorithms matches the lower bound in T-dependence, except for log factors.RBBE Pacchiano et al. (2020a) does not match the lower bound.Source: §1 · p. 2
- The paper connects adaptivity difficulty across RKHSs, Sobolev spaces, and Hölder spaces.These connections compare the statistical difficulty of adaptivity in three function-space settings.Source: §1 · p. 2
2 Related Work
Prior kernelised bandit analyses often assume the kernel and related parameters are known, while existing adaptive work addresses other kinds of misspecification or parameter uncertainty. This paper focuses on kernel regularity, whose effect on regret differs from parameters that affect only polynomial factors.
2 Related Work
- Most prior kernelised bandit methods assume the kernel and parameters such as the RKHS norm bound are known; SupKernelUCB is minimax optimal in T-dependence for common Matérn kernels, up to log factors.Its batching technique can make SupKernelUCB perform poorly in practice.Source: §2 · p. 3
- Prior adaptive kernelised bandit work addresses length scale and RKHS norm, epsilon-misspecification, unknown GP parameters, or meta-learned sparse combinations of known kernels.Meta-learning relies on offline tasks, whereas this paper considers fully online bandits.Source: §2 · p. 3
- Prior work on Hölder functions establishes that minimax adaptivity to the Hölder exponent is impossible, paralleling this paper’s RKHS regularity result.For epsilon-misspecification, a constant approximation error yields an unavoidable linear regret bound.Source: §2 · p. 3
- Earlier adaptive work considers parameters affecting regret in polynomial factors, whereas kernel regularity affects the rate in the exponent of T.Source: §2 · p. 3
- CORRAL corrals base algorithms as arms using online mirror descent, while RBBE adds base-algorithm elimination to a stochastic master algorithm.CORRAL can perform comparably to the best standalone base algorithm in certain cases.Source: §2 · p. 4
3 Problem Setting
The learner chooses points in a compact domain and receives noisy rewards from an unknown function, with performance measured by expected cumulative pseudo-regret. The setting restricts the reward function to a bounded-norm RKHS induced by a translation-invariant kernel, whose Fourier decay captures regularity.
3 Problem Setting
- At each time step, the learner selects an action in [0,1]^d and receives a noisy observation of the underlying reward function.The noise is zero-mean sub-Gaussian.Source: §3 · p. 4
- The objective is expected cumulative pseudo-regret, measured against the unknown global maximizer of the reward function.Source: §3 · p. 4
- The reward function lies in the RKHS of a symmetric positive-definite, translation-invariant kernel; its Fourier transform captures RKHS regularity.Translation invariance means the kernel depends on the difference between its two inputs.Source: §3 · p. 4
- The function’s RKHS norm is assumed bounded by B, defining an RKHS ball of radius B.Source: §3 · p. 4
4 Main Result: Adaptivity Lower Bound
The section establishes an impossibility lower bound for adapting to translation-invariant kernel regularity, measured by Fourier-decay rate, and connects it to Sobolev and Matérn settings. The proof uses RKHS–Sobolev norm equivalency, while the lower bound is stated for one dimension and its regret need not be linear in T.
4 Main Result: Adaptivity Lower Bound
- The main result uses Fourier-decay rate to express kernel regularity and relies on RKHS–Sobolev norm equivalency to establish the adaptivity lower bound.The section presents the lower bound as an impossibility result for simultaneously attaining minimax performance across RKHSs with different regularities.Source: §4 · p. 4, §4.2 · p. 5
4.1 Norm Equivalency Between RKHS and Sobolev Space
- For translation-invariant kernels with Fourier decay rate s, the associated RKHS is norm equivalent to the Sobolev space W^s(Ω).Under the stated conditions, the m-th Sobolev seminorm is bounded by the RKHS norm for a kernel with Fourier decay rate m.Source: §4.1 · p. 5
4.2 Lower Bound on Adaptivity to Kernel Regularity
- An algorithm achieving small regret on a smoother RKHS can incur larger, suboptimal regret on at least one function in a rougher RKHS; the lower-bound analysis considers d = 1.The regret lower bound is not necessarily linear in T because the smoother-space regret upper bound also depends on T.Source: §4.2 · p. 5
4.2.1 Proof Sketch
- The proof constructs compactly supported Sobolev hypothesis functions, then uses norm equivalency to place them in RKHS balls and derive the lower bound.The regret argument follows Hadiji (2019, Section 2.2): small regret on smoother functions entails disproportionately little exploration and larger regret on rougher functions.Source: §4.2.2 · p. 6, §4.2.1 · p. 6
4.2.2 A Sobolev Version of the Lower Bound
- The same adaptivity lower-bound structure holds for Sobolev spaces of different orders, connected to the RKHS result through norm equivalency.If an algorithm attains an upper bound in smoother W^m2(X), its regret over functions in rougher W^m1(X) is lower bounded.Source: §4.2.2 · p. 6
4.2.3 Impossibility Result for Matérn Kernels
- For Matérn kernels, Fourier decay is ν + d/2, so achieving minimax regret for ν2 does not yield minimax adaptivity to a rougher ν1 < ν2.The stated corollary assumes ν1, ν2 satisfy the supplied half-integer conditions; the resulting lower-bound rate is suboptimal relative to the minimax rate.Source: §4.2.3 · p. 6
5 Upper Bounds of Adaptive Algorithms
The section compares adaptive model-selection algorithms with minimax non-adaptive base learners for Matérn RKHSs. CORRAL matches the adaptivity lower bound in T-dependence up to log factors for certain regularity pairs; RBBE does not.
5 Upper Bounds of Adaptive Algorithms
- The adaptive algorithms require non-adaptive minimax-optimal base learners, and the section evaluates their regret guarantees for Matérn-ν kernels with d = 1.The setup is chosen to compare upper bounds with the adaptivity lower bound.Source: §5 · pp. 6–7
5.1.1 SupKernelUCB and GP-UCB for RKHS
- For Matérn RKHSs, SupKernelUCB matches the regret lower bound, while GP-UCB has a suboptimal theoretical upper bound.The comparison is under the RKHS assumption.Source: §5.1.1 · p. 7
5.1.2 UCB-Meta for H¨older Space
- UCB-Meta, designed for Hölder spaces, is also minimax optimal in T over Matérn RKHSs when ν + 1/2 is an integer.The stated result follows from the embedding of these RKHSs into a Hölder space with exponent α = ν.Source: §5.1.2 · p. 7, §5.1 · p. 7
5.2 CORRAL as Adaptive Algorithm
- The CORRAL guarantee assumes the true parameter is in the candidate set; if not, adaptation incurs an additional discretization cost.The candidate set specifies nested RKHSs.Source: §5.2 · p. 8
- CORRAL matches the adaptivity lower bound in T-dependence, up to log factors, for certain Matérn regularity pairs, whereas RBBE does not.The comparison assumes minimax non-adaptive base algorithms for CORRAL.Source: §5 · p. 7, §5.3 · p. 8, §5.2 · p. 8
5.3 RBBE as Adaptive Algorithm
- Both CORRAL and RBBE can achieve sublinear regret across different kernel regularities, but RBBE's upper bound misses the lower bound in the T exponent.CORRAL matches the lower bound only for certain pairs of Matérn regularities.Source: §5.3 · p. 8
6 Connection with Adaptivity to H¨older Exponents
The section connects adaptivity to kernel regularity in RKHSs with adaptivity to Hölder exponents. The connection holds when the Hölder spaces are the smallest ones containing the RKHSs.
6 Connection with Adaptivity to H¨older Exponents
- Prior Hölder-space results give an adaptivity lower bound for exponents α1 < α2 ≤ 1.The cited result concerns adaptation between two Hölder spaces.Source: §6 · p. 8
- The authors conjecture that RBBE's stochastic master limits its model-selection ability in some cases.This is presented as a conjecture, not an established explanation.Source: §6 · p. 8
- For continuum-armed bandits, adapting to RKHS kernel regularity has the same statistical difficulty as adapting to Hölder exponents when those are the smallest Hölder spaces containing the RKHSs.The section relates the spaces through Sobolev norm equivalence and Sobolev embedding.Source: §6 · p. 9
7 Discussion
The discussion identifies the one-dimensional domain as a current scope boundary and outlines extensions in dimension, kernel classes, and empirical study.
7 Discussion
- The theoretical results are currently for d = 1; extending them to d > 1 would require partitioning the hypercube into sub-cubes and constructing functions with corresponding Fourier decay.The authors note that such an extension may be possible along the lines of Scarlett et al. (2017).Source: §7 · p. 9
- The analysis covers translation-invariant kernels, leaving rotation-invariant kernels—including dot-product kernels used for NTKs—as a longer-term direction.The discussion cites Bietti and Bach (2020), Chen and Xu (2020), and Vakili et al. (2021a) in connection with NTKs.Source: §7 · p. 9
- The authors identify empirical study of adaptivity to kernel regularity as an open problem; their study is theoretical.They also call for Fourier-decay-based upper bounds and tests of lower-bound tightness beyond Matérn kernels.Source: §7 · p. 9
A.1 Proof of Norm Equivalency Between RKHS Norm and Sobolev Seminorm
This proof establishes the norm relationships needed to connect translation-invariant-kernel RKHSs with Sobolev spaces on the domain.
A.1 Proof of Norm Equivalency Between RKHS Norm and Sobolev Seminorm
- A translation-invariant kernel with Fourier decay rate s has an RKHS norm equivalent to the Sobolev W^{s,2}(Ω) norm on a Lipschitz domain Ω.The cited result is Wendland (2004, Theorem 10.12, Corollary 10.48).Source: §A.1 · p. 12
- On the interval X = [0, 1], the Sobolev seminorm is equivalent to the standard norm for functions in W^{m,p}_0(X).The argument invokes the finite-width result of Adams and Fournier (2003, 6.26) and the interval's Lipschitz boundary.Source: §A.1 · p. 12
- Combining Lemma 8 with the RKHS–Sobolev norm equivalence recovers the inequalities stated in Lemma 2.The section first sets out conditions for extending the equivalence to Sobolev seminorms.Source: §A.1 · p. 12
A.2 The Full Statement of Theorem 3
The appendix states the full conditions for the adaptivity lower bound and presents an RBBE regret bound adapted to the setting where candidate algorithms have different regret exponents.
A.2 The Full Statement of Theorem 3
- The theorem assumes 1/4-subgaussian noise and a finite upper bound γ0 on the functions' L2 norm.Its statement also introduces smoothness orders m2 > m1 and conditions on B1 and B2.Source: §A.2 · p. 12
- For any algorithm achieving the stated regret upper bound in RKHS ball H_km2(X, B2) with kernel decay rate m2, regret in the less-smooth ball induced by km1 with rate m1 is lower-bounded.The full version states constraints on radii B1 and B2; the proof is deferred to Appendix B.1.Source: §A.2 · p. 12
A.3 Adaptivity Upper Bound of RBBE
- RBBE eliminates base algorithms deemed misspecified, then selects among the remaining ones by presumed cumulative pseudo-regret; CORRAL instead uses an adversarial master algorithm.RBBE is described as using a stochastic master algorithm.Source: §A.3 · p. 13
- RBBE's play-ratio analysis is presented for base algorithms with a common T exponent, whereas this setting has exponents 2νi + 1 that vary with input νi.The proof is modified to handle this mismatch, and Theorem 10 states a high-probability regret bound for RBBE with the specified base algorithms.Source: §A.3 · p. 13
B.1 Proof of Theorem 9
The proof reduces the RKHS lower bound to a Sobolev-space argument, using constructed alternatives and a comparison of their induced observation distributions; it then applies the result to Matérn kernels.
B.1 Proof of Theorem 9
- The Sobolev version lower-bounds regret in the less-smooth ball when an algorithm has regret at most R̃ in the smoother ball, under the theorem's stated conditions.The setup assumes 1/4-subgaussian noise and an upper bound γ0 on function L2 norms; the RKHS result follows through norm equivalence and the parameter relationships in equation 31.Source: §B.1 · pp. 13, 17, 19
- The proof constructs alternatives by shifting a compactly supported, infinitely differentiable bump across bins, with the functions constrained to the respective Sobolev balls.The alternatives are arranged to have different peak locations while satisfying the stated membership conditions.Source: §B.1 · pp. 14, 17
- Pinsker's inequality relates the regret lower bounds through a comparison of trajectory distributions, with the KL bound relying on the alternatives' agreement outside their bins and the noise assumption.The proof sketch relates the regret on the alternatives to the assumed regret bound on the smoother-space function.Source: §B.1 · pp. 17–18
B.2 Proof of Corollary 5
- For d = 1, the Matérn regularity parameter ν maps to Fourier decay rate ν + 1/2, and the proof applies Theorem 3 using the corresponding decay orders.It then substitutes the regret rate to obtain a lower bound focused on its dependence on T.Source: §B.2 · p. 20
B.3 Proof of Theorem 6
The proof transfers UCB-Meta’s Hölder-space regret guarantee to Matérn-kernel RKHSs by embedding those RKHSs into Hölder spaces. The resulting rate on the Matérn RKHS is ~O(T^(2ν+1)).
B.3 Proof of Theorem 6
- UCB-Meta’s minimax regret guarantee for Hölder spaces is used to establish its minimax rate over certain Matérn RKHSs.The proof uses an RKHS-to-Hölder embedding to transfer the guarantee.Source: §B.3 · p. 20
- On X=[0,1], the proof obtains a Sobolev-to-Hölder embedding with exponent α=m−1/2 and combines it with RKHS–Sobolev norm equivalence.It applies the Sobolev embedding theorem with p=2 and d=1.Source: §B.3 · p. 20
- For translation-invariant kernels with polynomial Fourier decay, the Matérn RKHS embeds into the Hölder space with exponent α=ν.The stated relation uses Matérn regularity ν and Fourier decay rate s=ν+d/2.Source: §B.3 · p. 20
- ~O(T^(2ν+1)) is the regret rate UCB-Meta achieves on the Matérn-ν RKHS subset.The proof omits the RKHS norm bound because it affects only a multiplicative term, not the exponent of T.Source: §B.3 · p. 20
B.4 Proof of Theorem 7
The proof applies CORRAL with minimax kernelised-bandit algorithms as base learners to adapt to unknown Matérn regularity. It derives the resulting regret bound while accounting for the base algorithms’ parameter dependence and the need for anytime guarantees.
B.4 Proof of Theorem 7
- SupKernelUCB is used as the base algorithm because its regret bound explicitly depends on B, unlike UCB-Meta’s implicit dependence.The proof treats SupKernelUCB as minimax optimal after extending it to continuous actions by discretization and to anytime guarantees by doubling.Source: §B.4 · p. 21
- Improving the practical GP-UCB regret bound under RKHS assumptions remains an open problem.The passage frames the choice of SupKernelUCB as theoretical convenience.Source: §B.4 · p. 21
- CORRAL uses a user-specified regularity parameter because it does not know the true Matérn parameter ν* or norm bound B*.The learning rate η is chosen with respect to the specified parameter ν̃.Source: §B.4 · p. 21
- The proof derives the regret rate in equation 19 after absorbing the dependence on M and B into the tilde-O notation.The supplied passage does not state the rate’s full expression.Source: §B.4 · p. 21
B.5 Proof of Theorem 10
The proof adapts RBBE’s regret analysis to misspecified kernel-regularity base learners by bounding their play ratios. The resulting bound has distinct dominant terms for dependence on T and on the number and norm of the base learners.
B.5 Proof of Theorem 10
- For Matérn-kernel base learners, the analysis uses parameters βi and θi tied to each learner’s regularity and regret bound.The proof establishes bounds on the play ratios and then uses them to control terms #2 and #5.Source: §B.5 · pp. 22–23
- The proof bounds the play ratio between a misspecified base learner and a well-specified learner before applying RBBE’s general regret bound.It adapts the RBBE analysis and uses the resulting play-ratio bound in the regret calculation.Source: §B.5 · pp. 21–22
- Term #2 dominates the regret bound’s dependence on T, while term #5 dominates its dependence on |B| and B*.The proof derives rates for all five terms before identifying these dominant dependencies.Source: §B.5 · p. 23
- The candidate base-learner regret bounds have different exponents of T, so the more straightforward RBBE result cannot be applied directly.The proof instead follows the general RBBE bound involving play ratios.Source: §B.5 · pp. 22–23