8. CMDPs, Duality & Lagrangian Methods

Constrained MDPs, occupancy measures, zero duality gap, primal-dual algorithms, PID Lagrangians, risk and state augmentation

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

1. Constrained MDPs

Module 7 encoded safety as a set to stay in and asked how large a penalty makes the safe set attractive (Module 7). The constrained-RL tradition of Module 1 takes the other road: keep the reward and the safety signal as separate quantities, bound the expected cumulative safety cost by a budget, and let the algorithm find the trade-off.

First, Paternain et al., NeurIPS 2019 point out that a hand-tuned weight $w$ on a penalty has no transparent relation to the constraint value the final policy will achieve, so tuning $w$ can be as hard as solving the problem.

Second, and stronger, Calvo-Fullana et al., IEEE TAC 2024 exhibit constrained problems that no fixed weighted combination of rewards solves (see Sections 3 and 7 below). A budget is also what an engineer can specify: "at most 25 hazard contacts per episode" is a requirement, "weight 0.37 on hazard contacts" is not.

Background used in the definition: policies (stochastic or deterministic, stationary or history-dependent) and discounted returns are in Primer E, value functions, $Q$-functions and advantages in Primer E, expectations over random trajectories in Primer C, and $\sup$ versus $\max$ over infinite sets in Primer B.

We stick to one convention throughout the section: maximise reward, costs bounded from above, $\lambda\ge 0$ the Lagrange multiplier of a cost constraint, $\rho_\pi$ the occupancy measure. The literature does not. The table translates the papers cited on this page; the translation rule is that a "utility" constraint $V_g(\pi)\ge b$ is the cost constraint with $c=-g$ and $d=-b$, with the multiplier unchanged.

Discounted, average, episodic. The discounted formulation above is the default in deep safe RL. Altman also treats the total-cost problem (for transient or absorbing models, or under uniform Lyapunov conditions; his Chs. 7–9) and the expected-average-cost problem ($\lim_T \frac1T\mathbb E\sum_{t\lt T}c$; for finite MDPs under a unichain assumption, his Ch. 4), which is the setting of Calvo-Fullana et al.; finite-horizon episodic tasks (Safety Gym: $T_{\rm ep}=1000$, $d=25$) are the undiscounted case $\gamma=1$ with a terminal time. The occupancy, LP and duality results of Sections 2–3 have counterparts in these settings, but only under such extra assumptions (a finite horizon also needs time-indexed occupancy measures and non-stationary policies), and the convergence rates of Section 4 are proved for the discounted case; we write the discounted case throughout. Some authors normalise returns by $(1-\gamma)$ so that they live in $[0,1]$ when rewards do; we do not, and we say so wherever a factor $(1-\gamma)$ appears. The three criteria are compared in Primer E; the Markov-chain terms used here are explained in the box below.

Why the optimal policy is usually stochastic

An unconstrained discounted MDP with finitely many states and actions always has a deterministic optimal stationary policy (in general spaces an optimum need not even exist; see the definition above). A CMDP typically does not. Consider two states that alternate deterministically, $s_1\to s_2\to s_1\to\cdots$, whatever the action (two recurring phases of a task), $\mu=\delta_{s_1}$ (the point mass: start in $s_1$ with probability one; Primer C), $\gamma=\tfrac12$. In both states the agent chooses fast (reward 1) or slow (reward 0). Being fast costs $1$ in $s_1$ and $2$ in $s_2$ (the second phase is riskier), budget $d=1.2$. Write $p_1=\pi(\text{fast}\mid s_1)$, $p_2=\pi(\text{fast}\mid s_2)$. The discounted time spent in $s_1$ is $\sum_k\gamma^{2k}=\tfrac{1}{1-\gamma^2}=\tfrac43$ and in $s_2$ it is $\tfrac{\gamma}{1-\gamma^2}=\tfrac23$, so

The four deterministic policies give $(J_c,J_r)\in\{(0,0),\ (\tfrac43,\tfrac43),\ (\tfrac43,\tfrac23),\ (\tfrac83,2)\}$; only $(\text{slow},\text{slow})$ is feasible, with $J_r=0$. Randomising in $s_1$ with $p_1=0.9$, $p_2=0$ gives $J_c=1.2$ and $J_r=1.2$. The set of achievable $(J_c,J_r)$ pairs is the convex hull of the deterministic points, i.e. all their weighted averages (Primer B; Section 2 explains why), and the constrained optimum sits where the budget line cuts its upper boundary:

2. Occupancy Measures and the LP View

The CMDP problem is non-convex in the policy: $J_r(\pi)$ is a nonlinear function of the numbers $\pi(a\mid s)$ because they multiply along trajectories. The classical cure (Altman, Ch. 3) is to change variables to the occupancy measure, in which all returns become linear.

The point is that $\rho_\pi$ is characterised by linear equations. Conservation of probability flow says: discounted mass at $s$ equals what starts there plus what flows in from the previous step.

Three consequences that we will use. Randomisation count: the LP has $|\mathcal S|+m$ constraints besides $\rho\ge0$, so it has a basic optimal solution with at most $|\mathcal S|+m$ nonzero entries (slacks of the budget rows included). If every state is visited, each state uses at least one of them, which leaves at most $m$ extra entries, i.e. at most $m$ randomisations — Altman's bound with his $K=m$. If some states are never visited, their flow rows vanish on the support of $\rho$ (a zero-occupancy state receives no flow), so the same count runs over the visited states only and the conclusion is unchanged (Altman's proof removes those states); at unvisited states any deterministic action will do. Convex image: the zero-duality-gap proof of Section 3 rests on the convexity of $\mathcal Q(\mu)$, plus Slater's condition for continuity at the nominal budget. LP duality: the dual of this LP is the Lagrangian dual of the CMDP, and the dual variable of the budget row is the Lagrange multiplier $\lambda_i$.

3. Lagrangian Relaxation and the Zero Duality Gap

Deep RL cannot manipulate occupancy measures directly: it has a parametrised policy $\pi_\theta$ and a gradient estimator (Primer E). The Lagrangian route keeps the policy as the variable and moves the constraint into the objective with a price $\lambda$.

Weak duality is two lines. For any feasible $\pi$ and any $\lambda\ge0$, every term $\lambda_i(J_{c_i}(\pi)-d_i)$ is $\le0$, so $L(\pi,\lambda)\ge J_r(\pi)$; taking the max over $\pi$ on the left and over feasible $\pi$ on the right gives $D(\lambda)\ge P^\star$ for every $\lambda\ge0$, hence $D^\star\ge P^\star$. Convexity is one line: $D$ is a pointwise maximum of functions $\lambda\mapsto L(\pi,\lambda)$ that are affine in $\lambda$, hence convex (Exercise 8.2 does the cost-minimisation mirror image, where the dual function is concave and the dual problem is a maximisation). So the dual problem is a convex program in $m$ variables. The question is whether its value is the CMDP value.

Parametrised policies: almost no price to pay

With a neural policy $\pi_\theta$ the maximisation in $D(\lambda)$ runs over $\theta$, and the dual value $D^\star_\theta$ can differ from $P^\star$. Paternain et al. bound the difference in terms of how expressive the class is.

Primal recovery: the right price is not the right policy

Zero duality gap means the values agree. It does not mean that a maximiser of $L(\cdot,\lambda^\star)$ solves the CMDP. The precise relation is one inclusion.

The inclusion can be extremely loose. In the monitoring problem of Calvo-Fullana et al. (average reward; three states $R_0,R_1,R_2$; from $R_0$ the agent moves to $R_1$ or $R_2$, from $R_i$ it stays or returns to $R_0$; reward $\mathbf 1(s=R_0)$; constraints "spend at least a fraction $c=\tfrac13$ of the time in $R_1$ and in $R_2$", i.e. utility constraints $V_i\ge c$ in the paper's convention, costs $-\mathbf 1(s=R_i)$ with budget $-c$ in ours), an optimal policy flips a fair coin in every state and attains $P^\star=\tfrac13$ (the optimum is not unique: every policy whose long-run fractions are $(\tfrac13,\tfrac13,\tfrac13)$ is optimal). The dual optimum is $\lambda^\star=(1,1)$, and there the penalised reward is $\mathbf 1(R_0)+\mathbf 1(R_1)+\mathbf 1(R_2)-\tfrac23\equiv\tfrac13$: every policy maximises the Lagrangian, including "stay in $R_1$ forever", which violates the $R_2$ constraint. For any $\lambda\ne(1,1)$ no maximiser is optimal: with $\lambda_1\ne\lambda_2$ every maximiser abandons one region entirely ($V_1=0$ or $V_2=0$: infeasible), with $\lambda_1=\lambda_2\lt1$ the maximisers return to $R_0$ at once ($V_1+V_2=\tfrac12$: infeasible), and with $\lambda_1=\lambda_2\gt1$ every maximiser has $V_0=0$, hence zero return. The stationary maximisers enter a region and never leave (feasible in expectation only if the probability $q$ of entering $R_1$ lies in $[\tfrac13,\tfrac23]$, and even then every single trajectory starves one region). A history-dependent maximiser can instead shuttle between $R_1$ and $R_2$ in ever longer blocks, which meets both visit constraints on every trajectory but still earns zero return. So no fixed weighted reward identifies the solution; the multiplier is exact and useless at the same time (Exercise 8.6). The structural reason was stated in Section 1: finite penalised MDPs have deterministic optima, CMDPs often do not, so whenever the CMDP optimum must randomise, $\Pi(\lambda^\star)$ must contain several policies and the algorithm has to select among them.

From chance constraints to CMDP constraints with a safety guarantee

The constraints of a CMDP are expectations, while a safety requirement is usually "the trajectory stays in the safe set with probability at least $1-\delta$". Paternain, Calvo-Fullana, Chamon, Ribeiro, IEEE TAC 2023 show how to choose the budget so that the CMDP relaxation implies the chance constraint; the tool is the union bound over time steps (Primer C).

4. Primal-Dual Algorithms and Their Convergence

The dual problem is convex and $m$-dimensional, so we would like to run (sub)gradient descent on $D(\lambda)$. The only obstacle is evaluating $D(\lambda)$, which is itself an RL problem. Danskin's theorem tells us what the gradient is once that RL problem is solved.

Paternain et al. prove (their Theorem 3) that if the inner RL step returns a local maximiser whose Lagrangian value is within $\delta$ of the global one (their Assumption 1), then under Slater's condition for the parametrised problem and $\epsilon$-universality the dual iterates reach a neighbourhood of the optimum in at most $K\le\|\lambda_0-\lambda_\theta^\star\|^2/(2\eta\varepsilon)$ dual steps, with $P^\star-(B_{r_0}+\|\lambda^\star_\epsilon\|_1B_c)\Delta_\epsilon\le D_\theta(\lambda_K)\le P^\star+\eta B/2+\delta+\varepsilon$. Here $D_\theta$ is the dual function of the parametrised problem and $\lambda^\star_\theta$ its minimiser; the lower bound is the previous theorem, with the same tightened-problem multiplier $\lambda^\star_\epsilon$ and the same $\Delta_\epsilon=\epsilon/(1-\gamma)^2$ (the paper's statement prints $\epsilon/(1-\gamma)$ and calls the multiplier the solution of the unperturbed dual, but its proof, Eq. (46), inherits Theorem 2's tightened-problem multiplier); and $B=\sum_i\big(B_{c_i}/(1-\gamma)+d_i\big)^2$ is the paper's $\sum_i(B_{r_i}/(1-\gamma)-c_i)^2$ translated to cost budgets, a valid bound on $\|J_c-d\|_2^2$ when every $d_i\ge0$ (in general use $|d_i|$). The three error sources are visible: parametrisation ($\epsilon$), inner-loop inaccuracy ($\delta$) and the fixed dual step ($\eta$). Running the inner loop to convergence is expensive, which motivates interleaving the two updates.

RCPO: penalised reward and three timescales

Tessler, Mankowitz, Mannor, ICLR 2019 made the interleaved version the deep-RL standard. Two ideas. First, the actor and critic are trained on the penalised per-step reward $\hat r(\lambda,s,a)=r(s,a)-\lambda c(s,a)$, whose discounted value $\hat V^\pi(\lambda,s)=V_R^\pi(s)-\lambda V_{C_\gamma}^\pi(s)$ satisfies a Bellman equation and can be learned by an actor–critic with a temporal-difference (TD) critic (Primer E), even when the actual constraint $J_C$ is a general (e.g. average or non-discounted) functional that has no Bellman structure. Second, $\lambda$ is updated with Monte-Carlo estimates of the original constraint, on the slowest of three timescales.

Reading Algorithm 2: $v$ are the critic parameters, and the critic takes a TD semi-gradient step, i.e. the target $\hat R_t$ is computed with the current critic and held fixed while the squared prediction error is differentiated. $\Gamma_\theta$ projects onto the admissible actor parameters and $\Gamma_\lambda$ onto the multiplier range $[0,\lambda_{\max}]$. Actor and critic are updated after every transition; the multiplier only once per episode, which is what the index $k$ counts.

NPG-PD: a dimension-free global rate

Ding, Zhang, Başar, Jovanović, NeurIPS 2020 analyse the single-loop scheme "one natural policy gradient step (Primer E), one projected dual step" for tabular softmax policies with a utility constraint $V_g^\pi(\rho)\ge b$ (Slater margin $\xi$, rewards and utilities in $[0,1]$, $\rho$ the initial distribution). Under softmax, the natural gradient step on the Lagrangian is a multiplicative-weights update with the penalised advantage:

The symbol $\propto$ means "proportional to": in each state divide the right-hand side by $Z_t(s)=\sum_b\pi^{(t)}(b\mid s)\exp\big(\eta_1A_L^{(t)}(s,b)/(1-\gamma)\big)$ so that the probabilities sum to one. Equivalently (background box above, with step $\eta_1/(1-\gamma)$), $\pi^{(t+1)}(\cdot\mid s)$ maximises $\sum_ap_aA_L^{(t)}(s,a)-\frac{1-\gamma}{\eta_1}\mathrm{KL}\big(p\,\|\,\pi^{(t)}(\cdot\mid s)\big)$ over probability vectors $p$: follow the penalised advantage, but pay for moving away from the old action distribution.

(In our cost convention: $A_L=A_r-\lambda A_c$ and $\lambda\leftarrow\mathcal P_\Lambda(\lambda+\eta_2(J_c-d))$.) Started from the uniform policy $\theta^{(0)}=0$ with $\lambda^{(0)}=0$ (the initialisation used in the proof) and run with $\eta_1=2\log|\mathcal A|$ and $\eta_2=2(1-\gamma)/\sqrt T$, the iterates satisfy, on average over $t$ (journal version, Ding, Zhang, Duan, Başar, Jovanović, JMLR 26(256), 2025, Theorem 10; the NeurIPS paper's Theorem 1 has the same $O(1/\sqrt T)$ rates but states them with $\eta_2=(1-\gamma)/\sqrt T$ and the constants $4$ and $1/\xi+4\xi$ in place of $7$ and $2/\xi+4\xi$; we quote the journal version)

No factor $|\mathcal S|$ or $|\mathcal A|$ appears: $O(1/\varepsilon^2)$ iterations (big-O notation: Primer 0) for $\varepsilon$-optimality and $\varepsilon$-violation on average, whatever the size of the tables. The constants do depend on the start. The proof bounds the initial divergence (KL: Primer C) $\mathbb E_{s\sim d^{\pi^\star}_\rho}\mathrm{KL}\big(\pi^\star(\cdot\mid s)\,\|\,\pi^{(0)}(\cdot\mid s)\big)$ by $\log|\mathcal A|$, which holds only for the uniform $\pi^{(0)}$, and it telescopes the dual update from $\lambda^{(0)}=0$. From another start the paper still asserts convergence, but that divergence and $\lambda^{(0)}$ enter the bounds in place of the constants $7$ and $2/\xi+4\xi$. The divergence can be arbitrarily large when $\pi^{(0)}$ nearly excludes an optimal action. The proof combines the performance-difference lemma stated here (see Module 9 for further consequences) with the mirror-descent regret of the multiplicative-weights update and the multiplier bound of Section 3; the projection interval $\Lambda$ is twice the Slater bound on $\lambda^\star$. The result bounds averages over $t$ of the iterates' values, not the value of a policy obtained by averaging parameters or action probabilities; it is realised by drawing one iterate uniformly at random per episode, which is exactly the "averaging" cure of the primal-recovery problem.

Two readings. A bound $C/\sqrt T\le\varepsilon$ requires $T\ge(C/\varepsilon)^2$, which is where $O(1/\varepsilon^2)$ comes from; "dimension-free" refers to this iteration count with exact values and gradients, not to the cost of one iteration, which still grows with the numbers of states and actions. And the violation bound concerns $\big[\frac1T\sum_t\big(b-V_g^{(t)}(\rho)\big)\big]_+$, in which violations at some iterations cancel against slack at others: it is not the average violation $\frac1T\sum_t\big[b-V_g^{(t)}(\rho)\big]_+$ and bounds no single iterate.

Last-iterate convergence: regularise the saddle point

Average-iterate guarantees do not say that the current policy is safe: the iterates can circle the saddle forever (the walkthrough shows a period-two cycle). Ding, Wei, Zhang, Ribeiro, NeurIPS 2023 obtain last-iterate convergence for single-time-scale methods by regularising both players. They write the utility as $u$ with threshold $b$ and absorb the threshold into $g:=u-(1-\gamma)b\in[-1,1]$, so their constraint reads $V_g^\pi(\rho)\ge0$: the $g$ below is NPG-PD's utility shifted by $(1-\gamma)b$. With $\psi_t(s,a)=-\log\pi_t(a\mid s)$, the probability simplex $\Delta(\mathcal A)=\{p:p_a\ge0,\ \sum_ap_a=1\}$ of action distributions (Primer B) and its restricted version $\hat\Delta(\mathcal A)=\{\pi(\cdot\mid s)\in\Delta(\mathcal A):\ \pi(a\mid s)\ge\epsilon_0/|\mathcal A|\ \text{for all } a\}$, $\epsilon_0\in(0,1)$,

Here $\mathcal H(\pi)=\mathbb E_\rho^\pi\sum_{k\ge0}\gamma^k\big[-\log\pi(a_k\mid s_k)\big]$ is the discounted entropy of the policy, large when action probabilities are spread out. The shift is harmless: $\sum_{k\ge0}\gamma^k(1-\gamma)b=b$, so $V_g^\pi(\rho)=V_u^\pi(\rho)-b$ and $V_g^\pi(\rho)\ge0$ is exactly $V_u^\pi(\rho)\ge b$. The term $+\tfrac\tau2\lambda^2$ penalises the minimising multiplier player for large multipliers. The policy line is the KL-proximal (multiplicative-weights) step of the background box, restricted to $\hat\Delta(\mathcal A)$; the multiplier line is a projected gradient step, $\lambda_{t+1}=\mathcal P_\Lambda\big(\lambda_t-\eta(V_g^{\pi_t}(\rho)+\tau\lambda_t)\big)$, since $\partial_\lambda L_\tau=V_g^\pi(\rho)+\tau\lambda$.

Montenegro, Mussi, Papini, Metelli, NeurIPS 2024 (C-PG) extend the regularised idea to general parametrisations, including action-based exploration (a stochastic policy randomises each action, as so far) and parameter-based exploration (a deterministic policy whose parameters are drawn at random once per episode), in the cost-minimisation convention $\min_\upsilon J_0(\upsilon)$ s.t. $J_i(\upsilon)\le b_i$. Only the dual is regularised, by a ridge term:

Where the closed form comes from: with $\Delta_i=J_i(\upsilon)-b_i$ the maximisation over $\lambda\ge0$ splits into scalar problems $\max_{\lambda_i\ge0}\{\lambda_i\Delta_i-\tfrac\omega2\lambda_i^2\}$, concave parabolas with vertex at $\lambda_i=\Delta_i/\omega$. If $\Delta_i\gt0$ the vertex is feasible and the value is $\Delta_i^2/(2\omega)$; if $\Delta_i\le0$ the best feasible point is $\lambda_i=0$ with value $0$. So $\lambda_i^\star=(\Delta_i)_+/\omega$ and the maximum is $(\Delta_i)_+^2/(2\omega)$; summing over $i$ gives $H_\omega$.

The closed form is worth a second look: maximising over the regularised multiplier turns the Lagrangian into a quadratic penalty on the violation, and the multiplier that goes with it is proportional to the violation rather than an integral of it. Their Theorem 3.1 quantifies the bias of the ridge: if the potential $\mathcal P_k$ that drives the analysis is below $\varepsilon$, then $\mathbb E[J_0(\upsilon_k)-J_0(\upsilon_0^\star)]\le\varepsilon+\frac\omega2\|\lambda_0^\star\|_2^2$ and $\mathbb E[(J_i(\upsilon_k)-b_i)_+]\le4\varepsilon+\omega\|\lambda^\star_0\|_2$, where $\lambda_0^\star$ is the unregularised multiplier; Theorem 3.2 gives last-iterate iteration complexities for driving the potential down to $\mathcal P_K\le\varepsilon+\beta_1/\alpha_1$: $O(\omega^{-1}\log\varepsilon^{-1})$ (exact gradients, Polyak–Łojasiewicz-type domination $\psi=2$), $O(\omega^{-1}\varepsilon^{-(2/\psi-1)})$ (exact gradients, $\psi\in[1,2)$), and $O(\omega^{-3}\varepsilon^{-4/\psi+1})$ with estimated gradients, under weak $\psi$-gradient domination of the Lagrangian, smoothness and bounded gradient variance (smoothness and stochastic gradients: Primer B; the existence of a saddle point enters Theorem 3.1). Here $\alpha_1\gt0$, $\beta_1\ge0$ are the constants of the weak gradient-domination assumption: $\beta_1=0$ for tabular softmax ($\psi=1$) or direct ($\psi=2$) parametrisations, while for general parametrisations $\beta_1$ carries a compatible-function-approximation bias, and the floor $\beta_1/\alpha_1$ does not shrink with more iterations; Theorem 3.1 then applies with $\varepsilon+\beta_1/\alpha_1$ in place of $\varepsilon$. When $\beta_1=0$, setting $\omega=O(\varepsilon)$ balances bias and rate. Alternatively one tightens the budget to $b_i'=b_i-\delta$ (the paper's route to "zero constraint violation"), which needs the tightened problem to remain feasible and $\delta\ge4\varepsilon+\omega\|\lambda^\star_0\|$ with $\lambda^\star_0$ now the multiplier of the tightened problem. Because $\mathbb E[J_i-b_i']\le\mathbb E[(J_i-b_i')_+]\le\delta$, what this buys is $\mathbb E[J_i(\upsilon_k)]\le b_i$: feasibility in expectation over the algorithm's randomness. With exact gradients the iterate is deterministic and is itself feasible. With estimated gradients individual runs can still violate $b_i$: $J_i-b_i'\in\{0,2\delta\}$ with equal probability satisfies the bound and violates $b_i$ half the time.

Off-policy: conservative cost critics

Off-policy actor-critics (SAC-Lagrangian; off-policy learning from a replay buffer: Primer E) estimate $J_c$ from a replay buffer through a learned $Q_c$, and a cost critic that underestimates makes $\lambda$ collapse to zero while the true cost exceeds the budget. Wu et al., ICLR 2024 (CAL) replace $Q_c$ by an upper confidence bound over an ensemble of $E$ cost critics, $\hat Q_c^{\rm UCB}=\frac1E\sum_i\hat Q_c^i+k\cdot\mathrm{Std}_i(\hat Q_c^i)$, so that the constraint seen by the dual update is pessimistic, and they rectify the actor gradient with an augmented-Lagrangian term (a Lagrangian plus a quadratic penalty on the violation; penalties: Primer B): the multiplier that multiplies $\nabla_a\hat Q_c^{\rm UCB}$ in the actor update is $\tilde\lambda=\max\{0,\lambda-c_{\rm pen}\,(d-\mathbb E[\hat Q_c^{\rm UCB}])\}$, a proportional correction of the same kind as C-PG's closed form, which convexifies the objective near the constraint boundary (their Proposition 1 is a Platt–Barr energy argument in continuous time; see Section 5). The benefit is empirical: on Safety Gym and velocity-constrained MuJoCo tasks CAL reaches the asymptotic performance of state-of-the-art on-policy methods with far fewer samples while markedly reducing constraint violations during training (plus a real-world auto-bidding study).

Here $E$ is the number of critics, $k\gt0$ a chosen uncertainty weight and $\mathrm{Std}_i$ the standard deviation of their $E$ predictions, a measure of disagreement. Without a calibration theorem, “mean plus $k$ standard deviations” is a conservative heuristic, not a $1-\delta$ confidence bound of the kind proved in Module 3. In $\tilde\lambda$, $c_{\rm pen}\gt0$ is CAL's penalty coefficient (their $c$), not a cost function.

What is proved

5. The Multiplier as a Controller: PID Lagrangians

Look again at the dual step $\lambda_{k+1}=(\lambda_k+K_I(J_{C,k}-d))_+$. The multiplier is a running sum of the constraint violation: it is an integral controller (PID control: Primer D) acting on the error $e_k=J_{C,k}-d$, with the RL algorithm as the plant. Stooke, Achiam, Abbeel, ICML 2020 make this reading explicit and draw the obvious conclusion: integral-only controllers overshoot and oscillate, and the standard remedy is to add proportional and derivative action.

Timing convention. For the matrix below and the explorer the order is: measure $e_k$, update $I_k=I_{k-1}+e_k$, form $\lambda_k=K_Pe_k+K_II_k$, then update the policy to obtain $e_{k+1}$. With integral action alone, $\lambda_k=\lambda_{k-1}+K_Ie_k$. This is the same indexing convention used by the simulation. Updating the policy with the old multiplier instead produces a different state matrix.

The policy is then updated with the Lagrangian gradient. Stooke et al. rescale it as $\nabla_\theta L=\frac{1}{1+\lambda}\big(\nabla_\theta\hat J-\lambda\nabla_\theta\hat J_C\big)$, a convex combination of the reward and cost gradients that keeps the step size bounded when $\lambda$ is large; since $\operatorname*{arg\,max}_\theta(J-\lambda J_C)=\operatorname*{arg\,max}_\theta\frac{1}{1+\lambda}(J-\lambda J_C)$, it does not change the fixed points. With $u=\lambda/(1+\lambda)\in[0,1]$ this reads $\nabla_\theta L=(1-u)\nabla_\theta J-u\nabla_\theta J_C$. Their constraint-controlled PPO (CPPO-PID) uses separate value and cost-value critics, because a rapidly moving $\lambda$ would make a single critic for $r-\lambda c$ chase a moving target.

Results. On Safety Gym tasks (cost limits from 25 to 200 depending on the experiment, e.g. 50 in DoggoGoal2 and 50–200 in DoggoButton1) the paper shows that with the integral-only rule the episodic cost oscillates around the limit with a period and amplitude that shrink as $K_I$ grows (a fast $K_I$ removes the oscillation but costs return), that proportional control damps these oscillations across a range of $K_I$ while keeping return high, and that derivative control reduces cost overshoot in the reported experiments and slows cost increases inside the feasible region, which the Lagrangian method cannot do. CPPO-PID is a standard baseline in SafePO/OmniSafe and its multiplier rule is reused inside SafeDreamer's planner (Module 9). The explorer below reproduces the phenomenon on a one-parameter policy: watch the plain multiplier ring and the PID multiplier settle. Its cost curve is concave, so the Lagrangian is slightly convex in the policy parameter (case $a\gt1$ of (c)): the integral-only loop is even weakly unstable, and its oscillation can grow until clipping changes the motion; a periodic limiting orbit is not implied by the local model.

6. Risk-Sensitive Constraints: CVaR and Beyond

An expected-cost budget allows rare catastrophes as long as the average is fine. Risk-constrained RL replaces the expectation of the cumulative cost $Z$ by a tail statistic. The two classical ones are the value-at-risk $\mathrm{VaR}_\alpha(Z)=\min\{z:F_Z(z)\ge\alpha\}$ (a chance constraint in disguise) and the conditional value-at-risk, which also counts how bad the tail is.

Chow, Ghavamzadeh, Janson, Pavone, JMLR 2018 pose the CVaR-constrained MDP (cost minimisation: $\min_\theta V^\theta(x^0)$ s.t. $\mathrm{CVaR}_\alpha(\text{cumulative constraint cost})\le\beta$) and use the Rockafellar–Uryasev form to turn it into a joint problem in $(\theta,\nu)$ with an expectation constraint, since $\mathrm{CVaR}_\alpha\le\beta$ iff some $\nu$ has $H_\alpha(Z,\nu):=\nu+\frac{1}{1-\alpha}\mathbb E[(Z-\nu)_+]\le\beta$. The new constraint is convex in $\nu$ but not smooth (the kink of $(\cdot)_+$; for a cost with atoms $H_\alpha$ is piecewise linear in $\nu$), which is why the $\nu$-derivative below is a subgradient. The Lagrangian and its (sub)gradients (their Eqs. 5, 7–9) are

Why $\ge$ in $\partial_\nu L$: as a function of $\nu$, $(Z-\nu)_+$ has slope $-1$ where $Z>\nu$, slope $0$ where $Z\lt\nu$, and any slope in $[-1,0]$ at $Z=\nu$. Taking expectations, the left and right derivatives of $H_\alpha$ in $\nu$ are $1-\mathbb P(Z\ge\nu)/(1-\alpha)$ and $1-\mathbb P(Z>\nu)/(1-\alpha)$, and $\partial_\nu H_\alpha$ is the interval between them; the displayed element is the left end. They differ only if $Z$ has an atom at $\nu$. $H_\alpha$ is minimal where $0\in\partial_\nu H_\alpha$, i.e. $\mathbb P(Z>\nu)\le1-\alpha\le\mathbb P(Z\ge\nu)$: $\mathrm{VaR}_\alpha(Z)$ is one such $\nu$, not necessarily the only one.

Two structural points. An optimal policy need not be Markov in the state alone: the term $(Z-\nu)_+$ depends on the cost accumulated so far. Chow et al. cite Ott (2010) and Bäuerle and Ott (2011) for a deterministic optimal policy that depends on the history only through the time step, the current state and the accumulated discounted constraint cost. Those results are about minimising CVaR (Bäuerle and Ott minimise the AVaR of the discounted cost), not about the CVaR-constrained problem. For the constrained problem, the same augmented state (together with $\nu$) still gives a Markov description, since for fixed $\nu$ the constraint $H_\alpha\le\beta$ is an expected-cost constraint on the augmented MDP. But, as in every CMDP, the optimum may have to randomise. Take one decision with actions safe (task cost $1$, constraint cost $0$) and risky (task cost $0$, constraint cost $1$), $\alpha=0.5$ and $\beta=0.5$. Choosing risky with probability $p$ gives $\mathrm{CVaR}_{0.5}=\min(2p,1)$, so the optimum $p=\tfrac14$ has task cost $\tfrac34$, while the only feasible deterministic choice (safe) costs $1$. Their actor-critic algorithms work on this augmented MDP whose extra state variable tracks that running cost (compare Section 7), with stochastic policies $\mu(a\mid x,s;\theta)$. And in the policy-gradient algorithm the three variables move on three timescales, $\nu$ fastest, then $\theta$, then $\lambda$ (the actor-critic versions add a fourth, fastest one for the critic), which, under the assumptions of the theorem above, yields almost-sure convergence to a local saddle point of $L$, i.e. a locally optimal policy of the CVaR-constrained problem. The $\nu$ update is a subgradient step on a piecewise-linear function, exactly the kink phenomenon of the walkthrough.

Gaussian shortcut. Yang, Simão, Tindemans, Spaan, AAAI 2021 (WCSAC) keep SAC-Lagrangian but replace the expected-cost constraint by a per-state CVaR of a Gaussian safety critic $C^\pi(s,a)\sim\mathcal N(Q_c^\pi,\Sigma_c^\pi)$, which has the closed form (tail fraction $\alpha$)

with $\varphi,\Phi$ the standard normal density and CDF (Primer C), and the multiplier objective $J_s(\kappa)=\mathbb E[\kappa(d-\Gamma_{\pi_\theta})]$. WCSAC write the variance as $V_c^\pi$; we write $\Sigma_c^\pi$ because $V_c^\pi$ is this page's cost value function. The formula is the Gaussian tail mean. For a standard normal $U$, $\varphi'(u)=-u\varphi(u)$, so $\int_z^\infty u\varphi(u)\,du=\varphi(z)$ and $\mathbb E[U\mid U\ge z]=\varphi(z)/(1-\Phi(z))$ (the Mills-ratio identity). For $Z=\mu+\sigma U$ with $\mu=Q_c^\pi(s,a)$ and $\sigma=\sqrt{\Sigma_c^\pi(s,a)}$, the worst $\alpha$ fraction lies above $\mu+\sigma z_\alpha$ with $z_\alpha=\Phi^{-1}(1-\alpha)=-\Phi^{-1}(\alpha)$; since $1-\Phi(z_\alpha)=\alpha$ and $\varphi$ is even, $\mathbb E[Z\mid Z\ge\mu+\sigma z_\alpha]=\mu+\sigma\varphi(\Phi^{-1}(\alpha))/\alpha$, the displayed $\Gamma_\pi$. The formula is exact only when the cumulative cost really is Gaussian, not for every distribution with the same mean and variance; Exercise 8.5 shows how far it can be from the CVaR of a heavy-tailed cost.

Spectral risk. Kim et al., NeurIPS 2024 (SRCPO) constrain a spectral risk measure $R_\sigma(X)=\int_0^1F_X^{-1}(u)\sigma(u)\,du$ with an increasing spectrum $\sigma\ge0$, $\int_0^1\sigma=1$; CVaR is $\sigma(u)=\mathbf 1_{u\ge\alpha}/(1-\alpha)$. The dual form $R_\sigma(X)=\inf_g\{\mathbb E[g(X)]+\int_0^1g^\ast(\sigma(u))\,du\}$ over increasing convex $g$ (for CVaR, $g(x)=(x-\beta)_+/(1-\alpha)$ gives back Rockafellar–Uryasev) turns the risk constraint into an expectation for each fixed $g$.

The CVaR case in detail. For $g(x)=k(x-\beta)_+$ with $k=1/(1-\alpha)$, maximise $xy-g(x)$ separately over $x\le\beta$ (slope $y$) and over $x\ge\beta$ (slope $y-k$): $g^*(y)=\beta y$ for $0\le y\le k$ and $g^*(y)=+\infty$ otherwise. The CVaR spectrum takes only the values $0$ and $k$, so $\int_0^1g^*(\sigma(u))\,du=\beta\int_0^1\sigma(u)\,du=\beta$, and the infimum over this family of $g$ is $\inf_\beta\{\beta+\mathbb E[(X-\beta)_+]/(1-\alpha)\}$, exactly the Rockafellar–Uryasev formula.

SRCPO is therefore bilevel: the outer problem optimises the dual variables of the risk measure, the inner problem is a CMDP on the augmented state $(s_t,\{e_{i,t}\},\gamma^t)$ with $e_{i,t+1}=(c_{i,t}+e_{i,t})/\gamma$, and, to the authors' knowledge, it is the first risk-constrained method with a guarantee of convergence to an optimum in the tabular setting (earlier CVaR methods, Chow et al. included, guarantee only local convergence). That guarantee is narrower than "tabular" suggests. The inner theorem (their Thm 5.3) needs finite augmented state and action spaces (the accumulated-cost coordinates included), softmax policies and a strictly feasible policy. The outer theorem (Thm 6.3) needs a finite set of candidate parameters $\beta$ and a softmax sampler. A general spectrum is first replaced by an $M$-step function, which changes the risk by at most $C_{\max}\sigma(1)/((1-\gamma)M)$ (their Lemma 6.1). So the optimum reached is that of this finite, discretised problem; their practical algorithm, which samples $\beta$ from continuous ranges with a truncated-normal sampler, is not covered by the theorems.

The augmented state in detail: $e_{i,0}=0$ and $e_{i,t}=\gamma^{-t}\sum_{j\lt t}\gamma^jc_{i,j}$, the discounted cost accumulated so far, rescaled; then $e_{i,t+1}=(e_{i,t}+c_{i,t})/\gamma$, and the extra coordinate $\gamma^t$ converts back, $\gamma^te_{i,t}=\sum_{j\lt t}\gamma^jc_{i,j}$. The outer parameter vector $\beta$ fixes a finite-dimensional choice of the convex function $g$; it is not a CMDP multiplier. $C_{\max}$ bounds each one-step cost, and the discretisation bound is informative when $\sigma(1)$ is finite. See SRCPO, Sections 5–6.

7. Almost-Sure Constraints via State Augmentation

Under a cumulative constraint that must hold with probability one, how carefully the agent should act depends on how much budget is left, and a stationary policy $\pi(a\mid s)$ cannot see that. Feasibility is not necessarily the obstacle: with nonnegative costs, for instance, a policy that always picks an available zero-cost action is safe on every trajectory. What fails in general is optimality. Stationary policies in the original state need not include an optimal policy, and in Sootla et al.'s ablation the unaugmented policy hedges by leaving budget unused and pays for it in task cost. Tracking the remaining budget restores a Markov description, and Lemma 1 of the Wachi–Shen–Sui survey makes the missing variable explicit. Over a finite horizon $H$, with nonnegative costs (the survey takes $c\in[0,1]$) and budget $d$ (the survey's $\xi$), define the remaining discounted budget $\eta_{h+1}=\gamma_c^{-1}(\eta_h-c(s_h,a_h))$, $\eta_0=d$. Then $\sum_{h\le H}\gamma_c^hc(s_h,a_h)\le d$ iff $c(s_h,a_h)\le\eta_h$ for all $h$, so the single cumulative constraint is equivalent to instantaneous constraints on an augmented state. The closed form is $\eta_h=\gamma_c^{-h}\big(d-\sum_{h'\lt h}\gamma_c^{h'}c_{h'}\big)$: the rescaling by $\gamma_c^{-h}$ is what makes the recursion time-invariant, and $c_h\le\eta_h$ says exactly that the partial sum up to $h$ is within budget. Nonnegativity is what turns "every partial sum within budget" into "the total within budget": with signed costs an early overspend could be repaid later, and the instantaneous constraints would be strictly stronger than the cumulative one.

"With probability one" (almost surely, a.s.) allows exceptional trajectories as long as their total probability is zero; it is not literally a statement about every conceivable trajectory. Because time steps are countable, per-step statements combine: if $\mathbb P(E_t)=1$ for every $t$, then $\mathbb P(\bigcap_tE_t)=1$, since by the union bound the complements have total probability at most $\sum_t\mathbb P(E_t^c)=0$.

Two remarks. The a.s. formulation is much stronger than an expected or CVaR budget, and only makes sense when a policy that never overspends exists; in practice $n$ is finite, and $V_n^\star\uparrow V_\infty^\star$ is a statement about optimal values, not a violation bound for any finite-$n$ policy: a finite penalty can still make a rare or heavily discounted violation worthwhile. And because $d$ enters only as the initial safety state, one policy generalises across budgets by changing $z_0$: in their generalisation experiment (a pendulum-type task, their Fig. 4) a policy trained with budgets sampled from $[5,100]$ met test budgets of 40 and 80 more reliably than one trained at the single budget 60. Their Safety Gym runs, by contrast, test the almost-sure constraint itself, with a few outlier trajectories still violating it.

The multiplier as a state. Calvo-Fullana, Paternain, Chamon, Ribeiro, IEEE TAC 2024 augment with a different summary of the constraint history: the Lagrange multiplier itself. (They use the utility convention of the monitoring problem: rewards $r_i$ with thresholds $c_i$ and constraints $V_i\ge c_i$ on long-run averages, so here $c_i$ is a number, not a cost function.) Training samples $(s,\lambda)$ from $\mathcal S\times\Lambda$ and solves the ordinary MDP with reward $r_\lambda(s,a)=r_0(s,a)+\sum_i\lambda_i(r_i(s,a)-c_i)$ for a policy $\pi_\theta(a\mid s,\lambda)$ (Alg. 1). Execution runs the dual dynamics online (Alg. 2): for epochs of length $T_0$, act with $\pi_\theta(\cdot\mid s_t,\lambda_k)$ and then

Reading the statement: for a sequence $a_T$, $\liminf_Ta_T=\lim_{N\to\infty}\inf_{T\ge N}a_T$ is its eventual lower envelope (Primer 0). So the constraint part says that, with probability one, for every $\epsilon\gt0$ the running average $\frac1T\sum_{t\lt T}r_i(s_t,a_t)$ falls below $c_i-\epsilon$ only finitely often; deficits at finite times are allowed. The reward part is about an expectation over trajectories, not a bound on each realised average.

8. Adjacent: Safe RLHF

Dai et al., ICLR 2024 carry the CMDP template into language-model alignment. Human preferences are collected separately for helpfulness and harmlessness; a reward model $R_\phi(y,x)$ (learned reward models: Primer E) is fitted to the first with the Bradley–Terry loss, and a cost model $C_\psi(y,x)$ to the second with a pairwise term plus a classification term that anchors the sign of the cost: $$L_C(\psi)=-\mathbb E\big[\log\sigma\big(C_\psi(y_w,x)-C_\psi(y_l,x)\big)\big]-\mathbb E\big[\log\sigma(s_wC_\psi(y_w,x))+\log\sigma(s_lC_\psi(y_l,x))\big],$$ where in the harmlessness dataset $y_w$ is the more harmful response of the pair and $s=+1$ marks a harmful, $s=-1$ a harmless response, so that $C_\psi\gt0$ means unsafe and the boundary $C_\psi=0$ is a virtual response that the second term pins down. The fine-tuning problem is then a CMDP with a one-step horizon if the whole response is read as one action (prompt $x$, response $y\sim\pi_\theta(\cdot\mid x)$; PPO itself works token by token, $y=a_{1:T}$): $\max_\theta J_R(\theta)$ s.t. $J_C(\theta)\le0$ with $J_R=\mathbb E[R_\phi(y,x)]$, $J_C=\mathbb E[C_\psi(y,x)]+d$, relaxed to $\min_\theta\max_{\lambda\ge0}[-J_R(\theta)+\lambda J_C(\theta)]$ and solved by alternating PPO steps (Primer E) on $\theta$ with multiplier steps on $\lambda$ (Section 4); the offset $d$ tunes the permitted expected signed cost score.

The offset enforces $\mathbb E[C_\psi]\le-d$. This constrains an average score, not directly $\Pr(C_\psi>0)$. Positive scores can be offset by sufficiently negative ones. Converting this budget to a harmful-output frequency requires additional assumptions about score bounds or calibration. Likewise, convergence results from earlier sections do not transfer automatically to PPO with learned reward and cost models.

The Lagrangian template applies: the multiplier tracks the constraint violation as an integral controller, the trained policy is a Lagrangian maximiser rather than a certified-safe object, and the guarantee is on an expectation over prompts, not on individual outputs. The reported effect over three rounds on Alpaca-7B is a drop of harmful responses on their evaluation set from 53.08% to 2.45% with improved helpfulness, and the method spawned multimodal follow-ups. For the reader of this section the interesting point is the decoupling: one reward model per objective, with the trade-off set by a budget instead of a fixed weight, which is exactly the argument of Section 1 restated for LLMs.

Walkthrough: Dual Ascent on a Two-Action CMDP

The smallest CMDP that shows everything: one state, two actions, one budget. We compute the dual function by hand, recover the mixed optimum from the KKT conditions, and watch a fixed-step dual ascent oscillate around $\lambda^\star$. ("Dual ascent" is the traditional name, from the cost-minimisation convention, in which the dual function is concave and maximised; in this page's convention the very same multiplier update is projected subgradient descent on the convex $D$, as in Section 4.)

Interactive: Multiplier Dynamics (Plain vs PID)

Compare plain and PID multiplier updates on the same toy constrained policy. Change one gain and predict whether the cost settles near the budget, oscillates or overshoots. The plots show a finite simulation; the model and reference-line assumptions are explained below.

Exercises

Graded practice

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

Easy practice

Medium practice

Hard practice

Original longer exercises

Key Papers

Further reading: García & Fernández, JMLR 2015 (the classic taxonomy: constrained criteria are one of its "modified optimality criterion" branches), Gu et al., IEEE TPAMI 2024 (comprehensive review including a comparison of CMDP sample complexities), Wachi, Shen, Sui, IJCAI 2024 (how the constraint formulations relate), Wu et al., ICLR 2024 (CAL).

Flashcards