WorksMathematics
Tight Sequential Confidence Intervals for Online Kernel Regression
Abstract
We characterize, in the worst case over kernels, the sharp minimax width of online confidence intervals for elements of a reproducing kernel Hilbert space (RKHS). This resolves the open problem posed by Vakili et al. (2021) in its original discrete-time form. A learner observes at adaptively chosen points, with and i.i.d. -sub-Gaussian noise, and reports the interval , where and are the posterior mean and standard deviation of a surrogate Gaussian process model with regularization parameter . Writing for the minimax confidence width for a fixed kernel, we show that, for the sum of a linear kernel and a periodic Sobolev kernel, all sufficiently large , and all , , where is the maximal information gain and grows polynomially in . Building on Lattimore (2023), we construct an adaptive design on a fixed two-dimensional domain for which, under Gaussian noise, the normalized error at a prespecified point is with constant probability. This rules out the conjectured polylogarithmic width in the worst case over kernels and online designs.
Introduction
Kernel methods extend linear models to rich nonlinear function classes, and a large body of work studies online learning problems in which the unknown objective lies in a reproducing kernel Hilbert space (RKHS). Two prominent applications are kernelized bandits [44, 52, 7, 41, 50] and kernel-based reinforcement learning [59, 48, 47, 18].
In kernelized bandits and kernel-based reinforcement learning, surrogate Gaussian process (GP) models are often used to construct confidence intervals.
We observe an unknown function on a compact domain through
where is a known kernel and the noise terms are i.i.d. -sub-Gaussian. The design is online, so may depend on the past observations . Following Vakili et al. [51], let and denote the posterior mean and standard deviation of a zero-mean surrogate GP with kernel and regularization parameter . We seek the smallest width such that, for every admissible , noise law, and online design, the following holds with probability at least .
For offline designs independent of the noise, standard confidence bounds have only logarithmic dependence on under suitable kernel regularity conditions ([49 c]). In the online setting, self-normalized concentration gives the width ([2, 1, 7, 11])
where is the maximal information gain after observations. For kernels with polynomially decaying eigenvalues, including Matérn kernels, can grow polynomially in , making this width substantially larger than its offline counterpart ([50, 26]).
Over rounds, the standard analysis of the Gaussian process upper confidence bound (GP-UCB) algorithm gives regret , which becomes under the existing confidence width ([44, 7]). SupKernelUCB achieves using offline confidence intervals ([52]). This gap motivates asking whether the term in online confidence widths is necessary.
Vakili et al. [51] asked whether the term in online confidence widths could be replaced by a term that is polylogarithmic in . The discrete-time lower bound for linear regression of Khamaru et al. [28] does not distinguish these rates, since grows only logarithmically in for fixed dimension. Lattimore [31] showed that this inflation is unavoidable in a continuous-time analogue, but explicitly mentioned that the corresponding discrete-time result remained unproved despite supporting simulations. Thus, the original question remained open for kernels with polynomially growing information gain:
What is the minimax optimal growth rate of the width with ? In particular, can the existing width be reduced by a factor of order , up to logarithmic factors?
We resolve this question in its original discrete-time model, in the worst case over kernels. For each smoothness scale , we construct the sum of a linear kernel and a periodic Sobolev kernel of order on the fixed domain . For and i.i.d. noise, we construct, for each , an online design such that, with probability at least ,
where is fixed before observing any data.
Let denote the minimax confidence width of (2), defined in § 3. Combining this construction with the existing upper bound and a Gaussian tail lower bound for a deterministic design yields, for all and ,
where all comparison constants depend only on .
Since our kernel has input dimension and polynomially growing information gain, the conjectured polylogarithmic width cannot hold for every kernel. Consequently, the gap in the standard GP-UCB regret analysis cannot be closed in general solely by tightening a confidence width that is valid for every kernel and online design and depends on the kernel only through and . Whether the dependence can be improved for Matérn or squared exponential kernels remains open.
Notation: We write and use for the cardinality of a finite set . For a vector , denotes its Euclidean norm. For a matrix , , , and denote its operator norm, Frobenius norm, and trace, respectively. For symmetric matrices, means that is positive semidefinite, and means that is positive definite. We use for the identity matrix, for the all-ones vector in , and for the Kronecker product. For and , denotes the principal submatrix with rows and columns indexed by . The notation denotes the Gaussian distribution with mean and variance , and denotes the standard Gaussian distribution on . We use and for the floor and ceiling functions, and for the imaginary unit. For nonnegative quantities , we write if and if , where depend at most on the smoothness parameter , unless stated otherwise. The symbols and have their usual asymptotic meanings as , and hides polylogarithmic factors.
Literature Review
Kernelized bandits and Gaussian process optimization. Srinivas et al. [44] expressed GP-UCB regret through maximal information gain, with subsequent RKHS and contextual extensions [7, 29]. Lower bounds were established for the squared exponential and Matérn kernels [41, 4]. More recently, Ma and Scarlett [34] prove an expected regret lower bound for nonconstant continuous kernels on compact domains under Gaussian noise.
For the Matérn family, domain partitioning [25] and horizon-dependent regularization [56] yield sublinear regret. GP-UCB also admits improved guarantees in noise-free RKHS models and in the Bayesian setting [24 a], while regret lower bounds are available for specific exploration and regularization schedules [55, 57].
Related questions arise in kernel-based reinforcement learning [59, 48, 47]. For Sobolev RKHS reward and transition-density models, Hu and Simchi-Levi [18] characterize the minimax expected regret as a function of the number of episodes.
Self-normalized concentration and online confidence intervals. Confidence intervals and high-probability bounds are fundamental tools in probability and statistics. These include time-uniform confidence sequences for sequential data [15, 39] and uniform or pointwise bounds for stochastic processes [46, 10, 58, 19]. For online regression, self-normalized martingale inequalities [8, 9] underpin confidence ellipsoids for linear bandits and their Hilbert-space extensions [2, 1]. They yield online confidence bounds with a dependence for kernel regression [7, 11, 56]. Recent work develops tighter kernel confidence bounds [12], dimension-free Bernstein-type inequalities [3], bounds without regularization penalties under additional covariate assumptions [6], and guarantees under kernel misspecification [35].
Maximal information gain. The maximal information gain was introduced by Srinivas et al. [44], with bounds for common kernels building on Seeger et al. [42]. Vakili et al. [50] bound it through the eigenvalue decay of the kernel, which gives for the Matérn- kernel, and Janz et al. [26] determine its sharp order, up to constant factors, for the Matérn and squared exponential kernels. More broadly, effective dimension and eigenvalue decay control regret bounds in kernelized contextual bandits and online decision-making with functional regression [52, 60, 36, 20]. For our constructed kernel, we obtain matching information-gain bounds using Hadamard’s inequality for the upper bound and the spectrum of a repeated equispaced design for the lower bound.
Alternative approaches to kernelized bandits. In kernelized bandits, SupKernelUCB, batched elimination, and domain shrinking use staged or batched data collection to apply offline confidence bounds [52, 33, 40]. Related approaches combine experimental design with robust estimation [5], or use response-independent variance maximization to achieve near-optimal simple regret [49]. More recently, Takeno et al. [45] use data thinning under Gaussian noise to separate adaptive sampling from confidence interval construction, achieving near-optimal cumulative regret through phased elimination. RKHS regression can also serve as an estimation oracle within broader sequential decision-making frameworks. Such oracle-based approaches reduce contextual bandits to regression [13, 43, 21] and reinforcement learning to regression [38] (Hu et al. 2026).
The open problem and its partial answers. Vakili et al. [51] posed the question of tight online confidence intervals for RKHS elements. Lattimore [31] resolved its continuous-time version, with a lower bound for a direction that is not the feature vector of any point of the domain and on a domain that grows with , and left the discrete-time problem open. Khamaru et al. [28] carried out the discretization in finite dimension, where and the rate coincide. On the regret side, Whitehouse et al. [56], who describe their result as a partial resolution of the open problem, show that GP-UCB attains sublinear regret for the Matérn family when the regularization parameter grows with the horizon. Our analysis establishes a discrete-time lower bound at a prespecified point of a fixed compact domain for a kernel with polynomially growing information gain. Together with the existing upper bound, this yields the sharp minimax characterization in Corollary 4.3.
Preliminaries
In this section, we formalize the statistical model and the criterion used throughout the paper. We first recall the RKHS model and the online design protocol, following the notation of Vakili et al. [51]. We then describe the surrogate GP model and the form of the confidence intervals, state the existing upper bound, and finally define the minimax confidence width.
Reproducing kernel Hilbert spaces. Let be a compact set and let be a continuous positive definite kernel. Let denote the RKHS corresponding to , defined as the Hilbert space of functions on equipped with an inner product that satisfies
The second identity is the reproducing property. In particular, we have . Let and denote the Mercer eigenvalues and eigenfeatures of with respect to a finite Borel measure whose support is . By Mercer’s representation theorem [27], every can be written as
so the decay of the eigenvalues measures the size of the function class. We use two examples below. The linear kernel has at most nonzero eigenvalues, and its RKHS consists of linear functions. A kernel on the circle of the form , with and , has the trigonometric functions as eigenfeatures, and its eigenvalues are proportional to the weights , each with multiplicity two.
Observation model and online designs. A learner collects noisy observations of an unknown objective function , where
This is the standard observation model for kernelized bandits [44, 7]. Following Vakili et al. [51], we impose the following assumption.
Assumption 3.1. The RKHS norm of is bounded as , for some . Moreover, the noise terms are i.i.d. sub-Gaussian random variables, i.e., for some , for all and all $i\geq 1.
In online learning problems, as pointed out by Vakili et al. [51], the observation points are collected sequentially: the point is determined after all the values are revealed. This is in contrast to an offline design, where the points are fixed in advance.
Definition 3.2. (i) Online setting. Define the filtration
For each , is -measurable. The noise is -measurable and is independent of .
(ii) Offline setting. The design sequence is independent of the noise sequence .
We make two additions to part (i) explicit. First, we include the sigma algebra , which is needed for . Second, we state the independence of from , which is implicit in Vakili et al. [51]: it holds whenever is a measurable function of the past observations and of randomization that is independent of the noise. When only rounds are considered, we impose these conditions for . We refer to a sequence that satisfies part (i) as an online design.
Surrogate GP model
A standard approach in kernelized regression employs a zero-mean surrogate GP model with covariance kernel , using its posterior mean to estimate and its posterior standard deviation to quantify uncertainty ([44, 7, 49]). GP model with kernel provides a surrogate posterior mean and a surrogate posterior variance . It is well known that
where , is the kernel matrix , , and is a regularization parameter. denotes the vector of observations. The posterior mean coincides with the kernel ridge regression estimate with penalty . The GP model is only a surrogate: the objective function is a fixed element of , and the noise need not be Gaussian.
Confidence intervals and the existing bound
A confidence interval for takes the form
and we refer to as its width.
In the online setting, we use the maximal information gain
This quantity is closely related to the effective dimension of the kernel ([44, 52]). It is the normalized form of the definition in the open problem ([51]), since
The two definitions, therefore, have the same maximizing designs and agree in value when . For the linear kernel, we have , whereas can grow polynomially in for kernels whose Mercer eigenvalues decay polynomially ([50, 26]).
Several works study online confidence bounds for kernel regression ([1, 7, 51, 56]). We state the bound for any fixed in our notation.
Theorem 3.3 (Chowdhury and Gopalan [7]; Durand et al. [11]). Let be a continuous positive definite kernel on a compact set . Under Assumption 3.1, in the online design setting of Definition 3.2, for any , with probability at least $1-\deltan\geq 1
and all that
Theorem 3.3 holds for every kernel and every online design.
The minimax confidence width. To provide the minimax lower bound, we first define the notion of minimax confidence width. We call a pair , consisting of an objective function and a joint law of the design and the noise , an instance, and we write for the collection of all instances that satisfy Assumption 3.1 and the online design condition in Definition 3.2. We define the minimax confidence width by
The quantity depends on the kernel, the domain, and , which we suppress in the notation. The event in (8) is measurable, because , , and are continuous in and is separable. The supremum takes the worst-case failure probability over the objective function, the noise distribution, and the online design. The design may depend on , , , and . The outer infimum selects the smallest width with worst-case failure probability at most .
Theorem 3.3 gives
for every kernel and every . The open problem Vakili et al. [51] asks how grows with , and in particular whether the dependence can be improved.
The Sharp Minimax Confidence Width
In this section, we provide our theoretical guarantees on the sharp minimax confidence width. We first specify the kernel and the online design of the hard instance and establish a lower bound for online confidence intervals. Our additive Fourier kernel and adaptive sampling rule are partially motivated by the construction of Lattimore [31]. We then combine this result with the existing upper bound of Theorem 3.3 to obtain a sharp characterization of the minimax confidence width, and we record the resulting answer to the open problem.
The hard kernel. Fix a smoothness parameter . Define the -periodic function
Let for denote the Riemann zeta function. The weights are for , so .
Using the Fourier representation of periodic RKHS kernels in Krieg and Vybrál [30], we define the normalized periodic Sobolev kernel of order on by
The normalization gives . Under the uniform distribution on , the eigenfunctions are and for , each with eigenvalue . The associated RKHS is the mean-zero periodic Sobolev space of order [53, 30].
Our second kernel is the linear kernel on , given by
For the hard instance, we take the domain and combine the two kernels to obtain
The constructed kernel satisfies the following property.
Proposition 4.1. The kernel in (10) is continuous and positive definite, with . Under the uniform probability measure on , its nonzero Mercer eigenvalues consist of one copy of and two copies of for each . When listed in nonincreasing order with multiplicity, these eigenvalues satisfy .
The proof is given in Appendix § 7.
Data generation. Fix , set , and let . Before sampling, we fix the second coordinates by visiting equally spaced points in the same order for 20 passes, then using 0 for the remaining rounds.
From these coordinates, we form and compute the inverse and the factorization of the regularized kernel matrix.
where is unit lower triangular and is diagonal with positive entries. Set
The repeated visit to ensures , as shown in the proof of Theorem 4.2.
In round , take from (11) and choose using the past residuals , .
We then observe , where is independent of the past. We evaluate the confidence interval at the fixed point .
Theorem 4.2 (Lower bound for online confidence intervals). Fix and . Consider the kernel (10), the objective function , i.i.d. noise , and the online design (4.3–4.6). There exist constants depending only on and an integer such that, for every , with probability at least ,
Moreover, for every , the maximal information gain of the kernel (10) satisfies , with comparison constants depending only on .
Consequently, for every and , every deterministic width for which (5) holds for this instance satisfies
Combining the upper bound in Theorem 3.3 and the lower bound in Theorem 4.2 with a Gaussian tail lower bound for a deterministic design gives the sharp minimax confidence width.
Corollary 4.3 (Sharp minimax confidence width). Fix and , and consider the kernel (10). Let be as in Theorem 4.2. For all , , and , we have
with comparison constants depending only on .
For fixed , , , and , the minimax width for our kernel grows as , with the lower bound holding even at the prespecified point . Therefore, we resolve the open problem posed by Vakili et al. [51] in the worst case over kernels in discrete time.
Discussion
This paper resolves, in the worst case over kernels, the open problem on tight online confidence intervals for RKHS elements posed by Vakili et al. [51], in the discrete-time model in which it was stated. We use the existing upper bound and establish a matching lower bound. In particular, for the additive kernel (10), combining our lower bound with the existing self-normalized upper bound (Abbasi-Yadkori [1]; Chowdhury and Gopalan [7]; Durand et al. [11]) yields
for all sufficiently large and all . Our discrete-time analysis shows that, for intervals of the form (5) and in the worst case over kernels and online designs, this inflation is an unavoidable statistical obstruction rather than an artifact of a particular concentration inequality or proof technique. Thus, the dependence of the existing confidence width is unavoidable in general, ruling out the conjectured polylogarithmic width. It is also consistent with the fact that the known order-optimal algorithms for kernelized bandits rely on batching or elimination, which control the dependence between the design and the noise, rather than on a sharper online interval.
Several directions follow from this characterization. The most immediate task is to determine the minimax confidence width for specific kernel families. Our lower bound uses an additive linear component, and the online design steers the estimate of its coefficient. It remains open whether a Matérn or squared exponential kernel alone exhibits the same inflation at a point [26]. A second direction is the regret of GP-UCB with a fixed regularization parameter, for which our result does not exclude a design-specific analysis. A third direction is a lower bound over all estimators, as in the Bayes-risk bound of Lattimore [31] and the minimax bound of Khamaru et al. [28], and over all interval constructions, for a fixed kernel with polynomially growing information gain. Finally, a natural direction is to construct data-driven widths that adapt to the realized design while maintaining coverage. On the hard instance of Theorem 4.2, any data-dependent interval with coverage at least must satisfy with probability at least , for every . Wild refitting and related resampling methods provide tools for evaluating excess risk and prediction error [54, 21, 17, 37]. An open question is whether these ideas can be adapted to pointwise confidence intervals under adaptive sampling. We leave the investigation of these directions to future work.
Useful Mathematical Tools
We collect the concentration inequality and matrix formulas used below.
Lemma A.1 (Laurent–Massart inequality, Laurent and Massart [32]). Let and let be symmetric and positive semidefinite. For every ,
Lemma A.3 (Schur complements, Horn and Johnson [14]). Let be symmetric positive definite. Its Schur complement is positive, and
For , the empty determinant and quadratic form are interpreted as one and zero, respectively.
Lemma A.4 (Determinant identities and bounds, Horn and Johnson [14]). For , Sylvester’s determinant identity gives
For every symmetric positive definite , Hadamard’s inequality gives
Properties of the Hard Kernel
Proof of Proposition 4.1. Since , the weights satisfy . The Fourier series defining therefore converges uniformly, so and the additive kernel are continuous. Define
The cosine difference identity gives the uniformly convergent expansion
Each feature product is a positive semidefinite rank-one kernel, and all its coefficients are positive. We conclude that is positive definite. Setting and using yields .
Under the uniform probability measure on , the functions form an orthonormal family. The trigonometric functions are orthonormal under the uniform measure on . The first coordinate is independent of the second, with mean zero and second moment . Integrating the kernel expansion against each of these functions gives eigenvalue for and for both and . The integral operator vanishes on the orthogonal complement of their closed span, so these are all its nonzero eigenvalues.
The periodic eigenvalues in nonincreasing order are . After inserting the single eigenvalue , the ordered sequence satisfies for . Since , we obtain the claimed decay.
Proof of the Lower Bound
Fix a positive semidefinite kernel on with , a deterministic sequence , and a test point with . We use the additive kernel and the response model with and i.i.d. . Write and define as in (12) and (13). For , let and let be the corresponding principal submatrix of . The posterior variance for the component based on is
Write and .
Whenever , set and use the design (14). The residual equals for every realization, including when is clipped. Thus the vector with coordinates has law . The offset vector before clipping is
Indeed, is strictly lower triangular, so depends only on past residuals. The actual point is .
The posterior error at the test point
For vectors , define
Lemma C.1. Suppose that , , and . Then
Proof of Lemma C.1. Let . The additive kernel gives , $k_n(x_0)=a+h, and . Since , we have . Applying Lemma A.2, we obtain
Using this inverse, we obtain and
Substituting into (4) and subtracting yields the claimed error. For the variance, we obtain
Cholesky identities and Gaussian bounds
Lemma C.2. For and , we have . For each ,
Consequently,
with every summand nonnegative.
Proof of Lemma C.2. Completing the square, we obtain
The expression is nonnegative by positive semidefiniteness of the Gram matrix on the points in and . Extending by zero on shows . The choice gives .
The leading by principal submatrix of has determinant because is unit lower triangular. Taking the ratio of the leading determinants of orders and gives , with the empty determinant interpreted as one. Applying Lemma A.3 to that leading submatrix, we evaluate this ratio as . Applying the same lemma to the full matrix after moving index to the last position gives . Substituting both identities into (13) gives the first sum in (C.2), whose summands are nonnegative since . Rewriting gives the second sum.
Define and . For , write
Lemma C.3. The matrix is strictly lower triangular, so depends only on . For the offset vector ,
Proof of Lemma C.3. Since is unit lower triangular, is strictly lower triangular. We have and
We pair with and with itself to obtain the identities for and . Since , we have . The strictly lower triangular part and the diagonal part of are orthogonal under the Frobenius inner product. Therefore,
□
Lemma C.4. For the offset vector before clipping, each , , and is centered Gaussian, with
Moreover,
Proof of Lemma C.4. The three scalars in (C.3) are deterministic linear functions of . To bound the variance of , use (C.1) and the diagonal of to obtain
Since , we have . Combining this estimate with gives
Let . Then . Using and , we obtain
Finally, since is positive semidefinite,
where the last inequality uses Lemma C.3 and the operator bound for . The last bound in (C.4) follows from and .
A probability bound for the normalized error
Lemma C.5. Fix and suppose that
Under the design (14), with probability at least ,
Proof of Lemma C.5. Set . The quadratic form has mean . Applying Lemma A.1 to , we obtain, with probability at least ,
Here the norm bounds are from Lemma C.4, and makes the last two terms at most and . Denote the resulting event by .
For the martingale term, let and . The coefficient is -measurable by Lemma C.3, and is standard Gaussian independent of . For each sign , let
Conditional on , the Gaussian moment generating function gives . By nonnegativity and induction, each is integrable with mean one and . On , the sign of satisfies
where we used from (C.4). Applying Markov’s inequality for both signs gives
by (C.5).
Using the Gaussian variance bounds in (C.3) and , we obtain
The last line uses and a union bound. The first and last lines use the two terms of (C.5), respectively.
Together these bounds give an event of probability at least on which holds, , , , and no offset is clipped. On this event the raw response vector is , so Lemma C.1 applies to the realized design. By Lemma C.3, we have
The threshold gives . Since , the signed posterior error satisfies
Using in the variance identity, we obtain
Dividing the error bound by and using proves (C.6).
Spectral estimates for the cyclic design
Lemma C.6. Let with , and let and be integers with . Suppose that
with arbitrary for . Let be the eigenvalues of , and let . Then
Proof of Lemma C.6. Since , the matrix is circulant. Let consist of complete passes. Ordering the indices of by pass gives and , where is the -th standard basis vector. Since , we have
Using this identity in the posterior variance and simplifying gives
The second equality uses the constant diagonal of the circulant matrix in brackets. Since each , is nonincreasing in , with .
For with , the observations before are contained in the first passes, and those with indices other than include all passes other than pass . Monotonicity from Lemma C.2 and (C.7) therefore give and . The -th summand of in (C.2) is thus at least
All other summands are nonnegative by Lemma C.2. Summing over the first passes and substituting the eigenvalue formula for gives
For , the denominator is at most . Keeping those terms, we obtain
To count the eigenvalues above the threshold, we take the discrete Fourier transform of on the grid. Its absolutely convergent Fourier series has coefficient at each frequency , and equals when and zero otherwise. Hence
Keeping for gives . Thus every with contributes to the count.
Lemma C.7. Consider the kernel (10) with . For all and , let and . Then
For every deterministic sequence , we also have
Proof of Lemma C.7. For arbitrary , write , so . Lemma A.2 and give
where we used . Let have columns and for . Applying the two parts of Lemma A.4, we obtain
Here the two diagonal entries indexed by are at most . The Fourier series converges absolutely, so entrywise. Passing to the limit gives
Since , we compare this series with the integral of the decreasing function over . Rescaling by gives
Combining (C.8) with the determinant estimate for the linear coordinate and taking the supremum over gives the first upper bound. The second follows from .
For the lower bound, take so that . By (6), the factorization (12), and (C.1), we have
We used for and the representation (C.2) with nonnegative subtracted terms.
Proof of the lower-bound theorem
Proof of Theorem 4.2. We first verify that the construction is an admissible instance. The kernel sections at and differ by the function , and their squared distance in is . Thus,
The Gaussian noise is -sub-Gaussian, and the residual is available after round . Hence the rule (14) selects from past observations, and clipping ensures .
The scaling is well defined for every . Indeed, the second pass repeats , so Lemma C.2 gives
The first summand of in (C.2) is therefore positive, and all other summands are nonnegative.
We now lower bound . Apply Lemma C.6 with and . Since ,
For fixed and , we have and . Choose an integer such that for all . Then and . Using , we obtain
The right-hand side grows polynomially in , whereas in (C.5) grows logarithmically. We may therefore increase to an integer such that for every . Applying Lemma C.5 with , we obtain, for each such , with probability at least ,
where . The same event satisfies .
To express this bound in terms of information gain, let be the constant in Lemma C.7. There is an integer such that, for all , . The upper bound in that lemma then gives
Its lower bound and (C.9) show that, for ,
In particular, , and both comparison constants depend only on . Set . Combining (C.10) and (C.11), on the same event, we have
Fix and let be a deterministic width that gives coverage at least for this instance. If , then coverage fails at throughout the event just constructed, whose probability is at least . This contradiction proves the claimed width bound.
For a data-dependent width with coverage at least on this instance, the coverage event intersects our lower-bound event with probability at least . On that intersection the width is at least , which gives the claim used in § 5.
Proof of the Minimax Characterization
The dependence on the confidence level follows from an elementary Gaussian tail bound.
Lemma D.1. Let . For every ,
Proof of Lemma D.1. Let be an independent copy of . Since is contained in the disk of radius ,
Here has the exponential distribution with mean 2. Taking the complement and using for , we obtain
:::
Proof of Corollary 4.3. Fix , , and . Call a deterministic width valid if the supremum of failure probabilities in (8) is at most . Theorem 3.3 supplies such a width and gives
Every valid width must cover the hard instance of Theorem 4.2. Since , its constant-probability lower bound forces every such width to satisfy . Taking the infimum over valid widths, we obtain
To obtain the confidence-level term, consider the deterministic design for all , with and i.i.d. noise . This is an instance in . Since , its kernel matrix and test vector are and . The identity and (4) yield
Consequently,
where . A valid width has failure probability at most at . Applying Lemma D.1, we therefore find
Since , we have , and hence
This holds for every valid , so .
Set . By taking the average of the two lower bounds, we obtain
Together with the upper bound, this proves the claimed comparison, with constants depending only on .
References
- [1]Yasin Abbasi-Yadkori. Online Learning for Linearly Parametrized Control Problems. PhD thesis, University of Alberta, 2013.
- [2]Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, pages 2312–2320, 2011.
- [3]Arya Akhavan, Amitis Shidani, Alex Ayoub, and David Janz. Bernstein-type dimension-free concentration for self-normalised martingales. arXiv preprint arXiv:2507.20982, 2025.arxiv.org/abs/2507.20982
- [4]Xu Cai and Jonathan Scarlett. On lower bounds for standard and robust Gaussian process bandit optimization. In Proceedings of the 38th International Conference on Machine Learning, 2021.arxiv.org/abs/2008.08757
- [5]Romain Camilleri, Julian Katz-Samuels, and Kevin Jamieson. High-dimensional experimental design and kernel bandits. In Proceedings of the 38th International Conference on Machine Learning, 2021.arxiv.org/abs/2105.05806
- [6]Fan Chen, Jian Qian, Alexander Rakhlin, and Nikita Zhivotovskiy. Self-normalized martingales and uniform regret bounds for linear regression. arXiv preprint arXiv:2605.01628, 2026.arxiv.org/abs/2605.01628
- [7]Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning, pages 844–853, 2017.
- [8]Victor H. de la Peña, Michael J. Klass, and Tze Leung Lai. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. The Annals of Probability, 32(3A): 1902–1933, 2004.
- [9]Victor H. de la Peña, Tze Leung Lai, and Qi-Man Shao. Self-Normalized Processes: Limit Theory and Statistical Applications. Springer, 2009.
- [10]Sjoerd Dirksen. Tail bounds via generic chaining. Electronic Journal of Probability, 20(53):1–29, 2015.arxiv.org/abs/1309.3522
- [11]Audrey Durand, Odalric-Ambrym Maillard, and Joelle Pineau. Streaming kernel regression with provably adaptive mean, variance, and regularization. Journal of Machine Learning Research, 19(17):1–34, 2018.arxiv.org/abs/1708.00768
- [12]Hamish Flynn and David Reeb. Tighter confidence bounds for sequential kernel regression. arXiv preprint arXiv:2403.12732, 2024.arxiv.org/abs/2403.12732
- [13]Dylan Foster and Alexander Rakhlin. Beyond UCB: Optimal and efficient contextual bandits with regression oracles. In Proceedings of the 37th International Conference on Machine Learning, pages 3199–3210, 2020.arxiv.org/abs/2002.04926
- [14]Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, second edition, 2012.
- [15]Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055–1080, 2021.DOI
- [17]Haichen Hu and David Simchi-Levi. Interleaved resampling and refitting: Data and compute-efficient evaluation of black-box predictors. arXiv preprint arXiv:2603.14218, 2026a.arxiv.org/abs/2603.14218
- [18]Haichen Hu and David Simchi-Levi. Minimax regret for Sobolev kernel-based reinforcement learning. arXiv preprint arXiv:2610.34045, 2026b.arxiv.org/abs/2610.34045
- [19]Haichen Hu and David Simchi-Levi. Simultaneous pointwise majorization for mixed tail processes with applications in Gaussian chaos and ergodic diffusions. arXiv preprint arXiv:2609.01576, 2026c.arxiv.org/abs/2609.01576
- [20]Haichen Hu, Rui Ai, Stephen Bates, and David Simchi-Levi. Contextual online decision making with infinite-dimensional functional regression. In Proceedings of the 42nd International Conference on Machine Learning, 2025a.arxiv.org/abs/2501.18359
- [21]Haichen Hu, David Simchi-Levi, and Navid Azizan. Eluder-dimension-free regret for stage-wise constrained contextual bandits via offline regression. arXiv preprint arXiv:2505.07101, 2025b.arxiv.org/abs/2505.07101
- [24]Shogo Iwazaki. Gaussian process upper confidence bound achieves nearly optimal regret in noise-free Gaussian process bandits. In Advances in Neural Information Processing Systems, volume 38, 2025b.
- [25]David Janz, David Burt, and Javier González. Bandit optimisation of functions in the Matérn kernel RKHS. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020.arxiv.org/abs/2001.10396
- [26]David Janz, Arya Akhavan, and Alexandre B. Tsybakov. Maximum effective dimension and information gain. arXiv preprint arXiv:2608.24450, 2026.arxiv.org/abs/2608.24450
- [27]Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K. Sriperumbudur. Gaussian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv:1807.02582, 2018.arxiv.org/abs/1807.02582
- [28]Koulik Khamaru, Yash Deshpande, Tor Lattimore, Lester Mackey, and Martin J. Wainwright. Near-optimal inference in adaptive linear regression. arXiv preprint arXiv:2107.02266v3, 2023.arxiv.org/abs/2107.02266
- [29]Andreas Krause and Cheng Soon Ong. Contextual Gaussian process bandit optimization. In Advances in Neural Information Processing Systems, volume 24, pages 2447–2455, 2011.
- [30]David Krieg and Jan Vybíral. New lower bounds for the integration of periodic functions. Journal of Fourier Analysis and Applications, 29:41, 2023. doi: 10.1007/s00041-023-10021-7.DOI
- [31]Tor Lattimore. A lower bound for linear and kernel regression with adaptive covariates. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2095–2113. PMLR, 2023.
- [32]Béatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28(5):1302–1338, 2000.
- [33]Zihan Li and Jonathan Scarlett. Gaussian process bandit optimization with few batches. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, 2022.arxiv.org/abs/2110.07788
- [34]Chenkai Ma and Jonathan Scarlett. A general Ω̃(√(T/Tγ)) lower bound for kernel bandits. arXiv preprint arXiv:2610.11082, 2026.
- [35]Davide Maran and Csaba Szepesvári. Sharper guarantees for misspecified kernelized bandit optimization. arXiv preprint arXiv:2605.05967, 2026.arxiv.org/abs/2605.05967
- [36]Gergely Neu, Julia Olkhovskaya, and Sattar Vakili. Adversarial contextual bandits go kernelized. In Proceedings of the 35th International Conference on Algorithmic Learning Theory, volume 237 of Proceedings of Machine Learning Research, pages 907–929. PMLR, 2024. URL https://proceedings.mlr.press/v237/neu24a.html.arxiv.org/abs/2310.01609
- [37]Yijin Ni and Xiaoming Huo. Upper confidence bounds for the prediction error of kernel ridge regression via Gaussian refitting. arXiv preprint arXiv:2607.28846, 2026.arxiv.org/abs/2607.28846
- [38]Jian Qian, Haichen Hu, and David Simchi-Levi. Offline oracle-efficient learning for contextual MDPs via layerwise exploration-exploitation tradeoff. arXiv preprint arXiv:2405.17796, 2024.arxiv.org/abs/2405.17796
- [39]J. Jon Ryu and Gregory W. Wornell. Gambling-based confidence sequences for bounded random vectors. In Proceedings of the 41st International Conference on Machine Learning, 2024.arxiv.org/abs/2402.03683
- [40]Sudeep Salgia, Sattar Vakili, and Qing Zhao. A domain-shrinking based Bayesian optimization algorithm with order-optimal regret performance. In Advances in Neural Information Processing Systems, volume 34, 2021.arxiv.org/abs/2010.13997
- [41]Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy Gaussian process bandit optimization. In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1723–1742. PMLR, 2017.arxiv.org/abs/1706.00090
- [42]Matthias W. Seeger, Sham M. Kakade, and Dean P. Foster. Information consistency of nonparametric Gaussian process methods. IEEE Transactions on Information Theory, 54(5):2376–2382, 2008.DOI
- [43]David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 2021.
- [44]Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, pages 1015–1022, 2010.DOI
- [45]Shion Takeno, Shogo Iwazaki, and Ichiro Takeuchi. Near-optimal regret bounds for UCB-style Gaussian process bandits via data thinning. arXiv preprint arXiv:2610.28136, 2026.arxiv.org/abs/2610.28136
- [46]Michel Talagrand. The Generic Chaining: Upper and Lower Bounds of Stochastic Processes. Springer Monographs in Mathematics. Springer, 2005.DOI
- [47]Sattar Vakili. Open problem: Order optimal regret bounds for kernel-based reinforcement learning. In Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research. PMLR, 2024.arxiv.org/abs/2406.15250
- [48]Sattar Vakili and Julia Olkhovskaya. Kernelized reinforcement learning with order optimal regret bounds. In Advances in Neural Information Processing Systems, volume 36, 2023.arxiv.org/abs/2306.07745
- [49]Sattar Vakili, Nacime Bouziani, Sepehr Jalali, Alberto Bernacchia, and Da-shan Shiu. Optimal order simple regret for Gaussian process bandits. In Advances in Neural Information Processing Systems, volume 34, 2021a.arxiv.org/abs/2108.09262
- [50]Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in Gaussian process bandits. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pages 82–90, 2021b.arxiv.org/abs/2009.06966
- [51]Sattar Vakili, Jonathan Scarlett, and Tara Javidi. Open problem: Tight online confidence intervals for RKHS elements. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 4647–4652. PMLR, 2021c.arxiv.org/abs/2110.15458
- [52]Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, pages 654–663, 2013.arxiv.org/abs/1309.6869
- [53]Grace Wahba. Spline Models for Observational Data. SIAM, 1990.
- [54]Martin J. Wainwright. Wild refitting for black box prediction. arXiv preprint arXiv:2506.21460, 2025.arxiv.org/abs/2506.21460
- [55]Wenjia Wang and Xiaowei Zhang. On the suboptimality of GP-UCB under polynomial effective optimism. arXiv preprint arXiv:2312.01386v2, 2026.arxiv.org/abs/2312.01386
- [56]Justin Whitehouse, Aaditya Ramdas, and Zhiwei Steven Wu. On the sublinear regret of GP-UCB. In Advances in Neural Information Processing Systems, volume 36, 2023.arxiv.org/abs/2307.07539
- [57]Yunbei Xu. Bellman-sufficient information complexity. arXiv preprint arXiv:2606.11171, 2026a.arxiv.org/abs/2606.11171
- [58]Yunbei Xu. Pointwise complexity for gaussian fields: Upper envelopes, algorithmic lower bounds, and separation. arXiv preprint arXiv:2606.07931, 2026b.arxiv.org/abs/2606.07931
- [59]Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I. Jordan. Provably efficient reinforcement learning with kernel and neural function approximations. In Advances in Neural Information Processing Systems, volume 33, 2020.
- [60]Houssam Zenati, Alberto Bietti, Eustache Diemert, Julien Mairal, Matthieu Martin, and Pierre Gaillard. Efficient kernelized UCB for contextual bandits. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 5689–5720. PMLR, 2022. URL https://proceedings.mlr.press/v151/zenati22a.html.arxiv.org/abs/2202.05638