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

Regions of attraction under uncertainty, Lyapunov-based safe RL, neural certificates, learning-based and certified approximate MPC, statistical robust synthesis

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

Module 10 certified that a set is never left; this module also asks that the state is brought back. A Lyapunov function certifies both, and "safe" becomes "inside a certified region of attraction": the pendulum may swing but never falls. Berkenkamp et al. certify such a region from finitely many GP-modelled samples, so an RL agent can improve its policy and explore without leaving it. Chow et al. use a Lyapunov function for the constraint budget of a CMDP, turning a trajectory-level constraint into one linear constraint per state. Neural certificates learn Lyapunov and barrier functions with the controller and verify them afterwards. Model predictive control supplies the robust, recursively feasible backbone, and the Trimpe and Pauli groups show how to keep its guarantees when the MPC is replaced by a network or combined with learned uncertainty bounds.

1. Lyapunov Stability and Regions of Attraction

Stability is a safety notion because it encodes recoverability: a controller that stabilises the upright pendulum on a set $S$ brings any state of $S$ home, so an exploratory action that stays in $S$ can always be undone (safety notion (e) of Module 1). Everything below is discrete time, because learning algorithms see sampled data.

Proof idea (full proof: Exercise 11.1). Invariance: $V(x_t)\le c\Rightarrow V(x_{t+1})\le V(x_t)\le c$ (strict unless $x_t=0$). Convergence: $V(x_t)$ decreases to some $v^\ast\ge0$ (a bounded monotone sequence; see Primer 0); if $v^\ast\gt0$, the trajectory stays in the compact annulus $\{v^\ast\le V\le c\}$ where the continuous $\Delta V$ has a maximum $-\eta\lt0$, so $V$ would drop by $\eta$ every step. Hence $V(x_t)\to0$ and, by positive definiteness and compactness, $x_t\to0$.

Why each assumption matters. (A4) must hold on the whole set: one point with $\Delta V\ge0$ can be the exit door. (A3) excludes unbounded sublevel sets (a $V$ that is not radially unbounded; see Primer D), along which trajectories can drift to infinity while $V$ decreases. (A1) is the subtle one: with $V=x^2$ and $F(x)=x/2$ for $x\le1$, $F(x)=(1+x)/2$ for $x\gt1$, $\Delta V\lt0$ for all $x\ne0$ and all sublevel sets are compact, yet $x_0=2$ gives $x_t=1+2^{-t}\to1$: the limit point would be a fixed point of the continuous extension of $F$.

Linear systems, linearisation, and the largest certified level

For $x_{t+1}=Ax_t$ and $V=x^\top Px$ (see Primer A), $\Delta V(x)=x^\top(A^\top PA-P)x$, and the Stein equation $A^\top PA-P=-Q$, $Q\succ0$, has a unique solution $P\succ0$ exactly when $A$ is Schur stable: the discrete-time Lyapunov LMI of Module 2 (see Boyd et al., SIAM 1994). Then every sublevel set is an inner estimate and $\mathcal R_\pi=\mathbb R^q$. For a nonlinear loop $F_\pi(x)=Ax+r(x)$ (see Primer B), $A=\partial F_\pi/\partial x(0)$, the same $P$ certifies a neighbourhood of the origin.

Largest certified level. For a fixed $V$, ROA estimation is a line search over the scalar level $c$. With known $F_\pi$, the first failing level is the infimum (Primer 0; it need not be attained, and $\inf\varnothing=+\infty$)

since every compact $\mathcal V(c)$ with $c\lt c^\ast$ satisfies (A4). For polynomial systems, sufficient certificates can be sought using sum-of-squares relaxations or suitable LMIs via the S-procedure (Module 2); local sector constraints are introduced in Module 2; for their later use with neural controllers, see Module 14. With unknown $f$, $\Delta V$ cannot be evaluated at all: the starting point of Section 2. Candidates come from physical energy or from value functions: if the stage cost $r(x,u)$ is positive away from the origin, the undiscounted cost-to-go (see Primer E) satisfies $J(x)=r(x,\pi(x))+J(F_\pi(x))$, so $\Delta J=-r\lt0$.

The undiscounted argument requires a finite, continuous cost-to-go with $J(0)=0$. With a discount $0\lt\gamma\lt1$, $J=r+\gamma J\circ F_\pi$ gives $J(F_\pi(x))=(J(x)-r(x,\pi(x)))/\gamma$, hence $\Delta J=\big((1-\gamma)J-r\big)/\gamma$, which can be positive where $r$ is small compared with $(1-\gamma)J$. A discounted value is therefore only a candidate whose decrease still has to be checked.

2. Safe Model-Based RL with Stability Guarantees (Berkenkamp et al.)

Berkenkamp, Turchetta, Schoellig & Krause, NeurIPS 2017 turn Section 1 into a learning algorithm: which sublevel set can be certified with high probability from finitely many noisy evaluations of partly unknown dynamics, and how can the policy be improved and data be collected without ever leaving it?

Confidence intervals on $V(f)$. Let $L_V$ be a Lipschitz constant of $V$ on a set containing both the true successors $f(x,u)$ and the means $\mu_{n-1}(x,u)$. Since $|V(f)-V(\mu)|\le L_V\|f-\mu\|_1\le L_V\beta_n\sigma$, Assumption 2 gives, with probability at least $1-\delta$,

As in SafeOpt (Module 4) the intervals are intersected, $C_n:=C_{n-1}\cap Q_n$, with $C_0=(-\infty,V(x)-L_{\Delta V}\tau)$ on the initial safe set $S_0=\{(x,\pi_0(x)):x\in S_0^x\}$ and $C_0=\mathbb R$ elsewhere; $u_n:=\sup C_n$, $l_n:=\inf C_n$ (supremum and infimum, because $C_0$ is open or unbounded; $\pm\infty$ allowed). The sound version used below takes $C_0=\mathbb R$ everywhere and intersects only valid confidence intervals: on the calibration event every $C_n$ contains the true $V(f(x,u))$, so an empty intersection signals a violated assumption. (The paper scales by $\beta_n$, not $\beta_n^{1/2}$: our convention.) The decrease condition cannot be checked at infinitely many states, so let $X_\tau\subset X$ be a grid with $\|x-[x]_\tau\|_1\le\tau$ for all $x\in X$, $[x]_\tau$ the nearest grid point.

Safe policy optimisation and safe exploration

Safety is a property of states under a fixed policy, so the policy is chosen together with the level. The following are the source equations (2–3); for use here, replace their grid constraint by the repaired annular test and current-policy inner certificate above:

Theorem 3 follows from a sound version of Theorem 2 (in this page, use the repaired test): with probability at least $1-\delta$, $\mathcal V(c_n)\subseteq\mathcal R_{\pi_n}$ for all $n\gt0$. Problem (3) is intractable and ignores performance, so the practical algorithm minimises the Lagrangian (their eq. 7; Lagrangian penalties: Primer B)

over $\pi_\theta\in\Pi_L$, with $r\ge0$ a cost, $J_{\pi_\theta}$ the discounted cost-to-go under the mean dynamics, $\lambda=1$, and the value function as Lyapunov function, $V=J$; $c_n$ is computed afterwards for the fixed policy, and one reverts to the previous (certified) policy if the set shrinks. Two consequences: a discounted $J$ need not decrease at all (Section 1), which is exactly what the certification step checks; and since $V=J$ changes with the policy, the intervals $Q_n$ for $V(f)$ must be recomputed for the new $V$ before certifying. Since $L_{\Delta V}$ grows with $L_\pi$, the constraint term also regularises the policy's Lipschitz constant. For exploration, safety is generalised from already-safe pairs (eq. 4), the pairs whose successor provably stays in $\mathcal V(c_n)$ form $S_n$ (eq. 5), and the most uncertain one is sampled (eq. 6):

with $U_\tau$ a discretised action set, $z=(x,u)$ and $z'=(x',u')$ stacked state–input pairs, and $\pi_n$ as backup policy at the boundary of $\mathcal V(c_n)$ (the backup idea of Module 6). The sampled input is written $a_n$ because $u_n(x,u)$ already denotes the upper confidence bound.

The repaired practical version has the safety guarantee when all certification assumptions hold; a fixed penalty or a heuristic GP band alone does not establish them. The source exploration guarantee concerns its idealised sets and is not automatically inherited by this repair. On a simulated torque-limited pendulum with a wrong prior (lower mass, no friction), a policy network with two hidden layers of 32 ReLU units (see Primer E) is improved from 50 safely collected points; the certified set grows inside the true region of attraction and the pendulum never falls. The authors name the main limitation: grid verification suffers from the curse of dimensionality.

The precursor (CDC 2016). Berkenkamp, Moriconi, Schoellig & Krause, CDC 2016 treat a fixed policy in continuous time: with $\|g_\pi\|_k^2\le B_g$ (Srinivas convention, $\beta_n^{1/2}$, $\beta_n=2B_g+300\gamma_n\log^3(n/\delta)$ in their Lemma 1; their Assumption 1 writes the unsquared $\|g_\pi\|_k\le B_g$), $\dot V=\nabla V^\top(f_\pi+g_\pi)$ is affine in $g_\pi$, hence a GP (see Primer C); their Theorem 1 certifies the largest $c$ with $u_n(x)\lt-L\tau$ on $\mathcal V(c)\cap X_\tau$ ($L$ a Lipschitz constant of $\dot V$), $S_n=S_0\cup\mathcal V(c_n)$ lies in the ROA with probability at least $1-\delta$, and data are taken where $\sigma_{n-1}$ is largest. The experiment models the error as a GP sample with $\beta_n^{1/2}=2$ and $\tau=0.002$: a Bayesian, pointwise reading of the band, not the frequentist assumption of the theorem (Module 3).

3. Lyapunov-Based Safe RL (Chow et al.)

Chow, Nachum, Duenez-Guzman & Ghavamzadeh, NeurIPS 2018 use "Lyapunov" for a different object. Safety is the CMDP constraint of Module 8, an expected cumulative cost below a budget, and the goal is a policy update that never leaves the feasible set, unlike Lagrangian methods whose intermediate policies routinely violate it. The trick: replace one trajectory-level constraint by one local, linear constraint per state, certified by a function whose expected decrease pays for the constraint cost.

Can an optimal policy be Lyapunov-induced? In principle yes: their Lemma 1 gives an auxiliary cost $\epsilon$ with $L_\epsilon(s):=\mathbb E[\sum_{t\lt T^\ast}(c(s_t)+\epsilon(s_t))\mid\pi_B,s]=V_c^{\pi^\ast}(s)$, bounded by $\epsilon^\ast(s):=2Tc_{\max}D_{TV}(\pi^\ast\|\pi_B)(s)$.

The LP for the auxiliary cost. In practice $\epsilon$ is the largest auxiliary cost that keeps $L_\epsilon$ in the Lyapunov set, a linear program (their eq. 5; LPs and vertices: Primer B):

where $P_{\pi_B}$ is the transition matrix among transient states and $\mathbf 1(s_0)^\top(I-P_{\pi_B})^{-1}\mathbf 1(s)$ the expected number of visits to $s$. These visit counts must be positive: a transient state that $s_0$ never reaches under $\pi_B$ has coefficient $0$, so its $\epsilon$ is unconstrained and the LP is unbounded (fix or bound $\epsilon$ at such states; the paper only notes that the counts are non-negative). With one constraint and positive counts, an optimal vertex puts all the slack on the least visited state $\underline s$: $\tilde\epsilon(s)=(d-V_c^{\pi_B}(s_0))\mathbb 1\{s=\underline s\}/\mathbb E[\#\text{visits to }\underline s]$. A constant $\epsilon$ gives $\tilde\epsilon=(d-V_c^{\pi_B}(s_0))/\mathbb E[T^\ast\mid s_0,\pi_B]$ ($T$ may replace the expected stopping time). Exercise 11.5 shows why the vertex can be useless: it may leave zero slack where the policy should change.

Proposition 1 (SPI): (i) consistent feasibility ($\pi_k$ feasible $\Rightarrow$ $\pi_{k+1}$ feasible); (ii) monotone improvement at every state; (iii) convergence if strictly concave/convex regularisers are added. Safe value iteration (Proposition 2) has consistent feasibility and convergence; neither has an optimality guarantee. For large or unknown MDPs, safe DQN and safe DPI (see Primer E) learn a constraint-value network $\hat Q_D$ and a stopping-time network $\hat Q_T$, set $\hat Q_L=\hat Q_D+\epsilon'\hat Q_T$ with $\epsilon'=(d-\pi_k(\cdot|s_0)^\top\hat Q_D(s_0,\cdot))/\pi_k(\cdot|s_0)^\top\hat Q_T(s_0,\cdot)$, solve the per-state LP on sampled states and distil the result into a policy network; exact feasibility needs certified error bounds and enough slack to absorb them, as below.

Small approximation error alone is insufficient at an active constraint. For example, if $\|\widehat L-L\|_\infty\le e$ and transitions are known, write $T_{\pi,c}L-L=(T_{\pi,c}\widehat L-\widehat L)+P_\pi(L-\widehat L)-(L-\widehat L)$; each of the last two terms is at most $e$ in absolute value (the rows of $P_\pi$ sum to at most one), so enforcing $T_{\pi,c}\widehat L-\widehat L\le-2e$ guarantees $T_{\pi,c}L-L\le0$. With discount $\gamma$ the middle term carries a factor $\gamma$ and the margin becomes $(1+\gamma)e$. Learned transitions or action values need their own error bounds; without such margins the deep versions have no exact feasibility guarantee.

Continuous actions: parameter projection and a Lyapunov safety layer

Chow, Nachum, Faust, Duenez-Guzman & Ghavamzadeh, arXiv 2019 carry this to policy gradients (DDPG, PPO) with discount $\gamma$: $Q_L(s,a)=c(s)+\epsilon(s)+\gamma\sum_{s'}P(s'|s,a)L_{\pi_B,\epsilon}(s')$, constraint $\int_a(\pi(a|s)-\pi_B(a|s))Q_L(s,a)\,da\le\epsilon(s)$, and $\epsilon=(1-\gamma)(d-V_c^{\pi_B}(s_0))$. $\theta$-projection linearises objective and constraint in the parameters (a minorisation–maximisation step built on the conservative-policy-iteration bound of Kakade & Langford, ICML 2002, with a second-order KL penalty whose weight is tuned in practice) and averages the constraints over sampled states; with constant $\epsilon$ this is the CPO constraint, i.e. CPO without line search (Module 9). $a$-projection linearises $Q_L$ in the action, $g_L(s):=\nabla_aQ_L(s,a)|_{a=\pi_B(s)}$, and projects the policy's action inside the network, a safety layer in the spirit of Dalal et al., arXiv 2018:

by the KKT conditions, for $g_L(s)\ne0$: exactly the single-constraint CBF-QP closed form of Module 10. If $g_L(s)=0$ the linearised constraint reads $0\le\epsilon(s)$: vacuous when $\epsilon(s)\ge0$ (always the case for a feasible baseline), so $a^\ast=\pi_\theta(s)$ and $\lambda^\ast=0$; infeasible otherwise.

4. Neural Lyapunov, Barrier and Contraction Certificates

Sections 1–2 take the Lyapunov function as given. For nonlinear systems with input limits a good certificate is as hard to find as a good controller, and sums-of-squares methods need polynomial dynamics and scale badly. The neural-certificate programme, surveyed by Dawson, Gao & Fan, T-RO 2023, parameterises the certificate (often with the controller) by a network, trains it on the certificate conditions, and then verifies it formally or accepts statistical evidence.

The CLF row only says that at every state some admissible input decreases $V$; a closed-loop conclusion also needs a feedback that selects such inputs regularly enough (e.g. Lipschitz) for the closed-loop trajectories to exist, hence "by a regular feedback" in the last column.

The survey's $\{h\le0\}$ is the opposite sign of Module 10's $\{h\ge0\}$ (Module 10). Two rows are sharper than the survey's wording: it writes the CLF condition with $\le0$, which with a regular feedback and a non-strict derivative bound gives only stability in the sense of Lyapunov, and the exponential CLF without the norm bounds, which makes $V$ but not $\|x-x_g\|$ decay exponentially (the bounds are part of the exponential-CLF definition of Ames et al., TAC 2014); and its "$R$ = square root of the condition number of $M$" must be read with uniform bounds, as in Manchester & Slotine, TAC 2017 (Theorem 1): a pointwise condition number does not suffice, since a scalar metric $M(x)=m(x)I$ has $\kappa\equiv1$. Synthesis is a feasibility problem, find $V$ with $c_i(x,V)\le0$ for all $x\in X$, $i\in I$, relaxed twice: constraints become penalties and "for all $x$" becomes "for sampled $x_j$", giving the empirical loss $\mathcal L_V=\sum_{i\in I}\frac{\alpha_i}{N}\sum_{j=1}^N\max(c_i(x_j,V),0)$ (their eq. 19). The survey is explicit that zero empirical loss "does not guarantee that the certificate is valid; it provides only statistical evidence of validity". A verifier closes the gap, either in the loop or after training.

Learner and falsifier: Neural Lyapunov Control

Chang, Roohi & Gao, NeurIPS 2019 alternate gradient steps on the empirical risk in $(\theta,u)$ with SMT queries, adding counterexamples until $\Phi_\varepsilon$ is unsatisfiable, and return the largest sublevel set inside $D$. The network must be smooth so that its Lie derivative exists and can be written in closed form for dReal (ReLU networks are excluded); the authors use tanh networks, other smooth activations would also do. A penalty $\frac1N\sum_i\|x_i\|_2-\alpha V_\theta(x_i)$ enlarges the certified region, which on their benchmarks exceeds LQR and SOS/SDP designs. Caveats: the SMT query is NP-hard in general (low-dimensional demos), and with the ball of radius $\sqrt\varepsilon$ excluded the certificate strictly gives invariance and convergence to the smallest sublevel set containing the ball; the inside needs another argument (the authors deem it physically insignificant; a linearisation as in Section 1 closes it).

Verify only what you claim: Yang et al. (ICML 2024)

Verifying the decrease on a whole box $B$ and then taking the largest sublevel set inside it is valid but wasteful. Yang, Dai, Shi, Hsieh, Tedrake & Zhang, ICML 2024 work in discrete time, $\xi_{t+1}=f_{cl}(\xi_t)$ with $\xi=x$ (state feedback) or $\xi=(x,\hat x-x)$ (output feedback with a neural observer), build positive definiteness into $V(\xi)=|\phi_V(\xi)-\phi_V(\xi^\ast)|+\|(\epsilon I+R^\top R)(\xi-\xi^\ast)\|_1$ (or a quadratic), and certify $S:=\{\xi\in B:V(\xi)\lt\rho\}$.

Bisection starts with a verified level and an unverified larger level, tests their midpoint, and keeps the corresponding half interval; larger $\rho$ imposes the condition on more states. A verifier timeout means only "not verified", so the result is the largest level found by this procedure, not necessarily the mathematically largest level. Projected gradient ascent (PGD) instead searches for violations by $\xi^+=\operatorname{proj}_B(\xi+s\nabla g(\xi))$ with a step size $s\gt0$, clipping coordinates back into $B$ after each ascent step (Primer B). It supplies counterexamples, never an absence proof.

In their Example 3.2 ($x_{t+1}=x_t+0.1u_t$, $\pi(x)=-x$, $V=x^\top x$, $B=[-1,1]^2$, $\kappa=0.1$) the condition holds on all of $B$; choose $\rho\gt2=\max_B V$ to obtain $S=B$, whereas the two-step approach certifies only the disc $x^\top x\le1$. Verification uses $\alpha,\beta$-CROWN (bound propagation plus branch-and-bound; see Module 15); training uses cheap PGD falsification of the hinge $\mathrm{ReLU}\big(\min(\mathrm{ReLU}(F(\xi))+c_0H(\xi_{t+1}),\ \rho-V(\xi))\big)$, with $H$ measuring how far $\xi_{t+1}$ leaves $B$. On pendulum and path tracking their certified regions strictly contain those of the baselines (MIP-verified DITL, SMT-verified NLC, UNL); they report faster verification than MIP on the harder systems (cart-pole 129 s versus 448 s, PVTOL 217 s versus 1935 s; MIP wins on the small pendulum), and, to their knowledge, the first formally verified neural output-feedback controllers with Lyapunov certificates (the quadrotor case takes 8.9 hours to verify).

5. Learning-Based and Robust MPC

MPC solves a constrained finite-horizon problem (see Primer D) at every step and applies the first input. Its safety argument is Section 1 in disguise: an invariant terminal set with a terminal controller makes the shifted previous plan a feasible candidate (recursive feasibility), and the optimal cost acts as a Lyapunov function. Learning enters in three places (taxonomy of Hewing, Wabersich, Menner & Zeilinger, Annu. Rev. 2020):

Tube MPC in one page

Robust MPC is the backbone of most results below (invariance: Blanchini, Automatica 1999; tubes: Mayne, Seron & Raković, Automatica 2005).

Aswani et al. (2013): one model for safety, one for performance

Aswani, Gonzalez, Sastry & Tomlin, Automatica 2013 consider $x_{n+1}=Ax_n+Bu_n+g(x_n,u_n)$ with polytopes $X,U$ (bounded intersections of finitely many half-spaces; Primer B), $g(x,u)\in W$ (a polytope) and full state measurement. Learning-based MPC (LBMPC) drives two predictions with the same inputs:

with $\tilde x_n=\bar x_n=x_n$. The "oracle" $\mathcal O_n$ is any learned, time-varying model; $\Omega$ is a disturbance-invariant, constraint-admissible set of the augmented state $(x,\theta)$, $\theta$ parameterising the tracked steady state $x_s=\Lambda\theta$, $u_s=\Psi\theta$, under the terminal tracking law $u=K(x-x_s)+u_s=Kx+(\Psi-K\Lambda)\theta$ (their eqs. 3–4).

Safety is deterministic and decoupled from learning. The authors also prove robust asymptotic stability (Theorem 2) and, under sufficient excitation, convergence in probability of the LBMPC law to that of an MPC with the true model (Section 4, Theorems 5–7; a simplified version is stated below). That second result needs identification assumptions that the robust-feasibility theorem does not supply. The price of the robust design is conservatism: the worst case $W$ is used everywhere. Soloperto, Müller, Trimpe & Allgöwer, NMPC 2018 address exactly this with robust MPC for linear systems with bounded state-dependent uncertainty sets, which can shrink where a learned model is confident (in their numerical example the sets come from GP regression).

Koller et al. (2018): GP confidence tubes and a safe terminal set

Koller, Berkenkamp, Turchetta & Krause, CDC 2018 combine Section 2's GP model with MPC: $x_{t+1}=h(x_t,u_t)+g(x_t,u_t)$, $h$ twice continuously differentiable, $\|g\|_k\le B_g$, polytopic constraints. Their Lemma 1 (Chowdhury–Gopalan type, noise parameter $\lambda$) gives $|\mu_{n-1,j}(z)-g_j(z)|\le\beta_n\sigma_{n-1,j}(z)$ for all output dimensions and all $z=(x,u)$ with probability at least $1-\delta$. Under affine feedback $\pi_t(x)=K_t(x-p_t)+u_t$, the linearised prior (with a Lipschitz-gradient remainder) and the GP confidence box map an ellipsoid $R_t$ to an ellipsoid $R_{t+1}=\tilde m(R_t,\pi_t)$ containing all reachable states.

A performance plan with any model may run alongside if its first $r$ inputs coincide with the safe return plan. The experiments again fix $\beta_n=2$ "following" Berkenkamp et al., outside the theorem. The terminal-set-plus-backup argument is also the core of predictive safety filters (Module 10). The cautious MPC of Hewing, Kabzan & Zeilinger, TCST 2020 is the stochastic alternative: mean and variance of a GP residual are propagated by linearisation and $\Pr(h^\top x_k\le b)\ge p$ becomes $h^\top\mu_k+\Phi^{-1}(p)\sqrt{h^\top\Sigma_kh}\le b$; fast (autonomous racing), but the propagation, and hence the guarantee, is approximate.

Gros & Zanon (2020): MPC as the function approximator of RL

Category (ii) keeps a possibly wrong model and learns the MPC's cost so that the closed loop is optimal. Gros & Zanon, TAC 2020 show this is possible in principle.

Since $\hat L$ is unknown, an economic NMPC (their eq. 21; soft constraints and slack penalties: Primer B) is parameterised, with cost $\lambda_\theta(x_0)+\gamma^NV^f_\theta(x_N)+w_f^\top\sigma_N+\sum_{k\lt N}\gamma^k(l_\theta(x_k,u_k)+w^\top\sigma_k)$, model $f_\theta$, input constraints and softened state constraints $h_\theta(x_k,u_k)\le\sigma_k$; its optimal cost $V_\theta$ and first-input-fixed version $Q_\theta$ serve as function approximators, updated by Q-learning or deterministic policy gradients with NLP sensitivities:

The constraints stay explicit but softened, so violations remain possible; the authors state that safety-critical constraints need robust NMPC. Zanon & Gros, TAC 2021 take this step: the policy is a robust (tube) linear MPC whose parameters $\theta$ include the uncertainty set $\hat S^+(s,a,\theta)$ it robustifies against, and the RL update is a constrained problem whose "safe-design constraint" demands that every observed transition lies in $\hat S^+(s_k,a_k,\theta)$. Given that constraint, the robust MPC satisfies the constraints by construction; but the constraint is checked only on data, so safety is $\eta$-safety, with $\eta(\mathcal D)$ the probability, given the data, that the learned set really contains the true dispersion. Their "Fundamental Limitation 1" states that $\eta(\mathcal D)=1$ cannot be guaranteed from finite data without further assumptions on the system.

6. Certified Approximate MPC with Neural Networks

A nonlinear MPC needs an NLP solve every sampling period, too slow or unpredictable for fast embedded systems. Fitting a network $\pi_{\mathrm{approx}}\approx\pi_{\mathrm{MPC}}$ offline throws away what made MPC attractive: any approximation error can break recursive feasibility and constraint satisfaction. The papers below keep guarantees, but in different senses, and conflating them is the most common mistake here. This is also where the two research lines behind this site meet topically: the Trimpe group's approximate MPC (Hertneck, Nubert, Hose, Tokmak, with Johannes Köhler as robust-MPC link) and Patricia Pauli's quadratic-constraint view (Drummond et al., Chatzikiriakos et al.), both rooted in Allgöwer's Stuttgart group; no joint paper links them.

Hertneck et al. (2018): robustness by design, validation by Hoeffding

Hertneck, Köhler, Trimpe & Allgöwer, L-CSS 2018 make the MPC tolerate the error it will later suffer: treat $\pi_{\mathrm{approx}}(x)=\pi_{\mathrm{MPC}}(x)+d$, $\|d\|_\infty\le\eta$, as an input disturbance. The robust MPC is a nominal MPC with terminal set $X_f$ and tightened constraints $\bar X_k=(1-\epsilon_k)X$, $\bar U_k=(1-\epsilon_k)U_t$, $U_t=U\ominus\{\|d\|_\infty\le\eta\}$, $\epsilon_k=\epsilon(1-\sqrt\rho^{\,k})/(1-\sqrt\rho)$ growing like a tube. Assumptions 1–4: local incremental stabilisability (a $\delta$-Lyapunov function contracting at rate $\rho\lt1$), $\|f(x,u+d)-f(x,u)\|\le\lambda\|d\|_\infty$, a bound on $\eta$, and a robustly invariant terminal set with a local control Lyapunov function. Written out:

Nubert, Köhler, Berenz, Allgöwer & Trimpe, RA-L 2020 scale this to a KUKA LBR4+ arm: a robust setpoint-tracking MPC (nonlinear constraint tightening, obstacle avoidance, artificial steady states) approximated by a 20-layer ReLU network with about $5\cdot10^6$ parameters. Their Proposition 2 splits the tube budget, $w_d=w_{d,\mathrm{model}}+w_{d,\mathrm{approx}}$, and Hertneck's lemma is reused for validation. Honestly reported: the validation criterion held for only about 90% of sampled points, so the statistical guarantee was not obtained on hardware, and input constraints were occasionally violated under measurement noise. The network ran in about 1 ms (a 200-fold speed-up), and in thousands of runs the robot never came close to an obstacle.

Hose et al. (2025): check online, fall back deterministically

Hose, Köhler, Zeilinger & Trimpe, TCST 2025 let the network predict the whole input sequence $\hat{\mathbf u}=\Pi_{\mathrm{NN}}(x)\in U^N$, which one forward simulation can check: $\mathbf u\in\mathcal U^N(x)=\{\mathbf u\in U^N:\ \phi(k;x;\mathbf u)\in X\ (k\lt N),\ \phi(N;x;\mathbf u)\in X_f\}$, with $\phi(k;x;\mathbf u)$ the predicted state and $V(x,\mathbf u)$ the MPC cost.

How often the network is accepted is a performance question. Their Lemmas 2–3 give a sufficient condition: approximate a robust MPC with $\Pi_{\mathrm{RMPC}}(x)\oplus\mathcal B_\epsilon^N\subseteq\mathcal U^N(x)$; then any network with error at most $\epsilon$ is feasible. The online cost, one network evaluation and one forward simulation (typically within 0.2 ms), is one to four orders of magnitude below online optimisation on three nonlinear benchmarks on which the naive network violates constraints: a predictive safety filter whose optimisation is replaced by a single check.

Tokmak et al. (2025): certify the approximation error itself

Tokmak, Fiedler, Zeilinger, Trimpe & Köhler, TAC 2025 replace statistics by an interpolation bound. For samples $X$ of the function $f$ to approximate (here the MPC law), the kernel interpolant $h_X(x)=k_X(x)^\top K_X^{-1}f_X$ and the power function $P_X(x)=\sqrt{1-k_X(x)^\top K_X^{-1}k_X(x)}$ satisfy the bound below (their Prop. 1, compare the noise-free bound of Module 3). It needs their Assumption 1, a continuous, strictly positive definite, radial kernel normalised to $k(x,x)=1$ (for a general kernel the $1$ becomes $k(x,x)$), pairwise distinct samples, so that $K_X$ is invertible, and $f$ in the RKHS of $k$:

ALKIA-X refines an adaptive partition into cubes sampled at their vertices, assuming the power function peaks at the cube centre (Assumption 2), until the bound is below $\epsilon$; a robust MPC for input errors up to $\epsilon$ then gives closed-loop guarantees (Theorem 2, Corollary 2). The catch is $\|f\|_k$: its bound is extrapolated exponentially from the interpolants' norms on two refinement levels (Assumption 5), "only a heuristic" that "may fail on some occasions" in the authors' words; finite samples never bound the RKHS norm of an unknown function (their Remark 1; Module 5).

The Pauli line: worst-case bounds and value functions

Drummond, Duncan, Turner, Pauli & Allgöwer, L4DC 2022 compare a given NN controller with a given input-constrained linear MPC. The MPC law solves a QP, $z_{\mathrm{MPC}}(x)=\arg\min_uu^\top Hu+u^\top hx$ s.t. $Lu\le b$, whose solution satisfies quadratic constraints derived from the QP's structure (their Theorem 6, Lemma 7); the NN, in implicit form $z=\phi(Wz+W_0x+\beta)$ (see Primer E), satisfies activation QCs; the state box satisfies a diagonal QC. The S-procedure (Module 2, also the engine of LipSDP; see Module 12) turns this into an SDP certifying $\|u_{\mathrm{NN}}(x)-u_{\mathrm{MPC}}(x)\|_2^2\le\gamma_x\|x\|_2^2+\gamma$ for all $x$ in the box (their Theorem 10); the same machinery synthesises an MPC that robustly approximates a given NN (Theorem 11).

Chatzikiriakos, Wabersich, Berkel, Pauli & Iannelli, L4DC 2024 learn the value function $\tilde V^s$ of a tightened soft-constrained MPC instead of its policy: soft constraints make it locally Lipschitz (the policy may be discontinuous), and $\tilde u(x)\in\arg\min_{u\in U}\ell(x,u)+\tilde V^s(f(x,u))$ is a one-step problem, solvable by gridding a low-dimensional input. Given a uniform error bound $|\tilde V^s-V^{\ast,s}|\le\hat\varepsilon$ (their Assumption 3, assumed, not certified) and invariance of the feasible set, the closed loop is input-to-state stable with respect to the error, $|x(k)|\le\beta(|x(0)|,k)+\sigma(\sup_{i\lt k}|\bar\varepsilon(x(i))|)$ with $\beta\in\mathcal{KL}$, $\sigma\in\mathcal K$ (Theorem 3, for all $x(0)$ in the soft-constrained feasible set $X_{N,s}$). Constraint satisfaction needs more (Theorem 4): let $X_N^\eta$ be the feasible set of the hard-constrained MPC with state constraints tightened by $\eta\in(0,1)$; if $\ell(x,0)\gt2\hat\varepsilon$ for all $x\in X\setminus X_N^\eta$ (their Assumption 5) and the slack penalty $\rho$ satisfies $\eta\rho\ge V_{\max}+4\hat\varepsilon$ with $V_{\max}\ge V^{\ast,s}(x)$ for all $x\in X_N^\eta$, then trajectories starting in $X_N^\eta$ satisfy the original constraints. Starting anywhere in the larger $X_{N,s}$ gives ISS, not this guarantee.

7. Statistical Guarantees Meet Robust Control (Fiedler, Scherer, Trimpe)

Robust control certifies a controller for every member of an uncertainty set; learning produces sets that are correct only with high probability. Composing the two gives closed-loop guarantees with the probability of the learning step, provided the learned set is expressed in the language of robust control. Three statistical tools recur.

The third tool is the uniform GP error bound of Module 3: a tube $|\varphi(x)-\mu_D(x)|\le\beta_D\sigma_D(x)$ for all $x$ simultaneously, with probability $1-\delta$ over the data, for a fixed unknown function. This frequentist reading is what robust control needs.

Fiedler, Scherer & Trimpe (CDC 2021): from a GP tube to IQC synthesis

Fiedler, Scherer & Trimpe, CDC 2021 build a pipeline in which every stage carries a guarantee. The plant is a linear fractional representation: a known LTI part $G$ in feedback with $p=\Delta(q)$, here a diagonal static nonlinearity $p_i=\varphi_i(q_i)$, $i\le n_p$, whose unknown parts are "pulled out" so that all prior knowledge stays in $G$.

1. Learn. $y_n=\varphi(x_n)+\epsilon_n$ with independent $R$-sub-Gaussian noise (Assumption 1), $\varphi\in\mathcal H_k$, $\|\varphi\|_k\le B$ (Assumption 2); prior knowledge such as $\varphi(0)=0$ goes into the kernel, $k_0(x,x')=k(x,x')-k(x,0)k(x',0)/k(0,0)$ (for $k(0,0)\gt0$). This is the covariance of a zero-mean GP conditioned on the exact observation $\varphi(0)=0$ (Gaussian conditioning, Primer C), so $k_0(0,x)=0$ and every sample vanishes at $0$; in the frequentist reading used here, $\mathcal H_{k_0}$ consists exactly of the functions in $\mathcal H_k$ with $\varphi(0)=0$, with the same norm, so Assumption 2 carries over.
2. Bound. Proposition 1: $\mathbb P[|\varphi(x)-\mu_D(x)|\le\beta_D\sigma_D(x)\ \forall x]\ge1-\delta$ with a data-dependent $\beta_D$.
3. Sector. $\varphi$ is in the sector $[\kappa_1,\kappa_2]$ if $\kappa_1x^2\le x\varphi(x)\le\kappa_2x^2$ (Module 2). Lemma 2 gives the tightest sector compatible with the tube on $[a,b]$: $\hat\kappa_1=\inf_{x\in[a,b]\setminus\{0\}}\min\{x(\mu_D-\beta_D\sigma_D),\,x(\mu_D+\beta_D\sigma_D)\}/x^2$ and $\hat\kappa_2$ likewise with outer supremum and inner maximum, so with probability $1-\delta$ the true $\varphi$ lies in the sector $[\hat\kappa_1,\hat\kappa_2]$ on $[a,b]$: $\hat\kappa_1x^2\le x\varphi(x)\le\hat\kappa_2x^2$ there. Equivalently, $[\kappa_1,\kappa_2]\subseteq[\hat\kappa_1,\hat\kappa_2]$ for the tightest local sector, $\kappa_1=\inf_{[a,b]\setminus\{0\}}\varphi(x)/x$ and $\kappa_2$ likewise with sup. The paper states the containment for any sector of $\varphi$, which fails for a loose one: $\varphi(x)=x$ lies in $[-10,10]$, but an exact tube gives $[1,1]$. (For $x\ne0$ the tube gives an interval for $\varphi(x)/x$; dividing by a negative $x$ swaps its endpoints, hence the inner $\min$/$\max$. The punctured interval is not compact, hence $\inf$/$\sup$, and the ratios can blow up near $0$: the sector is finite only if, e.g., $|\mu_D(x)|+\beta_D\sigma_D(x)\le C|x|$ near $0$.)
4. Multipliers. With $\hat\kappa_1^{(i)}\le0\le\hat\kappa_2^{(i)}$ (Assumption 3), full-block multipliers on the vertices of the estimated sector box cover all channels; step 2 with $\delta/n_p$ per channel and a union bound makes the IQC description valid with probability $1-\delta$ (Lemma 3).
5. Synthesise. IQC analysis LMIs (via the KYP lemma, Module 2) alternate with controller synthesis until the robust performance level $\tilde\gamma$ stops improving (later use for neural networks: Module 14).

Exploration with a-priori robustness. Holicki, Scherer & Trimpe, L-CSS 2021 take the complementary route for a partially unknown linear plant $P_0=\Delta_0\star P$, $\Delta_0\in\boldsymbol\Delta$ known. They partition $\boldsymbol\Delta=\bigcup_k\boldsymbol\Delta_k$ and, for each partition member, synthesise by IQC/LMI relaxation (their Theorem 1) a controller $F(k)$ that robustly stabilises all of $\boldsymbol\Delta$ while optimising the worst-case performance over $\boldsymbol\Delta_k$ only. Every controller of the family therefore stabilises every plant in $\boldsymbol\Delta$, so experiments can explore the index with any black-box method without risk of instability. The paper separates two gaps. Refining the partition around the best member shrinks the parameterisation gap, their (P). The "cost of safety", their gap (S), comes from demanding stabilisation of all of $\boldsymbol\Delta$, and a finer partition of the same set leaves it unchanged. It shrinks only when the members inconsistent with the measurements, those whose measured cost $L(k)$ of $F(k)$ exceeds the level $\gamma_\varepsilon^\ast(k)$ that Theorem 1 certifies for $F(k)$ over $\boldsymbol\Delta_k$, are discarded (their eq. 13, since $\Delta_0\in\boldsymbol\Delta_k$ implies $L(k)\le\gamma_\varepsilon^\ast(k)$) and the family is redesigned for the smaller remaining set. It is the robust-control answer to safe BO (Module 4): certify candidates a priori, not statistically.

Probabilistic robust LQR with GPs (von Rohr et al. 2021)

von Rohr, Neumann-Brosig & Trimpe, L4DC 2021 differentiate a GP dynamics model at the operating point, obtaining a Bayesian (matrix-normal) posterior over $S=[\bar A\ \bar B]$, truncated to its credible region of mass $c$ (a region of posterior probability $c$; Primer C). With $\phi_K=\mathbb 1[\rho(\bar A+\bar BK)\lt1]$ they seek $\mathbb E[\phi_K]\ge1-\epsilon$ at minimal expected LQR cost. A priori: the initial controller solves a common-Lyapunov LMI over $M$ sampled systems, a convex scenario program with $n_k=2d_x^2+d_xd_u$ variables; their Theorem 1 gives $\mathbb E[\phi_{K_{\mathrm{init}}}]\ge1-\epsilon$ with probability greater than $1-\beta$ if $M\ge\lceil\frac2\epsilon(\ln\frac1\beta+n_k)\rceil$. A posteriori: the improvement steps (a majorise–minimise scheme averaging over samples; see the MM background in Section 3) are not a scenario program, so the final $K^\ast$ is returned only if its empirical stability rate on $M_{\mathrm{val}}$ fresh samples satisfies $\hat\phi\ge1-\epsilon$.

Walkthrough: Certifying a Region of Attraction from Samples

The heart of Section 2 is a Lipschitz interpolation argument that turns finitely many uncertain evaluations into a statement about a continuum of states. Step through it with the notation of Section 2: $u_n$ is the upper confidence bound on $V(f(x,\pi(x)))$, $X_\tau$ a grid with $\|x-[x]_\tau\|_1\le\tau$, and $E$ the event of probability at least $1-\delta$ on which the model is calibrated.

Interactive: Certified Invariant Set Under Model Uncertainty

Compare a certified invariant set for an uncertain pendulum with simulated trajectories. Increase the uncertainty or change the grid resolution and predict how the certificate changes. The certificate concerns forward invariance and ultimate boundedness; the shaded capture region is empirical, and convergence to the origin is not certified.

What to try. (1) Raise $\sigma_g$: the certified ellipse (green) shrinks away from the grey $\sigma_g=0$ certificate and the inner set grows; at $n_g=40$ nothing is certified beyond $\sigma_g=0.055$, a finer grid recovers it. (2) Switch to the composite constant: about four times the largest cell bound on the box and, at the default settings, about 6.5 to 60 times the cell bounds on the certified set; nothing is certified at any grid size offered, which is why fine grids and local constants are used in practice. (3) Set $\vartheta\lt1$: the certificate grows but is no longer backed by a bound, and the trajectories usually still behave, which is exactly why such shortcuts are tempting. (4) Compare with the shaded capture region, simulated for one sampled $g$ (empirical, not a certificate): the certificate is limited by the shape of $V$, not only by uncertainty.

Exercises

Graded practice

Each level has four problems. Write your steps before opening the answer; use the hint when you need a first move. Close the answer and retry after checking it.

Easy practice

Medium practice

Hard practice

Original longer exercises

Key Papers

Flashcards