Constrained Markov Decision Processes

Definition

A Constrained Markov Decision Process is an MDP augmented with auxiliary cost functions and thresholds, so a policy must maximize reward while satisfying expected cumulative cost constraints.

Why It Matters

CMDPs separate “what the agent is trying to do” from “what it is not allowed to spend, violate, or risk too much.” That separation is often cleaner than burying safety in a reward penalty, because feasibility remains a first-class object.

Formalism / Key Objects

• A discounted CMDP can be written as an MDP (S,A,P,R,mu,gamma) plus cost functions C_1,...,C_m and thresholds d_1,...,d_m.
• The reward objective is:

$$J(\pi )=E_{\tau \sim \pi }\left[\sum _{t=0}^{\infty }{\gamma }^{t}R(s_t,a_t,s_{t+1})\right].$$

• Each cost return is:

$$J_{C_i}(\pi )=E_{\tau \sim \pi }\left[\sum _{t=0}^{\infty }{\gamma }^t{C}_i(s_t,a_t,s_{t+1})\right].$$

• The feasible policy set is:

$${\Pi }_C=\{\pi \in \Pi :\forall i,J_{C_i}(\pi )\le d_i\}.$$

• The constrained RL problem is pi* in argmax_{pi in Pi_C} J(pi).
• Constrained Policy Optimization approximates this problem with trust-region surrogate reward and cost constraints.
• Probabilistic Shielding can enforce CMDP constraints by augmenting states with a cost budget x and filtering the sampled policy distribution through a backup cost critic.

Connections

• Achiam2017 - Constrained Policy Optimization is the central single-agent neural-policy source for CMDPs in this wiki.
• Gu2022 - Multi-Agent Constrained Policy Optimisation lifts CMDP-style cost constraints into constrained Markov games.
• Constrained Markov Potential Games are a multi-agent variant where equilibrium structure and coupled feasibility matter.
• Shielding is an alternative enforcement pattern: it filters unsafe actions by construction rather than optimizing inside an expected-cost feasible set.
• HamelDeLeCourt2025 - ProSh Probabilistic Shielding for Model-free Reinforcement Learning reframes a CMDP as a risk-augmented MDP where the shield keeps expected cost within a live budget.
• Decision Theory supplies the language for trade-offs among reward, cost, feasibility, and risk.

Common Confusions

• A CMDP cost is not automatically a hard safety invariant; it is usually an expected cumulative constraint unless the model encodes an invariant directly.
• A fixed reward penalty is not equivalent to a CMDP unless the penalty coefficient is known to recover the intended constrained solution.
• Feasibility during training is different from feasibility only at convergence.

Key Sources

• Achiam2017 - Constrained Policy Optimization
• HamelDeLeCourt2025 - ProSh Probabilistic Shielding for Model-free Reinforcement Learning
• Gu2022 - Multi-Agent Constrained Policy Optimisation
• Alatur2024 - Provably Learning Nash Policies in Constrained Markov Potential Games