Strict-sense constrained Markov decision processes

We introduce the strict-sense constrained Markov decision processes by extending the ideas of classical constrained Markov decision process and the safety control of discrete event systems. In our setting a convex set of constraint specified by a set of linear inequalities is given for the system´s state probability distribution. A distribution is safe if it is in the set of constraint. A policy is safe if it makes a state distribution that is initially safe remain safe after the process starts. Under the assumption of complete state observation, we first identify the optimal safe policy that minimizes the pre-specified cost function. Then, for a given safe policy, we provide an iterative algorithm for computing the maximum set of safe initial distributions corresponding to the policy. Under the assumption that the policy induces a unique limiting distribution in the interior of set of constraint, we give an explicit upper bound on the number of steps needed for the termination of the algorithm. In particular, we give the explicit expression for the maximum set of safe initial distributions in the two-state system, for which we show that at most one iteration is needed in running the algorithm