3. Math Toolkit II: Kernels, GPs & Uncertainty Bounds

RKHS, GP regression, information gain, frequentist confidence bounds and the β_t problem

Book contents · Apply this chapter to a real decision · Glossary

Almost every safe-exploration guarantee in Modules 4–6 (the deliberate exception is LoSBO in Module 5, whose safety argument uses only a Lipschitz constant (see Primer B) and a noise bound) and the data-driven region-of-attraction certificate of Module 11 rest on one statement: a Gaussian-process model (a model in which every finite collection of function values is jointly Gaussian) of an unknown function $f$ comes with a band $\mu_t(x)\pm\beta_t\sigma_t(x)$ that contains $f(x)$ for all $x$ and all times $t$ with probability at least $1-\delta$ (see Primer C). Whether a SafeOpt run is actually safe reduces to whether that band is honest. This page builds it from scratch: kernels and their RKHS, why the GP mean is a ridge regressor, why $\sigma_t$ measures ignorance even without probability, how the information gain enters, then the three classical frequentist bounds, the Trimpe-group refinement that made them computable (and the later correction of its constant), and the ways their assumptions fail.

1. Kernels & the RKHS

In plain words. A kernel $k(x,x')$ says how similar we expect the function values at two inputs to be: close inputs, similar values. The RKHS is the space of functions you can build by adding up "bumps" $k(z,\cdot)$ centred at different points. Its norm $\|f\|_k$ measures how much bump material you need. A function that changes sharply over short distances needs a lot of it, so the norm acts as a smoothness measure. Safe-BO guarantees assume a known bound $\|f\|_k\le B$.

A kernel is a similarity measure between inputs that behaves like an inner product. That single property is what turns the whole GP machinery into linear algebra.

The reproducing property is the only tool needed for most of this page. Two immediate consequences:

The RKHS norm is a smoothness measure

For a translation-invariant kernel $k(x,x')=\kappa(x-x')$ on $\mathbb R^d$ with integrable, positive Fourier transform $\hat\kappa$, the norm of $f\in\mathcal H_k(\mathbb R^d)$ is (up to a normalising constant) $\|f\|_k^2=\int|\hat f(\omega)|^2/\hat\kappa(\omega)\,d\omega$: frequency content is penalised in proportion to $1/\hat\kappa(\omega)$. (On a compact $D$, the norm of $f$ in the RKHS of the restricted kernel is the smallest such norm over all extensions of $f$ to $\mathbb R^d$.) For the SE kernel $\hat\kappa(\omega)\propto\ell^d e^{-\ell^2\|\omega\|^2/2}$, so high frequencies are penalised super-exponentially and $\mathcal H_{k_{\mathrm{SE}}}$ contains only analytic functions. For Matérn-$\nu$ with the $\sqrt{2\nu}\,r/\ell$ scaling used above, $\hat\kappa(\omega)\propto(2\nu/\ell^2+\|\omega\|^2)^{-(\nu+d/2)}$ and $\mathcal H_k$ is norm-equivalent to the Sobolev space $H^{\nu+d/2}$: a statement about square-integrable weak derivatives of order $\nu+d/2$, not an exact count of classical derivatives.

Changing the length-scale moves the norm, not only the space. For the SE kernel with $\ell'\le\ell$, $\mathcal H_{k_\ell}\subseteq\mathcal H_{k_{\ell'}}$ and $\|f\|_{k_{\ell'}}\le(\ell/\ell')^{d/2}\|f\|_{k_\ell}$ (Berkenkamp, Schoellig & Krause, JMLR 2019, Lemma 2, after Bull 2011): a shorter length-scale keeps $f$ in the space, but its norm may grow by up to that factor, so $B$ has to be inflated with it. For Matérn kernels of fixed $\nu$ the space does not change with $\ell$ at all, only the norm does. This is the precise sense in which under-estimating $\ell$ is the "safe direction" (Section 7): membership survives, the old $B$ does not.

2. GP Regression = Kernel Ridge Regression

In plain words. GP regression predicts an unknown function from noisy samples and says how unsure it is. Near the data the prediction follows the measurements and the uncertainty is small. For kernels whose correlations decay with distance, such as SE and Matérn, the prediction far from all data falls back to the prior mean, zero, and the uncertainty returns to its prior level. Other kernels, such as the linear kernel, extrapolate differently. The same formula has two readings: Bayesian (the posterior of a random function) and frequentist (kernel ridge regression of a fixed unknown function). Safe BO uses the second.

A Gaussian process $f\sim\mathcal{GP}(0,k)$ is the statement that the values of $f$ at any finite set of inputs are jointly Gaussian with covariance $K$. With the observation model $y_i=f(x_i)+\varepsilon_i$, $\varepsilon_i\sim\mathcal N(0,\sigma_n^2)$ i.i.d. and independent of $f$, the vector $(y_t,f(x))$ is jointly Gaussian too (see Primer C): $$\begin{pmatrix}y_t\\ f(x)\end{pmatrix}\sim\mathcal N\!\left(0,\begin{pmatrix}K_t+\sigma_n^2I & k_t(x)\\ k_t(x)^\top & k(x,x)\end{pmatrix}\right).$$ Conditioning on $y_t$ is a Schur-complement computation (Module 2).

The displayed joint law uses the physical noise variance $\sigma_n^2$, so the exact Bayesian posterior has $\lambda=\sigma_n^2$ below. Any other $\lambda$ gives the posterior of a working likelihood (equivalently, the ridge estimator of the next subsection), which need not be the physical conditional law. Also, $\sigma_t^2(x)$ is the variance of the latent value $f(x)$; a new noisy observation at $x$ has predictive variance $\sigma_t^2(x)+\sigma_n^2$ under the correctly specified model.

The same formula from an optimisation problem

Feature-space form and the variance identity

Let $\Phi_t:\mathcal H_k\to\mathbb R^t$, $\Phi_tg=[\langle\varphi(x_1),g\rangle_k,\dots,\langle\varphi(x_t),g\rangle_k]^\top$, be the design operator. Then $K_t=\Phi_t\Phi_t^*$, $k_t(x)=\Phi_t\varphi(x)$, $f_{1:t}=\Phi_tf$, and two identities carry the whole theory:

3. The Noise-Free Error Bound

In plain words. With exact, noise-free measurements, how far can the true function be from the interpolant through the data? The answer of this section is short: at most the function's RKHS norm times the posterior standard deviation, $\|f\|_k\,P_t(x)$. Near the data $P_t$ is small and the interpolant can be trusted. For a decaying kernel such as SE, far from the data $P_t$ is close to its prior value, and the norm bound is all you have. (In general $P_t(x)$ measures how much of "the value at $x$" cannot be reproduced from the measured values, which need not grow with distance.)

Before any probability enters, here is the cleanest reason why $\sigma_t$ measures ignorance. Take noise-free observations $y_i=f(x_i)$ at distinct inputs with $K_t\succ0$ and let $\lambda\to0$: the GP mean becomes the interpolant $s_t(x)=k_t(x)^\top K_t^{-1}f_{1:t}$ and $\sigma_t^2$ becomes the power function $P_t(x)^2=k(x,x)-k_t(x)^\top K_t^{-1}k_t(x)$.

4. Maximum Information Gain

In plain words. Each measurement teaches the GP something about $f$, but a measurement close to earlier ones teaches little that is new. The information gain counts how much is learned in total, in units of information (nats). The maximum information gain $\gamma_T$ is the most that $T$ measurements could ever reveal, and it is what regret and sample-complexity bounds depend on. If it grows slowly, the uncertainty must shrink fast wherever the algorithm keeps sampling.

Regret and sample-complexity bounds (see Primer E) must control how fast the posterior variances shrink along whatever sequence the algorithm chooses. The right quantity is the amount of information that $t$ noisy observations can reveal about $f$ under the GP model.

Closed form. $y_A\sim\mathcal N(0,K_A+\lambda I)$ and $y_A\mid f_A\sim\mathcal N(f_A,\lambda I)$; with $H(\mathcal N(m,\Sigma))=\tfrac12\log\det(2\pi e\Sigma)$ the $2\pi e$ factors cancel and $I=\tfrac12\log\det(K_A+\lambda I)-\tfrac12\log\det(\lambda I)=\tfrac12\log\det(I+\lambda^{-1}K_A)$.

How fast does $\gamma_T$ grow?

Growth rates use asymptotic notation (see Primer 0): as $T\to\infty$, $a_T=O(b_T)$ means $|a_T|\le Cb_T$ for all large $T$ with a constant $C$ independent of $T$; $a_T=o(b_T)$ means $a_T/b_T\to0$; $a_T=\Omega(b_T)$ means $a_T\ge cb_T$ eventually for some $c\gt0$; $\widetilde O$ also hides logarithmic factors. Kernel, dimension, domain and regulariser are fixed, and the hidden constants may depend on them. A regret bound is sublinear if $R_T/T\to0$. An $O(\cdot)$ rate is not a computable finite-sample certificate.

$\gamma_T$ is governed by the eigenvalue decay of the kernel operator: if the first few eigenfunctions carry most of the mass, $T$ observations cannot learn much more than a finite-dimensional model. Srinivas et al. bound it through this spectrum (their Theorems 4–5); Vakili, Khezeli & Picheny, AISTATS 2021 sharpen the Matérn case by projecting onto the span of the first $M$ Mercer eigenfunctions $e_m$ and controlling the tail. Under their Assumption 1 (a bounded kernel whose Mercer eigenfunctions are uniformly bounded, $|e_m(x)|\le\psi$), $\gamma_T=O(M\log T+\Delta_MT)$ for every $M$, with tail mass $\Delta_M=\psi^2\sum_{m\gt M}\lambda_m$ (their Theorem 3, stated precisely below; here $\lambda_m$ are the Mercer eigenvalues, not the regulariser). Choosing $M$ optimally gives the rates below, which for Matérn kernels are tight up to logarithms against the known lower bounds.

5. Frequentist Confidence Bounds & $\beta_t$

In plain words. Safe BO needs error bars that hold at every input and every round at once, with probability at least $1-\delta$, even though the algorithm chooses where to measure based on earlier noisy data. The answer is a band $\mu_{t-1}(x)\pm\beta_t\sigma_{t-1}(x)$. The width multiplier $\beta_t$ collects four ingredients: the norm bound $B$, the noise level $R$, the failure probability $\delta$, and the information gain. Only the information gain grows with data.

The goal is: with probability at least $1-\delta$, for all $t\ge1$ and all $x\in D$ simultaneously, $|\mu_{t-1}(x)-f(x)|\le\beta_t\,\sigma_{t-1}(x)$. "Simultaneously" is the hard part: a safe-exploration algorithm chooses $x_t$ from the past, the noise is only a martingale difference sequence (its conditional law may depend on the history; see Primer C), and a naive union bound assigning the same failure budget to every point and time is insufficient. Three generations of results achieve it.

A union bound does work over countably many times if the failure budgets are summable, e.g. $\delta_t=6\delta/(\pi^2t^2)$, which add up to $\delta$ because $\sum_t1/t^2=\pi^2/6$; Srinivas et al. use such a union bound over time. It cannot give a useful bound over the uncountably many points of $D$ by granting each point the same positive failure probability. The RKHS argument handles all $x$ at once through one norm bound, and the self-normalised bounds below handle all $t$ at once through a maximal inequality instead of a time budget.

How large are these $\beta$ really?

Take an ordinary case: $\|f\|_k=2$ (Srinivas' $B=4$), $t=100$, $\gamma_t=10$ (the same value for both theorems, a simplification: $\gamma_t$ depends on $\lambda$), $\delta=0.05$, and zero-mean noise bounded by $0.1$, so that Srinivas' $\sigma=0.1$ and, by Hoeffding's lemma, $R=0.1$ as well. (Gaussian noise would not do here: it is not bounded, so Srinivas' theorem would not apply to it.) Srinivas et al.: $\beta_t=8+300\cdot10\cdot\ln^3(2000)\approx8+300\cdot10\cdot439\approx1.32\times10^6$, a band of $\beta_t^{1/2}\approx1150$ posterior standard deviations. Chowdhury–Gopalan: $\beta_t=2+0.1\sqrt{2(10+1+3.0)}\approx2.53$, but for a posterior computed with $\lambda\approx1$, a hundred times $\sigma^2=0.01$, whose $\sigma_{t-1}$ is correspondingly inflated. The data-dependent bounds of Section 6 land at roughly $B$ plus a few units to a few tens for the $\lambda$ a practitioner would use (the explorer prints them). Against this, the constants used in practice are $\beta\equiv2$ (Berkenkamp et al. 2016, Turchetta et al. 2016), $\beta\equiv3$ (GoSafe) and $\beta\equiv4$ (GoSafeOpt), and Srinivas et al. already reported scaling their own $\beta_t$ down by a factor of five in experiments. Fiedler et al. (TMLR 2024) quantify the consequence: with $\beta\equiv2$, on average $2727\pm3882$ of $10^4$ sampled data sets per test function violated the uncertainty tube (100 test functions), and SafeOpt with $\beta\equiv2$ produced $2862$ unsafe runs out of $10^4$ on one test function; Real-$\beta$-SafeOpt with the true RKHS norm produced none, and with the norm under-estimated as $2.5$ instead of $10$ it produced $1338$ (Module 5).

6. Practical and Rigorous Bounds (Fiedler, Scherer, Trimpe)

For learning-based control one rarely needs an a-priori bound: the data set is fixed when the controller is synthesised, so the bound may depend on it. Fiedler, Scherer & Trimpe (AAAI 2021) exploit exactly this: stop the Chowdhury–Gopalan proof at the log-determinant instead of bounding it by $\gamma_t$.

Variants: log-det-free, Abbasi-Yadkori form, and tighter

• Independent noise, no log-det (Fiedler et al. 2021, Proposition 2). For given (non-adaptive) inputs and independent $R$-sub-Gaussian $\varepsilon_1,\dots,\varepsilon_N$, with probability at least $1-\delta$, for all $x$: $|\mu_N(x)-f(x)|\le B\sigma_N(x)+\eta_N(x)$ with (their notation; unrelated to Chowdhury–Gopalan's $\eta$)
  $$\eta_N(x)=R\,\big\|(K_N+\lambda I)^{-1}k_N(x)\big\|_2\sqrt{N+2\sqrt{N\log(1/\delta)}+2\log(1/\delta)}$$
  The noise part of the error is $a(x)^\top\varepsilon_{1:N}$ with $a(x)=(K_N+\lambda I)^{-1}k_N(x)$, and Cauchy–Schwarz in $\mathbb R^N$ gives $|a(x)^\top\varepsilon_{1:N}|\le\|a(x)\|_2\|\varepsilon_{1:N}\|_2$. The norm of the noise vector is controlled by the tail bound of Hsu, Kakade & Zhang (2012) (their main theorem with the identity matrix), which replaces the martingale bound: if $\mathbb E\,e^{\alpha^\top\varepsilon_{1:N}}\le e^{\|\alpha\|^2R^2/2}$ for all $\alpha\in\mathbb R^N$ (true for independent zero-mean $R$-sub-Gaussian entries), then $\Pr\{\|\varepsilon_{1:N}\|_2^2\gt R^2(N+2\sqrt{Nu}+2u)\}\le e^{-u}$ for every $u\gt0$; take $u=\log(1/\delta)$. This has the shape of a $\chi^2$ tail but does not assume Gaussian noise, and one event covers every $x$, for one fixed $N$ only (it is not uniform in $N$). Stated for $\lambda\ge0$, so it covers interpolation, but the case $\lambda=0$ requires an invertible $K_N$ (for example a strictly positive definite kernel evaluated at distinct inputs); with repeated inputs, or a kernel whose Gram matrices can be singular, keep $\lambda\gt0$.
• Abbasi-Yadkori (2013) form, eq. (7) of Fiedler et al. TMLR 2024. Using the $\rho$-parametrised self-normalised bound with $\rho=\lambda$ gives, for any $\lambda\gt0$ and positive definite $k$, $$\beta_t=\|f\|_k+\frac{R}{\sqrt\lambda}\sqrt{2\ln\Big(\tfrac1\delta\det\big(I_t+\tfrac1\lambda K_t\big)^{1/2}\Big)}=B+\frac{R}{\sqrt\lambda}\sqrt{\ln\det(I_t+K_t/\lambda)-2\ln\delta}\,.$$ (The printed eq. (7) omits the exponent $\tfrac12$ on the determinant; the paper's own rewrite directly below it, used here, has the correct form, which is also Whitehouse et al.'s Corollary 1 with $\rho=\lambda$.) For $\lambda\le1$ this coincides with the corrected AAAI formula; for $\lambda\gt1$ it is tighter, because $\log\det(K_t+\lambda I)=\log\det(I+K_t/\lambda)+t\log\lambda$. This is what Real-$\beta$-SafeOpt evaluates (Module 5).
• Comparison with Chowdhury–Gopalan. For the same $\lambda$, $\tfrac12\log\det(I+K_t/\lambda)=G_t\le\gamma_t$ (Section 4), so the data-dependent $\beta$ is never larger than the a-priori one; the gap is "maximal minus realised information gain", and an a-priori bound must additionally upper-bound $\gamma_t$ numerically or by a rate. The explorer prints both for $t=10,50,200$.
• Tighter still: Flynn & Reeb, AISTATS 2025. Instead of one ellipsoid, fix a mixture scale $c\gt0$ (the covariance scale of their Gaussian mixture $\mathcal N(0,cK_t)$) and keep the confidence sequence $\mathcal F_t=\{f\in\mathcal H_k:\|f_{1:t}-y_t\|_2\le R_t,\ \|f\|_k\le B\}$, the intersection of two ellipsoids, with the data-dependent radius of their eq. (8) (their $\sigma$ is our $R$) $$R_t^2=y_t^\top\big(I+\tfrac{c}{R^2}K_t\big)^{-1}y_t+R^2\ln\det\big(I+\tfrac{c}{R^2}K_t\big)+2R^2\ln\tfrac1\delta .$$ Their Lemma 4.2: if $\|f\|_k\le B$, the inputs are predictable, the noise is conditionally $R$-sub-Gaussian with $R\gt0$, and $c\gt0$ and $\delta\in(0,1)$ are fixed in advance, then with probability at least $1-\delta$, $f\in\mathcal F_t$ for all $t\ge1$ simultaneously; this is what "confidence sequence" means. The first constraint keeps the functions that agree with the data up to the radius $R_t$ (not the noise level $R$, nor the regret $R_T$), the second limits their complexity; tuning $c$ after seeing the data would break the mixture argument. The exact UCB $\max_{f\in\mathcal F_t}f(x)$ is a $(t+1)$-dimensional second-order cone program (their Theorem 4.4) whose Lagrangian dual gives the upper bound $\inf_{\alpha\gt0}\{\mu_{\alpha,t}(x)+\tfrac{1}{\sqrt\alpha}\tilde R_{\alpha,t}\,\rho_{\alpha,t}(x)\}$ with the KRR mean and standard deviation at regulariser $\alpha$ and $\tilde R_{\alpha,t}^2=R_t^2+\alpha B^2-\alpha\,y_t^\top(K_t+\alpha I)^{-1}y_t$ (Theorem 4.5 and Corollary 4.3), with equality when some function satisfies both constraints strictly: a bound of the same shape as above, optimised over the regulariser pointwise. The comparison with the classical sets holds for matched parameters (their Theorem 6.1): with $c=R^2/\lambda$ and $\alpha=\lambda$ the fixed-$\alpha$ bound is strictly tighter than the Abbasi-Yadkori bound with regulariser $\lambda$, and with $c=R^2/(1+\eta)$ and $\alpha=1+\eta$ strictly tighter than the Chowdhury–Gopalan bound with parameter $\eta$ (so the exact UCB, which is at most this infimum over $\alpha$, is too). A set built with an unrelated $c$ is not guaranteed to beat every comparator.
  Background — second-order cone programs and the dual

  The second-order cone is $\{(u,v):\|u\|_2\le v\}$; for example $(3,4,5)$ lies on its boundary since $\sqrt{3^2+4^2}=5$. A second-order cone program (SOCP) maximises a linear objective subject to constraints $\|Az+b\|_2\le c^\top z+d$, each saying that an affine image of $z$ lies in this cone. Here the maximising $f$ can be taken in the span of $k(x_1,\cdot),\dots,k(x_t,\cdot),k(x,\cdot)$, since projecting onto this span keeps the evaluations at $x_1,\dots,x_t,x$ and cannot increase the norm. With the Gram matrix $G$ of $(x_1,\dots,x_t,x)$ and coefficients $a\in\mathbb R^{t+1}$ the problem reads: maximise $(Ga)_{t+1}$ subject to $\|(Ga)_{1:t}-y_t\|_2\le R_t$ and $\|G^{1/2}a\|_2\le B$, two cone constraints. By weak duality the dual value is always an upper bound; it equals the maximum when some function satisfies both constraints strictly (Slater's condition, see Module 2), which is the usual case. Substituting a ratio $\alpha$ of the two multipliers reduces the dual to the one-dimensional problem above, where $\rho_{\alpha,t}$ is the posterior standard deviation with regulariser $\alpha$; the infimum may only be approached as $\alpha\to0$ or $\alpha\to\infty$.

• Sublinear regret for GP-UCB: Whitehouse, Ramdas & Wu, NeurIPS 2023. Their Theorem 2 fixes a horizon $T$ and a regulariser $\rho\gt0$, assumes a known bound $\|f\|_k\le B$ and conditionally $R$-sub-Gaussian noise (their Assumption 1) and a bounded kernel whose Mercer eigenfunctions are uniformly bounded (Assumption 2, as in Vakili et al.), and runs GP-UCB (regret as in Section 4) with posterior regulariser $\rho$ and the multiplier $B+\frac{R}{\sqrt\rho}\sqrt{\ln\det(I+K_{t-1}/\rho)-2\ln\delta}$ of the Abbasi-Yadkori form above. Then, with probability at least $1-\delta$, $R_T=O\big(\gamma_T(\rho)\sqrt T+\sqrt{\rho\,\gamma_T(\rho)\,T}\big)$, where $\gamma_T(\rho)$ is computed with regulariser $\rho$ and the constants depend on $\delta$, $B$, $R$ and the kernel bounds. A large $\rho$ shrinks $\gamma_T(\rho)$ but inflates the bias term. For $(C,\beta_p)$-polynomial eigendecay with $\beta_p\gt1$ (they write $\beta$; here $\beta_p$ as in Section 4, to avoid a clash with $\beta_t$), the choice $\rho\asymp T^{1/(1+\beta_p)}$ balances the two terms and gives $R_T=\tilde O(T^{\frac{3+\beta_p}{2+2\beta_p}})$, i.e. $\tilde O(T^{\frac{\nu+2d}{2\nu+2d}})$ for Matérn-$\nu$ with $\beta_p=(2\nu+d)/d$ (Corollary 2, stated for smoothness $\nu\gt\tfrac12$): sublinear in every dimension $d\ge1$ and for every $\nu\gt\tfrac12$. This is a rate for a horizon-dependent $\rho$ with unspecified constants, not a statement about a fixed $\lambda$; the computable confidence bounds above do not depend on it.

The Bayesian counterpart: Lederer, Umlauft & Hirche (NeurIPS 2019)

This bound needs no $B$ and gives modest $\sqrt{\beta(\tau)}$ (about $4.3$–$7.4$ for $\delta=0.01$, $\tau\in[10^{-3},10^{-2}]$ on the unit cube in $d=1,2,3$), which is why it is popular in GP-based control. But it is a statement about a random $f$ under the prior with Gaussian noise: it does not certify a fixed unknown plant, and the Bayesian-versus-RKHS incompatibility of Section 1 means it cannot be combined with the frequentist results. Capone, Lederer & Hirche (ICML 2022) extend it to unknown length-scales. They assume stationary kernels $k_\vartheta(x,x')=\kappa\big((x_1-x'_1)/\vartheta_1,\dots,(x_d-x'_d)/\vartheta_d\big)$ with $\kappa(0)=1$ and a Fourier transform that is a non-negative, non-increasing function of $\|\omega\|_2$ (their Assumption 2.1; SE and Matérn qualify), and a known scaling function $\beta(\vartheta)$ that yields a valid uniform bound with probability $1-\rho$ for each fixed length-scale vector $\vartheta$ (Assumption 3.2, e.g. from Lederer et al.). Then: if $\vartheta'\le\vartheta\le\vartheta''$ componentwise, $\sigma_\vartheta(x)\le\gamma\,\sigma_{\vartheta'}(x)$ with $\gamma^2=\prod_i\vartheta''_i/\vartheta'_i$ (Lemma 3.3), and with the inflated $\bar\beta=\gamma^2\big(\max_{\vartheta'\le\vartheta\le\vartheta''}\beta^{1/2}(\vartheta)+2\|y\|_2/\sigma_n\big)^2$ one has $\Pr[|f(x)-\mu_{\vartheta_0}(x)|\le\bar\beta^{1/2}\sigma_{\vartheta'}(x)\ \forall x]\ge1-\rho$ for a sample $f$ of the GP with any $\vartheta$ in the box and any working length-scale $\vartheta_0$ in the box (Theorem 3.5); with a hyperprior on $\vartheta$ (see Primer C) and the box chosen as a $1-\delta$ posterior credible region, the bound holds with probability $(1-\delta)(1-\rho)$ (Theorem 3.7). Their $\gamma$ is an inflation factor and their $\rho$ a probability, not the information gain and the Whitehouse regulariser.

Here the box describes plausible true length-scales, while $\vartheta_0$ is the one actually used to fit the mean. The probability $(1-\delta)(1-\rho)$ is not an independence calculation: the box contains the true $\vartheta$ with posterior probability at least $1-\delta$, and for every $\vartheta$ in the box the band holds with conditional probability at least $1-\rho$, so conditioning (the tower rule) multiplies the two. Like Lederer et al.'s bound, this is a statement under the GP model and the hyperprior, not a certificate for a fixed function.

7. When the Assumptions Fail

Each rigorous bound is only as good as its assumptions, and four of them fail routinely in control practice.

Unknown RKHS norm

Under-estimating $B$ shrinks the bias part $B\sigma_t$ of every band and the guarantee silently disappears (the explorer's "under-estimated $B$" option shows it once the bias term dominates, e.g. for $\lambda\approx1$; Fiedler et al. 2024 measured $1338/10^4$ unsafe runs with $B=2.5$ against a true norm of $10$). Tokmak, Krishnan, Schön & Baumann (AISTATS 2025) estimate an over-estimate $B_t\ge\|f\|_k$ from data: sample $m$ random RKHS functions consistent with the observations, sort their norms and discard the largest few (a sampling-and-discarding scenario programme, see Module 15 for a later treatment of scenario methods). Their Theorem 1: under their Assumption 2, that the norms of the random functions and of $f$ are i.i.d. draws from one unknown distribution, and for $m$ large enough, with confidence at least $1-\kappa$ the estimate satisfies $B_t\ge\|f\|_k$ with probability at least $1-\gamma$ (their $\gamma$ and $\kappa$ are probability levels, not the information gain); the resulting confidence intervals (Theorem 2, using the Abbasi-Yadkori form of Section 6) then hold with probability $(1-\gamma)(1-\delta)$, and safety follows as in SafeOpt with $d_k$ in place of the Lipschitz metric (Theorem 3). The i.i.d. assumption is the honest price: the norm of the true function is treated as one more sample. The same group's PACSBO (Tokmak, Schön & Baumann, SysDO 2024) estimates the norm bound locally, for $f$ restricted to a neighbourhood of the explored region rather than globally, which makes it less conservative, again with a probably-approximately-correct safety guarantee.

Hyperparameters chosen from the data

Every RKHS bound is for a fixed kernel. Maximising the marginal likelihood over the length-scale (see Primer C) after each observation changes $\mathcal H_k$ (or at least its norm) at every step and makes the kernel depend on the noise, so neither $\|f\|_k\le B$ nor the fixed-kernel martingale argument is automatically justified: the theorems do not apply to "ML-II, then Theorem 1". Partial remedies: Fiedler et al. 2021, Propositions 3–4: if the GP uses a kernel whose RKHS contains the true one (for the isotropic SE kernel, a length-scale $\ell\le\tilde\ell$), Theorem 1 holds unchanged provided $B$ bounds the norm of $f$ in the RKHS of the kernel actually used. That norm is finite because $\mathcal H_{\tilde k}\subseteq\mathcal H_k$, but it can exceed $\|f\|_{\tilde k}$ (by up to the factor $(\tilde\ell/\ell)^{d/2}$ of Section 1), since the inclusion map has norm greater than one in general; this is the clarification stated in the Corrections section of v2 (the footnote it adds to Proposition 4 is worded "valid for $\tilde k$"; by the argument just given, what Theorem 1 needs is a bound on the norm for the kernel $k$ used in the GP). Under-estimating $\ell$ is the safe direction for membership, over-estimating it is not. Their Theorem 5 covers a true kernel $\tilde k$ that differs from the working kernel $k$ by at most a known $\tilde\epsilon$ everywhere: the band is widened and shifted by explicit terms that do not vanish even where $\sigma_N=0$, because $f\notin\mathcal H_k$ is possible while $\mu_N\in\mathcal H_k$ always (a simplified version with a complete proof follows below). Capone et al. 2022 handle a box of length-scales in the Bayesian setting (Section 6). On the regret side, Berkenkamp, Schoellig & Krause (JMLR 2019) let the function class grow over time, shrinking the length-scales and inflating the norm bound with monotonically increasing scaling functions $g(t)$, $b(t)$ that may also depend on the data (A-GP-UCB, with $B_t=b(t)g(t)^dB_0$ in their eq. (9)). Their Section 2, Lemma 1 and Algorithm 1 use $B$ as a bound on the norm and insert it linearly into their confidence multiplier $\beta_t^{1/2}$ (Srinivas-style notation), while their Theorem 1 prints the squared-norm assumption $\|f\|_{k_\theta}^2\le B$, inconsistently with those definitions; read the algorithmic $B$ as a norm bound (the factor $g(t)^d$ is then conservative, since by their Lemma 2 the norm itself grows by at most $g(t)^{d/2}$). Their confidence bounds become valid from the (unknown) round on which the class contains $f$, which is enough for no-regret but gives no safety from the first query.

Misspecified function class: $f$ only close to the RKHS

Bogunovic & Krause (NeurIPS 2021) formalise $\min_{f\in\mathcal F_k(D;B)}\|f-f^*\|_\infty\le\epsilon$, where $\mathcal F_k(D;B)=\{g\in\mathcal H_k:\|g\|_k\le B\}$ is the norm ball and $\|g\|_\infty=\sup_{x\in D}|g(x)|$: the observed $f^*$ differs from some bounded-norm $\tilde f$ by an unknown $m(x)=f^*(x)-\tilde f(x)\in[-\epsilon,\epsilon]$.

Consequently, on the event where the well-specified bound $|\tilde f-\mu_{t-1}|\le\beta_t\sigma_{t-1}$ holds (with $\beta_t$ computed for $\|\tilde f\|_k\le B$), the triangle inequality gives

(the lemma with $t-1$ observations gives the factor $\epsilon\sqrt{t-1}/\sqrt\lambda$; the display uses the slightly larger $\epsilon\sqrt t/\sqrt\lambda$): the enlarged width of their EC-GP-UCB rule (eq. 15) plus the pointwise misfit $\epsilon$, which matters for safety because the constraint is on $f^*$, not on $\tilde f$. In the regret this costs an extra $O(\epsilon T\sqrt{\gamma_T})$ term in the proved upper bound (Theorem 1), and they show that an $\Omega(\epsilon T)$ dependence is unavoidable for any algorithm (Appendix C). For safety the point is that the enlargement does not vanish with data: the band never gets narrower than $\epsilon$ and its multiplier $\epsilon\sqrt t/\sqrt\lambda$ grows with $t$, so a safe set built from the unenlarged band is over-confident by an amount that more data cannot remove. Whether $\epsilon$ is known is the same problem as whether $B$ is known.

Noise that is not sub-Gaussian

All martingale bounds above need $\mathbb E[e^{\alpha\varepsilon_t}\mid F_{t-1}]\le e^{\alpha^2R^2/2}$. A common $R$ already covers heteroscedastic noise (noise whose scale depends on the input or the history; see Primer C) as long as every conditional law is $R$-sub-Gaussian (at the price of using the worst noise level everywhere). Polynomial-tailed disturbances without finite exponential moments violate it (occasional large observations alone do not show this: Gaussian noise produces outliers too), and then nothing above applies; then either bounded noise (deterministic statements, Module 5) or estimators with their own concentration results are needed. Fiedler et al. 2021 stress that their construction is flexible in the underlying concentration result (their Proposition 2 already swaps in a $\chi^2$-type bound), so the architecture survives whenever a suitable inequality exists for the noise class at hand. A scenario-based route is taken by Tokmak, Schön & Baumann (IEEE Control Systems Letters, accepted; arXiv 2025): they bound the measurement noise itself with high probability via the scenario approach, for noise models up to heteroscedastic heavy-tailed ones, insert that bound into the confidence intervals, and prove safety and optimality of the resulting safe BO algorithm.

Open problems

• A principled way to turn engineering knowledge (amplitude, slope, bandwidth of a plant) into a bound on $\|f\|_k$, or a kernel whose norm has physical meaning; the available remedies are data-driven over-estimates that rest on i.i.d.-type assumptions (Tokmak et al., PACSBO).
• Frequentist bounds that stay valid from the first query under unrestricted data-driven hyperparameter adaptation such as ML-II; structured adaptation such as A-GP-UCB gives regret guarantees, but only once the growing function class contains $f$.
• Tightness versus usefulness: Flynn & Reeb's sets are tighter, but how much safe region is gained per unit of tightness has, to our knowledge, not been characterised.
• Heavy-tailed noise with anytime-valid, uniform-in-$x$ guarantees beyond bounding the noise itself, and variance-adaptive bounds that exploit input-dependent noise levels instead of one worst-case $R$.

Walkthrough: Deriving the RKHS Error Bound

The central derivation of this page: from the kernel-ridge representation to $|\mu_t(x)-f(x)|\le\beta_t\sigma_t(x)$, following the proof of Theorem 2 of Chowdhury & Gopalan with the regulariser $\lambda$ kept general, so that the data-dependent bound of Fiedler et al. drops out at Step 4 and the a-priori bound at Step 5.

Interactive: GP Confidence Bands and $\beta$

A 1-D GP regression whose truth is an exact RKHS element $f=\sum_{i=1}^8c_i\,k_{\mathrm{SE}}(\cdot,z_i)$ with $\|f\|_k=\sqrt{c^\top K_zc}$ normalised to $3$ (so $|f|\le3$ by the reproducing property), so every assumption of the theorems can be met or broken on purpose.

The domain $D$ is the 201-point grid on $[0,1]$. The value $3$ is the norm of $f$ on $[0,1]$; the centres $z_i$ lie off the grid, and restricting $f$ to $D$ can only lower its norm (the minimum over all extensions, Section 1). Thus $B=3$ is a valid upper bound on the grid norm; equality is not needed for the certificate.

The $t$ inputs are drawn uniformly from $D$ (seeded and nested, so increasing $t$ adds points; repetitions are possible), with Gaussian noise of standard deviation $\sigma_n$, hence $R=\sigma_n$. The posterior is a Cholesky solve (see Primer A) of $K_t+\lambda I$.

The a-priori "Chowdhury–Gopalan type" rule is their proof with general $\lambda$, i.e. the corrected Fiedler et al. formula with the realised $\log\det(I+K_t/\lambda)$ replaced by $2\hat\gamma_t$, where $\hat\gamma_t=\tfrac{e}{e-1}I_{\mathrm{greedy}}\ge\gamma_t$ is a certified upper bound on this finite $D$ (the greedy design of Srinivas et al., which repeatedly observes the point of largest posterior variance, is within a factor $1-1/e$ of optimal by submodularity). The data-dependent rules use the realised $\log\det$. Red dots mark grid points where the true $f$ leaves the band.

The percentage of red points describes this one simulated data set; it is not an estimate of $\delta$, which bounds the probability, over repeated experiments, that the band fails anywhere at any time. Moving the length-scale slider rebuilds the true $f$ for the new $\ell$ (same centres and relative weights, norm renormalised to $3$), so it changes the experiment rather than refitting one fixed plant; each theorem concerns one fixed kernel and norm bound, not settings chosen after looking at the plot.

What to try. (i) Set $\sigma_n$ to $0$: with a valid norm bound for the working kernel, the correctly specified rules collapse to $\beta=B$, i.e. to the deterministic bias bound $B\sigma_t$ (Step 2 of the walkthrough; Section 3's bound when also $\lambda\to0$), and the band holds with certainty (the "B under-estimated" rule gives $(B/4)\sigma_t$, deliberately not certified). (ii) Lower $\lambda$ far below $\sigma_n^2$ (e.g. $0.001$): the posterior mean over-fits the noise and $\beta\equiv2$ is violated at many points, while the rigorous rules widen through $R/\sqrt\lambda$ and stay valid. (iii) Compare the a-priori and data-dependent rows of the table: the gap is $2\hat\gamma_t$ versus the realised $\log\det$ (last row). (iv) Select "B under-estimated ×0.25", raise $\lambda$ to about $1$ and keep $t\le20$: once the bias term $B\sigma_t$ dominates, the band is violated; at small $\lambda$ the noise term happens to cover the error, which is luck, not a guarantee. (v) Switch on the misspecification, set $\sigma_n=0$ and $t\ge50$: the norm bound for the original kernel does not certify the new kernel. The band may fail; whether it fails for a particular simulation is a separate numerical question (Section 7). (vi) Set $\lambda=0.001$ and compare the corrected and uncorrected AAAI rows: the uncorrected band is violated.

Exercises

Graded practice — Build the argument yourself

There are 12 new problems: four Easy, four Medium, and four Hard. Start with the level that lets you make progress without opening the solution. Easy problems rebuild individual operations; Medium problems combine them; Hard problems ask for proofs, boundary cases, and the limits of a guarantee. The required concepts are explained on this page or in the linked earlier material.

Easy — Warm up one skill at a time.

Medium — Combine definitions and compute a certificate.

Hard — Explain why the argument works and where it stops.

Further practice — Original problems and research connections

The original exercises below retain their numbering. Some compare later methods or ask for longer research derivations; use the graded set above first, and return to a research-connection problem after reading the relevant linked module.

Key Papers

Flashcards