Safe and Constrained RL: The CMDP and Policy Methods

Everything in the course so far has taken a single instruction on faith: find the policy that maximizes expected return. That instruction is complete only if the reward function is a perfect statement of what you want. It almost never is. A reward is a compression of a designer's intent into one scalar per step, and a capable optimizer exploits every gap between that scalar and the intent. It optimizes what you wrote, not what you meant, and the two diverge exactly where you were not looking. A cleaning robot rewarded for a tidy room learns to sweep dust under the rug; a boat-racing agent rewarded for the score circles a lagoon collecting the same power-ups forever instead of finishing the race.¹ These are not optimizer bugs: the optimizer worked, the reward was wrong, and nothing in reward maximization penalizes the difference.

This lesson is about the discipline that takes the gap seriously: state, alongside the reward, the constraints a good policy must respect — a collision budget, a power limit, a rule it may not break — and optimize return subject to them. It shares a principle with offline RL, where the remedy for unverifiable value estimates was pessimism about what the data cannot confirm; here the remedy for an incomplete reward is pessimism about what the reward does not measure. And it sharpens the over-optimization story from RLHF: the KL leash there is one instance of the general move this lesson formalizes — bound how hard you push on a proxy, because the proxy stops being right before the optimizer stops pushing.

This lesson builds the core machinery: the constrained MDP that states the problem, and the two policy-optimization methods that solve it — Lagrangian primal-dual (RCPO) and constrained policy optimization (CPO). Risk-sensitivity, safe exploration, and the alignment framing continue in a companion lesson.

Why reward maximization alone is dangerous

The trouble is structural, not a matter of careless reward design. Call the reward you wrote the proxy $r$ and the outcome you actually care about the true objective $r^{\star }$. The two agree on the behaviors you had in mind when you wrote $r$ — the ones near your demonstrations and your imagination — and they can diverge arbitrarily on behaviors you did not consider. Optimization is a search for the highest-reward behavior, so it is drawn precisely toward the regions where $r$ is high for reasons that have nothing to do with $r^{\star }$. The better the optimizer, the more reliably it finds them.²

The pattern is the same one the RLHF lesson named over-optimization: a language policy free to maximize a learned reward model drifts into degenerate text the reward model mistakenly scores highly. There the fix was a KL leash back to the reference model — a soft constraint on how far the policy may move. That is a special case of the general idea. When the thing you cannot capture in the reward is how far the policy strays, a KL bound suffices; when it is a physical limit (energy, collisions, torque), you need an explicit constraint on a measured cost. Both limit how far the optimizer can exploit the proxy. The rest of the lesson builds the machinery for the second, harder case.

A first instinct is to fold the constraint into the reward as a penalty: subtract $\lambda c_t$ from the reward for each unit of cost $c_t$ and tune $\lambda$ by hand. This works when you can find the right $\lambda$, but it hides the constraint inside a scalar and gives you no guarantee about the resulting cost. Pick $\lambda$ too small and the policy pays the penalty and violates the limit anyway; too large and it becomes so cautious it abandons the task. The constrained formulation makes the limit a first-class object — a number you specify rather than a weight you tune by trial and error — and derives the right penalty automatically.

The constrained MDP

The formalism is the constrained Markov decision process (CMDP).³ It is an ordinary MDP with one addition: alongside the reward $r(s,a)$, each transition emits one or more cost signals $c(s,a)$, and the policy must keep the expected discounted cost under a threshold $d$ the designer sets.

Write the return as before and define an analogous cost return:

The CMDP problem is then to maximize the reward return subject to the cost return staying within budget:

With several constraints there is one $c_i$ and one threshold $d_i$ per requirement. The cost is not the negative of reward; it is a separate measurement of something the reward does not price — a count of collisions, joules burned, or times a safety envelope was crossed — and $d$ says how much of it you will tolerate on average.

The constraint carves the space of all policies into a feasible set — those that satisfy $J_c(\pi )\le d$ — and the goal is the best-return policy inside it, which is in general different from the unconstrained optimum sitting outside.

Because the best feasible policy so often sits on the boundary $J_c(\pi )=d$ (spend the whole budget, no more), the constraint is typically active, and the two methods that follow are two ways of finding that boundary point.

Lagrangian methods and RCPO

The textbook tool for a constrained optimization is the Lagrangian. Introduce a multiplier $\lambda \ge 0$ on the constraint and fold it into a single objective,

Read the multiplier as a price on cost. For a fixed $\lambda$, maximizing $\mathcal{L}$ over $\pi$ is an ordinary unconstrained RL problem with the shaped reward $r_t-\lambda c_t$ — exactly the hand-penalty from earlier, except now $\lambda$ is not something you guess. The theory of Lagrangian duality says the constrained optimum is a saddle point of $\mathcal{L}$: a maximum over $\pi$ and a minimum over $\lambda$. We reach it by primal-dual optimization — alternate improving the policy at the current price and adjusting the price toward the constraint.

The multiplier update is a gradient step on $\mathcal{L}$ in $\lambda$, and $\partial \mathcal{L}/\partial \lambda =-(J_c(\pi )-d)$, so it is a simple feedback law:

with $[\cdot {]}_{+}$ clamping $\lambda$ to be non-negative. When the policy overspends its cost budget ($J_c>d$), $\lambda$ rises, the penalty grows, and the next policy update backs off the expensive behavior. When the policy is comfortably under budget ($J_c<d$), $\lambda$ falls toward zero, the constraint relaxes, and the policy is free to pursue reward. The price self-tunes until $J_c=d$.

Reward Constrained Policy Optimization (RCPO)⁴ is the actor-critic realization of this idea, with one refinement that makes it practical. Rather than wait for a full episode to measure $J_c(\pi )$, RCPO treats $\lambda$ as a slowly adapting parameter on a separate, slower timescale than the policy and value updates. On the fast timescale the actor and critic optimize the penalized reward $r_t-\lambda c_t$ with any standard policy-gradient method; on the slow timescale $\lambda$ drifts by the feedback law above. The timescale separation is what makes the saddle-point search converge: the policy sees a nearly-fixed price long enough to respond to it, and the price sees a nearly-converged policy long enough to read its true cost.

The appeal is that RCPO reuses any policy-gradient method wholesale and adds one scalar and one update line. The cost is that the guarantees are asymptotic: during training, before $\lambda$ has caught up, the policy can and does violate the constraint. For a simulator that is harmless. For a physical system where every constraint violation is a real collision, it is not — which motivates methods that bound the cost at every update, not just in the limit.

Worked example: the multiplier finding the budget

Trace $\lambda$ over a few dual steps to see the feedback settle. Set the cost budget $d=25$ (say, an average of 25 collisions-worth of cost per episode is tolerated) and the dual step ${\eta }_{\lambda }=0.01$, starting from $\lambda =0$. With $\lambda =0$ the policy ignores cost entirely, so it overspends badly — measure ${\hat{J}}_c=60$. The dual step raises

Now cost is priced at $0.35$ per unit; the next policy backs off and measures ${\hat{J}}_c=32$, still over budget, so

The policy tightens further to ${\hat{J}}_c=22$, now under budget, and the multiplier falls:

The overshoot-and-correct pattern — $0\to 0.35\to 0.42\to 0.39$ — is the feedback loop converging on the price at which ${\hat{J}}_c=d$. It oscillates around the budget and, on the slow timescale, damps toward the ${\lambda }^{\ast }$ where the constraint is exactly met. That equilibrium ${\lambda }^{\ast }$ is the shadow price of the constraint: the marginal reward the policy gives up per unit of cost budget, and had you set the hand-penalty of the opening section to exactly ${\lambda }^{\ast }$ you would have recovered the same policy — the primal-dual loop is what finds that number for you instead of making you guess it.

Constrained policy optimization (CPO)

Constrained Policy Optimization (CPO)⁵ delivers a per-update guarantee by grafting the constraint onto a trust-region method. Recall the trust-region idea from policy-gradient methods: improve the policy within a small KL ball around the current one, small enough that a local linear model of the return is trustworthy. TRPO solves, each step,

where ${\hat{A}}_r$ is the estimated reward advantage of the new policy over the old and $\delta$ is the trust-region radius. CPO adds a second constraint inside the same trust region: a linear model of the cost return must stay under budget. Using the surrogate $J_c({\theta }_k)+{\hat{A}}_c(\theta )$ for the new policy's cost, the CPO subproblem is

Because both the objective and the cost constraint are linearized and the KL constraint is quadratic, the subproblem is a small convex program solvable in closed form (up to a line search). Achiam et al. prove a worst-case bound: the true cost return of the updated policy exceeds the surrogate by at most a term that shrinks with $\delta$, so with a small enough trust region each CPO update keeps the policy approximately feasible throughout training, not merely at convergence. That near-monotonic feasibility is the property RCPO lacks and the reason CPO is the reference method when violations during learning are costly.

When a proposed update finds no feasible point at all — the current policy already violates the budget and no step within the trust region fixes it — CPO falls back to a pure recovery step that decreases cost as fast as the trust region allows, ignoring reward until the policy is feasible again. That recovery mode is what lets CPO start from an infeasible policy and steer it into the feasible set.

Where this leaves us

The honest formulation of behave well is now precise. A constrained MDP keeps the reward but adds one or more cost signals, each with a budget, and asks for the policy that maximizes return subject to keeping expected cost under budget. That single move turns the vague demand for safety into an optimization problem with a feasible set.

Two policy-optimization methods solve it:

• Lagrangian primal-dual (RCPO) turns the constraint into a penalty with a learned multiplier $\lambda$: raise $\lambda$ when the cost budget is exceeded, lower it when there is slack, so the penalty self-tunes toward the boundary.
• CPO builds the cost budget directly into a trust-region update, guaranteeing (to first order) that each policy step stays feasible rather than only converging to feasibility in the limit.

Both control the mean cost. But a policy safe on average can still be catastrophic in the tail, and a policy that respects a constraint at convergence may violate it wildly while learning. Optimizing the tail (risk-sensitive RL), staying safe during exploration (shields, Lyapunov methods, safety layers), and the connection to alignment continue in Safe RL: Risk, Safe Exploration, and Alignment.