Constrained MDPs and policy safety

Assume the Axiom of Choice. Let $S$ be a finite nonempty set, let $d$ be a probability distribution on $S$, and for each $s\in S$ let $A(s)$ be a finite nonempty set with probability distributions $q_s$ and $p_s$. On the power-set sigma-algebra of $A(s)$, define

${\mathrm{TV}}_{A(s)}(q_s,p_s):=\frac{1}{2}{\sum }_{a\in A(s)}\mathrm{\mid }{q}_s(a)-p_s(a)\mathrm{\mid }\mathrm{.}$

Use the directional Kullback–Leibler divergence with natural logarithms, defined by

$D_{\mathrm{K}\mathrm{L}}(q_s\mathrm{\parallel }{p}_s):=\{\begin{array}{ll}{\displaystyle \sum _{a:q_s(a)>0}{q}_s(a)\log \frac{q_s(a)}{p_s(a)},}& q_s(a)>0\Rightarrow p_s(a)>0,\\ +\mathrm{\infty },& \text{otherwise,}\end{array}$

and the convention $0\log 0=0$. Put

$K:={\sum }_{s:d(s)>0}d(s)D_{\mathrm{K}\mathrm{L}}(q_s\mathrm{\parallel }{p}_s)\in [0,+\mathrm{\infty }]\mathrm{.}$

Then

${\sum }_{s\in S}d(s){\mathrm{TV}}_{A(s)}(q_s,p_s)\le \sqrt{K\mathrm{/}2},$

where the right side is $+\mathrm{\infty }$ when $K=+\mathrm{\infty }$.

Achiam et al., Constrained Policy Optimization, §5.1, equation (7).

The finite-action equality in step 1.1 uses the event-supremum convention, not the total-variation norm of a signed measure. AC enters only in the KL/Pinsker branch; the finite-sum and weighted square-root arguments are choice-free.

Let $M=(S,\mathcal{R},(A(s){)}_{s\in S},p)$ be a finite Markov decision process with nonempty state set $S$ and finite nonempty action set $A(s)$ at each state. Put $\mathcal{X}=\{(s,a,\rho ,s^{\mathrm{\prime }}):s\in S,a\in A(s),\rho \in \mathcal{R},s^{\mathrm{\prime }}\in S\}$. Let $\mu$ be a probability distribution on $S$, let $\gamma \in [0,1)$, let $m\ge 1$ be an integer, and for each $i\in \{1,\dots ,m\}$ let $b_i\in \mathbb{R}$, $C_i\ge 0$, and $c_i:\mathcal{X}\to [-C_i,C_i]$. A finite discounted constrained Markov decision process (CMDP) is the tuple consisting of $M$, $\mu$, $\gamma$, and the bounded transition-cost functions and thresholds $(c_i,b_i{)}_{i=1}^m$. Its immediate reward signal is $r(s,a,\rho ,s^{\mathrm{\prime }})=\rho$.

For a stationary Markov policy $\pi$, define the state-mass sequence recursively by ${\mu }_0^{\pi }=\mu$ and

${\mu }_{t+1}^{\pi }(s^{\mathrm{\prime }}):={\sum }_{s\in S}{\sum }_{a\in A(s)}{\sum }_{\rho \in \mathcal{R}}{\mu }_t^{\pi }(s)\pi (a\mid s)p(s^{\mathrm{\prime }},\rho \mid s,a)\mathrm{.}$

This recurrence defines nonnegative finite-time masses; the result that each ${\mu }_t^{\pi }$ is a probability distribution is established separately.

A finite MDP supplies finite state/action/reward sets, a normalized joint next-state/reward law, and stationary Markov policies as normalized action probabilities.

The finite-time state masses remain probability distributions, and the normalized discounted occupancy has total mass one. ↗

Altman, Constrained Markov Decision Processes, Chapter 2.

Achiam et al., Constrained Policy Optimization, §3.

Let a finite discounted CMDP and a stationary policy $\pi$ be given. The column transition matrix $K_{\pi }$ has entry

$K_{\pi }(s^{\mathrm{\prime }},s):={\sum }_{a\in A(s)}{\sum }_{\rho \in \mathcal{R}}\pi (a\mid s)p(s^{\mathrm{\prime }},\rho \mid s,a),$

so that its column indexed by $s$ gives the next-state distribution from current state $s$. With the state-mass column vectors ${\mu }_t^{\pi }$ from the CMDP definition, the normalized discounted state occupancy is

$d^{\pi }(s):=(1-\gamma ){\sum }_{t=0}^{\mathrm{\infty }}{\gamma }^t{\mu }_t^{\pi }(s)\mathrm{.}$

This normalization is part of the definition; the occupancy is a probability distribution by the separate well-definedness result below.

The finite CMDP specifies the joint next-state/reward masses and the recursively defined state-mass vectors.

Normalized discounted occupancy is a probability distribution ↗: The recurrence yields probability vectors, and multiplying the geometric occupancy sum by $1-\gamma$ gives total mass one.

Achiam et al., Constrained Policy Optimization, supplementary material, Appendix 10.1.1.

Altman, Constrained Markov Decision Processes, Chapter 3 §3.1.

Let a finite discounted CMDP have initial distribution $\mu$, discount $\gamma \in [0,1)$, $m$ bounded transition signals $c_i$, thresholds $b_i$, and finite-time state masses ${\mu }_t^{\pi }$ under a stationary policy $\pi$, as defined in the CMDP model. For any bounded transition signal $g$ on $(s,a,\rho ,s^{\mathrm{\prime }})$, define its expected discounted sum under $\pi$ by

$J_g^{\pi }(\mu ):={\sum }_{t=0}^{\mathrm{\infty }}{\gamma }^t{\sum }_{s\in S}{\sum }_{a\in A(s)}{\sum }_{\rho \in \mathcal{R}}{\sum }_{s^{\mathrm{\prime }}\in S}{\mu }_t^{\pi }(s)\pi (a\mid s)p(s^{\mathrm{\prime }},\rho \mid s,a)g(s,a,\rho ,s^{\mathrm{\prime }})\mathrm{.}$

The expected discounted reward is $J^{\pi }:=J_r^{\pi }(\mu )$ for the immediate reward signal $r(s,a,\rho ,s^{\mathrm{\prime }})=\rho$, and the $i$th expected discounted cost is $J_{c_i}^{\pi }(\mu )$. The policy $\pi$ is feasible for the discounted-cost constraints exactly when $J_{c_i}^{\pi }(\mu )\le b_i$ for every $i\in \{1,\dots ,m\}$. Feasibility constrains these expectations; it does not assert a per-trajectory bound.

A finite CMDP fixes the finite joint transition/reward model, initial distribution, discount, bounded cost signals, and thresholds.

Absolute convergence and tail bound for bounded discounted rewards: Every bounded real signal sequence has an absolutely convergent discounted sum for $0\le \gamma <1$, bounded by its signal bound divided by $1-\gamma$.

The finite-time masses are probability distributions, so each bounded finite-time transition-signal expectation is bounded and the displayed discounted series is well defined. ↗

Altman, Constrained Markov Decision Processes, Chapter 2 §2.2.

Achiam et al., Constrained Policy Optimization, §3.

Let a finite discounted CMDP, a stationary policy $\pi$, its finite-time state-mass vectors ${\mu }_t^{\pi }$, its normalized discounted occupancy $d^{\pi }$, and the expected discounted signal $J_g^{\pi }(\mu )$ be as defined above. Each ${\mu }_t^{\pi }$ is a probability distribution, $d^{\pi }$ is a probability distribution, and for every real $B\ge 0$ and every transition signal $g:\mathcal{X}\to \mathbb{R}$ satisfying $\mathrm{\mid }g(s,a,\rho ,s^{\mathrm{\prime }})\mathrm{\mid }\le B$ for all $(s,a,\rho ,s^{\mathrm{\prime }})\in \mathcal{X}$, the series defining $J_g^{\pi }(\mu )$ converges absolutely and satisfies $\mathrm{\mid }{J}_g^{\pi }(\mu )\mathrm{\mid }\le B\mathrm{/}(1-\gamma )$.

The initial state distribution and recursive finite-time state masses.

The normalized occupancy formula.

The finite-sum formula for expected discounted transition signals.

Absolute convergence and the uniform geometric bound for every bounded signal sequence.

Let a finite discounted CMDP, a stationary policy $\pi$, and a bounded transition signal $g$ be given. For $s\in S$, let ${\delta }_s$ be the initial distribution assigning probability one to $s$. The state value is $V_g^{\pi }(s):=J_g^{\pi }({\delta }_s)$. For $a\in A(s)$, define the action value and advantage by

$Q_g^{\pi }(s,a):={\sum }_{\rho \in \mathcal{R}}{\sum }_{s^{\mathrm{\prime }}\in S}p(s^{\mathrm{\prime }},\rho \mid s,a)(g(s,a,\rho ,s^{\mathrm{\prime }})+\gamma V_g^{\pi }(s^{\mathrm{\prime }})),A_g^{\pi }(s,a):=Q_g^{\pi }(s,a)-V_g^{\pi }(s)\mathrm{.}$

Taking $g=r$ gives reward values and advantages; taking $g=c_i$ gives the value and advantage for the $i$th cost. These quantities are finite because the signal is bounded, $0\le \gamma <1$, and the transition law is normalized.

The finite CMDP and bounded transition signals.

Expected discounted-cost feasibility constraint: The well-defined expected discounted sum $J_g^{\pi }(\mu )$.

Bounded discounted signal sums are absolutely convergent and finite.

Achiam et al., Constrained Policy Optimization, §§3 and 5.3.

Let a finite discounted CMDP and two stationary policies $\pi ,{\pi }^{\mathrm{\prime }}$ be given, with normalized discounted occupancies $d^{\pi },d^{{\pi }^{\mathrm{\prime }}}$. Define

${\mathrm{TV}}_s({\pi }^{\mathrm{\prime }},\pi ):=\frac{1}{2}{\sum }_{a\in A(s)}\mathrm{\mid }{\pi }^{\mathrm{\prime }}(a\mid s)-\pi (a\mid s)\mathrm{\mid }$

and $\mathrm{\parallel }x{\mathrm{\parallel }}_1:={\sum }_{s\in S}\mathrm{\mid }x(s)\mathrm{\mid }$ for a state vector. Then

$\mathrm{\parallel }{d}^{{\pi }^{\mathrm{\prime }}}-d^{\pi }{\mathrm{\parallel }}_1\le \frac{2\gamma }{1-\gamma }{\sum }_{s\in S}{d}^{\pi }(s){\mathrm{TV}}_s({\pi }^{\mathrm{\prime }},\pi )\mathrm{.}$

A finite CMDP has finite states and actions, a normalized joint transition law, and stationary policies.

Normalized discounted state occupancy: The normalized occupancy is $(1-\gamma )$ times the discounted sum of state-mass vectors.

Each state-mass vector and the resulting occupancy are probability distributions.

Achiam et al., Constrained Policy Optimization, supplementary material, Appendix 10.1.

Altman, Constrained Markov Decision Processes, Chapter 3 §3.1.

Let a finite discounted CMDP, a bounded transition signal $g$, a bounded function $f:S\to \mathbb{R}$, and stationary policies $\pi ,{\pi }^{\mathrm{\prime }}$ be given. All sums below over $a,\rho ,s^{\mathrm{\prime }}$ range over $A(s),\mathcal{R},S$, respectively. For a policy $\sigma$ define

${\delta }_f^g(s,a,\rho ,s^{\mathrm{\prime }}):=g(s,a,\rho ,s^{\mathrm{\prime }})+\gamma f(s^{\mathrm{\prime }})-f(s),{\bar{\delta }}_f^{g,\sigma }(s):={\sum }_{a,\rho ,s^{\mathrm{\prime }}}\sigma (a\mid s)p(s^{\mathrm{\prime }},\rho \mid s,a){\delta }_f^g(s,a,\rho ,s^{\mathrm{\prime }})\mathrm{.}$

Put

$L_{\pi ,f}^g({\pi }^{\mathrm{\prime }}):={\sum }_s{d}^{\pi }(s)({\bar{\delta }}_f^{g,{\pi }^{\mathrm{\prime }}}(s)-{\bar{\delta }}_f^{g,\pi }(s))\mathrm{.}$

Then the exact performance-difference identity is

$J_g^{{\pi }^{\mathrm{\prime }}}(\mu )-J_g^{\pi }(\mu )=\frac{L_{\pi ,f}^g({\pi }^{\mathrm{\prime }})}{1-\gamma }+\frac{1}{1-\gamma }{\sum }_s(d^{{\pi }^{\mathrm{\prime }}}(s)-d^{\pi }(s)){\bar{\delta }}_f^{g,{\pi }^{\mathrm{\prime }}}(s)\mathrm{.}$

Finite CMDP data and finite-time state masses.

Expected discounted-cost feasibility constraint: The expected discounted transition-signal sum $J_g^{\pi }(\mu )$.

Normalized discounted state occupancy: The normalized discounted state occupancy $d^{\pi }$.

Probability mass and boundedness facts used to justify the discounted series.

Achiam et al., Constrained Policy Optimization, supplementary material, Appendix 10.1.

Let a finite discounted CMDP, a bounded transition signal $g$, a bounded function $f:S\to \mathbb{R}$, and stationary policies $\pi ,{\pi }^{\mathrm{\prime }}$ be given. For each state define

${\bar{\delta }}_f^{g,\sigma }(s):={\sum }_{a\in A(s)}{\sum }_{\rho \in \mathcal{R}}{\sum }_{s^{\mathrm{\prime }}\in S}\sigma (a\mid s)p(s^{\mathrm{\prime }},\rho \mid s,a)(g(s,a,\rho ,s^{\mathrm{\prime }})+\gamma f(s^{\mathrm{\prime }})-f(s)),\sigma \in \{\pi ,{\pi }^{\mathrm{\prime }}\}\mathrm{.}$

Set ${ϵ}_f^g({\pi }^{\mathrm{\prime }}):={\max }_{s\in S}\mathrm{\mid }{\bar{\delta }}_f^{g,{\pi }^{\mathrm{\prime }}}(s)\mathrm{\mid }$ and

$L_{\pi ,f}^g({\pi }^{\mathrm{\prime }}):={\sum }_{s\in S}{d}^{\pi }(s)({\bar{\delta }}_f^{g,{\pi }^{\mathrm{\prime }}}(s)-{\bar{\delta }}_f^{g,\pi }(s)),D_{\pi ,f}^{\pm ,g}({\pi }^{\mathrm{\prime }}):=\frac{L_{\pi ,f}^g({\pi }^{\mathrm{\prime }})}{1-\gamma }\pm \frac{2\gamma {ϵ}_f^g({\pi }^{\mathrm{\prime }})}{(1-\gamma {)}^2}{\sum }_{s\in S}{d}^{\pi }(s){\mathrm{TV}}_s({\pi }^{\mathrm{\prime }},\pi ),$

where ${\mathrm{TV}}_s({\pi }^{\mathrm{\prime }},\pi ):=\frac{1}{2}{\sum }_{a\in A(s)}\mathrm{\mid }{\pi }^{\mathrm{\prime }}(a\mid s)-\pi (a\mid s)\mathrm{\mid }$. Then

$D_{\pi ,f}^{-,g}({\pi }^{\mathrm{\prime }})\le J_g^{{\pi }^{\mathrm{\prime }}}(\mu )-J_g^{\pi }(\mu )\le D_{\pi ,f}^{+,g}({\pi }^{\mathrm{\prime }})\mathrm{.}$

These total-variation bounds are choice-free. Under the additional Axiom of Choice, define

${\bar{D}}_{\mathrm{K}\mathrm{L}}^{\pi }({\pi }^{\mathrm{\prime }}\mathrm{\parallel }\pi ):={\sum }_{s:d^{\pi }(s)>0}{d}^{\pi }(s)D_{\mathrm{K}\mathrm{L}}({\pi }^{\mathrm{\prime }}(\cdot \mid s)\mathrm{\parallel }\pi (\cdot \mid s)),$

using natural logarithms and $+\mathrm{\infty }$ when the first action law is not absolutely continuous with respect to the second. The same inequalities hold after replacing ${\sum }_s{d}^{\pi }(s){\mathrm{TV}}_s({\pi }^{\mathrm{\prime }},\pi )$ by $\sqrt{{\bar{D}}_{\mathrm{K}\mathrm{L}}^{\pi }({\pi }^{\mathrm{\prime }}\mathrm{\parallel }\pi )\mathrm{/}2}$; when the average KL is infinite, these KL-form inequalities are interpreted as the trivial extended bounds $-\mathrm{\infty }\le J_g^{{\pi }^{\mathrm{\prime }}}(\mu )-J_g^{\pi }(\mu )\le +\mathrm{\infty }$. Taking $g=r$ gives the reward bound, and taking $g=c_i$ gives the corresponding bound for each discounted cost.

The finite transition model, bounded signals, initial law, and discount.

Expected discounted-cost feasibility constraint: The expected discounted signal objective $J_g^{\pi }(\mu )$.

Normalized discounted state occupancy: The normalized occupancy $d^{\pi }$.

The AC-conditional finite-action Pinsker/Jensen bound.

The resolvent estimate for the change of discounted state occupancy.

Performance-difference identity for an arbitrary bounded baseline: The exact performance-difference identity for arbitrary bounded $f$.

Achiam et al., Constrained Policy Optimization, §5.1.

Achiam et al., Constrained Policy Optimization, supplementary material, Appendix 10.1.

Assume the Axiom of Choice for the theoretical average-KL comparison, and let a finite discounted CMDP have cost signals $c_1,\dots ,c_m$ with thresholds $b_1,\dots ,b_m$. Let $\theta \mapsto {\pi }_{\theta }$ be a stationary policy family on an open set $U\subseteq {\mathbb{R}}^d$ with fixed common support, where $d\ge 1$ and the current parameter ${\theta }_k$ lies in $U$. Assume its policy coordinates are twice continuously differentiable on a neighborhood of ${\theta }_k$. Choose a trust radius $\delta >0$, a backtracking factor $\beta \in (0,1)$, and a finite backtracking budget $L\ge 0$. At iteration $k$, the finite data batch consists of $N\ge 1$ rows $(s_j,a_j,{\omega }_j,{\widehat{A}}_j^r,{\widehat{A}}_{1,j}^c,\dots ,{\widehat{A}}_{m,j}^c)$ from trajectories generated in the CMDP under the current policy ${\pi }_{{\theta }_k}$, where ${\omega }_j\ge 0$, ${\sum }_j{\omega }_j=1$, and ${\pi }_{{\theta }_k}(a_j\mid s_j)>0$. The advantage estimates are real numbers held fixed during the update, and the batch also includes real baseline-cost estimates ${\widehat{J}}_{i,k}$. The weights and estimates may come from any fixed rollout or critic estimator; this procedure assumes no accuracy property for them. It specifies the exact finite-data trust-region subproblem and line search; implementations that approximate the subproblem solve are discussed separately.

For every $\theta \in U$, define the finite sample surrogates

${\widehat{L}}_r(\theta ):={\sum }_{j=1}^N{\omega }_j(\frac{{\pi }_{\theta }(a_j\mid s_j)}{{\pi }_{{\theta }_k}(a_j\mid s_j)}-1){\widehat{A}}_j^r,{\widehat{L}}_i^c(\theta ):={\sum }_{j=1}^N{\omega }_j(\frac{{\pi }_{\theta }(a_j\mid s_j)}{{\pi }_{{\theta }_k}(a_j\mid s_j)}-1){\widehat{A}}_{i,j}^c\mathrm{.}$

and $\widehat{K}(\theta ):={\sum }_j{\omega }_j{D}_{\mathrm{K}\mathrm{L}}({\pi }_{\theta }(\cdot \mid s_j)\mathrm{\parallel }{\pi }_{{\theta }_k}(\cdot \mid s_j))$. Put $g=\mathrm{\nabla }{\widehat{L}}_r({\theta }_k)$, $u_i=(1-\gamma {)}^{-1}\mathrm{\nabla }{\widehat{L}}_i^c({\theta }_k)$, $H={\mathrm{\nabla }}^2\widehat{K}({\theta }_k)$, and $q_i={\widehat{J}}_{i,k}-b_i$. The update procedure is:

1. If $H$ is not symmetric, or if some nonzero $x\in {\mathbb{R}}^d$ satisfies $x^{T}Hx\le 0$, return no-step. Otherwise form the local quadratic program

   ${\max }_{x\in {\mathbb{R}}^d}{g}^{T}x\text{subject to}{q}_i+u_i^{T}x\le 0(i=1,\dots ,m),\frac{1}{2}{x}^{T}Hx\le \delta \mathrm{.}$

2. If this program is feasible, let $x^{\ast }$ be its lexicographically least global maximizer. The feasible set is a closed subset of the compact ellipsoid, so the maximizer set is nonempty and compact. Minimize the first coordinate on that set, restrict to its nonempty compact minimizers, and repeat for each coordinate; the resulting point is the lexicographically least maximizer. If the program is infeasible and $m=1$, compute $v=H^{-1}{u}_1$. If $u_1=0$, return no-step, since the linearized cost cannot be reduced. Otherwise $u_1^{T}v>0$ by positive definiteness, and use the cost-recovery proposal $x^{\ast }=-\sqrt{2\delta \mathrm{/}(u_1^{T}v)}v$. If the program is infeasible and $m>1$, return no-step.

3. For $j=0,\dots ,L$, set ${\theta }_j={\theta }_k+{\beta }^j{x}^{\ast }$. Accept the first ${\theta }_j$ in the policy family's parameter domain for which $\widehat{K}({\theta }_j)\le \delta$ and every sample cost estimate ${\widehat{J}}_{i,k}+(1-\gamma {)}^{-1}{\widehat{L}}_i^c({\theta }_j)$ is at most $b_i$. If no candidate passes this sample check, return no-step; otherwise output the accepted parameter as ${\theta }_{k+1}$.

For finite constants $D_i\ge 0$, optional nonnegative bounded transition signals ${\mathrm{\Delta }}_i:\mathcal{X}\to [0,D_i]$ may be included in the supplied cost-advantage and baseline estimates by estimating the shaped costs $c_i+{\mathrm{\Delta }}_i$. The exact theorem concerns exact policies and expectations; the line search above checks only the supplied sample estimates.

Every family of nonempty sets has a choice function; AC is required for the theorem's KL branch.

The finite CMDP model and bounded transition signals.

The expected discounted cost and its threshold.

The value and advantage quantities estimated by the supplied critic.

A differentiable stationary policy family with fixed common support and score vectors.

The Hessian matrix is the matrix of second partial derivatives of a scalar function on an open Euclidean domain.

Directional KL uses natural logarithms and is infinite when the first action law is not absolutely continuous with respect to the second.

The state distribution targeted by the discounted sample weights.

The exact policy-return bound that motivates the trust-region constraint; its KL branch assumes AC.

Achiam et al., Constrained Policy Optimization, §5.3 and §§6.1–6.3.

Under the inputs and assumptions of the sample-based constrained policy optimization update, with finite parameter dimension $d$ and nonnegative integer backtracking budget $L$, the update has a unique mathematical output, either no-step or an accepted parameter. Its proposals satisfy these properties.

If its matrix $H$ is symmetric positive definite and its local quadratic program is feasible, the program has a nonempty compact global-maximizer set and a unique lexicographically least global maximizer. This is the proposal selected by the update and satisfies every linearized cost constraint and the quadratic trust-region constraint.

If the program is infeasible with one cost and $u_1\mathrm{\ne }0$, the inverse used by the update exists, $a=u_1^T{H}^{-1}{u}_1>0$, and its recovery proposal is $x^{\ast }=-\sqrt{2\delta \mathrm{/}a}{H}^{-1}{u}_1\mathrm{.}$ It is the unique minimizer of $u_1^{T}x$ on $\{x:x^{T}Hx\mathrm{/}2\le \delta \}$, satisfies $(x^{\ast }{)}^{T}H{x}^{\ast }\mathrm{/}2=\delta$, and decreases the linearized cost by $\sqrt{2\delta a}$. It need not make the infeasible cost constraint feasible. The non-positive-definite, zero-recovery-gradient and multiple-cost infeasible branches return no-step as specified.

Once the specified exact subproblem decisions and operations have been performed, backtracking terminates after at most $L+1$ candidate tests. It returns the first passing candidate, which belongs to the parameter domain and satisfies the empirical KL and all empirical cost tests, or returns no-step if none passes. These are well-definedness and finite-search properties of the exact mathematical update. They do not bound the cost of exact feasibility/optimization operations or certify the true expected costs, exact population KL, policy improvement, or convergence of sampled iterates.

Sample-based constrained policy optimization update

Achiam et al., Constrained Policy Optimization, Sections 6.1–6.3