E. MDPs, Reinforcement Learning & Neural Networks

Policies, value functions, Bellman equations, policy gradients, and the neural networks inside them

Readiness checks — a short prerequisite refresher

These checks are diagnostic, with the needed calculation explained in each answer. A gap tells you where to review; it is not a reason to skip this primer.

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

Half of this section is about agents that learn to act (safe RL, safe exploration, constrained policy optimisation), the other half about the networks those agents and controllers are made of (Lipschitz bounds, certified robustness, networks in feedback loops). This primer builds both vocabularies from scratch: first bandits, the one-state version of learning to act; then Markov decision processes, value functions and the Bellman equations; the dynamic-programming algorithms that solve them exactly; the gradient methods that replace them when the problem is large; and finally neural networks as compositions of affine maps and activations, how they are trained, and what it means to certify a classifier.

1. Bandits, Regret & Bayesian Optimization

The simplest sequential decision problem has no state: in every round you choose an action, receive a noisy payoff, and want to do well over many rounds. Tuning a controller by experiments (Modules 4–6) is exactly this: each experiment is a round, the controller parameters are the action, the measured performance is the payoff. Two questions organise everything: how do we score a learner (regret), and how should it trade trying new actions against repeating good ones (exploration versus exploitation)?

Example. Let $f(x^*)=1$ and suppose five experiments have true values $f(x_t)=0.2,\,0.5,\,0.9,\,1,\,1$. Then $r_t=0.8,\,0.5,\,0.1,\,0,\,0$, so $R_5=1.4$ and the average regret is $0.28$. If the fourth point is recommended, the simple regret is $0$ although the cumulative regret is not: the two criteria reward different behaviour. Changing objectives. If the objective drifts ($f_t$ in round $t$), static regret compares with the best fixed action in hindsight, $\max_x\sum_tf_t(x)-\sum_tf_t(x_t)$, and dynamic regret with the best action of each round, $\sum_t\big(\max_xf_t(x)-f_t(x_t)\big)$; the latter is harder to keep sublinear and needs a bound on how fast $f_t$ changes. For a fixed $f$ both equal $R_T$.

Example (UCB1). After $t=12$ pulls, arm 1 has $n_1=10$, $\hat\mu_1=0.6$ and arm 2 has $n_2=2$, $\hat\mu_2=0.5$. With $\ln12=2.485$: $U(1)=0.6+\sqrt{2\cdot2.485/10}=0.6+0.705=1.305$ and $U(2)=0.5+\sqrt{2\cdot2.485/2}=0.5+1.576=2.076$. UCB1 pulls arm 2: lower mean, but far fewer pulls.

Bayesian optimization: a bandit with a Gaussian-process model

For a continuous bandit with expensive, noisy evaluations, Bayesian optimization (BO) fits a probabilistic surrogate of $f$, usually a Gaussian process (GP), and chooses each experiment by maximising a cheap acquisition function built from the posterior mean $\mu_{t-1}(x)$ and standard deviation $\sigma_{t-1}(x)$. GP regression is the subject of Module 3 (its engine, Gaussian conditioning, is in Primer C); here only the loop and the acquisition functions matter.

Example. Incumbent $f^+=1$, $\beta_t=2$. Candidate A has $\mu=0.8$, $\sigma=0.3$; candidate B has $\mu=1.05$, $\sigma=0.05$. UCB: $0.8+0.6=1.40$ for A versus $1.05+0.10=1.15$ for B, so UCB explores A. EI: for A, $z=-0.667$, $\mathrm{EI}=(-0.2)(0.2525)+0.3\,(0.3194)=0.0453$; for B, $z=1$, $\mathrm{EI}=0.05\,(0.8413)+0.05\,(0.2420)=0.0542$, so EI exploits B. Acquisition functions encode different exploration preferences; none of them knows anything about safety.

Local search and trust regions. In high dimensions a single global GP is hard to fit and the acquisition is hard to maximise. Local BO (TuRBO, Eriksson et al., NeurIPS 2019) restricts the queries to a trust region, a box around the best point found so far whose side length is doubled after a run of successes and halved after a run of failures (with a restart when it becomes tiny). This region lives in the parameter space of the objective; the trust regions of Section 5 are instead KL balls around the current policy. Grids and the curse of dimensionality. A candidate grid with $m$ points per axis in $d$ dimensions has $m^d$ points: with $m=100$, $10^6$ points for $d=3$ and $10^{12}$ for $d=6$. Grid-based safe BO and grid-based verification therefore stop at a few dimensions, and a statement proved on grid points says nothing about the continuous domain between them unless a Lipschitz argument fills the gaps.

Example. Outcomes $A=(3,1)$, $B=(2,2)$, $C=(1,3)$, $D=(1.5,1.5)$, reference $q=(0,0)$. $D$ is dominated by $B$; the front is $\{A,B,C\}$ with hypervolume $3\cdot1+2\cdot(2-1)+1\cdot(3-2)=6$. A new outcome $(2.5,1.5)$ is non-dominated and raises the hypervolume to $6.25$; adding $D$ changes nothing. A front is a set of trade-offs, not a ranking: "method X is better" needs a single criterion, such as the best reward at a fixed cost budget.

Full-information and adversarial variants. In online learning with experts every action reveals its loss $\ell_t(a)\in[0,1]$ after each round (possibly chosen by an adversary), and regret is measured against the best fixed action in hindsight. The multiplicative-weights (Hedge) rule plays $p_{t+1}(a)\propto p_t(a)\,e^{-\eta\ell_t(a)}$; with $\eta=\sqrt{8\ln K/T}$ its regret, in expectation over its own randomisation, is at most $\sqrt{(T/2)\ln K}$. With bandit feedback (only the played action's loss is seen) EXP3 feeds Hedge the importance-weighted estimates $\hat\ell_t(a)=\ell_t(a)\mathbf 1\{a_t=a\}/p_t(a)$ and has regret $O(\sqrt{TK\ln K})$ (Lattimore & Szepesvári, Ch. 11, in the Further Reading). If both players of a zero-sum game (for example a policy player and a Lagrange-multiplier player) run no-regret rules, their time-averaged strategies form an approximate saddle point whose error is the sum of the two average regrets, while the last iterates may keep cycling (Primer B).

Practice — Score decisions before choosing an algorithm

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

2. Markov Decision Processes, Policies & Returns

In a bandit the action does not change the situation. In a Markov decision process it does: the action moves a state, the state decides which rewards are reachable next, and a good decision now may pay off only much later.

The Markov property is a statement about what we call "state". For a pendulum, the angle alone is not a state (the future depends on how fast it swings); angle and angular velocity together are. A reward that depends on the successor, $r(s,a,s')$ as in Module 1, can be replaced by its conditional mean $r(s,a)=\sum_{s'}P(s'\mid s,a)\,r(s,a,s')$ whenever only expected returns matter (tower rule, Primer C).

Softmax policies. A standard way to turn arbitrary scores $\theta_{s,a}$ into a point of the simplex is the softmax with temperature $\alpha\gt0$:

Every action gets positive probability (full support). For scores $(1,2,4)$: $\alpha=1$ gives $(0.042,0.114,0.844)$, $\alpha=0.5$ gives $(0.002,0.018,0.980)$ and $\alpha=5$ gives $(0.247,0.302,0.451)$. As $\alpha\to0$ the mass concentrates on the largest score (greedy), as $\alpha\to\infty$ it becomes uniform. Section 6 explains where this form comes from (entropy regularisation), Section 7 uses it for classifiers.

Example. Under the uniform policy ($\pi(a\mid s)=\pi(b\mid s)=\tfrac12$) the prefix $1\xrightarrow{b}2\xrightarrow{b}2$ has probability $1\cdot\tfrac12\cdot1\cdot\tfrac12\cdot1=\tfrac14$. The policy "always harvest" (go, then harvest forever) earns $0,2,2,\dots$, so $G=\sum_{t\ge1}0.9^t\cdot2=2\cdot0.9/0.1=18$ and $J_c=\sum_{t\ge1}0.9^t=9$; "always rest" earns $G=1/(1-0.9)=10$ at zero cost.

Effective horizon and time constant. For $0\lt\epsilon\lt1$, the weight $\gamma^T$ is at most $\epsilon$ exactly when $T\ge\ln(1/\epsilon)/\ln(1/\gamma)$; this needs $0\lt\gamma\lt1$ so that $\ln(1/\gamma)\gt0$. For $\gamma$ near $1$, $\ln(1/\gamma)\approx1-\gamma$, so the discount sees about $\ln(1/\epsilon)$ multiples of $1/(1-\gamma)$ steps. Example: $\gamma=0.99$, $\epsilon=0.01$ gives $T\ge458.2$, i.e. $459$ steps, while $1/(1-\gamma)=100$. In continuous time the weight is $e^{-t/\tau}$ with time constant $\tau$ (decay rate $1/\tau$); sampling at unit steps gives $\gamma=e^{-1/\tau}$, i.e. $\tau=-1/\ln\gamma$, which is $9.49$ steps for $\gamma=0.9$ (compare $1/(1-\gamma)=10$).

Episodes and absorbing states. In episodic tasks each episode (rollout) starts from $s_0\sim\mu$, often a fixed reset state $x_0$, and runs until a terminal state or a horizon; learning is an outer loop over episodes (experiments) around an inner loop over time steps. A terminal state is modelled as absorbing: once entered it is never left and yields reward and cost $0$, which turns an episodic task into an infinite-horizon one.

Deterministic MDPs as graphs. Draw a vertex per state and a directed edge $s\to f(s,a)$ per available action; a policy's run is a path. Which states are reachable is found by breadth-first search; a shortest path for nonnegative edge lengths by Dijkstra's algorithm (only this input–output behaviour is used later). A safety feature $g(s)$ that must stay above a threshold at every visited state is a separate signal from the reward.

Partial observation. If the agent sees only observations $o_t$, the Markov property usually fails for $o_t$; an information state (the whole observation history, or the posterior distribution of $s_t$ given it) restores it.

Practice — Follow the state-action-reward timeline

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

3. Value Functions & Bellman Equations

How good is a policy from a given starting point? That is a number, and collecting these numbers over all states gives a function. The key discovery of dynamic programming is that this function satisfies a simple equation linking each state to its successors.

Worked example (uniform policy on the running example). With $\pi(a\mid s)=\pi(b\mid s)=\tfrac12$ the expected one-step rewards are $0.5$ at home and $1$ in the field, and from either state the next state is home or field with probability $\tfrac12$ each. Writing $m=\tfrac12(V_1+V_2)$, the Bellman equations read $V_1=0.5+0.9m$ and $V_2=1+0.9m$; averaging them gives $m=0.75+0.9m$, so $m=7.5$ and $V^\pi=(7.25,\,7.75)$. Then

Each pair of advantages averages to zero. The same computation with the cost ($0.5$ expected cost per step in the field) gives $V_c^\pi=(2.25,\,2.75)$, $A_c^\pi(1,\cdot)=(-0.225,+0.225)$ and $A_c^\pi(2,\cdot)=(-0.725,+0.725)$: in the field, harvesting beats the average by $1.225$ in reward and loses $0.725$ in cost. This is the trade-off every constrained method negotiates.

Cost-to-go of a deterministic loop. For $x_{t+1}=F_\pi(x_t)$, $x_0=x$, and a stage cost $\ell(x)=r(x,\pi(x))\ge0$ with finite total $J(x)=\sum_t\ell(x_t)$, splitting at the first step gives $J(x)=\ell(x)+J(F_\pi(x))$, so $J(F_\pi(x))-J(x)=-\ell(x)\le0$: the undiscounted cost-to-go decreases along trajectories and is a Lyapunov-function candidate (Module 11). With a discount, $J_\gamma(x)=\ell(x)+\gamma J_\gamma(F_\pi(x))$ gives instead $J_\gamma(F_\pi(x))-J_\gamma(x)=-\ell(x)+(1-\gamma)J_\gamma(F_\pi(x))$, which can be positive. Example: stage costs $0,1,0,0,\dots$ along a trajectory give $J=(1,1,0,\dots)$, never increasing, but $J_\gamma=(\gamma,1,0,\dots)$, which increases at the first step.

In the running example $V^\ast=(18,20)$ with $Q^\ast(1,\cdot)=(17.2,\,18)$ and $Q^\ast(2,\cdot)=(16.2,\,20)$: harvesting everywhere is optimal for reward, at cost $J_c=9$. In learning the expectation in $\mathcal T^\pi$ is replaced by a sample: from a transition $(s,a,c,s')$ and $a'\sim\pi(\cdot\mid s')$ the target $y=c+\gamma Q(s',a')$ has conditional mean $(\mathcal T^\pi Q)(s,a)$. Fitting $Q$ to such targets by minimising the squared error $\mathbb E_{\mathcal D}\big[(Q(s,a)-y)^2\big]$ over a dataset $\mathcal D$, with $y$ held fixed during the fit (Section 6), moves $Q$ towards $\mathcal T^\pi Q$. In a table, where the fit can match the target at every pair, repeating it is iteration of the contraction $\mathcal T^\pi$ (Section 4, sampling noise averaged out) and approaches $Q^\pi$. With a function approximator the fit also projects onto the model class, which can destroy the contraction: the repeated fit can diverge even when $Q^\pi$ is representable (the "deadly triad" of Section 6). Module 9 writes this Bellman residual loss as $\mathbb E_{\mathcal D}\big[(Q_c-\mathcal T^\pi Q_c)^2\big]$. Indicator masks. Module 9 uses $(\mathcal T^\pi_PQ_r)(s,a)=r+\gamma\,\mathbb E\big[\mathbf 1(Q_c(s',a')\le l)\,Q_r(s',a')\big]$: the indicator is $1$ when the condition holds and $0$ otherwise, so successor pairs judged unsafe contribute no future reward. The bootstrap term is zeroed there.

The TD residual. For a value table $V$ and one observed transition, $\delta_t=r_t+\gamma V(s_{t+1})-V(s_t)$ is a one-sample Bellman residual: $\mathbb E[\delta_t\mid s_t=s]=(\mathcal T^\pi V)(s)-V(s)$. If $V=V^\pi$, then $\mathbb E[\delta_t\mid s_t,a_t]=Q^\pi(s_t,a_t)-V^\pi(s_t)=A^\pi(s_t,a_t)$: the TD residual is a noisy, unbiased advantage estimate. Advantage estimation (Section 5) and TD learning (Section 6) are built on it.

Discounted occupancy measures

Worked example. For the uniform policy, $d^\pi(1)=0.1\,(1+0.5\cdot0.9/0.1)=0.55$ (home at $t=0$, then home or field with probability $\tfrac12$ each) and $d^\pi(2)=0.45$, so $\rho_\pi=(0.275,0.275\,;\,0.225,0.225)$ for $(1,a),(1,b),(2,a),(2,b)$. Fact 1: $J=10\,(0.275\cdot1+0.225\cdot2)=7.25=V^\pi(1)$ and $J_c=10\cdot0.225=2.25$. Flow at home: $0.55=0.1+0.9\,(0.275+0.225)$.

Mixing policies versus mixing occupancies. "Always harvest" has $J=18$, $J_c=9$ and $\rho_H(1,b)=0.1$, $\rho_H(2,b)=0.9$; "always rest" has $J=10$, $J_c=0$, $\rho_R(1,a)=1$. With a budget $d=4.5$, flip one coin per episode between them: the occupancy is $\tfrac12\rho_H+\tfrac12\rho_R$, so by fact 1 the return and cost are the averages, $J=14$ and $J_c=4.5$, feasible and better than resting. By fact 3 the stationary policy $\pi_\rho(b\mid1)=0.05/0.55=1/11$, $\pi_\rho(b\mid2)=1$ achieves exactly the same pair (check: $V_1=\tfrac{10}{11}(1+0.9V_1)+\tfrac1{11}\,0.9\cdot20$ gives $V_1=14$). Averaging the action probabilities state by state instead gives $\pi(b\mid s)=\tfrac12$ everywhere, the uniform policy, with $J=7.25$ and $J_c=2.25$: neither average. The convexity used in Modules 2 and 8 is convexity of occupancy measures, not of action probabilities.

Support. $\operatorname{supp}\rho_\pi=\{(s,a):\rho_\pi(s,a)\gt0\}$ for $0\lt\gamma\lt1$ is the set of pairs the policy visits with positive probability from $\mu$ at some finite time (for $\gamma=0$, only the initial time contributes). Zero occupancy of an unsafe pair means only that it is not visited from $\mu$; it certifies nothing about what $\pi$ does at states outside the support, where a disturbance or a different initial state may put the system.

Practice — Solve a fixed point and interpret its weights

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

4. Dynamic Programming: Value & Policy Iteration

When the model $(P,r)$ is known and the state and action sets are small enough to store a table with one entry per state (the tabular setting), the Bellman equations can be solved exactly. Everything rests on one property: the Bellman operators shrink distances.

Consequences. $V^\pi$ and $V^\ast$ are the unique solutions of their Bellman equations, and iterating the operators from any table converges to them geometrically. Monotonicity adds a comparison principle: if $V\ge\mathcal T^\ast V$, then $V\ge\mathcal T^\ast V\ge(\mathcal T^\ast)^2V\ge\dots\to V^\ast$, so $V\ge V^\ast$. A "super-solution" of a Bellman inequality bounds the true value; Module 8 turns this into an LP, Module 11 into Lyapunov functions.

Worked example. Value iteration on the running example from $V_0=0$ ($\gamma=0.9$): $V_1=(\max\{1,0\},\max\{0,2\})=(1,2)$; $V_2=(\max\{1.9,1.8\},\max\{0.9,3.8\})=(1.9,3.8)$; $V_3=(\max\{2.71,3.42\},\max\{1.71,5.42\})=(3.42,5.42)$. The errors $\|V_k-V^\ast\|_\infty=18,\ 16.2,\ 14.58$ for $k=1,2,3$ are exactly $20\cdot0.9^k$, the contraction rate. At home the maximising action is "rest" in the backups that produce $V_1$ and $V_2$ and "go" from the backup producing $V_3$ on: the greedy policy for $V_k$ is optimal for every $k\ge2$, long before the values converge. Policies often converge much faster than values.

Other backups, same argument. Any backup built from averages, maxima, minima and constants, then multiplied by $\gamma$, is a $\gamma$-contraction, because each of those operations changes by at most the sup-norm change of its input. Example: the discounted safety Bellman equation $V(s)=(1-\gamma)\ell(s)+\gamma\min\{\ell(s),\max_aV(s^+_a)\}$ of Fisac et al. (safety margin $\ell$, successor $s^+_a$). Its undiscounted version $V(s)=\min\{\ell(s),\max_aV(s^+_a)\}$ is not a contraction: for one state with a self-loop and $\ell=1$, every $V\le1$ is a fixed point.

Worked example. Start with $\pi_0$ = rest everywhere: $V^{\pi_0}=(10,9)$, $Q^{\pi_0}(1,\cdot)=(10,\,8.1)$, $Q^{\pi_0}(2,\cdot)=(9,\,10.1)$, so $\pi_1$ rests at home and harvests in the field, $V^{\pi_1}=(10,20)$. Then $Q^{\pi_1}(1,\cdot)=(10,18)$ gives $\pi_2$ = harvest everywhere, $V^{\pi_2}=(18,20)=V^\ast$, and $\pi_3=\pi_2$. Note $J(\pi_1)=J(\pi_0)=10$ for the start distribution $\mu=(1,0)$ although $\pi_1$ is strictly better in the field and $\pi_0$ is not optimal: equal returns for one initial distribution do not mean equal (or optimal) values at every state. The improvement theorem is statewise.

Undiscounted problems: transient chains and weighted norms

Total-cost problems without discount (Module 11's transient CMDP) need a different reason for uniqueness: termination. Let the states be split into transient states and an absorbing terminal state, and let $P$ now be the transition matrix among transient states only. Its rows sum to at most $1$ (the missing mass is the probability of terminating): $P$ is substochastic. Assume termination happens with probability $1$ from every state. Then $P^t\to0$, and the fundamental matrix

exists; the total cost is $V=Nc$ and the expected time to termination is $w=N\mathbf 1$. The sup-norm argument fails, because a row of $P$ may sum to $1$ (a state that cannot terminate in one step). A weighted norm repairs it.

Example. Two transient states: from state 1 stay with probability $0.5$ or move to state 2; from state 2 always terminate. Then $P=\begin{bmatrix}0.5&0.5\\0&0\end{bmatrix}$, $\|P\|_\infty=1$ (no sup-norm contraction), $N=\begin{bmatrix}2&1\\0&1\end{bmatrix}$ (from state 1: two visits to itself, one to state 2 on average), $w=(3,1)$ and $\beta=1-1/3=2/3$; indeed $Pw=(2,0)=w-\mathbf 1$. With unit costs, $V=N\mathbf 1=(3,1)$, the expected numbers of steps. Two related terms appear with average-cost criteria (Module 8): a recurrent class is a set of states that the chain never leaves once inside and in which every state is revisited with probability $1$; an MDP is unichain if every deterministic stationary policy induces a chain with exactly one recurrent class (plus possibly transient states), which makes the long-run average reward of a stationary policy independent of the start state.

From dynamic programming to learning. Dynamic programming needs the model $(P,r)$ and a table over all states and actions. Discretising $[0,1]^d$ with $m$ points per axis gives $m^d$ states (Section 1), so tables stop at a few dimensions. Reinforcement learning replaces the expectations by sampled transitions (Section 6), the tables by function approximators such as networks (Section 7), and the exact greedy step by a small gradient step on the policy (Section 5).

Practice — Distinguish an iterate from its error

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

5. Policy Gradients, Advantages & Trust Regions

Dynamic programming needs a model and a table. Policy-gradient methods need neither: they give the policy trainable parameters $\theta$ (for example the weights of a network) and climb $J(\theta):=J(\pi_\theta)$ by gradient ascent (Primer B), $\theta_{k+1}=\theta_k+\eta\,\hat g_k$. The exact gradient $\nabla J(\theta_k)$ is unknown; $\hat g_k$ is a sampled estimate computed from rollouts, random, and unbiased when $\mathbb E\,\hat g_k=\nabla J(\theta_k)$. The basic ingredient is the score $\nabla_\theta\log\pi_\theta(a\mid s)$: for the Bernoulli policy $\pi_\theta(1)=\sigma(\theta)$, with the logistic function $\sigma(\theta)=1/(1+e^{-\theta})$ and its derivative $\sigma'=\sigma(1-\sigma)$ (Section 7), it is $1-\sigma(\theta)$ for action $1$ (because $\partial_\theta\log\sigma=\sigma'/\sigma$) and $-\sigma(\theta)$ for action $0$ (because $\partial_\theta\log(1-\sigma)=-\sigma'/(1-\sigma)$); for a Gaussian policy $a\sim\mathcal N(m_\theta(s),\sigma^2)$ with a fixed standard deviation $\sigma$ (a number here, not the logistic function) and a network mean it is $(a-m_\theta(s))\nabla_\theta m_\theta(s)/\sigma^2$.

Worked example (one state, two actions). Let $\pi_\theta(1)=\sigma(\theta)=p$, with reward $1$ for action $1$ and $0$ for action $0$, and one-step episodes. Then $J=p$ and $\nabla J=p(1-p)$. The REINFORCE sample $g=r\,\partial_\theta\log\pi_\theta(a)$ equals $1-p$ with probability $p$ and $0$ otherwise, so $\mathbb Eg=p(1-p)$: unbiased. At $\theta=0$ ($p=\tfrac12$), $g\in\{0.5,0\}$ has variance $0.0625$; with the baseline $b=\tfrac12$, $g=(r-b)\,\partial_\theta\log\pi_\theta(a)$ equals $0.25$ for both actions, variance $0$. At $p=0.8$, no baseline gives variance $0.0064$ while the "natural" baseline $b=\bar r=0.8$ gives $0.0576$, nine times worse. An action-independent baseline preserves the score-gradient expectation, but only a well-chosen one reduces variance (Exercise E.4 finds the best one).

Score-function versus pathwise gradients. There are two ways to differentiate $\mathbb E_{x\sim p_\theta}[h(x)]$. The score-function (likelihood-ratio) estimator $\mathbb E[h(x)\nabla_\theta\log p_\theta(x)]$ needs samples and log-probabilities only, never $\nabla h$: it works when $h$ is a black box such as the real environment.

The pathwise (reparametrisation) estimator writes $x=g_\theta(\varepsilon)$ with noise $\varepsilon$ independent of $\theta$ and differentiates through, $\mathbb E[\nabla h(g_\theta(\varepsilon))\,\nabla_\theta g_\theta(\varepsilon)]$; it needs a differentiable $h$ (for example a learned dynamics model) and usually has lower variance.

Example. $x\sim\mathcal N(\theta,1)$, $h(x)=x^2$, $\mathbb Eh=\theta^2+1$: the score estimator averages $x^2(x-\theta)$, the pathwise one $2(\theta+\varepsilon)$; both have mean $2\theta$.

In code, one minimises the negative surrogate $-\sum_t\gamma^t\log\pi_\theta(a_t\mid s_t)\,\mathrm{sg}(\hat A_t)$ (its gradient is $-\hat g$ for one rollout of Step 6 above), where the stop-gradient $\mathrm{sg}(x)$ returns the value $x$ but has derivative $0$, so the advantage acts as a fixed weight; many implementations drop the factor $\gamma^t$, which generally gives a biased estimator with a different variance.

An entropy bonus $\eta\,\mathcal H[\pi_\theta(\cdot\mid s_t)]$, $\mathcal H[p]=-\sum_ap_a\log p_a$, is added to the maximised objective to keep the policy exploring, so it enters the minimised loss with a minus sign: $-\sum_t\gamma^t\big(\log\pi_\theta(a_t\mid s_t)\,\mathrm{sg}(\hat A_t)+\eta\,\mathcal H[\pi_\theta(\cdot\mid s_t)]\big)$.

Action-based versus parameter-based exploration. Action-based methods sample a new action from $\pi_\theta(\cdot\mid s_t)$ at every step. Parameter-based methods sample the parameters once per rollout, $\theta\sim\nu_\omega$ (for example $\mathcal N(\omega,\sigma^2I)$), run the deterministic policy $\pi_\theta$, and use the score of $\nu_\omega$: $\nabla_\omega\mathbb E[R]=\mathbb E_{\theta\sim\nu_\omega}\big[R(\theta)\nabla_\omega\log\nu_\omega(\theta)\big]$. Such methods, like random search with the finite-difference estimate $\hat g=\frac{\hat J(\theta+\sigma u)-\hat J(\theta-\sigma u)}{2\sigma}\,u$ along a random direction $u$, use only returns: a zeroth-order oracle (values, no gradients).

Example. From the uniform policy $\pi$ to "always harvest" $\pi'$ in the running example: $d^{\pi'}=(0.1,0.9)$ and $\pi'$ plays $b$, so $J(\pi')-J(\pi)=10\,\big(0.1\cdot(-0.275)+0.9\cdot1.225\big)=10.75=18-7.25$, exactly. Replacing the unknown $d^{\pi'}$ by the old $d^\pi$ gives the surrogate

where the second form needs the support condition $\pi(a\mid s)=0\Rightarrow\pi'(a\mid s)=0$ at every state with $d^\pi(s)\gt0$ (otherwise the ratio is undefined, and samples of $\pi$ never show the new actions). Under it the surrogate is computable from data of the old policy, exact at $\pi'=\pi$ and with the same gradient there. Its accuracy degrades as the policy moves: here $L_\pi(\pi')=7.25+10\,(0.55\cdot(-0.275)+0.45\cdot1.225)=11.25$ instead of $18$, and the cost surrogate predicts $2.25+10\,(0.55\cdot0.225+0.45\cdot0.725)=6.75$ instead of the true $J_c(\pi')=9$. With a budget $d=7$, the surrogate says "feasible" for a policy that violates the constraint. The error comes entirely from the changed state distribution, $(0.55,0.45)\to(0.1,0.9)$.

Example. For the Bernoulli policy, $F=p(1-p)$ and $g=p(1-p)$, so $F^{-1}g=1$ for every $\theta$. At $\theta=-4$ ($p=0.018$) the ordinary gradient is only $0.0177$ (a plateau), while the natural step with $\delta=0.01$ is $\sqrt{2\delta/F}=1.06$ in $\theta$: a fixed change in distribution, however flat the parametrisation. Softmax policies. For tabular softmax $\pi_\theta(a\mid s)\propto e^{\theta_{s,a}}$ one checks $F\,w=\nabla J$ for $w=A^{\pi_\theta}/(1-\gamma)$, so a natural-gradient step of size $\eta$ is the probability-space update $\pi_{k+1}(a\mid s)\propto\pi_k(a\mid s)\exp\big(\eta A^{\pi_k}(s,a)/(1-\gamma)\big)$: multiplicative weights on advantages, state by state (Agarwal, Kakade, Lee & Mahajan, JMLR 2021). Conjugate gradients. $F$ has $n^2$ entries for $n$ parameters and is never formed: TRPO and CPO solve $Fx=g$ by the conjugate-gradient method, which needs only products $v\mapsto Fv$ (two backward passes each) and drives the residual $g-Fx$ down in a handful of iterations.

Example ($\epsilon=0.2$). Reward, $\hat A=2$, $\varrho=1.5$: $\min(3,\,2.4)=2.4$, the gain from raising the action's probability is capped. $\hat A=-2$, $\varrho=1.5$: $\min(-3,-2.4)=-3$, a harmful move is charged in full. Cost, $\hat A_c=2$, $\varrho=0.5$: $\max(1,\,1.6)=1.6$, the credit for avoiding a costly action is capped; $\hat A_c=-2$, $\varrho=1.5$: $\max(-3,-2.4)=-2.4$, capped again. Clipping removes the incentive to move the ratio outside $[1-\epsilon,1+\epsilon]$, not the possibility; implementations also monitor the KL.

Example. Rewards $1,0,2$, then termination; $V=(2,\,1.5,\,1)$; $\gamma=0.9$. Residuals: $\delta_0=1+1.35-2=0.35$, $\delta_1=0+0.9-1.5=-0.6$, $\delta_2=2-1=1$. With $\lambda=0.8$ ($\gamma\lambda=0.72$): $\hat A_2=1$, $\hat A_1=-0.6+0.72=0.12$, $\hat A_0=0.35+0.72\cdot0.12=0.436$. With $\lambda=1$: $\hat A_0=0.35-0.54+0.81=0.62=(1+0+0.81\cdot2)-2$; with $\lambda=0$: $\hat A_0=0.35$.

Practice — Differentiate probabilities and respect their geometry

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

6. Q-Learning, Actor-Critic, Entropy Regularisation, Model-Based & Offline RL

Section 4 solved Bellman equations with a known model; Section 5 improved policies with sampled gradients. Practical algorithms combine the two: they learn value functions from sampled transitions and use them to improve a policy, sometimes with a learned model, sometimes from a fixed dataset. This section is a map of that landscape with the few formulas the modules use.

Example. $Q(s,a)=2$, $r=1$, $\gamma=0.9$, $\max_{a'}Q(s',a')=3$, $\alpha=0.1$: target $1+2.7=3.7$, TD error $1.7$, new value $2.17$. DQN (Mnih et al., Nature 2015) replaces the table by a network $Q_\phi$, samples minibatches from a replay buffer, and minimises $\big(r+\gamma\max_{a'}Q_{\phi^-}(s',a')-Q_\phi(s,a)\big)^2$ with a target network $\phi^-$; the maximum over noisy estimates is biased upwards, which double Q-learning reduces by selecting and evaluating the maximiser with different networks. Safety variants change only the target, e.g. $(1-\gamma)\ell(x)+\gamma\min\{\ell(x),\max_{u'}Q(x^+,u')\}$ for the discounted safety equation of Section 4.

Uncertainty-weighted blending. A hybrid controller can mix a trusted control prior with the RL action, $a^{\rm ref}=(1-\lambda)a^{\rm prior}+\lambda a^{\rm RL}$, with a weight that falls as the critics disagree, e.g. $\lambda=\mathrm{clip}\big((u_{\rm hi}-u)/(u_{\rm hi}-u_{\rm lo}),0,1\big)$ with $u$ the standard deviation of the ensemble's $Q$-estimates. With $u_{\rm lo}=0.1$, $u_{\rm hi}=0.5$: $u=0.2$ gives $\lambda=0.75$, and $u\ge0.5$ gives $\lambda=0$ (pure prior). Clipping keeps $\lambda\in[0,1]$, so $a^{\rm ref}$ is always a convex combination of the two actions.

Entropy regularisation, softmax and soft Bellman equations

Example. $q=(1,2,4)$: $\alpha=1$ gives $\mathrm{softmax}=(0.042,0.114,0.844)$ and $\mathrm{LSE}=4.170\in[4,\,5.099]$; $\alpha=0.5$ gives $\mathrm{LSE}=4.010$; $\alpha=5$ gives $(0.247,0.302,0.451)$ and $\mathrm{LSE}=7.986\in[4,\,9.493]$.

Model-based RL and uncertainty

A learned dynamics model $\hat f_\phi(s,a)\approx\mathbb E[s'\mid s,a]$, or a predictive distribution $\hat p_\phi(s'\mid s,a)$, is fitted by regression on observed transitions and then used to plan (model-predictive control: optimise an action sequence over a horizon on the model, apply the first action, re-plan), to generate imagined transitions for a model-free learner (Dyna), or to differentiate through (pathwise gradients). Errors compound along long model rollouts, and a planner actively seeks the places where the model is wrong in its favour.

Example ($B=3$, one dimension). Near the data the members predict means $(1.0,1.2,0.8)$ with variances $(0.04,0.05,0.03)$: aleatoric $0.04$, epistemic $0.027$. Far from the data they predict $(1.0,2.0,-0.5)$: the epistemic part jumps to $1.056$. Optimism in model-based RL plans with an upper confidence reward, or jointly over policies and the most favourable model still consistent with the data (Section 1's principle), and epistemic uncertainty as intrinsic reward sends the agent where the model is unsure: useful for learning, and exactly where it is risky to go. Latent world models (Dreamer, Hafner et al., ICLR 2020) encode observations $o_t$ (e.g. images) into a learned latent state $z_t$, learn latent dynamics $z_{t+1}\sim p(\cdot\mid z_t,a_t)$ with reward and cost heads, and train the policy on imagined latent rollouts; a latent state is a learned representation for prediction and control, not a physical state. Approximate weight posteriors such as SWAG (a Gaussian fitted to the iterates of stochastic gradient descent) are another cheap source of epistemic uncertainty.

Offline RL, reward models and safety filters

Offline RL learns from a fixed dataset $\mathcal D=\{(s,a,r,c,s')\}$ collected by unknown behaviour policies $\pi_\beta$, with no further interaction. The central problem is distribution shift: the learned policy takes actions that are rare or absent in $\mathcal D$, their values are extrapolations of the function approximator, and a maximising policy seeks exactly the actions whose values are overestimated. Because no new data arrive, these errors are never corrected. The remedies are pessimistic: push down values outside the data (conservative Q-learning, Kumar et al., NeurIPS 2020), keep the policy close to $\pi_\beta$, or back up values only through dataset actions. A tutorial overview is Levine et al. (Further Reading).

Reward models and RLHF. From pairwise human preferences between a preferred response $y_w$ and a rejected response $y_l$ to a prompt $x$, the Bradley–Terry model sets $\mathbb P(y_w\succ y_l\mid x)=\sigma\big(R_\phi(y_w,x)-R_\phi(y_l,x)\big)$ with the logistic function $\sigma(z)=1/(1+e^{-z})$ (Section 7), and $\phi$ is fitted by minimising $-\mathbb E\big[\log\sigma(R_\phi(y_w,x)-R_\phi(y_l,x))\big]$ (Christiano et al., NeurIPS 2017, learn rewards from preferences this way for Atari and simulated robots). A score difference of $1$ means probability $\sigma(1)=0.731$ and loss $0.313$; a difference of $-1$ costs $1.313$. The policy (a language model: the prompt plays the state, the response the action) is then fine-tuned with PPO to maximise the learned reward minus a KL penalty to a reference model (Ziegler et al., 2019). Safe RLHF fits a cost model the same way. A learned score is a ranking signal: a cost score of $0.7$ is not a $70\%$ (or any) probability of harm unless it has been calibrated separately.

Safety filters and shields. A filter sits between the learner and the plant: it passes the proposed action if a certificate says it is safe and otherwise replaces it by a certified safe action (a backup controller's action, or the closest safe action from a small optimisation problem). A shield does the same against a finite-state safety specification. The learner can be any of the algorithms above; the guarantee comes from the certificate (Module 10).

Practice — Understand the update and its data assumptions

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

7. Neural Networks: Layers, Activations & Backpropagation

A neural network is a composition of two kinds of simple maps: affine layers that mix coordinates, and scalar nonlinearities applied to each coordinate separately. Every certificate in Modules 12–15 exploits exactly this structure; every RL agent above uses it to represent policies, critics and models.

Worked example (used throughout Sections 7–9 and in the explorer). The 2-2-1 ReLU network with

At $x=(1,2)$: $v_1=(2,-1)$, $z_1=(2,0)$, $f=2-0-1=1$. The lines $x_1+x_2=1$ and $x_1=x_2$ (where a neuron switches) cut the plane into four regions; on each, $f$ is affine. A ReLU network is continuous and piecewise affine.

A scalar $\varphi$ is slope-restricted in $[\alpha,\beta]$ if $\alpha\le\frac{\varphi(u)-\varphi(w)}{u-w}\le\beta$ for all $u\ne w$: every chord, not only every derivative, has slope in the interval (Module 12's key assumption; Lipschitz continuity: Primer B). The derivatives in the table follow from the quotient rule: $\sigma'=e^{-v}/(1+e^{-v})^2=\sigma(1-\sigma)$, maximal $\tfrac14$ at $v=0$; $\tanh'=(\cosh^2-\sinh^2)/\cosh^2=1-\tanh^2$ with $\cosh v=(e^v+e^{-v})/2$, $\sinh v=(e^v-e^{-v})/2$; and $\frac{d}{dv}\log\cosh v=\tanh v$. MaxMin ($\mathrm{MaxMin}(3,-1)=\mathrm{MaxMin}(-1,3)=(3,-1)$) is not coordinatewise, so slope restriction does not apply; on each region it permutes its inputs, so it preserves Euclidean norms of gradients, which is why Lipschitz-by-design networks use it (Anil, Lucas & Grosse, ICML 2019). Householder activations generalise it: for a unit vector $u$, $z\mapsto z$ if $u^{\top}z\gt0$ and $z\mapsto(I-2uu^{\top})z$ (a reflection) otherwise; with $u=(1,-1)/\sqrt2$ this is exactly MaxMin.

Networks inside RL. A policy network maps a state to the parameters of an action distribution: logits followed by a softmax for discrete actions, a mean $m_\theta(s)$ and a log-standard-deviation for Gaussian actions, or directly an action $\mu_\theta(s)$ for a deterministic policy (often squashed by $\tanh$ into the action bounds); $\theta$ collects all its weights. Critics $V_\phi(s)$, $Q_\phi(s,a)$ and dynamics models are networks too. Shared parameters couple states: a gradient step that fixes $V_\phi$ at one state also changes it elsewhere (generalisation, and interference). And since a parametrised family rarely contains $V^\pi$ exactly, the Bellman equation cannot hold everywhere: training minimises a mean squared Bellman residual that stays positive, and the learned "value function" is an approximation, not a solution.

Penalties versus certificates. Weight decay ($L_2$ regularisation) adds $\lambda\sum_k\|W_k\|_F^2$ and shrinks weights; a gradient penalty adds $\mathbb E\|\nabla_xf_\theta(x)\|^2$ at sampled inputs and flattens the network where it is evaluated. Both make large slopes unlikely but prove nothing about inputs that were not sampled. A hard certificate, such as a proven Lipschitz bound (LipSDP, Module 12) or an architecture that is Lipschitz by construction (Module 13), holds for every input. Margin-based training: Lipschitz-margin training adds $\sqrt2\,c\,L$ to every non-target logit before the cross-entropy; the loss then stays small only if the true logit beats the others by more than $\sqrt2cL$, a margin that Section 9 converts into a certified radius $c$. Raising the non-target logits makes training demand larger margins. Schedules: some losses change during training, e.g. Module 15's interval-bound-propagation (IBP) training (Section 9) minimises $\kappa\,\ell(z_K,y)+(1-\kappa)\,\ell(\hat z_K,y)$ with $z_K$ the logits of the last layer $K$, $\hat z_K$ worst-case logits over the perturbation set, and the weight $\kappa$ annealed (moved gradually) from $1$ to $\tfrac12$.

Gradient descent and backpropagation. Training runs (stochastic) gradient descent on $\hat R$ (Primer B), usually with minibatch gradient estimates; one pass over the data is an epoch. The problem is non-convex, so there is no guarantee of a global minimum. The gradient is computed by backpropagation (Rumelhart, Hinton & Williams, Nature 1986), the multivariable chain rule (Primer B) organised backwards: store all $v_k,z_k$ in a forward pass, then, starting from $\bar f=\partial\ell/\partial f$, apply for $k=l+1,\dots,1$ the weight and bias formulas, and for $k=l+1,\dots,2$ the recursion for $\delta_{k-1}$:

where $\delta_k=\partial\ell/\partial v_k$ for the hidden layers $k\le l$ and $\delta_{l+1}=\partial\ell/\partial f$ for the affine output layer (write $v_{l+1}:=f$), and $\odot$ is the coordinatewise product. There is no $v_0$: the input is not passed through an activation, so the recursion stops at $\delta_1$. One more product gives the gradient with respect to the input, $\partial\ell/\partial x=W_1^{\top}\delta_1$, which attacks use (Section 9). The walkthrough runs one pass on the worked example.

Practice — Trace a forward pass before differentiating

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

8. Convolutions, Residual, Recurrent & Equilibrium Layers

Four structures recur in the certified-network modules. All are still built from affine maps and activations; what changes is the pattern inside the weight matrices, or where a layer's input comes from.

Example. $x=(1,2,3,4)$, $w=(1,-1)$, no padding, stride $1$: $y=(x_1-x_2,\,x_2-x_3,\,x_3-x_4)=(-1,-1,-1)$ (length $\lfloor(4-1-1)/1\rfloor+1=3$), i.e. $y=Tx$ with $T=\begin{bmatrix}1&-1&0&0\\0&1&-1&0\\0&0&1&-1\end{bmatrix}$. To keep the length $4$ circularly, append only $x_1$ on the right (symmetric circular padding $p=1$ would give five outputs): then $y_4=x_4-x_1=3$ and $T$ is a $4\times4$ circulant matrix. Stride $2$ in the unpadded example keeps $y_1,y_3$, i.e. rows $1$ and $3$ of $T$, which are not a Toeplitz matrix. Invertible downsampling ("space-to-depth") moves each $2\times2$ block of an image into $4$ channels: the spatial size halves but nothing is lost. It only rearranges entries, so it is a permutation matrix, orthogonal, norm-preserving and exactly $1$-Lipschitz; Lipschitz-by-design networks use it instead of strided convolutions.

Uses and variants. System identification fits a dynamic model, such as a recurrent network, to measured input–output data; an observer is a dynamical system that estimates the state from measured outputs; both are natural jobs for recurrent networks. An echo state network keeps random, fixed recurrent weights (a "reservoir") and trains only the linear readout $C$. It needs the echo state property: the state forgets its initial condition. If $\varphi$ is $1$-Lipschitz and $\|A\|\lt1$, two runs with the same inputs satisfy $\|h_{t+1}-h'_{t+1}\|\le\|A\|\,\|h_t-h'_t\|$, a contraction, so the dependence on $h_0$ fades geometrically. (For the scalar reservoir $h_{t+1}=\tanh(0.8h_t+u_t)$ with input $u_t=0$, started at $h_0=\pm2$ (initial gap $4$), the gap after $1,2,3$ steps is $1.84,\,1.26,\,0.93$ and keeps shrinking.) Two further sequence and structure models appear in passing: a causal transformer maps a sequence of tokens (vectors encoding states, actions or return targets) to an output at each position using only earlier positions, through attention (averages of earlier tokens' features with softmax weights); a graph neural network updates each node's feature from its own and its neighbours', $h_i\leftarrow\varphi\big(W_{\rm self}h_i+\sum_{j\in\mathcal N(i)}W_{\rm msg}h_j\big)$, with the same weights at every node.

Example. $z=\tanh(0.5z+1)$: from $z^0=0$ the iterates are $0.7616,\,0.8811,\,0.8938,\,0.8951,\,0.8952$, converging to $z^\ast\approx0.8952$. Every feedforward network is an implicit layer with triangular $W$. Stack the hidden vectors, $z=(z_1,z_2)$ for two hidden layers: then $z=\varphi(Wz+W_0x+\beta)$ with

Because $W$ is strictly block lower triangular (layer $k$ only receives layer $k-1$), the equation is solved by forward substitution in one pass: no iteration and no well-posedness question. A genuine equilibrium layer has a non-triangular $W$ that couples neurons of the same layer; in a recurrent equilibrium network (REN) such an equation is solved within each time step while the recurrence $h_t\to h_{t+1}$ runs across time steps.

Practice — Recognise compositions, skip paths and recurrence

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

9. Classifiers, Margins & Adversarial Examples

A classifier can be right on a test image and wrong on the same image with an invisible change of every pixel. Certified robustness asks for a proof that no change within a given size can alter the decision. The two ingredients are how far ahead the winning class is (the margin) and how fast the network can change (a Lipschitz bound).

Example. Logits $(2.0,\,0.5,\,1.2)$: the prediction is class 1 with margin $2.0-1.2=0.8$; the softmax probabilities are $(0.598,\,0.133,\,0.269)$. A logit is a score, not a probability, and even the softmax output $0.598$ is not "the chance the prediction is right" unless the model has been calibrated.

Worked example. For the 2-2-1 network of Section 7, ReLU slopes lie in $[0,1]$, so $L\le\|W_2\|\,\|W_1\|=\sqrt5\cdot\sqrt2=\sqrt{10}\approx3.162$ (spectral norms, Primer A). At $x=(2,1)$, $f=-1$: certified radius $1/\sqrt{10}\approx0.316$, and here the true distance to the decision boundary is also $0.316$, because the network's local slope $\|(-1,3)\|=\sqrt{10}$ equals the global bound. At $x=(0.5,2.5)$, $f=+1$: the same certified radius $0.316$, but the true distance is $0.707$, since the local slope is only $\|(1,1)\|=\sqrt2$. A global bound is valid everywhere but loose where the network is flat; a local Lipschitz constant on a ball around $x$ can certify more but must be recomputed for every input (Module 15). The explorer below shows the certified radius and a numerical estimate of the true distance for any point.

Example. Five test points at $\epsilon=0.3$: four are classified correctly, with certified radii $0.5,\,0.2,\,0.4,\,0.1$; an attack breaks only the point with radius $0.1$. Clean accuracy $80\%$, certified accuracy $40\%$ (radii $0.5$ and $0.4$ exceed $\epsilon$), adversarial accuracy $60\%$; the true robust accuracy lies in $[40\%,60\%]$, because the point with radius $0.2$ survived the attack but is not certified.

Attacks and adversarial training. PGD (projected gradient ascent) maximises the loss over the ball: $\delta\leftarrow\Pi_{\{\|\delta\|\le\epsilon\}}\big(\delta+\eta\,s\big)$ with the ascent direction $s=\mathrm{sign}\big(\nabla_\delta\ell(f(x+\delta),y)\big)$ for $\ell_\infty$ (the projection clips each coordinate to $[-\epsilon,\epsilon]$) or the normalised gradient for $\ell_2$ (the projection rescales onto the ball). A successful attack is a counterexample; a failed one proves nothing, since a stronger attack may exist. Adversarial training (Madry et al., ICLR 2018) solves $\min_\theta\mathbb E\big[\max_{\|\delta\|\le\epsilon}\ell(f_\theta(x+\delta),y)\big]$ with the inner maximum approximated by PGD: it trains on approximately worst-case perturbations and raises adversarial accuracy, but, like weight penalties $\lambda\sum_k\|W_k\|_F^2$, it proves nothing. Certified training (training against bounds, Module 15) and Lipschitz-by-design architectures (Module 13) produce networks that come with certificates.

Input normalisation. Networks usually see $\tilde x=D^{-1}(x-m)$ with per-channel means $m$ and standard deviations $s$, $D=\mathrm{diag}(s)$ with every $s_c\gt0$. If $g$ is $L$-Lipschitz in normalised space, then $f(x)=g(D^{-1}(x-m))$ is $L\max_c(1/s_c)$-Lipschitz in pixel space, because $\|D^{-1}(x-x')\|\le\max_c(1/s_c)\,\|x-x'\|$. A radius certified in normalised space therefore shrinks by the factor $\min_cs_c$ in pixel space: for CIFAR-10's standard deviations of about $(0.247,0.243,0.261)$ the Lipschitz bound grows by $1/0.243\approx4.1$. Always state the input space of a radius.

Bound propagation (preview of Module 15). Push a whole set of inputs through the layers. Interval bound propagation uses boxes: if $x$ lies in the box with centre $c$ and half-widths $r$, then each coordinate of $Wx+b$ lies in $\big[Wc+b-|W|r,\ Wc+b+|W|r\big]$ ($|W|$ taken entrywise), and a monotone activation maps an interval $[a,b]$ to $[\varphi(a),\varphi(b)]$. If the lower bound of the margin over the input box is positive, every input in the box is classified correctly. For the worked network and the $\ell_\infty$ ball of radius $0.2$ around $(1,2)$: $v_1\in[1.6,2.4]\times[-1.4,-0.6]$, $z_1\in[1.6,2.4]\times\{0\}$ and $f\in[0.6,1.4]\gt0$: certified. The exact image of a box under an affine map is a zonotope $\{c+G\epsilon:\epsilon\in[-1,1]^m\}$ (generator matrix $G$), generally not a box; replacing it by its bounding box is where interval bounds lose tightness. Bounds are sound (never wrong) but may be too loose to certify a point that is in fact robust.

Practice — Separate a margin, a certificate and an attack

Easy checks the basic operation; Medium connects steps; Hard asks you to justify a conclusion or identify a limitation. Each solution explains why the steps work.

Interactive: Value Iteration & a Tiny Network

Two panels, both computed live. Panel A runs value iteration (Section 4) on a slippery cliff gridworld and reports how safe the greedy policy of the current iterate is. Panel B draws the 2-2-1 network of Section 7, its decision boundary, and the certified radius of Section 9 at a point you choose.

What to look for (A).

1. With the defaults, press "One sweep" repeatedly: the true error shrinks at least by the factor $\gamma$ per sweep and stays below both bounds; the arrows settle after about $11$ sweeps, long before the values stop changing.
2. Stopping early is not harmless: after $6$ sweeps the greedy policy falls off the cliff with probability $0.21$, after convergence with $0.07$.
3. Slip $0$: the optimal path hugs the cliff edge; slip $0.1$: it detours through the upper rows, trading length for safety.
4. Step reward $-0.3$ and slip $0.3$: the optimal policy walks into the cliff (falls with probability $0.91$). When every step is expensive, ending the episode early is "optimal": a failure penalty enforces safety only if it is large compared with the rewards at stake, the threshold $p^\star$ of Module 7.

How the bounds are computed (B). The Jacobian of $f$ is $W_2\,\mathrm{diag}(\varphi'(v))\,sW_1$ with slopes $\varphi'\in[0,1]$ for ReLU and tanh. Its norm is a convex function of the slope vector, so over the box $[0,1]^2$ it is largest at a corner: the all-pattern bound $L=\max_{d\in\{0,1\}^2}\|W_2\,\mathrm{diag}(d)\,sW_1\|$, which the mean-value inequality along segments turns into a Lipschitz bound. The product bound $\|W_2\|\,\|sW_1\|$ is never smaller. For ReLU, when the two neuron lines cross, all four patterns occur as regions and the all-pattern bound is the exact Lipschitz constant.

What to look for.

1. Worked example: at $x=(0.5,2.5)$ the certified radius is $0.316$ but the true distance $0.707$; move to $x=(2,1)$ and the two coincide (Section 9).
2. The green disk never crosses the black curve, for any network, scale or activation: that is the theorem.
3. Raising $s$ scales $L$ but also changes the margin $|f(x)|$, so the certified radius can grow, shrink or stay the same: at the default point, $s=1$ gives $0.316$ and $s=2$ gives $0.474$; compare both quantities.
4. With tanh the boundary bends and the slopes vary continuously in $(0,1]$, but the all-pattern bound stays valid and, for invertible $W_1$, exact: the two pre-activations vary independently, so each corner slope pair is attained or approached (at $s=1$, $x=(0.5,0.5)$ both pre-activations vanish, the gradient is $(-1,3)$ and its norm is $L=\sqrt{10}$). A tanh network can also have no boundary at all: for the worked network with $b_2=3$, $f=3+\tanh v_1-2\tanh v_2\gt0$ for every input, whatever $s$, and the readout says so.
5. Random networks: for the first ten seeds the product bound is $1$–$64\%$ above the all-pattern bound, the price of multiplying norms of layers that do not align (Module 12).

Exercises

These cumulative problems connect several ideas. If a step feels too large, return to the section practice route, where each topic has an Easy, Medium and Hard problem with a separate hint, worked solution and prerequisite review link.

Further Reading

Flashcards