1. The Safe Learning Landscape

$4-x^2\ge0$ is equivalent to $x^2\le4$, hence $|x|\le2$ and $C=[-2,2]$. The boundary is included because the inequality is non-strict. At the three states, $h(-2)=0$, $h(1.5)=1.75$, and $h(3)=-5$, so the first two are safe and the third is unsafe.

A safe starting state gives only the base case. For instance, the dynamics $x_{t+1}=x_t+3$ take the safe state $x_0=0$ to $x_1=3$, outside $C$. Forward invariance requires a statement about the dynamics and controller at every safe state, not just membership of the initial state.

$\mathbb E[N]=0(0.9)+5(0.1)=0.5$, so the expected-cost constraint passes. The event $\{N\ge1\}$ occurs exactly when $N=5$, giving probability $0.1$; it exceeds $0.05$, so the chance constraint fails.

The expectation counts unsafe steps, while the chance constraint counts unsafe episodes. Here one in ten episodes has five violations. Neither number tells us their physical severity; a separate magnitude-based cost would be needed for that.

Let $F_t$ be failure at step $t$. The union bound gives $\Pr(\bigcup_{t=1}^4F_t)\le\sum_{t=1}^4\Pr(F_t)\le0.04$. Taking complements yields $\Pr(\text{all four safe})\ge0.96$.

No independence is needed, so this remains valid for dependent states in one trajectory. Under the additional assumption of independent failures with probability exactly $0.01$, the exact safe probability would be $0.99^4=0.96059601$. Without that assumption, multiplying the four probabilities is unjustified.

Replace $x_t$ by $s_t$ and $u_t$ by $a_t$. Then $a_t=\pi(s_t)$ and $s_{t+1}=f(s_t,\pi(s_t))$. The function $f$ here is a transition map, rather than the unknown performance function called $f$ in BO.

A stochastic model needs a transition distribution $P(\cdot\mid s,a)$: the next state is sampled from $P(\cdot\mid s_t,a_t)$. If the policy is stochastic too, the action is sampled from $\pi(\cdot\mid s_t)$. A safety probability must specify whether it averages over transitions, actions, initial states, learned data, or several of these.

Equal budgets $\delta_t=0.02/20=0.001$ satisfy $\sum_{t=1}^{20}\delta_t=0.02$, hence joint safety has probability at least $0.98$. This is a sufficient allocation; dependence may make it conservative.

If each step gets $0.02$, the sum is $0.4$, so the bound becomes only $\Pr(\text{all safe})\ge0.6$. Reusing a full run-wide budget at every step changes the guarantee. No independence assumption repairs the arithmetic of the union bound; independence would allow a different calculation if its hypotheses were justified.

The mean is $0(0.8)+2(0.15)+10(0.05)=0.8$. Since $\Pr(Z\le0)=0.8$ and $\Pr(Z\le2)=0.95$, the lower 90% quantile is $\operatorname{VaR}_{0.9}=2$.

The worst 10% consists of the 5% mass at 10 and another 5% drawn from the atom at 2. Thus $\operatorname{CVaR}_{0.9}=[0.05(10)+0.05(2)]/0.1=6$. Equivalently, the variational formula at $\nu=2$ gives $2+10\,\mathbb E[(Z-2)^+]=2+10(0.05)(8)=6$. Averaging all outcomes satisfying $Z\ge2$ would average 20% of the distribution and give the wrong tail size.

The image of $C_1$ is $[-0.5,0.5]\subseteq C_1$, so $C_1$ is invariant. The image of $C_2$ is $[0.5,1]$, which is not a subset of $C_2$; for example, $x_0=1$ leaves at the first step.

From $x_0=2$, $x_t=2^{1-t}\to0$, so convergence holds. Nevertheless that initial state is already outside $C_1$, and the trajectory eventually leaves $C_2$. Stability concerns behavior near an equilibrium; a state constraint concerns a specified set. They coincide only when an additional invariant-set argument connects them.

The radius is $0.6/(2\sqrt2)\approx0.212132$. Thus every perturbation of norm $0.2$ is certified to keep the label, while a perturbation of norm $0.22$ is outside this guarantee. At the radius itself the lower bound on a competing logit gap is zero, so the strict-label guarantee does not include the boundary.

Outside the radius, a label change is possible under the bound but not proved to happen. The certificate is a sufficient condition. It describes the classifier at this input; obtaining a guarantee for the controlled system still requires connecting prediction error to the system dynamics.

Write viability as $\exists u\ \forall t:\varphi_x^u(t)\notin X_F$. Its negation is $\forall u\ \exists t:\varphi_x^u(t)\in X_F$: every controller eventually fails, with the failure time allowed to depend on the controller.

“Some controller eventually fails” is $\exists u\ \exists t:\varphi_x^u(t)\in X_F$. It can hold even at a viable state: one controller may steer into a wall while another brakes safely. Viability asks whether at least one safe continuation exists, rather than whether all available behaviors are safe.

The cost is $\sum_{t=50}^{\infty}0.9^t=0.9^{50}/(1-0.9)\approx0.0515378$, so the discounted-cost budget $0.1$ passes. Yet failure occurs with probability 1, because the trajectory is deterministic and leaves the safe set at time 50.

The discount shrinks late violations; it does not make them less certain. This example is also why the horizon and the meaning of the cost must be part of a safety statement. An undiscounted count here is infinite, and a joint infinite-horizon chance constraint with failure budget below 1 fails.

Induction gives $x_t=0.01t$. At time 100, $x_{100}=1\in C$; at time 101, $x_{101}=1.01\notin C$. Therefore the first violation is at time 101.

The experiment establishes safety of the checked trajectory over the finite checked horizon, under the experiment's model and conditions. Forward invariance of $C$ would require every initial state in $C$ to remain in $C$ for all subsequent times. It already fails at $x=1$, whose successor is 1.01. Even exact measurements of many safe finite trajectories cannot replace the missing universal argument.

If $|x_t|\le r$, the triangle inequality gives $|x_{t+1}|\le0.5|x_t|+|w_t|\le0.5r+0.1$. This is at most $r$ exactly when $r\ge0.2$. Necessity follows by choosing $x_t=r$ and $w_t=0.1$, so no smaller centered interval works.

For $r=0.2$, assume the initial state satisfies $|x_0|\le0.2$ (the base case). If $|x_t|\le0.2$, the preceding estimate gives $|x_{t+1}|\le0.2$ (the inductive step). Thus the interval is invariant for every allowed disturbance sequence. The result is deterministic under the stated disturbance bound; no distribution or confidence parameter is involved.

$\mathbb E[Z]=(-2.1+2.2)/10=0.01$ and $\mathbb P(Z\gt0)=0.3$.

$\alpha=0.9$. $\operatorname{VaR}_{0.9}=\inf\{z:\mathbb P(Z\le z)\ge0.9\}=0.5$ since $\mathbb P(Z\le0.5)=0.9$. The worst 10% is the single atom $1.5$, so $\operatorname{CVaR}_{0.9}=1.5$. Rockafellar–Uryasev at $\nu=0.5$: $0.5+\tfrac1{0.1}\cdot0.1\cdot(1.5-0.5)=1.5$.

$\alpha=0.75$. $\mathbb P(Z\le0)=0.7\lt0.75\le\mathbb P(Z\le0.2)=0.8$, so $\operatorname{VaR}_{0.75}=0.2$. The worst quarter is $2.5$ atoms: $1.5$ and $0.5$ in full and half of the atom $0.2$:

Verdicts: the mean excursion $\mathbb E[Z]=0.01$ is within the budget $0.05$, so the CMDP-style average says "safe" (with a zero budget, $\mathbb E[Z]\le0$, it would fail, but only by $0.01$, even though three episodes in ten cross the boundary); $\mathbb P(Z\gt0)=0.3\gt0.2$ says unsafe; $\operatorname{CVaR}_{0.75}=0.84\gt0$ and $\operatorname{CVaR}_{0.9}=1.5\gt0$ say unsafe; the hard view is unsafe because $\max Z=1.5\gt0$. Only the average calls it safe.

(i) $N$ is a non-negative integer, so $N\ge\mathbf 1\{N\ge1\}$ pointwise; taking expectations, $\mathbb E[N]\ge\mathbb P(N\ge1)=\mathbb P(E)$ (Markov's inequality at level $1$). Tightness: violate exactly one step with probability $p$ and never otherwise; then $N\in\{0,1\}$ and $\mathbb E[N]=p=\mathbb P(E)$.

(ii) Let every episode violate exactly once, at a random time. Then $N\equiv1$, $\mathbb E[N]=1\le d$, and $\mathbb P(E)=1$: the CMDP constraint is met by a policy that fails in every episode.

(iii) Take a policy inside $C$ for $t\lt t_0$ and outside for all $t\ge t_0$, surely. Then

(iv) $N\le T+1$ pointwise and $N=0$ on $E^c$, so $\mathbb E[N]=\mathbb E[N\mathbf 1_E]\le(T+1)\mathbb P(E)\le(T+1)\delta$. Tight: with probability $\delta$ violate at every step, otherwise never. The two formalisations control each other only up to the horizon. With discounting only this direction survives: $\sum_{t\ge0}\gamma^tc_t\le\mathbf 1_E/(1-\gamma)$ pointwise, so $\mathbb P(E)\le\delta$ still gives $J_c^\gamma\le\delta/(1-\gamma)$, whereas by (iii) no discounted budget $d\gt0$ bounds $\mathbb P(E)$. None of this involves the magnitude of a violation: an indicator cost counts a millimetre and a crash alike, which is what CVaR of the excursion (Exercise 1.2) adds.

SafeOpt needs a finite $D$; $f$ $L$-Lipschitz for a known $L$; $\|f\|_k^2\le B$ for a known kernel and known $B$; noise zero-mean given the past and bounded by $\sigma_0$, with the GP posterior (and $\gamma_t$) computed for likelihood variance $\lambda=\sigma_0^2$ or larger; a non-empty safe seed $S_0$ with $f\ge h$; $\beta_t=2B+300\gamma_t\log^3(t/\delta)$. It gives, with probability $\ge1-\delta$ over the noise and jointly for all $t$, $f(x_t)\ge h$ at every query, with a separate finite-sample optimality result previewed in Module 4. It protects the learning phase: exploration never leaves the certified set. Checkable: $S_0$ (a conservative controller), $L$ (physical rate limits, plausibly), the noise bound (a justified sensor specification; finite sensor data alone cannot prove it). Difficult to justify for an unknown $f$: $B$ and the kernel. Too small a $B$, or a heuristic constant in place of $\beta_t$, can produce intervals that are too narrow and admit unsafe points. Fiedler et al. (2024, Table 1) report 3.95% unsafe runs on average (28.62% worst) with $\beta\equiv2$, and 0.859% (13.38% worst) for Real-$\beta$-SafeOpt using their data-dependent formula (7) in arXiv v1, with a norm bound $\|f\|_k\le2.5$ against a true norm of $10$. Too small an $L$ can wrongly certify unevaluated points; if an unsafe seed point is selected at $t=1$, that first query violates safety. LoSBO drops $B$ and the kernel (safety from $L$ and a noise bound $E$ alone) and is exactly the "checkable assumptions" repair.

ZCBF needs known control-affine $f,g$, locally Lipschitz; a $C^1$ function $h$ with $C=\{h\ge0\}\subseteq D$, where $D$ is an open ambient neighbourhood of $C$ for the stated locally Lipschitz closed loop; for a boundary-only check, $0$ must additionally be a regular value of $h$ (with an open $D$ the inequality on $D$ already excludes leaving $C$; a check on $\partial C$ alone, Nagumo's condition, needs $\nabla h\ne0$ on $\partial C$; with neither, $h=-x^3$ on $D=C=(-\infty,0]$ with $\dot x=1$ satisfies the inequality and still leaves $C$); an extended class-$\mathcal K$ $\alpha$ with $\sup_u[L_fh+L_ghu+\alpha(h)]\ge0$ on $D$, feasible inputs $K_{\rm zcbf}(x)\ne\emptyset$ (automatic for $U=\mathbb R^m$, a closed polyhedron or a compact $U$; for an open $U$ a zero supremum need not be attained, see the theorem in Section 3); a Lipschitz continuous controller $u:D\to U$ with values in $K_{\rm zcbf}(x)$. It gives deterministic forward invariance of $C$ from every $x_0\in C$, no probability at all, on the maximal interval of existence of the closed-loop solution (for all $t\ge0$ when the closed loop is forward complete, e.g. for compact $C$), for the deployed controller and equally for a learning policy filtered through the CBF-QP (so it protects learning whenever the filter is active). Checkable: the structure of $h$ and $\alpha$ and the regular-value condition (by construction); the barrier inequality with $K_{\rm zcbf}(x)\ne\emptyset$ on all of $D$ (analytically, by an SOS certificate, or by gridding plus Lipschitz bounds with a margin that covers the space between grid points; a plain grid check certifies only the grid points); Lipschitz continuity of the QP solution (regularity conditions in Ames et al. 2017). Not directly checkable: the model. If $f,g$ are wrong, $\dot h$ is mis-evaluated and $C$ can be left; the repair is a robust or input-to-state-safe CBF with an uncertainty margin, or a learned residual with a GP bound, which re-imports SafeOpt's kind of assumptions (Module 10).

Summary: SafeOpt buys "no model needed" with statistical and function-class assumptions that can be difficult to justify for an unknown target; the CBF buys a deterministic guarantee with a model assumption engineers are used to quantifying. LoSBO and rigorous GP bounds on one side, learned residuals with bounds on the other, meet in the middle.

(i) With $e_t=x_t-x_{\rm goal}$, $e_{t+1}=(1-k)e_t+\sigma w_t$ and $e_0=-x_{\rm goal}$: a stable scalar AR(1) recursion since $|1-k|\lt1$. Unrolling, $e_t=(1-k)^te_0+\sigma\sum_{j=0}^{t-1}(1-k)^{t-1-j}w_j$; the noise terms are independent, so

(ii) $x_t\sim\mathcal N(m_t,v_t)$ exactly (a linear function of Gaussians), so $\mathbb P(x_t\gt1)=1-\Phi\big((1-m_t)/\sqrt{v_t}\big)$ and, by linearity of expectation (no independence needed),

Standardizing requires $v_t\gt0$. If $v_t=0$ (the case $\sigma=0$) the state is deterministic and $\mathbb P(x_t\gt1)=\mathbf1\{m_t\gt1\}$; equality $m_t=1$ is safe because the constraint is $x_t\le1$. The sum starts at $t=1$ because $x_0=0$ never violates.

(iii) $\sigma_\infty^2=0.01/0.75$, $\sigma_\infty=\sqrt{0.01/0.75}\approx0.1155$, so the stationary per-step violation probability is $p_\infty=1-\Phi(0.2/\sqrt{0.01/0.75})=1-\Phi(\sqrt3)\approx0.0416$ ($\sqrt3\approx1.732$). The transient is short: $p_1\approx0$ ($m_1=0.4$, $\sqrt{v_1}=0.1$, six standard deviations away), $p_3\approx0.0044$, $p_5\approx0.0256$, $p_{10}\approx0.0410$. Summing the exact terms gives $\mathbb E[N]\approx1.484$, slightly below the stationary approximation $Tp_\infty\approx1.665$. The Markov bound $\mathbb P(\exists t:x_t\gt1)\le\mathbb E[N]\lt1.485$ is vacuous; the explorer (set $\sigma=0.1$) estimates the actual joint probability, about $0.69$ in a large simulation, which individual marginal probabilities alone do not determine. This is the quantitative face of Exercise 1.3: the CMDP number is analytic and cheap, the chance-constraint number needs the joint law.

What the marginals miss is the dependence: $(x_1,\ldots,x_T)$ is jointly Gaussian with $\operatorname{Cov}(x_s,x_t)=(1-k)^{t-s}v_s$ for $s\le t$ (the noise after time $s$ is independent of $x_s$), so $\mathbb P(\exists t:x_t\gt1)$ is a $T$-dimensional Gaussian probability that can be computed numerically; simulation is simply the explorer's convenient estimate of it.