Markov decision processes with a constraint on the asymptotic failure rate (Q1610839)

The authors consider a finite-state discrete-time Markov decision process in which the state space is partitioned into two subsets, \(U\) and \(D\). Moves from \(U\) to \(D\) are defined as failures. The paper studies the following problem: in the class of all (randomized) stationary policies with the given asymptotic failure rate, find a policy that minimizes the average costs per unit time under the condition that the failure never happens. The failure rate at time \(n\) is defined as a probability of the failure happens at time \(n\) under the condition that it never happened before. Under the assumption that the transition matrix between the elements of \(U\) is primitive (i.e. all elements of its \(k\)-th power are positive for some integer \(k\)), the authors construct a linear program to solve this problem and discuss an application.