DISCOUNTED COST MARKOV DECISION-PROCESSES WITH A CONSTRAINT

We consider a discounted cost Markov decision process with a constrain t. Relating this to a vector-valued Markov decision process, we prove that there exists a constrained optimal randomized semistationary poli cy if there exists at least one policy satisfying a constraint. Moreov er, we present an algorithm by which we can find the constrained optim al randomized semistationary policy, or we can discover that there exi st no policies satisfying a given constraint.