Constrained MDP (CMDP): Definition and Examples

A constrained Markov decision process (CMDP) is a Markov decision process with one or more additional cost signals, each with a budget. The agent must maximise expected return while keeping every expected cumulative cost at or below its limit. It is the standard formalism for safe reinforcement learning when safety can be expressed as a measurable cost.

Definition

With reward $r$ , cost functions $c_{i}$ and limits $d_{i}$ , the CMDP problem is

π max J_{R} (π) = E_{π} [t \sum γ^{t} r_{t}] s.t. J_{C_{i}} (π) = E_{π} [t \sum γ^{t} c_{i, t}] \leq d_{i} for all i .

Here $γ$ is the discount factor. Altman's 1999 monograph laid out the theory: optimal policies exist, may need to be stochastic (a deterministic optimal policy is not guaranteed, unlike in an ordinary MDP), and for finite problems can be found by linear programming over state-action occupancy measures.

Why not just subtract the cost?

A fixed penalty $r - k c$ forces you to choose $k$ in advance, and the right value depends on the policy and environment. Too small and the agent ignores the constraint; too large and it refuses to do anything useful. A CMDP states the requirement you actually have, such as "at most 0.1 expected collisions per episode", and lets the algorithm find the trade-off.

Lagrangian methods

The most common solution turns the constraint into an adaptive penalty with a multiplier $λ \geq 0$ :

π max λ \geq 0 min J_{R} (π) - λ (J_{C} (π) - d) .

The policy is trained on $r - λ c$ , and $λ$ is updated by gradient ascent on the constraint violation: $λ \leftarrow max (0, λ + η (J_{C} - d))$ .

Worked example

The limit is $d = 0.1$ , the current policy's measured cost is 0.15, $λ = 0.5$ and the multiplier step is $η = 2$ . The update gives $λ = 0.5 + 2 \times 0.05 = 0.6$ , so each unit of cost now subtracts 0.6 from the reward and the policy is pushed toward safer behaviour. Once the measured cost drops below 0.1, $λ$ shrinks again. Lagrangian training often oscillates around the limit, so constraints can be violated during learning; methods such as constrained policy optimization add trust-region steps to keep each iterate approximately feasible.

Why it matters

CMDPs separate "what we want more of" from "what we must not exceed", which is how safety requirements are usually written. The same structure appears in RL for language models when a helpfulness reward is optimised subject to a limit on harmful outputs, and it gives evaluations a clear target: report the constraint metric with its uncertainty, not only the reward.

Sources

Eitan Altman. Constrained Markov Decision Processes, 1999. www-sop.inria.fr
Joshua Achiam, David Held, Aviv Tamar, Pieter Abbeel. Constrained Policy Optimization, 2017. arxiv.org