9. Trust Regions, CPO & Modern Safe Policy Optimization
Performance difference, CPO and its closed form, projections and first-order methods, model-based and offline safe RL, benchmarks and 2026 SOTA
This module assumes:
- CMDPs, discounted costs, occupancy measures, and Bellman-flow constraints (Module 8)
- Value functions, Bellman equations, and advantages (Primer E)
- Lagrangian duality, Slater's condition, and KKT conditions (Module 2)
- Policy gradients, Fisher information, and trust regions (Primer E)
- Gradients, Hessians, and multivariable Taylor approximations (Primer B)
- KL divergence, total variation, and Pinsker's inequality (Primer C)
- Positive definite matrices, quadratic forms, and ellipsoids (Primer A)
- Convexity, Jensen's inequality, and convex conjugates (Primer B)
- GP confidence bounds and calibrated uncertainty (Module 3)
- Viability kernels and actions that preserve feasibility (Module 7)
First build the core calculation: advantages and performance difference, surrogate error, the constrained update, the worked CPO calculation. Try the Easy practice as you go, then the Medium applications. Next compare projection, penalty and barrier methods. Model-based, offline and benchmark sections are a second pass connecting that shared update problem to applications.
The Hard practice checks proofs and assumptions. The original longer exercises remain for a deeper pass. If a calculation stalls, follow its prerequisite review link and return after practising that skill.
Check advantages, dot products and quadratic constraints before reading the CPO formulas.
Show hint
An advantage subtracts the old state value; a quadratic trust region bounds the size of a parameter step.
Show worked check
If $Q^\pi(s,a)=5$ and $V^\pi(s)=3$, then $A^\pi(s,a)=2$. For $g=(1,2)$ and $x=(0.1,0.2)$, the linearized reward change is $g^\top x=0.5$. If $H=I$ and $\tfrac12x^\top Hx\le0.125$, allowable steps have Euclidean length at most $0.5$. Review advantages, dot products, and quadratic forms.
Book contents · Apply this chapter to a real decision · Glossary
1. The Performance Difference Lemma
Module 8 solved CMDPs in the space of occupancy measures, where the problem is a linear program and duality is exact (Module 8). Deep safe RL cannot work there: the policy is a network $\pi_\theta$ (see Primer E), the state space is continuous, and every quantity has to be estimated from trajectories of the current policy. Policy search therefore moves in small steps $\pi_k\to\pi_{k+1}$, and every step must answer two questions using data of $\pi_k$ only: how much will the return improve, and how much will the cost grow? This module is built on one identity that answers both exactly but is not computable (the performance difference lemma), one inequality that answers them conservatively given a valid global advantage bound (the trust-region bound behind CPO), and the family of algorithms that optimise the resulting surrogate problem.
The network maps a state to action probabilities (or to a mean and covariance for continuous actions); $\theta$ collects its trainable weights. In KL, logarithms are natural, $0\log(0/q)=0$, and positive mass divided by zero gives infinite KL. The support is the set of actions with positive probability. These conventions explain why likelihood ratios and finite-KL updates require compatible support.
Reference — notation changes across papers
Statement. $$J(\pi')-J(\pi)=\frac{1}{1-\gamma}\ \mathbb E_{s\sim d^{\pi'},\ a\sim\pi'(\cdot\mid s)}\big[A^{\pi}(s,a)\big].$$ In words. The gain of the new policy is the old policy's advantage, accumulated along the new policy's trajectories (Kakade & Langford, ICML 2002). The same identity holds for the cost: $J_c(\pi')-J_c(\pi)=\frac{1}{1-\gamma}\mathbb E_{d^{\pi'},\pi'}[A_c^\pi]$.
Why each assumption matters. Bounded rewards and $\gamma\lt1$ make $V^\pi$ bounded, which kills the tail of a telescoping sum and allows exchanging sums and expectations. The same $\mu$: otherwise the extra term $\mathbb E_{s\sim\mu'}V^\pi(s)-\mathbb E_{s\sim\mu}V^\pi(s)$ appears. Stationarity of $\pi$ makes $A^\pi$ a fixed function; $\pi'$ may in fact be arbitrary (even history-dependent) if the right-hand side is written as the trajectory expectation $\mathbb E_{\tau\sim\pi'}[\sum_t\gamma^tA^\pi(s_t,a_t)]$.
Step 1 (advantage as a TD residual). Along a trajectory of $\pi'$, the next state has the conditional law $P(\cdot\mid s_t,a_t)$ no matter which policy chose $a_t$. Since $Q^\pi(s_t,a_t)=\mathbb E[r(s_t,a_t)+\gamma V^\pi(s_{t+1})\mid s_t,a_t]$, the tower property gives (see Primer C)
Step 2 (telescoping). Multiply by $\gamma^t$ and sum up to a horizon $T$; the value terms cancel pairwise:
Step 3 (the tail vanishes). Take expectations in Step 2 (using Step 1 on the left) and let $T\to\infty$. No convergence theorem is needed, because every tail is small on every trajectory: $|\gamma^TV^\pi(s_T)|\le\gamma^Tr_{\max}/(1-\gamma)$, and since $|r|\le r_{\max}$ and $|A^\pi|\le|Q^\pi|+|V^\pi|\le2r_{\max}/(1-\gamma)$, the parts of $\sum_t\gamma^tr_t$ and $\sum_t\gamma^tA^\pi(s_t,a_t)$ after time $T$ are at most $r_{\max}\gamma^T/(1-\gamma)$ and $2r_{\max}\gamma^T/(1-\gamma)^2$ in absolute value (geometric series). A bound that holds for every trajectory also bounds the expectation, and all three bounds tend to $0$:
Step 4 (occupancy form). Write the expectation state by state: $\sum_t\gamma^t\,\mathbb E[A^\pi(s_t,a_t)]=\sum_s\big(\sum_t\gamma^t\mathbb P(s_t=s\mid\pi')\big)\sum_a\pi'(a\mid s)A^\pi(s,a)=\frac{1}{1-\gamma}\mathbb E_{s\sim d^{\pi'},a\sim\pi'}[A^\pi(s,a)]$. $\square$
Corollary (policy improvement theorem, Primer E). If $\mathbb E_{a\sim\pi'}[A^\pi(s,a)]\ge0$ at every state, every term of the expectation is non-negative, so $J(\pi')\ge J(\pi)$. The greedy policy of policy iteration satisfies this condition. Equality $J(\pi')=J(\pi)$ for one $\mu$ does not prove optimality ($\mu$ may never reach the states where improvement is possible); the optimality test is statewise, $\max_aQ^\pi(s,a)=V^\pi(s)$ for every $s$.
The surrogate: same advantage, old state distribution
The lemma is exact but not computable before deploying $\pi'$: it needs states from $d^{\pi'}$. The obvious approximation keeps the advantage and swaps in the state distribution we do have samples from.
Let $\pi_\theta$ be differentiable in $\theta$ and $\pi_k=\pi_{\theta_k}$. For finite MDPs write distributions as column vectors and let $[P_\pi]_{s',s}=\sum_aP(s'\mid s,a)\pi(a\mid s)$ (each column sums to one; Exercise 9.1 uses the transpose, acting on value vectors). The state distribution at time $t$ is $p_t=P_\pi^t\mu$, so $d^\pi=(1-\gamma)\sum_t\gamma^tP_\pi^t\mu$ satisfies $d^\pi=(1-\gamma)\mu+\gamma P_\pi d^\pi$, i.e. $d^{\pi_\theta}=(1-\gamma)(I-\gamma P_{\pi_\theta})^{-1}\mu$ (Section 2 shows the inverse exists). This is a differentiable function of $\theta$, because $P_{\pi_\theta}$ is linear in the probabilities $\pi_\theta$ and matrix inversion is differentiable. Apply the lemma with $\pi=\pi_k$, $\pi'=\pi_\theta$ and write it as a double sum:
Differentiate at $\theta=\theta_k$ with the product rule (see Primer B). The term in which $d^{\pi_\theta}$ is differentiated is multiplied by $\sum_a\pi_k(a\mid s)A^{\pi_k}(s,a)=\sum_a\pi_k(a\mid s)Q^{\pi_k}(s,a)-V^{\pi_k}(s)=0$ (the advantage has zero mean under its own policy, by the definition of $V^{\pi_k}$), so it vanishes:
The error is second order because of its product form: in the key equation above, $J(\pi_\theta)-J(\pi_k)-L_{\pi_k}(\pi_\theta)=\frac{1}{1-\gamma}\sum_s\big(d^{\pi_\theta}(s)-d^{\pi_k}(s)\big)\bar a(s)$ with $\bar a(s)=\sum_a\big(\pi_\theta(a\mid s)-\pi_k(a\mid s)\big)A^{\pi_k}(s,a)$ (zero mean again). Differentiability at $\theta_k$ makes each factor $O(\|x\|)$ (at most a constant times $\|x\|$) for small $x=\theta-\theta_k$, so the product is $O(\|x\|^2)$ (Primer 0).
Using $\nabla\pi=\pi\nabla\log\pi$ gives the policy gradient theorem, $\nabla_\theta J=\frac{1}{1-\gamma}\mathbb E_{s\sim d^{\pi_k},a\sim\pi_k}[\nabla_\theta\log\pi_\theta(a\mid s)A^{\pi_k}(s,a)]$. So the surrogate agrees with the true objective to first order: the vector $g=\nabla_\theta L_{\pi_k}(\pi_\theta)|_{\theta_k}$ that CPO uses is the policy gradient. The same argument gives $b=\nabla_\theta L_{c,\pi_k}(\pi_\theta)|_{\theta_k}=\nabla_\theta J_c(\pi_\theta)|_{\theta_k}$. The remaining error is second order: how far the state distribution drifts, which is what Section 2 bounds.
2. Trust-Region Bounds for Return and Cost
The surrogate is useful only if we know how wrong it can be. Achiam et al. bound the error term above by the average policy change under the old state distribution. That single design choice (averaging over $d^\pi$ instead of taking a maximum over states, as TRPO's theory did) is what makes the bound match the trust region used in practice.
In words. Estimate the change with the surrogate, then subtract a penalty proportional to how much the policy moves on average over the states the old policy visits. The factor $2\gamma/(1-\gamma)$ is the worst-case amplification of a one-step policy change into a change of the discounted state distribution.
Why each assumption matters. Finiteness is only for the matrix identity in the proof. $\epsilon^{\pi'}$ depends on the new policy, so the bound is evaluated after a candidate is proposed (or $\epsilon^{\pi'}\le\max_{s,a}|A^\pi(s,a)|$ is used). The expectation is over $d^\pi$: this is the point of the theorem.
Step 1 (vector form). With $\bar a(s)=\mathbb E_{a\sim\pi'}[A^\pi(s,a)]$, the lemma reads $J(\pi')-J(\pi)=\frac{1}{1-\gamma}\langle d^{\pi'},\bar a\rangle$.
Step 2 (add and subtract the old distribution). $\langle d^{\pi'},\bar a\rangle=\langle d^{\pi},\bar a\rangle+\langle d^{\pi'}-d^\pi,\bar a\rangle$. The first term is exactly $(1-\gamma)L_\pi(\pi')$.
Step 3 (Hölder with $p=1$, $q=\infty$; Primer A). $|\langle d^{\pi'}-d^\pi,\bar a\rangle|\le\sum_s|d^{\pi'}(s)-d^\pi(s)|\,|\bar a(s)|\le\|d^{\pi'}-d^\pi\|_1\,\|\bar a\|_\infty=\|d^{\pi'}-d^\pi\|_1\,\epsilon^{\pi'}$ (bound each $|\bar a(s)|$ by the largest one). (Achiam et al. remark that other Hölder pairs could give other bounds.)
Step 4 (how far can the state distribution drift?). Let $P_\pi(s'\mid s)=\sum_aP(s'\mid s,a)\pi(a\mid s)$, a column-stochastic matrix, so that $d^\pi=(1-\gamma)(I-\gamma P_\pi)^{-1}\mu$. Put $G=(I-\gamma P_\pi)^{-1}$, $\bar G=(I-\gamma P_{\pi'})^{-1}$, $\Delta=P_{\pi'}-P_\pi$. Then $G^{-1}-\bar G^{-1}=\gamma\Delta$; multiplying by $\bar G$ on the left and $G$ on the right gives the resolvent identity $\bar G-G=\gamma\bar G\Delta G$, hence
The induced 1-norm of a matrix is its maximal absolute column sum, so a column-stochastic matrix has $\|P_{\pi'}\|_1=1$ (Primer A). With $A=\gamma P_{\pi'}$ and $S_N=I+A+\cdots+A^N$, multiplying out gives $(I-A)S_N=I-A^{N+1}$, and $\|A^{N+1}\|_1\le\gamma^{N+1}\to0$; so $I-A$ is invertible with the matrix geometric (Neumann) series $\bar G=\sum_{t\ge0}\gamma^tP_{\pi'}^t$ (Primer 0). By the triangle inequality and submultiplicativity, $\|\bar G\|_1\le\sum_t\gamma^t\|P_{\pi'}\|_1^t=\frac{1}{1-\gamma}$. And
where $\sum_{s'}P(s'\mid s,a)=1$ was used after the triangle inequality. Together (Lemma 3 of the paper): $\ \|d^{\pi'}-d^\pi\|_1\le\frac{2\gamma}{1-\gamma}\,\mathbb E_{s\sim d^\pi}\big[D_{\mathrm{TV}}(\pi'\|\pi)[s]\big]$.
Step 5 (assemble). $J(\pi')-J(\pi)\ge\frac{1}{1-\gamma}\big(\langle d^\pi,\bar a\rangle-\frac{2\gamma\epsilon^{\pi'}}{1-\gamma}\mathbb E_{d^\pi}[D_{\mathrm{TV}}]\big)$, which is the stated lower bound. The cost bound uses the other side of Hölder, $\langle d^{\pi'},\bar a_c\rangle\le\langle d^\pi,\bar a_c\rangle+\|d^{\pi'}-d^\pi\|_1\epsilon_c^{\pi'}$. $\square$
TRPO's bound is a corollary. Since $\sum_a\pi(a\mid s)A^\pi(s,a)=0$, $\ |\bar a(s)|=|\sum_a(\pi'-\pi)(a\mid s)A^\pi(s,a)|\le2D_{\mathrm{TV}}(\pi'\|\pi)[s]\,\epsilon$ with $\epsilon=\max_{s,a}|A^\pi(s,a)|$. With $\alpha=\max_sD_{\mathrm{TV}}(\pi'\|\pi)[s]$ this gives $\epsilon^{\pi'}\le2\alpha\epsilon$ and $\mathbb E_{d^\pi}[D_{\mathrm{TV}}]\le\alpha$, so the penalty is at most $\frac{4\epsilon\gamma}{(1-\gamma)^2}\alpha^2$: the total-variation form of Theorem 1 of Schulman et al., ICML 2015, whose KL form then uses $\alpha^2\le D_{\mathrm{KL}}^{\max}$ and $C=4\epsilon\gamma/(1-\gamma)^2$. CPO's version is tighter because it keeps the average over $d^\pi$ instead of the maximum over states.
From total variation to KL: Pinsker and Jensen
Trust-region methods constrain KL divergences, not TV distances. Pinsker's inequality (see Primer C) $D_{\mathrm{TV}}(p\|q)\le\sqrt{D_{\mathrm{KL}}(p\|q)/2}$ at every state, followed by Jensen's inequality for the concave square root (see Primer B), gives
so both bounds hold with $\mathbb E[D_{\mathrm{TV}}]$ replaced by $\sqrt{\bar D_{\mathrm{KL}}/2}$ (Achiam et al., Cor. 3). Two worst-case guarantees follow directly.
(Prop. 1, TRPO-type update $\max_\pi\mathbb E_{d^{\pi_k},\pi}[A^{\pi_k}]$ s.t. $\bar D_{\mathrm{KL}}\le\delta$). Since $\pi_k$ itself is feasible with objective $0$, the optimum has $\mathbb E_{d^{\pi_k},\pi_{k+1}}[A^{\pi_k}]\ge0$, and the lower bound with $\sqrt{\delta/2}$ gives $$J(\pi_{k+1})-J(\pi_k)\ \ge\ -\frac{\sqrt{2\delta}\,\gamma\,\epsilon^{\pi_{k+1}}}{(1-\gamma)^2},\qquad \epsilon^{\pi_{k+1}}=\max_s\big|\mathbb E_{a\sim\pi_{k+1}}[A^{\pi_k}(s,a)]\big|.$$ (Prop. 2, CPO update (10) below). The update enforces $J_c(\pi_k)+\frac{1}{1-\gamma}\mathbb E_{d^{\pi_k},\pi_{k+1}}[A_c^{\pi_k}]\le d$; adding the cost bound gives $$J_c(\pi_{k+1})\ \le\ d+\frac{\sqrt{2\delta}\,\gamma\,\epsilon_c^{\pi_{k+1}}}{(1-\gamma)^2}.$$ In words. One exact step can lose at most $O(\sqrt\delta)$ (at most a constant times $\sqrt\delta$; Primer 0) return and overshoot the budget by at most $O(\sqrt\delta)$, with the arithmetic $\frac{1}{1-\gamma}\cdot\frac{2\gamma}{1-\gamma}\cdot\sqrt{\delta/2}=\frac{\sqrt{2\delta}\gamma}{(1-\gamma)^2}$.
How loose is the bound? A three-state experiment
The explorer evaluates everything exactly (linear solves, no sampling) on a three-state corridor: states $0,1,2$, action "right" moves right with probability $0.8$ and stays otherwise, "left" moves left likewise (a move beyond either end leaves the state unchanged), reward $1$ per step in state $2$, start in state $0$. The old policy goes right with probability $p$; the new policy is the mixture $\pi'=(1-\alpha)\pi+\alpha\,\pi_{\rm greedy}$ towards the greedy policy of $Q^\pi$, the conservative-policy-iteration update of Kakade and Langford. Along this path $\epsilon^{\pi'}$ and $\mathbb E_{d^\pi}[D_{\mathrm{TV}}]$ are both linear in $\alpha$, so the CPO lower bound is a concave quadratic $X\alpha-Y\alpha^2$. For $X,Y\gt0$, every $0\lt\alpha\le1$ with $\alpha\lt X/Y$ is certified to improve the return. Because the mixture weight is confined to $[0,1]$, the step with the largest guaranteed improvement is $\alpha^\star=\min\{1,X/(2Y)\}$, with guaranteed improvement $X\alpha^\star-Y(\alpha^\star)^2$; this equals $X^2/(4Y)$ only when the vertex $X/(2Y)\le1$ (at $\gamma=0.3$, $p=0.95$ the vertex is $X/(2Y)\approx4.43$, so $\alpha^\star=1$).
Write $\pi_g$ for the greedy policy and $\pi'=(1-\alpha)\pi+\alpha\pi_g$. Because the old policy's advantage has zero mean, $\mathbb E_{a\sim\pi'}A^\pi(s,a)=\alpha\,\mathbb E_{a\sim\pi_g}A^\pi(s,a)$, and $D_{\mathrm{TV}}(\pi'\|\pi)[s]=\tfrac12\sum_a\alpha|\pi_g(a\mid s)-\pi(a\mid s)|=\alpha D_{\mathrm{TV}}(\pi_g\|\pi)[s]$. Hence $L_\pi(\pi')=\alpha X$ with $X=L_\pi(\pi_g)$, $\epsilon^{\pi'}=\alpha e$ with $e=\max_s|\mathbb E_{\pi_g}A^\pi(s,a)|$, and $\mathbb E_{d^\pi}[D_{\mathrm{TV}}(\pi'\|\pi)]=\alpha v$ with $v=\mathbb E_{d^\pi}D_{\mathrm{TV}}(\pi_g\|\pi)$. Substituting into the CPO bound, the penalty is $\frac{1}{1-\gamma}\cdot\frac{2\gamma\,\alpha e}{1-\gamma}\cdot\alpha v=Y\alpha^2$ with $Y=\frac{2\gamma ev}{(1-\gamma)^2}$. The TRPO-type bound replaces $e$ and $v$ by maxima and gives $Y_T=\frac{4\gamma\max_{s,a}|A^\pi(s,a)|\,[\max_sD_{\mathrm{TV}}(\pi_g\|\pi)]^2}{(1-\gamma)^2}$.
Things to try: at $\gamma=0.5$ the lower bound is informative for small $\alpha$; push $\gamma$ to $0.9$ and the best-guaranteed step $\alpha^\star$ shrinks to about $0.02$ (certified improvement only up to $2\alpha^\star\approx0.035$) while the true improvement keeps growing all the way to $\alpha=1$. The upper and lower bounds always sandwich the true curve, and all four curves share the same slope at $\alpha=0$ (first-order exactness). This is why practical methods treat $\delta$ as a tuning knob rather than computing the penalty.
3. Constrained Policy Optimization (CPO)
Applying the two bounds (in their KL form) to the objective and to the cost gives an update that maximises the surrogate minus a penalty proportional to $\sqrt{\bar D_{\mathrm{KL}}(\pi\|\pi_k)}$, subject to the cost surrogate plus such a penalty staying below $d$, with coefficients read off the corollaries. Solved exactly from a feasible $\pi_0$, it yields monotonically non-decreasing returns and feasible iterates. Achiam et al. note that the penalties are so steep for $\gamma$ near 1 that the steps become tiny, and replace them by a trust region, exactly as TRPO did.
Here $\operatorname*{arg\,max}$ denotes the set of maximisers (Primer B); writing one update assumes a maximiser exists and one is chosen.
The linearised problem
For a network with thousands of parameters, (10) is solved approximately around $\theta_k$. Both surrogates are linearised (their gradients at $\theta_k$ are the true gradients, Section 1), and the mean KL is replaced by its second-order Taylor model: at $\theta=\theta_k$ the KL and its gradient vanish, and its Hessian is the Fisher information matrix (see Primer E)
Assume the action probabilities are positive and twice differentiable near $\theta_k$, and fix a state; write $p_\theta(a)=\pi_\theta(a\mid s)$ and $f(\theta)=\sum_a p_\theta(a)\log\frac{p_\theta(a)}{p_k(a)}$. Then $\nabla f=\sum_a\nabla p_\theta(a)\log\frac{p_\theta(a)}{p_k(a)}+\sum_a\nabla p_\theta(a)$. At $\theta_k$ the logarithm is $\log1=0$, and $\sum_a\nabla p_\theta(a)=\nabla\sum_ap_\theta(a)=\nabla1=0$, so $\nabla f(\theta_k)=0$. Differentiating once more, the terms containing the logarithm or $\sum_a\nabla^2p_\theta(a)$ vanish at $\theta_k$ for the same two reasons, leaving $\nabla^2f(\theta_k)=\sum_a\frac{\nabla p_k(a)\nabla p_k(a)^\top}{p_k(a)}=\sum_ap_k(a)\,\nabla\log p_k(a)\,\nabla\log p_k(a)^\top$, since $\nabla\log p=\nabla p/p$. Averaging over $s\sim d^{\pi_k}$, which does not depend on $\theta$, gives $H$; with value and gradient zero, the Taylor model of the mean KL is $\tfrac12x^\top Hx$. $H$ is positive semidefinite because $v^\top Hv=\mathbb E[(v^\top\nabla\log\pi)^2]\ge0$.
Geometrically, $\sqrt q$ and $\sqrt s$ are the lengths of $g$ and $b$ in the $H^{-1}$ metric and $r/\sqrt{qs}$ is the cosine of the angle between them. The number $c^2/(2s)$ is the smallest value of $\tfrac12x^{\top}Hx$ on the hyperplane $c+b^{\top}x=0$ (attained at $x=-cH^{-1}b/s$), so the hyperplane cuts the trust region exactly when $c^2/s\le2\delta$. The unconstrained trust-region (TRPO) step is $x_{\rm TRPO}=\sqrt{2\delta/q}\,H^{-1}g$.
Write $b^\top x=(H^{-1/2}b)^\top(H^{1/2}x)$ with the matrix square roots of Primer A. Cauchy–Schwarz gives $(b^\top x)^2\le(b^\top H^{-1}b)(x^\top Hx)=s\,x^\top Hx$. On the hyperplane $b^\top x=-c$ this says $\tfrac12x^\top Hx\ge c^2/(2s)$, with equality at $x=-cH^{-1}b/s$ (substitute: $b^\top x=-c$ and $x^\top Hx=c^2/s$). On the trust region $\tfrac12x^\top Hx\le\delta$ the same inequality gives $|b^\top x|\le\sqrt{2\delta s}$, and both ends are attained, at $x=\pm\sqrt{2\delta/s}\,H^{-1}b$. The constraint asks $b^\top x\le-c$. If $-c\ge\sqrt{2\delta s}$ ($c\lt0$ and $c^2/s\ge2\delta$) every point of the trust region satisfies it; if $-c\lt-\sqrt{2\delta s}$ ($c\gt0$ and $c^2/s\gt2\delta$) none does; otherwise the hyperplane cuts the trust region.
Statement. Three regimes.
- Trust region entirely feasible ($c\lt0$ and $c^2/s\ge2\delta$): the linear constraint can be dropped, $\nu^\star=0$, $\lambda^\star=\sqrt{q/(2\delta)}$ and $x^\star=x_{\rm TRPO}$.
- Hyperplane cuts the trust region ($c^2/s\lt2\delta$): with $\Lambda_a=\{\lambda\ge0:\lambda c+r\gt0\}$ and $\Lambda_b=\{\lambda\ge0:\lambda c+r\le0\}$, the dual function minimised over $\nu\ge0$ is $$D(\lambda)=\begin{cases}D_a(\lambda)=\dfrac{q-r^2/s}{2\lambda}+\dfrac{\lambda}{2}\Big(2\delta-\dfrac{c^2}{s}\Big)-\dfrac{rc}{s}, & \lambda\in\Lambda_a\ \ (\nu^\star\gt0),\\[2mm] D_b(\lambda)=\dfrac{q}{2\lambda}+\lambda\delta, & \lambda\in\Lambda_b\ \ (\nu^\star=0),\end{cases}$$ minimised on each piece at $\lambda_a^\star=\mathrm{Proj}\Big(\sqrt{\tfrac{q-r^2/s}{2\delta-c^2/s}},\bar\Lambda_a\Big)$ and $\lambda_b^\star=\mathrm{Proj}\Big(\sqrt{\tfrac{q}{2\delta}},\bar\Lambda_b\Big)$, projections onto the closed intervals $\bar\Lambda_a,\bar\Lambda_b$ (projecting a number $z$ onto $[\ell,u]$ means clipping it, $\min(u,\max(\ell,z))$, Primer B; a piece that is empty, such as $\Lambda_a$ when $c\le0$ and $r\le0$, is skipped); $\lambda^\star$ is whichever gives the smaller $D$, and, provided $\lambda^\star\gt0$, with $(z)_+=\max(0,z)$, $$\nu^\star=\Big(\frac{\lambda^\star c+r}{s}\Big)_+,\qquad x^\star=\frac{1}{\lambda^\star}H^{-1}\big(g-\nu^\star b\big).$$ If the TRPO step happens to satisfy the linearised constraint ($c+r\sqrt{2\delta/q}\le0$), then $\sqrt{q/(2\delta)}\in\bar\Lambda_b$ wins the comparison and again $\nu^\star=0$, $x^\star=x_{\rm TRPO}$; otherwise $\lambda^\star=\lambda_a^\star$ and $\nu^\star\gt0$: the linearised constraint is active, and so is the trust region whenever $\lambda^\star\gt0$. By stationarity $g=\lambda^\star Hx^\star+\nu^\star b$, $\lambda^\star=0$ happens only in the degenerate case $g=\kappa b$ with $\kappa\gt0$ (Cauchy–Schwarz equality $qs=r^2$ with $r\gt0$). The objective is then a positive multiple of the cost surrogate, $\lambda^\star=0$ and $\nu^\star=\kappa$, the formula for $x^\star$ is undefined, and every point of the chord $\{c+b^{\top}x=0\}$ inside the trust region is optimal; $x^\star=-cH^{-1}b/s$ (the chord point closest to $\theta_k$ in the $H$-metric) is one optimal choice, with the trust region slack.
- Infeasible ($c\gt0$ and $c^2/s\gt2\delta$: every point of the trust region violates the linearised constraint): take the recovery step $x^\star=-\sqrt{2\delta/s}\,H^{-1}b$, the steepest decrease of the cost in the $H$-metric. (At the tangency $c\gt0$, $c^2/s=2\delta$, which Slater excludes, the feasible set is the single point $x=-cH^{-1}b/s$, and it coincides with this recovery step.)
In words. The step is a natural-gradient step on the penalised gradient $g-\nu^\star b$, where the price $\nu^\star$ of the cost is computed afresh at every iteration (not learned incrementally as in primal-dual methods) so that the step lands exactly on the linearised constraint surface whenever the TRPO step would cross it (if the TRPO step is already feasible, $\nu^\star=0$ and the step stays on the feasible side).
Why each assumption matters. $H\succ0$: otherwise $H^{-1}$ does not exist and the trust region is unbounded in some directions (in practice a damping term $\epsilon I$ is added). $g,b\ne0$: otherwise $q$ or $s$ vanishes and the formulas divide by zero ($g=0$: every feasible step is optimal; $b=0$: no step changes the linearised cost). Slater: without a strictly feasible point strong duality can fail, and in the infeasible regime the problem has no solution at all, hence the separate recovery rule. Single constraint: the case analysis relies on $\nu$ being a scalar.
The complete derivation, one step at a time and with the numbers of the explorer's default problem, is the walkthrough of Section 8. The recovery step needs one line: minimising $b^{\top}x$ subject to $\tfrac12x^{\top}Hx\le\delta$ is the Cauchy–Schwarz problem $b^{\top}x=(H^{-1/2}b)^{\top}(H^{1/2}x)\ge-\sqrt{s}\,\sqrt{2\delta}$, with equality at $x=-\sqrt{2\delta/s}\,H^{-1}b$. Achiam et al. justify it as the limit of the CPO direction as the intersection of trust region and feasible half-space shrinks to a point.
Implementation: conjugate gradients, line search, cost shaping
Conjugate gradients (CG) solves $Hv=g$ for symmetric positive definite $H$ by minimising the quadratic $\tfrac12v^\top Hv-g^\top v$ (whose minimiser is $H^{-1}g$) over a growing sequence of search directions, using only products $Hv$. In exact arithmetic it finishes after at most $n$ steps; in practice it is stopped after a few, so the result is an approximate solve, controlled by the residual $g-Hv$: if $H\succeq mI$ with $m\gt0$, then $\|v-H^{-1}g\|_2=\|H^{-1}(Hv-g)\|_2\le\|g-Hv\|_2/m$. Example: $H=\operatorname{diag}(2,1)$, $g=(2,1)$ has solution $(1,1)$; the iterate $(0.9,1)$ has residual $(0.2,0)$ and error $0.1\le0.2/1$. Poor conditioning (widely separated eigenvalues) slows convergence. CPO runs CG twice, for $g$ and for $b$.
Degenerate cases are handled before the generic formulas (see the theorem): $b=0$ (if $c\le0$ the constraint is inactive and $x_{\rm TRPO}$ is optimal; if $c\gt0$ no step repairs it in the linear model), $g=0$ (any feasible step is optimal), and $\lambda^\star=0$ (then $g=\kappa b$ with $\kappa\gt0$; take the chord point $x=-cH^{-1}b/s$ instead of dividing by zero).
The advantages come from generalised advantage estimation (GAE). With a fitted value function $V$ (the critic) and TD residuals $\delta_t^r=r_t+\gamma V(s_{t+1})-V(s_t)$ (Primer E), a rollout $t=0,\dots,L-1$ gives $\hat A_t=\sum_{\ell=0}^{L-1-t}(\gamma\lambda^{\rm GAE})^\ell\delta_{t+\ell}^r$; replace $r,V$ by $c,V_c$ for the cost. At a genuine terminal state the remaining value is zero; at a truncated rollout one bootstraps from the critic. Smaller $\lambda^{\rm GAE}$ looks fewer steps ahead, which usually lowers variance but increases the dependence on critic error.
- Input: initial policy $\pi_{\theta_0}$, trust-region radius $\delta$, backtracking factors $\omega^j$ with $\omega\in(0,1)$, $j=0,\dots,J$.
- for $k=0,1,2,\dots$ do
- Sample trajectories with $\pi_k$; estimate $\hat A$ and $\hat A_c$ with GAE (separate $\lambda^{\rm GAE}$ for costs) and $\hat c=\hat J_c(\pi_k)-d$.
- Form $\hat g,\hat b$ and the Fisher–vector product $v\mapsto\hat Hv$ (a Hessian–vector product, Primer B) // never build $H$ itself
- Conjugate gradient: $v_g\approx\hat H^{-1}\hat g$, $v_b\approx\hat H^{-1}\hat b$; then $q=\hat g^{\top}v_g$, $r=\hat g^{\top}v_b$, $s=\hat b^{\top}v_b$.
- after handling the degeneracies above, if the subproblem is strictly feasible: solve the dual in closed form for $(\lambda^\star,\nu^\star)$; $x^\star=(v_g-\nu^\star v_b)/\lambda^\star$ when $\lambda^\star\gt0$; otherwise use the minimum-norm chord point above.
- else: $x^\star=-\sqrt{2\delta/s}\;v_b$ // recovery (at a tangency, the only feasible point)
- Backtracking line search over $\theta_j=\theta_k+\omega^jx^\star$, $j=0,\dots,J$: accept the first $\theta_j$ whose sample estimates pass the test of the current mode:
- normal ($\hat c\le0$): the surrogate return improves, mean KL $\le\delta$, and the cost surrogate stays within budget, $\hat c+\hat L_{c,\pi_k}(\pi_{\theta_j})\le0$ (the constraints of (10));
- recovery ($\hat c\gt0$): mean KL $\le\delta$ and the cost surrogate does not increase, $\hat L_{c,\pi_k}(\pi_{\theta_j})\le0$; no return test // the budget may be out of reach, and shrinking the step only raises the cost
- if no $j\le J$ passes: normal mode rejects the step ($\theta\leftarrow\theta_k$); the reference code keeps its smallest recovery step (an alternative is to revert to the last feasible iterate)
- $\theta_{k+1}\leftarrow\theta$; refit the reward and cost value networks.
Conjugate gradients. $H$ has $n^2$ entries for $n$ network parameters, so it is never formed. CG needs only products $Hv=\nabla_\theta\big((\nabla_\theta\bar D_{\mathrm{KL}})^{\top}v\big)$ (evaluated at $\theta_k$ with $v$ held fixed; damping uses $Hv+\epsilon v$), two backward passes each, and a handful of iterations (TRPO's standard is about 10). CPO needs two solves, $H^{-1}g$ and $H^{-1}b$; everything else is scalar algebra on $q,r,s,c,\delta$. Line search. The linearisation is only locally valid, so the proposed step is shrunk until the sampled KL and cost surrogate are acceptable; this is the only place where the non-linearised problem (10) is consulted. The paper's Algorithm 1 asks the line search to enforce the constraints of (10) in every case. That is impossible when $\hat c\gt0$ and the budget is out of reach within the trust region: every backtracked recovery step is still infeasible, and shorter steps are worse. The authors' code (jachiam/cpo; defaults $\omega=0.8$, at most 15 trials) therefore checks a threshold $\max(d-\hat J_c(\pi_k),0)$ on the change of the cost surrogate: the budget in normal mode, "no increase" in recovery mode, where the return test is also dropped.
Cost shaping and the failure predictor. Because of the approximations between the original CMDP problem and the practical step, Achiam et al. build in a factor of safety: they constrain an upper bound $C^+=C+\Delta$ of the cost (their Eq. 15), where the bonus $\Delta$ is a weighted output of a learned failure predictor $P_\phi(s\to U)$, a small network estimating the probability of entering an unsafe state within the next $T$ steps (horizon $T=5$ or $20$; weight $1$, or $0.01$ on Ant-Gather; no bonus on Point-Gather). Their appendix also reports that for high-dimensional robots the cost advantages had to be computed with $\lambda^{\rm GAE}_C\lt1$ (0.5): undiscounted cost advantages overestimated the constraint gradient and produced unsafe steps. In their experiments CPO drove the constraint value "almost directly to the limit", i.e. it operates on the boundary, where any estimation error becomes a violation; the shaping bonus is the margin.
| Algorithm | Return $\bar J_r$ | Violation $\bar M_c$ | Cost rate $\bar\rho_c$ |
|---|---|---|---|
| PPO (reference) | 1.0 | 1.0 | 1.0 |
| PPO-Lagrangian | 0.24 | 0.026 | 0.245 |
| TRPO-Lagrangian | 0.331 | 0.018 | 0.265 |
| CPO | 0.784 | 0.593 | 0.646 |
4. PCPO, FOCOPS, CUP, P3O, IPO, CVPO, C-TRPO
CPO's weaknesses are practical: second-order machinery, a case analysis with a separate recovery rule, and active-constraint steps that sit exactly on an estimated boundary. The successors change one ingredient each: where the problem is solved (parameter space or policy space), how the constraint enters (intersection, projection, penalty, barrier, geometry), and which optimiser is used (conjugate gradients or plain SGD, Primer B).
PCPO: improve, then project
Yang, Rosca, Narasimhan & Ramadge, ICLR 2020 split the step in two: an unconstrained TRPO step for the reward, then a projection of the intermediate policy onto the (surrogate) constraint set, $\pi^{k+1}=\operatorname*{arg\,min}_\pi D(\pi,\pi^{k+1/2})$ s.t. $J_c(\pi_k)+\frac{1}{1-\gamma}\mathbb E_{d^{\pi_k},\pi}[A_c^{\pi_k}]\le d$, with $D$ either the $L_2$ distance of parameters or the KL divergence. Linearised (their Eqs. 4–6, translated to CPO letters: their $a,b,h$ are our $b,c,d$), the projection onto $\{x:c+b^{\top}x\le0\}$ in the metric $L$ has the KKT solution $x=x_{\rm TRPO}-\mu L^{-1}b$ with $\mu=(c+b^{\top}x_{\rm TRPO})_+/(b^{\top}L^{-1}b)$, i.e.
The linearised projection solves $\min_x\tfrac12(x-x_{\rm TRPO})^\top L(x-x_{\rm TRPO})$ subject to $c+b^\top x\le0$, with $L\succ0$. Stationarity of the Lagrangian with multiplier $\mu\ge0$ gives $L(x-x_{\rm TRPO})+\mu b=0$, i.e. $x=x_{\rm TRPO}-\mu L^{-1}b$. If $x_{\rm TRPO}$ already satisfies the constraint, $\mu=0$. Otherwise the constraint is active: substituting into $c+b^\top x=0$ gives $c+b^\top x_{\rm TRPO}-\mu\,b^\top L^{-1}b=0$, so $\mu=(c+b^\top x_{\rm TRPO})/(b^\top L^{-1}b)$. Both cases together are the $(\cdot)_+$ formula, and $b^\top x_{\rm TRPO}=\sqrt{2\delta/q}\,r$.
Take $L=H$ and suppose the projection is active. Let $\beta:=b^{\top}x_{\rm TRPO}=\sqrt{2\delta/q}\,r$, so $\mu=(c+\beta)/s$ and $x_P=x_{\rm TRPO}-\mu H^{-1}b$. Expanding the quadratic and using $\tfrac12x_{\rm TRPO}^{\top}Hx_{\rm TRPO}=\delta$, $b^{\top}H^{-1}b=s$:
Two consequences. (i) Feasible $\pi_k$ ($c\le0$). The projection is active only if $c+\beta\gt0$, i.e. $\beta\gt-c\ge0$, so $\beta^2\gt c^2$ and $\tfrac12x_P^{\top}Hx_P\lt\delta$: the projected step stays strictly inside the trust region (the quadratic-model version of their Lemma S.1). (ii) Infeasible $\pi_k$ ($c\gt0$). $\tfrac12x_P^{\top}Hx_P\le\delta+c^2/(2s)=\delta+(b^+)^2\alpha_{\mathrm{KL}}$: exactly the enlarged radius of Theorem 3.2. For the $L_2$ projection no such identity exists; the Euclidean projection is non-expansive in the Euclidean norm, not in the $H$-norm, and can leave the KL trust region even from a feasible policy. In the explorer's default problem the three steps give $g^{\top}x=0.354$ (CPO), $0.324$ (PCPO, KL) and $0.283$ (PCPO, $L_2$). With the KL projection and a feasible iterate, PCPO therefore returns a feasible but generally suboptimal point of CPO's subproblem (the $L_2$ step is feasible in this example too, but not in general), in exchange for never needing a separate recovery rule.
For a differentiable convex $F$, the Bregman divergence $D_F(u\|v)=F(u)-F(v)-\nabla F(v)^\top(u-v)\ge0$ is the gap between $F$ and its tangent at $v$ (Primer B). $F(u)=\tfrac12\|u\|_2^2$ gives $\tfrac12\|u-v\|_2^2$; the negative entropy $F(u)=\sum_iu_i\log u_i$ on probability vectors gives $D_{\mathrm{KL}}(u\|v)$. $F$ is called a mirror function: its gradient supplies the coordinates in which mirror-descent methods take their steps. Unlike $\tfrac12\|u-v\|_2^2$, the KL is not symmetric: for $u=(0.5,0.5)$, $v=(0.9,0.1)$, $D_{\mathrm{KL}}(u\|v)\approx0.511$ but $D_{\mathrm{KL}}(v\|u)\approx0.368$.
Three-point inequality. If $p$ minimises $D_F(u\|y)$ over $u$ in a closed convex set $C$, then $D_F(z\|y)\ge D_F(z\|p)+D_F(p\|y)$ for every $z\in C$. In PCPO, $y=\pi^{k+1/2}$ (after the reward step), $p=\pi_{k+1}$ (its KL projection) and $z=\pi_k$ (feasible), so $D_{\mathrm{KL}}(\pi_k\|\pi_{k+1})\le D_{\mathrm{KL}}(\pi_k\|\pi^{k+1/2})$: a bound with $\pi_k$ first, whereas the trust region constrains $D_{\mathrm{KL}}(\pi^{k+1/2}\|\pi_k)$. Treating the two orders as equal is only a local approximation for nearby policies, and the theorem below needs exactly that approximation.
Thm. 3.1 ($\pi_k$ feasible). $\ J(\pi_{k+1})-J(\pi_k)\ge-\frac{\sqrt{2\delta}\gamma\epsilon_R^{\pi_{k+1}}}{(1-\gamma)^2}$ and $J_c(\pi_{k+1})\le d+\frac{\sqrt{2\delta}\gamma\epsilon_C^{\pi_{k+1}}}{(1-\gamma)^2}$: the same guarantee as CPO.
Thm. 3.2 ($\pi_k$ infeasible). With $b^+=\max(0,J_c(\pi_k)-d)$ and $\alpha_{\mathrm{KL}}=\frac{1}{2\,b^{\top}H^{-1}b}$, the same bounds hold with $\delta$ replaced by $\delta+(b^+)^2\alpha_{\mathrm{KL}}$: a larger violation buys a larger worst-case step.
In words. Measured in the old-first KL, the projection never moves the policy farther from a feasible $\pi_k$ than the reward step did (three-point inequality with $z=\pi_k$). If the KL were symmetric, this would keep $\pi_{k+1}$ in the trust region and Achiam's bounds would apply; because it is not, the argument swap is a local approximation. The statement that is exact is the quadratic-model one derived above.
Why each assumption matters. KL (not $L_2$) projection: the Bregman three-point inequality is what keeps the step inside the KL ball. Their proof bounds $\mathbb E[D_{\mathrm{KL}}(\pi_k\|\pi_{k+1})]$ and then swaps the arguments of the KL by appealing to its asymptotic symmetry for nearby policies, so even the idealised theorem contains a local approximation. The practical update is linearised exactly as in CPO.
FOCOPS: solve in policy space, then regress
Zhang, Vuong & Ross, NeurIPS 2020 keep problem (10) but optimise first over all stationary policies (see Primer B), where it is convex and has a closed-form solution, and only then fit the network. Their $b$ is our budget $d$.
Statement. $$\begin{aligned}\pi^\star(a\mid s)&=\frac{\pi_{\theta_k}(a\mid s)}{Z_{\lambda,\nu}(s)}\exp\Big(\frac{1}{\lambda}\big(A^{\pi_{\theta_k}}(s,a)-\nu A_c^{\pi_{\theta_k}}(s,a)\big)\Big),\\ (\lambda,\nu)&=\operatorname*{arg\,min}_{\lambda,\nu\ge0}\ \lambda\delta+\nu\tilde b+\lambda\,\mathbb E_{s\sim d^{\pi_{\theta_k}}}\big[\log Z_{\lambda,\nu}(s)\big],\end{aligned}$$ with the normaliser $Z_{\lambda,\nu}(s)=\sum_a\pi_{\theta_k}(a\mid s)\exp\big(\frac{1}{\lambda}(A^{\pi_{\theta_k}}-\nu A_c^{\pi_{\theta_k}})(s,a)\big)$. The Gibbs formula needs $\lambda\gt0$: if the optimal KL multiplier is $0$ (KL constraint slack, as in Exercise 9.3), solve the problem without the KL term instead of substituting $\lambda=0$. At states with $d^{\pi_{\theta_k}}(s)=0$ the surrogate does not determine the update. $\pi^\star$ inherits CPO's worst case, $J_c(\pi^\star)\le d+\sqrt{2\delta}\gamma\epsilon_C^{\pi^\star}/(1-\gamma)^2$.
In words. Reweight the old policy exponentially by a Lagrangian advantage: actions with high return advantage and low cost advantage gain mass; $\lambda$ is a temperature set by the trust region, $\nu$ the price of cost.
Step 1 (convexity). In the variables $\{\pi(\cdot\mid s)\}_s$ the objective and the cost constraint are linear; the KL constraint $\sum_sd^{\pi_{\theta_k}}(s)D_{\mathrm{KL}}(\pi\|\pi_{\theta_k})[s]\le\delta$ is a positive combination of functions convex in their first argument. With the Slater point $\pi_{\theta_k}$, strong duality holds (Module 2).
Step 2 (Lagrangian). Rewrite the cost constraint as $\mathbb E_{d^{\pi_{\theta_k}},\pi}[A_c]\le\tilde b$ and attach $\nu\ge0$ to it and $\lambda\ge0$ to the KL constraint:
Step 3 (decoupling). For fixed $(\lambda,\nu)$ the maximisation over $\pi$ splits into one problem per state (the weights $d^{\pi_{\theta_k}}(s)$ are fixed and non-negative): maximise $\sum_ap(a)\big[A-\nu A_c-\lambda(\log p(a)-\log\pi_{\theta_k}(a\mid s))\big]$ over the simplex.
Step 4 (stationarity). With a multiplier $\zeta$ for $\sum_ap(a)=1$: $\ A-\nu A_c-\lambda(\log p(a)+1-\log\pi_{\theta_k}(a\mid s))+\zeta=0$, so $p(a)=\pi_{\theta_k}(a\mid s)\exp\big((A-\nu A_c)/\lambda\big)\,e^{\zeta/\lambda-1}$. Normalising fixes $e^{\zeta/\lambda-1}=1/Z_{\lambda,\nu}(s)$ with $Z_{\lambda,\nu}(s)=\sum_a\pi_{\theta_k}(a\mid s)e^{(A-\nu A_c)/\lambda}$. For $\lambda\gt0$ the per-state objective is strictly concave (negative entropy), so this stationary point is the maximum and it is automatically positive.
Step 5 (dual function). At $\pi^\star$, $\ A-\nu A_c-\lambda\log\frac{\pi^\star}{\pi_{\theta_k}}=A-\nu A_c-\lambda\big(\tfrac{A-\nu A_c}{\lambda}-\log Z\big)=\lambda\log Z_{\lambda,\nu}(s)$ for every action, hence $\max_\pi\mathcal L=\lambda\delta+\nu\tilde b+\lambda\,\mathbb E_{s}[\log Z_{\lambda,\nu}(s)]$, which is minimised over $\lambda,\nu\ge0$. $\square$
Step 6 (the practical multiplier update). Differentiating $\log Z$ gives $\partial_\nu\big(\lambda\,\mathbb E_s\log Z_{\lambda,\nu}\big)=-\mathbb E_{s\sim d^{\pi_{\theta_k}},a\sim\pi^\star}[A_c(s,a)]$, so the dual gradient in $\nu$ is $\tilde b-\mathbb E_{d^{\pi_{\theta_k}},\pi^\star}[A_c]$. FOCOPS approximates the expectation under $\pi^\star$ by the one under $\pi_{\theta_k}$, which is zero, and descends: $\nu\leftarrow\mathrm{proj}_{[0,\nu_{\max}]}\big[\nu-\alpha\,(d-J_c(\pi_{\theta_k}))\big]$, with the factor $1-\gamma$ of $\tilde b$ absorbed into the step size $\alpha$. This is an approximation, so the update does not solve the two-variable dual exactly. The price rises while the constraint is violated: the integral controller of Module 8 again.
Back to the network. $\pi^\star$ cannot be sampled directly, so FOCOPS minimises $\mathbb E_{s\sim d^{\pi_{\theta_k}}}[D_{\mathrm{KL}}(\pi_\theta\|\pi^\star)[s]]$ by SGD, with gradient $\nabla_\theta D_{\mathrm{KL}}(\pi_\theta\|\pi_{\theta_k})[s]-\frac1\lambda\mathbb E_{a\sim\pi_{\theta_k}}\big[\frac{\nabla_\theta\pi_\theta(a\mid s)}{\pi_{\theta_k}(a\mid s)}(A-\nu A_c)\big]$ (their Cor. 1). In practice $\lambda$ is a fixed temperature found by a sweep, samples whose per-state KL exceeds $\delta$ are rejected, and the inner loop stops early when the average KL exceeds $\delta$. The worst-case bound holds for $\pi^\star$, not for the fitted $\pi_\theta$: the projection error is uncontrolled. Exercise 3 computes $\pi^\star$ by hand for two actions.
CUP: tighter surrogates, first-order projection
Yang, Ji, Dai et al., NeurIPS 2022 generalise the performance bounds to GAE-weighted state distributions $d^\lambda_\pi$ with effective discount $\tilde\gamma=\gamma(1-\lambda)/(1-\gamma\lambda)$ (here $\lambda$ is the GAE parameter). Step 1 improves $\mathbb E_{d^\lambda_{\pi_{\theta_k}},\pi_{\theta_k}}\big[\frac{\pi_\theta}{\pi_{\theta_k}}A^{\mathrm{GAE}}\big]-\alpha_k\sqrt{\mathbb E[\mathrm{KL}(\pi_{\theta_k},\pi_\theta)]}$; step 2 projects onto $\{\pi_\theta:\ J_c(\pi_{\theta_k})+\frac{1}{1-\tilde\gamma}\mathbb E[A_c^{\mathrm{GAE}}]+\beta_k\sqrt{\mathbb E[\mathrm{KL}]}\le d\}$, both with first-order optimisers (the projection by a primal–dual scheme). Every expectation in both steps uses the fixed weighting $d^\lambda_{\pi_{\theta_k}}$ defined in the theorem below; sampled neural implementations only approximate these policy-space updates. Their Theorem 2 gives $\sqrt{\mathrm{KL}}$-type improvement and violation bounds with the constant $\iota=\frac{\tilde\gamma(\gamma\lambda(|\mathcal S|-1)+1)}{(1-\tilde\gamma)(1-\gamma\lambda)}$, and Remark 2 discusses "asymptotic safety" as $\alpha_k,\beta_k\to0$; the complete remainder must also vanish (Going deeper, below). Note that $\iota$ grows with the number of states, so the bound says nothing for continuous state spaces, and the strong-duality argument for the projection holds in the space of policies, not of network weights.
Assume finite states and actions, bounded rewards/costs, a common initial distribution $\mu$, stationary policies $\pi,\pi'$, $0\lt\gamma\lt1$, and $0\le\lambda\le1$. Use column-stochastic $P_\pi$. Define
This is an occupancy for a chain that jumps a geometrically distributed number of ordinary time steps. Set $\bar a(s)=\mathbb E_{a\sim\pi'}A^\pi(s,a)$ as in Section 2 and $B=(I-\gamma\lambda P_{\pi'}^\top)^{-1}\bar a$, i.e. $B(s)$ is the expected $(\gamma\lambda)$-discounted sum of old-policy TD residuals along a trajectory of $\pi'$ from $s$. Let $L_\lambda=(d_\pi^\lambda)^\top B/(1-\tilde\gamma)$ and $E_\lambda=\|d_{\pi'}^\lambda-d_\pi^\lambda\|_1\|B\|_\infty/(1-\tilde\gamma)$. Then
Replace reward advantage by cost advantage for the cost bounds. The proof is the resolvent identity $(I-\tilde\gamma P^{(\lambda)})=(I-\gamma P)(I-\gamma\lambda P)^{-1}$, followed by the same add/subtract and norm bound as Section 2. Multi-step residuals change the weighting, not the need to bound distribution shift.
Consequences: an exact update with $L_\lambda-E_\lambda\ge0$ does not decrease the return, and one with $J_c(\pi)+L_{c,\lambda}+E_{c,\lambda}\le d$ is safe. CUP's penalty $\beta_k\sqrt{\mathrm{KL}}$ (or $\alpha_k\sqrt{\mathrm{KL}}$) certifies nothing unless it upper-bounds $E_{c,\lambda}$ (or $E_\lambda$) for every candidate policy considered, and a sampled GAE batch cannot check that: $E_\lambda$ involves the new policy's distribution and a maximum over all states.
For the exact two-stage updates described above, the paper’s Theorem 2 reports, with $\chi_k=\mathbb E_{d_{\pi_k}^\lambda}D_{\rm KL}(\pi_k\|\pi_{k+1/2})$,
Here $\epsilon_R$ bounds the expected absolute old-value TD residual over all states and times under the candidate policy, and $\epsilon_C$ is its cost analogue; bounded signals give finite bounds. All state expectations use $d_{\pi_k}^\lambda$, and $\alpha_k,\beta_k$ are the coefficients of the two surrogate penalties. The proof assumes a feasible old policy and an exact Bregman projection onto a convex set, then reverses KL arguments using local symmetry. It also inserts the adjustable penalty coefficients into the performance-error terms without a general coefficient condition. Thus these printed inequalities are not an exact global certificate for arbitrary coefficients and neural policy classes. The theorem above supplies the explicit multi-step bound and the error-dominance condition a certificate would need.
Even if the reported bounds apply in a chosen idealisation, asymptotic safety requires $\beta_k\sqrt{\chi_k}\epsilon_C\to0$, with fixed finite $\iota/(1-\tilde\gamma)$; vanishing $\beta_k$ alone is insufficient if the other factors grow. A vanishing negative lower bound on reward change is not a proof that each finite update improves reward.
P3O: an exact penalty instead of a projection
Zhang, Shen, Yang et al., IJCAI 2022 write the per-iteration problem with the importance ratio $\varrho_\theta=\pi_\theta(a\mid s)/\pi_k(a\mid s)$ as (P): $\min_\theta L_R(\theta)=\mathbb E[-\varrho_\theta A^{\pi_k}]$ s.t. $L_{C_i}(\theta)=\mathbb E[\varrho_\theta A_{c_i}^{\pi_k}]+(1-\gamma)(J_{c_i}(\pi_k)-d_i)\le0$, and replace it by the unconstrained ReLU penalty (Q): $\min_\theta L_R(\theta)+\kappa\sum_i\max\{0,L_{C_i}(\theta)\}$. The practical loss clips both terms PPO-style (see Primer E), with a $\max$ in the cost term so that clipping is pessimistic for safety:
Here $\mathrm{clip}(z,l,u)=\min(u,\max(l,z))$ and $\epsilon$ is the clipping range. The reward uses the smaller of the clipped and unclipped surrogate terms, while the cost uses the larger: optimistic changes are suppressed in each direction. This conservatism concerns the estimated surrogate, not the true trajectory cost.
Statement. (a) If $\kappa\ge\|\bar\lambda\|_\infty$, then $\bar\theta$ minimises (Q). (b) If $\kappa\gt\|\bar\lambda\|_\infty$, every minimiser of (Q) is feasible and optimal for (P), so (P) and (Q) have the same solution set. P3O states the set equality with $\kappa\ge\|\bar\lambda\|_\infty$; at equality (b) can fail (Exercise 4 gives a one-line counterexample).
In words. A penalty that grows linearly in the violation is exact for a finite weight, the largest shadow price. A quadratic penalty is exact only in the limit of an infinite weight, and a log barrier only in the limit of a vanishing weight $1/t$ (IPO's $t\to\infty$). P3O's second theorem adds that replacing $d^{\pi}$ by $d^{\pi_k}$ costs $O(\kappa m\sqrt\delta)$, so $\kappa$ should not be larger than necessary.
Why each assumption matters. $\bar\lambda$ is unknown, so P3O grows $\kappa\leftarrow\min(\rho\kappa,\kappa_{\max})$ inside each update; without the saddle-point property the chain of inequalities in the proof breaks.
Write $Q(\theta)=L_R(\theta)+\kappa\sum_i[L_{C_i}(\theta)]_+$. For any $\theta$,
(1) $\kappa\ge\bar\lambda_i\ge0$; (2) $[u]_+\ge u$ and $\bar\lambda_i\ge0$; (3) the saddle point; (4) complementary slackness; (5) $\bar\theta$ is feasible, so every $[\cdot]_+$ vanishes. This proves (a). For (b) let $\tilde\theta$ minimise $Q$. If $\tilde\theta$ is feasible, $L_R(\tilde\theta)=Q(\tilde\theta)\le Q(\bar\theta)=L_R(\bar\theta)$, so $\tilde\theta$ is optimal for (P). If some $L_{C_j}(\tilde\theta)\gt0$ and $\kappa\gt\bar\lambda_j$, inequality (1) is strict at $\tilde\theta$, giving $Q(\tilde\theta)\gt Q(\bar\theta)$, a contradiction. With $\kappa=\bar\lambda_j$ inequality (1) can be an equality at an infeasible point, and then infeasible minimisers can exist. $\square$
IPO: a log barrier
Liu, Ding & Liu, AAAI 2020 add logarithmic barriers (Primer B) to PPO's clipped objective, $\max_\theta L^{\rm CLIP}(\theta)+\sum_{i=1}^m\frac1t\log\big(-\hat J_{c_i}(\pi_\theta)\big)$ with $\hat J_{c_i}=J_{c_i}-d_i$. Their Theorem 1 bounds the gap between the constrained optimum and the barrier optimum by $m/t$ "if the optimal policy is strictly feasible". The argument is the central-path argument of interior-point methods: at a stationary point $\theta^\star(t)$ of the barrier objective, the numbers $\lambda_i=-1/(t\,\hat J_{c_i}(\theta^\star))\gt0$ make $\theta^\star$ a stationary point of the Lagrangian; if it also maximises the Lagrangian (true for concave objectives and convex constraints), weak duality gives $p^\star\le L^{\rm CLIP}(\theta^\star)+\sum_i\lambda_i(-\hat J_{c_i}(\theta^\star))=L^{\rm CLIP}(\theta^\star)+m/t$. For neural policies that step is not justified, so the $m/t$ bound is a heuristic there. The barrier is also undefined at infeasible points ($\hat J_{c_i}\ge0$), so it needs a strictly feasible estimate to start from.
CVPO: safe RL as inference
Liu, Cen, Isenbaev et al., ICML 2022 solve the same kind of problem by expectation–maximisation, off-policy. The E-step optimises a non-parametric variational policy $q(\cdot\mid s)$ ($|\mathcal A|$ weights, or $K$ sampled particles for continuous actions) against off-policy critics $Q_r=Q_r^{\pi_{\theta_i}}$, $Q_c=Q_c^{\pi_{\theta_i}}$ with the state distribution held fixed (the paper writes it $\rho_q$, but it is a fixed state weighting, not recomputed for each candidate $q$): $\max_q\mathbb E_{\rho_q}\mathbb E_q[Q_r]$ s.t. $\mathbb E_{\rho_q}\mathbb E_q[Q_c]\le\epsilon_1$, $\mathbb E_{\rho_q}[D_{\mathrm{KL}}(q\|\pi_{\theta_i})]\le\epsilon_2$. Under Slater's condition (some feasible $\bar q$ with $D_{\mathrm{KL}}(\bar q\|\pi_{\theta_i})\lt\epsilon_2$) their Theorem 1 gives
the FOCOPS form with CVPO's letters ($\eta$ = temperature/KL multiplier, $\lambda$ = cost multiplier) and with $Q$-values in place of advantages. This is equivalent: subtracting $V_r(s)$ from $Q_r$ shifts the objective by a constant, while replacing $Q_c$ by $A_c=Q_c-V_c$ also shifts the threshold $\epsilon_1$ to $\epsilon_1-\mathbb E_{\rho_q}V_c$. As for FOCOPS, the formula needs $\eta^\star\gt0$ and gives mass only to actions in the support of $\pi_{\theta_i}$. Their Theorem 2 shows the two-dimensional dual is convex, and strictly convex under non-degeneracy conditions. The M-step is supervised: $\max_\theta\mathbb E_{\rho_q}\mathbb E_{q_i^\star}[\log\pi_\theta(a\mid s)]$ s.t. $\mathbb E_{\rho_q}[D_{\mathrm{KL}}(\pi_{\theta_i}\|\pi_\theta)]\le\epsilon$. Unlike FOCOPS, CVPO solves for both multipliers at every iteration; like FOCOPS, the guarantee concerns the non-parametric policy, not the network. The two fits run in opposite KL directions: CVPO's M-step is weighted maximum likelihood (see Primer C), i.e. it minimises $\mathbb E_{\rho_q}[D_{\mathrm{KL}}(q_i^\star\|\pi_\theta)]$ up to a constant, whereas FOCOPS minimises $\mathbb E_{s}[D_{\mathrm{KL}}(\pi_\theta\|\pi^\star)[s]]$, which is not a maximum-likelihood fit.
EM fits a model by alternating two easier problems: an E-step that computes an auxiliary distribution over hidden quantities, and an M-step that fits the model parameters to it by weighted maximum likelihood. CVPO reads "this action is good and safe" as an observed event and the action as the hidden quantity: the E-step computes a variational policy $q$, a freely adjustable distribution that plays the role of the posterior over actions given that event (it is optimised directly, one number per action, instead of through the network weights), and the M-step moves the network $\pi_\theta$ towards $q$. Example with two actions: $\pi_{\theta_i}(\cdot\mid s)=(0.5,0.5)$, $Q_r-\lambda Q_c=(1,0)$ and $\eta=1/\ln4$ give $q\propto(0.5\cdot4,\ 0.5\cdot1)$, i.e. $q=(0.8,0.2)$; the M-step then maximises $0.8\log\pi_\theta(a_1\mid s)+0.2\log\pi_\theta(a_2\mid s)$, whose unrestricted maximiser is $\pi_\theta(\cdot\mid s)=q$. A network with a KL limit generally lands only near $q$, which is why the guarantee concerns $q$, not $\pi_\theta$.
C-TRPO: put the constraint into the geometry
Milosevic, Müller & Scherf, ICML 2025 observe that a TRPO trust region is a Bregman ball of a mirror function (the conditional entropy) and ask for a mirror function whose balls contain only safe policies. The paper works with normalised values $V_c(\pi)=(1-\gamma)J_c(\pi)$, so its budget $b$ is our $d$ in normalised units, $b=(1-\gamma)d$. With a convex $\phi$ that is steep at $0$,
where $D_K(d^{\pi_1}\|d^{\pi_2})=\sum_sd^{\pi_1}(s)D_{\mathrm{KL}}(\pi_1\|\pi_2)[s]$ is TRPO's divergence and $D_\phi$ is the Bregman divergence of $\phi$ evaluated at the constraint margins. $D_C$ is finite only for safe occupancies and blows up as the second argument approaches the constraint surface, so the exact update $\max_\pi A_r^{\pi_k}(\pi)$ s.t. $D_C(d^{\pi_k}\|d^\pi)\le\delta$ can never leave the safe set. The practical C-TRPO makes two replacements: the value difference $V_c(\pi)-V_c(\pi_k)$ inside $D_\phi$ by the cost surrogate $\mathbb E_{d^{\pi_k}}[\frac{\pi}{\pi_k}A_c^{\pi_k}]$ (equal to first order, with the unnormalised $A_c^{\pi_k}$ of Section 1), giving $\bar D_\phi(\pi\|\pi_k)$; and the Kakade part by TRPO's mean KL $\bar D_{\mathrm{KL}}(\pi\|\pi_k)=\mathbb E_{s\sim d^{\pi_k}}D_{\mathrm{KL}}(\pi\|\pi_k)[s]$. The resulting surrogate divergence $\bar D_C(\pi\|\pi_k)=\bar D_{\mathrm{KL}}(\pi\|\pi_k)+\beta\bar D_\phi(\pi\|\pi_k)$ is computable from one batch, so C-TRPO approximates a single quadratic constraint (no intersection with a half-space as in CPO), and it switches to a pure cost-decreasing TRPO step when the iterate is unsafe, with hysteresis (return to constrained mode only below $b_H=0.8b$).
Let $m_k=b-V_c(\pi_k)$ and $m=b-V_c(\pi)$. In the exact constraint written here, the margin term is $D_\phi(m_k\|m)=\phi(m_k)-\phi(m)-\phi'(m)(m_k-m)$. The reversed order is generally different. For the practical candidate-first surrogate, put $u=\mathbb E_{d^{\pi_k},\pi}A_c^{\pi_k}$ and $\widehat m=m_k-u$. Then $\bar D_\phi(\pi\|\pi_k)=\phi(m_k-u)-\phi(m_k)+\phi'(m_k)u$, defined only when $m_k-u\gt0$. Both have the same local quadratic term $\tfrac12\phi''(m_k)(m-m_k)^2$, but they are different functions away from $\pi_k$.
Prop. 4.3. If the surrogate divergence satisfies $\bar D_C(\pi_{k+1}\|\pi_k)\le\delta$, then $V_c(\pi_{k+1})\le V_c(\pi_k)+\mathbb E_{s\sim d^{\pi_k},a\sim\pi_{k+1}}[A_c^{\pi_k}(s,a)]+\frac{\sqrt{2\delta(\beta)}\gamma\epsilon_c^{\pi_{k+1}}}{1-\gamma}$ with $\delta(\beta)=\delta-\beta\bar D_\phi(\pi_{k+1}\|\pi_k)\le\delta$. Here $V_c=(1-\gamma)J_c$ is normalised, while $A_c^{\pi_k}$ and $\epsilon_c^{\pi_{k+1}}$ are the unnormalised quantities of Section 2. Dividing by $1-\gamma$ gives exactly the KL-form cost bound of Section 2 (the ingredient of CPO's Prop. 2) with the smaller radius $\delta(\beta)$. The proof needs the old-occupancy mean KL, $\bar D_{\mathrm{KL}}(\pi_{k+1}\|\pi_k)=\bar D_C-\beta\bar D_\phi\le\delta(\beta)$, which is why the hypothesis must be on $\bar D_C$; the paper writes $D_C(\pi_{k+1}\|\pi_k)$, whose Kakade part $\sum_sd^{\pi_{k+1}}(s)D_{\mathrm{KL}}(\pi_{k+1}\|\pi_k)[s]$ is weighted by the new occupancy. (Normalisation caveat: the paper also normalises the advantages, $A_{c,N}=(1-\gamma)A_c$. In that convention its printed surrogate and remainder each miss a factor $1/(1-\gamma)$; the consistent form is $V_c(\pi_{k+1})\le V_c(\pi_k)+\frac{1}{1-\gamma}\mathbb E[A_{c,N}]+\frac{\sqrt{2\delta(\beta)}\gamma\epsilon_{c,N}}{(1-\gamma)^2}$ with $\epsilon_{c,N}=(1-\gamma)\epsilon_c$. See the normalisation pitfall in Section 1.)
Setting of Thms. 4.4–4.5. A finite MDP in which every policy visits every state ($d^\pi(s)\gt0$, e.g. $\mu(s)\gt0$). The mirror function of $D_C$ is $\Phi_C(d)=\sum_{s,a}d(s,a)\log\frac{d(s,a)}{\sum_{a'}d(s,a')}+\sum_i\beta_i\phi_i\big(b_i-\langle c_i,d\rangle\big)$, $\beta_i\gt0$ (conditional entropy plus barriers on the margins), defined on safe occupancies with positive entries and strictly positive margins. Its Hessian pulled back to parameters is the metric $G_C(\theta)=J(\theta)^\top\nabla^2\Phi_C(d_\theta)J(\theta)$, with $J(\theta)$ the Jacobian of $\theta\mapsto d_{\pi_\theta}$; $G_C^+$ is its Moore–Penrose pseudoinverse (Primer A), not a positive part. A regular parameterisation is surjective onto the strictly positive policies with a Jacobian of maximal rank everywhere, e.g. tabular softmax.
Thm. 4.4 (safety during training). For $\phi$ steep at the boundary and a regular parameterisation, the safe parameter set is invariant (Primer D) under the continuous-time constrained natural policy gradient flow $\partial_t\theta_t=G_C(\theta_t)^+\nabla V_r(\theta_t)$: started strictly inside the safe set, the flow exists for all times and never leaves it.
Thm. 4.5. Under the same conditions the flow converges to the optimal safe value, and the limit policy is the $D_C$-projection of $\pi_0$ onto the set of optimal safe policies. (This description needs $\Phi_C$ to stay finite on the optimal face, as for $\phi(m)=m\log m$; for a barrier that is infinite there, such as $-\log m$, it holds only in a limiting sense.)
In words. The idealised continuous-time flow never leaves the safe set; a finite, noisy step inherits this only approximately (estimation errors can push an iterate out, hence the recovery mode). Note on the steepness condition: the paper writes it as $\phi'(x)\to+\infty$ for $x\searrow0$; for a convex $\phi$ the derivative is non-decreasing, and what the proof uses (a gradient of the mirror map that blows up at the boundary) is $|\phi'(x)|\to\infty$, i.e. $\phi'(x)\to-\infty$, as for $-\log x$ or the $x\log x$ used in their experiments.
Empirically, on 8 Safety-Gymnasium tasks (4 navigation, 4 locomotion; 10M steps, 5 seeds, interquartile means with bootstrap confidence intervals, $\beta=1$) C-TRPO is competitive in return with the best baselines, is safe at the last iterate where CPO and CUP are not, and has notably lower cost regret over training, $\sum_k[J_c(\pi_k)-d]_+$ summed over the training iterates (violations add up; safe iterates cannot cancel them), than the other high-return algorithms (comparable to PCPO; P3O's regret is lower still, at a price in return).
An interquartile mean averages the middle half of the ordered scores, reducing the influence of extreme runs. A bootstrap interval repeatedly resamples the specified experimental units with replacement and recomputes the score. State whether those units are seeds, tasks, or episodes; episodes from one trained policy are not independent training runs. Such an interval estimates uncertainty in an aggregate score, not a pathwise safety guarantee.
For sorted scores $1,2,3,20$, the middle-half mean is $(2+3)/2=2.5$. A bootstrap draw might repeat one seed and omit another; its interval describes the chosen aggregation, not every task.
CRPO: no multipliers at all
Xu, Liang & Lan, ICML 2021 alternate between objectives instead of pricing them: if every estimated constraint satisfies $\hat J_{c_i}\le d_i+\eta$ (a tolerance), take one policy step on the reward; otherwise take one step that decreases a violated constraint; output an iterate drawn uniformly from those where the constraints held. For tabular softmax policies with NPG steps and TD critics, their Theorem 1 gives, with probability $1-\delta$, both $J(\pi^\star)-\mathbb E[J(w_{\rm out})]$ and $\mathbb E[J_{c_i}(w_{\rm out})]-d_i$ of order $\sqrt{|\mathcal S||\mathcal A|}/\big((1-\gamma)^{1.5}\sqrt T\big)$: a primal method with global convergence despite the non-convexity. The precise statement:
Assume a finite discounted CMDP, $0\lt\gamma\lt1$, $|r|,|c_i|\le C$, a feasible optimal policy $\pi^*$, and a finite tabular-softmax initial parameter $w_0$ (hence positive probabilities). Let $n=|\mathcal S||\mathcal A|$, $K=\mathbb E_{s\sim d^{\pi^*}}D_{\rm KL}(\pi^*\|\pi_{w_0})[s]$, $B_T=\sqrt n/((1-\gamma)^{3/2}\sqrt T)$. Run $T$ updates $w_0,\dots,w_{T-1}$ ($w$ are the softmax parameters) with the tabular natural-gradient update of CRPO, step size $\alpha=(1-\gamma)^{3/2}/\sqrt{nT}$, tolerance $\eta=2B_T(3+K+3C+C^2)$, and cost tests formed by averaging the critics under $\mu$ and the current action probabilities. For definiteness take $T\ge1/(n(1-\gamma))$ so $\alpha\le(1-\gamma)^2$.
Require the critic estimates, clipped to their bounded value range, to satisfy $\max_i\|\widehat Q_t^i-Q_{\pi_t}^i\|_2\le\sqrt{(1-\gamma)n/T}$ at every update $t$, simultaneously on an event of probability at least $1-\delta$; $i=0$ denotes reward and $i\ge1$ a cost. This implies the cumulative error bound $\sum_t\|\widehat Q_t^{i_t}-Q_{\pi_t}^{i_t}\|_2\le\sqrt{(1-\gamma)nT}$ for any selected sequence $i_t$. This explicit accuracy assumption replaces a hidden choice of the number of TD iterations; exact critics satisfy it. Then the set $\mathcal N_0$ of iterates that passed the cost test is nonempty, and $w_{\rm out}$ drawn uniformly from $\mathcal N_0$ obeys
The high-probability event concerns learning data; the displayed expectation concerns output selection. Switching gives enough reward steps or already good reward, while the cost test bounds the output violation. Finite support, a finite initial KL and the stated critic accuracy are essential; this is not a last-iterate or per-trajectory guarantee.
| Method | Update | Constraint enters as | What is proved | Cost per iteration |
|---|---|---|---|---|
| CPO (2017) | 2nd-order trust region, linearised | intersection, dual solved exactly each step | per-step worst case for the exact update (Prop. 2) | 2 CG solves + line search |
| PCPO (2020) | TRPO step, then projection | projection (KL or $L_2$) | Thms. 3.1/3.2 for KL projection | TRPO + projection |
| FOCOPS (2020) | closed form in policy space, then KL regression | Gibbs reweighting, $\nu$ by dual descent | CPO-type bound for $\pi^\star$ only | first order |
| CUP (2022) | GAE surrogate + projection | first-order primal–dual projection | reported Thm. 2; KL/penalty qualifications above; exact multi-step bound stated separately | first order |
| P3O (2022) | one penalised clipped loss | exact ReLU penalty $\kappa$ | exactness for $\kappa\gt\|\bar\lambda\|_\infty$ (saddle point) | PPO |
| IPO (2020) | clipped loss + log barrier | barrier, weight $1/t$ | $m/t$ gap (convex case) | PPO |
| CVPO (2022) | EM, off-policy | 2-D convex dual in the E-step | E-step optimality under Slater | critics + particles |
| C-TRPO (2025) | TRPO with a safe Bregman trust region | geometry + recovery with hysteresis | invariance of the safe set for the flow (Thm. 4.4) | like TRPO |
| CRPO (2021) | switch between reward and cost steps | tolerance test | $O(1/\sqrt T)$ rates, tabular softmax | base optimiser |
5. Model-Based Safe RL: LAMBDA, SafeDreamer, ActSafe, SOOPER
Model-free safe RL pays for safety in samples: Safety Gym agents train for $10^7$ (Point, Car) to $10^8$ (Doggo) steps and incur cost the whole time. Model-based methods learn the dynamics and optimise the policy (at least partly) in imagination, which cuts real interaction, at the price of model error. The recurring design principle of the ETH line of work is the RL version of SafeOpt's confidence bounds (Module 4): be optimistic about reward (to explore) and pessimistic about cost (to stay safe) over the set of models that are statistically plausible given the data.
LAMBDA: posterior sampling plus an augmented Lagrangian
A latent world model encodes observations into a learned vector, predicts the next vector from the current vector and action, and predicts reward and cost there. Imagined rollouts repeatedly apply these learned maps. SWAG approximates uncertainty in network weights by fitting a Gaussian to selected SGD iterates. Sampling those weights produces alternative models; their spread is not automatically a calibrated confidence set for the true dynamics.
For example, an image of a moving robot may be encoded by a 32-number vector; alternative weight samples predict different next vectors. Their disagreement is model uncertainty, whereas fresh process noise can remain even with the correct weights.
As, Usmanova, Curi & Krause, ICLR 2022 use a Dreamer-style latent world model with an approximate posterior over its weights (SWAG, a Gaussian fitted to SGD iterates; Primer C), and solve
where $\mathcal P$ is the set of statistically plausible models. The inner maxima are estimated by sampling $N$ models from the posterior, simulating trajectories under each, and keeping the largest estimate, separately for the objective and for every constraint (their Alg. 1). The policy is trained by back-propagating through imagined rollouts with the augmented Lagrangian below. There is no formal guarantee: the authors state the optimism/pessimism combination as a conjecture and support it with Safety Gym experiments, where LAMBDA was markedly more sample efficient than model-free baselines at publication.
Step 1 (why not the plain Lagrangian). $\max_\pi\min_{\lambda\ge0}J(\pi)-\lambda(J_c(\pi)-d)$ equals $J(\pi)$ for feasible $\pi$ and $-\infty$ otherwise: exact but non-smooth, useless for gradient steps.
Step 2 (proximal relaxation). Keep the multiplier close to its previous value $\lambda_k$ with a proximal term of weight $1/(2\mu_k)$, $\mu_k$ non-decreasing:
by setting the derivative $-(J_c-d)+(\lambda-\lambda_k)/\mu_k$ to zero and projecting onto $\lambda\ge0$ (the objective is a strictly convex quadratic in the single variable $\lambda$, so the projection of its stationary point onto $[0,\infty)$ is the minimiser).
Step 3 (plug back). If $\lambda_k+\mu_k(J_c-d)\ge0$ the minimum equals $-\lambda_k(J_c-d)-\frac{\mu_k}{2}(J_c-d)^2$; otherwise ($\lambda=0$) it equals $\lambda_k^2/(2\mu_k)$. Writing the result as $-\Psi$,
This is LAMBDA's Eq. 8 and SafeDreamer's Eq. 8. (LAMBDA prints the proximal weight as $1/\mu_k$; the factor $\tfrac12$ is what makes its multiplier update and its $\Psi$ consistent with each other.) Far inside the feasible region the penalty is a constant; near or beyond the boundary it adds a quadratic term, which is the "local convexification" that CAL (Wu et al., ICLR 2024) also uses to stabilise off-policy primal–dual updates.
SafeDreamer: constrained planning in DreamerV3
BSRP-Lag below trains the actor with three standard ingredients. The TD($\lambda$) return ($\lambda\in[0,1]$ here is the TD parameter, not a multiplier; Primer E) obeys $G_t^\lambda=r_t+\gamma[(1-\lambda)V(s_{t+1})+\lambda G_{t+1}^\lambda]$, with value zero after a terminal state and a critic bootstrap at the end of a rollout. REINFORCE multiplies an advantage by $\nabla\log\pi(a\mid s)$ (Primer E); an entropy bonus rewards spread-out action probabilities. The stop-gradient $\mathrm{sg}(x)$ has value $x$ but is treated as a constant when differentiating, so the actor does not differentiate through its target.
Huang, Ji, Xia, Zhang & Yang, ICLR 2024 add costs to DreamerV3 in three ways. OSRP plans online with a constrained cross-entropy method in the world model: if fewer than $N_s$ sampled action sequences are predicted safe, the candidates are ranked by predicted cost (safest first), otherwise only the safe ones are kept and ranked by predicted return; the elites refit the sampling distribution. (The cross-entropy method is a sampling optimiser, unrelated to entropy bonuses: sample action sequences from a Gaussian, keep the top-ranked "elite" sequences, replace the Gaussian's mean and covariance by theirs, repeat for a few rounds, execute the first action of the final plan and plan again at the next state.) OSRP-Lag ranks the safe candidates by $J_R-\lambda_pJ_C$ with $\lambda_p$ driven by a PID Lagrangian on the episode cost (Module 8). BSRP-Lag trains the actor in the background on imagined rollouts (length 15) to maximise the TD($\lambda$) reward return $R^\lambda$ plus an entropy bonus $\eta\,\mathcal H[\pi_\theta(\cdot\mid s_t)]$, minus the augmented-Lagrangian penalty $\Psi$ above applied to the TD($\lambda$) cost return $C^\lambda$ (multipliers $\lambda_p^k,\mu^k$ held fixed during the actor step). The gradient must reach $\theta$ through the returns. In the authors' code the reward term is the normalised advantage, back-propagated through the world model for continuous actions (DreamerV3's dynamics backpropagation) or used as a REINFORCE weight, $-\log\pi_\theta(a_t\mid s_t)\,\mathrm{sg}(\cdot)$, for discrete actions; the cost return, averaged over the imagined batch, enters $\Psi$ without a stop-gradient. The paper's Eq. (7) prints the loss as $-\sum_t\big[\mathrm{sg}(R^\lambda(s_t))+\eta\,\mathcal H[\pi_\theta(\cdot\mid s_t)]-\Psi\big(\mathrm{sg}(C^\lambda(s_t)),\lambda_p^k,\mu^k\big)\big]$ ($\mathrm{sg}$ the stop-gradient). Read literally, with both returns stopped and no log-probability factor, only the entropy term of that expression would have a gradient. Reported: nearly zero cost on low-dimensional and vision-only Safety-Gymnasium tasks, with the cost limit lowered from the conventional 25 to 2.0 (zero was avoided because of errors of the learned cost model). The constraint remains an expected episode cost and the evidence is empirical.
ActSafe: safety and sample complexity with a calibrated model
Assumptions. (4.1) $f^\ast$ is $L_f$-Lipschitz (see Primer B), $c$ is $L_c$-Lipschitz, all policies are continuous; (4.2) i.i.d. Gaussian process noise $w_t\sim\mathcal N(0,\sigma^2I)$; (4.3) a non-empty initial safe set of policies $S_0$ with $J_c(\pi)\le d$; (4.5) each $f_j^\ast$ is in an RKHS with $\|f_j^\ast\|_k\le B$ and $k(z,z)\le\sigma_{\max}$.
Algorithm. Expand a pessimistic safe set $S_n=S_{n-1}\cup\{\pi\notin S_{n-1}:\exists\pi'\in S_{n-1},\ P_n(\pi')+D(\pi,\pi')\le d\}$, where $D(\pi,\pi')$ bounds how much the cost can change between two policies (built from $L_c$, $L_f$, $\sigma$ and $C_{\max}$). For $n^\star$ episodes run the policy in $S_n$ (and the optimistic model in $\mathcal M_n$) that maximises the accumulated epistemic uncertainty $\mathbb E\sum_t\|\sigma_{n-1}(\hat s_t,\pi(\hat s_t))\|$, then exploit.
Statement. With probability at least $1-\delta$: $J_c(\pi_n,f^\ast)\le d$ for all $n\ge0$; and for $n\ge n^\star$ (defined through the maximum information gain $\Gamma_n$, written $\gamma_n(k)$ in the paper, and $\beta_n(\delta)$, $H$, $T$, $\epsilon$), the pessimistic exploitation policy is $\epsilon$-optimal within $R^\epsilon_H(S_0)$, the set reachable from $S_0$ by $H$ expansion steps with $\epsilon$-precise dynamics.
Why each assumption matters. Lipschitz continuity makes the expansion operator sound (nearby policies have nearby costs); the RKHS bound $B$ makes the model calibrated (with a misspecified $B$ the safety guarantee is void, exactly as for SafeOpt in Module 5); the safe seed is unavoidable, since nothing can be certified from nothing. Optimality is only relative to $R^\epsilon_H(S_0)$, as in SafeOpt.
A practical version with a Dreamer-style ensemble scales to visual control, without the guarantee. ActSafe is also discussed as a safe-exploration method in Module 6.
SOOPER: a safe prior policy as the fallback
Wendl, As, Prajapat, Pollak, Coros & Krause, ICLR 2026 replace ActSafe's reward-free expansion phase by a fallback: a conservative prior policy $\hat\pi$ (from a simulator or offline data) takes over whenever the realised cost plus the prior's pessimistic cost-to-go could exceed the budget.
Rule. With $c_{\lt t}=\sum_{\tau\lt t}\gamma^\tau c(s_\tau,a_\tau)$ the discounted cost already incurred and the pessimistic cost-to-go of the prior $$\begin{aligned}Q_{c,n}^{\hat\pi}(s,a)&=\mathbb E^{\hat\pi}\Big[\sum_t\gamma^t\big(c(s_t,a_t)+\lambda_{\rm pess}\|\sigma_n(s_t,a_t)\|\big)\,\Big|\,s_0=s,a_0=a\Big],\\ \lambda_{\rm pess}&=\bar C\,\frac{\gamma}{1-\gamma}\,\frac{(1+\sqrt{d_S})\,\beta_N(\delta)}{\sigma},\end{aligned}$$ ($\bar C=\max\{C_{\max},k_{\max}\}$), execute $a_t\sim\pi_n(\cdot\mid s_t)$ if $\Phi_t:=c_{\lt t}+\gamma^tQ^{\hat\pi}_{c,n}(s_t,a_t)\lt d$ and switch to $\hat\pi$ otherwise (for the rest of the episode); $\bar\pi_n$ denotes this switched, history-dependent policy.
Statement. With probability $1-\delta$, $J_c(\bar\pi_n,f)\le d$ in every episode $n=1,\dots,N$ (Thm. 1), and the cumulative regret satisfies $\sum_{n=1}^N\big(J_r(\pi_c^\ast,f)-J_r(\bar\pi_n,f)\big)\le O\big(\Gamma_{N\log N}^{7/2}\sqrt N\big)$ (Thm. 2), with $\Gamma$ the maximum information gain. (The published proof of Thm. 1 does not handle the random switching time under stochastic transitions; see the proof sketch below.)
Why each assumption matters. The penalty $\lambda_{\rm pess}\|\sigma_n\|$ replaces an intractable maximisation over $\mathcal F_n$; it is an upper bound only on the calibration event, which needs the RKHS bound. The prior is the "safe seed" of this method. The comparison $V_c^{\hat\pi}\le V_c^{\pi_c^\ast}$, the density bound $p_{\max}$ and the gap $\delta_c$ enter only the regret proof, where they bound how often, and at what price, the prior interrupts a near-optimal policy. Sublinear regret means regret$/N\to0$: on average the episodes become as good as the comparator (Primer 0). Here it needs $\Gamma_N$ to grow slower than $N^{1/7}$ (true for kernels with rapidly decaying spectra, such as the squared exponential; not for every kernel).
Work on the calibration event, where $Q_{c,n}^{\hat\pi}$ upper-bounds the true expected discounted cost of "take $a$, then follow $\hat\pi$ forever" (their Lemma 2). Let $\bar V_c^{\hat\pi}(s)$ be a pessimistic bound on the prior's expected discounted cost from $s$ (a natural candidate is $\mathbb E_{a\sim\hat\pi}Q_{c,n}^{\hat\pi}(s,a)$), and consider the committed-plus-promised cost $M_t=c_{\lt t}+\gamma^t\bar V_c^{\hat\pi}(s_t)$: what has been paid plus a pessimistic promise for the rest of the episode if the prior took over now. At $t=0$ the prior is safe by Assumption 4, $\mathbb E[M_0]\le d$ (in expectation over the initial state). If the test passes at time $t$, the executed $a_t$ satisfies $c_{\lt t}+\gamma^tQ_{c,n}^{\hat\pi}(s_t,a_t)\lt d$, and since $Q^{\hat\pi}(s_t,a_t)=c(s_t,a_t)+\gamma\,\mathbb E[V^{\hat\pi}(s_{t+1})]$, this would bound the conditional expectation of $M_{t+1}$ by $d$, provided $\bar V_c^{\hat\pi}$ also satisfies this Bellman inequality under the true transitions ($Q_{c,n}^{\hat\pi}$ satisfies it under the learned pessimistic model). Even then it bounds $\mathbb E[M_{t+1}\mid\mathcal F_t]$ by the constant $d$, not by $M_t$, which is not the supermartingale property used below. If the test fails at a (random) time $\tau$, the prior takes over for good, and the episode's expected cost is at most the promise $M_\tau$ at that time.
The gap. Their Lemma 1 concludes that $\mathbb E[M_\tau]\lt d$: the total expected cost is bounded by "the last promise, whose expectation is below $d$". That does not follow. The switching time is random, and the learner keeps running exactly on the branches where the promise turned out low. Example with $d=1$, $\gamma=0.9$: the first action costs nothing and leads, with probability $\tfrac12$ each, to a state where the prior's discounted promise is $0$ or $1.8$, so its test value is $0.9\lt1$ and it passes. On the high branch every test fails ($1.8\ge1$) and the prior finishes the episode at cost $1.8$. On the low branch an action of discounted cost $0.9$ passes its test ($0.9\lt1$) and ends in a cost-free state. Every executed test passed and the prior is safe from the start, yet the expected discounted cost is $\tfrac12\cdot1.8+\tfrac12\cdot0.9=1.35\gt d$.
What would suffice. Let $\mathcal F_t$ be the information available before $a_t$ is chosen (Primer C), and let $\bar V_c^{\hat\pi}\ge0$ be one fixed function that bounds the prior's true expected remaining cost. If $M_t$ is a supermartingale along every executed branch, $\mathbb E[M_{t+1}\mid\mathcal F_t]\le M_t$, and $\mathbb E[M_0]\le d$, the optional stopping theorem gives $\mathbb E[M_\tau]\le\mathbb E[M_0]\le d$: directly for a bounded switching time, and for an unbounded one because $M_t\ge0$ (apply it to $\min(\tau,n)$ and let $n\to\infty$ with Fatou's lemma; the same limit covers episodes that never switch). The episode's expected cost is then at most $\mathbb E[M_\tau]\le d$. The threshold test does not provide the supermartingale property: the counterexample passes every test. If the transitions are deterministic and the prior's promise is at most $d$ from every initial state, the test value is the next promise, $M_{t+1}\lt d$ after every accepted step, and the argument goes through path by path. Under SOOPER's Gaussian noise, Thm. 1 needs an additional stopping-time argument that neither this sketch nor the published induction supplies. The switch is decided on realised costs, so the safeguard reacts to the actual trajectory; the claimed guarantee is on the expected discounted cost, on the calibration event.
Exploration happens in the model: SOOPER trains $\pi_n$ on a "planning MDP" that terminates wherever the prior would be invoked and pays the prior's pessimistic return at termination, plus intrinsic exploration and expansion bonuses $(\lambda_{\rm explore}+\lambda_{\rm expand})\|\sigma_n\|$. On a real remote-controlled race car (60 Hz, prior from a first-principles simulator, five seeds) it roughly doubled the prior's reward while satisfying the constraint throughout learning.
6. Offline Safe RL: CPQ, COptiDICE, CDT, FISOR
Offline safe RL learns from a fixed dataset (see Primer E) $\mathcal D=\{(s,a,r,c,s')\}$ collected by unknown behaviour policies $\pi_\beta$, with no further interaction. Two problems compound. Distribution shift: values of actions outside the data support are pure extrapolation, and a policy that maximises them walks into them; standard offline RL counters this with pessimism (behaviour regularisation, conservative values). Constraint bias: a learned cost estimate is compared with an absolute threshold, so a small negative bias produces an unsafe policy and a positive one an overly conservative policy (the argument of the CDT paper); the multiplier cannot correct itself by observing violations, because there is nothing to observe. A third issue: regularising towards $\pi_\beta$ is harmful when most of the data is unsafe or low-reward (OASIS calls this the safe dataset mismatch).
CPQ: make out-of-distribution actions look unsafe
A conditional VAE learns an encoder distribution $q(z\mid s,a)$ and a decoder that reconstructs actions from state and latent vector $z$, using a simple prior such as $\mathcal N(0,I)$. CPQ treats a large encoder-to-prior KL as an OOD score; it is not a proof that an action is unsafe.
For example, $q(z\mid s,a)=\mathcal N(3,1)$ has KL $4.5$ from $\mathcal N(0,1)$, whereas $q=\mathcal N(0,1)$ has KL zero. This is a learned support heuristic, not a physical failure test.
Xu, Zhan & Zhu, AAAI 2022 train a conditional VAE on the data and flag a policy action as out-of-distribution when its latent posterior is far from the prior ($D_{\mathrm{KL}}(q(z\mid s,a)\|\mathcal N(0,I))$ above a threshold); $\nu$ denotes the distribution of these flagged actions. Then
with $\mathcal T^\pi Q_c(s,a)=c(s,a)+\gamma\,\mathbb E_{s'\sim P(\cdot\mid s,a),\,a'\sim\pi(\cdot\mid s')}Q_c(s',a')$ the cost Bellman operator (Primer E; in the loss, the recorded successor $s'$ samples the expectation), $l$ the cost limit and $\alpha$ tuned automatically so that OOD cost values settle above $l_c=1.5\,l$. The penalty pushes the cost value of flagged actions up, the ordinary Bellman error keeps in-distribution values honest, and the indicator makes the policy treat anything the cost critic distrusts as having zero value. Safety is only as good as the OOD detector and the cost critic.
COptiDICE: optimise the occupancy ratio directly
Lee, Paduraru, Mankowitz, Heess, Precup, Kim & Guez, ICLR 2022 start from the occupancy LP of Module 8 and never represent a $Q$-function. In their normalised convention $V_R(\pi)=\mathbb E_{(s,a)\sim d^\pi}[R]$ and budgets $\hat c_k$ are per-step averages.
Step 1 (Lagrangian). Attach $\lambda\in\mathbb R^K_+$ to the cost constraints and a free multiplier $\nu(s')$ to each Bellman-flow equality. The flow term is
so all $d$-dependent terms collect into $\mathbb E_{(s,a)\sim d}[e_{\lambda,\nu}(s,a)]-\alpha D_f(d\|d^{\mathcal D})$: $\nu$ acts as a value-like potential and $e_{\lambda,\nu}$ is its Bellman residual for the scalarised reward $R-\lambda^{\top}C$. It is an actual advantage only if $\nu$ equals the value function of some policy for that reward, which the derivation never assumes.
Step 2 (change of variables). $\mathbb E_{d}[e]=\mathbb E_{d^{\mathcal D}}[w\,e]$ with $w=d/d^{\mathcal D}$, which removes every expectation under the unknown $d$ and every appearance of $T$ except the conditional expectation $\mathbb E_{s'\sim T(s,a)}\nu(s')$ inside $e$. For a fixed $w$ the objective is linear in $e$, so the sampled successor $s'$ of a data tuple estimates it without bias; after Step 3 this is no longer true (Step 4).
Step 3 (inner maximisation, pointwise). For each $(s,a)$ maximise $w\,e-\alpha f(w)$ over $w\ge0$; with $\alpha\gt0$ and $f$ strictly convex it is strictly concave. For differentiable $f$ its derivative is $e-\alpha f'(w)$. If $e/\alpha\gt f'(0)$, the maximiser is the root of $f'(w)=e/\alpha$ (when one exists); if $e/\alpha\le f'(0)$, the derivative is $\le0$ on all of $w\ge0$ and the maximum sits at $w=0$. Both cases are $w^\ast=\big((f')^{-1}(e/\alpha)\big)_+$, with $(f')^{-1}$ extended by any value $\le0$ below $f'(0)$. Example: $f(x)=\tfrac12(x-1)^2$ ($\chi^2$) gives $w^\ast=\max\big(0,1+e_{\lambda,\nu}/\alpha\big)$: over-weight state-actions with positive scalarised advantage, drop those whose advantage is below $-\alpha$.
Step 4 (dual). Plugging $w^\ast$ back gives $L(\lambda,\nu)$, a pointwise maximum of functions affine in $(\lambda,\nu)$, hence convex (Fenchel duality, Primer B: $\max_w\{we-\alpha f(w)\}=\alpha f^\ast(e/\alpha)$ with $f^\ast$ the convex conjugate of $f$ restricted to $w\ge0$). With $\lambda$ fixed this is OptiDICE for the reward $R-\lambda^{\top}C$; the $\lambda$-update is again "raise the price while the (estimated) cost $\mathbb E_{d^{\mathcal D}}[w^\ast C]$ exceeds $\hat c$". $\square$
What is actually computed. After Step 3 the conditional expectation over $s'$ sits inside the nonlinear $\alpha f^\ast(e/\alpha)$. The practical loss (their Eq. 23) instead plugs the single-sample residual $\hat e(s,a,s')=R-\lambda^{\top}C+\gamma\nu(s')-\nu(s)$ into $w^\ast$ and $f$. Because $f^\ast$ is convex, Jensen's inequality makes this sampled objective an upper bound on $L(\lambda,\nu)$, biased in general. The two coincide for deterministic transitions (e.g. MuJoCo control, as the paper notes); for stochastic transitions the exact dual needs the conditional expectation before the conjugate is applied.
Two further ingredients make it safe in practice. The cost estimate $\mathbb E_{d^{\mathcal D}}[wC]$ is replaced by an upper bound: the data distribution is adversarially reweighted within a KL ball of radius $\epsilon$ (subject to a Bellman-flow compatibility constraint), in the spirit of CoinDICE, and by the same duality argument this reduces, per cost, to an unconstrained log-sum-exp minimisation over a scalar temperature $\tau\ge0$ (the multiplier of the KL ball) and a state function $\chi(s)$ (the multiplier of the flow constraint), all estimable from the dataset (their Prop. 2). And since $w^\ast$ is a ratio, not a policy, the policy is extracted by importance-weighted behaviour cloning, $\max_\pi\mathbb E_{d^{\mathcal D}}[w^\ast(s,a)\log\pi(a\mid s)]$.
Fix finite tuple support $x=(s_0,s,a,s')$, a positive reference law $q(x)$, a fixed nonnegative ratio $w(s,a)$, bounded cost $C$, and $0\le\gamma\lt1$. Put $b_y(x)=(1-\gamma)\mathbf1[s_0=y]+w(s,a)(\gamma\mathbf1[s'=y]-\mathbf1[s=y])$. For $\epsilon\gt0$ define $\mathcal U=\{p\ge0:\sum_xp(x)=1,\ D_{\rm KL}(p\|q)\le\epsilon,\ \mathbb E_p b_y=0\ \forall y\}$. If this set has a relative-interior point with KL strictly below $\epsilon$, then
At $\tau=0$ use the limit of the log-sum-exp term, not division by zero. The $b_y$ equations enforce discounted flow for the weighted occupancy. The true normalised policy cost is bounded by this supremum only on an event where a law $p_{\rm true}\in\mathcal U$ also makes $wp_{\rm true}(s,a)$ that policy’s true occupancy. Finite support and strict feasibility justify duality; inclusion supplies the statistical interpretation. A fitted ratio or a chosen radius alone supplies neither inclusion nor coverage.
The adversary reallocates data mass towards expensive compatible transitions. Its dual replaces a search over distributions by a temperature and a state potential.
At a state $s$, $\max_\pi\sum_ad^{\mathcal D}(s,a)w^\ast(s,a)\log\pi(a\mid s)$ over probability vectors is a weighted maximum-likelihood problem; with a Lagrange multiplier for $\sum_a\pi(a\mid s)=1$ (Primer B), stationarity gives $\pi(a\mid s)\propto d^{\mathcal D}(s,a)w^\ast(s,a)$. So, at a state with positive total weight, the unrestricted fit is $\pi(a\mid s)=d^{\mathcal D}(s,a)w^\ast(s,a)/\sum_{a'}d^{\mathcal D}(s,a')w^\ast(s,a')$. The denominator normalizes the action probabilities. If it is zero, this objective supplies no policy information at that state. A neural fit may only approximate these probabilities.
CDT: condition on the cost-to-go
Here $o_t$ denotes the available sequence of states, past actions, and reward/cost target tokens up to time $t$. A token is a vector representation of one of those inputs. A causal transformer processes this history without seeing future observations and outputs the next action distribution. The scalar target updates are bookkeeping inputs to this predictor, not constraints imposed by its architecture.
For example, the inputs “state, target cost 10, past action, next state, target cost 8” condition the next prediction after spending cost 2. Causal attention lets each input use only earlier inputs.
Liu, Guo, Yao, Cen, Yu, Zhang & Zhao, ICML 2023 treat offline safe RL as sequence modelling. A decision transformer receives, besides states and past actions, two return tokens: the reward-to-go $R_t=\sum_{t'\ge t}r_{t'}$ and the cost-to-go $C_t=\sum_{t'\ge t}c_{t'}$ (undiscounted), and outputs a Gaussian policy $\pi_\theta(\cdot\mid o_t)=\mathcal N(\mu_\theta(o_t),\Sigma_\theta(o_t))$ trained by $\min_\theta\mathbb E_{o}\big[-\log\pi_\theta(a\mid o)-\lambda\,\mathcal H[\pi_\theta(\cdot\mid o)]\big]$ (here $\lambda$ is an entropy weight, not a multiplier). At deployment the user sets the targets $(R_1,C_1)=(\rho,\kappa)$ and after each step updates $R_{t+1}=R_t-r_t$, $C_{t+1}=C_t-c_t$: zero-shot adaptation to a new cost threshold means simply starting from a different $C_1$, without retraining. Because a target pair $(\rho,\kappa)$ may be infeasible for the data (no trajectory with cost $\le\kappa$ reaches return $\rho$), CDT augments the data by relabelling: sample $\kappa$ and an infeasible $\rho$, find the highest-return trajectory $\tau^\ast$ with cost $\le\kappa$, and add a copy of $\tau^\ast$ whose reward-to-go tokens are shifted by $\rho-R(\tau^\ast)$ and cost-to-go tokens by $\kappa-C(\tau^\ast)$. These examples encourage the policy to reproduce the best supported safe trajectory when asked for too much, giving the cost token priority in the training targets. The paper itself lists the lack of a rigorous safety guarantee as a limitation: conditioning is imitation, not constraint enforcement (Exercise 6).
FISOR: hard constraints via a feasible region
Zheng, Li, Yu, Yang, Li, Zhan & Liu, ICLR 2024 replace the expected-cost budget by a state-wise hard constraint $h(s_t)\le0$ for all $t$ and use dynamic-programming safety values (defined below; Module 10 gives the Hamilton–Jacobi reachability view), following the online method RCRL of Yu, Ma, Li & Chen, ICML 2022.
Assume deterministic dynamics $s'=f(s,a)$ and bounded $h$ (Primer D for the dynamic-programming principle). Define $V_h^*(s)=\inf_\pi\sup_{t\ge0}h(s_t)$ and $Q_h^*(s,a)=\max\{h(s),V_h^*(f(s,a))\}$. Then $V_h^*(s)=\inf_aQ_h^*(s,a)$: an action must keep both the present state and the future trajectory safe. This is the dynamic-programming form of Module 7's viability kernel. Module 10 develops the reachability connection further. Stochastic dynamics require a separately stated expected, almost-sure, or worst-case formulation.
Decoupled problem. Fix a state $s$, let $p_0=\pi_\beta(\cdot\mid s)$, $A_r^\ast=Q_r^\ast-V_r^\ast$, $A_h^\ast=Q_h^\ast-V_h^\ast$ (bounded tables), and let $\alpha_1,\alpha_2\gt0$ be inverse temperatures (larger values concentrate probability more strongly). In a feasible state ($V_h^\ast(s)\le0$) maximise $\sum_ap(a)A_r^\ast(s,a)-\alpha_1^{-1}D_{\mathrm{KL}}(p\|p_0)$ over distributions $p$ on the safe actions $S_s=\{a:Q_h^\ast(s,a)\le0\}$, assuming $p_0(S_s)\gt0$; in an infeasible state minimise $\sum_ap(a)A_h^\ast(s,a)+\alpha_2^{-1}D_{\mathrm{KL}}(p\|p_0)$.
Statement (Thm. 1). The optimal solution is weighted behaviour cloning, $\pi^\ast(a\mid s)\propto\pi_\beta(a\mid s)\,w(s,a)$, with $$w(s,a)=\begin{cases}\exp\big(\alpha_1A_r^\ast(s,a)\big)\,\mathbf 1\big[Q_h^\ast(s,a)\le0\big], & V_h^\ast(s)\le0,\\ \exp\big(-\alpha_2A_h^\ast(s,a)\big), & V_h^\ast(s)\gt0,\end{cases}$$ normalised by $Z(s)=\sum_a\pi_\beta(a\mid s)w(s,a)$, which is positive exactly when the behaviour policy gives mass to a safe action (weighted cloning cannot create safe actions the data never took). Proof: substituting $p^\ast$ turns the gap to any other admissible $p$ into $\alpha_i^{-1}D_{\mathrm{KL}}(p\|p^\ast)\ge0$, the Gibbs argument of FOCOPS. Exact safety additionally needs the exact undiscounted feasibility values; approximate critics and a finite diffusion fit do not inherit the hard mask automatically.
In words. Inside the region from which the constraint can be kept forever, imitate the rewarding actions that keep you inside; outside it, imitate the actions that reduce the violation fastest. The same Gibbs reweighting as FOCOPS, with a hard feasibility mask instead of a price.
Assume a deterministic finite-state, finite-action system $s'=f(s,a)$, a nonempty action set at each state, bounded $h$, and $0\lt\gamma\lt1$. On real-valued state-action tables write FISOR's operator $\mathcal P^\ast$ as $T_\gamma Q=(1-\gamma)h(s)+\gamma\max\{h(s),\min_{a'}Q(f(s,a),a')\}$. Then $\|T_\gamma Q-T_\gamma\widetilde Q\|_\infty\le\gamma\|Q-\widetilde Q\|_\infty$. There is a unique fixed point $Q_\gamma$, and $\|T_\gamma^kQ_0-Q_\gamma\|_\infty\le\gamma^k\|Q_0-Q_\gamma\|_\infty$. In this finite deterministic setting, $Q_\gamma\to Q_h^*$ as $\gamma\uparrow1$, with $Q_h^*(s,a)=\inf_\pi\sup_{t\ge0}h(s_t)$ after initial action $a$.
Proof sketch. $|\max\{h,x\}-\max\{h,y\}|\le|x-y|$ and $|\min_{a'}Q(s',a')-\min_{a'}\widetilde Q(s',a')|\le\max_{a'}|Q(s',a')-\widetilde Q(s',a')|$, so min and max cannot enlarge the largest input error, and the factor $\gamma$ shrinks it (Banach fixed point, Primer 0). For the separate discount limit, a fixed stationary policy eventually repeats a state; the maximum on its finite prefix and cycle is attained in finite time. Its discounted stopping value tends to this maximum. There are finitely many deterministic stationary policies, so the limit commutes with their minimum. This also ensures the viability infimum is attained. Continuous or stochastic systems need additional assumptions and a specified safety semantics. A negative finite-discount estimate alone is not an undiscounted sign certificate.
For example, a forced transition from $h(s_0)=-1$ to an absorbing state with $h(s_1)=0.1$ gives $Q_{1/2}(s_1)=0.1$ and $Q_{1/2}(s_0)=-0.5+0.5(0.1)=-0.45$, but the undiscounted maximum is $0.1\gt0$.
The operator is FISOR's (Zheng et al., ICLR 2024); the limit statement and its proof sketch are the elementary finite deterministic case.
An expectile fits a scalar $v$ by minimizing $\mathbb E[|\tau-\mathbf1\{y-v\lt 0\}|(y-v)^2]$. With $\tau\lt 1/2$, overestimating low targets is penalized more heavily, moving the fit toward the lower tail. Applied to action values observed in the dataset, this approximates a low supported value without optimizing over unseen actions. A finite expectile level is not an exact minimum.
For equally likely targets $0$ and $2$, the expectile at $\tau=1/4$ solves $(3/4)v=(1/4)(2-v)$, hence $v=0.5$; the minimum is still $0$. Unlike a quantile, an expectile weights squared distances.
A diffusion policy starts from random noise and applies learned denoising steps conditioned on the state to produce an action. Training corrupts dataset actions with noise and teaches the model to reverse that corruption; weighting training examples favors actions with larger feasibility/reward weights. The claim of exact guidance concerns an ideal density-modeling objective under the cited theorem's assumptions, not a finite trained network or a guarantee that every sampled action is safe.
A simple corruption is $a_t=\sqrt{\bar\alpha_t}a_0+\sqrt{1-\bar\alpha_t}\epsilon$, $\epsilon\sim\mathcal N(0,I)$. The noise schedule $\bar\alpha_t$ decreases from near one towards zero. A typical weighted loss is $\mathbb E[w(s,a_0)\|\epsilon-\epsilon_\theta(a_t,s,t)\|_2^2]$. Here “energy” means minus log target weight, so guidance favours large weights.
$\pi^\ast$ is represented by a diffusion policy trained with the weighted denoising loss (their Thm. 2 shows the weighting gives exact energy guidance without a time-dependent classifier); at run time $N$ candidate actions are sampled and the one with the lowest $Q_h^\ast$ is executed. On DSRL with stringent limits (cost limit 10 on Safety-Gymnasium tasks, 5 on Bullet-Safety-Gym and MetaDrive; 20 episodes × 3 seeds) FISOR was the only method with normalised cost below 1 on all 26 tasks of that evaluation (9 Safety-Gymnasium, 8 Bullet-Safety-Gym, 9 MetaDrive). The price is visible in the same table: its average normalised reward on the Safety-Gymnasium tasks is 0.30, below CDT's 0.50, which however violates the limit (normalised cost 4.31).
Data shaping and online-learning views: OASIS and O3SRL
Yao, Cen, Ding et al., NeurIPS 2024 (OASIS) attack the safe-dataset mismatch at the data level: a conditional diffusion model trained on the dataset generates trajectories conditioned on high return and on cost below the limit, and an ordinary (Q-learning-based) offline safe RL agent is trained on the shaped data, with proposed shaping-error and violation bounds (their Thms. 1–2; the explicit distribution-compatibility qualification below is needed for a cost certificate). Chemingui, Deshwal, Fern, Nguyen-Tang & Doppa, NeurIPS 2025 (O3SRL) solve the Lagrangian game $\min_{\lambda\in[0,C]}\max_{D\in\Delta(\Pi)}\mathbb E_{\pi\sim D}[J(\pi)-\lambda(J_c(\pi)-\kappa)]$ by alternating an offline RL oracle on the shaped reward $r-\lambda\,(c-(1-\gamma)\kappa)$ with a no-regret update of $\lambda$; averaged iterates are an $\epsilon$-equilibrium with $\epsilon=\epsilon_{\rm offlineRL}(n)+R_T(\Lambda)/T$, and a bandit (EXP3) version over a grid of multipliers avoids off-policy evaluation. On eight Bullet-Safety-Gym tasks with a stringent threshold they report O3SRL as the only method satisfying the constraint on all eight.
$\Delta(\Pi)$ is the set of distributions over policies; drawing one policy per episode realizes a mixture. Write $L(\pi,\lambda)=J(\pi)-\lambda(J_c(\pi)-\kappa)$. Suppose each RL call is within $\epsilon_{\rm oracle}$ of maximizing $L(\cdot,\lambda_t)$, and the multiplier learner has external regret $R_T$, meaning $\sum_tL(\pi_t,\lambda_t)-\min_{\lambda\in[0,C]}\sum_tL(\pi_t,\lambda)\le R_T$. Averaging yields a saddle-point gap at most $\epsilon_{\rm oracle}+R_T/T$. EXP3 is a bandit method for a finite multiplier grid: it observes only the sampled choice's outcome. A bounded multiplier interval and an approximate equilibrium do not alone imply zero constraint violation.
For example, $R_T\le2\sqrt T$ and $\epsilon_{\rm oracle}=0.01$ give a gap at most $0.03$ at $T=10{,}000$. The inequality follows by summing the approximate best-response inequalities and adding the multiplier regret inequality; division by $T$ turns these into the averaged saddle gap.
This is a self-contained sufficient version of the distribution-transfer argument used by OASIS, not the paper's own statement. Assume $0\le c\le C_{\max}$, $0\lt\gamma\lt1$, and a feasible comparator $\pi^*$ with $J_c(\pi^*)\le\kappa$. Let the generated joint law be $d_g(s)\pi_g(a\mid s)$ and assume $d_g$ is the true normalised occupancy of $\pi_g$ in the same MDP. Suppose
Then the joint shaping error is at most $e_s+\sqrt{e_i/2}$ and
Proof. For joint laws, $D_{\mathrm{TV}}(d_g\pi_g,d^{\pi^\ast}\pi^\ast)\le D_{\mathrm{TV}}(d_g,d^{\pi^\ast})+\mathbb E_{d^{\pi^\ast}}D_{\mathrm{TV}}(\pi_g\|\pi^\ast)$, and Pinsker plus Jensen bound the last term by $\sqrt{e_i/2}$. Since $J_c(\pi)=\frac{1}{1-\gamma}\mathbb E_{d^\pi\pi}[c]$ and $|\mathbb E_pc-\mathbb E_qc|\le2C_{\max}D_{\mathrm{TV}}(p,q)$, this gives $J_c(\pi_g)-J_c(\pi^\ast)\le\frac{2C_{\max}}{1-\gamma}(e_s+\sqrt{e_i/2})$. For $\pi_\phi$ versus $\pi_g$, the joint laws differ by at most $\|d^{\pi_\phi}-d_g\|_1+2\mathbb E_{d_g}D_{\mathrm{TV}}(\pi_\phi\|\pi_g)\le\frac{2}{1-\gamma}\mathbb E_{d_g}D_{\mathrm{TV}}(\pi_\phi\|\pi_g)$ in $\ell_1$ (Step 4 of Section 2), and Pinsker plus Jensen give the $\sqrt{e_r/2}$ term; finally $J_c(\pi^\ast)\le\kappa$. This explains why realistic generated transitions and small fit error both matter.
The source’s diffusion theorem seeks $e_s=\widetilde O(\varepsilon_{\rm score}\sqrt K)+C(d^*,L,K)$, assuming an $L$-Lipschitz score $\nabla\log d^*$, finite second moment, an appropriate target condition, controlled score error and inverse-policy KL error. Here $K$ is diffusion time, not policy updates; the unspecified remainder prevents a numerical certificate. Its printed cost proof additionally replaces the learned policy occupancy by the dataset marginal and moves a KL average between different state weightings. Those steps need coverage/compatibility assumptions. The explicit bound above states a sufficient occupancy condition and retains a distribution-shift factor instead of silently making those replacements. Synthetic data do not automatically satisfy that condition.
Compare Yao et al., NeurIPS 2024, Thms. 1–2.
The benchmark: DSRL
Liu, Guo, Lin et al., DMLR 2024 provide 38 datasets (Safety-Gymnasium, Bullet-Safety-Gym, MetaDrive) and reference implementations (OSRL) of BC, CDT, BCQ-Lag, BEAR-Lag, CPQ and COptiDICE. Metrics: $R_{\rm norm}=\frac{R_\pi-r_{\min}(M)}{r_{\max}(M)-r_{\min}(M)}$ (the paper writes a factor 100; tables report the fraction) and $C_{\rm norm}=\frac{C_\pi+\epsilon}{\kappa+\epsilon}$, so an agent is safe iff $C_{\rm norm}\le1$. The protocol evaluates each method at three thresholds $\kappa$, three seeds and 20 episodes per dataset (constraint-variation evaluation).
| Method | Against distribution shift | Constraint handling | Guarantee | FISOR's Table 1 averages (reward / cost): SG, Bullet, MetaDrive |
|---|---|---|---|---|
| CPQ | inflate cost of OOD actions | indicator $Q_c\le l$ | OOD costs exceed $l$ for large $\alpha$ (Thm. 1) | 0.02/10.58, 0.32/5.28, −0.06/0.24 |
| COptiDICE | $f$-divergence to $d^{\mathcal D}$ | Lagrangian + cost upper bound | exact for the regularised LP | 0.29/5.94, 0.55/7.64, 0.63/10.26 |
| CDT | imitation of the data | cost-to-go conditioning + relabelling | none (stated) | 0.50/4.31, 0.63/2.09, 0.25/1.45 |
| FISOR | weighted BC in the data support | HJ feasible region (hard) | optimal form of the decoupled surrogate | 0.30/0.35, 0.39/0.10, 0.36/0.25 |
Normalised cost below 1 is safe. Numbers are the per-suite averages in FISOR's Table 1 (stringent limits: 10 for Safety-Gymnasium, 5 otherwise; 20 episodes × 3 seeds), run by the FISOR authors; they are not comparable with DSRL's own tables, which average over three thresholds.
7. Benchmarks, Reproducibility and the 2026 State of the Art
Every empirical claim in Sections 3 to 6 is a number on a benchmark, so it pays to know what the benchmarks measure. The online lineage is Safety Gym (Section 3: Point, Car and Doggo robots, Goal, Button and Push tasks at two constrained difficulty levels, one aggregate indicator cost, budget $d=25$ per 1000-step episode, undiscounted episode return and cost) → Safety-Gymnasium (Ji et al., NeurIPS 2023 Datasets & Benchmarks: the navigation tasks rebuilt on Gymnasium and MuJoCo, plus velocity-constrained locomotion, vision-only, multi-agent and Isaac Gym dexterous-hand tasks, and the SafePO library of 16 algorithms) → OmniSafe (Ji et al., JMLR 2024: a modular PyTorch infrastructure with on-policy, off-policy, model-based and offline algorithms, a common source of baselines in 2024 to 2026 papers). For control-oriented work, safe-control-gym (Yuan et al., IEEE RA-L 2022) extends the Gym API with symbolic (CasADi) dynamics, queryable constraints and repeatable disturbance injection on cart-pole and 1-D/2-D quadrotor stabilisation and tracking tasks, so that MPC, learning-based control (see Primer D) (Module 11) and safe RL can be compared on performance, data efficiency and safety through one interface. Offline, DSRL (Section 6) plays the role of Safety-Gymnasium.
| Benchmark | Constraint | Cost score | Return score | Counted as safe |
|---|---|---|---|---|
| Safety Gym (2019) | undiscounted episode cost $\le d=25$ | $\bar M_c=\frac{\max(0,J_c-d)}{\max(\epsilon,J_c^E-d)}$ at the end of training; $\bar\rho_c=\rho_c/\rho_c^E$ over all of training | $J_r/J_r^E$ ($E$ = unconstrained PPO) | $\bar M_c\approx0$; training-average episode safe iff $\rho_cT_{\rm ep}\le d$ |
| Safety-Gymnasium (2023) | episode cost $\le25$ | $\bar J_C=J_C/25$ | relative to PPO | $\bar J_C\le1$ |
| DSRL (2024) | episode cost $\le\kappa$, three $\kappa$ per dataset | $\frac{C_\pi+\epsilon}{\kappa+\epsilon}$ | $\frac{R_\pi-r_{\min}}{r_{\max}-r_{\min}}$ of the dataset | $C_{\rm norm}\le1$ |
| OASIS (2024) | episode cost $\le\kappa=20$ on its "tempting" datasets | $C_\pi/\kappa$ | $R_\pi/r_{\max}$ | $\le1$ |
| SAC-FDPI (2026) | state-wise: zero violating steps | violating steps per episode, normalised by PPO | normalised by PPO | near-zero violations of the final policy |
Reproducibility. Three findings make single numbers fragile. The multiplier and the budget: Spoor, Serra-Gómez, Plaat & Moerland, arXiv 2025 trace empirical return–cost Pareto frontiers (the non-dominated runs: no other run has at least the return and at most the cost, with one of the two strictly better; Primer E) of PPO-Lagrangian with fixed multipliers on eight Safety-Gymnasium tasks and compare the best fixed $\lambda^\star$ with gradient-ascent and PI-controlled multipliers ($K_P=K_I=10^{-4}$; 10 seeds, $3.5\cdot10^7$ steps). The return is highly sensitive to $\lambda$, the restrictiveness of the constraint changes with the cost limit within a task, and no update rule wins across tasks or even within one: the ranking depends on the cost limit. They recommend reporting over a task-specific set of cost limits (and list one per task), and note that with the observed seed variance, methods that are safe on average still produce individual runs that violate the constraint, since "Lagrangian methods are not strict constraint enforcers by design". Oscillation: Safety-Gymnasium's own evaluation finds that Lagrangian methods oscillate more than projection-based ones, most strongly on the stochastic navigation tasks, which is why the damped multipliers of Module 8 matter. What is averaged: end-of-training cost, cost over all of training (Safety Gym's $\rho_c$, an average in which cheap steps offset expensive ones; C-TRPO's cost regret, which only adds up violations) and the cost of the final policy are different quantities. SAC-FDPI, for instance, targets a safe policy at convergence and generates unsafe samples on purpose during training, whereas SafeDreamer, ActSafe, SOOPER and C-TRPO's cost regret are about safety during learning. A defensible protocol, our synthesis of Spoor et al.'s recommendation and C-TRPO's evaluation rather than an agreed standard: several cost limits per task, at least five seeds, interquartile means with bootstrap intervals, and both final-policy cost and cost regret.
| Method (venue) | Setting | Mechanism | Reported standing | Read with care |
|---|---|---|---|---|
| SafeDreamer (ICLR 2024) | online, model-based, pixels | DreamerV3 + constrained CEM planning or PID / augmented Lagrangian (Section 5) | nearly zero cost on low-dimensional and vision-only Safety-Gymnasium tasks, cost limit lowered to 2.0 | expected episode cost; empirical only |
| CAL (Wu et al., ICLR 2024) | online, off-policy | upper-confidence cost from a critic ensemble + local convexification (augmented Lagrangian) | asymptotic return comparable to on-policy methods with far fewer samples, and far fewer violations during training; a real-world auto-bidding experiment | diagnoses cost underestimation as the failure mode of off-policy primal–dual methods |
| C-TRPO (ICML 2025) | online, on-policy | safe Bregman trust region + recovery with hysteresis (Section 4) | competitive return, last-iterate safety and lower cost regret than the other high-return methods on 8 tasks (5 seeds, $10^7$ steps, IQM) | invariance proved for the idealised flow only |
| SAC-FDPI (Yang et al., ICLR 2026) | online, off-policy, state-wise constraint | a dual policy that seeks violations (while staying KL-close) keeps the feasibility critic accurate; importance-weighted data pooling | lowest PPO-normalised cost and an almost tied highest return, averaged over 14 Safety-Gymnasium tasks, against OmniSafe implementations of RCPO, PPO-Lag, SAC-Lag, CPO, FOCOPS and CUP and a penalised DSAC-T; near-zero violations of the final policies | safety at convergence, not during training |
| ActSafe (ICLR 2025), SOOPER (ICLR 2026) | online, model-based | calibrated models; pessimistic safe set or a prior-policy fallback (Section 5) | ActSafe: safe in every episode on its calibration event; SOOPER: claimed, subject to the switching-time gap, plus sample complexity (ActSafe) or sublinear regret (SOOPER); SOOPER also on a real RC car | RKHS/calibration assumptions and a safe seed or prior |
| FISOR (ICLR 2024) | offline, hard constraint | HJ feasible region + weighted behaviour cloning with a diffusion policy (Section 6) | only method with normalised cost below 1 on all 26 DSRL tasks it evaluated, at stringent limits | lower reward than unsafe baselines |
| OASIS (NeurIPS 2024) | offline | conditional diffusion reshapes the data, then BCQ-Lag trains on it | reports a better safety–reward trade-off than BC, BCQ-Lag, BEAR-Lag, CPQ, COptiDICE, CDT and FISOR on its datasets | own normalisation ($C_\pi/\kappa$, $\kappa=20$) |
| O3SRL (NeurIPS 2025) | offline | Lagrangian game: offline RL oracle + no-regret (EXP3) multiplier | only method satisfying the constraint on all eight Bullet-Safety-Gym tasks at $\kappa=5$ | $\epsilon$-equilibrium relative to the oracle's error |
| SB-TRPO (Wagner, Kanwar & Ong, arXiv preprint) | online, zero-cost constraint | each trust-region step must achieve a fixed fraction $\beta$ (0.75 in the experiments) of the maximal cost decrease attainable in the trust region, with no separate recovery phase; $\beta=1$ recovers CPO for zero-cost constraints (its feasible step when a zero-cost policy lies in the trust region, otherwise its recovery step) | in finite MDPs the idealised update converges to the minimal cost, and for $\beta\lt1$ also to the maximal reward among minimal-cost policies (zero cost when zero-cost policies exist); high safety with strong return on level-2 Safety-Gymnasium tasks | preprint, not peer reviewed |
Standings are as reported by each paper under its own protocol and metric (see the definition box at the start of this section); they are not a single leaderboard. Lagrangian PPO/SAC variants and CPPO-PID remain the default baselines in OmniSafe and SafePO, and the same CMDP-Lagrangian machinery now drives LLM alignment (Safe RLHF, Module 8).
Assume a finite discounted MDP, bounded rewards and nonnegative costs, a fixed initial distribution, $0\lt\gamma\lt1$, the full class of stationary stochastic policies, a fixed radius $\delta\gt0$ and fixed $\beta\in(0,1]$. Start with any policy. Use the old-first divergence $K_k(\pi)=\mathbb E_{s\sim d^{\pi_k}}D_{\rm KL}(\pi_k\|\pi)[s]$, exact values, and globally attained optimisers:
Then $J_c(\pi_k)\to J_c^*:=\min_\pi J_c(\pi)$. If $\beta\lt1$, also $J_r(\pi_k)\to\max_{J_c(\pi)=J_c^*}J_r(\pi)$. These are convergence statements for values, not necessarily for policy parameters. Zero cost is the limit only when a zero-cost policy exists.
Each step must take a fixed fraction of the cost improvement available locally, preventing it from settling at a cost-suboptimal policy. When $\beta\lt1$, the remaining freedom permits reward improvement among cost-minimal policies. Exact optimisation over the full policy class and a fixed positive radius are the essential idealisations; a neural surrogate step is outside this theorem.
8. Walkthrough: The CPO Step From Bound to Closed Form
Seven steps from the performance difference lemma to the point the explorer plots. The running example is the explorer's default: two parameters, $g=(1,1)$, $b=(1,0)$, $H=\begin{pmatrix}2&1\\1&2\end{pmatrix}$, $\delta=0.1$ and $c=J_c(\pi_k)-d=-0.1$, i.e. the current policy is feasible with a margin of $0.1$. The numbers are small enough to check by hand, and each of them appears in the explorer's readout.
Interactive: CPO vs Projection in Parameter Space
Set the objective gradient $g$, the cost gradient $b$, the constraint value $c=J_c(\pi_k)-d$, the Fisher matrix $H$ and the radius $\delta$. The page solves the linearised CPO problem with the closed-form dual of Section 3, computes both PCPO projections and the recovery step, and checks the CPO optimum against a brute-force search over the boundary of the feasible set after every change.
From the mathematics to a real decision
- Separate the optimization of a local surrogate from verification of the updated policy.
- Derive a constrained step in scaled parameter coordinates.
- Use a remainder bound to turn a local prediction into a certified statement within its stated region.
Updating a learned cooling controller
Consider a learned controller with two adjustable parameters. We want to increase a productivity score while keeping a temperature-related constraint below its limit. The variables below are dimensionless parameter changes, not temperatures or direct actuator commands. They are a constructed local model for teaching policy updates. A reward gradient predicts which change improves productivity, a cost gradient predicts which change increases the constraint, and a trust-region matrix describes how large a change is considered reliable.
This problem begins after gradients have been estimated. Their statistical uncertainty and the relation between a KL divergence and the chosen parameter metric are separate assumptions. To see the geometry without those complications, assume the displayed gradients and positive-definite matrix are given exactly. We will later ask what the model can actually certify.
Worked decision: a cheap direction is not always an admissible direction
Let the change be $s=(s_1,s_2)$, reward gradient $g=(2,1)$, trust matrix $H=\operatorname{diag}(1,4)$, and radius $\delta=1/2$. Suppose the old cost margin is $-1/5$ and the cost gradient is $b=(1,0)$. The local subproblem is
The factor 4 means a unit change in the second parameter consumes four times as much quadratic trust budget as a unit change in the first. Introduce scaled coordinates $y_1=s_1$, $y_2=2s_2$. The ellipse becomes a unit disk, and the reward becomes $2y_1+y_2/2$. Without the cost constraint, the best disk point lies along $(2,1/2)$, giving $s_1=4/\sqrt{17}\approx0.9701$ and $s_2=1/(2\sqrt{17})\approx0.1213$. It violates $s_1\le0.2$.
For each feasible $s_1$, the best second coordinate is the upper ellipse boundary, $s_2=\tfrac12\sqrt{1-s_1^2}$. Thus the remaining objective is $f(s_1)=2s_1+\tfrac12\sqrt{1-s_1^2}$ on $[-1,1/5]$. In the interior its derivative is $2-s_1/(2\sqrt{1-s_1^2})$, which is positive for negative $s_1$ and remains positive through $1/5$. The largest objective therefore occurs at the allowed right endpoint:
Both constraints are active. Substitution checks the trust ellipse: $1/25+4(6/25)=1$. The cost surrogate is exactly zero. The step is optimal for the displayed local problem, but the word “surrogate” still matters. We have not yet shown that the nonlinear controller respects its true constraint after this update.
Worked audit: reserve a margin for curvature
Suppose a valid analysis of the true constraint change gives, throughout this trust region, $C(s)-d\le-1/5+s_1+(1/5)\|s\|_2^2$. The last term is a certified upper bound on the neglected nonlinear remainder. Since $H\succeq I$ and $s^\top Hs\le1$, we know $\|s\|_2^2\le1$. This coarse bound shows why satisfying only $s_1\le1/5$ is insufficient: the remainder can consume another $1/5$.
A simple robust modification is to require $s_1\le0$. Then the true constraint bound is at most $-1/5+0+1/5=0$. Solving the modified local problem gives $s=(0,1/2)$ and predicted reward improvement $1/2$. Its actual squared Euclidean norm is only $1/4$, so the stated remainder bound gives the sharper constraint upper bound $-1/5+1/20=-3/20$. The coarse design sacrifices predicted reward but leaves a visible safety margin.
This is one sufficient design, not a claim of the best robust update. Optimizing the full quadratic upper constraint could be less conservative. Nor does an estimated curvature constant become certified by being named in an equation. The conclusion requires the bound to hold on the entire region where the optimizer can choose a step.
For a scalar nonlinear constraint $h(s)=s^2$ with safe requirement $h\le0$, at $s=0$ the linearization is zero for every proposed step. Any nonzero step violates the true requirement, however small the trust radius is. Strict feasibility or a valid remainder treatment is needed; shrinking a radius alone is not a general safety proof.
Application exercises
Exercise 9.B1 — Medium: Explain the metric before computing a step
The candidate changes are $s=(1/2,0)$ and $t=(0,1/2)$. Compare their Euclidean lengths, quadratic trust costs $\tfrac12v^\top Hv$, reward improvements and local cost feasibility in the original problem. Why is “same parameter distance” not enough to compare them?
Show hint
Compute all four quantities separately; the trust metric and the cost constraint measure different things.
Show solution
Both lengths are $1/2$. Trust costs are $1/8$ and $1/2$, while reward predictions are 1 and $1/2$. The first violates $s_1\le1/5$; the second satisfies it. The matrix weights directions differently, and the cost gradient distinguishes them again. A direction can be cheap in the trust metric yet forbidden by the safety surrogate.
Exercise 9.B2 — Hard: Check the price of an active constraint
For the original optimizer, use the maximization Lagrangian $g^\top s-\lambda(\tfrac12s^\top Hs-1/2)-\nu(s_1-1/5)$. Find nonnegative $\lambda,\nu$ satisfying stationarity and complementary slackness. Interpret the two prices without claiming that the true controller is safe.
Show hint
The second coordinate of $g=\lambda Hs+\nu b$ first determines $\lambda$.
Show solution
The second coordinate gives $1=\lambda(4\sqrt6/5)$, hence $\lambda=5/(4\sqrt6)$. The first gives $2=\lambda/5+\nu$, so $\nu=2-1/(4\sqrt6)\gt0$. Both constraints are active, so both complementarity products vanish. The prices describe marginal trade-offs in this local convex subproblem. They do not account for estimation error or a nonlinear constraint remainder.
Exercise 9.B3 — Hard: Build a less coarse sufficient constraint
Keep the valid true-constraint upper bound $-1/5+s_1+(1/5)(s_1^2+s_2^2)$. Test the original optimum and the conservative optimum. Does failure of this upper-bound test prove that the true constraint is violated? If the true constraint equals the bound exactly, what changes?
Show hint
The original optimum has squared norm $7/25$; distinguish an upper bound from an identity.
Show solution
At the original step the bound is $-1/5+1/5+(1/5)(7/25)=7/125\gt0$. It cannot certify feasibility. At $(0,1/2)$ it is $-3/20\lt0$, so feasibility follows from the assumed upper bound. A positive upper bound alone does not prove violation: the true value might be smaller. If the true function equals that expression, then the original step really violates by $7/125$ and the conservative step has margin $3/20$.
Read a policy-update claim in two layers
First identify exactly which finite-dimensional problem the algorithm solves. Then identify the argument that connects this solution to the original policy’s returns and constraints. A local optimizer, a line search and a high-probability model estimate answer different questions. Module 10’s next example moves the decision from a policy update to an action chosen at each sampling instant.
Exercises
Graded practice
Each level has four problems. Write your steps before opening the answer; use the hint when you need a first move. Close the answer and retry after checking it.
Easy practice
Exercise 9.P1 — Easy: Center an advantage under the old policy
At one state let $Q^\pi=(5,1)$ and $\pi=(1/4,3/4)$. Compute $V^\pi$ and the two advantages. What is their expectation under $\pi$? Under $\pi'=(1/2,1/2)$, what is the average advantage?
Review this topic · Revisit the prerequisite
Show hint
Show answer
$V^\pi=(1/4)5+(3/4)1=2$. Subtracting gives advantages $(3,-1)$. Their old-policy average is $(1/4)3+(3/4)(-1)=0$, as the advantage definition requires. The new-policy average is $(1/2)3+(1/2)(-1)=1$. The new policy shifts probability toward the action better than the old average; converting this local quantity to return also involves discounted visitation.
Exercise 9.P2 — Easy: Measure a change in action probabilities
For old probabilities $(1/2,1/2)$ and new probabilities $(3/4,1/4)$, compute total variation and the KL divergence of new relative to old, using natural logs.
Review this topic · Revisit the prerequisite
Show hint
Show answer
Total variation is $\tfrac12(|3/4-1/2|+|1/4-1/2|)=1/4$. The KL divergence is
Both vanish for identical distributions, but they measure change differently. KL is not symmetric; the direction specified in the question matters.
Exercise 9.P3 — Easy: Read the axes of a trust-region ellipse
Let $H=\mathrm{diag}(4,1)$ and $\delta=1/2$. Rewrite $\tfrac12x^\top Hx\le\delta$ in coordinates, find the axis radii, and check $x=(1/2,0)$.
Review this topic · Revisit the prerequisite
Show hint
Show answer
The inequality becomes $4x_1^2+x_2^2\le1$. Setting $x_2=0$ gives $|x_1|\le1/2$; setting $x_1=0$ gives $|x_2|\le1$. The axes have radii $1/2$ and $1$. At $(1/2,0)$, the quadratic form is $1$, hence the original left side is $1/2=\delta$: this point is on the boundary. Larger curvature in the first direction permits a smaller step.
Exercise 9.P4 — Easy: Check a linearized cost constraint
The current cost residual is $c=-0.2$ and its gradient is $b=(1,0)$. Test $c+b^\top x\le0$ at $x=(0.3,0.1)$ and $x=(0.1,0.1)$. What does this check actually certify?
Review this topic · Revisit the prerequisite
Show hint
Show answer
The first predicted residual is $-0.2+0.3=0.1$, which violates the linearized constraint. The second is $-0.2+0.1=-0.1$, which passes. This certifies feasibility of a local affine approximation, not of the true nonlinear cost. Curvature and estimation error need separate bounds or an actual acceptance check.
Medium practice
Exercise 9.P5 — Medium: Solve the unconstrained trust-region step
Maximize $g^\top x$ subject to $\tfrac12x^\top Hx\le1/2$, with $g=(1,2)$ and $H=\mathrm{diag}(1,4)$. Use $x=\sqrt{2\delta/(g^\top H^{-1}g)}\,H^{-1}g$ and verify the solution.
Review this topic · Revisit the prerequisite
Show hint
Show answer
$H^{-1}=\mathrm{diag}(1,1/4)$, so $H^{-1}g=(1,1/2)$ and $g^\top H^{-1}g=2$. Thus $x=(1/\sqrt2,1/(2\sqrt2))$. Its quadratic form is $1/2+4(1/8)=1$, meeting the constraint boundary. The objective is $1/\sqrt2+1/\sqrt2=\sqrt2$. Cauchy–Schwarz in the $H$ metric bounds every feasible objective by $\sqrt{(g^\top H^{-1}g)(x^\top Hx)}\le\sqrt2$, proving optimality.
Exercise 9.P6 — Medium: Project a proposed step onto a cost half-space
Find the Euclidean projection of $y=(0.6,0.2)$ onto $\{x:x_1\le0.1\}$. Compute the displacement and the objective $\tfrac12\|x-y\|^2$.
Review this topic · Revisit the prerequisite
Show hint
Show answer
The nearest feasible first coordinate is the boundary $x_1=0.1$, and $x_2$ remains $0.2$. Thus $x=(0.1,0.2)$ and $x-y=(-0.5,0)$. The distance is $0.5$ and the objective is $\tfrac12(0.5)^2=0.125$. A projection repairs the constraint with the smallest change in the chosen metric; another metric can produce another correction.
Exercise 9.P7 — Medium: See how discounting enlarges a bound
A surrogate error is bounded by $2\gamma\varepsilon v/(1-\gamma)^2$, with valid advantage bound $\varepsilon=0.5$ and average total variation $v=0.01$. Evaluate this expression at $\gamma=0.9$ and $\gamma=0.5$.
Review this topic · Revisit the prerequisite
Show hint
Show answer
At $0.9$, the numerator is $2(0.9)(0.5)(0.01)=0.009$ and denominator is $0.1^2=0.01$, giving $0.9$. At $0.5$, they are $0.005$ and $0.5^2=0.25$, giving $0.02$. The first bound is $45$ times larger. A small policy change can therefore have a loose worst-case return bound at a long effective horizon; this calculation describes the bound, not the actual error.
Exercise 9.P8 — Medium: Apply a pessimistic model cost check
On a stated confidence event, true policy cost satisfies $J_c\le\widehat J_c+2$. The budget is $8$. Can estimates $7$ and $5$ certify feasibility on that event? Does failure of the check prove a policy is unsafe?
Review this topic · Revisit the prerequisite
Show hint
Show answer
An estimate of $7$ gives upper bound $9\gt8$, so the stated bound cannot certify that policy. An estimate of $5$ gives upper bound $7\le8$, so that policy is feasible on the confidence event. The failed first check does not prove true cost exceeds $8$: it may be below the upper bound. The probability of the resulting certificate is inherited from the confidence event, which must cover this policy evaluation.
Hard practice
Exercise 9.P9 — Hard: Solve a cost-constrained step on a disk
Maximize $x_1+x_2$ subject to $x_1^2+x_2^2\le1$ and $x_1\le0.2$. Find the optimizer and explain why simply taking the unconstrained trust-region direction fails.
Review this topic · Revisit the prerequisite
Show hint
Show answer
Without the cost constraint, the optimum is $(1/\sqrt2,1/\sqrt2)$, whose first coordinate exceeds $0.2$. On the upper disk boundary, the objective is $f(t)=t+\sqrt{1-t^2}$. Its derivative is $1-t/\sqrt{1-t^2}$, positive for $-1\lt t\le0.2$. Therefore its maximum on the allowed interval occurs at $t=0.2$.
The optimizer is $(0.2,\sqrt{0.96})\approx(0.2,0.979796)$, with objective approximately $1.179796$. Both the disk and cost constraints are active; the gradient direction alone does not account for their intersection.
Exercise 9.P10 — Hard: Audit a linearized boundary step
The true cost residual is $J_c(x)-d=-0.1+x+2x^2$. Linearize at $x=0$. A step $x=0.1$ reaches the linearized boundary. Is it truly feasible? Find the largest nonnegative feasible step.
Review this topic · Revisit the prerequisite
Show hint
Show answer
The linearization is $-0.1+x$, which is zero at $0.1$. But the true residual there is $-0.1+0.1+2(0.1)^2=0.02\gt0$, so the step is infeasible. The positive root is
The quadratic increases for $x\ge0$, so feasible nonnegative steps are exactly $0\le x\le x_{\max}$. The discarded curvature term explains the violation. A local subproblem needs an error margin or line search to transfer its prediction to the true constraint.
Exercise 9.P11 — Hard: Check support before importance weighting
The data policy chooses two actions with probabilities $(0.99,0.01)$; the candidate uses $(0.5,0.5)$. Find both likelihood ratios and their expectation under the data policy. What changes if its second probability is zero?
Review this topic · Revisit the prerequisite
Show hint
Show answer
The ratios are $0.5/0.99=50/99$ and $0.5/0.01=50$. Their old-policy average is $0.99(50/99)+0.01(50)=0.5+0.5=1$. The rare action receives a large weight, making estimates sensitive to few observations even though the normalization is correct.
If the data policy assigns zero probability to the second action while the candidate assigns $0.5$, the ratio is undefined there and data provide no samples of that action. The usual importance-sampling identity requires candidate support to be contained in data-policy support; an extrapolated critic does not repair that missing statistical assumption.
Exercise 9.P12 — Hard: Combine reward and cost confidence statements
A proposed update has predicted return improvement $0.4$ with error at most $0.3$ on event $E_r$ of probability at least $0.98$. Its cost estimate is $7$ with upward error at most $0.5$ on event $E_c$ of probability at least $0.97$. Budget is $8$. Give a joint guarantee without assuming independence.
Review this topic · Revisit the prerequisite
Show hint
Show answer
The union bound gives $\mathbb P(E_r\cap E_c)\ge1-0.02-0.03=0.95$. On that joint event, true improvement is at least $0.4-0.3=0.1\gt0$, and true cost is at most $7+0.5=7.5\le8$. Hence the update improves reward and satisfies the budget with probability at least $0.95$, provided the two events apply to this selected update. No independence was used; multiplying the two success probabilities would require it.
Original longer exercises
Key Papers
| Paper | Venue | Contribution | Why read it |
|---|---|---|---|
| Achiam, Held, Tamar & Abbeel: Constrained Policy Optimization | ICML 2017 | Performance bounds with the average TV distance under $d^\pi$; trust-region CMDP update with per-step worst-case bounds; closed-form dual and recovery step | The theorem, the algorithm and the appendix derivation this module is built on |
| Kakade & Langford: Approximately Optimal Approximate Reinforcement Learning | ICML 2002 | The performance difference lemma; conservative policy iteration with mixture updates | Where the identity and the idea of a guaranteed small step come from |
| Schulman, Levine, Abbeel, Jordan & Moritz: Trust Region Policy Optimization | ICML 2015 | Monotone-improvement bound with $\max_s D_{\mathrm{TV}}$; mean-KL trust region, conjugate gradients, line search | The unconstrained machinery that CPO reuses step for step |
| Ray, Achiam & Amodei: Benchmarking Safe Exploration in Deep Reinforcement Learning | OpenAI report 2019 | Safety Gym; cost rate as safety regret; normalised metrics; CPO vs Lagrangian comparison | The honest data point: CPO 0.593 normalised violation vs about 0.02 for Lagrangian methods |
| Yang, Rosca, Narasimhan & Ramadge: Projection-Based Constrained Policy Optimization | ICLR 2020 | TRPO step then closed-form projection; bounds for feasible and infeasible iterates under KL projection | A clean KKT exercise on the same linearised problem, and why the metric of the projection matters |
| Zhang, Vuong & Ross: First Order Constrained Optimization in Policy Space | NeurIPS 2020 | Closed-form Gibbs update policy in policy space, then first-order KL regression | Shows that the constrained step is convex once you leave parameter space |
| Zhang, Shen, Yang et al.: Penalized Proximal Policy Optimization for Safe Reinforcement Learning | IJCAI 2022 | Exact ReLU penalty with finite weight inside a clipped PPO loss | The penalty view of CMDP updates in one first-order loss |
| Milosevic, Müller & Scherf: Embedding Safety into RL: A New Take on Trust Region Methods | ICML 2025 | Safe Bregman trust region (C-TRPO); invariance of the safe set for the natural-gradient flow; last-iterate safety | The trust-region line's answer to the Safety Gym critique |
| As, Usmanova, Curi & Krause: Constrained Policy Optimization via Bayesian World Models | ICLR 2022 | LAMBDA: optimistic reward and pessimistic cost over posterior model samples; augmented Lagrangian | The template for uncertainty-aware model-based safe RL |
| As, Sukhija, Treven, Sferrazza, Coros & Krause: ActSafe: Active Exploration with Safety Constraints for Reinforcement Learning | ICLR 2025 | Safety in every episode with high probability plus sample complexity, via a calibrated model and pessimistic safe-set expansion | SafeOpt's logic lifted to policies and dynamics |
| Wendl, As, Prajapat, Pollak, Coros & Krause: Safe Exploration via Policy Priors | ICLR 2026 | SOOPER: pessimistic prior fallback with online cost tracking; claimed per-episode safety and sublinear regret; hardware | The current frontier of guarantee-driven safe exploration (the safety proof has a gap for stochastic transitions, Section 5) |
| Lee, Paduraru, Mankowitz, Heess, Precup, Kim & Guez: COptiDICE: Offline Constrained Reinforcement Learning via Stationary Distribution Correction Estimation | ICLR 2022 | Offline constrained RL directly in occupancy ratios; closed-form inner maximisation; cost upper bounds | The occupancy LP of Module 8 made offline and trainable |
| Zheng, Li, Yu, Yang, Li, Zhan & Liu: Safe Offline Reinforcement Learning with Feasibility-Guided Diffusion Model | ICLR 2024 | FISOR: HJ-reachable feasible region, decoupled weighted-BC optimum, diffusion policy | Hard constraints offline; safe on all 26 DSRL tasks of its evaluation at stringent limits |
| Liu, Guo, Lin et al.: Datasets and Benchmarks for Offline Safe Reinforcement Learning | DMLR 2024 | DSRL: 38 datasets, normalised metrics, multi-threshold protocol, OSRL baselines | Needed to read any offline safe RL table |
| Ji, Zhang, Zhou et al.: Safety-Gymnasium: A Unified Safe Reinforcement Learning Benchmark | NeurIPS 2023 D&B | Single- and multi-agent, vector and vision safe RL tasks; SafePO with 16 algorithms | The benchmark behind most 2024 to 2026 online results |