Finite discounted constrained Markov decision process

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.