6. Global Safe Exploration of Dynamical Systems: GoSafe & GoSafeOpt
Disconnected safe regions, backup policies, boundary conditions, and safe exploration in MDPs
This module assumes:
- SafeOpt: safe sets, expanders, maximisers, and confidence widths (Module 4)
- SafeOpt-MC: multiple constraints and the selector function (Module 4)
- State-space trajectories, feedback, and uniqueness of solutions (Primer D)
- Lipschitz continuity and transferring safety margins (Primer B)
- Norms, distances, balls, and the triangle inequality (Primer A)
- RKHS assumptions and valid GP confidence bounds (Module 3)
- Reachable-set optimality and SafeOpt's sample budget (Module 4)
- Joint high-probability statements and union bounds (Primer C)
- MDPs, stochastic policies, episodes, and returns (Primer E)
- Why heuristic confidence multipliers lose the guarantee (Module 5)
Core reading. Read why parameter-space expansion can stop and trajectory-minimum constraints. Then follow stored backups and their state-space balls, the backup-proof walkthrough, and the safety/discoverability distinction in the guarantees.
Practice route. Try the three readiness checks. If a skill is rusty, use its exact review link, then return. Work through Easy P1–P4, Medium P5–P8, and Hard P9–P12; each has a separate hint and a full worked solution. Reattempt a missed problem later without opening the answer.
Optional research reading. GoSafe’s augmented grid, the experimental configurations, and the SafeMDP/SNO-MDP/ActSafe/SageMPC research survey can be read afterward. The finite-graph returnability example and the practice problems give an elementary introduction to the MDP branch without requiring those papers.
Try these before opening the answer. The review links lead to earlier material.
- What is the smallest of the margins $0.4,0.1,0.3$? Review minima and infima.
- If speed is bounded by 2 for 0.05 seconds, how far can a state move? Review trajectories.
- Does a safe endpoint prove the earlier path was safe? Review trajectory-level safety.
Show readiness answers
The minimum is 0.1. Integrating speed over the interval gives displacement at most $2(0.05)=0.1$. A safe endpoint does not prove the preceding path was safe; a state constraint must hold throughout the trajectory.
Book contents · Apply this chapter to a real decision · Glossary
1. Why Local Safe Exploration Gets Stuck
Parameter space and state space are different. A parameter $a$ chooses a controller; a state $x$ says where the system currently is. Two far-apart parameters can produce trajectories visiting similar states. A known controller can therefore be a backup near a previously visited state even when the parameter being tested has no safe neighbor in parameter space. GoSafeOpt uses this idea to try new parameters while monitoring whether a certified backup remains available. A backup protects only the states covered by its margin and motion bound; similarity in a plot alone is insufficient.
Module 4 ended with the SafeOpt guarantee of Sui et al., ICML 2015: with probability at least $1-\delta$ every query is safe (see Primer C), and after finitely many steps the recommended parameter is $\epsilon$-optimal within the safely reachable set. That qualifier is the whole story of this module. SafeOpt certifies a new parameter only by propagating a lower confidence bound from an already certified neighbour through Lipschitz continuity (see Primer B), so the certified set grows by contact. If the feasible region $\{a : g_i(a)\ge 0\ \forall i\}$ (see Primer B) of the underlying continuous parameter space has several connected components, SafeOpt only ever certifies parameters that are Lipschitz-reachable from the safe seed $S_0$; for a single constraint this means that it never leaves the component(s) containing $S_0$ (derivation below).
Set notation used throughout (see Primer 0): $\{a:g_i(a)\ge0\ \forall i\}$ is the set of all parameters $a$ that satisfy every constraint; $S\subseteq A$ means that every member of $S$ lies in $A$; $S\cup T$ collects the members of $S$ or $T$ (or both), $S\cap T$ those of both, and $A\setminus S$ those of $A$ outside $S$; $|S|$ is the number of members. An indexed union $\bigcup_i S_i$ contains the points that lie in at least one $S_i$, an indexed intersection $\bigcap_i S_i$ those that lie in every $S_i$.
The islands in the sketch below belong to the continuous feasible region, not to the finite candidate set $A$. A path is a continuous curve that lies entirely in the region; a path-connected component is a largest group of points that can all be joined to each other by such paths. The derivation below builds its paths from straight segments, so it proves membership in the seed's path-connected component. (Topology also knows the slightly weaker notion "connected"; for regions like the ones drawn here the two coincide, and the argument needs the path version.) The bar in $\bar R_\epsilon$ below denotes the limit of repeated certification, not the topological closure of a set.
Two facts suffice. (i) For every set $T$, $R^c_\epsilon(T)\subseteq R_\epsilon(T)$: a common witness $a'$ can serve as the separate witness $a'_i=a'$ of every constraint. (ii) Both operators are monotone, $T\subseteq T'\Rightarrow R_\epsilon(T)\subseteq R_\epsilon(T')$ (and likewise for $R^c_\epsilon$): a larger set of known points can only offer more witnesses. Now argue by induction on $n$, starting from $(R^c_\epsilon)^0(S)=R^0_\epsilon(S)=S$: if $(R^c_\epsilon)^n(S)\subseteq R^n_\epsilon(S)$, then
Both sequences only grow (each operator contains its argument) and $A$ is finite, so each stops changing after finitely many steps, and the limits inherit the inclusion: $\bar R^c_\epsilon(S)\subseteq\bar R_\epsilon(S)$.
Take a single constraint $g$ ($q=1$), assume that $g$ is defined and $L_a$-Lipschitz on a convex set (see Primer B) that contains the finite domain $A$ (which discretises it), and assume the confidence bounds are valid, $l_n(a)\le g(a)$. Every $a\in S_n\setminus S_{n-1}$ was added because some $a'\in S_{n-1}$ satisfies $l_n(a')-L_a\|a-a'\|\ge 0$. Take any point $a''=a'+\theta(a-a')$, $\theta\in[0,1]$, on the segment between them. Then
The first step is Lipschitz continuity, the second uses $\|a''-a'\|=\theta\|a-a'\|\le\|a-a'\|$, the third the validity of the lower bound. So the whole segment is feasible. By induction on $n$ every point of $S_n$ is joined to a point of $S_0$ by a chain of feasible segments, i.e. $S_n$ lies in the union of the path-connected components of the feasible region that meet $S_0$. Nothing SafeOpt observes can change this, because it never evaluates outside $S_n$.
With several constraints the picture needs care: the SafeOpt-MC update (eq. 8 in Section 4) lets every constraint $i$ have its own witness $a'_i$, and the segment $[a'_i,a]$ is then only known to satisfy its own constraint, so the chain argument applies only when one witness certifies all constraints. What holds in general is an operator statement. On the event that all confidence bounds are valid, every added $a$ has, for each $i$, a witness $a'_i\in S_{n-1}$ with $g_i(a'_i)-L_a\|a-a'_i\|\ge l_n(a'_i,i)-L_a\|a-a'_i\|\ge0$, so by induction $S_n\subseteq\bar R_0(S_0)$ for all $n$ (SafeOpt-MC, Lemma 9): the zero-error closure of the seed bounds everything SafeOpt can ever certify, and it is fixed by $S_0$ alone. GoSafeOpt phrases the idea as Proposition 4.4: for SafeOpt, $a^*$ is discoverable at iteration $n\gt0$ if and only if it is discoverable at $n=0$ (a parameter is "discoverable at $n$" if $a^*\in\bar R^c_\epsilon(A')$ for some $A'\subseteq S_n$, Definition 4.2 below). Read literally with a fixed $\epsilon\gt0$, the "only if" fails, because SafeOpt keeps sampling and can learn a constraint more precisely than $\epsilon$: with $A=\{0,0.45\}$, $S_0=\{0\}$, $g\equiv0.5$, $L_a=1$, $\epsilon=0.1$, the point $0.45$ is not in $\bar R^c_\epsilon(S_0)$ ($0.5-0.1-0.45\lt0$), but once a valid lower bound reaches $l_n(0)\ge0.45$ SafeOpt certifies it, and every point of $S_n$ is discoverable at $n$. So the positive-$\epsilon$ closure is a benchmark that SafeOpt is guaranteed to explore, while $\bar R_0(S_0)$ bounds what it can discover. The conclusion that matters here survives: a parameter outside $\bar R_0(S_0)$, such as one in a feasible island that no chain of Lipschitz certificates from the seed reaches, is never found.
The sketch shows the situation in a two-dimensional parameter space. The seed lies in island A; SafeOpt's safe set grows inside A and stops at its boundary, while the global optimum sits in island B.
Disconnected safe regions are not exotic. GoSafe cites stability regions of parameterised linear systems (D-decomposition), and local optima in gait learning for bipedal robots; GoSafeOpt exhibits one in the LQR-weight space $(q_c, r)$ (LQR: see Primer D) of an impedance controller for a simulated Franka Emika arm (its Fig. 5): a grid search reveals a disconnected safe region, and SafeOpt, which cannot reach it, "cannot significantly improve over the initial policy" (Sukhija et al., AIJ 2023).
An impedance controller makes a robot respond like a chosen mass, spring and damper around a desired position. In one coordinate, a simple force rule is $u=-k(x-x_{\rm ref})-b\dot x$ with stiffness $k\gt0$ and damping $b\gt0$. For $k=2$, $b=1$, position error $x-x_{\rm ref}=0.1$ and velocity $\dot x=0.2$, it requests $u=-2\cdot0.1-1\cdot0.2=-0.4$. Tuning these gains changes both tracking quality and the forces applied, which is why a parameter that performs well can still violate a safety constraint.
The way out exploits what the bandit model of safe BO throws away. SafeOpt treats an experiment as a black box: commit to $a$, wait, read the outcome. On a dynamical system (state-space models: see Primer D) we can instead watch the state during the experiment and switch to a different controller before anything breaks. Two algorithms from Sebastian Trimpe's group and its ETH Zurich collaborators build on this:
- GoSafe (Baumann et al., ICRA 2021) learns a safe set in the joint space of parameters and initial conditions, so that it knows from which states which policies can recover. It works, but the joint space must be discretised and explored, which limits it to low-dimensional systems.
- GoSafeOpt (Sukhija et al., AIJ 2023) keeps the GP in parameter space only and obtains backup policies for free from the Markov property: every state visited during a safe rollout is a state from which the same policy is known to be safe.
2. Safety Along Trajectories
Both algorithms consider an unknown, Lipschitz-continuous system with policy parameters $a$:
with state $x(t)\in X\subset\mathbb R^s$, input $u(t)\in U\subset\mathbb R^p$ and parameters $a\in A\subset\mathbb R^d$, where $A$ is a finite set (a continuous parameter space is discretised or randomly subsampled). The initial state $x_0$ is fixed and known, as in episodic RL (see Primer E). Because the system is deterministic, the whole trajectory is a function of $(a,x_0)$, so the objective and the constraints can be written as functions of the parameter alone, $f:A\to\mathbb R$ and $g_i:A\to\mathbb R$, $i\in I_g:=\{1,\dots,q\}$:
For each fixed $a$ the closed loop $\dot x=z\big(x,\pi^a(x)\big)$ is assumed to have, from every initial state, exactly one solution, defined for all $t\ge0$. A Lipschitz right-hand side gives uniqueness (Picard–Lindelöf, see Primer D); existence for all future times (no escape to infinity in finite time, called forward completeness) holds, e.g., when the right-hand side is globally Lipschitz or the trajectories stay in a bounded set. Because neither $z$ nor $\pi^a$ depends explicitly on time, restarting the policy from a visited state reproduces the rest of the trajectory, only shifted in time; Section 4 builds on exactly this.
Objective and constraints are stacked into one selector function $h(a,i)=f(a)$ for $i=0$ and $h(a,i)=g_i(a)$ for $i\in I_g$, with $I:=\{0\}\cup I_g$, exactly as in SafeOpt-MC (Berkenkamp et al., Mach. Learn. 2023). Two notational clashes with the rest of these notes: the letter $h$ is the selector here, not SafeOpt's safety threshold (the threshold is absorbed into $g_i\ge 0$) and not the barrier function introduced later (see Module 10); and the RKHS-norm bound is $B$ while the set of backups below is written $\mathcal B_n$. Confidence bounds are written in the Chowdhury–Gopalan convention of Module 3, $\mu_{n-1}\pm\beta_n\sigma_{n-1}$; the papers write $\beta_n^{1/2}\sigma_{n-1}$, so their $\beta_n$ is our $\beta_n^2$.
The GP input is the pair $(a,i)\in A\times I$: the Cartesian product lists every parameter together with every output index. Its kernel compares two such pairs. The outer index $n$ counts experiments; time $t$ runs within one experiment, which resets to $x_0$.
The five assumptions
Why the trajectory minimum is what makes backups possible
Two elementary facts about minima carry the whole construction. First, the minimum over a subset is at least the minimum over the set: if a trajectory is safe, every suffix of it is safe. Second, a state lies on the trajectory that starts at it, so the immediate constraint at $x$ is at least the trajectory minimum from $x$:
Hence a state is immediately safe as soon as some policy is known to be safe from it (GoSafe, Lemma 3). "Some policy is safe from $x$" is precisely the information a backup set stores. Section 4 shows that the Markov property delivers this information for every state visited during a safe rollout, at no experimental cost.
3. GoSafe: Exploring the Augmented Space
GoSafe (Baumann, Marco, Turchetta & Trimpe, ICRA 2021) makes the initial condition a second argument of everything. The reward and the constraints become $f(a,x_0)$ and $g_i(a,\tilde x_0)=\min_{t\ge0}\bar g_i(x(t))$ for a trajectory started at $\tilde x_0$, the selector is $h(a,\tilde x_0,i)$, and the safe set lives in $A\times X_\mu$, where $X_\mu$ is a quantisation of the bounded state space with $\|x-[x]_\mu\|_1\le\mu$ for every $x\in X$ ($[x]_\mu$ is the nearest grid point). The GP now models $h$ over the joint space, and the sets of Module 4 are rebuilt with two Lipschitz constants, $L_a$ in the parameter and $L_x$ in the state.
The exploration proceeds in three stages of increasing cost; at every iteration the first stage whose condition holds is executed.
- S1 if $\max\{w(a,x_0,i):\ (a,x_0)\in G\cup M,\ i\in I\}\gt\epsilon$, where only pairs at the nominal initial state $x_0$ are considered;
- otherwise S2 if $\max\{w(a,\tilde x_0,i):\ (a,\tilde x_0)\in G,\ i\in I_g\}\gt\epsilon$;
- otherwise S3, over the pairs $(a,\tilde x_0)\notin E_f\cup S$ with $a\in A$ arbitrary and $\tilde x_0\in P_X(S):=\{\tilde x_0\in X_\mu:\ \exists a'\in A,\ (a',\tilde x_0)\in S\}$, the projection of $S$ onto the state coordinate, i.e. the grid states that already have a certified policy.
| Stage | Search space | Acquisition | Purpose |
|---|---|---|---|
| S1 (SafeOpt) | $a\in A$ with $\tilde x_0=x_0$ | $a_n=\arg\max_{(a,x_0)\in G_n\cup M_n}\max_{i\in I}w_n(a,x_0,i)$ (eq. 4) | optimise and expand for the nominal initial state, as in Module 4 |
| S2 (joint expansion) | $(a,\tilde x_0)\in A\times X_\mu$ | $(a_n,\tilde x_0)=\arg\max_{(a,\tilde x_0)\in G_n}\max_{i\in I_g}w_n(a,\tilde x_0,i)$ (eq. 5), expanders only | learn from which states which policies are safe: this is the backup set |
| S3 (global) | $a\in A$ arbitrary, $\tilde x_0\in P_X(S_n)$, excluding $E_f\cup S_n$ | $(a_n,\tilde x_0)=\arg\max\max_{i\in I}w_n(a,\tilde x_0,i)$ (eq. 6) | test possibly unsafe parameters; intervene if the state reaches the border $\partial S_n$ |
The border of the safe set is the set of certified grid states with an uncertified neighbour, $\partial S_n:=\{\tilde x_0\in X_\mu\mid\exists a:(a,\tilde x_0)\in S_n\ \wedge\ \exists x\in X:\|\tilde x_0-x\|_1\lt2\mu\ \wedge\ \nexists a':(a',[x]_\mu)\in S_n\}$. During an S3 rollout, if $[x(t)]_\mu\in\partial S_n$ at some $t$, GoSafe switches to any $a'$ with $(a',[x(t)]_\mu)\in S_n$ and records $(a,\tilde x_0)$ in the fail set $E_f$; a continuity argument (Lemma 2 of the paper) shows that a trajectory cannot leave the certified region without first visiting a border state. If no intervention was needed, the pair is safe and $S_n=S_{n-1}\cup\{(a_n,\tilde x_{0,n})\}$ (eq. 7). Failed pairs are re-examined whenever the safe set has grown, because a prematurely stopped experiment need not have failed.
In words: each grid point stands for its whole cell; the margin $L_x\mu$ pays for the distance $\|x-[x]_\mu\|_1\le\mu$ to the cell's grid point, and the $2\mu$ in the definition of $\partial S$ flags every certified grid state that has a state with an uncertified grid point within reach. The argument needs continuous monitoring: with sampled measurements the state could cross a whole cell between two looks. GoSafeOpt closes exactly this gap with the motion bound $\Xi$ (Section 4).
Setting: finite $A$ and $X_\mu$; dynamics, objective and constraints Lipschitz with constants $L_x$, $L_a$ (appendix, Assumption 1); trajectory-minimum constraints; continuous monitoring with switching at the border as in the lemma above. 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$ (Theorem 1).
Under the same assumptions GoSafe converges with $\epsilon$-precision to the optimum within $\bar R^g_\epsilon(S_0)$ (Theorem 2), where the global reachability operator (the superscript $g$ is ours) adds to $R^c_\epsilon$ (here GoSafe's version on pairs: one common witness $(a',\tilde x_0')\in S$ with $g_i(a',\tilde x_0')-\epsilon-L_a\|a-a'\|_1-L_x(\|\tilde x_0-\tilde x_0'\|_1+\mu)\ge0$ for all $i$) 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)$. Corollary 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.
The paper states Theorem 2 "assuming the same as in Theorem 1", which bounds the RKHS norm only for the constraints. Its optimality argument also needs valid bounds for the objective: the appendix (Lemma 1) assumes the norm bound for all $i\in I$, including $h(\cdot,\cdot,0)=f$, and every S1/S2 phase must end, which holds if $\beta_n^2\gamma_{|I|n}$ grows sublinearly (see the remark on Theorem A.12 in Section 5).
In words: as long as the optimum's trajectory stays inside the largest region in state space that can be learned without risking a failure, the global optimum is found. If the optimal trajectory must cross uncertifiable territory, every attempt is interrupted and the optimum is not discoverable.
With GoSafe's $R^c_\epsilon$ on pairs as in the theorem and the trajectory set $\xi_{(0,\tilde x_0,a)}$ of Assumption 2.5,
The added pairs have a certified backup at their starting state and a trajectory that never touches the border of what the local stages can certify. Set $S^{(0)}=S_0$ and $S^{(j+1)}=R^g_\epsilon(S^{(j)})$; the sets only grow, and $\bar R^g_\epsilon(S_0)=\bigcup_{j\ge0}S^{(j)}$ is their limit. The optimum in Theorem 2 is $\max\{f(a,x_0):(a,x_0)\in\bar R^g_\epsilon(S_0)\}$: it is measured at the nominal initial state $x_0$, although exploration also uses other initial states.
Why GoSafe does not scale
Everything is paid in the size of $X_\mu$. A box of side length $R$ in $\mathbb R^s$ quantised so that $\|x-[x]_\mu\|_1\le\mu$ needs roughly $(sR/2\mu)^s$ grid points (Exercise 6.4). Stage S2 optimises an acquisition over $|A|\cdot|X_\mu|$ candidates, the GP must reduce its uncertainty over the joint space of dimension $d+s$ (its information gain grows with the dimension), and every S2 experiment starts the physical system in a new initial condition $\tilde x_0$, which is itself expensive or impossible on hardware. GoSafeOpt puts it bluntly: the active exploration of the state space "is infeasible for all but the simplest systems with low-dimensional state spaces", and cites LineBO's observation that dimension $d\gt3$ is already challenging for SafeOpt-type discretisations (Kirschner et al., ICML 2019). In practice GoSafe fixes $\tilde x_0=x_0$ during S3 (its eq. 8), terminates S2 early, and interrupts when $\inf_{y\in\partial S_n}\|x(t)-y\|_1\lt\eta$ for a sampling-rate-dependent threshold $\eta$. On the Furuta pendulum (two learned state-feedback gains $K_\theta,K_\alpha\in[0,1]$, measurements at 50 Hz) it ran S1 for 20 and S2 for 100 iterations before discovering a second safe area with a slightly better controller; the pole never dropped, while the constrained-BO baseline EIC incurred 10 and 7 failures in two runs.
4. GoSafeOpt: Backups from the Markov Property
GoSafeOpt (Sukhija, Turchetta, Lindner, Krause, Trimpe & Baumann, AIJ 2023) keeps the GP where SafeOpt-MC had it, on $h(a,i)$ over the parameter space only, and replaces the actively learned joint safe set by a set of backups that is collected passively. The key observation is a one-line consequence of the Markov property.
Fix $a$ and let $x(\cdot)$ be the trajectory from $x_0$. For $t_2\gt t_1\gt0$,
Because the closed-loop vector field $x\mapsto z\big(x,\pi^a(x)\big)$ is Lipschitz (for instance, $z$ and $\pi^a$ both Lipschitz; a Lipschitz $z$ alone is not enough, since the feedback can destroy uniqueness), the solution through $(t_1,x(t_1))$ is unique (Picard–Lindelöf, Section 2), so the trajectory started at $x(t_1)$ under $a$ is exactly the tail $\{x(t):t\ge t_1\}$ of the original one, independently of how the system arrived at $x(t_1)$. Therefore
where the inequality holds because $\xi_{(t_1,x(t_1),a)}\subseteq\xi_{(0,x_0,a)}$ (a minimum over a subset is at least the minimum over the set), and the last step is the safety of $(a,x_0)$. The independence of the past is what allows us to switch to $a$ at $x(t_1)$ even if $x(t_1)$ was reached under a completely different, untested policy.
Consequently, every rollout of a safe parameter $a$ hands us a whole family of backup pairs $\{(a,x(k\Delta t))\}_k$: after each experiment GoSafeOpt stores the discrete state measurements $R=\bigcup_k\{(a,x(k))\}$ in the set of backups $\mathcal B_{n+1}=\mathcal B_n\cup R$, initialised as $\mathcal B_0=\{(a,x_0):a\in S_0\}$. Corollary A.4 turns the proposition into a usable lower bound: for every $(a_s,x_s)\in\mathcal B_n$,
because $x_s$ lies on the trajectory from $x_0$ and $l_n(a_s,i)$ is a valid lower bound on the measured quantity $g_i(a_s,x_0)$. The bound is conservative (the paper notes that a GP over $(a,x)$ could tighten it if $g_i(a_s,x_s)$ were observable, which the Franka experiments of the paper in fact do, Appendix B), but it costs no extra experiment.
Local safe exploration (LSE)
LSE is SafeOpt-MC in parameter space. Lower and upper bounds are monotone, $l_n(a,i)=\max\{l_{n-1}(a,i),\ \mu_{n-1}(a,i)-\beta_n\sigma_{n-1}(a,i)\}$ and $u_n(a,i)=\min\{u_{n-1}(a,i),\ \mu_{n-1}(a,i)+\beta_n\sigma_{n-1}(a,i)\}$, with $l_0=0$ on $S_0$ for $i\in I_g$ and $-\infty$ elsewhere, $u_0=\infty$. The safe set, expanders, maximisers and the acquisition are
with $G_n=\{a\in S_n\mid e_n(a)\gt0\}$, $e_n(a)=|\{a'\in A\setminus S_n:\exists i\in I_g,\ u_n(a,i)-L_a\|a-a'\|\ge0\}|$, and $M_n=\{a\in S_n\mid u_n(a,0)\ge\max_{a'\in S_n}l_n(a',0)\}$ (Definitions D.1–D.2). LSE is declared converged when the connected region is learned to precision $\epsilon$ and has stopped growing (eq. 10):
Global exploration (GE) and the boundary condition
GE evaluates the most uncertain parameter that is neither certified nor known to trigger a backup,
where $E\subset A$ is the fail set. During the rollout, every state measurement is checked against the following rule.
The condition satisfies the three requirements the authors set: it is safe (Section 5), it is cheap, because the $l_n(a_s,i)$ are already computed offline for the safe-set update and only $\|x-x_s\|$ must be evaluated online, at cost $O(s)$ per backup (big-O notation: see Primer 0), and it works with discrete-time measurements thanks to the $\Xi$ term. On hardware the state arrived at 250 Hz and the condition was evaluated at 100 Hz.
- Input: domain $A$, kernel $k$, seed $S_0$, initial data $D_0$. Initialise the GP on $h(a,i)$, $E=\emptyset$, $X_{\rm Fail}=\emptyset$, $\mathcal B_0=\{(a,x_0):a\in S_0\}$.
- loop // the paper's Algorithm 4 writes "while $S_n$ expanding or $A\setminus(S_n\cup E)\neq\emptyset$"; read literally, that can stop before eq. 10 holds (with $S_0=A$ nothing can expand or be tested while $f$ is still unknown, and one iteration without growth does not mean the widths are below $\epsilon$), so here the stop test uses eq. 10, as the optimality proof assumes
- for every $(a,x)\in X_{\rm Fail}$: if the boundary condition no longer triggers at $x$, remove $a$ from $E$ and $(a,x)$ from $X_{\rm Fail}$ // new backups make old failures worth retrying; done before deciding that no GE candidate is left
- update $l_n(a,i)$, $u_n(a,i)$ for all $a\in A$, $i\in I$
- if LSE not converged (eq. 10): LSE step: pick $a_n$ by eq. 9; roll out; $\mathcal B\leftarrow\mathcal B\cup\{(a_n,x(k))\}_k$; $D\leftarrow D\cup\{(a_n,y)\}$; update $S$, $G$, $M$ by eq. 8
- else if $A\setminus(S_n\cup E)\neq\emptyset$: GE step: pick $a_n$ by eq. 11; roll out while checking the boundary condition at every measurement:
- if it triggers at $x(k)$: switch to $a_s^*$ (eq. 12), $E\leftarrow E\cup\{a_n\}$, $X_{\rm Fail}\leftarrow X_{\rm Fail}\cup\{(a_n,x(k))\}$ // experiment marked failed; no data added
- if it never triggers: $a_n$ is safe: $\mathcal B\leftarrow\mathcal B\cup\{(a_n,x(k))\}_k$, $D\leftarrow D\cup\{(a_n,y)\}$, $S\leftarrow S\cup\{a_n\}$, $C(a_n,i)\leftarrow C(a_n,i)\cap[0,\infty)$ for $i\in I_g$ (with $C_n(a,i)=[l_n(a,i),u_n(a,i)]$ this raises the lower bound to $\max\{l_n(a_n,i),0\}$); return to LSE to explore the new region
- else stop // LSE has converged and no untested parameter is left outside $S_n\cup E$
- return $\hat a_n=\arg\max_{a\in S_n}l_n(a,0)$
Three practical modifications are used in the experiments; the paper's Section 4.3 states that the first two keep the safety guarantee, and the third comes from its Appendix B. (i) LSE runs for a fixed $n_{\rm LSE}$ steps before GE gets $n_{\rm GE}$ attempts, which allows jumping between regions early; the toy example of the paper's Appendix C shows the trade-off ($n_{\rm LSE}=5$ converged faster than 10, but with $n_{\rm LSE}=1$ and $n_{\rm GE}=10$ global exploration also failed and the run got stuck at a bad optimum). (ii) The boundary condition can be restricted to interior and marginal subsets of the backups (Definition 4.5, states with $l_n\ge\eta_u$ resp. $\eta_l\le l_n\lt\eta_u$, checked with distance tolerances $d_u\gt d_l$); this is faster and more conservative, and the paper states explicitly that it costs the optimality guarantee. It is safe only for suitably chosen tolerances (the paper: "we can derive appropriate values for $\eta_u$, $d_u$, respectively $\eta_l$, $d_l$ to guarantee safety"); a sufficient choice is $L_x(d_u+\Xi)\le\eta_u$ and $L_x(d_l+\Xi)\le\eta_l$, which makes every accepted neighbourhood satisfy the original condition. (iii) When the constraint values $g_i(a,x(k))$ along the rollout can be measured, as on the Franka arm, a GP over $(a,x)$ provides less conservative bounds $l_n(a_s,x_s,i)$, thinned by subset selection once it exceeds $n_{\max}=1000$ points: a random subset of the stored points is kept, favouring points with small lower bounds, which keeps inference cheap but changes the posterior, so the confidence bounds must be valid for the data actually kept.
5. Safety and Optimality Guarantees
In words: neither the LSE experiments (which only use certified parameters) nor the GE experiments (which test uncertified ones under the boundary condition) ever violate $\bar g_i(x(t))\ge0$, jointly for all $n$, on an event of probability $1-\delta$. The event is the one on which the GP confidence bounds hold simultaneously for all $n$ and $a$, which is where $\beta_n$ enters and where a heuristic $\beta$ breaks the theorem (Section 6). Assumptions 2.4 and 2.5 are what make the GE part work: without a motion bound the state could leave the certified balls between two looks, and without trajectory-minimum constraints a safe suffix would not make the whole experiment safe.
The proof separates the two stages. LSE inherits safety from SafeOpt-MC. For GE the argument is a chain of five small lemmas around one working hypothesis, Hypothesis A.1: with probability at least $1-\delta$, for all $n$ and $i\in I_g$, (A.1) $g_i(a,x_0)\ge0$ for all $a\in S_n$ and (A.2) $l_n(a,i)\le g_i(a,x_0)\le u_n(a,i)$ for all $a\in A$. The walkthrough below goes through the certificate step by step; the collapsible gives the lemmas with every inequality justified.
Lemma A.2 ($\Xi$-tolerance). Let Assumptions 2.4 and 2.5 hold and let $k_+\ge k_-\ge0$. If for every integer $k\in[k_-,k_+]$ there is an $a_s\in A$ with $g_i(a_s,x(k))\ge L_x\Xi$ for all $i\in I_g$, then $\bar g_i(x(t))\ge0$ for all $t\in[k_-\Delta t,(k_++1)\Delta t]$.
Proof. The $k$-th measurement is $x(k)=x(k\Delta t)$. For $t\in[k\Delta t,(k+1)\Delta t]$,
by Lipschitz continuity in the state (Assumption 2.2) and the motion bound (Assumption 2.4). Rearranging and using the hypothesis,
and since $x(t)$ lies on the trajectory that starts at $x(t)$ under $a_s$, $\bar g_i(x(t))\ge g_i(a_s,x(t))\ge0$ (Assumption 2.5). Covering $[k_-\Delta t,(k_++1)\Delta t]$ by the intervals $[k\Delta t,(k+1)\Delta t]$ finishes the proof. $\square$
Lemma A.5 (safe before the trigger). Under the assumptions of Theorem 4.1 and Hypothesis A.1: if the boundary condition triggers at step $k^*\gt0$ during GE, then $\bar g_i(x(t))\ge0$ for all $t\le k^*\Delta t$ with probability at least $1-\delta$.
Proof. For $k\lt k^*$ the condition did not trigger, so some $(a_s,x_s)\in\mathcal B_n$ satisfies $l_n(a_s,i)\ge L_x(\|x(k)-x_s\|+\Xi)$ for all $i$ (A.4). Then
Lemma A.2 with $k_-=0$, $k_+=k^*-1$ gives safety on $[0,k^*\Delta t]$. $\square$
Lemma A.6 (safe after the trigger). If the condition triggers at $k^*\ge0$ and the backup $a_s^*$ of eq. 12 is applied, then $\bar g_i(x(t))\ge0$ for all $t\ge k^*\Delta t$ with probability at least $1-\delta$.
Proof. It suffices that $g_i(a_s^*,x(k^*))\ge0$: then the tail trajectory under $a_s^*$ has non-negative minimum by definition of $g_i(a_s^*,x(k^*))$. For $k^*=0$ the state is $x(0)=x_0$, and every parameter stored in $\mathcal B_n$ is known to be safe from $x_0$ (it comes from $S_0$, from an LSE rollout of a certified parameter, or from a GE rollout that did not trigger, Lemma A.7); so whichever pair eq. 12 selects, $g_i(a_s^*,x_0)\ge0$, even if its score is negative. For $k^*\gt0$ take the pair $(a_s,x_s)\in\mathcal B_n$ that passed the test at step $k^*-1$:
So at least one pair in $\mathcal B_n$ has $\min_i l_n(a_s,i)-L_x\|x(k^*)-x_s\|\ge0$, hence the maximum in eq. 12 is non-negative, and the chosen $a_s^*$ satisfies $g_i(a_s^*,x(k^*))\ge0$ for all $i$. $\square$
Lemma A.7 (no trigger means the new parameter is safe). If a GE experiment with parameter $a_{\rm GE}$ completes without triggering, then $g_i(a_{\rm GE},x_0)\ge0$ for all $i$ with probability at least $1-\delta$.
Proof. Suppose $\bar g_i(x(t))\lt0$ for some $t\in[k\Delta t,(k+1)\Delta t]$. The condition did not trigger at $k$, so some $(a_s,x_s)$ has $l_n(a_s,i)-L_x(\|x_s-x(k)\|+\Xi)\ge0$, hence $g_i(a_s,x(k))\ge L_x\Xi$ by the chain of Lemma A.5, and Lemma A.2 gives $\bar g_i(x(t))\ge0$, a contradiction. Thus the whole trajectory of $a_{\rm GE}$ from $x_0$ satisfies $\bar g_i\ge0$, i.e. its minimum $g_i(a_{\rm GE},x_0)\ge0$. $\square$
Corollary A.8 and Lemma A.9. Every GE experiment either triggers (safe before by A.5 and after by A.6) or does not (safe by A.7). It remains to show that Hypothesis A.1 holds for all $n$, by induction. Base: $S_0$ is safe by Assumption 2.1, $l_0=0$ on $S_0$ and $-\infty$ elsewhere, $u_0=\infty$, so (A.2) holds. Step: during LSE the GP bounds $\mu_n\pm\beta_n\sigma_n$ contain $g_i(a,x_0)$ with probability $1-\delta$ (SafeOpt-MC), and taking $\max$ with a valid lower bound or $\min$ with a valid upper bound keeps validity; during GE the only change is $l_n(a,i)\leftarrow\max\{l_n(a,i),0\}$ for a parameter that Lemma A.7 has shown to satisfy $g_i(a,x_0)\ge0$. For the safe set: GE adds only such parameters; LSE adds $a'$ only if some $a\in S_{n-1}$ has $l_n(a,i)-L_a\|a-a'\|\ge0$, whence $g_i(a',x_0)\ge g_i(a,x_0)-L_a\|a-a'\|\ge l_n(a,i)-L_a\|a-a'\|\ge0$. $\square$
Theorem 4.1 follows: LSE only queries $S_n$, which is safe by A.9, and GE is safe by A.8. Note that the whole chain is deterministic given Hypothesis A.1; the probability $1-\delta$ enters once, through the confidence bounds.
Optimality
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')$.
Theorem 4.3. 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).$$
In words: once the island containing $a^*$ has been entered (by a successful GE experiment), LSE finds its $\epsilon$-optimum in finite time. The theorem does not say that every island will be entered; that is the discoverability condition, which Lemma A.18 makes concrete.
The proof is the SafeOpt-MC convergence argument restated for the seed $S$. Finiteness comes from the SafeOpt-MC sample budget, which is a sufficient worst case, not a formula for $n^*$. Let $N$ be the smallest integer with (in our convention, band $\mu\pm\beta_n\sigma$)
the paper uses it as an upper bound on the first convergence iteration, $n^*\le N$ (up to the indexing of the convergence test), and the actual stopping time can be much smaller. The paper writes $n^*$ for both quantities, and $\beta_{N}$ instead of $\beta_{N}^2$ because its $\beta$ multiplies $\sigma$ as $\beta^{1/2}$. It also writes $|\bar R^c_0(S)|$. That is the same for a single constraint, but with several constraints the per-constraint update eq. 8 can certify more than $\bar R^c_0(S)$ (Section 1), and SafeOpt-MC's counting argument (Lemma 10) needs $S_n\subseteq\bar R_0(S)$, so $|\bar R_0(S)|$ is the count its proof supports. The argument then combines monotonicity of the safe set (Proposition A.13: $S_n\subseteq S_{n+1}$, since LSE only adds and GE adds only successful parameters), the fact that every newly added region $A'=S_{n+1}\setminus S_n$ is explored to its own closure in finite time (Lemma A.14), and the sandwich $l_n(a^*,0)\le f(a^*)\le u_n(a^*,0)$ with $w_n(a^*,0)\lt\epsilon$ at convergence (eq. 10 bounds the widths on $G_n\cup M_n$, and once $a^*\in S_n$ it lies in $M_n$, because $u_n(a^*,0)\ge f(a^*)\ge f(a)\ge l_n(a,0)$ for every certified, hence safe, $a$): if $f(\hat a_n)\lt f(a^*)-\epsilon$ then $l_n(\hat a_n,0)\le f(\hat a_n)\lt f(a^*)-\epsilon\le u_n(a^*,0)-\epsilon\le l_n(a^*,0)$, contradicting the choice of $\hat a_n$ as the maximiser of $l_n(\cdot,0)$.
Why the product must grow sublinearly. A finite $N$ exists as soon as the ratio $N/(\beta_N^2\gamma_{|I|N})$ can exceed the fixed right-hand side, which is guaranteed if $\beta_N^2\gamma_{|I|N}/N\to0$, written $\beta_N^2\gamma_{|I|N}=o(N)$. Sublinear $\gamma_N$ alone is not enough, because $\beta_N$ grows with the information gain: for the multiplier $B+4\sigma\sqrt{\gamma+1+\ln(1/\delta)}$, $\beta_N^2$ is about $16\sigma^2\gamma_N$ once $\gamma_N$ is large, so $\gamma_N=N^{3/4}$ (sublinear) gives a product of order $N^{3/2}$ and the ratio tends to $0$: the budget is never met. For the squared-exponential kernel $\gamma_N$ grows only polylogarithmically, and the product is sublinear.
6. Experiments and the β Caveat
GoSafeOpt was evaluated on a Franka Emika Panda arm with an operational-space impedance controller. The state is the six-dimensional end-effector position and velocity (seven with the path-progress variable), far beyond what GoSafe's discretised state space can handle, so the baselines are SafeOpt and its particle-swarm variant SafeOptSwarm. Two simulation tasks (MuJoCo) and one hardware task were run:
| Task | Parameters | Runs | Safety | Outcome |
|---|---|---|---|---|
| 8-D: reach a target (6 states + 2 LQR weights $(q_c,r)\in[2,6]\times[-3,3]$) | $\sigma$-multiplier 4, Matérn 3/2 kernel, $\epsilon=0.1$, $n_{\rm LSE}\le30$, $n_{\rm GE}\le10$ | 20 runs, 200 iterations | GoSafeOpt 99.9 % on average, SafeOpt 100 %; the failures occurred in LSE | finds the disconnected region; optimum within 0.007 of the grid-search optimum; SafeOpt cannot significantly improve on the seed |
| 11-D: path following (7 states + 4 parameters $q_c,r,\kappa_d,a_\rho$) | $\sigma$-multiplier 3, SE kernel, $\epsilon=0.1$, $n_{\rm LSE}\le100$, $n_{\rm GE}\le10$ | 20 runs, 200 iterations | 100 % for both GoSafeOpt and SafeOptSwarm | considerably better objective than SafeOptSwarm; EIC matches the objective but averages more than 15 unsafe evaluations |
| Hardware: path following next to a wall, $\alpha_{x,y,z}\in[0,1.2]^3$ scaling the manufacturer's impedance gains, seed $a_0=(0.6,0.6,0.6)$ | $\sigma$-multiplier 3, SE kernel, $\epsilon=0.01$, $n_{\rm LSE}\le20$, $n_{\rm GE}\le5$, state at 250 Hz, boundary condition at 100 Hz | 3 runs, 50 iterations | 100 % for both GoSafeOpt and SafeOptSwarm; backups were triggered during GE | better tracking than SafeOptSwarm and than the manufacturer's controller ($\alpha=1$); the optimum found has $\alpha_x=\alpha_y=1.2$, even though a disconnected region cannot be proven to exist |
The hyperparameters were chosen with the simulator (kernel parameters, $\beta_n$, distance metric of the boundary condition) and fine-tuned with controlled safe experiments on the hardware. The paper itself flags this as the gap between theory and practice and points to meta-learned priors and to work on that gap: Fiedler et al., AAAI 2021 (rigorous yet usable bounds) and Berkenkamp, Schoellig & Krause, JMLR 2019 (BO with unknown hyperparameters).
Both papers use constant confidence multipliers: GoSafe reports "$\beta_n\equiv3$" on the Furuta pendulum (in GoSafe's own $\beta_n^{1/2}$ notation this would be a $\sigma$-multiplier of $\sqrt3$; the TMLR paper below reads it as a multiplier of 3; either way it is a constant), and GoSafeOpt's hyperparameter table lists a $\sigma$-multiplier ($\beta_n^{1/2}$ in its notation) of 4 for the 8-D task and 3 for the 11-D and hardware tasks. Fiedler, Menn, Kreisköther & Trimpe, TMLR 2024 document exactly this practice ("$\beta_t\equiv3$ in […] Baumann et al. (2021) or $\beta_t\equiv4$ in Sukhija et al. (2022)"; 2022 is the arXiv year of the GoSafeOpt paper cited here as Sukhija et al. 2023) and state that "using such heuristics instead of evaluating $\beta_t$ invalidates all theoretical safety guarantees" and "can actually lead to safety violations". Theorems 4.1 and 4.3 hold for the theoretical $\beta_n$ of SafeOpt-MC, which depends on $B$, the information gain and $\delta$; the TMLR paper notes that such bounds tend to be conservative, which "can completely prevent exploration", and that is why implementations fall back to constants.
The 99.9 % average safety of the 8-D simulation is consistent with this: the failures arose in LSE, i.e. in plain SafeOpt with a heuristic $\beta$, not in the global stage, and the paper's own remark is that a larger $\beta_n$ would avoid them. Note also that the kernel was chosen from observed behaviour (a Matérn 3/2 kernel for the 8-D task, because $f$ and $g_i$ looked non-smooth), so the RKHS-norm bound $\|h\|_k\le B$ in that kernel's space was an assumption nobody could check. Module 5 gives the two repairs: evaluate the real $\beta$ (Real-$\beta$-SafeOpt) or make the safe set independent of the GP altogether (LoSBO, which only needs a Lipschitz constant and a noise bound). Nothing in the GE argument prevents the second repair: if $l_n(a_s,i)$ were replaced by a deterministic Lipschitz-and-noise-bound lower bound as in LoSBO, the backup certificate would hold deterministically (under LoSBO's bounded-noise assumption and with correct $L_x$ and $\Xi$). That combination is an observation of these notes, not a published result.
7. Safe Exploration in MDPs: SafeMDP, SNO-MDP, ActSafe
GoSafe and GoSafeOpt model safety as a function of the policy parameter. A second line of work, whose GP-based form starts with Turchetta, Berkenkamp & Krause, NeurIPS 2016 (building on the ergodicity idea of Moldovan & Abbeel, ICML 2012), models safety as a function of the state and exploits known dynamics to move only through certified states. The two views meet in the notion of ergodicity: a state is only worth visiting if one can also get back.
SafeMDP
The environment is a finite, deterministic MDP (see Primer E) $\langle\mathcal S,\mathcal A(\cdot),f(s,a),r(s)\rangle$ with a known transition function $f$ and an unknown safety feature $r(s)$ that must stay above a threshold $h$ at every visited state (in this subsection $f$ is the transition function, $r$ the safety feature and $h$ its threshold, not the objective, a reward or the selector of Section 2). The feature has bounded RKHS norm and is $L$-Lipschitz in a metric $d$ on $\mathcal S$, so a GP gives bounds $l_t(s)\le r(s)\le u_t(s)$ (contained sets $C_t=C_{t-1}\cap Q_t$ with $C_0=[h,\infty)$ on $S_0$). Three operators describe what an explorer may do:
with $R^{\rm ret}_n(S,\bar S)=R^{\rm ret}(S,R^{\rm ret}_{n-1}(S,\bar S))$, starting from $R^{\rm ret}_0(S,\bar S)=\bar S$ (so $R^{\rm ret}_1=R^{\rm ret}$, the paper's base case, and $R^{\rm ret}_n$ adds the states of $S$ that can return to $\bar S$ within $n$ steps without leaving $S$), and the closure $\bar R^{\rm ret}(S,\bar S)=\lim_n R^{\rm ret}_n(S,\bar S)$, reached after finitely many steps on a finite state space: all states from which $\bar S$ can be reached by a path that stays inside $S$. The best any algorithm can do is $R_\epsilon(S)=R^{\rm safe}_\epsilon(S)\cap R^{\rm reach}(S)\cap\bar R^{\rm ret}(R^{\rm safe}_\epsilon(S),S)$ iterated to its closure $\bar R_\epsilon(S_0)$ (eq. 4).
SafeMDP then samples the most uncertain expander, $s_t=\arg\max_{s\in G_t}w_t(s)$ with $G_t=\{s\in\hat S_t:\ g_t(s)\gt0\}$ and $g_t(s)=|\{s'\in\mathcal S\setminus S_t:\ u_t(s)-L\,d(s,s')\ge h\}|$, and travels there along the shortest safe path (Dijkstra through $S_t$, as in the paper's Algorithm 1; Lemma 2 guarantees such a path between any two states of $\hat S_t$, but not necessarily one that stays inside $\hat S_t$). Theorem 1: under $\|r\|_k^2\le B$, noise that is zero-mean conditioned on the history (see Primer C) and uniformly bounded by $\sigma$, $L$-Lipschitz $r$, a non-empty safe seed ($r(s)\ge h$ on $S_0$) whose states can reach each other inside $S_0$, and $\beta_t=2B+300\gamma_t\log^3(t/\delta)$ in the Srinivas convention (band $\mu\pm\beta_t^{1/2}\sigma$, squared-norm bound), every visited state satisfies $r(s)\ge h$ with probability at least $1-\delta$, and with $t^*$ the smallest integer such that $t^*/(\beta_{t^*}\gamma_{t^*})\ge C|\bar R_0(S_0)|/\epsilon^2$, $C=8/\log(1+\sigma^{-2})$, there is $t_0\le t^*$ with $\bar R_\epsilon(S_0)\subseteq\hat S_{t_0}\subseteq\bar R_0(S_0)$: safe and complete exploration. Action-dependent safety features are handled by inserting an "action state" between $s$ and $f(s,a)$ (collapsible below).
Draw one vertex per state and a directed edge $s\to f(s,a)$ for every available action $a\in\mathcal A(s)$. A safe path is a sequence of edges whose vertices are all certified. Dijkstra's algorithm is a standard routine that returns a path of minimum total length between two vertices when all edge lengths are nonnegative (with unit lengths, breadth-first search does the same); only this input-output behaviour is needed here.
Action states. If safety depends on the action, $r(s,a)$, SafeMDP replaces each edge $s\xrightarrow{a}f(s,a)$ by two edges $s\to s_a\to f(s,a)$ through a new vertex $s_a$ that carries the value $r(s,a)$ and whose only transition leads to $f(s,a)$. A path in the new graph is then safe exactly when every state visited and every action taken along the original path is safe. Example with threshold $h=0$: if $r(s)=r(f(s,a))=0.5$ but $r(s,a)=-0.2$, the action state $s_a$ is unsafe, so the certified paths avoid taking $a$ in $s$ although both states are safe. The algorithm runs unchanged on the enlarged MDP; its theorem applies if the safety feature on the enlarged state set satisfies the same assumptions (RKHS bound, Lipschitz constant, safe seed).
Goal-oriented and reward-aware variants
GoOSE (Turchetta, Berkenkamp & Krause, NeurIPS 2019) observes that learning the whole safe set is wasteful. It wraps any unsafe interactive-ML oracle (a BO algorithm, an MDP planner): the oracle proposes $x^\star_i$ inside an optimistic safe set, and GoOSE learns about the safety of that decision only, using a pessimistic operator $p_t(S)=\{x\mid\exists z\in S:\ l_t(z)-L\,d(x,z)\ge0\}$ and an optimistic one $o_t(S)=\{x\mid\exists z\in S:\ u_t(z)-L\,d(x,z)-\epsilon\ge0\}$, each intersected with the ergodicity operator $R^{\rm ergodic}(S,\bar S)=\bar R^{\rm reach}(\bar S)\cap\bar R^{\rm ret}(S,\bar S)$ of SafeMDP. Its Theorem 1 and Corollary 1 (box below; the operators are written out in the collapsible) keep SafeMDP's safety and show that, after finitely many safety queries, the oracle makes the decisions it would have made had it been given, from the start, a safe set between the two reachable benchmarks $\tilde R_\epsilon(S_0)\subseteq\tilde R_0(S_0)$ (the analogues of SafeMDP's $\bar R$). The pessimistic/optimistic pair reappears in SageMPC and ActSafe below.
For an allowed set $U$ and return target $B$, put $E(U,B)=\bar R^{\rm reach}(B)\cap\bar R^{\rm ret}(U,B)$ using the graph operators above. For $v=p_t$ or $v=o_t$, start at $U_0=B$ and iterate $U_{j+1}=v(U_j)\cap E(v(U_j),B)$. Their limiting sets are $\tilde P_t(B)$ and $\tilde O_t^\epsilon(B)$. These are the paper's repeated certification-and-ergodicity operations at a fixed data index $t$.
The true-function benchmark has a separate seed-preserving definition: $V_\epsilon(U)=U\cup\{x:\exists z\in U, q(z)-\epsilon-Ld(x,z)\ge0\}$, $R_\epsilon(U)=V_\epsilon(U)\cap E(V_\epsilon(U),U)$. Starting at $U_0=S_0$, repeatedly apply $R_\epsilon$ and take the union of the increasing sets; this is $\tilde R_\epsilon(S_0)$. Here the return target is the current set $U$, and the union preserves its already safe members.
GoOSE initializes $\bar S^p_0=S_0$, then sets $\bar S^p_t=\tilde P_t(\bar S^p_{t-1})$ and $\bar S^{o,\epsilon}_t=\tilde O_t^\epsilon(\bar S^p_{t-1})$. The optimistic operator subtracts $\epsilon$ whereas the pessimistic operator does not: these are not simply the pointwise sets $\{u_t\ge0\}$ and $\{l_t\ge0\}$.
In words: normally the optimistic set contains the pessimistic one. The middle inclusion reverses this only at the time $t$ the theorem provides: the optimistic operator works with the margin $u_t-\epsilon$, and by then every decision that could still be safe with that margin has been certified pessimistically. The seed's connectivity lets the agent travel between certified decisions and back.
SNO-MDP (Wachi & Sui, ICML 2020) adds a GP-modelled reward to SafeMDP and proceeds stepwise: first expand the pessimistic safe region $X^-_t$ with SafeMDP's operators until $\max_{s\in G_t}w_t(s)\lt\epsilon_g$, then optimise the cumulative reward inside it with optimism in the face of uncertainty (the upper confidence bound $\mu^r+\alpha_t^{1/2}\sigma^r$ of the reward GP serves as reward; see Primer E). Its guarantees (box below) are safety in both stages, completeness of the pessimistic region, and $\epsilon_V$-near-optimality of the return at all but finitely many time steps, with $\epsilon_V=V_{\max}(\Delta_g+\Sigma^r_{t^*}/R_{\max})$; here $R_{\max}$ bounds the reward, $V_{\max}=R_{\max}/(1-\gamma)$ (see Primer E) with $\gamma$ the discount factor (not the information gain), $\Delta_g$ is the failure probability allowed for the safety GP and $\Sigma^r_{t^*}$ is a reward-uncertainty term that shrinks as $t^*$ grows. The early-stopping rule ES$^2$ halts safety exploration once the optimal policy of an auxiliary MDP on the optimistic safe region (optimistic reward outside $X^-_t$, pessimistic inside) never leaves the pessimistic region, and near-optimality is kept. Its Theorem 1 mixes conventions ($\|g\|_k^2\le B_g$ with a Chowdhury–Gopalan-type $\beta_t$), as StageOpt does.
- (Thm. 1) With probability at least $1-\Delta_g$, every visited state satisfies $g(s_t)\ge h$, and $\bar R_{\epsilon_g}(S_0)\subseteq X^-_{t_0}\subseteq\bar R_0(S_0)$ for some $t_0\le t^*$.
- (Thm. 2) With high probability, $V^{\pi_t}(s_t,b^r_t,b^g_t)\ge V^*(s_t)-\epsilon_V$ at all but at most $t^*$ time steps. Here $b^r_t,b^g_t$ are the two GP posteriors (the agent's beliefs), $V^*$ is the optimal value when the agent is restricted to $\bar R_{\epsilon_g}(S_0)$, and $\Sigma^r_t=\tfrac12\sqrt{C_r\alpha_t\Gamma^r_t/t}$ with $C_r=8/\log(1+\sigma_r^{-2})$.
- (Thm. 3) With ES$^2$ the same holds with $t^*$ replaced by the first time $\tilde t$ at which $Y_t\subseteq X^-_t$. Here $Y_t=\{f(s,\pi_y(s)):\ s\in X^-_t\}$ collects the successors of pessimistically safe states under an optimal policy $\pi_y$ of the auxiliary MDP on $X^+_t$, whose reward is $\mu^r+\alpha^{1/2}\sigma^r$ outside $X^-_t$ and $\mu^r-\alpha^{1/2}\sigma^r$ inside.
Continuous states, policies and dynamics models
SageMPC (Prajapat, Köhler, Turchetta, Krause & Zeilinger, IEEE TAC 2025) moves the SafeMDP idea to continuous domains with nonlinear dynamics. The constraint $q(x)\ge0$ is a state function in an RKHS; the pessimistic and optimistic sets sandwich the true safe set $S^\star=\{x:\ q(x)\ge0\}$ with high probability, $S^p_n=\{x:\ l_n(x)\ge0\}\subseteq S^\star\subseteq S^o_n=\{x:\ u_n(x)\ge0\}$; any sampling rule that picks $x_{n+1}\in S^p_n$ with $w_n(x_{n+1})\ge\epsilon$ terminates after at most $n^\star$ samples, the largest integer with $n^\star/(\beta^2_{n^\star}\gamma_{n^\star})\le C_1/\epsilon^2$, $C_1=8/\log(1+\varsigma^{-2})$ with $\varsigma$ the sub-Gaussian noise level (Theorem 1, which assumes that $\beta_n^2\gamma_n$ grows sublinearly; SageMPC writes the band as $\mu\pm\sqrt{\beta_n}\,\sigma$, so its $\beta_n$ is our $\beta_n^2$), a sample complexity with no discretisation-size factor. Samples are reached through safe, returnable trajectories computed by an optimal-control problem with a known terminal set (Assumption 3), and SageMPC adds a Lipschitz bound, goal-directed exploration and receding-horizon replanning while keeping the guarantees. It complements the learning-based MPC of Koller et al., CDC 2018 (Module 11), which learns the dynamics instead of the constraint.
What it does not say: the theorem counts observations; it does not show that the system can reach them. Driving the system to $x_{n+1}$ and back safely is the job of the control layer, which needs known dynamics and terminal sets that are pessimistically safe, nondecreasing, control invariant and safely traversable (their Assumption 3).
ActSafe (As, Sukhija, Treven, Sferrazza, Coros & Krause, ICLR 2025) lifts the safe-set expansion from parameters or states to policies $\pi\in\Pi$ of a constrained MDP with unknown dynamics $f^*$ (RKHS dynamics, i.i.d. Gaussian transition noise, Lipschitz $f^*$ and cost $c$). The constraint is on the expected cumulative cost over the horizon $T$, $J_c(\pi,f)=\mathbb E\big[\sum_{t=0}^{T-1}c(s_t,a_t)\big]\le d$. A well-calibrated model set $M_n=M_{n-1}\cap Q_n$ defines the pessimistic cost $P_n(\pi)=\max_{f\in M_n}J_c(\pi,f)$ and the expansion
where $D(\pi,\pi')$ bounds the cost difference of two policies through the Lipschitz constants $L_c$, $L_f$ and the noise level; it is the policy-space analogue of $L_a\|a-a'\|$. During expansion ActSafe chooses $\pi_n,f_n=\arg\max_{\pi\in S_n,f\in M_n}\mathbb E[\sum_t\|\sigma_{n-1}(\hat s_t,\pi(\hat s_t))\|]$, where $\hat s_t$ are the states predicted by the candidate model $f$ under $\pi$ (optimistic about the dynamics, pessimistic about the constraint, with the epistemic uncertainty as intrinsic reward; see Primer E), then exploits. Theorem 4.8 (box below) guarantees that every deployed policy has expected cost at most $d$, a statement about expectations rather than about every realised trajectory, and that after a finite number of episodes a pessimistic recommendation is $\epsilon$-optimal within the set $R^H_\epsilon(S_0)$ reachable in $H$ certified expansion rounds. Here $\beta_n$ multiplies $\sigma_n$ directly, as in our convention. A practical variant with a learned latent model handles visual control.
Assumptions. $f^*$ is $L_f$-Lipschitz, the cost $c\in[0,C_{\max}]$ is $L_c$-Lipschitz and all policies are continuous (Assumption 4.1); the transition noise is i.i.d. $\mathcal N(0,\sigma^2I)$ with $\sigma\gt0$ (4.2); a nonempty seed $S_0$ of policies with $J_c\le d$ is known (4.3); every coordinate $f^*_j$ lies in an RKHS with $\|f^*_j\|_k\le B$ and a bounded kernel (4.5). Rewards are bounded by $R_{\max}$.
Calibration and certificate. With $z=(s,a)$, $Q_n=\{f:\ |f_j(z)-\mu_{n,j}(z)|\le\beta_n\sigma_{n,j}(z)\text{ for all }z,j\}$ is a set of whole dynamics functions, and under 4.5 a GP achieves $\Pr(f^*\in Q_n\ \forall n\ge0)\ge1-\delta$ (Lemma 4.6). On this event $f^*\in M_n$, so $J_c(\pi,f^*)\le P_n(\pi)$ for every policy. The distance
with $\Delta_t:=\pi'(s_t)-\pi(s_t)$, an expectation over trajectories of $\pi'$ on the true system, satisfies $J_c(\pi,f^*)-J_c(\pi',f^*)\le D(\pi,\pi')$ (Lemma A.3). Hence $P_n(\pi')+D(\pi,\pi')\le d$ gives $J_c(\pi,f^*)\le J_c(\pi',f^*)+D(\pi,\pi')\le P_n(\pi')+D(\pi,\pi')\le d$, which is why the expansion rule is safe.
Conclusions, jointly with probability at least $1-\delta$: (i) $J_c(\pi_n,f^*)\le d$ in every episode; (ii) let $R^0_\epsilon(S_0)=S_0$, $R^{h+1}_\epsilon(S_0)=R^h_\epsilon(S_0)\cup\{\pi:\ \exists\pi'\in R^h_\epsilon(S_0),\ J_c(\pi',f^*)+D(\pi,\pi')\le d-\epsilon\}$, $C=(1+\sqrt{d_s})\max\{C_{\max},R_{\max},\sigma_0\}$ with $d_s$ the state dimension and $\sigma_0$ a bound on the model's prior standard deviation, and let $n^*$ be the smallest integer with
then for all $n\ge n^*$ the pessimistic recommendation $\tilde\pi_n=\arg\max_{\pi\in S_n}\min_{f\in M_n}J_r(\pi,f)$ satisfies $J_r(\tilde\pi_n,f^*)\ge\max_{\pi\in R^H_\epsilon(S_0)}J_r(\pi,f^*)-\epsilon$. Such an $n^*$ exists if $\beta_n^4\gamma_n$ grows sublinearly.
In words: the worst plausible model cannot underestimate the true expected cost, and $D$ transfers a certificate from a certified policy to a nearby one. $H$ counts certification rounds between policies, not time steps. The theorem covers the idealised GP version; the practical latent-model variant does not inherit it.
SOOPER (Wendl, As, Prajapat, Pollak, Coros & Krause, ICLR 2026) is the closest relative of GoSafeOpt's boundary condition in deep RL. It assumes a pessimistic policy prior $\hat\pi$ (from offline data or a simulator; a truncated Gaussian policy with positive variance, i.e. a Gaussian restricted to the allowed actions and renormalised, see Primer C) that satisfies the constraint for all plausible models $f\in F_0$ (Assumption 4), and an uncertainty-penalised cost critic $Q^{\hat\pi}_{c,n}(s,a)$ that upper-bounds the prior's cost-to-go. The online rule
keeps the exploring policy while the realised discounted cost so far plus a pessimistic estimate of what the fallback would still accrue stays under the budget, and switches to the prior otherwise ($\gamma$ is the discount factor here, not the information gain). Operationally it is a proposal-and-filter rule: at step $t$ a candidate $a_t\sim\pi_n(\cdot\mid s_t)$ is drawn and executed only if $\Phi\lt d$; otherwise an action is drawn from $\hat\pi$, and $\hat\pi$ is kept for the rest of the episode (the safety proof needs this absorbing fallback). $Q^{\hat\pi}_{c,n}(s_t,a_t)$ is the pessimistic cost of taking $a_t$ now and following $\hat\pi$ afterwards, so the decision depends on $s_t$, the accumulated cost $c_{\lt t}$, the time $t$ and the fallback flag, not on $s_t$ alone. The constraint is on the expected discounted cost, $J_c(\pi)=\mathbb E\big[\sum_t\gamma^tc(s_t,a_t)\big]\le d$, and Theorem 1 states that, with probability $1-\delta$ over the model learning, the switched policy $\bar\pi_n$ satisfies it in every episode; it is not a bound on the cost of every realised trajectory. Because the budget is cumulative, the certificate tracks the accumulated cost, which is exactly the case GoSafeOpt excluded in Assumption 2.5. Optimistic planning in the model then yields cumulative regret $O(\Gamma_{N\log N}^{7/2}\sqrt N)$ with $\Gamma$ the maximum information gain (Theorem 2, box below), a heavy information-gain dependence worth noticing. The regret bound rests on two conditions that a merely robustly safe prior does not supply. First, an optimal policy is strictly feasible, $J_c(\pi^*_c)\lt d$. Second, the prior is statewise no costlier than that optimum under the true dynamics, $V_c^{\hat\pi}(s)\le V_c^{\pi^*_c}(s)$ for all $s$ (part of Assumption 4). The proof uses them to show that running $\pi^*_c$ under the switching rule falls back to $\hat\pi$ less and less as the model uncertainty shrinks; without them the fallback could keep cutting the optimal policy short. The method is validated on Safety-Gym and RWRL tasks and on a real RC race car.
Assumptions. i.i.d. Gaussian transition noise $\mathcal N(0,\sigma^2I)$ (Assumption 1); Lipschitz dynamics, reward and cost with $r\in[0,R_{\max}]$, $c\in[0,C_{\max}]$, $\gamma\in(0,1)$ (2); dynamics in an RKHS with component-wise norm bound $B$ and kernel bounded by $k_{\max}$ (3); a prior $\hat\pi$ as above that satisfies the constraint for every $f\in F_0$ from the initial-state distribution (4); a well-calibrated model, $f^*\in F_n$ for all $n\le N$ with probability at least $1-\delta$. The critic is $Q^{\hat\pi}_{c,n}(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]$ on the nominal model, with $\lambda_{\rm pess}=\max\{C_{\max},k_{\max}\}\,\gamma(1+\sqrt{d_s})\beta_N(\delta)/((1-\gamma)\sigma)$ and $d_s$ the state dimension.
Safety (Thm. 1). With probability at least $1-\delta$, the switched policy satisfies $J_c(\bar\pi_n,f^*)\le d$ in every episode $n=1,\dots,N$. (The paper states Theorem 1 under all of Assumption 4, including the statewise condition below; its safety proof uses only the robust feasibility of $\hat\pi$.)
Regret (Thm. 2). If moreover $V^{\hat\pi}_c(s)\le V^{\pi^*_c}_c(s)$ for all states (the rest of Assumption 4) and the optimal constrained policy $\pi^*_c$ is stationary, strictly feasible, $J_c(\pi^*_c,f^*)\lt d$, and has an action density bounded by some $p_{\max}$, then with probability at least $1-\delta$ the constraint $J_c(\bar\pi_n,f^*)\le d$ holds for all $n\le N$ and
Here $J_r$ is the expected discounted return from the initial-state distribution (not a realised episode return), $\Gamma_m$ the maximum information gain of the dynamics model after $m$ observations, and $O(\cdot)$ hides factors that do not depend on $N$. Dividing by $N$, the bound on the average regret is $O(\Gamma_{N\log N}^{7/2}/\sqrt N)$; it tends to zero exactly when $\Gamma_{N\log N}=o(N^{1/7})$, so the information gain has to grow very slowly for the guarantee to say that learning converges.
| Method | Safety is a function of | Model / assumptions | Backup mechanism | Guarantee |
|---|---|---|---|---|
| SafeOpt / SafeOpt-MC | parameters $a$ | GP on $h(a,i)$, $L_a$, seed | none (bandit) | safe w.h.p.; $\epsilon$-optimal in $\bar R_\epsilon(S_0)\supseteq\bar R^c_\epsilon(S_0)$ |
| GoSafe | $(a,\tilde x_0)$, discretised state | GP on joint space, $L_a$, $L_x$, $\mu$ | switch when $[x(t)]_\mu\in\partial S_n$ | safe w.h.p.; $\epsilon$-optimal in $\bar R^g_\epsilon(S_0)$; low-dimensional states only |
| GoSafeOpt | parameters $a$, backups in $A\times X$ | GP on $h(a,i)$, $L_a$, $L_x$, $\Xi$, $\Delta t$, trajectory-min constraints | boundary condition from visited states (Markov) | safe w.h.p. (Thm 4.1); $\epsilon$-optimal if $a^*$ discoverable (Thm 4.3) |
| SafeMDP | states $s$ of a known deterministic MDP | GP on $r(s)$, $L$, ergodic seed | returnability built into $\hat S_t$ | safe w.h.p.; complete exploration of $\bar R_\epsilon(S_0)$ |
| GoOSE / SNO-MDP | states (decisions) | as SafeMDP plus oracle / reward GP | pessimistic ergodic set | safety; oracle-optimal / $\epsilon_V$-near-optimal return |
| SageMPC | states $x$ of a continuous domain, nonlinear dynamics | GP on $q(x)$, known dynamics, terminal set | returnable trajectories via optimal control | safety w.h.p.; finite sample complexity without discretisation |
| ActSafe | policies $\pi$ of a CMDP | well-calibrated model of $f^*$, $L_f$, $L_c$, safe seed of policies | pessimistic cost over plausible models | expected cost $\le d$ in every episode w.h.p.; $\epsilon$-optimal in $R^H_\epsilon(S_0)$ after $n^*$ |
| SOOPER | trajectories (cumulative cost) | calibrated probabilistic model, pessimistic policy prior (for the regret: strictly feasible optimum, $V_c^{\hat\pi}\le V_c^{\pi^*_c}$ statewise) | online cost tracking, fallback to prior | expected-cost constraint holds in every episode w.h.p.; cumulative regret $O(\Gamma^{7/2}\sqrt N)$ |
Walkthrough: Why Backups Keep You Safe
The five steps below assemble the boundary condition from the assumptions, one inequality at a time. Each step states what is used and why the step is allowed.
Interactive: Local vs Global Safe Exploration
Run SafeOpt and GoSafeOpt on a toy dynamical system with two disconnected safe islands and watch the backup mechanism work, or break it by switching the boundary condition off or by feeding it wrong constants.
Choose a local or global exploration mode, then step through experiments. The parameter map shows what is certified; the trajectory plot shows where a tested controller moves and whether a backup takes over. Open the setup below for the equations and assumptions behind the simulation.
Toy system. A scalar state $x$ moves on a track with walls at $\pm1$, so $\bar g(x)=1-|x|$, and every experiment starts at $x_0=0$. The closed loop is the Euler-discretised P-control (see Primer D) of $\dot x=-x+u+w$ with a constant disturbance $w=0.6$: $x_{k+1}=x_k+\Delta t\,[-(1+\kappa)x_k+\kappa\rho+w]$, $\Delta t=0.0025$, 1200 steps. The parameters are a reference command $\rho(a_1)=0.8\,(1+\cos 4\pi a_1)\ge0$ and the gain $\kappa(a_2)=3+5a_2$. From $x_0=0$ the state moves monotonically to the equilibrium $x_{\rm eq}=(\kappa\rho+w)/(1+\kappa)\gt0$ (see Primer D), so the trajectory-minimum constraint is $g(a)=1-x_{\rm eq}(a)$: a smooth function of $a$ that is negative wherever $x_{\rm eq}\gt1$, i.e. for $a_1$ near $0$, $0.5$ and $1$. Since $g\ge0$ exactly when $\cos4\pi a_1\le\tfrac14+\tfrac1{2\kappa}$, this cuts the feasible set into two islands, $a_1\in[b,\tfrac12-b]$ around the seed $(0.25,0.5)$ and $a_1\in[\tfrac12+b,1-b]$ around the global maximum of the objective (a designed smooth function), where $b(\kappa)=\arccos\big(\tfrac14+\tfrac1{2\kappa}\big)/(4\pi)$ rises from $0.0908$ at $\kappa=3$ to $0.0997$ at $\kappa=8$. So the islands are approximately $[0.09,0.41]$ and $[0.59,0.91]$; on the grid $a_1=i/24$ they are the columns $a_1=0.125,\dots,0.375$ and $0.625,\dots,0.875$, with 175 parameters each. The explorer evaluates this $g$ in closed form on a $25\times25$ grid (it is the infimum along the infinite-horizon trajectory; the rollouts shown are simulated for 1200 steps), and from any start $x$ the same reasoning gives $g(a,x)=1-\max(|x|,x_{\rm eq}(a))$. Because $\bar g$ is 1-Lipschitz and every Euler step is non-expansive (see Primer B), $L_x=1$ exactly; $\Xi$ is the largest one-step motion over all grid parameters and all states with $|x|\le1.2$; $L_a$ is the largest difference quotient of $g$ over all pairs of grid points. Two independent GPs (SE kernel, length scale 0.12, noise 0.02) model $f$ and $g$ with the heuristic $\beta$ of the slider; the safe set, expanders and maximisers are those of Section 4; parameters whose confidence widths agree to within $10^{-3}$ (every parameter far from all data) count as ties and are broken with a seeded generator. GE rollouts use Algorithm 3 with a backup set collected from every safe rollout (every 30th sample).
Equilibrium. The controller is $u=\kappa(\rho-x)$, so $\dot x=-(1+\kappa)x+\kappa\rho+w$, and forward Euler with step $\Delta t$ gives the recursion above. Its fixed point solves $-(1+\kappa)x+\kappa\rho+w=0$, i.e. $x_{\rm eq}=(\kappa\rho+w)/(1+\kappa)$. Subtracting the fixed-point equation gives $x_{k+1}-x_{\rm eq}=r\,(x_k-x_{\rm eq})$ with $r=1-\Delta t(1+\kappa)\in[0.9775,0.99]$, hence $x_k=x_{\rm eq}+r^k(x_0-x_{\rm eq})$: the state moves monotonically from $x_0$ towards $x_{\rm eq}$ without reaching it when $x_0\ne x_{\rm eq}$; if $x_0=x_{\rm eq}$, it stays fixed. So $\sup_k|x_k|=\max(|x_0|,x_{\rm eq})$ and $g(a,x_0)=\inf_k\bar g(x_k)=1-\max(|x_0|,x_{\rm eq})$.
Two islands. From $x_0=0$, $g\ge0$ means $x_{\rm eq}\le1$, i.e. $\kappa\rho+0.6\le1+\kappa$ (multiply by $1+\kappa\gt0$), i.e. $\rho\le1+0.4/\kappa$. With $\rho=0.8(1+\cos4\pi a_1)$, dividing by $0.8$ and subtracting $1$ gives $\cos4\pi a_1\le\tfrac14+\tfrac1{2\kappa}$. For $a_1\in[0,1]$ the cosine runs through two periods and is small only around $a_1=\tfrac14$ and $a_1=\tfrac34$: two islands.
$L_x=1$. For the same parameter, two trajectories started at $x$ and $y$ satisfy $x_k-y_k=r^k(x-y)$, so $|x_k-y_k|\le|x-y|$, and $|\bar g(v)-\bar g(v')|=\big||v'|-|v|\big|\le|v-v'|$. So the immediate constraint values differ by at most $|x-y|$ at every step, and so do their infima. Equivalently, $g(a,x)=1-\max(|x|,x_{\rm eq})$ has slope at most $1$ in $x$, with equality for $|x|\gt x_{\rm eq}$.
$\Xi$ and $L_a$. One Euler step moves the state by $\Delta t\,|{-(1+\kappa)x}+\kappa\rho+w|$; on $|x|\le1.2$ this is largest at $x=-1.2$, where it equals $\Delta t\,[1.2(1+\kappa)+\kappa\rho+w]$. Over the grid the maximum is at $\kappa=8$, $\rho=1.6$: $\Xi=0.0025\cdot(10.8+12.8+0.6)=0.0605$. The "true" $L_a\approx8.53$ shown next to the slider is the largest difference quotient over pairs of grid points; it need not bound the slope between grid points.
The objective is a fixed synthetic function, independent of the track dynamics: $f(a)=e^{-[(a_1-0.75)^2+(a_2-0.6)^2]/(2\cdot0.13^2)}+0.6\,e^{-[(a_1-0.25)^2+(a_2-0.4)^2]/(2\cdot0.13^2)}+0.1\,a_2$. The best guess is $\hat a_n=\arg\max_{a\in S_n}l_n(a,0)$, and the displayed regret is its simple regret $f^*-f(\hat a_n)$ (see Primer E), where $f^*$ is the largest true objective over the safe grid points; the true values are used for this score only, never by the algorithms.
Observations of $g$ are the closed-form infinite-horizon value plus noise; the 1200 simulated steps ($3$ s) only draw the rollout and count wall hits, so a zero violation count refers to the simulated prefix. Settings: width tolerance $\epsilon=0.2$; at most 160 experiments ("finished" appears either when the convergence test passes and nothing is left to try, or when this budget is used up without convergence; the log says which); at most six GE attempts per GE phase; eight LSE steps before each GE phase, halved after an unsuccessful GE phase (minimum three) and reset to eight after a successful one. The GP posterior is computed exactly with a Cholesky factorisation $K+\sigma^2I=LL^\top$ and triangular solves (see Primer A).
Things to try: run SafeOpt to convergence and note that the safe set never leaves the left island (its 175 parameters). Switch to GoSafeOpt: in the first GE phase experiments are interrupted (orange) or succeed (purple), after which LSE takes over in the right island; the green band on the trajectory panel is the certified safe-state set $X^s_n$, which grows with the backups, and the violation counter stays at zero. Untick the boundary condition and violations appear. Set $L_x$ or $\Xi$ below their true values and the certified balls are too large, so backups are triggered too late or not at all. Set $L_a$ well below its true value and the local phase itself fails, the analogue of the "failures in the local phase" of Section 6. Set $\beta$ to 1 and some GP lower bounds become invalid: backups built on them certify balls that are too large, and with the default noise seed a few GE experiments hit the wall although the boundary condition is on. The certificate is only as good as the bound it is built on. Slider changes act on the running experiment without resetting data, bounds or certified sets, so press Reset for a clean comparison; in deliberately misspecified runs, "safe set" and "backups" are what the algorithm believes, not proven facts.
From the mathematics to a real decision
Learning objectives
- Build a backup switching test in state space, including localization error and monitoring latency.
- Distinguish a stored controller from a certificate that it recovers from nearby full states.
- Explain how several backup regions can support exploration without promising global discoverability.
A commissioning decision
A small robot moves toward a wall while a learned controller explores faster motion. Its state is $z=(d,v)$: wall clearance $d$ in metres and approach velocity $v$ in metres per second. Nonnegative clearance is required continuously. A stored backup controller was validated from $z_b=(0.8,0.3)$. Let $g_b(z)$ denote the minimum clearance over the complete future trajectory obtained by starting that backup at $z$.
Assume the backup closed loop is well defined, and its minimum-clearance function satisfies $g_b(z_b)\ge0.4\,\mathrm m$ and $g_b(z)\ge0.4-D(z,z_b)$ in the region considered. The weighted distance is $D(z,z_b)=|d-0.8|+\tau|v-0.3|$, with $\tau=0.5\,\mathrm s$, so both terms are in metres. This is a model-based recovery certificate; it is stronger than storing one successful trajectory.
State-estimation error has weighted magnitude at most $0.02\,\mathrm m$. During the complete interval between the last observation and the backup taking effect, assume weighted state motion is bounded by $M=0.8\,\mathrm{m/s}$. The total observation-plus-switching interval is at most $\Delta t=0.1\,\mathrm s$. These are explicit assumptions about the monitor and controller implementation.
Worked decision, with its limits
Reserve the latency budget. The state at actual backup activation can differ from the reported state by at most $r=0.02+M\Delta t=0.10\,\mathrm m$. By the triangle inequality, a reported state $\hat z$ can be approved for recovery through this backup if
This guarantees that the activation state has nonnegative future minimum clearance under the backup. Monitoring samples alone would not provide this implication; the latency reserve covers movement after the last sample.
Check the present exploratory state. At $\hat z=(0.60,0.40)$, the distance is $|0.60-0.80|+0.5|0.40-0.30|=0.25\,\mathrm m$. The available recovery margin after reserving latency is $0.4-0.25-0.10=0.05\,\mathrm m$. Recovery is certified. Before activation, clearance itself is at least $0.60-0.02-0.08=0.50\,\mathrm m$, using the same motion bound. Thus the transition into the backup is also covered.
Reject a later switching point. At $\hat z=(0.50,0.50)$, the weighted distance is $0.30+0.10=0.40\,\mathrm m$. Including latency gives 0.50, exceeding the backup radius. The fact that the robot has not yet touched the wall does not authorize further exploration. A monitoring policy should trigger the validated backup while the recovery test still holds, before entering a state from which that test has failed.
State what was achieved. The proof covers recovery through this backup under the assumed trajectory regularity, state completeness, and implementation bounds. It does not prove that a particular exploratory controller will find a better policy, visit every safe state, or reach another parameter-space component. Those are discoverability questions requiring additional conditions. The useful local result is that exploratory motion can be interrupted through a state-space certificate.
A tempting wrong approach
A backup that succeeds from clearance 0.6 metres at low speed need not succeed from the same clearance at high speed. Dropping velocity from the stored state loses the Markov information needed by the recovery argument. Similarly, a validated nominal policy is not a universal backup: its recovery region and the delay before it takes effect must be specified together.
Transfer the argument
Exercise 6.B1 — Medium: Choose the monitoring period
Keep the state $(0.60,0.40)$ and all bounds except $\Delta t$. Find the largest total observation-plus-switching interval allowed by the certificate. Does 0.2 seconds pass?
Review: State-space backup regions.
Show hint
Use distance 0.25 and solve $0.25+0.02+0.8\Delta t\le0.4$.
Show worked solution
The limit is $\Delta t\le(0.4-0.25-0.02)/0.8=0.1625\,\mathrm s$. At 0.2 seconds the reserve is $0.02+0.16=0.18$ metres and the total is 0.43, so recovery is uncertified. This time is the whole latency budget; a sensor sampling period of 0.16 seconds leaves almost no room for computation or actuation delay. Equality permits zero certified clearance and may be unsuitable for a specification requiring positive separation.
Exercise 6.B2 — Hard: Use a library of recovery regions
A second backup has center $(0.45,0)$ and certified minimum clearance 0.25 metres, using the same metric and reserve 0.10. Determine whether state $(0.40,0.10)$ is covered by either backup. Repeat for $(0.40,1.0)$.
Review: Backup selection and complete states.
Show hint
Test each center independently, then take the union of successful certificates. Velocity is multiplied by 0.5 seconds.
Show worked solution
For $(0.40,0.10)$, the first distance is $0.40+0.5(0.20)=0.50$, which fails after adding the reserve. The second distance is $0.05+0.5(0.10)=0.10$; its total 0.20 is below 0.25, so this backup certifies recovery with 0.05 metres remaining. For $(0.40,1.0)$, distances are $0.40+0.35=0.75$ and $0.05+0.50=0.55$; neither passes. More stored backups can enlarge the covered union, but arbitrary interpolation between their controllers has no certificate from these calculations.
Synthesis and bridge
State-space backups add a new route to safe exploration: permission comes from the ability to recover after the exploratory action, rather than only from neighboring safe parameters. The practical certificate includes the measured state, recovery controller, metric, error bounds, and timing budget. Each item participates in the inequality.
The viability chapter makes the underlying question explicit: which states admit any future sequence of actions that avoids failure? A backup region is one constructive inner approximation to that set. It can be conservative, and a state may be viable even when this particular recovery library cannot certify it.
Exercises
Graded practice — Build the argument yourself
There are 12 new problems: four Easy, four Medium, and four Hard. Start with the level that lets you make progress without opening the solution. Easy problems rebuild individual operations; Medium problems combine them; Hard problems ask for proofs, boundary cases, and the limits of a guarantee. The required concepts are explained on this page or in the linked earlier material.
Easy — Warm up one skill at a time.
Exercise 6.P1 — Easy: Safety is the minimum along a trajectory
For state constraint $\bar g(x)=1-|x|$, a sampled trajectory visits $x=0,0.3,0.9,0.4$. Compute the smallest sampled margin. If it also visits $x=1.1$ between two samples, is the full experiment safe?
Review if needed: Primer D: trajectories. Apply here: this module's explanation.
Show hint
Apply $\bar g$ at every listed state. A minimum over samples need not equal a minimum over continuous time.
Show worked solution
The sampled margins are 1, 0.7, 0.1, and 0.6, so the smallest sampled margin is 0.1. At an intermediate state 1.1, however, $\bar g(1.1)=-0.1$, so the full continuous-time experiment is unsafe.
A trajectory-minimum constraint must cover all relevant times. Sampling alone checks only the sampled states; a motion bound and an appropriate margin bridge the intervals. A safe final state, or even safe states at every recorded sample, is insufficient without that bridge.
Exercise 6.P2 — Easy: Compute a backup ball
A stored backup at state $x'=0.2$ has lower constraint margin $l=0.6$. Let $L_x=2$ and the between-sample motion allowance be $\Xi=0.05$. Compute its certified radius $r=l/L_x-\Xi$ and interval in a scalar state space. Check state 0.4.
Review if needed: Primer B: sensitivity margins. Apply here: this module's explanation.
Show hint
The motion allowance consumes part of the geometric radius.
Show worked solution
The radius is $0.6/2-0.05=0.25$, giving $[0.2-0.25,0.2+0.25]=[-0.05,0.45]$. State 0.4 is at distance 0.2 and lies inside the interval.
The corresponding worst-case margin is $l-L_x(|0.4-0.2|+\Xi)=0.6-2(0.2+0.05)=0.1\ge0$. This is the certificate under the page's trajectory/Lipschitz assumptions. If $l/L_x-\Xi$ were negative, this backup would certify no states, rather than a ball with a negative radius.
Exercise 6.P3 — Easy: Turn a speed bound into a motion allowance
A continuously monitored state has $\|\dot x(t)\|\le3$ in the chosen norm and is sampled every $\Delta t=0.02$. Bound its displacement between a sample and any time before the next sample. What allowance is needed if the interval doubles?
Review if needed: Primer B: derivatives and rates of change. Apply here: this module's explanation.
Show hint
Integrate the speed bound over at most one sampling interval.
Show worked solution
For $s\in[t,t+\Delta t]$, $\|x(s)-x(t)\|\le\int_t^s\|\dot x(r)\|dr\le3(s-t)\le3(0.02)=0.06$. Thus $\Xi=0.06$ is a valid allowance under the stated speed bound.
If the interval doubles to 0.04, the allowance doubles to 0.12. The same lower constraint margin then covers a smaller set of starting states. The speed bound must hold throughout the interval, under the tested controller and any switching delay included in the model; a speed estimate at the sample alone does not establish this integral bound.
Exercise 6.P4 — Easy: Why augmenting the state can be expensive
A parameter grid has 100 points. A state grid has 10 bins in each coordinate. How many joint parameter-state pairs are there for two state coordinates? For six? Why does GoSafeOpt try to avoid learning a GP on that full product?
Review if needed: Primer 0: Cartesian products. Apply here: this module's explanation.
Show hint
Multiply the number of parameter points by the number of state-grid combinations.
Show worked solution
With two state coordinates, the state grid has $10^2=100$ points and the product has $100(100)=10{,}000$ pairs. With six coordinates, there are $10^6$ state combinations and $100(10^6)=100{,}000{,}000$ pairs.
The rapid growth comes from the Cartesian product: every extra coordinate multiplies the count by 10. GoSafeOpt keeps the learned GP on parameters and collects state backups along trajectories instead. This reduces the need for a full state grid; it does not remove the need to certify that those backups cover states reached during a global experiment.
Medium — Combine definitions and compute a certificate.
Exercise 6.P5 — Medium: Unite backup regions without filling their gaps
Two scalar backups certify intervals $[-0.4,0.1]$ and $[0.3,0.7]$. Which of states 0, 0.2 and 0.5 are covered? May the algorithm replace their union by the enclosing interval $[-0.4,0.7]$?
Review if needed: Primer 0: interval unions. Apply here: this module's explanation.
Show hint
Membership needs one actual certificate. An enclosing interval can contain points covered by neither.
Show worked solution
State 0 is covered by the first interval, 0.5 by the second, and 0.2 by neither. The safe-state certificate is the union $[-0.4,0.1]\cup[0.3,0.7]$.
Replacing the union by its enclosing interval would silently add the gap $(0.1,0.3)$ without a witness. Additional trajectory analysis might prove that some gap points are safe, but these two backup certificates do not. A geometric approximation of a certified set must remain inside that set if it is to preserve safety automatically.
Exercise 6.P6 — Medium: A suffix cannot have a smaller trajectory minimum
A deterministic Markov closed loop under a fixed backup parameter has trajectory $x_a(t)$ from $x_0$, with constraint $g(a,x_0)=\inf_{t\ge0}\bar g(x_a(t))\ge0.2$. Explain why restarting the same controller at a visited state $x_a(t_1)$ has constraint at least 0.2. State what could break the argument.
Review if needed: Primer 0: infima over sets. Apply here: this module's explanation.
Show hint
The restarted path is a suffix when the state contains all information needed to determine future evolution.
Show worked solution
For autonomous deterministic dynamics with the same controller, uniqueness and the Markov state description give the restarted trajectory $x_a(t_1+s)$ for $s\ge0$. Its constraint is $\inf_{t\ge t_1}\bar g(x_a(t))\ge\inf_{t\ge0}\bar g(x_a(t))\ge0.2$, because the infimum is taken over fewer times.
The argument can fail if restarting omits an internal controller state, the dynamics depend on an unrecorded clock, or switching does not actually reproduce the same closed loop. Markov means the stored state contains the information determining the future; merely naming a position as “state” does not ensure it.
Exercise 6.P7 — Medium: A safe state may be a trap
A known deterministic graph has safe states $A,B,C$. Available edges are $A\to A$, $A\to B$, $B\to A$, $B\to C$, and $C\to C$. Start from seed $\{A\}$. Which states are both reachable from the seed through safe states and able to return to the seed?
Review if needed: Primer E: transition graphs. Apply here: this module's explanation.
Show hint
Check a path in each direction; safety of a node does not imply a return path.
Show worked solution
All three states are reachable: $A$ immediately, $B$ via $A\to B$, and $C$ via $A\to B\to C$. Both $A$ and $B$ can return to the seed, using $A\to A$ and $B\to A$.
State $C$ has only a self-loop, so it cannot return to $A$. The reachable-and-returnable set is $\{A,B\}$. A safety-feature certificate at $C$ would establish that remaining there meets the state constraint, but would not establish the reversible exploration property required by the returnability condition.
Exercise 6.P8 — Medium: Budget one confidence event for several functions
Suppose separate valid time-uniform bands are available for an objective and two constraints. If each band fails with probability at most $0.01$, what joint failure bound follows? How should equal budgets be chosen for total failure at most $0.01$?
Review if needed: Primer C: simultaneous events. Apply here: this module's explanation.
Show hint
There are three failure events even though each one already covers all times.
Show worked solution
The union bound gives joint failure probability at most $3(0.01)=0.03$, hence all three bands hold with probability at least 0.97. To obtain a total budget 0.01 from separate bands, assign each failure budget $0.01/3$.
No independence is needed. Since each band is already time-uniform, this calculation adds across functions rather than across rounds. If a theorem directly supplies one joint band for the stacked objective and constraints, its stated $\delta$ already covers that collection and should not be multiplied again.
Hard — Explain why the argument works and where it stops.
Exercise 6.P9 — Hard: Derive the backup condition with every loss visible
For a backup controller $a'$, suppose $g_i(a',x')\ge l_i$ at its stored state, and $g_i(a',\cdot)$ is $L_x$-Lipschitz. The current sampled state is $x$, and before switching the state moves to some $\tilde x$ with $\|\tilde x-x\|\le\Xi$. Prove that $\min_i l_i\ge L_x(\|x-x'\|+\Xi)$ suffices for all backup trajectory constraints from $\tilde x$.
Review if needed: Primer B: Lipschitz lower bounds. Apply here: this module's explanation.
Show hint
Bound the distance from $\tilde x$ to the stored state using the triangle inequality.
Show worked solution
The triangle inequality gives $\|\tilde x-x'\|\le\|\tilde x-x\|+\|x-x'\|\le\Xi+\|x-x'\|$. For every constraint, Lipschitz continuity gives
The minimum over $i$ enforces all constraints using this one backup controller. The motion allowance covers the pre-switch displacement; the trajectory constraint $g_i$ then covers the entire backup continuation. The actual global-experiment proof must also show that the prefix before switching remains safe, using the monitored coverage and motion assumptions.
Exercise 6.P10 — Hard: Why certified state sets grow
Let $X_n^s$ be the union of balls centered at stored backup states with radii $r_n(a',x')=\min_i l_n(a',i)/L_x-\Xi$, ignoring negative radii. Assume backups are retained and each lower bound is nondecreasing. Prove $X_n^s\subseteq X_{n+1}^s$ and explain its role in retries.
Review if needed: Primer 0: set-inclusion proofs. Apply here: this module's explanation.
Show hint
Take a point and keep its existing witnessing backup at the next iteration.
Show worked solution
For any $x\in X_n^s$, choose a stored backup $(a',x')$ with $\|x-x'\|\le r_n(a',x')$. Retention keeps this center available. Since each $l_{n+1}(a',i)\ge l_n(a',i)$, taking minima preserves the inequality and gives $r_{n+1}(a',x')\ge r_n(a',x')$. Therefore the same backup still covers $x$.
New backups can add further regions. A parameter interrupted earlier may become executable after its trigger state enters this larger set; retaining a permanent “failed” label without rechecking would discard such opportunities. Monotonicity depends on valid retained certificates for a stationary system; a changed plant requires a new validity argument.
Exercise 6.P11 — Hard: Choose monitoring speed from a required radius
A backup has lower margin 0.3 and state sensitivity $L_x=2$. You want it to cover all sampled states within distance 0.1 of its stored state. If $\|\dot x\|\le5$ and the motion allowance is $\Xi=5\Delta t$, find a sufficient maximum sample interval. Include a switching delay of 0.004 seconds in a second calculation.
Review if needed: Primer D: continuous-time trajectories. Apply here: this module's explanation.
Show hint
Require $L_x(0.1+\Xi)\le0.3$. A delay adds to the time over which motion is possible.
Show worked solution
The margin condition gives $2(0.1+5\Delta t)\le0.3$, hence $\Delta t\le0.01$ seconds. At this limit the worst-case transferred margin is exactly zero; a strict practical margin would require a smaller interval or a stronger lower bound.
If switching takes 0.004 seconds and the same speed bound holds during it, use $\Xi=5(\Delta t+0.004)$. Then $\Delta t+0.004\le0.01$, giving $\Delta t\le0.006$ seconds. Ignoring implementation delay would spend more geometric margin than the certificate allows. This calculation assumes the stated sensitivity and speed bounds throughout the monitored region.
Exercise 6.P12 — Hard: Safe global exploration is not automatic global discovery
Two safe parameter islands contain best objective values 1 and 3, respectively. The seed lies in the first. Suppose the only parameter capable of reaching the second island must pass through a state outside every certified backup region, so every such experiment is interrupted. What can the safety theorem establish? Does it prove convergence to value 3?
Review if needed: Module 4: reachable optima. Apply here: this module's explanation.
Show hint
Separate the statement about every executed trajectory from the condition that an optimal island is eventually discoverable.
Show worked solution
Under its full assumptions, the safety theorem can establish that the interrupted experiments and their backup continuations remain safe. It does not establish that the second parameter island is entered. In the scenario given, the coverage required to complete the transition is missing.
Convergence to the safe global optimum needs the additional discoverability condition stated on this page. Without it, exploration may remain in the seed's reachable region and achieve at most value 1 in this example. Increasing optimism alone does not supply a backup for the uncovered state; more certified coverage or a different safe route is needed.
Further practice — Original problems and research connections
The original exercises below retain their numbering. Some compare later methods or ask for longer research derivations; use the graded set above first, and return to a research-connection problem after reading the relevant linked module.
Key Papers
| Paper | Venue | Contribution | Why read it |
|---|---|---|---|
| Sukhija, Turchetta, Lindner, Krause, Trimpe, Baumann — GoSafeOpt: Scalable safe exploration for global optimization of dynamical systems | Artificial Intelligence 320, 2023 | LSE/GE alternation, backups from the Markov property, online boundary condition; Theorems 4.1 and 4.3 | The reference algorithm of this module; Appendix A is a model of a clean safety proof |
| Baumann, Marco, Turchetta, Trimpe — GoSafe: Globally Optimal Safe Robot Learning | IEEE ICRA 2021 (arXiv version with corrections) | Safe set over parameters and initial conditions, three stages, backup from the border of the safe set; Furuta pendulum | The first provable escape from SafeOpt's locality and the reason GoSafeOpt exists |
| Sui, Gotovos, Burdick, Krause — Safe Exploration for Optimization with Gaussian Processes | ICML 2015 | SafeOpt: Lipschitz safe set, expanders, maximisers, reachability operator | Every operator in this module is a variant of the ones defined here |
| Berkenkamp, Krause, Schoellig — Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Robotics | Machine Learning 112, 2023 (online 2021) | SafeOpt-MC with multiple constraints via the selector function; the $\beta_n$ and convergence result reused by GoSafeOpt's LSE | The exact statement "with $\beta_n$ as defined in [18]" points here |
| Fiedler, Menn, Kreisköther, Trimpe — On Safety in Safe Bayesian Optimization | TMLR 2024 | Documents heuristic $\beta$ in SafeOpt-type implementations (including GoSafe and GoSafeOpt) and shows it voids the guarantees; Real-$\beta$-SafeOpt and LoSBO | Puts Section 6 in perspective and suggests how to repair the LSE part |
| Turchetta, Berkenkamp, Krause — Safe Exploration in Finite Markov Decision Processes with Gaussian Processes | NeurIPS 2016 | SafeMDP: safety feature over states, reachability and returnability operators, complete safe exploration | The template for ergodicity-constrained safe exploration |
| Turchetta, Berkenkamp, Krause — Safe Exploration for Interactive Machine Learning | NeurIPS 2019 | GoOSE: goal-oriented safe exploration wrapping any oracle; pessimistic and optimistic expansion operators | Where the pessimistic/optimistic safe-set pair comes from |
| Wachi, Sui — Safe Reinforcement Learning in Constrained Markov Decision Processes | ICML 2020 | SNO-MDP: expand the safe region, then optimise reward inside it; ES$^2$ early stopping; near-optimality | The reward-aware SafeMDP with guarantees |
| As, Sukhija, Treven, Sferrazza, Coros, Krause — ActSafe: Active Exploration with Safety Constraints for Reinforcement Learning | ICLR 2025 | Model-based safe-set expansion over policies with pessimism for the constraint and optimism for exploration; safety and sample complexity | The expansion operator of SafeOpt, rewritten for policies and dynamics models |
| Wendl, As, Prajapat, Pollak, Coros, Krause — Safe Exploration via Policy Priors | ICLR 2026 | SOOPER: pessimistic policy prior as fallback, online cost tracking, cumulative regret | The deep-RL counterpart of the boundary condition, for cumulative constraints |
| Prajapat, Köhler, Turchetta, Krause, Zeilinger — Safe Guaranteed Exploration for Non-linear Systems | IEEE TAC, 2025 (DOI 10.1109/TAC.2025.3541577) | SageMPC: safe exploration of a continuous state constraint with nonlinear dynamics; sample complexity without discretisation | Shows how the state-space line reaches continuous domains with MPC |