← Back to overview

Safe Learning Formula Sheet

Safe RL, Safe ML & Learning-Based Control — All key definitions, theorems and update rules

Use this as a reference while studying. Each module heading links to the explanations, worked examples and practice behind its formulas. Check the assumptions in the box before applying a result. If the notation feels unfamiliar, start with the short refresher checks and the linked primers.

Jump to module: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Conventions. GP bands are written $\mu_t\pm\beta_t\sigma_t$ (Chowdhury–Gopalan form); Srinivas et al. and Sui et al. write $\beta_t^{1/2}\sigma_t$, and their $\beta_t$ is the square of ours. $\|f\|_k\le B$ bounds the RKHS norm, not its square, unless a box says otherwise. LipSDP writes $\rho=L^2$ (LipKernel: $\rho=L$). The slope bound $\beta$ of the LMI and network modules (2, 12–14) is unrelated to the GP multiplier $\beta_t$. The letter $h$ is SafeOpt’s safety threshold ($f(x)\ge h$) in Modules 4–5, the GP-modelled selector function of GoSafe in Module 6 (its threshold is absorbed into $g_i\ge0$), and the barrier function ($C=\{x:h(x)\ge0\}$) in Modules 10–11; FISOR’s constraint function in Module 9 has the opposite sign ($h\le0$ is safe), and every other use of $h$ (Modules 8, 9, 11) is local to its box.

1. The Safe Learning Landscape

Hard constraints and forward invariance (Brunke et al. 2022, Safety Level III)
$C\subseteq X$ is forward invariant under the closed loop $x_{t+1}=f(x_t,\pi(x_t))$ if $x_0\in C$ implies $x_t\in C$ for all $t\ge0$. Hard-constraint requirement: $$ x_t\in C\ \text{ and }\ u_t\in U\quad\text{for all } t\text{ and every disturbance sequence } w_t\in W $$ Deterministic and worst-case over $W$; needs a model of $f$ and $W$.
Chance constraints, joint and per-step (Brunke et al. 2022, Safety Level II)
Joint (trajectory-level): $$ \mathbb P\big(x_t\in C\ \ \forall t\in\{0,\dots,T\}\big)\ \ge\ 1-\delta $$ per-step: $\mathbb P(x_t\in C)\ge1-\delta_t$. Union bound: $\mathbb P(\exists t: x_t\notin C)\le\sum_t\delta_t$. Always state over which randomness the probability is taken (process noise, measurement noise, a prior over $f$, or calibration data together with the test point).
Expected-cost constraint: the CMDP (Altman 1999; notation of Achiam et al. 2017)
$$ \pi^\star=\operatorname*{arg\,max}_{\pi}\ J(\pi)\quad\text{s.t.}\quad J_{c_i}(\pi)=\mathbb E_{\tau\sim\pi}\Big[\sum_{t=0}^{\infty}\gamma^t c_i(s_t,a_t,s_{t+1})\Big]\le d_i $$ An average over episodes and over discounted time: single episodes may violate arbitrarily.
Risk-sensitive constraint: CVaR (Rockafellar–Uryasev form; Chow et al. 2018)
For a cost $Z$ (large is bad) and $\alpha\in(0,1)$: $$ \operatorname{CVaR}_\alpha(Z)=\min_{\nu\in\mathbb R}\Big\{\nu+\frac{1}{1-\alpha}\,\mathbb E\big[(Z-\nu)^+\big]\Big\} $$ the average of the worst $(1-\alpha)$-fraction of outcomes: $\alpha\to1$ is the tail, $\alpha\to0$ recovers $\mathbb E[Z]$. A risk constraint reads $\operatorname{CVaR}_\alpha(\sum_t c_t)\le d$.
Lyapunov region-of-attraction certificate (Berkenkamp et al. 2017)
$V$ continuous and positive definite about the equilibrium $x^\ast$, closed-loop map $F(x)=f(x,\pi(x))$ continuous with $F(x^\ast)=x^\ast$. If $V(F(x))-V(x)\lt0$ for all $x\ne x^\ast$ in a compact sublevel set $\mathcal V(c)=\{x:V(x)\le c\}$, then $\mathcal V(c)$ is forward invariant and $\mathcal V(c)\subseteq\mathcal R$, the region of attraction (initial states whose trajectories converge to $x^\ast$).
Certified robustness radii (Tsuzuku et al. 2018; Cohen et al. 2019)
$L$-Lipschitz ($\ell_2$) network with margin $M(x)=\varphi_c(x)-\max_{j\ne c}\varphi_j(x)\gt0$: the label cannot change for $$\|\delta\|_2\lt M(x)/(\sqrt2L)$$ Randomized smoothing, $g(x)=\operatorname*{arg\,max}_c\mathbb P_{\varepsilon\sim\mathcal N(0,\sigma^2I)}\big(\text{label}(x+\varepsilon)=c\big)$: with a lower confidence bound $\underline{p_A}\gt1/2$ on the top-class probability, $g$ keeps its label for $$\|\delta\|_2\lt\sigma\,\Phi^{-1}(\underline{p_A})$$ a radius that holds only with the Monte-Carlo confidence of $\underline{p_A}$.
Viability kernel (Massiani et al. 2023, Def. 1)
For a failure set $X_F$: $$ X_V=\{x\in X:\ \exists u\in\mathcal U,\ \forall t\in\mathcal T,\ \varphi^u_x(t)\notin X_F\} $$ with $\varphi^u_x$ the trajectory from $x$ under controller $u$; $X_U=X\setminus X_V$ is the unviability kernel. $X_V$ is the largest controlled-invariant subset of $X\setminus X_F$.

2. Math Toolkit I: Duality, LMIs & the S-Procedure

Algorithms: dual ascent (projected supergradient ascent on the dual function), the template behind every Lagrangian safe-RL method.

Lagrangian, dual function and weak duality
$$ p^\star=\min_{x\in\mathcal D} f_0(x)\quad\text{s.t.}\quad f_i(x)\le0,\ i=1,\dots,m,\qquad h_j(x)=0,\ j=1,\dots,p $$ $$ L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^m\lambda_i f_i(x)+\sum_{j=1}^p\nu_j h_j(x),\qquad \lambda\in\mathbb R^m_+,\ \nu\in\mathbb R^p $$ Dual function $g(\lambda,\nu)=\inf_{x\in\mathcal D}L(x,\lambda,\nu)$, dual problem $d^\star=\max_{\lambda\ge0,\ \nu}\ g(\lambda,\nu)$. For any primal problem (convex or not), $g$ is concave and $g(\lambda,\nu)\le p^\star$ for every $\lambda\ge0$ and every $\nu$, hence $d^\star\le p^\star$; the duality gap is $p^\star-d^\star\ge0$.
Strong duality under Slater’s condition (Boyd & Vandenberghe 2004, Sec. 5.2.3)
Convex problem ($f_0,\dots,f_m$ convex, $h_j$ affine, $\mathcal D$ convex) and a point $\bar x$ in the relative interior of $\mathcal D$ with $f_i(\bar x)\lt0$ for all non-affine $f_i$ (affine inequalities only need $f_i(\bar x)\le0$) and $h(\bar x)=0$. Then $p^\star=d^\star$, and if $p^\star\gt-\infty$ the dual optimum is attained by some $(\lambda^\star,\nu^\star)$.
Karush–Kuhn–Tucker conditions (Boyd & Vandenberghe 2004, Sec. 5.5.3)
For differentiable $f_i,h_j$ on an open domain $\mathcal D$ (e.g. $\mathcal D=\mathbb R^n$), $(x^\star,\lambda^\star,\nu^\star)$ is a KKT point if $$ \begin{aligned} &\text{primal feasibility:}\quad x^\star\in\mathcal D,\ \ f_i(x^\star)\le0,\ \ h_j(x^\star)=0;\qquad \text{dual feasibility:}\quad \lambda^\star\ge0;\\ &\text{complementary slackness:}\quad \lambda_i^\star f_i(x^\star)=0\ \ \forall i;\\ &\text{stationarity:}\quad \nabla f_0(x^\star)+\sum_i\lambda_i^\star\nabla f_i(x^\star)+\sum_j\nu_j^\star\nabla h_j(x^\star)=0 . \end{aligned} $$ (a) If strong duality holds and $x^\star$, $(\lambda^\star,\nu^\star)$ are primal and dual optimal, they form a KKT point. (b) For a convex problem, every KKT point is primal-dual optimal with zero gap.
Dual ascent is projected supergradient ascent
Let $x(\lambda)\in\arg\min_xL(x,\lambda)$ (inequality constraints only). Then $f(x(\lambda))=(f_1(x(\lambda)),\dots,f_m(x(\lambda)))$ is a supergradient of $g$ at $\lambda$: $$ g(\lambda')=\inf_xL(x,\lambda')\le L(x(\lambda),\lambda')=f_0(x(\lambda))+\lambda'^{\top}f(x(\lambda))=g(\lambda)+(\lambda'-\lambda)^{\top}f(x(\lambda))\quad\forall\lambda' $$ Projected supergradient ascent on the concave $g$: $$ \lambda_{k+1}=\big[\lambda_k+\eta\,f(x(\lambda_k))\big]_+ $$ With a constant step $\eta$ and bounded supergradients the best dual value found comes within $O(\eta)$ of $d^\star$; convergence of $\lambda_k$ needs diminishing steps, e.g. $\sum_k\eta_k=\infty$ and $\sum_k\eta_k^2\lt\infty$.
Linear matrix inequality and semidefinite program
Given $F_0,F_1,\dots,F_m\in\mathbb S^n$, an LMI in $x$ (strict if $F(x)\succ0$): $$ F(x)=F_0+\sum_{i=1}^m x_iF_i\ \succeq\ 0\qquad(x\in\mathbb R^m) $$ A semidefinite program minimises a linear objective over LMI constraints: $$ \min_{x}\ c^{\top}x\quad\text{s.t.}\quad F(x)\succeq0 $$ Several LMIs are one LMI: $F^{(1)}(x)\succeq0,\dots,F^{(k)}(x)\succeq0$ iff $\mathrm{blkdiag}\big(F^{(1)}(x),\dots,F^{(k)}(x)\big)\succeq0$.
Discrete-time Lyapunov LMI
For $A\in\mathbb R^{n\times n}$ the following are equivalent: (i) $A$ is Schur stable, i.e. $\rho(A)\lt1$; (ii) the LMI $P\succ0$, $A^{\top}PA-P\prec0$ is feasible; (iii) for some (equivalently, every) $Q\succ0$ the Stein equation $A^{\top}PA-P=-Q$ has a unique solution and it satisfies $P\succ0$. Then $V(x)=x^{\top}Px$ strictly decreases along $x_{t+1}=Ax_t$.
Schur complement (both signs)
Let $M=\begin{bmatrix}A&B\\B^{\top}&C\end{bmatrix}$ with $A\in\mathbb S^p$, $C\in\mathbb S^q$.
If $C\succ0$: $\ M\succeq0\iff A-BC^{-1}B^{\top}\succeq0$, and $M\succ0\iff A-BC^{-1}B^{\top}\succ0$.
If $A\succ0$: $\ M\succeq0\iff C-B^{\top}A^{-1}B\succeq0$, and $M\succ0\iff C-B^{\top}A^{-1}B\succ0$.
Negative form: if $C\prec0$, $\ M\preceq0\iff A-BC^{-1}B^{\top}\preceq0$.
S-procedure, sufficient condition
Quadratic functions $\sigma_i(\xi)=\xi^{\top}A_i\xi+2b_i^{\top}\xi+c_i$ with $A_i\in\mathbb S^n$. If there exist $\tau_1,\dots,\tau_m\ge0$ such that $$ \sigma_0(\xi)-\sum_{i=1}^m\tau_i\,\sigma_i(\xi)\ \ge\ 0\qquad\text{for all }\xi\in\mathbb R^n $$ then $\sigma_0(\xi)\ge0$ for every $\xi$ with $\sigma_1(\xi)\ge0,\dots,\sigma_m(\xi)\ge0$. The premise is the LMI (linear in $\tau$) $$ \begin{bmatrix}A_0&b_0\\b_0^{\top}&c_0\end{bmatrix}-\sum_{i=1}^m\tau_i\begin{bmatrix}A_i&b_i\\b_i^{\top}&c_i\end{bmatrix}\succeq0\qquad(\text{for homogeneous forms: }A_0-\textstyle\sum_i\tau_iA_i\succeq0) $$
S-lemma (Yakubovich): one constraint is lossless
$A,B\in\mathbb S^n$ and a point $\bar\xi$ with $\bar\xi^{\top}A\bar\xi\gt0$ (strict feasibility). Then $$ \Big[\ \xi^{\top}A\xi\ge0\ \Rightarrow\ \xi^{\top}B\xi\ge0\ \Big]\quad\Longleftrightarrow\quad\exists\,\tau\ge0:\ \ B-\tau A\succeq0 $$ For $m\ge2$ constraints the S-procedure is in general only sufficient.
From quadratic constraints to an LMI: the engine of LipSDP
A stacked vector $\xi$ satisfies $n$ quadratic constraints $\xi^{\top}Q_i\xi\ge0$, $i=1,\dots,n$; to certify $\xi^{\top}M\xi\le0$ for all such $\xi$ it suffices that $$ M+\sum_{i=1}^n\lambda_iQ_i\ \preceq\ 0\qquad\text{for some }\lambda_1,\dots,\lambda_n\ge0 $$ For slope-restricted neurons, $\sum_i\lambda_iQ_i$ assembles into $\begin{bmatrix}-2\alpha\beta T&(\alpha+\beta)T\\(\alpha+\beta)T&-2T\end{bmatrix}$ with $T=\mathrm{diag}(\lambda_1,\dots,\lambda_n)$: the diagonal multiplier of LipSDP is the vector of S-procedure multipliers, one per neuron.
Slope restriction and diagonal multipliers (Fazlyab et al. 2019, Def. 1 and Lemma 1)
$\varphi:\mathbb R\to\mathbb R$ is slope-restricted in $[\alpha,\beta]$ ($0\le\alpha\lt\beta\lt\infty$) if $$ \alpha\le\frac{\varphi(a)-\varphi(b)}{a-b}\le\beta\qquad\forall a\ne b $$ For $\phi(x)=[\varphi(x_1)\ \cdots\ \varphi(x_n)]^{\top}$, every $T\in\mathcal T_n=\{T=\sum_{i=1}^n\lambda_ie_ie_i^{\top}:\ \lambda_i\ge0\}$ (diagonal, PSD) and all $x,y\in\mathbb R^n$ satisfy $$ \begin{bmatrix}x-y\\\phi(x)-\phi(y)\end{bmatrix}^{\top}\begin{bmatrix}-2\alpha\beta T&(\alpha+\beta)T\\(\alpha+\beta)T&-2T\end{bmatrix}\begin{bmatrix}x-y\\\phi(x)-\phi(y)\end{bmatrix}\ \ge\ 0 $$
Dissipativity, storage function and QSR supply rate (Willems 1972)
$x_{t+1}=f(x_t,w_t)$, $z_t=h(x_t,w_t)$ is dissipative with respect to the supply rate $s(w,z)$ if there is a storage function $V\ge0$ with $$ V(x_{t+1})-V(x_t)\ \le\ s(w_t,z_t)\qquad\text{for all }t\text{ and all trajectories} $$ QSR supply rate: $$ s(w,z)=\begin{bmatrix}z\\w\end{bmatrix}^{\top}\begin{bmatrix}Q&S\\S^{\top}&R\end{bmatrix}\begin{bmatrix}z\\w\end{bmatrix} $$ $\ell_2$ gain at most $\gamma$: $Q=-I$, $S=0$, $R=\gamma^2I$; passivity: $Q=R=0$, $S=I$. Papers differ on whether the vector is ordered $(z,w)$ or $(w,z)$; check before copying a $(Q,S,R)$ triple.
Dissipativity LMI of a discrete-time linear system
For $x_{t+1}=Ax_t+Bw_t$, $z_t=Cx_t+Dw_t$ with storage $V(x)=x^{\top}Px$, $P\succeq0$, the dissipation inequality holds for all $(x_t,w_t)$ iff $$ \begin{bmatrix}A&B\\I&0\end{bmatrix}^{\top}\begin{bmatrix}P&0\\0&-P\end{bmatrix}\begin{bmatrix}A&B\\I&0\end{bmatrix}-\begin{bmatrix}C&D\\0&I\end{bmatrix}^{\top}\begin{bmatrix}Q&S\\S^{\top}&R\end{bmatrix}\begin{bmatrix}C&D\\0&I\end{bmatrix}\ \preceq\ 0 $$ with $\Pi$ the QSR matrix. The matrix is affine in $(P,\Pi)$: an LMI in $P$ for fixed supply and also in the supply parameters, e.g. in $\gamma^2$.
Kalman–Yakubovich–Popov lemma (Rantzer 1996 form)
$A\in\mathbb R^{n\times n}$, $B\in\mathbb R^{n\times m}$, $M\in\mathbb S^{n+m}$, $\det(j\omega I-A)\ne0$ for all $\omega\in\mathbb R$ and $(A,B)$ controllable. Equivalent:
(i) $$\begin{bmatrix}(j\omega I-A)^{-1}B\\I\end{bmatrix}^{*}M\begin{bmatrix}(j\omega I-A)^{-1}B\\I\end{bmatrix}\preceq0$$ for all $\omega\in\mathbb R\cup\{\infty\}$;
(ii) there exists $P\in\mathbb S^n$ with $$M+\begin{bmatrix}A^{\top}P+PA&PB\\B^{\top}P&0\end{bmatrix}\preceq0$$ The equivalence for strict inequalities holds even without controllability. With $M=\begin{bmatrix}C^{\top}C&C^{\top}D\\D^{\top}C&D^{\top}D-\gamma^2I\end{bmatrix}$, (i) reads $G(j\omega)^{*}G(j\omega)\preceq\gamma^2I$ for all $\omega$, with $G(s)=C(sI-A)^{-1}B+D$. If $A$ is Hurwitz, (i) says exactly $\|G\|_\infty\le\gamma$, i.e. the $\mathcal L_2$ gain is at most $\gamma$, and every $P$ satisfying (ii) is automatically $\succeq0$ (bounded-real lemma); the Hurwitz assumption cannot be dropped.

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

Positive-definite kernel and common kernels
A symmetric $k:D\times D\to\mathbb R$ is a (positive semi-definite) kernel if for every finite set $x_1,\dots,x_m\in D$ and every $c\in\mathbb R^m$ $$ \sum_{i,j=1}^m c_ic_j\,k(x_i,x_j)=c^\top Kc\ge0,\qquad K=[k(x_i,x_j)]_{i,j} $$ With $r=\|x-x'\|$ and length-scale $\ell$: $$ k_{\mathrm{SE}}=e^{-r^2/(2\ell^2)},\qquad k_{\nu=3/2}=\Big(1+\tfrac{\sqrt3r}{\ell}\Big)e^{-\sqrt3r/\ell},\qquad k_{\nu=5/2}=\Big(1+\tfrac{\sqrt5r}{\ell}+\tfrac{5r^2}{3\ell^2}\Big)e^{-\sqrt5r/\ell},\qquad k_{\mathrm{lin}}=x^\top x' $$
RKHS and the reproducing property (Moore–Aronszajn)
$\mathcal H_k$ is the completion of all finite expansions $f=\sum_ic_i\,k(z_i,\cdot)$ under the inner product $$ \Big\langle\sum_ic_ik(z_i,\cdot),\ \sum_jd_jk(w_j,\cdot)\Big\rangle_k=\sum_{i,j}c_id_j\,k(z_i,w_j),\qquad\text{so}\qquad\|f\|_k^2=c^\top K_zc $$ Reproducing property: for every $f\in\mathcal H_k$ and $x\in D$, $$ \langle f,\,k(x,\cdot)\rangle_k=f(x) $$ Feature $\varphi(x):=k(x,\cdot)\in\mathcal H_k$, with $k(x,x')=\langle\varphi(x),\varphi(x')\rangle_k$ and $|f(x)|\le\|f\|_k\sqrt{k(x,x)}$.
RKHS functions are continuous in the kernel metric
For all $f\in\mathcal H_k$ and $x,x'\in D$, $$ |f(x)-f(x')|\le\|f\|_k\,d_k(x,x'),\qquad d_k(x,x')^2=k(x,x)-2k(x,x')+k(x',x') $$ For the SE kernel $d_k^2=2\big(1-e^{-r^2/(2\ell^2)}\big)\le r^2/\ell^2$, so every $f$ with $\|f\|_k\le B$ is Lipschitz with constant $L=B/\ell$.
GP posterior = kernel ridge regression (Kanagawa et al. 2018)
Data $(x_i,y_i)_{i\le t}$ with $y_i=f(x_i)+\varepsilon_i$; $K_t=[k(x_i,x_j)]_{i,j\le t}$, $k_t(x)=[k(x_1,x),\dots,k(x_t,x)]^\top$; $\lambda\gt0$ is the noise variance used in the likelihood. $$ \mu_t(x)=k_t(x)^\top(K_t+\lambda I)^{-1}y_t,\qquad\sigma_t^2(x)=k(x,x)-k_t(x)^\top(K_t+\lambda I)^{-1}k_t(x) $$ and $f(x)\mid y_t\sim\mathcal N(\mu_t(x),\sigma_t^2(x))$. The minimiser of $\sum_{i=1}^t(y_i-f(x_i))^2+\lambda\|f\|_k^2$ over $f\in\mathcal H_k$ is $f^\star(x)=k_t(x)^\top(K_t+\lambda I)^{-1}y_t=\mu_t(x)$.
Noise-free (interpolation) error bound
For noise-free data at distinct inputs with $K_t\succ0$ and $\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)$. For every $f\in\mathcal H_k$ and every $x\in D$: $$|f(x)-s_t(x)|\le\|f\|_k\,P_t(x)$$ Moreover $s_t$ is the minimum-norm interpolant, $s_t=\operatorname*{arg\,min}\{\|g\|_k:\ g(x_i)=f(x_i),\ i\le t\}$, and the bound is sharp (deterministic: no prior, no noise, no probability).
Maximum information gain (Srinivas et al. 2010)
Under the GP model with noise variance $\lambda$, the mutual information between the observations $y_A$ at a fixed design $A=(x_1,\dots,x_T)$ (repetitions allowed) and the values $f_A$ is $$ I(y_A;f_A)=H(y_A)-H(y_A\mid f_A)=\tfrac12\log\det\big(I+\lambda^{-1}K_A\big) $$ and the maximum information gain after $T$ rounds is $$\gamma_T:=\sup_{x_1,\dots,x_T\in D}\tfrac12\log\det\big(I_T+\lambda^{-1}K_T\big)$$ It depends on $k$, $D$, $\lambda$ and $T$ only, not on the data.
Sequential information gain and sum of posterior variances
For any sequence $x_1,\dots,x_T$, fixed in advance or chosen adaptively, the realised information gain $G_T:=\tfrac12\log\det(I+\lambda^{-1}K_T)$ satisfies, pathwise, $$ G_T=\tfrac12\sum_{t=1}^T\log\big(1+\lambda^{-1}\sigma_{t-1}^2(x_t)\big)\le\gamma_T $$ If $k(x,x)\le1$ on $D$, then for every sequence $$ \sum_{t=1}^T\sigma_{t-1}^2(x_t)\le\frac{2}{\log(1+\lambda^{-1})}\,\gamma_T,\qquad\text{hence}\qquad\sum_{t=1}^T\sigma_{t-1}(x_t)\le\sqrt{\frac{2T\gamma_T}{\log(1+\lambda^{-1})}} $$
Self-normalised bound (Abbasi-Yadkori, Pál & Szepesvári, NeurIPS 2011, Thm. 1)
$X_t\in\mathbb R^d$ is $F_{t-1}$-measurable, $\varepsilon_t$ is $F_t$-measurable and conditionally $R$-sub-Gaussian, $\mathbb E[e^{\alpha\varepsilon_t}\mid F_{t-1}]\le e^{\alpha^2R^2/2}$ for all $\alpha\in\mathbb R$; $V\succ0$ fixed; $S_t=\sum_{s\le t}\varepsilon_sX_s$, $\bar V_t=V+\sum_{s\le t}X_sX_s^\top$. With probability at least $1-\delta$, for all $t\ge0$ simultaneously, $$ \|S_t\|_{\bar V_t^{-1}}^2\le2R^2\log\!\Big(\frac{\det(\bar V_t)^{1/2}\det(V)^{-1/2}}{\delta}\Big) $$
RKHS self-normalised bound (Chowdhury & Gopalan 2017, Thm. 1; Abbasi-Yadkori 2013 / Whitehouse et al. 2023, Cor. 1)
Assume a separable RKHS and a measurable feature map $\varphi(x)=k(x,\cdot)$. The inputs $x_t$ are $F_{t-1}$-measurable, so $\varphi(x_t)$ are predictable Hilbert-valued features; $\varepsilon_t$ is $F_t$-measurable and conditionally $R$-sub-Gaussian; $S_t=\sum_{s\le t}\varepsilon_s\varphi(x_s)$, $A_t=\Phi_t^*\Phi_t=\sum_{s\le t}\varphi(x_s)\varphi(x_s)^*$. Whitehouse et al. form: for any $\rho\gt0$, with probability at least $1-\delta$, simultaneously for all $t\ge0$, $$ \big\|(A_t+\rho\,\mathrm{id})^{-1/2}S_t\big\|_k\le R\sqrt{2\log\Big(\tfrac1\delta\sqrt{\det(I_t+\rho^{-1}K_t)}\Big)}=R\sqrt{\log\det(I_t+\rho^{-1}K_t)-2\log\delta} $$ Chowdhury & Gopalan form: for any $\eta\gt0$ (or $\eta=0$ if $K_t\succ0$ a.s.), with probability at least $1-\delta$, for all $t\ge0$, $$ \|\varepsilon_{1:t}\|^2_{((K_t+\eta I)^{-1}+I)^{-1}}\le2R^2\log\Big(\tfrac1\delta\sqrt{\det((1+\eta)I+K_t)}\Big) $$ The two coincide at $\rho=1$, $\eta\downarrow0$ and are otherwise not equivalent.
Srinivas, Krause, Kakade & Seeger (ICML 2010), Thm. 6: squared-norm convention
$f\in\mathcal H_k$ with $\|f\|_k^2\le B$ (bound on the squared norm); noise $\varepsilon_t$ a martingale difference sequence uniformly bounded by $\sigma$; prior $\mathcal{GP}(0,k)$ and noise variance $\lambda=\sigma^2$. With $\beta_t=2B+300\,\gamma_t\log^3(t/\delta)$, $$ \Pr\Big\{\forall T\ge1,\ \forall x\in D:\ |\mu_T(x)-f(x)|\le\beta_{T+1}^{1/2}\,\sigma_T(x)\Big\}\ge1-\delta $$
Chowdhury & Gopalan (ICML 2017), Thm. 2: norm convention
$f\in\mathcal H_k$ with $\|f\|_k\le B$ (bound on the norm); $x_t$ predictable, $\varepsilon_t$ conditionally $R$-sub-Gaussian; $\mu_{t-1},\sigma_{t-1}$ computed with $\lambda=1+\eta$, $\eta=2/T$, $T\ge1$ the fixed horizon. With probability at least $1-\delta$, for all $x\in D$ and all $1\le t\le T$, $$ |\mu_{t-1}(x)-f(x)|\le\Big(B+R\sqrt{2\big(\gamma_{t-1}+1+\ln(1/\delta)\big)}\Big)\sigma_{t-1}(x)=:\beta_t\,\sigma_{t-1}(x) $$
Data-dependent bound (Fiedler, Scherer & Trimpe, AAAI 2021, Thm. 1, as corrected in arXiv v2)
$k$ positive definite on $D\ne\emptyset$; $f\in\mathcal H_k$ with $\|f\|_k\le B$; $(x_n)$ predictable, $\varepsilon_n$ conditionally $R$-sub-Gaussian; $\mu_N,\sigma_N$ the GP posterior with likelihood noise variance $\lambda\gt0$ (any value); $\bar\lambda:=\max\{1,\lambda\}$. For any $\delta\in(0,1)$: $$\beta_N=B+\frac{R}{\sqrt\lambda}\sqrt{\log\det\Big(\frac{\bar\lambda}{\lambda}K_N+\bar\lambda I_N\Big)-2\log\delta}$$ $$\Pr\big[\,|\mu_N(x)-f(x)|\le\beta_N\sigma_N(x)\ \ \forall N\in\mathbb N,\ \forall x\in D\,\big]\ge1-\delta$$ The information term is the realised $\log\det$ of the actual Gram matrix: no $\gamma_t$, any kernel, any $\lambda$.
Uniform error bound for GP sample paths (Lederer et al. 2019, Thm. 3.1)
$f$ is a sample from $\mathcal{GP}(0,k)$ on a compact $X$; observations $y=f(x)+\epsilon$ with i.i.d. $\mathcal N(0,\sigma_n^2)$ noise; $k$ continuous with Lipschitz constant $L_k$; $f$ Lipschitz with constant $L_f$; $M(\tau,X)$ the $\tau$-covering number of $X$. The posterior mean $\nu_N$ and standard deviation $\sigma_N$ are continuous, with Lipschitz constant $L_{\nu_N}$ and modulus of continuity $\omega_{\sigma_N}$ bounded by $$ L_{\nu_N}\le L_k\sqrt N\,\|(K+\sigma_n^2I)^{-1}y\|,\qquad\omega_{\sigma_N}(\tau)\le\sqrt{2\tau L_k\Big(1+N\,\|(K+\sigma_n^2I)^{-1}\|\max_{x,x'\in X}k(x,x')\Big)} $$ For any $\delta\in(0,1)$ and $\tau\gt0$, with $$ \beta(\tau)=2\log\frac{M(\tau,X)}{\delta},\qquad\gamma(\tau)=(L_{\nu_N}+L_f)\tau+\sqrt{\beta(\tau)}\,\omega_{\sigma_N}(\tau) $$ $$ \Pr\Big[\,|f(x)-\nu_N(x)|\le\sqrt{\beta(\tau)}\,\sigma_N(x)+\gamma(\tau)\ \ \forall x\in X\Big]\ge1-\delta,\qquad M(\tau,[0,r]^d)\le\big(1+r\sqrt d/\tau\big)^d $$ The covering bound uses the diameter $r\sqrt d$ of the cube, as in the paper’s appendix; its main-text eq. (9) prints $(1+r/\tau)^d$ with $r$ the edge length, which in the Euclidean metric is too small in high dimension.
Bias of the posterior mean under $\epsilon$-misspecification (Bogunovic & Krause 2021, Lemma 2)
Misspecification: $\min_{f\in\mathcal F_k(D;B)}\|f-f^*\|_\infty\le\epsilon$, i.e. the observed $f^*$ differs from some bounded-norm $\tilde f$ by an unknown $m(x)\in[-\epsilon,\epsilon]$. Let $\mu_t^*$ be the posterior mean computed from the actual observations $y_i^*=f^*(x_i)+\varepsilon_i$ and $\mu_t$ the one computed from the hypothetical (unobservable) noisy observations $y_i=\tilde f(x_i)+\varepsilon_i=y_i^*-m(x_i)$ of $\tilde f$: same inputs, same noise realisation $\varepsilon_i$, same $\lambda\gt0$, so that $y^*_{1:t}-y_{1:t}=m_{1:t}$ (noise-free values of $\tilde f$ would leave $\varepsilon_{1:t}$ in this difference, and the bound would fail even for $\epsilon=0$). Then for all $x$ and $t$: $$|\mu_t(x)-\mu_t^*(x)|\le\dfrac{\epsilon\sqrt t}{\sqrt\lambda}\,\sigma_t(x)$$

4. Safe Bayesian Optimization: SafeOpt & Controller Tuning

Algorithms: SafeOpt (Sui et al. 2015); practical variants SafeOpt-MC, StageOpt; Lipschitz-free sets (Berkenkamp et al. 2016).

Safe Bayesian optimization problem (Sui et al. 2015)
Finite decision set $D$ (a grid of controller parameters) and unknown $f: D \to \mathbb{R}$. At round $t = 1, 2, \dots$ choose $x_t \in D$ and observe $y_t = f(x_t) + n_t$. Goal: find a maximiser of $f$ while, for all rounds, $f(x_t) \ge h$, where $h \in \mathbb{R}$ is a known safety threshold.
Assumptions: what SafeOpt needs
(1) Safe seed: a non-empty $S_0 \subseteq D$ with $f(x) \ge h$ for all $x \in S_0$.
(2) RKHS regularity: $\|f\|_k \le B$ for a known kernel $k$ (module convention; Sui et al. write $\|f\|_k^2 \le B$).
(3) Lipschitz continuity: $|f(x) - f(x')| \le L\,d(x,x')$ for a known metric $d$ on $D$ and a known constant $L$.
(4) Noise $n_t$ zero-mean given the history and uniformly bounded by $\sigma$ (Sui et al.); later papers assume $\sigma$-sub-Gaussian noise, $\mathbb{E}[e^{\nu n_t} \mid \text{history}] \le e^{\nu^2\sigma^2/2}$ for all $\nu \in \mathbb R$.
Reachability operator and the ε-reachable optimum (Sui et al. 2015)
For $S \subseteq D$ and $\epsilon \ge 0$ the one-step reachability operator is $$ R_\epsilon(S) := S \cup \big\{x \in D : \exists x' \in S,\ f(x') - \epsilon - L\,d(x',x) \ge h\big\} $$ with $n$-fold iterate $R^n_\epsilon(S)$ and closure $\bar R_\epsilon(S) := \lim_{n\to\infty} R^n_\epsilon(S)$. Benchmark, the $\epsilon$-reachable maximum: $f^*_\epsilon := \max_{x \in \bar R_\epsilon(S_0)} f(x)$.
Confidence intervals, intersected over time
The posterior after $t-1$ observations gives, for every $x \in D$, $$ Q_t(x) := \big[\mu_{t-1}(x) - \beta_t\,\sigma_{t-1}(x),\ \mu_{t-1}(x) + \beta_t\,\sigma_{t-1}(x)\big] $$ (Module convention: $\beta_t$ is the half-width multiplier. Sui et al. write $\beta_t^{1/2}\sigma_{t-1}$; their $\beta_t$ is the square of ours.) SafeOpt uses the contained intervals $$ C_t(x) := C_{t-1}(x) \cap Q_t(x), \qquad C_0(x) = [h, \infty) \text{ for } x \in S_0, \quad C_0(x) = \mathbb{R} \text{ otherwise} $$ with lower bound $l_t(x) := \min C_t(x)$, upper bound $u_t(x) := \max C_t(x)$ and width $w_t(x) := u_t(x) - l_t(x)$.
SafeOpt safe set, expanders, maximisers and acquisition (Sui et al. 2015)
Safe set (pessimistic, grown with the Lipschitz constant from the previous safe set): $$ S_t := \bigcup_{x \in S_{t-1}} \big\{x' \in D : l_t(x) - L\,d(x,x') \ge h\big\} $$ Expanders (optimistic): $g_t(x)$ counts the uncertified points that could be certified from $x$ if $f(x)$ were as large as $u_t(x)$, $$ g_t(x) := \big|\{x' \in D \setminus S_t : u_t(x) - L\,d(x,x') \ge h\}\big|, \qquad G_t := \{x \in S_t : g_t(x) \gt 0\} $$ Maximisers (optimistic value at least the best pessimistic value): $$ M_t := \Big\{x \in S_t : u_t(x) \ge \max_{x' \in S_t} l_t(x')\Big\} $$ Acquisition (uncertainty sampling over the union): $x_t \in \operatorname*{arg\,max}_{x \in G_t \cup M_t} w_t(x)$.
Valid confidence intervals (Sui et al. 2015, Lemma 1; Srinivas et al. 2010, Thm. 6)
Suppose $\|f\|_k^2 \le B$ and the noise $n_t$ is zero-mean given the history and uniformly bounded by $\sigma$ for all $t$. Choose $$ \beta_t^{\mathrm{Sui}} = 2B + 300\,\gamma_t\log^3(t/\delta), \qquad \gamma_t := \max_{x_1,\dots,x_t \in D} I(f; y_{1:t}) = \max_{x_1,\dots,x_t \in D} \tfrac12\log\det\big(I_t + \sigma^{-2}K_t\big) $$ and $Q_t(x) = [\mu_{t-1}(x) \pm (\beta_t^{\mathrm{Sui}})^{1/2}\sigma_{t-1}(x)]$. Then with probability at least $1-\delta$, $f(x) \in C_t(x)$ for all $t \ge 1$ and all $x \in D$. Translation: with $\|f\|_k \le B$ (so $\|f\|_k^2 \le B^2$) the module’s half-width multiplier is $\beta_t = \sqrt{2B^2 + 300\,\gamma_t\log^3(t/\delta)}$. The analysis assumes $k(x,x) \le 1$.
SafeOpt is safe and converges to the ε-reachable optimum (Sui et al. 2015, Thm. 1)
Assume $f$ is $L$-Lipschitz, $\|f\|_k^2 \le B$, the noise is as in the Lemma, $S_0 \ne \emptyset$ and $f(x) \ge h$ for all $x \in S_0$. Choose $\beta_t^{\mathrm{Sui}}$ as in the Lemma, define $\hat x_t := \operatorname{arg\,max}_{x \in S_t} l_t(x)$, and let $t^*$ be the smallest positive integer with $$ \frac{t^*}{\beta^{\mathrm{Sui}}_{t^*}\,\gamma_{t^*}} \ \ge\ \frac{C_1\big(|\bar R_0(S_0)| + 1\big)}{\epsilon^2}, \qquad C_1 = \frac{8}{\log(1 + \sigma^{-2})} $$ Then for any $\epsilon \gt 0$ and $\delta \in (0,1)$ the following hold jointly with probability at least $1-\delta$: safety, $f(x_t) \ge h$ for all $t \ge 1$; optimality, $f(\hat x_t) \ge f^*_\epsilon - \epsilon$ for all $t \ge t^*$. In the module convention the condition reads $t^*/(\beta_{t^*}^2\gamma_{t^*}) \ge C_1(|\bar R_0(S_0)| + 1)/\epsilon^2$.
Lipschitz-free sets (Berkenkamp et al. 2016, eqs. 7 and 9)
With $l_n(a) = \mu_{n-1}(a) - \beta_n\sigma_{n-1}(a)$, $u_n(a) = \mu_{n-1}(a) + \beta_n\sigma_{n-1}(a)$ (no intersection over time), $$ S_n = \{a \in A : l_n(a) \ge J_{\min}\}, \qquad M_n = \Big\{a \in S_n : u_n(a) \ge \max_{a' \in S_n} l_n(a')\Big\} $$ $$ g_n(a) = \big|\{a' \in A \setminus S_n : l_{n,(a,u_n(a))}(a') \ge J_{\min}\}\big|, \qquad G_n = \{a \in S_n : g_n(a) \gt 0\} $$ where $l_{n,(a,u_n(a))}$ is the lower bound of the GP conditioned on the data and a fictitious noiseless observation $u_n(a)$ at $a$. The acquisition is unchanged, and the experiments use $\beta_n \equiv 2$.

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

Algorithms: Real-β-SafeOpt, LoSBO, LoS-GP-UCB (Fiedler et al. 2024); MCLoSBO (Menn et al. 2024); ET-GP-UCB (Brunzema et al. 2025).

Data-dependent frequentist GP bound (Fiedler et al. 2024, eq. 7; after Abbasi-Yadkori 2013)
(i) $k$ is a positive definite kernel and $f \in \mathcal{H}_k$ with $\|f\|_k \le B$; (ii) there is a filtration $(\mathcal{F}_t)$ such that each input $x_t$ is $\mathcal{F}_{t-1}$-measurable (predictable) and each $\epsilon_t$ is $\mathcal{F}_t$-measurable; (iii) the noise is conditionally $R$-sub-Gaussian: $\mathbb{E}[e^{\nu\epsilon_t}\mid\mathcal{F}_{t-1}] \le e^{R^2\nu^2/2}$ for all $\nu \in \mathbb{R}$; (iv) $\mu_t, \sigma_t$ are the GP posterior mean and standard deviation for a zero-mean prior with covariance $k$ and nominal noise variance $\lambda \gt 0$. For any $\delta \in (0,1)$, with $$ \beta_t = B + \frac{R}{\sqrt{\lambda}}\sqrt{2\ln\!\Big(\frac{1}{\delta}\det\big(I_t + \lambda^{-1}K_t\big)^{1/2}\Big)} \;=\; B + \frac{R}{\sqrt{\lambda}}\sqrt{\ln\det\big(I_t + \lambda^{-1}K_t\big) - 2\ln\delta} $$ $$ \mathbb{P}\Big[\,|f(x) - \mu_t(x)| \le \beta_t\,\sigma_t(x)\quad \forall x \in D,\ \forall t \ge 1\,\Big] \ge 1-\delta $$
LoSBO safety assumptions (Fiedler et al. 2024, Assumption 1)
(1) Lipschitz regularity: $D$ carries a metric $d$ and $f$ is $L$-Lipschitz with a known constant, $|f(x) - f(x')| \le L\,d(x,x')$ for all $x,x' \in D$.
(2) Bounded noise: $y_t = f(x_t) + \epsilon_t$ with $|\epsilon_t| \le E$ for all $t \ge 1$, $E$ known.
(3) Safe seed: a non-empty $S_0 \subseteq D$ with $f(x) \ge h$ for all $x \in S_0$.
Nothing is assumed about $f \in \mathcal{H}_k$, about $\|f\|_k$, about the kernel or its hyperparameters.
LoSBO safe set (Fiedler et al. 2024, eq. 11)
$$ S_t = S_{t-1} \cup \big\{\, x \in D \;:\; y_{t-1} - E - L\,d(x_{t-1}, x) \ge h \,\big\}, \qquad t \ge 1 $$ with $S_1 = S_0$ (no measurement yet). Lower the last measurement by the noise bound, hang a Lipschitz cone of slope $L$ below it, and certify every point where the cone is still above $h$. For $L\gt0$, $\{x : y - E - L\,d(x_s,x) \ge h\} = \bar B_r(x_s)$ with radius $r = (y - E - h)/L$ (empty if $y - E \lt h$), the safe set is a union of closed metric balls around queried points, plus $S_0$. If $L=0$, the new certificate is all of $D$ when $y-E\ge h$, and empty otherwise.
LoSBO is deterministically safe (Fiedler et al. 2024, Prop. 1)
Let $f$ be $L$-Lipschitz, $|\epsilon_t| \le E$ for all $t \ge 1$, and $\emptyset \ne S_0 \subseteq D$ with $f \ge h$ on $S_0$. Then for any choice of the scaling factors $\beta_t \gt 0$, LoSBO queries only safe inputs: $f(x_t) \ge h$ for all $t \ge 1$. By induction $f \ge h$ on every $S_t$: for $x \in S_{t-1}$ use the hypothesis; otherwise $y_{t-1} - E - L\,d(x_{t-1},x) \ge h$ and $$ f(x) = \underbrace{f(x_{t-1}) + \epsilon_{t-1}}_{y_{t-1}} - \epsilon_{t-1} + \big(f(x) - f(x_{t-1})\big) \;\ge\; y_{t-1} - E - L\,d(x_{t-1},x) \;\ge\; h. \qquad\blacksquare $$ The guarantee holds surely, not with probability $1-\delta$.
LoS-GP-UCB (Fiedler et al. 2024, eqs. 13–16)
Start from GP-UCB, $x_{t+1} = \arg\max_{x\in D}\ \mu_t(x) + \beta_t\sigma_t(x)$, restrict it to the LoSBO safe set, $x_{t+1} = \arg\max_{x \in S_t}\ \mu_t(x) + \beta_t\sigma_t(x)$, and use the ball decomposition to split the constrained problem into $N_t$ independent problems, one per ball, with $a_t(x) = \mu_t(x) + \beta_t\sigma_t(x)$: $$ x_j^\star \in \operatorname*{arg\,max}_{x \in \bar B_{r_j}(z_j)} a_t(x) \quad (j = 1,\dots,N_t), \qquad x_{t+1} = x_{j^\star}^\star \ \text{ with } \ j^\star \in \operatorname*{arg\,max}_{j = 1,\dots,N_t} a_t(x_j^\star) $$ After the query, add the new centre $x_{t+1}$ with radius $(y_{t+1} - E - h)/L$.
MCLoSBO safe set (Menn et al. 2024, eq. 5 as read in Module 5) and Prop. 3
Each constraint $i \in I_g$ keeps its own LoSBO set, accumulated over all measured points; a parameter is safe once every constraint certifies it, possibly from different measurements: $$ S_n = \bigcap_{i \in I_g} A_{i,n}, \qquad A_{i,n} = A_{i,n-1} \cup \big\{\theta' \in \Theta : y_{i,n-1} - E_i - L_i\|\theta_{n-1} - \theta'\| \ge 0\big\}, \qquad A_{i,0} = S_0 $$ (Module 5’s reading of the paper’s eq. (5): the printed index of $y$ does not track $\theta$.) Assumptions: each $g_i$ is $L_i$-Lipschitz, $|g_i(\theta) - g_i(\theta')| \le L_i\|\theta - \theta'\|$, and $|\epsilon_{i,n}| \le E_i$. Proposition 3. For any $\beta \in \mathbb{R}_+$, MCLoSBO yields only safe inputs: $g_i(\theta_n) \ge 0$ for all $i \in I_g$ and $n \ge 1$.
ET-GP-UCB event trigger (Brunzema et al. 2025, Def. 2, Lemma 3, eq. 11)
Let $t_r$ count the steps since the last reset and pick $\pi_{t_r} \gt 0$ with $\sum_{t_r \ge 1}\pi_{t_r}^{-1} = 1$ (e.g. $\pi_{t_r} = \pi^2 t_r^2/6$). With $$ \rho_{t_r} = 2\ln\frac{2\pi_{t_r}}{\delta_B}, \qquad \bar w_{t_r}^2 = 2\sigma_n^2\ln\frac{2\pi_{t_r}}{\delta_B} $$ the trigger resets the dataset iff $$ \gamma_{\mathrm{reset}} = 1 \iff \underbrace{|y_t - \mu_{D_t}(x_t)|}_{\text{test } \psi_t} \;\gt\; \underbrace{\sqrt{\rho_{t_r}}\,\sigma_{D_t}(x_t) + \bar w_{t_r}}_{\text{threshold } \kappa_t} $$ Lemma 3. Assume the paper’s Bayesian model with nothing changed: $f_t = \sqrt{1-\varepsilon}\,f_{t-1} + \sqrt{\varepsilon}\,g_t$ with i.i.d. $g_t \sim \mathcal{GP}(0,k)$ and rate $\varepsilon = 0$, so $f_t = f \sim \mathcal{GP}(0,k)$ (Assumption 2); observations $y_t = f(x_t) + w_t$ with i.i.d. $w_t \sim \mathcal N(0,\sigma_n^2)$ (Assumption 1); and $\mu_{D_t}$, $\sigma_{D_t}$ the posterior from the data $D_t$ collected since the last reset, before $y_t$. Then with probability at least $1 - \delta_B$ the threshold is exceeded at no $t_r \ge 1$ of the current segment. So a trigger is evidence of change at level $\delta_B$, the single design parameter, but only under this GP-sample, Gaussian-noise model (not the frequentist RKHS or bounded-noise settings of the boxes above) and only per segment: every reset, forced ones included, restarts $t_r$ and the union bound, so over $m$ segments of a stationary run the false-trigger probability is only bounded by $m\delta_B$.

6. Global Safe Exploration of Dynamical Systems: GoSafe & GoSafeOpt

Algorithms: GoSafe (Baumann et al. 2021), GoSafeOpt (Sukhija et al. 2023); safe exploration in MDPs: SafeMDP, SNO-MDP, ActSafe.

Reachability operators and safely reachable closures (Sukhija et al. 2023, eq. A.12–A.13; Berkenkamp et al. 2023, eq. 8)
Let $S\subseteq A$ be a set of parameters whose constraint values are known up to accuracy $\epsilon$ and $L_a$ a Lipschitz constant of the constraints $g_i$ in the parameter. GoSafeOpt’s Lipschitz step asks for one common witness $a'$ for all constraints: $$ R^c_\epsilon(S) := S\cup\Big\{a\in A \;\Big|\; \exists a'\in S:\ g_i(a') - \epsilon - L_a\|a-a'\| \ge 0\ \ \forall i\in I_g\Big\},\qquad \bar R^c_\epsilon(S) := \lim_{n\to\infty} (R^c_\epsilon)^n(S) $$ SafeOpt-MC’s operator lets every constraint have its own witness: $$ R_\epsilon(S) := S\cup\Big\{a\in A \;\Big|\; \forall i\in I_g\ \exists a'_i\in S:\ g_i(a'_i) - \epsilon - L_a\|a-a'_i\| \ge 0\Big\},\qquad \bar R_\epsilon(S) := \lim_{n\to\infty} R_\epsilon^n(S) $$ $\bar R_\epsilon(S)$ is the largest set that any method relying only on Lipschitz continuity can certify by starting from $S$ and repeatedly learning the constraints to accuracy $\epsilon$ at parameters it has already certified, never evaluating an uncertified one. Always $\bar R^c_\epsilon(S)\subseteq\bar R_\epsilon(S)$, with equality for a single constraint (the $\bar R_\epsilon$ of Module 4). With several constraints the inclusion can be strict: for $A=\{0,1,2\}$, $S=\{0,2\}$, $g_1(a)=2-a$, $g_2(a)=a$, $L_a=1$, $\epsilon=0.1$, the witness $0$ certifies $a=1$ for $g_1$ and the witness $2$ for $g_2$, but no single witness does both, so $\bar R^c_\epsilon(S)=S$ while $\bar R_\epsilon(S)=A$. GoSafeOpt uses $\bar R^c_\epsilon$ as the benchmark its LSE provably reaches, not as a limit on what can be certified.
Trajectory-minimum constraints (Sukhija et al. 2023, Assumption 2.5)
Each $g_i$ is the minimum of a state-dependent immediate constraint $\bar g_i:X\to\mathbb R$ along the trajectory, $$ g_i(a)=\min_{x'\in\xi_{(0,x_0,a)}}\bar g_i(x'),\qquad \xi_{(t,x,a)}:=\Big\{x+\int_t^{t'} z\big(x(\tau),\pi^a(x(\tau))\big)\,\mathrm d\tau\ \Big|\ t'\ge t\Big\} $$ where $\xi_{(t,x,a)}$ is the set of states visited when policy $a$ is started at state $x$ at time $t$. The proofs use the two-argument version $g_i(a,x):=\min_{x'\in\xi_{(0,x,a)}}\bar g_i(x')$, so that $g_i(a)=g_i(a,x_0)$.
Safe experiment (Sukhija et al. 2023, Def. 2.6) and bounded motion (Assumption 2.4)
An experiment is safe if $\bar g_i(x(t))\ge 0$ for all $t\ge0$ and all $i\in I_g$; this also covers experiments in which different portions of the trajectory are generated by different controllers (a triggered backup). The state is measured every $\Delta t$ seconds, and for any $x(t)$, any $\rho\in[0,1]$ and any action, $\|x(t+\rho\Delta t)-x(t)\|\le\Xi$ for a known constant $\Xi$.
GoSafe safe-set update (Baumann et al. 2021, arXiv version of eq. 3)
Confidence sets $Q_n(a,\tilde x_0,i)=[\mu_{n-1}\pm\beta_n\sigma_{n-1}](a,\tilde x_0,i)$, contained sets $C_n=C_{n-1}\cap Q_n$ initialised as $C_0=[L_x\mu,\infty)$ on $S_0$ and $\mathbb R$ elsewhere (for the constraint indices $i\in I_g$), and $l_n=\min C_n$, $u_n=\max C_n$: $$ S_n=\bigcap_{i\in I_g}\ \bigcup_{(a,\tilde x_0)\in S_{n-1}}\Big\{(a',\tilde x_0')\in A\times X_\mu\ \Big|\ l_n(a,\tilde x_0,i)-L_a\|a-a'\|_1-L_x\big(\|\tilde x_0-\tilde x_0'\|_1+\mu\big)\ge0\Big\}\ \cup\ S_{n-1} $$ The extra $+\mu$ inside the state term makes the certificate cover the whole quantisation cell of $\tilde x_0'$, not just the grid point.
GoSafe safety and convergence (Baumann et al. 2021, Thms. 1–2, Cor. 1)
Assume $h(a,\tilde x_0,i)$, $i\in I_g$, has RKHS norm at most $B$, the noise is $\sigma$-sub-Gaussian, $S_0\neq\emptyset$ with $g_i(a,\tilde x_0)\gt L_x\mu$ on $S_0$, and the confidence multiplier is $$\beta_n = B+4\sigma\sqrt{\gamma_{(n-1)|I|}+1+\ln(1/\delta)}$$ (the paper writes this as $\beta_n^{1/2}$; the information gain is indexed by $(n-1)|I|$ because each experiment yields $|I|$ measurements). Then with probability at least $1-\delta$, $\bar g_i(x_n(t))\ge0$ for all $n\ge1$, all $t$ and all $i\in I_g$ (Thm. 1). GoSafe converges with $\epsilon$-precision to the optimum within $\bar R^g_\epsilon(S_0)$ (Thm. 2), where the global reachability operator adds to $R^c_\epsilon$ (here GoSafe’s version on pairs $(a,\tilde x_0)$: one common witness $(a',\tilde x_0')\in S$ for all $i$, with the extra state term $L_x(\|\tilde x_0-\tilde x_0'\|_1+\mu)$ as in the safe-set update above) all pairs $(a,\tilde x_0)$ that have a backup $(a',\tilde x_0)\in S$ and whose quantised trajectory never touches $\partial R^c_\epsilon(S)$. Cor. 1: if the quantised trajectory of the true optimum $a^*$ from $x_0$ never touches $\partial\bar R^g_\epsilon(S_0)$, then $(a^*,x_0)\in\bar R^g_\epsilon(S_0)$ and GoSafe finds an $\epsilon$-optimal solution.
GoSafeOpt boundary condition and backup selection (Sukhija et al. 2023, Sec. 4.1.3, eq. 12)
At iteration $n$, trigger a backup at the measured state $x$ if and only if there is no backup pair $(a_s,x_s)\in\mathcal B_n$ with $$ l_n(a_s,i)\ \ge\ L_x\big(\|x-x_s\|+\Xi\big)\qquad\text{for all } i\in I_g $$ When triggered, switch to the backup parameter with the largest safety margin at the current state, $$ (a_s^*,x_s^*)\in\arg\max_{(a_s,x_s)\in\mathcal B_n}\ \min_{i\in I_g}\ l_n(a_s,i)-L_x\|x-x_s\| $$ apply $a_s^*$ and keep it for the rest of the experiment. Read the condition as a certified ball: backup $(a_s,x_s)$ covers all states within distance $\min_{i\in I_g}l_n(a_s,i)/L_x-\Xi$ of $x_s$; the experiment may continue as long as the current state is inside at least one ball.
Every state visited by a safe policy is a backup point (Sukhija et al. 2023, Prop. A.3)
Let Assumption 2.5 hold. If $(a,x_0)$ is safe, i.e. $g_i(a,x_0)=\min_{x'\in\xi_{(0,x_0,a)}}\bar g_i(x')\ge0$ for all $i\in I_g$, then for every $t_1\ge0$ the pair $(a,x(t_1))$ is also safe: $g_i(a,x(t_1))\ge0$ for all $i\in I_g$.
GoSafeOpt is safe (Sukhija et al. 2023, Thm. 4.1)
Under Assumptions 2.1–2.5 (known safe seed; $h$ in an RKHS with $\|h\|_k\le B$ and Lipschitz constants $L_a$, $L_x$; i.i.d. $\sigma$-sub-Gaussian measurement noise; state sampled every $\Delta t$ with motion bound $\Xi$; trajectory-minimum constraints) and with $\beta_n$ chosen as in SafeOpt-MC, GoSafeOpt guarantees for all $n\ge0$ and any $\delta\in(0,1)$ that every experiment is safe in the sense of Definition 2.6 with probability at least $1-\delta$.
Discoverability and convergence to the safe global optimum (Sukhija et al. 2023, Def. 4.2, Thm. 4.3)
A parameter $a\in A$ is discoverable at iteration $n$ if there is a set $A'\subseteq S_n$ with $a\in\bar R^c_\epsilon(A')$. Let $a^*$ be a safe global optimum, let Assumptions 2.1–2.5 hold with $\beta_n$ as in SafeOpt-MC, and assume $a^*$ is discoverable at some finite iteration $\tilde n\ge0$. Then for any $\epsilon\gt0$ and $\delta\in(0,1)$ there is a finite $n^*\ge\tilde n$ such that with probability at least $1-\delta$, $$ f(\hat a_n)\ \ge\ f(a^*)-\epsilon\qquad\text{for all } n\ge n^*,\qquad \hat a_n=\arg\max_{a\in S_n}l_n(a,0) $$

7. Viability & Safe Value Functions

Algorithms: viability iteration (finite $X \times U$, deterministic $f$); learning the safety measure (Heim et al., Alg. 1); uncertainty-aware safe RL at DSME: UPSi, Dyna-SAuR, CHEQ.

Viability kernel and unviability kernel (Massiani et al. 2023, Def. 1)
Failure set $X_F\subset X$ (closed, absorbing), $\mathcal U$ the set of measurable feedback controllers, $\varphi^u_x$ the trajectory from $x$ under $u$, $\mathbb{T} = \mathbb{R}_+$ or $\mathbb{T} = \mathbb{N}$: $$ X_V = \{\,x \in X : \exists u \in \mathcal{U},\ \forall t \in \mathbb{T},\ \varphi^u_x(t) \notin X_F\,\}, \qquad X_U = X \setminus X_V $$ $x$ is viable if some controller keeps the trajectory out of the failure set for all time. $X_V$ is the maximal controlled-invariant subset of $X \setminus X_F$.
Safe controller and viable set (Massiani et al. 2023; Heim et al. 2019)
A controller $u$ is safe for the point $x$ if $\varphi^u_x(t) \notin X_F$ for all $t \in \mathbb{T}$. In discrete time the viable set is the set of pairs that transition into the kernel, $$ Q_V = f^{-1}(X_V) = \{(x,u) : f(x,u) \in X_V\} \subset X_V \times U, \qquad Q_U = (X \times U) \setminus Q_V $$ with slice $Q_V[x] = \{u : (x,u) \in Q_V\}$. The kernel is the projection of $Q_V$ onto the state space, and $Q_V[x] \neq \emptyset$ exactly when $x \in X_V$.
Safety measure and safe level sets (Heim et al. 2019, Defs. 3–5)
The safety measure is the volume of the slice of the viable set at $s$, $$ \Lambda(s) = \operatorname{vol}\{a \in A : (s,a) \in Q_V\} $$ Lebesgue measure on continuous action spaces, counting measure on discrete ones. Q-safety measure $\Lambda_Q(q) = \Lambda(T(q))$; for a level $\lambda \ge 0$ the safe level sets are $S_\lambda = \{s : \Lambda(s) \gt \lambda\}$ and $Q_\lambda = \{q : \Lambda_Q(q) \gt \lambda\}$. With the counting measure the viable set is recovered as $Q_V = Q_{\lambda = 0}$.
Optimistic and cautious sets of a GP over the safety measure (Heim et al. 2019)
Model $\hat\Lambda_Q(q) \mid \mathcal{D} \sim \mathcal{N}(\mu(q), \sigma^2(q))$ with a Gaussian process on $\mathcal{D} = \{(q_i, \hat\Lambda_i(s'_i))\}$. Two thresholded sets drive learning: $$ \begin{aligned} \hat Q_{\mathrm{opt}}(\gamma_{\mathrm{opt}}) &= \{q : P[\hat\Lambda_Q \gt 0] \gt \gamma_{\mathrm{opt}}\}, \\ \hat Q_{\mathrm{caut}}(\gamma_{\mathrm{caut}}, \lambda_{\mathrm{caut}}) &= \{q : P[\hat\Lambda_Q \gt \lambda_{\mathrm{caut}}] \gt \gamma_{\mathrm{caut}}\}. \end{aligned} $$ $\hat Q_{\mathrm{opt}}$ is used to compute $\hat\Lambda$ (optimism, needed for convergence); $\hat Q_{\mathrm{caut}}$ is used for active sampling (caution, needed to avoid failures). $\gamma_{\mathrm{opt}}$, $\gamma_{\mathrm{caut}} \in [0,1]$ are confidence levels, not discount factors; $\gamma_{\mathrm{caut}} \ge \gamma_{\mathrm{opt}}$ gives $\hat Q_{\mathrm{caut}} \subseteq \hat Q_{\mathrm{opt}}$.
Critical set and admissible constraints (Massiani, Heim & Trimpe, L4DC 2021, Def. 5 and Thm. 6)
The critical set is the set of unviable pairs at viable states that the projection would prefer over the optimal viable action: $$ Q_{\mathrm{crit}} = \{(s,a) \in Q \setminus Q_V : s \in S_V,\ J(s,a) \le J(s, \mathrm{OPT}(Q_V)(s))\} $$ Theorem 6. Assume $Q_V$ is closed, and let $K$ be closed with $\mathrm{OPT}(Q_V) \subseteq K$. Then $\mathrm{OPT}(K)(s) = \mathrm{OPT}(Q_V)(s)$ for all $s \in S_V$ if, and only if, $K \cap Q_{\mathrm{crit}} = \emptyset$. Such a $K$ is called admissible.
Discounted risk (Massiani et al. 2023, Lemma 1)
For $x \in X$ and $u \in \mathcal{U}$ define $$ \rho(x,u) = \int_{\mathbb{T}} e^{-t/\tau}\, \delta_{X_F}\big(\varphi^u_x(t)\big)\, dt $$ where $\delta_{X_F}$ is the indicator function in discrete time and, in the paper’s words, “the Dirac distribution” in continuous time: $\delta_{X_F}(\varphi^u_x(t))\,dt$ stands for the unit point mass $\delta_{t_f}(dt)$ at the failure instant (a spatial Dirac composed with the trajectory would give $1/|\dot x(t_f)|$ for a scalar crossing). With the sink convention of Remark 1 (see the Lemma 2 box) this gives $\rho(x,u)=e^{-t_f/\tau}$, and $0$ if the trajectory never fails. Then $u$ is safe for $x$ if, and only if, $\rho(x,u) = 0$.
Constrained problem (C) and penalised problem (P) (Massiani et al. 2023)
Maximise the expected return over safe controllers, for an initial distribution $\mu$ supported in $X_V$: $$ \text{(C)} \qquad \sup_{u \in \mathcal{U}_{\mathrm{safe}}} \mathbb{E}_{x \sim \mu}\big[G(x,u)\big], \qquad\qquad V : x \in X_V \mapsto \sup_{u \in \mathcal{U}_{\mathrm{safe}}} G(x,u) $$ Relax by replacing $r$ with $r - p\,\delta_{X_F}$ for a constant designer-chosen penalty $p \in \mathbb{R}_+$: $$ \text{(P)} \qquad V_p : x \in X \mapsto \sup_{u \in \mathcal{U}} \big[G(x,u) - p\,\rho(x,u)\big] $$
Safe value function and Proposition 1 (Massiani et al. 2023, Def. 3)
$V_p$ is a safe value function (SVF) if all of its optimal controllers are both safe and optimal with respect to (C). Proposition 1. If $V_p$ is an SVF, then $V_p(x) = V(x)$ for all $x \in X_V$.
Zeroth-order condition for safety (Massiani et al. 2023, Thm. 1)
Consider $V_p$ from (P) and assume the zeroth-order condition holds: $$ \text{(Za)} \qquad \sup_{X_U} V_p \ \lt\ \inf_{X_V} V \qquad\qquad \text{if } \mathbb{T} = \mathbb{R}_+ $$ $$ \text{(Zb)} \qquad R_{Q_U} + \gamma \sup_{X_U} V_p \ \lt\ R_{Q_V} + \gamma \inf_{X_V} V \qquad \text{if } \mathbb{T} = \mathbb{N} $$ with $R_{Q_U} = \sup_{Q_U} r$ and $R_{Q_V} = \inf_{Q_V} r$. Then $V_p$ is a safe value function: all of its optimal controllers are safe and optimal for (C).
Influence of the penalty (Massiani et al. 2023, Remark 1, Assumption 1 and Lemma 2)
Convention (Remark 1): on reaching $X_F$ the system jumps to a zero-reward sink (bookkeeping, not a state of $X$), so the return stops at the failure time $t_f$ and the penalty is charged once, $\rho(x,u)=e^{-t_f/\tau}$ (continuous) or $\gamma^{t_f}$ (discrete). Assumption 1: the time-to-failure in $X_U$ is uniformly upper bounded by some $T_f \in \mathbb{T}$, i.e. for every $x \in X_U$ and every controller $u$, the trajectory $\varphi^u_x$ enters $X_F$ at a time $t_f(x,u) \le T_f$. Then: (i) for every $x \in X$ the map $p \mapsto V_p(x)$ is nonincreasing; (ii) the value function is uniformly upper bounded on $X_U$, $$ \begin{aligned} \sup_{X_U} V_p &\le R_{X_U}\, \tau \big(1 - e^{-T_f/\tau}\big) - p\, e^{-T_f/\tau} && (\mathbb{T} = \mathbb{R}_+), \\ \sup_{X_U} V_p &\le R_{X_U}\, \frac{1 - \gamma^{T_f + 1}}{1 - \gamma} - p\, \gamma^{T_f} && (\mathbb{T} = \mathbb{N}), \end{aligned} $$ with $R_{X_U} = \max\{0,\ \sup_{X_U \times U} r\}$. The paper writes $R_{X_U} = \sup_{X_U \times U} r$, but the bound extends the reward sum from $t_f$ to $T_f$, which needs $R_{X_U} \ge 0$: with a living cost $r \equiv -c$ on $X_U$ the unclipped value $-c$ gives a false bound (the agent can fail early and stop paying).
Finite penalty threshold p* (Massiani et al. 2023, Thm. 2)
Under Assumption 1, with the sink convention and the nonnegative $R_{X_U}$ of Lemma 2, there exists a finite threshold $p^\star \in \mathbb{R}$ such that for all penalties $p \ge 0$ with $p \gt p^\star$ the penalised value function $V_p$ is safe and the zeroth-order condition (Z) holds, with $$ p^\star = \Big(R_{X_U}\,\tau - \inf_{X_V} V\Big)\, e^{T_f/\tau} - R_{X_U}\,\tau \qquad (\mathbb{T} = \mathbb{R}_+) $$ $$ p^\star = \frac{1}{\gamma^{T_f}} \left[ R_{X_U}\, \frac{1 - \gamma^{T_f+1}}{1 - \gamma} + \frac{R_{Q_U} - R_{Q_V}}{\gamma} - \inf_{X_V} V \right] \qquad (\mathbb{T} = \mathbb{N}) $$ The paper writes $p^\star \in \mathbb{R}_+$, but both expressions can be negative (e.g. large rewards inside $X_V$); then every $p \ge 0$ is certified, $p = 0$ included, and $\max\{0, p^\star\}$ is the nonnegative threshold.
Thresholding recovers the kernel; Vp as a CBF (Massiani et al. 2023, Props. 2–3)
Let $V_p$ be an SVF for which (Z) holds, and let $\alpha_{\inf}$, $\alpha_{\sup}$ be the left- and right-hand sides of (Z). For every $\alpha \in (\alpha_{\inf}, \alpha_{\sup}]$, $$ \begin{aligned} X_V &= \{x : V_p(x) \ge \alpha\} && (\mathbb{T} = \mathbb{R}_+), \\ X_V &= \{x : \exists u \in Q_V[x],\ r(x,u) + \gamma V_p(x) \ge \alpha\} && (\mathbb{T} = \mathbb{N}). \end{aligned} $$ (Read literally, the discrete version is satisfied by every $x$ with $Q_V[x] \neq \emptyset$; the informative reading thresholds the one-step look-ahead over all inputs: $X_V = \{x : \exists u \in U,\ r(x,u) + \gamma V_p(f(x,u)) \ge \alpha\}$.) If moreover $\mathbb{T} = \mathbb{R}_+$, $V_p|_{X_V}$ is continuously differentiable, $X_V$ is compact and $\partial V_p / \partial x \neq 0$ on $\partial X_V$, the paper concludes (Prop. 3) that $h = V_p|_{X_V} - \alpha$ is a control barrier function of $X_V$. This holds only in a restricted-domain sense that certifies nothing: for $\alpha \lt \alpha_{\sup}$, $h \ge \inf_{X_V} V - \alpha \gt 0$ on all of $X_V$, boundary included, so the CBF inequality constrains no input at $\partial X_V$. A CBF for the whole kernel needs a $C^1$ function that vanishes exactly on $\partial X_V$ (Module 7).
Maximum-entropy RL: soft Q-function and optimal policy (as used in Massiani et al. 2025)
Return $G(x,\pi) = \sum_t \gamma^t r(X_t, A_t)$ with expectation $\bar G$; discounted cumulative entropy $S(x,\pi) = \sum_t \gamma^t H(\pi(\cdot \mid X_t))$ with expectation $\bar S$. The entropy-regularised objective with temperature $\alpha \ge 0$ is $\max_\pi \bar G(x,\pi) + \alpha \bar S(x,\pi)$ for all $x$. For $\alpha \gt 0$ its optimal soft Q-function $q$ satisfies $$ q(x,a) = r(x,a) + \gamma \alpha \ln \sum_{b \in A} \exp\Big(\tfrac{1}{\alpha} q(x', b)\Big), \qquad x' = f(x,a) $$ and the optimal policy is the softmax $\pi_{\mathrm{opt}}(a \mid x) = \operatorname{softmax}\big(q(x,\cdot)/\alpha\big)(a)$. Both formulas divide by $\alpha$; at $\alpha = 0$ (their zero-temperature limit) they become the ordinary Bellman equation $q(x,a) = r(x,a) + \gamma \max_b q(x',b)$, and the optimal policies are those supported on $\arg\max_b q(x,b)$.
δ-safety for large penalties (Massiani et al. 2025, Thm. 2 and Cor. 2)
A policy is $\delta$-safe if $\max_{Q_{\mathrm{crit}}} \pi \le \delta$. For any $\delta \gt 0$, $\epsilon \gt 0$ and $\alpha \gt 0$ there exists $p^\star \ge 0$ such that for all $p \gt p^\star$ the optimal policy $\pi^\star_{\alpha,p}$ of the penalised problem is $\delta$-safe and $$ \max_{Q_V} \big|\pi^\star_{\alpha,p} - \pi^\star_\alpha\big| \ \lt\ \epsilon $$ Cor. 2: there is $\bar\delta \in (0,1)$ such that for $\delta \in (0, \bar\delta)$ the policy that follows the mode of $\pi^\star_{\alpha,p}$ is safe.

8. CMDPs, Duality & Lagrangian Methods

Algorithms: dual descent for constrained RL (Paternain et al. 2019, Alg. 1); RCPO (Tessler et al. 2019); PID-controlled Lagrange multiplier (Stooke et al. 2020); RPG-PD (Ding et al. 2023); Sauté MDP (Sootla et al. 2022).

Constrained Markov decision process (Altman 1999)
A CMDP is a tuple $(\mathcal S, \mathcal A, P, \mu, r, \{c_i\}_{i=1}^m, \{d_i\}_{i=1}^m, \gamma)$ with transition kernel $P(s'\mid s,a)$, initial distribution $\mu$, reward $r:\mathcal S\times\mathcal A\to\mathbb R$, $m$ cost functions $c_i:\mathcal S\times\mathcal A\to\mathbb R$ with budgets $d_i\in\mathbb R$, and a discount $\gamma\in(0,1)$. For a (possibly history-dependent) policy $\pi$ the discounted return and cost returns are $$ J_r(\pi) := \mathbb E^{\pi}_{\mu}\Big[\sum_{t=0}^{\infty}\gamma^t r(s_t,a_t)\Big],\qquad J_{c_i}(\pi) := \mathbb E^{\pi}_{\mu}\Big[\sum_{t=0}^{\infty}\gamma^t c_i(s_t,a_t)\Big] $$ and the CMDP problem is $$ P^\star := \max_{\pi}\ J_r(\pi)\quad\text{s.t.}\quad J_{c_i}(\pi)\le d_i,\ \ i=1,\dots,m. \qquad\text{(CMDP)} $$ For finite CMDPs the maximum is attained (occupancy LP); in general state and action spaces read $\max$ as $\sup$, which need not be attained even with bounded rewards and Slater’s condition (one state, actions $a\in[0,1]$, $r(a)=a$ for $a\lt1$, $r(1)=0$, zero cost).
Occupancy measure
For a policy $\pi$ and initial law $\mu$, the (normalised, discounted) occupancy measure is $$ \rho_\pi(s,a) := (1-\gamma)\sum_{t=0}^{\infty}\gamma^t\,\mathbb P^{\pi}_{\mu}(s_t=s,\ a_t=a),\qquad \rho_\pi(s):=\sum_a\rho_\pi(s,a) $$ a probability measure on $\mathcal S\times\mathcal A$, and every discounted return is an expectation under it: $$ J_r(\pi)=\frac{1}{1-\gamma}\sum_{s,a}\rho_\pi(s,a)\,r(s,a)=\frac{\langle\rho_\pi,r\rangle}{1-\gamma},\qquad J_{c_i}(\pi)=\frac{\langle\rho_\pi,c_i\rangle}{1-\gamma} $$
Occupancy LP and stationary policies (Altman 1999, Thms 3.1–3.3)
$$ \begin{aligned} \max_{\rho\ \ge\ 0}\quad & \frac{1}{1-\gamma}\langle\rho,r\rangle\\ \text{s.t.}\quad & \frac{1}{1-\gamma}\langle\rho,c_i\rangle\le d_i,\qquad i=1,\dots,m,\\ & \sum_a\rho(s,a)-\gamma\sum_{s',a'}\rho(s',a')P(s\mid s',a')=(1-\gamma)\mu(s)\qquad\forall s. \end{aligned} $$ Its optimal value is $P^\star$. For a finite CMDP, every $\rho$ feasible for the flow constraints is the occupancy measure of the stationary policy $$ \pi_\rho(a\mid s):=\frac{\rho(s,a)}{\sum_{a'}\rho(s,a')}\qquad(\text{arbitrary where the denominator vanishes}) $$ and the set of such $\rho$ is a closed convex polytope whose vertices are occupancy measures of deterministic policies; an optimal $\rho^\star$ yields the optimal policy $\pi_{\rho^\star}$.
Lagrangian, dual function, dual problem
$$ L(\pi,\lambda):=J_r(\pi)-\sum_{i=1}^m\lambda_i\big(J_{c_i}(\pi)-d_i\big),\qquad D(\lambda):=\max_{\pi}L(\pi,\lambda),\qquad D^\star:=\min_{\lambda\in\mathbb R^m_+}D(\lambda) $$ For fixed $\lambda$, maximising $L$ is an ordinary MDP with the penalised reward $r_\lambda=r-\sum_i\lambda_ic_i$ (plus the constant $\langle\lambda,d\rangle$). Slater’s condition asks for a strictly feasible policy: $\bar\pi$ with $J_{c_i}(\bar\pi)\le d_i-\xi$ for some margin $\xi\gt0$ and all $i$.
Zero duality gap for CMDPs (Paternain, Chamon, Calvo-Fullana & Ribeiro, NeurIPS 2019, Thm 1)
Assumptions: (A1) the reward and all costs are bounded; (A2) Slater’s condition holds. Then strong duality holds: $P^\star=D^\star$, although the CMDP is non-convex in $\pi$.
Slater’s margin bounds the multiplier (Ding et al., journal version, Lemma 3)
If $\bar\pi$ is feasible with margin $\xi$, every dual optimum satisfies $$\|\lambda^\star\|_1\le\big(P^\star-J_r(\bar\pi)\big)/\xi$$ (there stated for one constraint). Proof: $D^\star=D(\lambda^\star)\ge L(\bar\pi,\lambda^\star)=J_r(\bar\pi)+\sum_i\lambda^\star_i\big(d_i-J_{c_i}(\bar\pi)\big)\ge J_r(\bar\pi)+\xi\|\lambda^\star\|_1$, and $D^\star=P^\star$.
Duality gap of an ε-universal parametrisation (Paternain et al. 2019, Def. 1 and Thm 2)
A parametrisation is $\epsilon$-universal if for every policy $\pi$ there is $\theta$ with $\max_{s}\int_{\mathcal A}|\pi(a\mid s)-\pi_\theta(a\mid s)|\,da\le\epsilon$. Suppose $|r|\le B_{r_0}$, $|c_i|\le B_c$ with $B_c=\max_i B_{c_i}$, and let $\lambda^\star_\epsilon$ be the dual solution of the tightened problem with budgets $d_i-B_c\Delta_\epsilon$. Under the assumptions of the zero-gap theorem, $$ P^\star\ \ge\ D^\star_\theta\ \ge\ P^\star-\big(B_{r_0}+\|\lambda^\star_\epsilon\|_1B_c\big)\,\Delta_\epsilon,\qquad \Delta_\epsilon=\frac{\epsilon}{(1-\gamma)^2} $$ The bound is informative when the tightened problem is still strictly feasible; a policy with Slater margin $\xi\gt B_c\Delta_\epsilon$ certifies this (sufficient, not necessary: another policy may have a larger margin). If the tightened problem is infeasible, $\lambda^\star_\epsilon$ has “infinite norm” and the bound is vacuous.
Optimal policies are Lagrangian maximisers, not conversely (Calvo-Fullana et al. 2024, Prop. 1)
Under zero duality gap, $\Pi^\star\subseteq\Pi(\lambda^\star)$, and every $\pi^\star\in\Pi^\star$ satisfies complementary slackness $\lambda_i^\star\big(J_{c_i}(\pi^\star)-d_i\big)=0$. Here $\Pi^\star$ is the set of optimal policies and $\Pi(\lambda)$ the set of maximisers of $L(\cdot,\lambda)$.
Safe policies from a CMDP relaxation (Paternain et al. 2023, Def. 1 and Thm 1)
A policy is $(1-\delta)$-safe for $S_0\subseteq\mathcal S$ if $\mathbb P\big(\bigcap_{t\ge0}\{s_t\in S_0\}\mid\pi\big)\ge1-\delta$. Replace the chance constraint by the expected discounted occupation time $U_i(\theta):=\sum_t\gamma^t\,\mathbb P(s_t\in S_i\mid\pi_\theta)\ge c_i$ (here $c_i$ is a threshold, not a cost function). For $\gamma=1$ and a finite horizon $T$, choosing $$ c_i=(T+1)\Big(1-\frac{\delta_i}{T+1}\Big)=T+1-\delta_i $$ makes every feasible policy $(1-\delta_i)$-safe for $S_i$ up to time $T$.
Dual gradient is the constraint violation; dual descent
If $\pi_\lambda\in\Pi(\lambda)$ is any maximiser of $L(\cdot,\lambda)$, then $$ g_i(\lambda)=-\big(J_{c_i}(\pi_\lambda)-d_i\big)=d_i-J_{c_i}(\pi_\lambda) $$ is a subgradient of $D$ at $\lambda$. Projected subgradient descent on $D$: $$ \lambda_{k+1}=\Big[\lambda_k+\eta\big(J_c(\pi_{\lambda_k})-d\big)\Big]_+ $$ raise the price of a constraint while it is violated, lower it (down to zero) while it is slack.
Multiplier as a controller: integral control and PID Lagrangian (Stooke et al. 2020, Eqs. 18–22, Alg. 2)
Constrained RL as a feedback loop, with $F$ the (unknown, nonlinear) policy update and $h$ the multiplier rule: $$ \theta_{k+1}=F(\theta_k,\lambda_k),\qquad y_k=J_C(\pi_{\theta_k}),\qquad \lambda_k=h(y_0,\dots,y_k,d) $$ The Lagrangian rule $\lambda_{k+1}=(\lambda_k+K_I(J_C-d))_+$ is integral control with gain $K_I$. PID rule: choose $K_P,K_I,K_D\ge0$, $I\leftarrow0$, $J_{C,\rm prev}\leftarrow0$; at each iteration, given the cost estimate $J_C$, $$\Delta\leftarrow J_C-d,\qquad \partial\leftarrow(J_C-J_{C,\rm prev})_+,\qquad I\leftarrow(I+\Delta)_+$$ $$\lambda\leftarrow(K_P\Delta+K_II+K_D\partial)_+,\qquad J_{C,\rm prev}\leftarrow J_C$$ $K_P=K_D=0$ recovers the Lagrangian method.
CVaR, Rockafellar–Uryasev form (as used by Chow et al. 2018, Eq. 1)
For an integrable loss $Z$, $$ \mathrm{CVaR}_\alpha(Z)=\min_{\nu\in\mathbb R}\Big\{\nu+\frac{1}{1-\alpha}\,\mathbb E\big[(Z-\nu)_+\big]\Big\},\qquad \alpha\in(0,1) $$ the minimiser being $\nu^\star=\mathrm{VaR}_\alpha(Z)$. For a continuous distribution $\mathrm{CVaR}_\alpha(Z)=\mathbb E[Z\mid Z\ge\mathrm{VaR}_\alpha(Z)]$: the mean of the worst $(1-\alpha)$ fraction of outcomes; $\alpha\to1$ is the extreme tail, $\alpha\to0$ recovers the mean.
Sauté MDP (Sootla et al., ICML 2022, Def. 3 and Eqs. 7–9)
Task cost $c$, discount $\gamma_c$, safety cost $l\ge0$, safety discount $\gamma_l\in(0,1]$ and budget $d$; augment the state with the rescaled remaining budget $z_t$ and reshape the task cost: $$ z_{t+1}=\frac{z_t-l(s_t,a_t)}{\gamma_l},\quad z_0=d;\qquad \tilde c_n(s,z,a)=\begin{cases}c(s,a)&z\ge0\\ n&z\lt0\end{cases};\qquad \min_\pi\ \mathbb E\sum_t\gamma_c^t\,\tilde c_n(s_t,z_t,a_t) $$ The transitions of $(s,z)$ are Markov, so $\tilde{\mathcal M}_n$ is an ordinary MDP. Theorem 3: an optimal policy of $\tilde{\mathcal M}_\infty$ with finite cost is optimal for the almost-surely constrained problem $\min\mathbb E J_{\rm task}$ s.t. $z_t\ge0$ a.s. for all $t$.
State-augmented CRL: feasible, near-optimal trajectories (Calvo-Fullana et al. 2024, Thm 1; average-reward setting)
Assumptions: (A1) a strictly feasible policy with margin $C\gt0$; (A2) $|r_i(s,a)-c_i|\le B$ for all $s,a,i$ as printed (for $m$ constraints read $B$ as a bound on $\|r(s,a)-c\|_2$, or replace $B^2$ by $mB^2$ below); (A3) the epoch average is an unbiased estimate of $V_i(\pi(\lambda_k))$. Then the state-action sequence satisfies $\liminf_{T}\frac1T\sum_{t\lt T}r_i(s_t,a_t)\ge c_i$ almost surely for every constraint, and $\lim_T\mathbb E\big[\frac1T\sum_{t\lt T}r_0(s_t,a_t)\big]\ge P^\star-\eta_\lambda B^2/2$. The guarantee is about the trajectory generated by switching among Lagrangian maximisers as the multipliers drift, not about any single $\pi(\lambda_k)$.

9. Trust Regions, CPO & Modern Safe Policy Optimization

Algorithms: CPO, PCPO, FOCOPS, CUP, P3O, IPO, CVPO, C-TRPO; model-based: LAMBDA, SafeDreamer, ActSafe, SOOPER; offline: CPQ, COptiDICE, CDT, FISOR.

Returns, advantage and discounted state occupancy (setting of Achiam et al. 2017)
Discounted MDP $(\mathcal S,\mathcal A,P,\mu,r,\gamma)$ with a cost function $c(s,a)\ge0$ and budget $d$; stationary stochastic policies $\pi(a\mid s)$. $$ J(\pi)=\mathbb E_{\tau\sim\pi}\Big[\sum_{t\ge0}\gamma^t r(s_t,a_t)\Big],\qquad J_c(\pi)=\mathbb E_{\tau\sim\pi}\Big[\sum_{t\ge0}\gamma^t c(s_t,a_t)\Big] $$ $V^\pi,Q^\pi$ are the value functions, $Q^\pi(s,a)=r(s,a)+\gamma\,\mathbb E_{s'\sim P(\cdot\mid s,a)}V^\pi(s')$, and $A^\pi=Q^\pi-V^\pi$ is the advantage; $V_c^\pi,Q_c^\pi,A_c^\pi$ are the same objects for $c$. The discounted state occupancy is $$ d^\pi(s)=(1-\gamma)\sum_{t\ge0}\gamma^t\,\mathbb P(s_t=s\mid\pi,\ s_0\sim\mu) $$ and for every bounded $f$: $\ \mathbb E_{\tau\sim\pi}\big[\sum_t\gamma^tf(s_t,a_t)\big]=\frac{1}{1-\gamma}\mathbb E_{s\sim d^\pi,\,a\sim\pi}[f(s,a)]$. Divergences at a state: $D_{\mathrm{TV}}(\pi'\|\pi)[s]=\tfrac12\sum_a|\pi'(a\mid s)-\pi(a\mid s)|$, $D_{\mathrm{KL}}(\pi'\|\pi)[s]=\sum_a\pi'(a\mid s)\log\frac{\pi'(a\mid s)}{\pi(a\mid s)}$, and $\bar D_{\mathrm{KL}}(\pi'\|\pi)=\mathbb E_{s\sim d^{\pi}}\big[D_{\mathrm{KL}}(\pi'\|\pi)[s]\big]$.
Performance difference lemma (Kakade & Langford 2002) and the surrogate objective
Bounded rewards, $\gamma\in(0,1)$, two stationary policies $\pi,\pi'$ started from the same initial distribution $\mu$: $$ J(\pi')-J(\pi)=\frac{1}{1-\gamma}\ \mathbb E_{s\sim d^{\pi'},\ a\sim\pi'(\cdot\mid s)}\big[A^{\pi}(s,a)\big] $$ The same identity holds for the cost: $J_c(\pi')-J_c(\pi)=\frac{1}{1-\gamma}\mathbb E_{d^{\pi'},\pi'}[A_c^\pi]$. When $\pi'(\cdot\mid s)$ is absolutely continuous with respect to $\pi(\cdot\mid s)$ at the sampled states, the surrogate objective admits the importance-sampling identity $$ L_\pi(\pi'):=\frac{1}{1-\gamma}\,\mathbb E_{s\sim d^{\pi},\,a\sim\pi'}\big[A^\pi(s,a)\big]=\frac{1}{1-\gamma}\,\mathbb E_{s\sim d^{\pi},\,a\sim\pi}\Big[\frac{\pi'(a\mid s)}{\pi(a\mid s)}A^\pi(s,a)\Big] $$ and the lemma pins down its error exactly: $$ \begin{aligned}J(\pi')-J(\pi)-L_\pi(\pi')&=\frac{1}{1-\gamma}\sum_s\big(d^{\pi'}(s)-d^{\pi}(s)\big)\,\bar a(s),\\ \bar a(s)&:=\mathbb E_{a\sim\pi'}\big[A^\pi(s,a)\big].\end{aligned} $$ The cost surrogate is $J_c(\pi)+L_{c,\pi}(\pi')$ with $L_{c,\pi}(\pi')=\frac{1}{1-\gamma}\mathbb E_{d^\pi,\pi'}[A_c^\pi]$.
Policy performance bounds (Achiam et al. 2017, Thm. 1 with $f=V^\pi$)
Finite $\mathcal S,\mathcal A$; bounded $r$ and $c$; $\gamma\in(0,1)$; arbitrary stationary policies $\pi,\pi'$. Define $$ \epsilon^{\pi'}:=\max_s\big|\mathbb E_{a\sim\pi'}[A^\pi(s,a)]\big|,\qquad \epsilon_c^{\pi'}:=\max_s\big|\mathbb E_{a\sim\pi'}[A_c^\pi(s,a)]\big| $$ Then $$ \begin{aligned} J(\pi')-J(\pi)&\ \ge\ \frac{1}{1-\gamma}\ \mathbb E_{s\sim d^{\pi},\,a\sim\pi'}\Big[A^\pi(s,a)-\frac{2\gamma\,\epsilon^{\pi'}}{1-\gamma}\,D_{\mathrm{TV}}(\pi'\|\pi)[s]\Big],\\ J_c(\pi')-J_c(\pi)&\ \le\ \frac{1}{1-\gamma}\ \mathbb E_{s\sim d^{\pi},\,a\sim\pi'}\Big[A_c^\pi(s,a)+\frac{2\gamma\,\epsilon_c^{\pi'}}{1-\gamma}\,D_{\mathrm{TV}}(\pi'\|\pi)[s]\Big]. \end{aligned} $$ Both bounds hold with equality at $\pi'=\pi$.
Worst case of one trust-region step (Achiam et al. 2017, Props. 1 and 2)
$\pi_k\in\Pi_\theta$ and $\pi_{k+1}$ an exact solution of the update over $\Pi_\theta$ with exact advantages and exact expectations under $d^{\pi_k}$; $\bar D_{\mathrm{KL}}(\pi_{k+1}\|\pi_k)\le\delta$.
TRPO-type update $\max_\pi\mathbb E_{d^{\pi_k},\pi}[A^{\pi_k}]$ s.t. $\bar D_{\mathrm{KL}}\le\delta$: $$ J(\pi_{k+1})-J(\pi_k)\ \ge\ -\frac{\sqrt{2\delta}\,\gamma\,\epsilon^{\pi_{k+1}}}{(1-\gamma)^2},\qquad \epsilon^{\pi_{k+1}}=\max_s\big|\mathbb E_{a\sim\pi_{k+1}}[A^{\pi_k}(s,a)]\big| $$ CPO update (enforces $J_c(\pi_k)+\frac{1}{1-\gamma}\mathbb E_{d^{\pi_k},\pi_{k+1}}[A_c^{\pi_k}]\le d$): $$ J_c(\pi_{k+1})\ \le\ d+\frac{\sqrt{2\delta}\,\gamma\,\epsilon_c^{\pi_{k+1}}}{(1-\gamma)^2} $$
The CPO update (Achiam et al. 2017, Eq. 10)
$$ \begin{aligned} \pi_{k+1}=\operatorname*{arg\,max}_{\pi\in\Pi_\theta}\quad &\mathbb E_{s\sim d^{\pi_k},\,a\sim\pi}\big[A^{\pi_k}(s,a)\big]\\ \text{s.t.}\quad &J_c(\pi_k)+\frac{1}{1-\gamma}\,\mathbb E_{s\sim d^{\pi_k},\,a\sim\pi}\big[A_c^{\pi_k}(s,a)\big]\le d,\\ &\bar D_{\mathrm{KL}}(\pi\|\pi_k)\le\delta . \end{aligned} $$ With several costs there is one surrogate constraint per $c_i$. Every expectation is over the old policy’s states.
The CPO subproblem and its scalars (Achiam et al. 2017, Eq. 11)
For $\delta\gt0$, with $g=\nabla_\theta L_{\pi_k}$, $b=\nabla_\theta L_{c,\pi_k}$ (both at $\theta_k$), $c=J_c(\pi_k)-d$, $H\succ0$ assumed, and $x=\theta-\theta_k$: $$ \max_{x\in\mathbb R^n}\ g^{\top}x\qquad\text{s.t.}\qquad c+b^{\top}x\le0,\qquad \tfrac12\,x^{\top}Hx\le\delta $$ A linear objective over the intersection of an ellipsoid and a half-space: a convex problem (a QCLP) with an explicit solution. The scalars are inner products in the $H^{-1}$ metric, $$ q=g^{\top}H^{-1}g,\quad r=g^{\top}H^{-1}b,\quad s=b^{\top}H^{-1}b,\qquad qs\ge r^2\ \text{(Cauchy–Schwarz)} $$
Closed-form CPO step, one constraint (Achiam et al. 2017, Eqs. 12–14 and App. 10.2, Thm. 2)
Assumptions: $\delta\gt0$; $H\succ0$; $g\ne0$ and $b\ne0$, so that $q,s\gt0$ (otherwise the formulas divide by zero; $g=0$: every feasible step is optimal; $b=0$: no step changes the linearised cost); a single constraint; the subproblem has a strictly feasible point (Slater), which holds unless $c\gt0$ and $c^2/s\ge2\delta$.
(1) Trust region entirely feasible ($c\lt0$ and $c^2/s\ge2\delta$): the linear constraint can be dropped, $\nu^\star=0$, $\lambda^\star=\sqrt{q/(2\delta)}$ and $x^\star=x_{\rm TRPO}$.
(2) Hyperplane cuts the trust region ($c^2/s\lt2\delta$): with $\Lambda_a=\{\lambda\ge0:\lambda c+r\gt0\}$ and $\Lambda_b=\{\lambda\ge0:\lambda c+r\le0\}$, the dual function minimised over $\nu\ge0$ is $$ D(\lambda)=\begin{cases}D_a(\lambda)=\dfrac{q-r^2/s}{2\lambda}+\dfrac{\lambda}{2}\Big(2\delta-\dfrac{c^2}{s}\Big)-\dfrac{rc}{s}, & \lambda\in\Lambda_a\ \ (\nu^\star\gt0),\\[2mm] D_b(\lambda)=\dfrac{q}{2\lambda}+\lambda\delta, & \lambda\in\Lambda_b\ \ (\nu^\star=0),\end{cases} $$ minimised on each piece at $\lambda_a^\star=\mathrm{Proj}\Big(\sqrt{\tfrac{q-r^2/s}{2\delta-c^2/s}},\bar\Lambda_a\Big)$ and $\lambda_b^\star=\mathrm{Proj}\Big(\sqrt{\tfrac{q}{2\delta}},\bar\Lambda_b\Big)$, projections onto the closed intervals (an empty piece is skipped); $\lambda^\star$ is whichever gives the smaller $D$, and, provided $\lambda^\star\gt0$, $$ \nu^\star=\Big(\frac{\lambda^\star c+r}{s}\Big)_+,\qquad x^\star=\frac{1}{\lambda^\star}H^{-1}\big(g-\nu^\star b\big) $$ By stationarity, $g=\lambda^\star Hx^\star+\nu^\star b$, so $\lambda^\star=0$ happens only in the degenerate case $g=\kappa b$ with $\kappa\gt0$ ($qs=r^2$, $r\gt0$): then $\nu^\star=\kappa$, the formula for $x^\star$ is $0/0$, every point of the chord $\{c+b^{\top}x=0\}$ inside the trust region is optimal, and $x^\star=-cH^{-1}b/s$ is one optimal choice (e.g. $H=1$, $g=b=1$, $c=0$, $\delta=1$: $\lambda^\star=0$, $\nu^\star=1$, $x^\star=0$).
(3) Infeasible ($c\gt0$ and $c^2/s\gt2\delta$: every point of the trust region violates the linearised constraint): take the recovery step $x^\star=-\sqrt{2\delta/s}\,H^{-1}b$. (At the tangency $c\gt0$, $c^2/s=2\delta$, which Slater excludes, the only feasible point is $x=-cH^{-1}b/s$, and it coincides with this recovery step.)
FOCOPS: optimal update policy in closed form (Zhang, Vuong & Ross, NeurIPS 2020, Thm. 1)
$\pi_{\theta_k}$ feasible; optimisation over all stationary policies with the state distribution $d^{\pi_{\theta_k}}$ held fixed. With $\tilde b=(1-\gamma)\big(d-J_c(\pi_{\theta_k})\big)$ and $Z_{\lambda,\nu}(s)$ the normaliser, $$ \begin{aligned}\pi^\star(a\mid s)&=\frac{\pi_{\theta_k}(a\mid s)}{Z_{\lambda,\nu}(s)}\exp\Big(\frac{1}{\lambda}\big(A^{\pi_{\theta_k}}(s,a)-\nu A_c^{\pi_{\theta_k}}(s,a)\big)\Big),\\ (\lambda,\nu)&=\operatorname*{arg\,min}_{\lambda,\nu\ge0}\ \lambda\delta+\nu\tilde b+\lambda\,\mathbb E_{s\sim d^{\pi_{\theta_k}}}\big[\log Z_{\lambda,\nu}(s)\big],\end{aligned} $$ $\pi^\star$ inherits CPO’s worst case, $J_c(\pi^\star)\le d+\sqrt{2\delta}\gamma\epsilon_C^{\pi^\star}/(1-\gamma)^2$.
P3O: exactness of the ReLU penalty (Zhang et al., IJCAI 2022, Thm. 1; strict threshold)
With the importance ratio $\varrho_\theta=\pi_\theta(a\mid s)/\pi_k(a\mid s)$, (P): $\min_\theta L_R(\theta)=\mathbb E[-\varrho_\theta A^{\pi_k}]$ s.t. $L_{C_i}(\theta)=\mathbb E[\varrho_\theta A_{c_i}^{\pi_k}]+(1-\gamma)(J_{c_i}(\pi_k)-d_i)\le0$, and the unconstrained ReLU penalty (Q): $\min_\theta L_R(\theta)+\kappa\sum_i\max\{0,L_{C_i}(\theta)\}$. Let $\bar\theta$ solve (P) with multipliers $\bar\lambda\ge0$ such that $(\bar\theta,\bar\lambda)$ is a saddle point: $\bar\theta$ minimises the Lagrangian $L_R+\sum_i\bar\lambda_iL_{C_i}$ over all $\theta$ and complementary slackness holds. (a) If $\kappa\ge\|\bar\lambda\|_\infty$, then $\bar\theta$ minimises (Q). (b) If $\kappa\gt\|\bar\lambda\|_\infty$, every minimiser of (Q) is feasible and optimal for (P), so (P) and (Q) have the same solution set. P3O states the set equality with $\kappa\ge\|\bar\lambda\|_\infty$; at equality (b) can fail.
ActSafe: calibrated model, pessimistic cost and safe-set expansion (As et al., ICLR 2025, Defs. 4.4, 4.7, Thm. 4.8)
Dynamics $s_{t+1}=f^\ast(s_t,a_t)+w_t$, $z=(s,a)$; episodic with horizon $T$, $J_c(\pi,f)=\mathbb E\sum_{t\lt T}c(s_t,a_t)\le d$. The sets $$ \mathcal Q_n(\delta)=\big\{f:\ |\mu_{n,j}(z)-f_j(z)|\le\beta_n(\delta)\,\sigma_{n,j}(z)\ \ \forall z,\ \forall j\big\} $$ are all-time well calibrated if $f^\ast\in\bigcap_{n\ge0}\mathcal Q_n(\delta)$ with probability at least $1-\delta$ (e.g. GP posterior, $\|f_j^\ast\|_k\le B$). With the plausible set $\mathcal M_n=\mathcal M_{n-1}\cap\mathcal Q_n$, the pessimistic cost of a policy is $P_n(\pi)=\max_{f\in\mathcal M_n}J_c(\pi,f)$: a policy with $P_n(\pi)\le d$ is safe for the true system on the calibration event. ActSafe expands a pessimistic safe set $S_n=S_{n-1}\cup\{\pi\notin S_{n-1}:\exists\pi'\in S_{n-1},\ P_n(\pi')+D(\pi,\pi')\le d\}$, where $D(\pi,\pi')$ bounds how much the cost can change between two policies, starting from a non-empty initial safe set $S_0$ with $J_c(\pi)\le d$. With probability at least $1-\delta$: $J_c(\pi_n,f^\ast)\le d$ for all $n\ge0$.
SOOPER: pessimistic switching to a prior policy (Wendl et al., ICLR 2026, Thms. 1–2)
Assumptions 1–4: dynamics $s_{t+1}=f(s_t,a_t)+\omega_t$ with i.i.d. zero-mean Gaussian noise $\omega_t$ of variance $\sigma^2$; $f$, $r$, $c$ Lipschitz with known constants; $f$ in an RKHS with known component-wise norm bound $B$ and kernel $k\le k_{\max}$; a pessimistic prior $\hat\pi$ (truncated Gaussian, variance $\sigma_a^2\gt0$) that satisfies the constraint for every model in the initial set $\mathcal F_0$ and, under the true dynamics, $V_c^{\hat\pi}(s)\le V_c^{\pi_c^\ast}(s)$ for all $s$; and well-calibrated models $\mathcal F_n$ (Def. 1). With $c_{\lt t}=\sum_{\tau\lt t}\gamma^\tau c(s_\tau,a_\tau)$ the discounted cost already incurred and the pessimistic cost-to-go of the prior $\hat\pi$ ($\bar C=\max\{C_{\max},k_{\max}\}$), the expectation taken along the nominal dynamics $s_{t+1}=\mu_n(s_t,a_t)+\omega_t$, $$ \begin{aligned}Q_{c,n}^{\hat\pi}(s,a)&=\mathbb E^{\hat\pi}\Big[\sum_t\gamma^t\big(c(s_t,a_t)+\lambda_{\rm pess}\|\sigma_n(s_t,a_t)\|\big)\,\Big|\,s_0=s,a_0=a\Big],\\ \lambda_{\rm pess}&=\bar C\,\frac{\gamma}{1-\gamma}\,\frac{(1+\sqrt{d_S})\,\beta_N(\delta)}{\sigma},\end{aligned} $$ execute $a_t\sim\pi_n(\cdot\mid s_t)$ if $\Phi_t:=c_{\lt t}+\gamma^tQ^{\hat\pi}_{c,n}(s_t,a_t)\lt d$ and switch to $\hat\pi$ otherwise (for the rest of the episode). With probability $1-\delta$, $J_c(\bar\pi_n,f)\le d$ in every episode $n=1,\dots,N$ (Thm. 1; its published proof does not handle the random switching time under stochastic transitions, see Module 9). The regret bound is for Algorithm 2, not for the switching rule with an arbitrary $\pi_n$, which can stay safely suboptimal forever: every episode $\pi_n$ is re-planned optimistically in the model, maximising $\mathbb E^\pi\sum_t\gamma^t\big(\tilde r(s_t,a_t)+(\lambda_{\rm explore}+\lambda_{\rm expand})\|\sigma_n(s_t,a_t)\|\big)$ along $s_{t+1}=\mu_n(s_t,a_t)+\omega_t$, where $\tilde r$ ends the episode wherever the prior would take over and pays the prior’s pessimistic return there. Then $\sum_{n=1}^N\big(J_r(\pi_c^\ast,f)-J_r(\bar\pi_n,f)\big)\le O\big(\Gamma_{N\log N}^{7/2}\sqrt N\big)$ (Thm. 2), with $\Gamma$ the maximum information gain; its proof also uses a comparator density bound $\pi_c^\ast(a\mid s)\le p_{\max}$ and a strictly positive uniform safety gap $\delta_c$ (their Eq. 54), which the paper derives from strict feasibility $J_c(\pi_c^\ast,f)\lt d$, although a margin in expected cost does not bound the realised cost on every history.
COptiDICE objective (Lee et al., ICLR 2022, Eqs. 4–12)
Regularise the constrained LP with an $f$-divergence to the data distribution ($f$ strictly convex, $f(1)=0$, $d^{\mathcal D}\gt0$), $D_f(d\|d^{\mathcal D})=\mathbb E_{d^{\mathcal D}}[f(d/d^{\mathcal D})]$: $$ \begin{aligned}\max_{d\ge0}\ \ &\mathbb E_{d}[R]-\alpha\,D_f(d\,\|\,d^{\mathcal D})\\ \text{s.t.}\ \ &\mathbb E_d[C_k]\le\hat c_k,\\ &\sum_{a'}d(s',a')=(1-\gamma)p_0(s')+\gamma\sum_{s,a}d(s,a)T(s'\mid s,a)\ \ \forall s',\end{aligned} $$ With $w=d/d^{\mathcal D}$ and $e_{\lambda,\nu}(s,a)=R(s,a)-\lambda^{\top}C(s,a)+\gamma\,\mathbb E_{s'\sim T(s,a)}[\nu(s')]-\nu(s)$, $$ \begin{aligned}\min_{\lambda\ge0,\ \nu}\ \max_{w\ge0}\ &\mathbb E_{(s,a)\sim d^{\mathcal D}}\big[w(s,a)\,e_{\lambda,\nu}(s,a)-\alpha f(w(s,a))\big]\\ &+(1-\gamma)\,\mathbb E_{s_0\sim p_0}[\nu(s_0)]+\lambda^{\top}\hat c,\end{aligned} $$ $$ w^\ast_{\lambda,\nu}(s,a)=\Big((f')^{-1}\big(\tfrac1\alpha e_{\lambda,\nu}(s,a)\big)\Big)_+ $$ and substituting $w^\ast$ leaves a convex minimisation over $(\lambda,\nu)$ alone. Every term is an expectation over the dataset, so the problem is fully offline; the one catch is the conditional expectation over $s'$ inside $e_{\lambda,\nu}$, which the practical single-sample loss (their Eq. 23) only upper-bounds (Jensen, $f^\ast$ convex) unless transitions are deterministic.
FISOR: feasibility-guided optimal policy (Zheng et al., ICLR 2024, Defs. 1–4, Thm. 1)
Feasible values $V_h^\ast(s)=\min_\pi\max_{t\in\mathbb N}h(s_t)$ with $s_0=s$ (the worst future violation under the best policy) and $Q_h^\ast$ likewise; the largest feasible region is $S_f^\ast=\{s:V_h^\ast(s)\le0\}$. It is approximated offline with the discounted feasible Bellman operator $(\mathcal P^\ast Q)(s,a)=(1-\gamma)h(s)+\gamma\max\{h(s),\min_{a'}Q(s',a')\}$, $s'$ the successor of $(s,a)$ (the paper writes the inner minimum as $V_h^\ast(s')$, meaning $\min_{a'}Q(s',a')$ of the current iterate), a contraction whose fixed point $Q^\ast_{h,\gamma}$ tends to the undiscounted $Q_h^\ast$ only as $\gamma\to1$. For $\gamma\lt1$ its zero sublevel set is an approximation that can contain states from which violation is certain: $h=-1$ followed by an absorbing state with $h=1$ has discounted value $2\gamma-1\le0$ for $\gamma\le\tfrac12$. Thm. 1: the optimal solution is weighted behaviour cloning, $\pi^\ast(a\mid s)\propto\pi_\beta(a\mid s)\,w(s,a)$, with $$ w(s,a)=\begin{cases}\exp\big(\alpha_1A_r^\ast(s,a)\big)\,\mathbf 1\big[Q_h^\ast(s,a)\le0\big], & V_h^\ast(s)\le0,\\ \exp\big(-\alpha_2A_h^\ast(s,a)\big), & V_h^\ast(s)\gt0,\end{cases} $$ where $\alpha_1,\alpha_2$ are temperatures of the behaviour regularisation.
Safety Gym normalised metrics (Ray, Achiam & Amodei 2019)
Normalised by an unconstrained PPO reference $E$: $$\bar J_r=J_r/J_r^E,\qquad \bar M_c=\max(0,J_c-d)/\max(\epsilon,J_c^E-d),\qquad \bar\rho_c=\rho_c/\rho_c^E$$ where $\rho_c$ is the average cost per environment step over all of training ($d=25$, $T_{\rm ep}=1000$, so $\rho_c=0.025$ means approximate satisfaction throughout training).

10. Barrier Functions, Reachability & Safety Filters

Algorithms: CBF-QP safety filter (sampled-data implementation); nominal predictive safety filter (Wabersich & Zeilinger 2021, Alg. 1); shield synthesis (Alshiekh et al. 2018); Hamilton–Jacobi reachability; UPSi (Frauenknecht et al. 2026).

Safe set and forward invariance (Ames et al. 2019, Def. 1)
Let $h:D\to\mathbb R$ be continuously differentiable on an open set $D\subseteq\mathbb R^n$ and $$ C=\{x\in D: h(x)\ge 0\},\qquad \partial C=\{x\in D: h(x)=0\},\qquad \operatorname{Int}(C)=\{x\in D: h(x)>0\} $$ $C$ is forward invariant if for every $x_0\in C$ the solution satisfies $x(t)\in C$ for all $t\in I(x_0)$. The system is safe with respect to $C$ if $C$ is forward invariant.
Nagumo’s theorem, superlevel-set form (Wabersich et al. 2023, Thm. 1; Ames et al. 2019)
Let $f$ be locally Lipschitz, $\operatorname{Int}(C)\neq\emptyset$ and $\nabla h(x)\neq 0$ for all $x\in\partial C$. Then $C$ is forward invariant if and only if $$ \dot h(x)=\nabla h(x)^\top f(x)\ \ge\ 0\qquad\text{for all }x\in\partial C $$ Only the boundary matters, and there the vector field must point inward or be tangent. Invariance is asserted throughout the maximal interval of existence; a guarantee for every $t\ge0$ additionally requires forward completeness.
Barrier certificate (Prajna & Jadbabaie 2004)
For $\dot x=f(x,d)$ with disturbance $d\in\mathcal D$, initial set $X_0$ and unsafe set $X_u$, a differentiable $B:X\to\mathbb R$ is a barrier certificate if $$ B(x)\le 0\ \ \forall x\in X_0,\qquad B(x)>0\ \ \forall x\in X_u,\qquad \frac{\partial B}{\partial x}(x)\,f(x,d)\le 0\ \ \forall (x,d)\in X\times\mathcal D $$ Then no trajectory starting in $X_0$ ever reaches $X_u$: $B(x(t))$ is non-increasing along every trajectory, starts at a value $\le 0$, and $X_u$ requires $B>0$.
Extended class-K function and zeroing barrier function (Ames et al. 2017, Defs. 2–3)
A continuous $\alpha:(-b,a)\to\mathbb R$ ($a,b>0$, possibly $\infty$) is an extended class-$\mathcal K$ function if it is strictly increasing with $\alpha(0)=0$. A continuously differentiable $h$ is a zeroing barrier function (ZBF) for $C$ if there exist an extended class-$\mathcal K$ $\alpha$ and a set $D\supseteq C$ such that $$ L_fh(x)\ \ge\ -\alpha(h(x))\qquad\text{for all }x\in D $$ Prop. 1: a ZBF renders $C$ forward invariant if $\nabla h\neq0$ on $\partial C$ or $D$ is an open neighbourhood of $C$ (the hypothesis added in Ames et al. 2019, Thm. 2 and Rem. 5). With $D=C$ and neither it fails: $\dot x=1$, $h(x)=(1-x^2)^3$ and $\alpha(r)=6\,\mathrm{sgn}(r)|r|^{2/3}$ give $L_fh+\alpha(h)=6(1-x^2)^2(1-x)\ge0$ on $C=[-1,1]$, yet $x(0)=0$ leaves $C$ at $t=1$. Prop. 3: if $C$ is compact and forward invariant, then $h|_C$ is a ZBF (with $D=C$); so for compact $C$ with $\nabla h\neq0$ on $\partial C$, forward invariance and the existence of a ZBF are equivalent.
Control barrier function (Ames et al. 2019, Def. 2; zeroing CBF of Ames et al. 2017, Def. 5)
Let $C\subset D$ be the superlevel set of a continuously differentiable $h:D\to\mathbb R$. Then $h$ is a control barrier function on $D$ if there exists an extended class-$\mathcal K_\infty$ function $\alpha$ such that $$ \sup_{u\in U}\big[L_fh(x)+L_gh(x)\,u\big]\ \ge\ -\alpha(h(x))\qquad\text{for all }x\in D $$ The supremum condition ensures an available safe input when the supremum is attained, for example for nonempty compact $U$ with continuous dependence on $u$. The set of safe inputs at $x$ is $$ K_{\mathrm{cbf}}(x)=\{u\in U:\ L_fh(x)+L_gh(x)u+\alpha(h(x))\ge 0\} $$
Safety via CBFs (Ames et al. 2019, Thm. 2; Ames et al. 2017, Cor. 2 and Prop. 2)
Let $h$ be a CBF on $D$ with $\nabla h(x)\neq 0$ for all $x\in\partial C$. Then any Lipschitz continuous controller $u(x)\in K_{\mathrm{cbf}}(x)$ renders $C$ forward invariant (safe). Moreover, if $C$ is compact, $C$ is asymptotically stable: trajectories that start in $D$ close enough to $C$ converge to it.
CBF-QP safety filter (Ames et al. 2019)
$$ u^*(x)=\operatorname*{arg\,min}_{u\in\mathbb R^m}\ \tfrac12\|u-k(x)\|^2\qquad\text{s.t.}\qquad L_fh(x)+L_gh(x)\,u\ \ge\ -\alpha(h(x)) $$ With input bounds $u\in U$ (a polytope) it remains a QP but loses its closed form.
Closed form of the single-constraint CBF-QP
Write $a(x):=L_fh(x)+\alpha(h(x))$ and $b(x):=L_gh(x)^\top\in\mathbb R^m$ with $b(x)\neq 0$. Then $$ u^*(x)=k(x)+\max\Big\{0,\ -\frac{a(x)+b(x)^\top k(x)}{b(x)^\top b(x)}\Big\}\,b(x) $$ The scalar $\psi(x):=a(x)+b(x)^\top k(x)=\dot h(x,k(x))+\alpha(h(x))$ is the nominal controller’s safety margin: the filter is inactive when $\psi\ge 0$ and otherwise adds exactly the correction $-\psi/\|b\|^2\cdot b$ along $b=g(x)^\top\nabla h(x)$.
High-order CBF (Xiao & Belta, TAC 2022, Defs. 7–8)
For an $m$ times differentiable constraint $b(x,t)\ge 0$ of relative degree $m$ define, with class-$\mathcal K$ functions $\alpha_1,\dots,\alpha_m$ such that $\alpha_i$ is $(m-i)$ times differentiable for $i\lt m$ (the TAC text asks only for “differentiable” $\alpha_i$, but $\psi_i$ is differentiated $m-i$ more times on the way to $\psi_m$, e.g. $\psi_3$ contains $\alpha_1''(b)\,\dot b^2$), $$ \psi_0:=b,\qquad \psi_i:=\dot\psi_{i-1}+\alpha_i(\psi_{i-1})\ \ (i=1,\dots,m),\qquad C_i:=\{x:\psi_{i-1}(x,t)\ge 0\} $$ $b$ is an HOCBF of relative degree $m$ if $$ \sup_{u\in U}\Big[L_f^mb+L_gL_f^{m-1}b\,u+\frac{\partial^mb}{\partial t^m}+O(b)+\alpha_m(\psi_{m-1})\Big]\ \ge\ 0\qquad\forall (x,t)\in (C_1\cap\dots\cap C_m)\times[t_0,\infty) $$ where $O(b)$ collects the remaining Lie derivatives and time partials of order $\le m-1$. Thm. 4: if $x(t_0)\in C_1(t_0)\cap\dots\cap C_m(t_0)$, every Lipschitz continuous $u(t)\in K_{\mathrm{hocbf}}$ renders $C_1\cap\dots\cap C_m$ forward invariant.
ISSf barrier functions and ISSf-CBFs (Kolathaya & Ames 2019, Defs. 3–5, Thms. 1–2)
For a class-$\mathcal K$ function $\gamma$ define the inflated set $$ C_d:=\{x\in\mathbb R^n:\ h(x)+\gamma(\|d\|_\infty)\ge 0\} $$ $h$ is an ISSf barrier function if there are an extended class-$\mathcal K$ $\alpha$ and a class-$\mathcal K$ $\iota$ with $$ L_{\bar f}h(x)+L_gh(x)\,\mu\ \ge\ -\alpha(h(x))-\iota(|\mu|)\qquad\forall x\in D,\ |\mu|\le\bar d $$ and an ISSf control barrier function if $$ \sup_{u\in U}\big[L_fh(x)+L_gh(x)(u+\mu)\big]\ \ge\ -\alpha(h(x))-\iota(|\mu|)\qquad\forall x\in D,\ |\mu|\le\bar d $$ Thm. 1: if $h$ is an ISSf-BF on $D$, then $C$ is ISSf with $\gamma=\beta^{-1}\circ\iota$, where $\beta(r):=-\alpha(-r)$, for every $\bar d$ such that $\beta^{-1}\circ\iota(\bar d)\lt b$ (their condition (24)), where $b>0$ fixes the domain $D=\{x: h(x)+b>0\}$. For the linear choice $\alpha(h)=\lambda h$ the invariant set is (eq. 25) $$ C_d=\Big\{x:\ h(x)+\tfrac{1}{\lambda}\,\iota(\|d\|_\infty)\ge 0\Big\} $$ Thm. 2: if for all $x\in D$ $$ \sup_{u\in U}\big[L_fh(x)+L_gh(x)u-L_gh(x)L_gh(x)^\top\big]\ \ge\ -\alpha(h(x)) $$ then $h$ is an ISSf-CBF, with $\iota(r)=r^2/4$. If $k$ is safeguarding ($L_fh+L_ghk\ge-\alpha(h)$), the controller $u(x)=k(x)+L_gh(x)^\top$ (eq. 27) satisfies the inequality whenever it lies in $U$ (always for $U=\mathbb R^m$).
HJ reachability: safety value function and discriminating kernel (Fisac et al. 2019, eqs. 5–6)
Let the constraint set be $K=\{x: l(x)\ge 0\}$ with $l$ Lipschitz (a signed distance to the failure set works). For a trajectory $\xi$ from $x$ under signals $u(\cdot),d(\cdot)$ define the lowest margin ever attained and the game value $$ V(x,u(\cdot),d(\cdot)):=\inf_{t\ge 0}l(\xi(t)),\qquad V(x):=\inf_{\beta\in\mathcal B}\ \sup_{u(\cdot)}\ V\big(x,u(\cdot),\beta[u](\cdot)\big) $$ Then $\Omega:=\{x: V(x)\ge 0\}$ is the discriminating kernel of $K$: the set of states from which the controller can keep the state in $K$ forever against every disturbance strategy, i.e. the maximal robust controlled invariant subset of $K$.
HJI variational inequality and optimal safe policy (Fisac et al. 2019, eq. 7, Def. 4)
On a horizon $[0,T]$ the value $V(x,t)$ is the viscosity solution of $$ \min\Big\{\,l(x)-V(x,t),\ \ \frac{\partial V}{\partial t}(x,t)+\max_{u\in U}\min_{d\in\hat{\mathcal D}(x)}\frac{\partial V}{\partial x}(x,t)\,f(x,u,d)\Big\}=0,\qquad V(x,T)=l(x) $$ The optimal safe policy is $$ \kappa^*(x)=\operatorname*{arg\,max}_{u\in U}\ \min_{d\in\hat{\mathcal D}(x)}\ \frac{\partial V}{\partial x}(x)\,f(x,u,d) $$
Discounted safety Bellman equation (Fisac et al., ICRA 2019)
$$ V(x)=(1-\gamma)\,l(x)+\gamma\,\min\Big\{l(x),\ \max_{u\in U}V\big(f(x,u)\big)\Big\},\qquad\gamma\in[0,1) $$ with the Q-learning target $Q(x,u)\leftarrow(1-\gamma)l(x)+\gamma\min\{l(x),\max_{u'}Q(x^+,u')\}$. The right-hand side defines a $\gamma$-contraction in the sup norm; as $\gamma\to 1$ the undiscounted value is recovered and the safe set is $\{V\ge 0\}$.
Nominal predictive safety filter (Wabersich & Zeilinger 2021, problem (5), Assumption 4.2)
$$ \begin{aligned} \min_{\{u_{i|k}\}}\ &\|u_L(k)-u_{0|k}\| \\ \text{s.t.}\ \ &x_{i+1|k}=f(x_{i|k},u_{i|k};\bar\theta),\quad x_{i|k}\in X,\quad u_{i|k}\in U,\quad (x_{i|k},u_{i|k})\in Z_c\qquad i=0,\dots,N-1,\\ &x_{N|k}\in S^t,\qquad x_{0|k}=x(k). \end{aligned} $$ $Z_c$ is the region where the model is trusted. Terminal safe set: there is a set $S^t=\{x: a_S(x)\le\mathbf 1\}\subseteq X$ with Lipschitz $a_S$ and a terminal safety filter $\pi_S^t$ such that if $x(\bar k)\in S^t$, applying $u(k)=\pi_S^t(k,x(k),u_L(k))$ gives $x(k)\in X$ and $u(k)\in U$ for all $k>\bar k$.

11. Lyapunov Certificates, Safe Model-Based RL & Learning-Based MPC

Algorithms: safe Lyapunov learning (Berkenkamp et al. 2017); safe policy iteration, SPI (Chow et al. 2018); learning-based MPC, LBMPC (Aswani et al. 2013); SafeMPC (Koller et al. 2018); approximate MPC with a safety-augmented NN (Hose et al. 2025).

Sublevel sets with strict decrease are inner estimates of the ROA (Berkenkamp et al. 2017, Thm. 1)
Closed loop $F_\pi(x):=f(x,\pi(x))$, $F_\pi(0)=0$; sublevel set $\mathcal V(c):=\{x\in X:V(x)\le c\}$, $\Delta V(x):=V(F_\pi(x))-V(x)$, region of attraction $\mathcal R_\pi:=\{x_0\in X:\lim_{t\to\infty}x_t=0\}$. Assumptions: (A1) $F_\pi$ is continuous with $F_\pi(0)=0$. (A2) $V$ is continuous and positive definite. (A3) $\mathcal V(c)$ is compact for some $c\gt0$. (A4) $\Delta V(x)\lt0$ for all $x\in\mathcal V(c)\setminus\{0\}$. Then $\mathcal V(c)$ is forward invariant, every trajectory starting in it converges to the origin, so $\mathcal V(c)\subseteq\mathcal R_\pi$, and the origin is asymptotically stable.
Setting and well-calibrated model (Berkenkamp et al. 2017, Assumptions 1–2)
Deterministic dynamics $x_{t+1}=f(x_t,u_t)=h(x_t,u_t)+g(x_t,u_t)$: known prior model $h$, unknown error $g$. Assumption 1: $h$, $g$ are $L_h$-, $L_g$-Lipschitz in the 1-norm, so $f$ is $L_f$-Lipschitz with $L_f\le L_h+L_g$; policies lie in a class $\Pi_L$ of $L_\pi$-Lipschitz functions. Assumption 2: with posterior mean $\mu_n$, covariance $\Sigma_n$ and $\sigma_n:=\operatorname{trace}\big(\Sigma_n^{1/2}\big)$ (for independent outputs the sum of the marginal standard deviations, their Remark 1), there is $\beta_n\gt0$ such that with probability at least $1-\delta$, for all $n\ge0$, $x\in X$, $u\in U$: $$\|f(x,u)-\mu_n(x,u)\|_1\le\beta_n\sigma_n(x,u)$$
Discretised ROA certificate (Berkenkamp et al. 2017, Thm. 2)
Assumptions 1 and 2; $V$ is $L_V$-Lipschitz; $X_\tau$ a grid with $\|x-[x]_\tau\|_1\le\tau$ for all $x\in X$; $L_{\Delta V}:=L_VL_f(L_\pi+1)+L_V$; $u_n$ the upper confidence bound on $V(f(x,\pi(x)))$ (contained intervals $C_n:=C_{n-1}\cap Q_n$, $u_n:=\max C_n$). If for some $n\ge0$ and $c\gt0$ $$ u_n\big(x,\pi(x)\big)\lt V(x)-L_{\Delta V}\,\tau\qquad\text{for all }x\in\mathcal V(c)\cap X_\tau $$ then with probability at least $1-\delta$, $V(f(x,\pi(x)))\lt V(x)$ for all $x\in\mathcal V(c)\setminus\{0\}$, and $\mathcal V(c)$ is a region of attraction of the true system under $\pi$. (As printed in the paper: the proof needs the grid test on $\mathcal V(c+L_V\tau)\cap X_\tau$, see the caveat in Module 11.)
Safe exploration guarantee (Berkenkamp et al. 2017, Thm. 4)
Assumptions of Thm. 2; $\sigma$-sub-Gaussian noise; $\|g\|_k\le B_g$; $\beta_n=B_g+4\sigma\sqrt{\gamma_n+1+\ln(1/\delta)}$; data collected by the algorithm’s acquisition rule (6) within the Lipschitz-based sets (4)–(5) of Module 11; $X\subseteq\mathbb R^q$. Let $n^\ast$ be the smallest integer with $$ \frac{n^\ast}{\beta_{n^\ast}^2\gamma_{n^\ast}}\ge\frac{C\,q\,L_V^2\,\big(|\mathcal R_0(S_0)|+1\big)}{\epsilon^2},\qquad C=\frac{8}{\log(1+\sigma^{-2})} $$ where $\mathcal R_\epsilon(S_0)$ is what an oracle knowing $V(f(\cdot))$ to accuracy $\epsilon$ could certify from $S_0$, and $\mathcal R_0(S_0)$ what a perfect oracle could certify. (The printed theorem has $L_V^2$ in the denominator and an unsubscripted $\mathcal R(S_0)$; the appendix, with widths $u_n-l_n\le L_V\sqrt{Cq\beta_n^2\gamma_n/(n-n_0)}$ (Cor. 2) and a count over the elements of $\mathcal R_0(S_0)$ (Lemma 10), gives the displayed form: Module 11’s reading.) For any $\epsilon\gt0$, $\delta\in(0,1)$, jointly with probability at least $1-\delta$ for all $n\gt0$: (i) $\mathcal V(c_n)\subseteq\mathcal R_{\pi_n}$; (ii) $f(x,u)\in\mathcal R_{\pi_n}$ for all $(x,u)\in S_n$; (iii) $\mathcal R_\epsilon(S_0)\subseteq S_{n^\ast}\subseteq\mathcal R_0(S_0)$.
Lyapunov functions and induced policies for a feasible baseline (Chow et al. 2018, eq. 1)
$T_{\pi,h}[W](s):=\sum_a\pi(a|s)\big[h(s,a)+\sum_{s'\in S'}P(s'|s,a)W(s')\big]$ for $s\in S'$; the constraint value $V_c^\pi(s)=\mathbb E\big[\sum_{t=0}^{T^\ast-1}c(s_t)\,\big|\,s_0=s,\pi\big]$ is the unique fixed point of $T_{\pi,c}$. For a feasible baseline $\pi_B$ ($V_c^{\pi_B}(s_0)\le d$) the Lyapunov functions are $$ \mathcal L_{\pi_B}(s_0,d):=\Big\{L\ge0:\ T_{\pi_B,c}[L]\le L\text{ on }S',\ \ L=0\text{ at termination},\ \ L(s_0)\le d\Big\} $$ and the $L$-induced policies at $s$ are $\mathcal F_L(s):=\{\pi(\cdot|s)\in\Delta:\ T_{\pi,c}[L](s)\le L(s)\}$. The set is non-empty: $V_c^{\pi_B}$ belongs to it.
Lyapunov risk and falsification constraint (Chang, Roohi & Gao 2019, Defs. 4–6)
For a sampling distribution $\rho$ on the domain $D$ and closed-loop vector field $f_u$, $$ L_\rho(\theta,u)=\mathbb E_{x\sim\rho(D)}\Big[\max\big(0,-V_\theta(x)\big)+\max\big(0,L_{f_u}V_\theta(x)\big)+V_\theta^2(0)\Big] $$ true Lyapunov functions have zero risk (not conversely). The falsifier searches for a solution of $$ \Phi_\varepsilon(x):=\Big(\textstyle\sum_ix_i^2\ge\varepsilon\Big)\wedge\Big(V(x)\le0\ \vee\ L_{f_u}V(x)\ge0\Big),\qquad x\in D $$ with dReal, a $\delta$-complete solver: it proves $\Phi_\varepsilon$ unsatisfiable, which certifies the Lyapunov conditions on $D$ outside the ball $\sum_ix_i^2\lt\varepsilon$ (radius $\sqrt\varepsilon$; the paper’s “$\varepsilon$-ball”), or returns a point satisfying a $\delta$-weakening.
Verifiable ROA condition (Yang et al., ICML 2024, Thm. 3.3)
$B$ a compact box containing $\xi^\ast$, $V$ positive definite with $V(\xi^\ast)=0$, $\kappa\gt0$, $F(\xi):=V(f_{cl}(\xi))-(1-\kappa)V(\xi)$; certify $S:=\{\xi\in B:V(\xi)\lt\rho\}$. If $$\big(-F(\xi)\ge0\ \wedge\ f_{cl}(\xi)\in B\big)\ \vee\ \big(V(\xi)\ge\rho\big)$$ for all $\xi\in B$, then $S$ is forward invariant, $V(\xi_{t+1})\le(1-\kappa)V(\xi_t)$ on $S$, and $S$ is an inner estimate of the region of attraction.
Set algebra and robust positive invariance
Minkowski sum $A\oplus B=\{a+b:a\in A,b\in B\}$; Pontryagin difference $A\ominus B=\{x:\ x+b\in A\ \forall b\in B\}$; $TA=\{Ta:a\in A\}$. Rules: $(A\ominus B)\oplus B\subseteq A$ and $(A\ominus(B\oplus C))\oplus C\subseteq A\ominus B$. For $e^+=A_Ke+w$, $w\in W$, a set $Z$ is robust positively invariant (RPI) if $A_KZ\oplus W\subseteq Z$; when $A_K$ is Schur stable and $W$ is compact with $0\in W$, the minimal closed RPI set is $\mathrm{cl}\bigcup_{k\ge0}\bigoplus_{i=0}^{k}A_K^iW$.
Tube constraint satisfaction (Mayne et al. 2005)
$x^+=Ax+Bu+w$, $w\in W$ compact; nominal $z^+=Az+Bv$; $u=v+K(x-z)$ with $A_K=A+BK$ Schur stable; $Z$ RPI for $e^+=A_Ke+w$. If $x_0-z_0\in Z$, then $x_t-z_t\in Z$ for all $t$; if also $z_t\in X\ominus Z$ and $v_t\in U\ominus KZ$, then $x_t\in X$, $u_t\in U$ for every disturbance sequence.
Robust feasibility and constraint satisfaction of LBMPC (Aswani et al. 2013, Thm. 1 and Cor. 1)
Assumptions: $g(x,u)\in W$ on $X\times U$; $A+BK$ Schur stable; $\Omega$ constraint-admissible and disturbance-invariant; LBMPC feasible at $x_n$ with $M_n=\{c_n,\dots,c_{n+N-1},\theta_n\}$. Applying $u_n=Kx_n+c_n$ gives (a) a feasible $M_{n+1}$ at $x_{n+1}$ and (b) $x_{n+1}\in X$. Hence feasibility at $n=0$ implies constraint satisfaction, feasibility and boundedness for all $n$, whatever the oracle does.
SafeMPC is δ-safe (Koller et al. 2018, Assumption 2, Def. 1, Thm. 2)
Assumptions: $\|g\|_k\le B_g$, sub-Gaussian noise, $\beta_n$ from their Lemma 1; a polytopic $X_{\mathrm{safe}}\subseteq X$ that is robust control positively invariant under a known backup $\pi_{\mathrm{safe}}$ with $\pi_{\mathrm{safe}}(x)\in U$ there; $x_0\in X_{\mathrm{safe}}$. Scheme: minimise $J_t$ s.t. $R_{t+1}=\tilde m(R_t,\pi_t)$, $R_t\subset X$, $\pi_t(R_t)\subset U$ ($t\lt T$) and $R_T\subset X_{\mathrm{safe}}$; apply the first feedback; if infeasible, shift the previous sequence and append $\pi_{\mathrm{safe}}$. Then $$\Pr\big[\forall t:\ x_{t+1}\in X,\ \pi(x_t)\in U\big]\ge1-\delta$$
An MPC on a wrong model can be optimal (Gros & Zanon 2020, Thm. 1)
True MDP with stage cost $L$ (minimised, discount $\gamma$) and optimal $V^\star,Q^\star,\pi^\star$; a possibly wrong model $P[\hat s^+\mid s,a]$. Modified stage cost and $N$-step model cost: $$\hat L(s,a)=Q^\star(s,a)-\gamma\,\mathbb E[V^\star(\hat s^+)\mid s,a]$$ $$\hat V_N(s)=\min_\pi\mathbb E\big[\gamma^NV^\star(\hat s_N)+\sum_{k\lt N}\gamma^k\hat L(\hat s_k,\pi(\hat s_k))\big]$$ On the set $S$ of states whose model trajectories under $\pi^\star$ keep $\mathbb E[V^\star(\hat s_k)]$ finite for all $k$: $\hat V_N=V^\star$, $\hat\pi=\pi^\star$, and $\hat Q_N=Q^\star$ for inputs with finite $\mathbb E[V^\star(\hat s^+)\mid s,a]$.
Robust MPC and its validated approximation (Hertneck et al. 2018, Thms. 5 and 8)
Robust MPC (Thm. 5): from every $x(0)\in X_{\mathrm{feas}}$ the closed loop with inputs $\pi_{\mathrm{MPC}}(x)+d$, $\|d\|_\infty\le\eta$, satisfies $(x(t),u(t))\in X_{\mathrm{feas}}\times U$ for all $t$ and converges to a robust positively invariant set around the origin; so any $\pi_{\mathrm{approx}}$ with $\|\pi_{\mathrm{approx}}-\pi_{\mathrm{MPC}}\|_\infty\le\eta$ on the visited states inherits this. Validation: draw initial conditions i.i.d. from $\Omega$ on $X_{\mathrm{feas}}$, simulate $\pi_{\mathrm{approx}}$ until $X_f$, and set $I(X_i)=1$ if the error bound held along the whole trajectory. From $X_f$ on, the terminal controller $k_f$ of their Assumption 4 takes over, and $\pi_{\mathrm{approx}}$ is never checked inside $X_f$. With $\mu=\mathbb P[I=1]$ and the empirical mean $\tilde\mu$ of $p$ runs, Hoeffding gives $\mathbb P[|\tilde\mu-\mu|\ge\epsilon_h]\le2e^{-2p\epsilon_h^2}=:\delta_h$; the test passes if $$ \mu_{\mathrm{crit}}\ \le\ \tilde\mu-\sqrt{\ln(2/\delta_h)/(2p)} $$ Thm. 8: if validation succeeds, then with confidence at least $1-\delta_h$ the approximate MPC ensures stability and constraint satisfaction for a fraction $\mu_{\mathrm{crit}}$ of the initial conditions distributed according to $\Omega$. This holds for the hybrid controller that switches to $k_f$ on entering $X_f$; keeping $\pi_{\mathrm{approx}}$ inside $X_f$ would need a separate guarantee.
The scenario approach (Calafiore & Campi 2006; Campi & Garatti 2008)
Convex program with $d$ decision variables and uncertain convex constraints $\theta\in\Theta_\delta$, $\delta\sim P$ (here $\delta$ is the uncertain parameter, not a failure probability). Scenario program $\min c^\top\theta$ s.t. $\theta\in\Theta_{\delta^{(i)}}$ for $N$ i.i.d. samples, with unique solution $\theta_N^\ast$; violation probability $V(\theta)=P\{\delta:\theta\notin\Theta_\delta\}$. For any $P$, $$ P^N\big\{V(\theta_N^\ast)\gt\epsilon\big\}\ \le\ \sum_{i=0}^{d-1}\binom Ni\epsilon^i(1-\epsilon)^{N-i} $$ with equality for fully-supported problems, sharpening the earlier $\binom Nd(1-\epsilon)^{N-d}$. A simple sufficient size (after Campi, Garatti & Prandini 2009) is $N\ge\frac2\epsilon(\ln\frac1\beta+d)$, with $\beta$ the scenario-approach confidence.

12. Lipschitz Bounds via SDP: LipSDP and Beyond

Algorithms: LipSDP (Neuron and Layer variants), AutoLip (product bound), Chordal-LipSDP, GLipSDP, ECLipsE; Lipschitz-constrained training with a log-det barrier (Pauli et al.).

Lipschitz constant ($\ell_2$) and its Jacobian characterisation
A map $f:\mathbb R^{n_0}\to\mathbb R^{m}$ is $L$-Lipschitz if $$ \|f(x)-f(y)\|\ \le\ L\,\|x-y\|\qquad\forall\,x,y\in\mathbb R^{n_0} $$ The smallest such $L$ is the Lipschitz constant $L^\star(f)$, and $$ L^\star(f)=\sup_{x}\ \|J_f(x)\| $$ for a locally Lipschitz map on $\mathbb R^{n_0}$, the supremum of the spectral norm of the Jacobian over the points where it exists (Virmaux & Scaman 2018, Thm. 1).
Certified radius from a Lipschitz bound (Tsuzuku, Sato & Sugiyama 2018, Prop. 1)
$f:\mathbb R^{n_0}\to\mathbb R^{K}$ is the logit map of the classifier $C(x)=\operatorname*{arg\,max}_if_i(x)$; $f$ is $L$-Lipschitz in $\ell_2$ with a known upper bound $L$; at the input $x$ the predicted class is $y=C(x)$ with margin $$ m_f(x)=f_y(x)-\max_{j\ne y}f_j(x)\ \gt\ 0 $$ Then $$ C(x+\delta)=y\qquad\text{for all perturbations with}\qquad \|\delta\|\ \lt\ \frac{m_f(x)}{\sqrt2\,L} $$
Product of spectral norms (AutoLip; Virmaux & Scaman 2018, Prop. 1)
$f$ is the $l$-hidden-layer network (pre-activations $v_k=W_{k-1}z_{k-1}+b_{k-1}$, $z_k=\phi(v_k)$, output $f(x)=W_lz_l+b_l$) and $\varphi$ is slope-restricted in $[\alpha,\beta]$ with $\alpha\ge0$, so $|\varphi(a)-\varphi(b)|\le\beta|a-b|$. Then $$ L^\star(f)\ \le\ \beta^{\,l}\,\prod_{k=0}^{l}\|W_k\|\qquad(\beta=1\text{ for ReLU and tanh}) $$ Each affine map stretches increments by at most its largest singular value, each activation layer by at most $\beta$.
Slope restriction (Fazlyab et al. 2019, Def. 1)
$\varphi:\mathbb R\to\mathbb R$ is slope-restricted on $[\alpha,\beta]$, $0\le\alpha\lt\beta\lt\infty$, if every chord has slope in $[\alpha,\beta]$: $$ \alpha\ \le\ \frac{\varphi(a)-\varphi(b)}{a-b}\ \le\ \beta\qquad\forall\,a\ne b $$ Equivalently, the antiderivative $\int\varphi$ is $\alpha$-strongly convex and $\beta$-smooth.
Diagonal multipliers (Fazlyab et al. 2019, Lemma 1)
Let $\varphi$ be slope-restricted on $[\alpha,\beta]$ and $\phi(v)=[\varphi(v_1),\dots,\varphi(v_n)]^{\top}$. For every $T\in\mathcal T_n=\big\{\sum_{i=1}^n\lambda_ie_ie_i^{\top}:\ \lambda_i\ge0\big\}$ (diagonal and positive semidefinite) and all $v,\bar v\in\mathbb R^n$, $$ \begin{bmatrix}v-\bar v\\ \phi(v)-\phi(\bar v)\end{bmatrix}^{\top}\underbrace{\begin{bmatrix}-2\alpha\beta T& (\alpha+\beta)T\\ (\alpha+\beta)T& -2T\end{bmatrix}}_{Q_T}\begin{bmatrix}v-\bar v\\ \phi(v)-\phi(\bar v)\end{bmatrix}\ \ge\ 0 $$
What the quadratic constraint knows, and what it forgets
A pair $(u,w)\in\mathbb R^n\times\mathbb R^n$ satisfies the QC of the lemma for every $T\in\mathcal T_n$ if and only if $$ w=Du\qquad\text{for some }D=\mathrm{diag}(d_1,\dots,d_n),\ d_i\in[\alpha,\beta] $$ Every neuron gets its own chord slope, chosen independently of the other neurons and of where the inputs are; the QC forgets which slope combinations occur together and it forgets the base points.
LipSDP for one hidden layer (Fazlyab et al. 2019, Thm. 1, arXiv v2)
(A1) $f(x)=W_1\phi(W_0x+b_0)+b_1$ with $\phi(v)=[\varphi(v_1),\dots,\varphi(v_n)]^{\top}$ applied elementwise; (A2) $\varphi$ is slope-restricted on $[\alpha,\beta]$; (A3) $T\in\mathcal T_n$, i.e. diagonal with nonnegative entries. With $$M(\rho,T)=\begin{bmatrix}-2\alpha\beta\,W_0^{\top}TW_0-\rho I_{n_0} & (\alpha+\beta)W_0^{\top}T\\ (\alpha+\beta)TW_0 & -2T+W_1^{\top}W_1\end{bmatrix}\ \preceq\ 0$$ if $M(\rho,T)\preceq0$ for some $\rho\gt0$ and $T\in\mathcal T_n$, then $\|f(x)-f(y)\|\le\sqrt\rho\,\|x-y\|$ for all $x,y\in\mathbb R^{n_0}$. The best bound is $$ \rho^\star=\min_{\rho\ge0,\ T\in\mathcal T_n}\ \rho\qquad\text{s.t.}\qquad M(\rho,T)\preceq0 $$ a semidefinite program: $M$ is affine in $(\rho,T)$ and $\mathcal T_n$ is a convex cone. Diagonality of $T$ is essential (the NeurIPS version allowed coupled $T$ and was wrong); the biases appear nowhere in $M$, so the certificate holds for every bias vector at once.
LipSDP for deep networks (Fazlyab et al. 2019, Thm. 2)
For $l$ hidden layers stack $\xi=(\Delta z_0,\Delta z_1,\dots,\Delta z_l)\in\mathbb R^{n_0+n}$ with $\Delta z_0=\Delta x$, and select the pre-activation and activation increments of all hidden layers by $$A=\big[\,\mathrm{blkdiag}(W_0,\dots,W_{l-1})\ \ 0\,\big],\qquad B=\big[\,0\ \ I_n\,\big]$$ With $T=\mathrm{blkdiag}(T_1,\dots,T_l)$ diagonal, $$\begin{aligned}M(\rho,T)&=\begin{bmatrix}A\\ B\end{bmatrix}^{\top}\begin{bmatrix}-2\alpha\beta T & (\alpha+\beta)T\\ (\alpha+\beta)T & -2T\end{bmatrix}\begin{bmatrix}A\\ B\end{bmatrix}\\ &\qquad+\mathrm{blkdiag}\big(-\rho I_{n_0},0,\dots,0,W_l^{\top}W_l\big)\ \preceq\ 0\quad\Longrightarrow\quad L=\sqrt\rho\end{aligned}$$ The matrix is block tridiagonal: each neuron’s constraint couples only its own input and output increments, which live in consecutive layers.
Where LipSDP sits (slopes in $[0,1]$, e.g. ReLU and tanh)
$$ \underbrace{L^\star(f)}_{\text{true}}\ \le\ \underbrace{\max_{D_k\in[0,1]^{n_k}}\big\|W_lD_l\cdots D_1W_0\big\|}_{\text{all-patterns bound}}\ \le\ L_{\rm Neuron}\ \le\ L_{\rm Layer}\ \le\ \prod_{k=0}^{l}\|W_k\| $$ $L_{\rm Neuron}$: LipSDP-Neuron, multiplier $T=\mathrm{diag}(\lambda_1,\dots,\lambda_n)$; $L_{\rm Layer}$: LipSDP-Layer, multiplier $T=\mathrm{blkdiag}(\lambda_1I_{n_1},\dots,\lambda_lI_{n_l})$ (Layer restricts Neuron). LipSDP is never worse than the product bound, and it can never be better than the all-patterns bound.
Coupled multipliers are unsound: a counterexample (Pauli et al., L-CSS 2022, Sec. II-C)
One hidden layer, $n_0=m=1$, $n=2$, $\varphi=\tanh$ (slope-restricted on $[0,1]$), and $$ W_0=\begin{bmatrix}-1\\ -1\end{bmatrix},\quad b_0=\begin{bmatrix}-1\\ 1\end{bmatrix},\quad W_1=\begin{bmatrix}-1 & 1\end{bmatrix},\quad b_1=-0.5 $$ $$ \begin{aligned}f(x)&=-\tanh(-x-1)+\tanh(-x+1)-0.5\\ &=\tanh(x+1)-\tanh(x-1)-0.5\end{aligned} $$ It fits $\cos x$ on $[-\pi/2,\pi/2]$; its true constant is $L^\star=\max_x|\mathrm{sech}^2(x+1)-\mathrm{sech}^2(x-1)|\approx0.9335$. Now take the coupled multiplier $T=(e_1-e_2)(e_1-e_2)^{\top}$: $$ TW_0=\begin{bmatrix}1 & -1\\ -1 & 1\end{bmatrix}\begin{bmatrix}-1\\ -1\end{bmatrix}=0,\qquad W_1^{\top}W_1=\begin{bmatrix}1 & -1\\ -1 & 1\end{bmatrix}=T $$ $$ \Longrightarrow\qquad M(\rho,T)=\begin{bmatrix}-\rho & 0\\ 0 & -2T+T\end{bmatrix}=\mathrm{blkdiag}(-\rho,\,-T)\ \preceq\ 0 $$ for every $\rho\gt0$: the coupled LMI “certifies” $L=\sqrt\rho\to0$. With diagonal multipliers, $T=I$ gives $M(1,I)=-\mathbf 1\mathbf 1^{\top}\preceq0$, so LipSDP-Neuron returns $L=1$ (valid).
1-D convolutional layer as an FIR system (Pauli, Gramlich & Allgöwer, L4DC 2023)
A layer with kernel $K_0,\dots,K_{\ell-1}\in\mathbb R^{c_{\rm out}\times c_{\rm in}}$ and zero padding maps $(u_k)_{k\ge0}$, $u_k\in\mathbb R^{c_{\rm in}}$, to $$ y_k=b+\sum_{j=0}^{\ell-1}K_j\,u_{k-j}\quad(u_{k-j}=0\text{ for }k-j\lt0),\qquad w_k=\phi(y_k) $$ Storing the last $\ell-1$ inputs in the state $x_k=(u_{k-1},\dots,u_{k-\ell+1})\in\mathbb R^{(\ell-1)c_{\rm in}}$ gives $$ x_{k+1}=Ax_k+Bu_k,\qquad y_k=Cx_k+Du_k+b $$ $$ A=\begin{bmatrix}0 & & & \\ I & 0 & & \\ & \ddots & \ddots & \\ & & I & 0\end{bmatrix},\ \ B=\begin{bmatrix}I\\ 0\\ \vdots\\ 0\end{bmatrix},\ \ C=\begin{bmatrix}K_1 & \cdots & K_{\ell-1}\end{bmatrix},\ \ D=K_0 $$ $A$ is nilpotent ($A^{\ell-1}=0$); the state dimension $n_x=(\ell-1)c_{\rm in}$ does not depend on the signal length.
Roesser realisation of a 2-D convolution (Pauli, Gramlich & Allgöwer, IFAC-PapersOnLine 2024, Thms. 1–2)
$y[i_1,i_2]=b+\sum_{t_1=0}^{r_1}\sum_{t_2=0}^{r_2}K[t_1,t_2]\,u[i_1-t_1,i_2-t_2]$ with $K[t_1,t_2]\in\mathbb R^{c_{\rm out}\times c_{\rm in}}$ (a kernel of size $(r_1{+}1)\times(r_2{+}1)$) and zero padding. (Thm. 1) The layer has a Roesser realisation with $A_{21}=0$ and state dimensions $n_1=c_{\rm out}r_1$ and $n_2=c_{\rm in}r_2$; shift blocks $A_{11},A_{22}$ store delayed values and the kernel blocks fill $\begin{bmatrix}A_{12} & B_1\\ C_2 & D\end{bmatrix}$. (Thm. 2) If $c_{\rm in}=c_{\rm out}$ and $K[r_1,r_2]$ has full rank, then $n_1+n_2$ is the minimal state dimension among all realisations. Quote the theorem’s total $c_{\rm out}r_1+c_{\rm in}r_2$; the abstract’s $c_{\rm in}r_1+c_{\rm out}r_2$ agrees only when $c_{\rm in}=c_{\rm out}$ or $r_1=r_2$. For $c_{\rm in}\ne c_{\rm out}$ the realisation may not be minimal.
A quadratic constraint for GroupSort (Pauli et al., ICLR 2024, Lemma 1)
Let $\phi:\mathbb R^n\to\mathbb R^n$ be GroupSort with group size $n_g$ and $N=n/n_g$ groups. For all $\lambda\in\mathbb R^N_{+}$ and all $\gamma,\nu,\tau\in\mathbb R^N$ (no sign constraint), and all $x,y\in\mathbb R^n$, $$ \begin{bmatrix}x-y\\ \phi(x)-\phi(y)\end{bmatrix}^{\top}\begin{bmatrix}T-2S & P+S\\ P+S & -T-2P\end{bmatrix}\begin{bmatrix}x-y\\ \phi(x)-\phi(y)\end{bmatrix}\ \ge\ 0 $$ $$ \begin{aligned}T&=\mathrm{diag}(\lambda)\otimes I_{n_g}+\mathrm{diag}(\gamma)\otimes\mathbf 1\mathbf 1^{\top},\\ P&=\mathrm{diag}(\nu)\otimes\mathbf 1\mathbf 1^{\top},\qquad S=\mathrm{diag}(\tau)\otimes\mathbf 1\mathbf 1^{\top}.\end{aligned} $$ Each group is 1-Lipschitz (multiplier $\lambda_i\ge0$) and preserves the sum of its entries (multipliers $\gamma_i,\nu_i,\tau_i$ of either sign, because an equality can be added with any sign). This $T$ is block diagonal rather than diagonal.

13. Lipschitz-by-Design Networks & Direct Parameterizations

Algorithms: spectral normalization, Parseval, Cayley, SOC, AOL; SLL and sandwich layers (training a $\gamma$-Lipschitz network); Cayley–Gramian 1-D convolutional layers and LipKernel (Pauli et al.); recurrent equilibrium networks (RENs) and R2DN.

Convex, direct, certified and complete parameterizations (Wang & Manchester 2023, Def. 2.3)
A parameterization is a differentiable map $\phi=\mathcal M(\theta)$ from free parameters $\theta\in\Theta\subseteq\mathbb R^N$ to weights and biases $\phi=\{(W_k,b_k)\}$; it is convex if $\Theta$ is convex and direct if $\Theta=\mathbb R^N$. It is certified if $\mathcal M(\Theta)\subseteq\Theta_{\rm cert}(\gamma)$ and complete (for that certificate) if $\mathcal M(\Theta)=\Theta_{\rm cert}(\gamma)$. A certified direct parameterization turns the constrained problem into $\min_{\theta\in\mathbb R^N}\mathcal L(f_{\mathcal M(\theta)})$, solvable by any first-order method without projections, with every iterate satisfying $\operatorname{Lip}\le\gamma$.
Spectral normalization with one power-iteration step (Miyato et al., ICLR 2018)
$$ \bar W_{\rm SN}=\frac{W}{\sigma(W)},\qquad \tilde v\leftarrow\frac{W^{\top}\tilde u}{\|W^{\top}\tilde u\|},\quad \tilde u\leftarrow\frac{W\tilde v}{\|W\tilde v\|},\quad \sigma(W)\approx\tilde u^{\top}W\tilde v $$ with $\tilde u$ kept from one SGD step to the next, so one power iteration per update suffices in practice. With exact spectral norms ($W\ne0$) and 1-Lipschitz activations the network bound is $\prod_l\sigma(\bar W^l_{\rm SN})=1$. The estimate is a lower bound, $\tilde u^{\top}W\tilde v\le\sigma(W)$ for unit vectors, so dividing by it can leave $\sigma(W/\tilde u^{\top}W\tilde v)\gt1$: one-step spectral normalization does not certify a 1-Lipschitz network; a certificate needs a guaranteed upper bound on each $\sigma(W^l)$.
Cayley transform of a skew-symmetric matrix (Trockman & Kolter, ICLR 2021)
Let $A^{\top}=-A\in\mathbb R^{n\times n}$ and $Q=(I-A)(I+A)^{-1}$. Then (i) $I+A$ is invertible; (ii) $Q$ is orthogonal; (iii) $-1$ is not an eigenvalue of $Q$ and $\det Q=+1$; (iv) every orthogonal $Q$ without eigenvalue $-1$ is the Cayley transform of exactly one skew-symmetric matrix, $A=(I+Q)^{-1}(I-Q)$. So the Cayley transform is a bijection between skew-symmetric matrices and orthogonal matrices without eigenvalue $-1$.
AOL rescaling (Prach & Lampert 2022, Thm. 1)
For $P\in\mathbb R^{n\times m}$ without zero columns let $D=\operatorname{diag}(d_i)$, $d_i=\big(\sum_j|P^{\top}P|_{ij}\big)^{-1/2}$. Then $\|PD\|_2\le1$, with $D^{\top}P^{\top}PD=I$ when $P$ has orthogonal columns.
SLL: the unifying algebraic condition (Araujo, Havens, Delattre, Allauzen & Hu, ICLR 2023, Thm. 1)
Let $W\in\mathbb R^{m\times n}$ and let $T$ be a nonsingular diagonal matrix with $W^{\top}W\preceq T$. Then (1) $$g(x)=WT^{-1/2}x+b$$ is 1-Lipschitz, and (2) $$h(x)=x-2WT^{-1}\varphi(W^{\top}x+b)$$ is 1-Lipschitz if $\varphi$ is ReLU, tanh or sigmoid (slope-restricted in $[0,1]$), applied elementwise. $W^{\top}W\preceq T$ forces $T\succ0$ and is linear in $T$: an SDP condition in a diagonal unknown.
SLL: analytic multiplier via Gershgorin (Araujo et al. 2023, Thm. 3)
Let $T$ be nonsingular diagonal. If for some diagonal $Q\succ0$ the matrix $T-QW^{\top}WQ^{-1}$ is diagonally dominant with positive diagonal, then $T\succeq W^{\top}W$, and $h(x)=x-2WT^{-1}\varphi(W^{\top}x+b)$ is 1-Lipschitz for ReLU, tanh or sigmoid. With $Q^{-1}=\operatorname{diag}(q_i)$ the choice $T_{ii}=\sum_j|W^{\top}W|_{ij}\,q_j/q_i$ makes it diagonally dominant with nonnegative diagonal (a diagonal entry is $0$ if column $i$ of $W$ is orthogonal to all others), which is all Gershgorin needs.
LipSDP in block-tridiagonal γ-form (Wang & Manchester 2023, Thm. A.3 and eq. (5))
The network is $\gamma$-Lipschitz if there are positive diagonal $\Lambda_k\in\mathbb D^{n_{k+1}}_{++}$, $k=0,\dots,L-1$, with $$ H=\begin{bmatrix}\gamma I&-W_0^{\top}\Lambda_0&&&\\-\Lambda_0W_0&2\Lambda_0&-W_1^{\top}\Lambda_1&&\\&\ddots&\ddots&\ddots&\\&&-\Lambda_{L-1}W_{L-1}&2\Lambda_{L-1}&-W_L^{\top}\\&&&-W_L&\gamma I\end{bmatrix}\succeq0 $$ For one hidden layer this is Module 12’s $M(\rho,T)\preceq0$ with $\alpha=0$, $\beta=1$, $\rho=\gamma^2$, $T=\gamma\Lambda_0$.
Direct parameterization of all LipSDP-certified networks (Wang & Manchester 2023, Thm. 3.1)
Free parameters: $d_k\in\mathbb R^{n_{k+1}}$ ($0\le k\lt L$), $X_k\in\mathbb R^{n_{k+1}\times n_{k+1}}$, $Y_k\in\mathbb R^{n_k\times n_{k+1}}$, $b_k$ ($0\le k\le L$). Set $\Psi_k=\operatorname{diag}(e^{d_k})$, $[A_k^{\top};B_k^{\top}]=\operatorname{Cayley}(X_k,Y_k)$ and $$ W_k=2\,\Psi_k^{-1}B_kA_{k-1}^{\top}\Psi_{k-1},\qquad k=0,\dots,L $$ with $A_{-1}=I$, $\Psi_{-1}=\sqrt{\gamma/2}\,I$, $\Psi_L=\sqrt{2/\gamma}\,I$. Then the block-tridiagonal LMI holds with $\Lambda_k=\Psi_k^2$ (the paper’s Section 3 prints $\tfrac12\Psi_k^2$; for the LMI as written the certificate is $\Psi_k^2$), hence $\operatorname{Lip}\le\gamma$, for every value of the free parameters; conversely, every network satisfying the LMI can be written this way.
The sandwich layer is 1-Lipschitz (Wang & Manchester 2023, Thm. 3.2 and Prop. 3.3)
For $\Psi=\operatorname{diag}(e^d)$ and $[A^{\top};B^{\top}]=\operatorname{Cayley}(X,Y)$, the layer $$h_{\rm out}=\sqrt2A^{\top}\Psi\varphi(\sqrt2\Psi^{-1}Bh_{\rm in}+b)$$ is 1-Lipschitz for every $\varphi$ slope-restricted in $[0,1]$. With $\varphi$ the identity it is the linear layer $h_{\rm out}=2A^{\top}Bh_{\rm in}+\hat b$, and a linear layer is 1-Lipschitz iff its weight can be written $W=2A^{\top}B$ this way.
Layer-wise LMIs certify the whole 1-D CNN (Pauli et al., CDC 2023, Thm. 2)
Let all activations be slope-restricted in $[0,1]$ and $\rho\gt0$. Suppose every convolutional layer $i$ has $Q_i\in\mathbb S^{c_i}$ (diagonal if the layer contains max pooling), $P_i\succeq0$ and a positive diagonal $\Lambda_i$ with $$ \begin{bmatrix}P_i-A_i^{\top}P_iA_i&-A_i^{\top}P_iB_i&-C_i^{\top}\Lambda_i\\-B_i^{\top}P_iA_i&Q_{i-1}-B_i^{\top}P_iB_i&-D_i^{\top}\Lambda_i\\-\Lambda_iC_i&-\Lambda_iD_i&2\Lambda_i-Q_i\end{bmatrix}\succeq0,\qquad Q_0=\tilde\rho^{\,2}I $$ and every fully connected layer satisfies $\begin{bmatrix}Q_{i-1}&-W_i^{\top}\Lambda_i\\-\Lambda_iW_i&2\Lambda_i-Q_i\end{bmatrix}\succeq0$, the last (no activation) $\begin{bmatrix}Q_{l-1}&-W_l^{\top}\\-W_l&I\end{bmatrix}\succeq0$, with $Q_{i-1}$ replaced by $I_N\otimes Q_{i-1}$ at the flattening step. Then the CNN is $\rho$-Lipschitz with $\rho=\tilde\rho\prod_s\mu_s$, where $\mu_s$ are the Lipschitz constants of the average-pooling layers ($\mu=1/\sqrt\ell$ for non-overlapping windows of length $\ell$). Both papers define max and average pooling with non-overlapping windows (stride equal to window length), and the diagonal $Q_i$ covers only that case: overlapping max pooling is not even 1-Lipschitz, since $(a,b,c)\mapsto(\max(a,b),\max(b,c))$ has gain $\sqrt2$ near $(0,1,0)$.
Gramian parameterization of the storage (Pauli, Wang, Manchester & Allgöwer, CDC 2023, Lemma 7)
With $F_i:=\begin{bmatrix}P_i-A_i^{\top}P_iA_i&-A_i^{\top}P_iB_i\\-B_i^{\top}P_iA_i&Q_{i-1}-B_i^{\top}P_iB_i\end{bmatrix}$ the conv LMI reads $\begin{bmatrix}F_i&-\hat C_i^{\top}\Lambda_i\\-\Lambda_i\hat C_i&2\Lambda_i-Q_i\end{bmatrix}\succeq0$. Let $Q_{i-1}\succ0$. For some $\varepsilon\gt0$ (in fact any) and all $H_i\in\mathbb R^{n_{x_i}\times n_{x_i}}$, $P_i=X_i^{-1}$ with $$ X_i=\sum_{k\ge0}A_i^k\big(B_iQ_{i-1}^{-1}B_i^{\top}+H_i^{\top}H_i+\varepsilon I\big)(A_i^{\top})^k $$ renders $F_i\succ0$. The sum is finite because $A_i$ is nilpotent, and $X_i$ is the unique solution of $X_i-A_iX_iA_i^{\top}-B_iQ_{i-1}^{-1}B_i^{\top}=H_i^{\top}H_i+\varepsilon I\succ0$.
Cayley–Gramian convolutional layers (Pauli et al., CDC 2023, Thm. 8)
For a convolutional layer with average pooling or no pooling set $$ \hat C_i=\sqrt2\,\Gamma_i^{-1}V_i^{\top}L^F_i,\qquad \Gamma_i=\operatorname{diag}(\gamma_i),\quad \begin{bmatrix}U_i\\V_i\end{bmatrix}=\operatorname{Cayley}\begin{bmatrix}Y_i\\Z_i\end{bmatrix},\quad L^F_i=\operatorname{chol}(F_i) $$ with $F_i=L_i^{F\top}L^F_i$ built from $P_i$ of the Lemma, $Q_i=L_i^{\top}L_i$, $L_0=\rho I$, $L_i=\sqrt2\,U_i\Gamma_i$. Assume that every $\Gamma_i$ and $L_i$ is nonsingular, so that $Q_{i-1}\succ0$ (e.g. $\Gamma_i=\operatorname{diag}(e^{\gamma_i})$). Then the conv LMI holds for all free variables $Y_i\in\mathbb R^{c_i\times c_i}$, $Z_i\in\mathbb R^{\ell_ic_{i-1}\times c_i}$, $H_i$, $\gamma_i$, $b_i$, and the kernel is read off $\hat C_i$. With average pooling $\rho$ is first divided by the pooling constants; max pooling needs diagonal $Q_i$ and a modified formula (Corollary 9).
Incrementally dissipative layers compose (LipKernel: Pauli, Wang, Manchester & Allgöwer, Automatica 2026, Def. 4 and Thm. 7)
A layer $u_k\mapsto y_k$ is incrementally dissipative with respect to the supply $\sum_{i}\big(\|\Delta u_k[i]\|^2_{X_{k-1}}-\|\Delta y_k[i]\|^2_{X_k}\big)\ge0$ if this holds for all input pairs and horizons. With $u_{k+1}=y_k$ and matrices $X_0,\dots,X_l\succ0$: if every layer $k=1,\dots,l$ is, then $\|\Delta y_l\|^2_{X_l}\le\|\Delta u_1\|^2_{X_0}$ (the layer inequalities telescope), i.e. the network is $(Q,R)$-Lipschitz with $X_0=R$ and $X_l=Q$; $X_0=\rho^2I$, $X_l=I$ gives $\rho$-Lipschitz (in LipKernel’s convention $\rho$ is the constant itself, not its square).
Contracting RENs (Revay, Wang & Manchester 2024, Thm. 1, part 1)
Let Assumption 1 hold and $\bar\alpha\in(0,1]$. If there are $P=P^{\top}\succ0$ and a positive diagonal $\Lambda$ with $$ \begin{bmatrix}\bar\alpha^2P&-C_1^{\top}\Lambda\\-\Lambda C_1&\mathcal W\end{bmatrix}-\begin{bmatrix}A^{\top}\\B_1^{\top}\end{bmatrix}P\begin{bmatrix}A&B_1\end{bmatrix}\succ0,\qquad \mathcal W=2\Lambda-\Lambda D_{11}-D_{11}^{\top}\Lambda $$ then the REN is well-posed ($\mathcal W\succ0$ is implied) and contracting with some rate $\alpha\lt\bar\alpha$. An analogous LMI (Thm. 1, part 2) additionally certifies a given incremental IQC $(Q,S,R)$ with $Q\preceq0$.

14. Neural Networks in the Loop: QCs, IQCs & Dissipativity

Algorithms: local sector bounds by interval bound propagation (Yin et al.); reference governor on the certified set (Pauli et al.); RL with a dissipativity-enforcing projection (Junnarkar, Arcak & Seiler); Youla-REN synthesis.

LTI plant with a feedforward NN controller (Yin, Seiler & Arcak, TAC 2022, Def. 1 and eq. 1)
$$ \begin{aligned}&x_{t+1}=Ax_t+Bu_t,\qquad u_t=\pi(x_t):\\ &w^0_t=x_t,\qquad v^i_t=W_{i-1}w^{i-1}_t+b_{i-1},\qquad w^i_t=\phi(v^i_t)\quad(i=1,\dots,\ell),\\ &u_t=W_\ell w^\ell_t+b_\ell .\end{aligned} $$ An equilibrium is a tuple $(x_*,u_*,v_*,w_*)$ with $x_*=Ax_*+Bu_*$ and $u_*=\pi(x_*)$, where $v_*,w_*$ are obtained by propagating $x_*$ through the layers. The region of attraction (ROA) is $\{x_0:\ x_t\to x_*\}$; the goal is an ellipsoid $\mathcal E(P,x_*)=\{x:(x-x_*)^\top P(x-x_*)\le1\}$ that is provably contained in the ROA, as large as possible.
Isolating the nonlinearities: LFT / Lur’e form
$$ \begin{bmatrix}u_t\\ v_t\end{bmatrix}=\underbrace{\begin{bmatrix}N_{ux} & N_{uw} & N_{ub}\\ N_{vx} & N_{vw} & N_{vb}\end{bmatrix}}_{N}\begin{bmatrix}x_t\\ w_t\\ 1\end{bmatrix},\qquad w_t=\phi(v_t) $$ with $N_{ux}=0$, $N_{uw}=\begin{bmatrix}0 & \cdots & 0 & W_\ell\end{bmatrix}$, $N_{ub}=b_\ell$ and $$ N_{vx}=\begin{bmatrix}W_0\\ 0\\ \vdots\\ 0\end{bmatrix},\qquad N_{vw}=\begin{bmatrix}0 & & & \\ W_1 & 0 & & \\ & \ddots & \ddots & \\ & & W_{\ell-1} & 0\end{bmatrix},\qquad N_{vb}=\begin{bmatrix}b_0\\ \vdots\\ b_{\ell-1}\end{bmatrix} $$ The closed loop is a linear system in feedback with the diagonal static map $\phi$: $\ x_{t+1}=Ax_t+BN_{uw}w_t+BN_{ub}$, $\ v_t=N_{vx}x_t+N_{vw}w_t+N_{vb}$, $\ w_t=\phi(v_t)$.
Sector and slope restrictions as quadratic constraints (Yin et al. 2022, Defs. 2–4)
Let $\mathcal I\subseteq\mathbb R$ be an interval containing $v_*$, $\Delta v=v-v_*$, $\Delta\varphi=\varphi(v)-\varphi(v_*)$. $\varphi$ satisfies the (offset) sector $[\alpha,\beta]$ around $(v_*,\varphi(v_*))$ on $\mathcal I$ if $(\Delta\varphi-\alpha\,\Delta v)(\beta\,\Delta v-\Delta\varphi)\ge0$ for all $v\in\mathcal I$; it is slope-restricted in $[\mu,\nu]$ on $\mathcal I$ if $\mu\le\frac{\varphi(v)-\varphi(v')}{v-v'}\le\nu$ for all $v\ne v'$ in $\mathcal I$. The sector condition is the quadratic constraint $$ \begin{bmatrix}\Delta v\\ \Delta\varphi\end{bmatrix}^{\top}\begin{bmatrix}-2\alpha\beta & \alpha+\beta\\ \alpha+\beta & -2\end{bmatrix}\begin{bmatrix}\Delta v\\ \Delta\varphi\end{bmatrix}\ge0 $$ and slope restriction is the same inequality for the pair $(v-v',\ \varphi(v)-\varphi(v'))$ with $(\mu,\nu)$ in place of $(\alpha,\beta)$. Slope restriction on $\mathcal I$ implies the sector $[\mu,\nu]$ around every point of the graph over $\mathcal I$; the converse fails. tanh and ReLU are globally slope-restricted, hence sector-bounded, in $[0,1]$.
Stacked offset local sector QC (Yin et al. 2022, Lemma 1)
Let $\alpha,\beta,\underline v,\bar v,v_*\in\mathbb R^{n_\phi}$ with $\alpha\le\beta$ and $\underline v\le v_*\le\bar v$ elementwise, $w_*=\phi(v_*)$, and suppose the $i$-th activation satisfies the offset local sector $[\alpha_i,\beta_i]$ around $(v_{*,i},w_{*,i})$ for $v_i\in[\underline v_i,\bar v_i]$. Then for every $T=\mathrm{diag}(\lambda)$, $\lambda\ge0$, $$ \begin{gathered}\begin{bmatrix}v-v_*\\ w-w_*\end{bmatrix}^{\top}\underbrace{\begin{bmatrix}-2D_\alpha D_\beta T & (D_\alpha+D_\beta)T\\ (D_\alpha+D_\beta)T & -2T\end{bmatrix}}_{Q_{\alpha\beta}(T)}\begin{bmatrix}v-v_*\\ w-w_*\end{bmatrix}\ \ge\ 0\\ \text{for all }v\in[\underline v,\bar v],\ w=\phi(v).\end{gathered} $$
Local stability and an ellipsoidal ROA estimate (Yin, Seiler & Arcak, TAC 2022, Thm. 1)
Assumptions: (i) LTI plant and $\ell$-layer feedforward network as above, with an equilibrium $(x_*,u_*,v_*,w_*)$; (ii) a first-layer box $\bar v^1$, $\underline v^1=2v^1_*-\bar v^1$, and vectors $\alpha,\beta$ such that $\phi$ satisfies the offset local sector $[\alpha,\beta]$ around $(v_*,w_*)$ for all $v$ in the box obtained by interval bound propagation; (iii) with $R_V=\begin{bmatrix}I & 0\\ N_{ux} & N_{uw}\end{bmatrix}$ and $R_\phi=\begin{bmatrix}N_{vx} & N_{vw}\\ 0 & I\end{bmatrix}$ there exist $P\succ0$ and $T=\mathrm{diag}(\lambda)$, $\lambda\ge0$, such that $$ \mathcal M(P,T):=R_V^{\top}\begin{bmatrix}A^{\top}PA-P & A^{\top}PB\\ B^{\top}PA & B^{\top}PB\end{bmatrix}R_V+R_\phi^{\top}Q_{\alpha\beta}(T)R_\phi\ \prec\ 0 $$ $$ \begin{bmatrix}(\bar v^1_i-v^1_{*,i})^2 & (W_0)_i\\ (W_0)_i^{\top} & P\end{bmatrix}\succeq0,\qquad i=1,\dots,n_1 $$ where $(W_0)_i$ is the $i$-th row of the first weight. Then (a) $x_*$ is locally asymptotically stable (the paper says “locally stable”; the proof gives asymptotic stability) and (b) $\mathcal E(P,x_*)$ is an inner approximation of the ROA.
Integral quadratic constraints (Megretski & Rantzer 1997; discrete-time form of Pauli et al., Defs. 4–5)
Signals $v,w\in\ell_2^n$ satisfy the frequency-domain IQC defined by $\Pi:\{|z|=1\}\to\mathbb C^{2n\times2n}$ if $$\int_0^{2\pi}\begin{bmatrix}\hat v(e^{j\omega})\\ \hat w(e^{j\omega})\end{bmatrix}^{*}\Pi(e^{j\omega})\begin{bmatrix}\hat v(e^{j\omega})\\ \hat w(e^{j\omega})\end{bmatrix}d\omega\ge0$$ With a factorisation $\Pi=\Psi^{*}M\Psi$, $\Psi$ stable, let $r=\Psi\begin{bmatrix}v\\ w\end{bmatrix}$ (zero initial filter state). The pair satisfies the soft IQC if $\sum_{t=0}^{\infty}r_t^{\top}Mr_t\ge0$ and the hard IQC if $\sum_{t=0}^{N}r_t^{\top}Mr_t\ge0$ for every $N\ge0$. A static QC is the special case $\Psi=I$ that holds at every $t$.
IQC stability theorem (Megretski & Rantzer, TAC 1997)
Let $G$ be a stable LTI system and $\Delta$ a bounded causal operator. Assume (i) the loop $v=Gw+f$, $w=\Delta(v)+e$ is well posed for $\tau\Delta$, every $\tau\in[0,1]$; (ii) $\tau\Delta$ satisfies the IQC defined by $\Pi$ for every $\tau\in[0,1]$; (iii) there is $\varepsilon\gt0$ with $$ \begin{bmatrix}G(j\omega)\\ I\end{bmatrix}^{*}\Pi(j\omega)\begin{bmatrix}G(j\omega)\\ I\end{bmatrix}\preceq-\varepsilon I\qquad\forall\omega $$ Then the loop is stable.
Acausal Zames–Falb multipliers with FIR factorisation (Pauli et al., Sec. II-D)
For monotone nonlinearities with $\varphi(0)=0$, i.e. slope restriction $[0,\infty]$ (Pauli et al. write “the sector $[0,\infty]$”; a sector bound alone would not do, because the cross terms compare values at different times or of different neurons), take FIR coefficients $M_{-\ell},\dots,M_{\ell}\in\mathbb R^{n\times n}$ and the block matrix $$ \tilde P=\begin{bmatrix}M_0 & M_{-1} & \cdots & M_{-\ell}\\ M_1 & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ M_\ell & 0 & \cdots & 0\end{bmatrix},\qquad \Pi^{ZF}_{[0,\infty]}=\Big\{\begin{bmatrix}0 & \tilde P^{\top}\\ \tilde P & 0\end{bmatrix}\Big\} $$ acting on the window $(v_t,\dots,v_{t-\ell},w_t,\dots,w_{t-\ell})$, i.e. with the FIR filter $$ \Psi^{ZF}(z)=\mathrm{blkdiag}\big([I,z^{-1}I,\dots,z^{-\ell}I]^{\top},\ [I,z^{-1}I,\dots,z^{-\ell}I]^{\top}\big) $$ The coefficients must satisfy the row and column sum conditions $$ \Big(\sum_{j=-\ell}^{\ell}M_j\Big)\mathbf 1\ge0,\qquad \mathbf 1^{\top}\Big(\sum_{j=-\ell}^{\ell}M_j\Big)\ge0 $$ together with sign conditions: all entries except the diagonal of $M_0$ are nonpositive; for odd nonlinearities these are replaced by absolute-value dominance conditions of the diagonal of $M_0$ over all other entries. Slope bounds $[\mu,\nu]$ follow by the loop transformation: $\Pi^{ZF}_{[\mu,\nu]}=T^{\top}\Pi^{ZF}_{[0,\infty]}T$, with $T=\begin{bmatrix}I\otimes\mathrm{diag}(\mu) & -I\\ -I\otimes\mathrm{diag}(\nu) & I\end{bmatrix}$. Per-neuron bounds $\mu,\nu\in\mathbb R^n$ are fine for diagonal $M_j$; an entry of $M_j$ that couples neurons $i$ and $k$ also needs $\mu_i=\mu_k$ and $\nu_i=\nu_k$.
Hard IQC for acausal Zames–Falb multipliers (Pauli et al., CDC 2021, Thm. 1)
Let $\tilde\phi:\mathbb R^n\to\mathbb R^n$ be a diagonally repeated nonlinearity (the same scalar function in every channel) that is slope-restricted in $[\mu,\nu]$ with scalar bounds $\mu,\nu$ common to all channels, and let $\Pi\in\Pi^{ZF}_{[\mu,\nu]}$ with middle matrix $M$. Then all $v,w\in\ell_2^n$ with $w_t=\tilde\phi(v_t)$ (and $v_t=w_t=0$ for $t\lt0$) satisfy $$ \sum_{t=0}^{N}\begin{bmatrix}v_t\\ \vdots\\ v_{t-\ell}\\ w_t\\ \vdots\\ w_{t-\ell}\end{bmatrix}^{\top}M\begin{bmatrix}v_t\\ \vdots\\ v_{t-\ell}\\ w_t\\ \vdots\\ w_{t-\ell}\end{bmatrix}\ge0\qquad\forall N\in\mathbb N_0 $$ a hard IQC with the FIR filter $\Psi^{ZF}$. If $\tilde\phi$ is not diagonally repeated, or its slope bounds $\mu_i,\nu_i$ differ between neurons, the statement holds with diagonal $M_j=\mathrm{diag}(m_j)$; block-diagonal $M_j$ need the repeated function and common bounds only within each block. (The paper writes $T$ with per-neuron $\mu,\nu$; with coupled $M_j$ that fails: $\varphi(s)=s/2$ in two channels, $\mu=(1/4,0)$, $\nu=(1,3/4)$, $M_0=\begin{bmatrix}1&-1\\-1&1\end{bmatrix}$ and $v=(1,1)$ give the value $-1/8$ at a single time step.)
NN controller with integral action (Pauli et al., L4DC 2021, Sec. 2.1)
Plant $x_{t+1}=Ax_t+Bu_t$, $y_t=Cx_t$ with as many inputs as outputs ($n_u=n_r$). Controller $$ \xi_{t+1}=\xi_t+r-y_t,\qquad u_t=k_\xi\,\xi_t+\kappa(x_t,r) $$ where $k_\xi$ is invertible and $\kappa$ is an $\ell$-layer network with input $w^0=H_xx+H_rr$ (state feedback: $H_x=I$, $H_r=0$; output-error feedback: $H_x=-C$, $H_r=I$). The augmented state $\chi=(x,\xi)$ obeys $$ \begin{gathered}\chi_{t+1}=\tilde A\chi_t+\tilde B\,\kappa(x_t,r)+B_rr,\qquad y_t=\tilde C\chi_t,\\ \tilde A=\begin{bmatrix}A & Bk_\xi\\ -C & I\end{bmatrix},\ \tilde B=\begin{bmatrix}B\\ 0\end{bmatrix},\ B_r=\begin{bmatrix}0\\ I\end{bmatrix},\ \tilde C=\begin{bmatrix}C & 0\end{bmatrix}.\end{gathered} $$ Standing assumption: $A_a=\begin{bmatrix}A-I & B\\ C & 0\end{bmatrix}$ is square and nonsingular, so each $r$ has a unique steady state $\begin{bmatrix}x_*\\ u_*\end{bmatrix}=A_a^{-1}\begin{bmatrix}0\\ r\end{bmatrix}$ with $y_*=r$.
Global exponential stability and offset-free tracking (Pauli et al., L4DC 2021, Thm. 1)
Let $R_V$ map $(\tilde\chi,\tilde w)\mapsto(\tilde\chi,\tilde u)$ and $R_\phi$ map $(\tilde\chi,\tilde w)\mapsto(\tilde v,\tilde w)$, built from the weights as in the LFT form (the integrator state does not enter the network). If there exist a diagonal $T\succeq0$ and $P\succ0$ with $$ R_V^{\top}\begin{bmatrix}\tilde A^{\top}P\tilde A-P & \tilde A^{\top}P\tilde B\\ \tilde B^{\top}P\tilde A & \tilde B^{\top}P\tilde B\end{bmatrix}R_V+R_\phi^{\top}\begin{bmatrix}-2\alpha\beta T & (\alpha+\beta)T\\ (\alpha+\beta)T & -2T\end{bmatrix}R_\phi\ \prec\ 0 $$ then for every initial condition and every reference $r$ the steady state $\chi_*(r)$ is globally exponentially stable and $y_t\to r$. Assumptions used: $A_a$ square and nonsingular, $k_\xi$ invertible, $n_u=n_r$, and every activation slope-restricted on all of $\mathbb R$ with bounds $0\le\alpha\lt\beta$.
ℓ2-gain LMI for an RNN, activations in the sector $[0,1]$ (Pauli et al.)
The RNN as a linear system in feedback with its activations: $$ \begin{gathered}x_{t+1}=Ax_t+B_1w_t+B_2u_t,\qquad v_t=C_1x_t+D_{11}w_t+D_{12}u_t,\\ y_t=C_2x_t+D_{21}w_t+D_{22}u_t,\qquad w_t=\phi(v_t).\end{gathered} $$ A vanilla RNN $h_{t+1}=\phi(W_hh_t+W_uu_t)$, $y_t=C_hh_t$ has $x=h$, $A=0$, $B_1=I$, $B_2=0$, $C_1=W_h$, $D_{12}=W_u$, $C_2=C_h$ and $D_{11}=0$. With $\zeta=(x,w,u)$, the certificate is $P\succeq0$, $T=\mathrm{diag}(\lambda)\succeq0$ and $\gamma$ such that $$ \begin{aligned}&\begin{bmatrix}A & B_1 & B_2\\ I & 0 & 0\end{bmatrix}^{\top}\begin{bmatrix}P & 0\\ 0 & -P\end{bmatrix}\begin{bmatrix}A & B_1 & B_2\\ I & 0 & 0\end{bmatrix}\\ &+\begin{bmatrix}C_2 & D_{21} & D_{22}\\ 0 & 0 & I\end{bmatrix}^{\top}\begin{bmatrix}I & 0\\ 0 & -\gamma^2I\end{bmatrix}\begin{bmatrix}C_2 & D_{21} & D_{22}\\ 0 & 0 & I\end{bmatrix}\\ &+\begin{bmatrix}C_1 & D_{11} & D_{12}\\ 0 & I & 0\end{bmatrix}^{\top}\begin{bmatrix}0 & T\\ T & -2T\end{bmatrix}\begin{bmatrix}C_1 & D_{11} & D_{12}\\ 0 & I & 0\end{bmatrix}\preceq0 .\end{aligned} $$ For fixed weights it is linear in $(P,T,\gamma^2)$, so the smallest certified gain is an SDP; summing from $x_0=0$ gives $\sum_t\|y_t\|^2\le\gamma^2\sum_t\|u_t\|^2$.
Nonlinear Youla parameterisation (Wang et al., L-CSS 2023, Props. 1–2)
The closed-loop response is $z=T_0d+T_1\mathcal Q(T_2d)$ with stable LTI systems $T_0,T_1,T_2$. (1) For every contracting and Lipschitz $\mathcal Q$, the closed loop is contracting and the map from disturbances to the performance output is Lipschitz. (2) Conversely, every output-feedback controller (with a locally Lipschitz state-space realisation) that achieves a contracting and Lipschitz closed loop can be written in this form with a contracting and Lipschitz $\mathcal Q$. (3) RENs approximate any contracting and Lipschitz $\mathcal Q$ arbitrarily well on bounded input sets.
SDP for the one-step reachable set (Hu et al., CDC 2020, Thm. 1)
If the initial set satisfies the QCs defined by $M_{\rm in}(\cdot)$, the projected network those defined by $M_{\rm mid}(\cdot)$, and $M_{\rm out}(S)$ encodes the candidate set $\bar{\mathcal R}$, then feasibility of $$ M_{\rm in}(P)+M_{\rm mid}(Q)+M_{\rm out}(S)\preceq0 $$ for some admissible multipliers $(P,Q,S)$ implies $\mathcal R(\mathcal X_0)\subseteq\bar{\mathcal R}(\mathcal X_0)$. For a polytope with fixed facet normals $a_i$ one solves $\min b_i$ for each facet; for an ellipsoid, $\min-\log\det$ of its shape matrix. Multi-step sets are obtained recursively, $\bar{\mathcal R}_{t+1}=\mathrm{ReachSDP}(\bar{\mathcal R}_t)$, so over-approximation errors accumulate with the horizon.

15. Verification & Distribution-Free Guarantees

Algorithms: IBP, Fast-Lin, CROWN, α,β-CROWN (branch and bound with an incomplete bound); SDP-CROWN; DeepSDP; randomized smoothing with CERTIFY (Cohen et al.); split conformal prediction (Angelopoulos & Bates); the scenario approach.

Verification problem, linear specification
Given $f$, an input set $\mathcal X$ and $c\in\mathbb R^{n_m}$, $d\in\mathbb R$, decide whether $$ c^{\top} f(x) + d \le 0 \quad \text{for all } x\in\mathcal X, \qquad\text{equivalently}\qquad p^\star := \max_{x\in\mathcal X}\ c^{\top}f(x)+d \le 0 $$ For a classifier with true label $y$ and competitor $j$, $c = e_j - e_y$, $d=0$ certifies that the margin $f_y(x)-f_j(x)$ stays non-negative on $\mathcal X$. A sound verifier only answers “verified” when the property holds; a complete verifier always answers; an incomplete verifier computes an upper bound $\bar p \ge p^\star$ and verifies when $\bar p\le 0$.
Linear bounds on an activation: CROWN (Zhang et al. 2018, Def. 3.1)
For a neuron with pre-activation range $[l_r,u_r]$, two affine functions $h_{L,r}(z)=\alpha_{L,r}(z+\beta_{L,r})$ and $h_{U,r}(z)=\alpha_{U,r}(z+\beta_{U,r})$ with $\alpha_{L,r},\alpha_{U,r}\ge 0$ are valid linear bounds if $$ h_{L,r}(z)\ \le\ \phi(z)\ \le\ h_{U,r}(z)\qquad\text{for all } z\in[l_r,u_r] $$ ReLU, three cases: stable active, $0\le l_r$: $h_L=h_U=z$; stable inactive, $u_r\le 0$: $h_L=h_U=0$; unstable, $l_r \lt 0 \lt u_r$: the upper bound is the chord $h_U(z)=\dfrac{u_r}{u_r-l_r}(z-l_r)$ and the lower bound is any line through the origin, $h_L(z)=\alpha z$ with $\alpha\in[0,1]$. Fast-Lin fixes $\alpha=u_r/(u_r-l_r)$; CROWN’s adaptive rule takes $\alpha=1$ when $u_r\ge|l_r|$ and $\alpha=0$ otherwise, which minimises the area between $h_L$ and the ReLU on $[l_r,u_r]$.
SDP-CROWN inter-neuron bound (Chiu et al., Thms. 4.1 and 5.2)
For $c,\hat x\in\mathbb R^n$, $\rho\ge 0$, any $g\in\mathbb R^n$ and any $\lambda\gt 0$ (the paper writes $\lambda\ge0$; because of the $1/\lambda$, $\lambda=0$ only makes sense as the limit $\lambda\to0^+$), $$ \begin{aligned} c^{\top}\mathrm{ReLU}(x)\ &\ge\ g^{\top}x + h(g,\lambda)\qquad\forall x\in\mathcal B_2(\hat x,\rho),\\ h(g,\lambda) &= -\tfrac12\Big(\lambda(\rho^2-\|\hat x\|_2^2)+\tfrac1\lambda\|\varphi(g,\lambda)\|_2^2\Big), \end{aligned} $$ with $\varphi_i(g,\lambda)=\min\{c_i-g_i-\lambda\hat x_i,\ g_i+\lambda\hat x_i,\ 0\}$. For $\hat x=0$, the supremum over $\lambda\gt0$ (attained at $\lambda=\|\min\{c-g,\,g,\,0\}\|_2/\rho$ when both are positive, only approached as $\lambda\to0^+$ or $\lambda\to\infty$ when exactly one is zero) gives the clean form $c^{\top}\mathrm{ReLU}(x)\ge g^{\top}x-\rho\,\|\min\{c-g,\,g,\,0\}\|_2$ on $\mathcal B_2(0,\rho)$, and this offset is the best possible for the given slope $g$ (Thm. 5.3). For the CROWN slopes $g(\alpha)=\tfrac12\min\{c,0\}+\alpha\odot\max\{c,0\}$ the box-based offset is $-\rho\|\min\{g(\alpha),0\}\|_1$ (Lemma 5.1), while SDP-CROWN gives $-\rho\|\min\{g(\alpha),0\}\|_2$: the $\ell_1$ norm of an $n$-vector exceeds its $\ell_2$ norm by at most a factor $\sqrt n$.
DeepSDP, one hidden layer (Fazlyab, Morari & Pappas, Thm. 1; multi-layer Thm. 2)
Let $f(x)=W^1\phi(W^0x+b^0)+b^1$, let $\mathcal X$ satisfy the QC defined by $\mathcal P_{\mathcal X}$ and let $\phi$ satisfy the QC defined by $\mathcal Q_\phi$ on $\mathcal Z=\{W^0x+b^0: x\in\mathcal X\}$. If for some $P\in\mathcal P_{\mathcal X}$, $Q\in\mathcal Q_\phi$ the linear matrix inequality $$ M_{\rm in}(P) + M_{\rm mid}(Q) + M_{\rm out}(S)\ \preceq\ 0 $$ holds, where the specification $c^{\top}y\le d$ is encoded by $S=\begin{bmatrix}0&0&0\\0&0&c\\0&c^{\top}&-2d\end{bmatrix}$ (their eq. 37), so that $[x;y;1]^{\top}S\,[x;y;1]=2(c^{\top}y-d)$, and the three matrices are $P$, $Q$ and $S$ lifted to $\xi=[x;\,\phi;\,1]$ by the affine maps $\xi\mapsto[x;1]$, $\xi\mapsto[W^0x+b^0;\,\phi;\,1]$ and $\xi\mapsto[x;\,W^1\phi+b^1;\,1]$ respectively (e.g. $M_{\rm out}(S)=E^{\top}SE$ with $E\xi=[x;\,W^1\phi+b^1;\,1]$), then $c^{\top}f(x)\le d$ for all $x\in\mathcal X$. Minimising $d$ subject to the LMI is an SDP that returns a certified bound on $\max_{x\in\mathcal X}c^{\top}f(x)$.
Smoothed classifier (Cohen, Rosenfeld & Kolter, ICML 2019)
Let $f:\mathbb R^d\to\mathcal Y$ be any deterministic or random base classifier and $\varepsilon\sim\mathcal N(0,\sigma^2I)$. The smoothed classifier returns the most probable class of $f$ under noise, $$ g(x) = \arg\max_{c\in\mathcal Y}\ \mathbb P\big(f(x+\varepsilon)=c\big) $$ Write $p_A=\mathbb P(f(x+\varepsilon)=c_A)$ for the top class and $p_B$ for the runner-up.
Certified ℓ2 radius (Cohen et al., Thm. 1) and its tightness (Thm. 2)
Suppose that for a given $x$ there are $c_A\in\mathcal Y$ and $\underline{p_A},\overline{p_B}\in[0,1]$ with $$ \mathbb P\big(f(x+\varepsilon)=c_A\big)\ \ge\ \underline{p_A}\ \ge\ \overline{p_B}\ \ge\ \max_{c\ne c_A}\mathbb P\big(f(x+\varepsilon)=c\big) $$ Then $g(x+\delta)=c_A$ for all $\|\delta\|_2\lt R$, where $$ R = \frac{\sigma}{2}\Big(\Phi^{-1}(\underline{p_A})-\Phi^{-1}(\overline{p_B})\Big) $$ $\Phi^{-1}$ the standard Gaussian quantile function. The radius is tight: if $\underline{p_A}+\overline{p_B}\le 1$, and the $K=|\mathcal Y|$ labels leave room for the remaining probability, $\underline{p_A}+(K-1)\,\overline{p_B}\ge 1$, then for every $\|\delta\|_2\gt R$ there is a base classifier consistent with the class probabilities for which $g(x+\delta)\ne c_A$. (Cohen et al. state only the first condition. Without the second, normalisation forces $\mathbb P(f(x+\varepsilon)=c_A)\ge1-(K-1)\overline{p_B}\gt\underline{p_A}$ and a larger radius follows: for $K=2$, $0.6/0.3$ gives $R\approx0.389\sigma$, but $p_A\ge0.7$ certifies $0.524\sigma$.)
Marginal coverage of split conformal prediction (Vovk et al.; Angelopoulos & Bates, Thm. 1 and Thms. D.1–D.2)
Construction: a nonconformity score $s(x,y)$ fixed in advance (any model inside it trained on data independent of the calibration and test points), calibration scores $s_i=s(X_i,Y_i)$, $k=\lceil(n+1)(1-\alpha)\rceil$, $\hat q$ the $k$-th smallest of $s_1,\dots,s_n$ ($\hat q=+\infty$ if $k\gt n$), and $\mathcal C(x)=\{y:\ s(x,y)\le\hat q\}$. If $(X_1,Y_1),\dots,(X_n,Y_n),(X_{\rm test},Y_{\rm test})$ are exchangeable (i.i.d. suffices), then $$ \mathbb P\big(Y_{\rm test}\in\mathcal C(X_{\rm test})\big)\ \ge\ 1-\alpha $$ If in addition the scores have a continuous joint distribution (no ties almost surely), then also $$ \mathbb P\big(Y_{\rm test}\in\mathcal C(X_{\rm test})\big)\ \le\ 1-\alpha+\frac{1}{n+1} $$ The probability is over the calibration data and the test point jointly (marginal coverage).
Conformal prediction regions for trajectory forecasts (Lindemann et al., Lemma 1 and Thm. 1)
Nonconformity score $R_{\tau|t}=\|Y_\tau-\hat Y_{\tau|t}\|$, computed on every calibration trajectory, sorted, with $R^{(|D_{\rm cal}|+1)}=\infty$ appended, and $$ C_{\tau|t} := R^{(p)}_{\tau|t},\qquad p=\big\lceil(|D_{\rm cal}|+1)(1-\bar\delta)\big\rceil $$ Lemma 1. $\mathbb P\big(\|Y_\tau-\hat Y_{\tau|t}\|\le C_{\tau|t}\big)\ge 1-\bar\delta$ for each $\tau\gt t$. This needs the paper’s assumptions, not just the construction of the scores: the calibration trajectories and the test trajectory are drawn independently from the same law $\mathcal D$ (Assumption 2) and the predictor is learned from a separate training set $D_{\rm train}$, so the $|D_{\rm cal}|+1$ scores are i.i.d., hence exchangeable; when the regions are used in feedback control, the robot’s actions must also leave $\mathcal D$ unchanged (Assumption 1). Theorem 1. With $\bar\delta:=\delta/T$, simultaneously over the horizon, $$ \begin{aligned} &\mathbb P\big(\|Y_\tau-\hat Y_{\tau|0}\|\le C_{\tau|0}\ \ \forall\tau\in\{1,\dots,T\}\big)\ge 1-\delta,\\ &\mathbb P\big(\|Y_{t+1}-\hat Y_{t+1|t}\|\le C_{t+1|t}\ \ \forall t\in\{0,\dots,T-1\}\big)\ge 1-\delta . \end{aligned} $$
Scenario program and violation probability (Calafiore & Campi 2006; Campi & Garatti 2008)
Let $\mathcal X\subseteq\mathbb R^d$ be a closed convex design domain, $\mathcal X_\delta\subseteq\mathbb R^d$ a closed convex set for every $\delta\in\Delta$ and $\mathbb P$ a probability on $\Delta$. The uncertain program is $\min_{x\in\mathcal X} c^{\top}x$ s.t. $x\in\mathcal X_\delta$ for all $\delta\in\Delta$. Draw $\delta^{(1)},\dots,\delta^{(N)}$ i.i.d. from $\mathbb P$ and solve the scenario program $$ x^\star_N=\arg\min_{x\in\mathcal X}\ c^{\top}x\quad\text{s.t.}\quad x\in\bigcap_{i=1}^N\mathcal X_{\delta^{(i)}} $$ The violation probability of a design $x$ is $V(x)=\mathbb P\{\delta:\ x\notin\mathcal X_\delta\}$. A constraint is a support constraint if removing it changes the solution; there are at most $d$ of them, and the problem is fully supported if, for every $N\ge d$, there are exactly $d$ with probability one.
Exact feasibility of scenario solutions (Campi & Garatti 2008, Thm. 2.4)
Assume every scenario program is feasible, its feasible set has non-empty interior, and its solution exists and is unique. Then for every $\varepsilon\in(0,1)$, $$ \mathbb P^N\big\{V(x^\star_N)\gt\varepsilon\big\}\ \le\ \sum_{i=0}^{d-1}\binom Ni\varepsilon^i(1-\varepsilon)^{N-i} $$ with equality for every fully supported problem. The right-hand side is the lower tail $\mathbb P(\mathrm{Bin}(N,\varepsilon)\le d-1)$ of a binomial distribution; it does not depend on $\mathbb P$, on the geometry of the sets $\mathcal X_\delta$ or on the cost.
Hoeffding’s inequality and the validation sample size
If $\phi_1,\dots,\phi_M$ are i.i.d. with values in $[0,1]$ and $\hat\phi=\frac1M\sum_i\phi_i$, then for every $t\gt 0$, $\mathbb P\big(\hat\phi-\mathbb E[\phi]\ge t\big)\le e^{-2Mt^2}$ (one-sided; the two-sided version has a factor 2). Hence with probability at least $1-\alpha$ the true success probability satisfies $\mathbb E[\phi]\ge\hat\phi-t$ as soon as $$ M\ \ge\ \frac{\ln(1/\alpha)}{2t^2} $$ For $t=0.05$ and $\alpha=0.05$ this is $M\ge 600$; for $t=0.02$, $\alpha=0.01$ it is $M\ge 5757$.
Safe Learning — study notes on safe RL, safe ML and learning-based control