Discounted Cost Markov Decision Processes on Borel Spaces: The Linear Programming Formulation

This paper is concerned with the linear programming formulation of Markov decision processes (or stochastic dynamic programs) with Borel state and action spaces and the discounted cost criterion. The one-stage cost function may be unbounded. A linear program and its dual are introduced, for which is shown the absence of a duality gap and that a strong duality condition holds. These results are used to determine the optimal value and the existence of an optimal policy for the discounted cost problem.