5. Is Safe BO Actually Safe? Real-β-SafeOpt and LoSBO

The β-heuristic gap, Real-β-SafeOpt, Lipschitz-only safe BO, LoS-GP-UCB, MCLoSBO and event-triggered safe BO

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

Module 4 ended with a comfortable picture: SafeOpt certifies a growing safe set from GP confidence bounds, and Theorem 1 of Sui et al., ICML 2015 promises that all queries are safe with probability at least $1-\delta$. This module asks the uncomfortable follow-up question posed by Fiedler, Menn, Kreisköther and Trimpe, TMLR 2024: does that promise survive contact with an implementation? The answer is no, for two independent reasons, and the fix (LoSBO) is a small change to one line of the algorithm that separates safety from statistics entirely.

1. The Gap Between Theory and Practice

1.1 Where the guarantee lives

Every SafeOpt-type guarantee rests on one event. Let $Q_t(x) = [\mu_{t-1}(x) \pm \beta_t\sigma_{t-1}(x)]$, $C_t(x) = C_{t-1}(x) \cap Q_t(x)$ (see Primer 0) with $C_0(x) = [h,\infty)$ on $S_0$ and $C_0(x) = \mathbb{R}$ elsewhere, $\ell_t = \inf C_t$, $u_t = \sup C_t$. Define the good event (see Primer C)

The endpoints are infima and suprema because the initial intervals are unbounded: $\mathbb{R}$ has endpoints $\mp\infty$, and $[h,\infty)$ has endpoints $h$ and $+\infty$. Since $Q_1 = [\mu_0 \pm \beta_1\sigma_0]$ is already bounded, $\ell_t$ and $u_t$ are finite for all $t \ge 1$ unless the intersection is empty (Section 3). Algorithm 3 below uses no prior band ($Q_0 = \mathbb{R}$): in its first round every width is infinite, and the first query is a seed point picked by a tie-break.

Everything downstream of $\mathcal{E}_\delta$ is deterministic: on $\mathcal{E}_\delta$ the Lipschitz expansion $S_t = \bigcup_{x \in S_{t-1}}\{x' : \ell_t(x) - L\,d(x,x') \ge h\}$ only ever adds points with $f(x') \ge f(x) - L\,d(x,x') \ge \ell_t(x) - L\,d(x,x') \ge h$. The only probabilistic statement in the whole theory is $\mathbb{P}[\mathcal{E}_\delta] \ge 1-\delta$, and that statement is a theorem about $\beta_t$, not about the algorithm. The walkthrough below spells this out step by step, because the next two subsections are about what happens when the theorem is not applied.

Three bounds (on their stated time ranges) of the form $\nu(x) = \beta\,\sigma(x)$ certify $\mathcal{E}_\delta$ for a fixed $f \in \mathcal{H}_k$ (frequentist setting: $f$ is not random, only the noise is; see Module 3 and Primer C). In the convention of this module ($\|f\|_k \le B$, $\beta$ multiplies $\sigma$ directly) and with the time indices of the sources: the Srinivas and Chowdhury–Gopalan multipliers $\beta_t$ are stated for $\sigma_{t-1}$, the posterior after $t-1$ observations (as in $Q_t$ above), eq. (7) for $\sigma_t$, with $K_t$ the Gram matrix of $t$ observations. Written for the same posterior, the first two simply shift $t \to t+1$.

Reading the table: “a.s.” (almost surely) means with probability one; “given the past” means conditionally on everything known before the current query; conditional sub-Gaussianity (Section 2) bounds the tails of the noise through $R$, not its largest value. To compare the rows for one posterior, say after $n$ observations, use the Srinivas and Chowdhury–Gopalan multipliers with index $n+1$ and eq. (7) with index $n$, and compute each $\gamma$ with the $\lambda$ that its own theorem prescribes. The “$+1$” of Chowdhury–Gopalan uses $\eta t \le 2$, so with $\eta = 2/T$ that row certifies the event only for $t \le T$, not for all $t \ge 1$.

1.2 The β problem

To the best of Fiedler et al.'s knowledge, no implementation of SafeOpt or its variants before their paper evaluated any of these $\beta_t$; all used heuristics. They document the constants actually used: $\beta_t \equiv 2$ in Berkenkamp, Schoellig & Krause, ICRA 2016 and in SafeMDP (Turchetta et al., NeurIPS 2016), $\beta_t \equiv 3$ in Helwa et al. 2019 and in GoSafe (Baumann et al., ICRA 2021), $\beta_t \equiv 4$ in GoSafeOpt (Sukhija et al., AIJ 2023). These are multipliers of $\sigma$, the convention of Fiedler et al. and of this module. Two of the papers print their band as $\mu \pm \beta^{1/2}\sigma$ instead: SafeMDP sets $\beta_t = 2$ and GoSafe $\beta_n \equiv 3$, which read literally would be multipliers $\sqrt2$ and $\sqrt3$. The code settles it. SafeMDP's public implementation (befelix/SafeMDP) multiplies $\sigma$ by beta $= 2$ directly. GoSafe's implementation builds on the SafeOpt package (befelix/SafeOpt), whose beta likewise multiplies $\sigma$ directly (default 2), so its 3 is presumably a multiplier of $\sigma$ too. The group's own event-triggered quadcopter work (Section 6) also uses $\beta \equiv 2$. The usual justification is conservatism: in the words of the SafeOpt-MC paper (Berkenkamp, Krause & Schoellig, ML 2023), the theoretical $\beta_n$ "may be impractically conservative for experiments", and a constant $\beta$ "roughly corresponds to bounding the failure probability per iteration, rather than over all iterations" (SafeMDP argues the same for its $\beta_t = 2$).

How often does the tube break? Fiedler et al. sample 100 functions from the RKHS of a squared-exponential kernel (length scale $0.2/\sqrt{2}$, domain $[-2,2]$, RKHS norm exactly 10, built from the RKHS orthonormal basis), draw $10^4$ datasets per function (100 uniformly sampled inputs, i.i.d. Gaussian noise of variance $0.01$, i.e. standard deviation $0.1$), fit the GP with the correct kernel and check on a fine grid whether $f$ lies inside $\mu \pm 2\sigma$. Result: $2727 \pm 3882$ of the $10^4$ datasets per function (mean $\pm$ SD over functions) violate the tube. Running SafeOpt with $\beta \equiv 2$ on one such function from a random safe start gave $2862$ unsafe runs out of $10^4$.

An orthonormal basis $(b_j)$ of $\mathcal{H}_k$ consists of mutually orthogonal functions of unit RKHS norm, so $f = \sum_j c_jb_j$ has $\|f\|_k^2 = \sum_j c_j^2$, and a prescribed norm is reached by rescaling the coefficients (Primer A); i.i.d. means independent and identically distributed (Primer C).

1.3 The RKHS-norm problem

Suppose we do evaluate a rigorous $\beta_t$. All three formulas above need $B \ge \|f\|_k$ (Assumption 2 of the paper), and a justified RKHS-norm upper bound is particularly difficult to supply from engineering knowledge. Fiedler et al. survey the known characterizations and conclude that, to the best of their knowledge, none currently turns realistic prior knowledge into a numerical upper bound in non-trivial cases:

• Variational / discretization characterizations (maximization over families of lower bounds, minimum-norm interpolation problems, matrix inequalities): explicit, kernel-agnostic, but they need exact function values and can only produce lower bounds numerically (the minimum-norm interpolant of any finite data set has a norm no larger than that of $f$).
• Mercer / weighted $\ell^2$ representation for continuous kernels on compact spaces (see Primer 0): explains the regularization behaviour of kernel machines, requires the full coefficient sequence to give a number.
  Background — Mercer coefficients

  The idea is the function-space version of diagonalizing a symmetric matrix. For a continuous positive semidefinite kernel on a compact set (integrals taken with a finite measure that gives every non-empty open set positive mass), Mercer's theorem gives $k(x,x')=\sum_j\lambda_j e_j(x)e_j(x')$ with eigenvalues $\lambda_j \gt 0$ and eigenfunctions $e_j$ that are orthonormal in $L^2$, the space of square-integrable functions (the rescaled $\sqrt{\lambda_j}e_j$ are orthonormal in $\mathcal{H}_k$). A function $f=\sum_j a_j e_j$ lies in $\mathcal{H}_k$ iff $\|f\|_k^2=\sum_j a_j^2/\lambda_j \lt \infty$, so components along eigenfunctions with small $\lambda_j$ are expensive. Example: $(a_1,a_2)=(1,1)$ with $(\lambda_1,\lambda_2)=(1,\tfrac14)$ contributes $1+4=5$ to $\|f\|_k^2$. The formula needs the whole coefficient sequence; finitely many measured values say nothing about its unobserved tail, which is why it yields no upper bound.

• Fourier representation for translation-invariant kernels: $\|f\|_k$ is a weighted energy of $\hat f$ that penalizes high frequencies; Sobolev spaces (norms that measure the energy of derivatives) and Fock spaces (Gaussian-weighted spaces of analytic functions, a specialist example not needed below) have analogous formulas. These formulas alone do not turn finite observations into an upper bound.

Worse, $f \in \mathcal{H}_k$ is itself delicate: for squared-exponential kernels the RKHSs for different length scales are different spaces (Steinwart & Christmann, Sect. 4.4), so a wrong length scale can push the norm to infinity, and hyperparameters are routinely re-fitted during BO. Both over- and under-estimating $B$ hurt: too small voids the guarantee silently, too large freezes the safe set. With a misspecified $B = 2.5$ (true norm 10) Real-$\beta$-SafeOpt (Section 2) produced $1338$ unsafe runs out of $10^4$ on the test function, against a promised $\delta = 0.01$.

1.4 Which noise?

The three bounds also differ in what they assume about $\epsilon_t$. Sui et al. inherit Srinivas' Theorem 6, which needs noise that is zero-mean given the past and uniformly bounded by $\sigma$, while the GP likelihood is Gaussian (a deliberately misspecified but frequentist-valid model, see Module 3). Chowdhury–Gopalan and Abbasi-Yadkori allow conditionally $R$-sub-Gaussian martingale differences, which covers bounded zero-mean and Gaussian noise. LoSBO (Section 3) will need a hard bound $|\epsilon_t| \le E$, which Gaussian noise violates with positive probability. Keep the three models apart: zero-mean bounded (Srinivas) $\subset$ conditionally sub-Gaussian (Chowdhury–Gopalan, Abbasi-Yadkori), whereas LoSBO's hard bound needs neither zero mean nor a martingale structure (a bounded bias is allowed) but excludes Gaussian noise; only the hard bound supports a deterministic guarantee.

1.5 The numbers

Table 1 of the paper is the empirical core of this module. Setup: 100 functions from the SE-kernel RKHS with $B = 10$, each algorithm run $10^4$ times per function for 20 iterations from a random initial safe point (the table caption says two initial safe points, the text of Sect. 6.3 describes a singleton seed drawn from the plateau around the maximizer where $f \ge h + E$); the threshold is $h = \hat\mu(f) - 0.2\,\widehat{\mathrm{SD}}(f)$ (empirical mean and standard deviation of $f$ on a fine grid); $L$ is $1.1\times$ the numerically computed maximum slope; noise uniform on $[-B_\epsilon, B_\epsilon]$ with $B_\epsilon = 0.01$ (Sect. 6.3; the single-function $\beta \equiv 2$ experiment of Sect. 5.1, whose 2862 unsafe runs per $10^4$ match the worst-function entry 28.62%, used Gaussian noise of variance 0.01); $\delta = 0.01$. The paper (arXiv v1) does not define "not started"; we read it as runs that never left their initial safe points. "Final performance" is $\hat f^*_t = \big(f(\arg\max_{x\in S_t}\mu_t(x)) - h\big)/(f^* - h)$.

Here $f^*=\max_{x\in D}f(x)$ (assumed $\gt h$), so the score is $0$ when the recommended point $\tilde x_t\in\arg\max_{x\in S_t}\mu_t(x)$ sits exactly at the threshold and $1$ when it is a global maximizer. It scores a posterior-mean recommendation; SafeOpt's exploration theorem (Section 3.2) is about a different point, $\hat x_t\in\arg\max_{x \in S_t}\ell_t(x)$, and a reachable rather than global optimum.

2. Real-β-SafeOpt

The first fix is the obvious one: run SafeOpt (Algorithm 2 of the paper, i.e. Sui et al.'s original with Lipschitz expansion) but actually compute a valid $\beta_t$. Fiedler et al. call this Real-$\beta$-SafeOpt and use the a-posteriori bound that follows from Theorem 3.11 and Remark 3.13 of Abbasi-Yadkori's 2013 thesis, the RKHS version of the self-normalized inequality of Abbasi-Yadkori, Pál & Szepesvári, NeurIPS 2011.

Why each assumption matters. Positive definiteness of $k$ is part of the setting in which Fiedler et al. state eqs. (6)–(7) (it makes $K_t$ invertible for distinct inputs). Predictability of $x_t$ is what allows the bound inside a closed loop (BO chooses $x_t$ from past $y$'s, never from the noise of the current measurement); it is paid for by the martingale structure of the noise. Sub-Gaussianity gives the exponential supermartingale behind the method of mixtures (Module 3, confidence bounds). The nominal $\lambda$ is a free algorithmic choice; it is not the physical noise variance, and the factor $1/\sqrt{\lambda}$ shows that under-regularizing is penalized.

2.1 The algorithm and its cost

Real-$\beta$-SafeOpt is Algorithm 2 of the paper with line 17 ("compute updated $\beta_t$") implemented as an evaluation of eq. (7): after each update, compute the Cholesky factor (see Primer A) of $I_t + \lambda^{-1}K_t$, read off $\ln\det$ as twice the sum of the log-diagonal, and form $Q_t(x) = [\mu_t(x) \pm \beta_t\sigma_t(x)]$. The $O(t^3)$ cost of the determinant (Primer 0) is irrelevant at the tens of evaluations typical for controller tuning. Inputs: $B$, $R$, $\lambda$, $\delta$, $L$, $S_0$, $h$. The noise must be conditionally $R$-sub-Gaussian with $R$ known; zero-mean noise bounded in $[-B_\epsilon, B_\epsilon]$ gives $R = B_\epsilon$ (Hoeffding's lemma, Primer C: a zero-mean variable with values in $[a,b]$ is $\tfrac{b-a}{2}$-sub-Gaussian).

2.2 The conservatism trade-off

With the true norm and $\delta = 0.01$, Real-$\beta$-SafeOpt made zero unsafe queries in $10^6$ runs, comfortably inside the promised $\delta$. The price is in the first row of Table 1: with $B = 10$, 30.40% of the runs are "not started" (never leave their initial points, in our reading), with $B = 20$ 68.34%. The mechanism is structural, not a bug: the certificate $\ell_t(x) - L\,d(x,x') \ge h$ needs $\ell_t(x)$ well above $h$, and the raw lower endpoint $\mu_t - \beta_t\sigma_t$ with $\beta_t \approx B$ is far below $\mu_t$ wherever $\sigma_t$ is not tiny. A safe set that cannot grow is safe in the same way a switched-off robot is.

Strictly, the lower bound actually used is the running maximum of these raw endpoints (and of $h$ on $S_0$), because $C_t$ intersects all bands so far and $[a,b]\cap[c,d]=[\max\{a,c\},\min\{b,d\}]$. A large $\beta_t$ therefore never lowers a certificate already obtained; it stops new bands from raising $\ell_t$ far enough to expand the safe set.

Real-$\beta$-SafeOpt also inherits every other assumption of Section 1: the kernel and its hyperparameters must be right (with a length scale 4$\times$ too large, the paper reports safety violations in 12.57% of all runs and in 943 of $10^4$ runs for the worst-behaving function; it does not name the algorithm, but only Real-$\beta$ can violate there, and the two numbers are inconsistent as printed in arXiv v1, since a worst-function rate of 9.43% cannot lie below an average of 12.57%), and hyperparameters may not be adapted online. Fiedler et al. are careful to note that a comparison between Real-$\beta$-SafeOpt and heuristic SafeOpt is meaningless: they solve different problems (hard safety versus cautious BO).

Interactive: How Large Is a Real β_t?

This explorer computes the three theoretical scalings on a real design: it runs uncertainty sampling (greedy maximum-variance selection, which approximates the maximal-information design) on a 200-point grid with a squared-exponential kernel, evaluates $\ln\det(I_t + \lambda^{-1}K_t)$ by Cholesky at every $t$, sets $\gamma_t \approx \tfrac12\ln\det(I_t + \lambda^{-1}K_t)$ for that design (the information gain of one design is a lower bound on $\gamma_t$, so the two $\gamma_t$-based curves are, if anything, too low), and plots $\beta_t$ on a log scale against the heuristics $2,3,4$. The Chowdhury–Gopalan curve is evaluated with your $\lambda$ for comparison, although their theorem fixes $\lambda = 1 + 2/T$.

Reading the plot. At horizontal position $t$, Real-$\beta$ uses the $t$-observation posterior, whereas the Chowdhury–Gopalan curve uses the gain after $t-1$ observations: each curve keeps its source's index. For the same $t$-observation posterior, read the Chowdhury–Gopalan curve one step to the right. The vertical axis is logarithmic (equal steps are equal ratios), and information is measured in nats because the logarithm is natural (Primer C).

3. LoSBO: Safety from a Lipschitz Constant Alone

The second fix attacks objective (O2) of the paper: safety should rest only on assumptions that the user can verify and interpret. Two such assumptions have decades of use in system identification (Milanese & Novara's set-membership bounds, Calliess' kinky inference): a bound on the slope of $f$ and a bound on the size of the measurement noise. Both are engineering quantities, related to sensitivity analysis and sensor specifications. LoSBO builds the safe set from these two alone and leaves the GP to do what it is good at, guiding exploration.

Compare with SafeOpt's Algorithm 2: the only change is the safe-set line (line 8 of the paper's Algorithms 2 and 3, line 5 of the box above), where $\ell_t(x_s) - L\,d(x_s,x) \ge h$ over all $x_s \in S_{t-1}$ became $y_{t-1} - E - L\,d(x_{t-1},x) \ge h$ for the single last query. The measurement replaces the GP lower bound; the cone is the same. Everything else, expanders, maximizers, uncertainty sampling, is untouched, so LoSBO is a drop-in change for any SafeOpt variant (the paper expects it to transfer to most of them). A note on indices: the pseudocode labels the band by the posterior it uses, $Q_{t-1} = [\mu_{t-1} \pm \beta_{t-1}\sigma_{t-1}]$, whereas Section 1.1 followed the paper's prose, which calls the same band $Q_t$ and indexes $\beta$ by the round in which it is used; both describe the same intersection $C_t = C_{t-1} \cap [\mu_{t-1} \pm \beta\,\sigma_{t-1}]$.

Neither pseudocode says what happens when that intersection is empty. With a valid $\beta$ this has probability at most $\delta$, because $f(x)$ lies in every band. With a heuristic $\beta$ a measurement can contradict an earlier band. For example, a single seed point with $f = h = 1$, $k(x,x) = 1$, $\lambda = 1$, a noise-free measurement and $\beta = 0.5$ gives $\mu_1 = 0.5$, $\sigma_1 = 1/\sqrt2$ and an upper band end $0.854 \lt h$, so $C_2 = [h,\infty) \cap Q_1 = \emptyset$. Then $\ell_t$, $u_t$ and $w_t$ are undefined, so an implementation needs an explicit rule. A naive one that keeps the crossed endpoints gets negative widths and can end up with an empty $G_t \cup M_t$. For LoSBO any rule is harmless for safety as long as queries are taken from $S_t$. Two natural choices are to restart $C_t(x)$ from the current band (the rule used by the explorer in Section 9) or to drop the intersection altogether, as SafeOpt-MC's practical version and MCLoSBO do (Section 5). For SafeOpt and Real-$\beta$-SafeOpt, an empty intersection (given a safe seed) proves that some band missed $f(x)$, so the good event $\mathcal{E}_\delta$ failed on this run. It does not prove that the assumptions are wrong: a valid $1-\delta$ theorem still allows this failure with probability up to $\delta$, and one run cannot tell the two explanations apart.

3.1 What the separation buys

• $\beta_t$ is a tuning parameter. It may be constant, adapted online, or over-optimistic; the paper runs $\beta \equiv 2$ throughout and suggests ("it appears") that this over-optimism is what makes LoSBO explore better than Real-$\beta$-SafeOpt (Table 1: 90.90% vs 82.45%).
• No RKHS norm, no kernel correctness. Assumption 2 disappears. A wrong kernel or length scale can degrade exploration but cannot cause an unsafe query; hyperparameter optimization during the run is allowed. In the misspecified experiments (Matérn functions, length scale $4\times$ or $0.2\times$ the truth, SE model on Matérn functions) LoSBO's certificate is untouched, since $L$ and $E$ remain valid, whereas the $4\times$ setting produced safety violations in 12.57% of all runs, which can only be Real-$\beta$'s (Section 2.2).
• Deterministic, not probabilistic. The bound $f(x_t) \ge y_t - E$ holds for every realization. This is the Milanese–Novara set-membership philosophy imported into BO.

3.2 What the separation costs: no exploration theorem

SafeOpt's Theorem 1 also guarantees that for all $t \ge t^*$ the point $\hat x_t = \arg\max_{x \in S_t}\ell_t(x)$ is $\epsilon$-optimal with respect to the best value on the $\epsilon$-reachable safe region $\bar R_\epsilon(S_0)$. Its proof relies on the GP model interacting with the safety mechanism: the safe set grows exactly when the lower bound at an expander rises above $h + L\,d$, and the uncertainty-sampling rule shrinks $w_t$ at expanders. In LoSBO the safe set no longer depends on the GP at all, so this coupling is gone; Fiedler et al. state that the last inequality in the proof of Sui et al.'s Lemma 7 cannot be ensured, and they suspect (but never observed) pathological cases where LoSBO under-explores. Their position is that this loss is acceptable: SafeOpt's own exploration guarantee is conditional on the kernel through the growth of $\gamma_t$ ($t^*$ is the smallest $t$ with $t/(\beta_t^2\gamma_t) \ge C_1(|\bar R_0(S_0)| + 1)/\epsilon^2$, $C_1 = 8/\ln(1 + \sigma^{-2})$ with $\sigma$ the noise bound, in this module's convention; note that the size of the larger $0$-reachable set $\bar R_0(S_0)$ sets the time, while $\epsilon$-optimality is measured on $\bar R_\epsilon(S_0)$; Sui et al. write $\beta_t\gamma_t$ for their squared multiplier, so the statement is vacuous unless $t/(\beta_t^2\gamma_t)$ grows), and LoSBO's $\beta_t$ is a free knob for fixing under-exploration when it happens. Providing exploration guarantees for LoSBO is listed as open.

3.3 Experimental evidence

The frequentist protocol of Section 1.5 (100 functions, $10^4$ repetitions each, 20 iterations, functions from the pre-RKHS (the space of finite kernel expansions) $f = \sum_i \alpha_i k(\cdot,x_i)$ or from the SE orthonormal basis, norm 10, uniform noise with $B_\epsilon = 0.01$, $R = B_\epsilon$, nominal noise variance $\lambda = R$, $\delta = 0.01$, $E = 2B_\epsilon$, $\beta \equiv 2$ in LoSBO) gives the LoSBO column of Table 1: never a violation, essentially never stuck (0.018%), best final performance. Two details are worth remembering for your own experiments: the target functions are generated in two ways for variety, and ONB samples turn out "bumpier" and harder for the bounds than pre-RKHS samples; and Matérn-3/2 functions are slightly harder for both algorithms, which the authors relate to their lower smoothness (both algorithms rely on a Lipschitz bound, which is tied to regularity).

4. LoS-GP-UCB: Dropping the Grid

Objective (O3) of the paper is scalability. Computing SafeOpt's sets exactly needs a discrete $D$: expanders count the points of $D \setminus S_t$ that an optimistic observation would certify, maximizers compare $u_t$ against a maximum over $S_t$. On a continuous domain the enumerated implementations therefore grid, and dense grids quickly become impractical as the dimension grows (the motivation for LineBO, Kirschner et al., ICML 2019, and for GoSafeOpt). A fixed grid is not intrinsic to every SafeOpt-type method, though: the swarm-based SafeOpt of Duivenvoorden et al., IFAC 2017 (SafeOptSwarm, built on the Lipschitz-free SafeOpt) searches a continuous parameter space and approximates the sets with particle swarms, an adaptive discretization; Fiedler et al. note that it comes with only heuristic safety guarantees. LoSBO as stated in Algorithm 3 enumerates its sets and inherits the grid. Fiedler et al. remove it with three observations.

A grid with $m$ values per coordinate has $m^d$ candidates, exponential in the dimension $d$ (Primer 0): with $m=100$, two dimensions give $10^4$ points and six give $10^{12}$. There is no sharp cutoff dimension; what is feasible depends on the resolution and on the cost of the acquisition and expansion tests per candidate.

1. Safety needs only a safe feasible region. Any acquisition rule restricted to a set $S$ with $f|_S \ge h$ is safe, whatever the rule and however the optimization is carried out. Expanders and maximizers were introduced for the exploration proof, not for safety.
2. LoSBO's safe sets are unions of balls. By eq. (11) and the geometric reading above,
   $$S_t = \bigcup_{j=1}^{N_t} \bar B_{r_j}(z_j), \qquad \bar B_r(z) = \{x \in D : d(z,x) \le r\},$$
   with $L\gt0$ for this radius representation (the $L=0$ case is handled in Section 3), and, for a singleton seed $x_0$ and no repeated inputs, $z_1 = x_0$ (radius 0) and $z_j = x_{j-1}$, $r_j = (y_{j-1} - E - h)/L$ for $j = 2,\dots,t+1$ (eq. 15). Balls with negative radius are empty and are dropped (and the rest relabelled), so $N_t \le t+1$, with equality when all $t$ measurements have non-negative slack. Few evaluations means few balls. Note the index shift: here, as in Section 7 of the paper, $S_t$ is the safe set available after the $t$-th observation (it would be $S_{t+1}$ in Algorithm 3), which is why $x_{t+1}$ is chosen from $S_t$ below.
3. Modern BO does not grid. Acquisition functions are maximized by multi-start local (gradient-based) optimization (see Primer B), which copes with moderate dimensions; BoTorch does this by default.

Why the split is exact, and what the solver really returns. Every point of $S_t$ lies in at least one ball, so $\sup_{x\in S_t}a_t(x)=\max_j\sup_{x\in\bar B_{r_j}(z_j)}a_t(x)$; each supremum is attained when $D$ is compact and $a_t$ is continuous, and “$\in\arg\max$” means picking any one maximizer (Primer B). The feasible ball is convex, but the problem is not: $a_t$ is generally not concave, so multistart local search returns good candidates, not certified global maxima. Safety does not care: any returned point that lies in a certified ball is safe.

LoS-GP-UCB keeps Proposition 1 verbatim (the query is always in $S_t$), needs no RKHS norm bound, and Remarks 2 and 3 apply. Its exploration behaviour is the interesting question: Sui et al. already tested a "Safe-UCB" variant of GP-UCB restricted to the certified set and found that it can get stuck at low-value boundary points that it never expands. In the 1-D comparison of Fiedler et al. (100 Matérn-3/2 pre-RKHS functions, 1000 runs each, $\beta \equiv 2$), LoS-GP-UCB is only slightly worse than LoSBO and still better than Real-$\beta$-SafeOpt, and the authors attribute the absence of severe under-exploration to the optimism of $\beta \equiv 2$. On benchmarks without a discrete alternative (Camelback in 2-D, Hartmann in 6-D, a Gaussian bump $\exp(-4\|x\|_2^2)$ in 10-D; SE kernel with output variance 1, length scale $1/L$, prior mean $0.5$, noise level $0.01$, 100 iterations, 100 repetitions) it outperforms random search started from the same initial safe set (Fig. 8 of the paper).

5. Multiple Constraints and Automotive Control

Controller tuning (see Primer D) rarely has a single safety requirement on the objective. SafeOpt-MC (Berkenkamp, Krause & Schoellig, ML 2023) and StageOpt (Sui et al., ICML 2018) handle $q$ unknown constraint functions $g_i(\theta) \ge 0$, but through GP bounds, hence with RKHS-norm bounds for every $g_i$ and probabilistic guarantees. Menn, Pelizzari, Fleps-Dezasse & Trimpe, CDC 2024 transplant the LoSBO safe set into that setting; the result, MCLoSBO, was tuned on a real car.

5.1 Setting and assumptions

Parameters $\theta \in \Theta \subseteq \mathbb{R}^d$ (the paper's $\theta$ is our $x$), objective $f$ and constraints $g_i$, $i \in I_g = \{1,\dots,q\}$, with thresholds normalized to zero. Every query returns noisy values of all functions, $y_{0,n} = f(\theta_n) + \epsilon_{0,n}$ and $y_{i,n} = g_i(\theta_n) + \epsilon_{i,n}$, each modelled by its own GP. The requirement is $g_i(\theta_n) \ge 0$ for all $i$ and all $n$. Assumption 1: each $g_i$ is $L_i$-Lipschitz, $|g_i(\theta) - g_i(\theta')| \le L_i\|\theta - \theta'\|$. Assumption 2: $|\epsilon_{i,n}| \le E_i$. A safe seed $\theta_0$ is given. The constants are per constraint, which matters: a stability-type constraint may be much steeper than a tracking-error constraint.

The parameter vector $\theta$ specifies one feedback controller (for example, its gains). During one experiment the physical state evolves under that fixed controller; a trajectory is then reduced to scalar objective and constraint measurements. The BO iteration index counts experiments, not the small time steps within a trajectory.

Relative to SafeOpt-MC's Algorithm 1, two things changed. The first is the safe set. The second is easy to miss: the bounds are the current GP confidence intervals $Q_n(\theta,i) = [\mu_{n-1}(\theta,i) \pm \beta\sigma_{n-1}(\theta,i)]$ themselves, with a tuning factor $\beta$, so that $l_{i,n}(\theta) = \mu_{n-1}(\theta,i) - \beta\sigma_{n-1}(\theta,i)$ and $u_{i,n}(\theta) = \mu_{n-1}(\theta,i) + \beta\sigma_{n-1}(\theta,i)$ (the paper's eq. (6) and the definitions after it). There is no intersection $C_n = C_{n-1} \cap Q_n$ over time. SafeOpt-MC's own practical version (its Section 4.3) drops the intersection as well. Since these bounds never enter the safe set, dropping the intersection costs nothing in safety, and the empty-intersection problem of Section 3 cannot arise. They drive the rest: maximizers $M_n = \{\theta \in S_n : u_{0,n}(\theta) \ge \max_{\theta' \in S_n} l_{0,n}(\theta')\}$ (objective only), expanders $G_n = \{\theta \in S_n : e_n(\theta) \gt 0\}$ with $e_n(\theta) = |\{\theta' \in \Theta\setminus S_n : \exists i \in I_g,\ u_{i,n}(\theta) - L_i\|\theta - \theta'\| \ge 0\}|$ (the paper's eq. (7) and Algorithm 1 print $e_n(\theta) \ge 0$, as does the algorithm box of SafeOpt-MC; for a cardinality that would make every safe point an expander, and SafeOpt-MC's own definition, its eq. (13), uses $\gt 0$). The count $e_n(\theta)$ is optimistic and per constraint: it counts uncertified points that an optimistic measurement of at least one constraint at $\theta$ could certify for that constraint, not points that would become jointly safe. The acquisition picks the most uncertain function at the most uncertain point, $\theta_n = \arg\max_{\theta \in G_n \cup M_n}\max_{i \in \{0\}\cup I_g}\ u_{i,n}(\theta) - l_{i,n}(\theta)$. With $q = 1$ and $g_1 = f$ this recovers LoSBO's setting and safety rule (the paper says it recovers "the setting of LoSBO"). The acquisition, however, then uses the current bands $Q_n$ instead of the intersected $C_t$ of Algorithm 3, so the two algorithms need not query the same points.

As in LoSBO, the count $|\cdot|$ in $e_n$ and the $\arg\max$ of the acquisition only make sense on a finite candidate set, so the enumerated algorithm replaces $\Theta$ there by a grid $\Theta_{\mathrm{grid}}$ (then $|A|$ is the number of grid points in $A$, and a maximizer exists); the Lipschitz certificates themselves remain valid on all of $\Theta$.

5.2 Practical adaptations

• Asynchronous experiments. On a driving vehicle there is no pause between experiments to wait for the optimizer. MCLoSBO uses a batch acquisition with a pending parameter $\tilde\theta$: since $\sigma_n$ does not depend on $y$, a virtual data point $(\tilde\theta, \mu_n(\tilde\theta))$ is added to the GP before evaluating the acquisition, which discourages re-querying near $\tilde\theta$. The safe set, however, is computed only from points with measured values, so safety is untouched.
  Derivation — what the virtual observation does to $\mu_n$ and $\sigma_n$

  Let $c_n(\theta,\theta')$ be the current posterior covariance of one GP (so $c_n(\theta,\theta)=\sigma_n^2(\theta)$) and add a virtual observation $\tilde y$ at $\tilde\theta$ with noise variance $\lambda$. Conditioning the Gaussian posterior on it (Primer C) gives

  $$\mu_{\mathrm{new}}(\theta)=\mu_n(\theta)+\frac{c_n(\theta,\tilde\theta)\,\big(\tilde y-\mu_n(\tilde\theta)\big)}{\sigma_n^2(\tilde\theta)+\lambda},\qquad \sigma_{\mathrm{new}}^2(\theta)=\sigma_n^2(\theta)-\frac{c_n(\theta,\tilde\theta)^2}{\sigma_n^2(\tilde\theta)+\lambda}.$$

  The variance update does not contain $\tilde y$ (this is what “$\sigma_n$ does not depend on $y$” means), and the choice $\tilde y=\mu_n(\tilde\theta)$ makes the mean update vanish. So points correlated with $\tilde\theta$ look less uncertain to the acquisition, as if $\tilde\theta$ had been explored, without any invented change in the predicted values; the virtual value never enters the safe set.

• Hyperparameter optimization. Marginal-likelihood fitting (see Primer C) of length scales and output scales during the run is allowed for the same reason. The authors point out that hyperparameter optimization inside SafeOpt-MC has led to safety violations in earlier controller-tuning work (safe model-free adaptive control, and controller design with the parameter-space approach), precisely because there the covariance function is the safety mechanism.
  Background — marginal-likelihood fitting

  Collect the kernel hyperparameters (length scales, output scale) in $\omega$. Under a zero-mean GP prior with kernel $k_\omega$, the vector $\mathbf{y}$ of the $n$ observations of one function is Gaussian, $\mathbf{y}\sim\mathcal N(0,K_\omega+\lambda I_n)$, because the unknown function values have been integrated out (hence “marginal”). Fitting chooses $\omega$ to maximize the log of this density, $-\tfrac12\mathbf{y}^\top(K_\omega+\lambda I_n)^{-1}\mathbf{y}-\tfrac12\ln\det(K_\omega+\lambda I_n)-\tfrac n2\ln(2\pi)$: the first term rewards fitting the data, the second penalizes overly flexible kernels.

5.3 The automotive application

The task is lateral trajectory tracking on a closed test track with two straights and two turns (about 55 km/h on the straights). The controller is a rear-axle tracking controller with three free parameters, treated as a black box. With cross-track error $e_{ct}$ (lateral distance to the reference path) and course-angle error $e_{ca}$, one experiment is scored by the cost

and BO maximizes $f(\theta) = -\mathrm{cost}(\theta)$ (the paper writes $f$ for the cost itself and flips the sign for the optimization). The window $[T_0,T_1)$ covers one straight and the turns; the sum adds metres and radians, so it is a designed score rather than a physical quantity. The two safety constraints are $g_1(\theta) = 2\,\mathrm{m} - \max_{t\in[T_0,T_1)}|e_{ct}(t)|$ (stay on the track) and $g_2(\theta) = 0.2\,\mathrm{rad/s} - \max_{t \in [T_1,T_2)}|\dot\psi(t)|$, where $\psi$ is the yaw (heading) angle and $\dot\psi$ the yaw rate, measured in the window $[T_1,T_2)$ after a virtual 1 m cross-track disturbance injected at $T_1$ on the long straight, emulating side wind. The second constraint catches controllers that track corners well but oscillate on straights, a real hazard when tuning on the vehicle.

6. Event-Triggered and Time-Varying Safe BO

All safe sets so far assume $f$ is fixed. Wear, payload changes or a re-tuned inner loop shift the objective, and a parameter certified safe last week may be unsafe today. Two responses exist: model the drift (time-varying BO), or detect it and start over (event triggering). The Trimpe group has done both, and the event-triggered route leads to the group's safe variant.

6.1 ET-GP-UCB: a GP error bound as an event trigger

Brunzema, von Rohr, Solowjow & Trimpe, TMLR 2025 work in the Bayesian time-varying setting of Bogunovic et al.: $f_t = \sqrt{1-\varepsilon}\,f_{t-1} + \sqrt{\varepsilon}\,g_t$ with i.i.d. $g_t \sim \mathcal{GP}(0,k)$, $k \le 1$, i.i.d. Gaussian noise $w_t \sim \mathcal{N}(0,\sigma_n^2)$ and an unknown rate of change $\varepsilon$. Instead of forgetting at a rate that requires $\varepsilon$, ET-GP-UCB treats $f$ as static, runs GP-UCB, and resets the dataset when an observation is inconsistent with the posterior (see Primer C). The trigger is an error bound, in the spirit of event-triggered learning (Solowjow & Trimpe, Automatica 2020): learn only when the data say the model is wrong.

Resets are confined to a window $[\underline N, \bar N]$ of steps since the last reset (a forced reset at $\bar N$), and the paper's Theorem 1 and Corollary 1 bound the regret of GP-UCB under any reset strategy inside such a window, which is how ET-GP-UCB inherits guarantees without knowing $\varepsilon$. Regret is now dynamic: each query is compared with the optimum of its own round, $R_T=\sum_{t=1}^T[\max_{x\in D}f_t(x)-f_t(x_t)]$. For fixed $\varepsilon \gt 0$ no algorithm achieves sublinear regret (Bogunovic et al. prove an $\Omega(\varepsilon T)$ lower bound), so the bound below is linear in $T$ with an explicit dependence on $\varepsilon$; for $\varepsilon = 0$ and $\underline N = T$ (no resets) it recovers GP-UCB's sublinear rate. It is a performance statement, not a safety certificate.

6.2 ETSO: event-triggered SafeOpt on quadcopters

Holzapfel, Brunzema & Trimpe, L4DC 2024 combine the trigger with safe BO for controller tuning under unknown mode changes $\xi_t$ of the closed loop (minimum dwell time between changes). The performance $J_{\xi_t}(\theta)$ must stay above a mode-dependent threshold $J_{\min,t}$. Assumption 1: a backup controller $\theta_B$ (typically the manufacturer's robust default) is safe for all modes, with a safe neighbourhood, $J_{\xi_t}(\theta_B) - \epsilon \ge J_{\mathrm{crit}}$. ETSO runs the practical SafeOpt of Berkenkamp et al. 2016 for $T_L$ learning rounds, monitored at every step by the trigger of Definition 1 (test $\psi_t = |\hat J_t - \mu_{D_t}(\theta_t)|$, threshold $\kappa_t = \sqrt{\rho_{t'}}\sigma_{D_t}(\theta_t) + \bar w_{t'}$ with $t'$ the steps since the last reset), then exploits $\arg\max_{\theta \in S_t}\mu_t(\theta)$. When the trigger fires:

1. apply the backup controller $\theta_B$ and observe $\hat J_B$;
2. reset the data set to $D_{t+1} = \{(\theta_B, \hat J_B), (\theta_t, \hat J_t)\}$, which resets the safe set;
3. recompute the threshold $J_{\min,t}$ from $\hat J_B$ and restart safe exploration ($t' \leftarrow 2$).

Assumption 2 asks that every performance-relevant change is detected and that the parameters in use at the moment of change are at least critically stable in the new mode; under Assumptions 1 and 2, Corollary 3 states that ETSO stays safe across time variations, by chaining the stationary SafeOpt guarantee across the segments between resets.

The experiments are nonetheless instructive. In simulation with the attitude-controller gains multiplied by 0.65 (AC.65), SafeOpt without a budget limit (SafeOpt$^\infty$) crashed in 50 of 50 runs after the change, while ETSO detected the change in all 50 runs, reset to the backup and had no crash (the budget-limited SafeOpt, which only exploits after its $T_L$ learning rounds, had none either). On hardware (AC.40, attitude gains multiplied by 0.4) SafeOpt crashed in 2 of 10 runs and SafeOpt$^\infty$ in 2 of 10; ETSO reset in 9 of 10 runs and never crashed. For an insignificant trajectory change (2DTV) the trigger never fired on hardware (0 of 10 runs; the simulation figure reports 2 resets in 50 runs), so ETSO behaved like SafeOpt.

6.3 Modelling the drift instead: UI-TVBO

The alternative is to keep all data and let the model forget. Brunzema, von Rohr & Trimpe, CDC 2022 observe that in controller tuning changes are typically incremental and lasting (wear), not mean-reverting, and that the tuning objective is often convex in the parameters. Their UI-TVBO models the objective as a spatio-temporal GP on inputs $(\theta,t)$ with a Wiener-process temporal kernel,

which injects uncertainty linearly in time between queries without pulling the mean back to the prior (contrast: back-to-prior forgetting with a stationary temporal kernel). Convexity is encouraged through GPs with linear inequality constraints: nonnegative second derivatives, enforced coordinate-wise at finitely many virtual observation points, which, as the authors note, does not enforce a positive semidefinite Hessian (Primer B) in more than one dimension. The benefit reported is fewer unstable controllers tried during online tuning, a safety lever even without a formal safe set. The 2026 review of Stenger et al. places these time-varying and event-triggered variants in the wider landscape of BO for controller tuning.

7. Consequences for Control and Open Problems

The thesis of this module in one sentence, from Fiedler et al.: in the hard-safety setting, safety should rest only on assumptions that practitioners judge reliable, that have a clear interpretation, and that connect to established prior knowledge in the application area. Lipschitz constants and noise bounds pass that test; RKHS norms, kernels and hyperparameters do not. The short companion paper "Safety in safe Bayesian optimization and its ramifications for control" (Fiedler, Menn and Trimpe, SysDO 2024, arXiv 2501.13697) restates this for the control audience; cite the TMLR paper for the results.

7.1 Open problems

• Estimating the RKHS norm. Data only give lower bounds (minimum-norm interpolation), and queries needed for estimation must already be safe. Tokmak et al. (AISTATS 2025) over-estimate $\|f\|_k$ by comparing with random RKHS functions in a sampling-and-discarding scenario programme (theorem box above; the general scenario approach follows in Module 15), which is rigorous but rests on the assumption that $\|f\|_k$ is an i.i.d. sample from the same distribution as the comparison functions. PACSBO (Tokmak, Schön & Baumann, SysDO 2024) estimates an upper bound on the RKHS norm from data in a probably-approximately-correct sense and treats the norm locally, much as Lipschitz methods use local slopes. The 2026 preprint of Wenzel, Tokmak and Fiedler (arXiv 2605.20091) uses superconvergence of kernel interpolation (for targets smoother than a typical RKHS member, the interpolation error in the RKHS norm decays like a power of the sample spacing) for sampling-based norm estimation, assuming noise-free and safe access to the target function (a setting that arises, e.g., in approximate MPC), not the noisy, safety-constrained queries of safe BO. None of these yet delivers the "engineering-knowledge" bound that Real-$\beta$-SafeOpt would need.
  Going deeper — the superconvergence theorem behind the 2026 estimator (optional)

  Setting (their Assumption 1): $\Omega \subset \mathbb{R}^d$ is a compact Lipschitz region, and $k$ is continuous and strictly positive definite with $\mathcal{H}_k(\Omega)$ norm-equivalent to the Sobolev space $H^\tau(\Omega)$, $\tau \gt d/2$ (e.g. Matérn kernels, not the SE kernel). With the Mercer eigenpairs $(\lambda_j, e_j)$ of $k$ on $L^2(\Omega)$, the power space $(\mathcal{H}_k)^{\vartheta}$ contains the $f$ with $\sum_j \langle f, e_j\rangle_{L^2}^2/\lambda_j^{\vartheta} \lt \infty$: $\vartheta = 1$ is the RKHS itself, $\vartheta \gt 1$ means extra smoothness. Theorem 2 (forward direction): if $f \in (\mathcal{H}_k)^{\vartheta'}$ for all $\vartheta' \lt \vartheta$, where $\vartheta \in (1,2]$, then for every $\vartheta' \lt \vartheta$ there is a constant $C$ such that for all finite point sets $X \subset \Omega$ the kernel interpolant $s_{f,X}$ of the exact values satisfies $\|f - s_{f,X}\|_k \le C\,h_X^{(\vartheta'-1)\tau}$, where the fill distance $h_X = \sup_{x \in \Omega}\min_{x_i \in X}\|x - x_i\|$ is the largest distance from a point of $\Omega$ to its nearest sample. Since $s_{f,X}$ is the orthogonal projection of $f$ onto the span of the $k(\cdot,x_i)$, Pythagoras gives $\|f\|_k^2 = \|s_{f,X}\|_k^2 + \|f - s_{f,X}\|_k^2$, so the computable $\|s_{f,X}\|_k$ approaches $\|f\|_k$ at an algebraic rate in $h_X$, which their estimator exploits. The constant $C$ is unknown and exact function values are needed, which is why this does not yet give a numerical bound for noisy safe BO. Wenzel, Tokmak & Fiedler, Theorem 2.

• Hyperparameter adaptation with guarantees. Online length-scale fitting changes the RKHS; theory for uncertainty bounds under adapted hyperparameters is only emerging (the TMLR paper points to Teckentrup and Karvonen et al.). A-GP-UCB (Berkenkamp, Schoellig & Krause, JMLR 2019) keeps sublinear regret with unknown hyperparameters by slowly enlarging the function class, but, as Fiedler et al. note, such schemes may query unsafe inputs. LoSBO sidesteps the issue for safety, not for exploration quality.
• Gaussian noise versus hard bounds. LoSBO's $|\epsilon_t| \le E$ excludes Gaussian noise; the practical remedy $E = 2B_\epsilon$ addresses false alarms, not unboundedness. A quantile-based $E$ restores a probabilistic guarantee (Exercise 5.5), which is a different promise. Heteroscedastic and asymmetric bounds are covered by Remark 2 but rarely known.
• Exploration guarantees for Lipschitz-only methods. SafeOpt's Theorem 1 does not transfer; that under-exploration of LoS-GP-UCB (the Safe-UCB effect of Sui et al.) stays mild is only an empirical finding. The optimality properties of the set-membership lower bound (Milanese & Novara) might offer a starting point.
• Connection to cautious BO. If practice runs cautious BO, then conservative bandits and cautious BO with tolerated, bounded violations (e.g. CONFIG, Xu et al., ICML 2023, which bounds cumulative violation) may be the honest theoretical frame for $\beta \equiv 2$; the TMLR paper flags this as future work.
• Transfer to other SafeOpt variants and to dynamical systems. The LoSBO modification applies to any algorithm of the generic SafeOpt class; a Lipschitz-only GoSafeOpt with backup policies certified from trajectory data (see Module 6) would combine deterministic parameter-space safety with global exploration; we are not aware that it has been done.

8. Walkthrough: The LoSBO Safety Proof

Proposition 1 is one line in the paper. Here it is taken apart inequality by inequality, because the point of LoSBO is which assumption each inequality uses, and which it does not.

9. Interactive: Break SafeOpt, Not LoSBO

A small Monte-Carlo version of the paper's Table 1 in the browser. Each run samples $N_{\mathrm{functions}}$ functions $f = \sum_{i=1}^{12}\alpha_i k(\cdot, x_i)$ from the pre-RKHS of a squared-exponential kernel (length scale $0.2$ on $[0,1]$), rescales the coefficients so that $\|f\|_k = \sqrt{\alpha^\top K\alpha}$ ($K$ the Gram matrix of the 12 centres) equals the chosen norm exactly, sets $h = \hat\mu(f) - 0.2\,\widehat{\mathrm{SD}}(f)$, computes $L_{\mathrm{true}}$ as the largest slope of $f$ (the maximum of $|f'|$ on a 401-point grid, raised if necessary to the exact Lipschitz constant of $f$ on the query grid), picks a random safe seed from the plateau around the maximizer where $f \ge h + E$, and then runs three algorithms for 25 iterations on a 40-point grid with a real GP posterior (Cholesky solves, intersection of confidence sets, expanders and maximizers as in Algorithms 2 and 3). Where a measurement contradicts an earlier band, $C_{t-1}(x) \cap Q(x)$ is empty and the algorithms are undefined (Section 3). There the explorer restarts $C_t(x)$ from the current band $Q(x)$. This keeps $\ell_t \le u_t$ everywhere, so the maximizer of $\ell_t$ over $S_t$ always lies in $M_t$ and no other fallback is needed (on the finite grid a maximizer $z$ of $\ell_t$ over $S_t$ exists, $S_t$ containing the seed, and $u_t(z) \ge \ell_t(z) = \max_{S_t}\ell_t$ puts $z$ in $M_t$); the last column of the table reports the share of runs in which a restart happened. The three algorithms are SafeOpt with a heuristic constant $\beta$, Real-$\beta$-SafeOpt with eq. (7) and $B = (\text{factor})\times\|f\|_k$, and LoSBO with $E = (\text{multiple})\times B_\epsilon$ and the same $\beta$ as its (safety-irrelevant) tuning knob. All three use the same Lipschitz constant $L = (\text{factor})\times L_{\mathrm{true}}$ (SafeOpt's expansion rule needs it too, so an under-estimated $L$ can hurt every algorithm, while an under-estimated $B$ or $\beta$ only hurts the GP-certified ones). Noise is uniform on $[-B_\epsilon, B_\epsilon]$ ($R = B_\epsilon$, nominal $\lambda = B_\epsilon$ as in the paper) or, to break LoSBO's assumption, Gaussian with $\sigma_n = B_\epsilon$. Besides violations, the table reports which share of the truly safe grid points the final safe set certifies. The absolute rates are not comparable with Table 1 (coarser grid, larger noise, 25 iterations, small $N_{\mathrm{functions}}$), and the "never expanded" column is mostly a grid effect: a seed whose margin $f - h$ is below roughly $L$ times the grid spacing cannot certify a neighbour under any of the three rules, so, unlike Table 1's "not started" row, it is often the same for all three (when it differs, it is mostly Real-$\beta$ that is left behind). The explorer illustrates the mechanisms; finite samples need not reproduce a fixed ranking.

Reading the plot. The mean and band use all 25 observations, and the band is the raw interval $\mu_{25} \pm \beta\sigma_{25}$ ($Q_{25}$ in the indexing of Algorithm 3), not the intersected $C_t$ used for acquisition. The safe-set bars show $S_{25}$, the set from which query 25 was chosen, so they include observations up to the 24th only.

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

DKW is the Dvoretzky–Kiefer–Wolfowitz inequality, Lemma 3 of Solowjow and Trimpe (with Massart's constant): for $n$ i.i.d. samples $X_i$ with CDF $F$ and empirical CDF $F_n(z) = \frac1n\#\{i : X_i \le z\}$, $\mathbb{P}\big[\sup_{z}|F_n(z) - F(z)| \gt \epsilon\big] \le 2e^{-2n\epsilon^2}$ for every $\epsilon \gt 0$, so a whole CDF is learned uniformly from samples. Their triggers compare observed and predicted distributions this way; ET-GP-UCB instead uses the GP bound of Lemma 3 above.

Flashcards