Duality in Markov Decision Problems with Countable Action and State Spaces

The recent literature contains several papers which explore mathematical programming formulations of particular Markov sequential decision problems. Each of these papers deals with finite state and action spaces; thus, the corresponding programming formulations yield dual finite linear programs. In this paper these investigations are extended to include countable action and/or state spaces for finite horison problems. Of particular interest are the duality aspects of the mathematical programming formulations. In addition, employing conditions analogous to fundamental concepts of Haar semi-infinite dual programming, we provide sufficient conditions for the existence of optimal rules for countable action spaces. Guided by the semi-infinite duality theory we explore mathematical programming formulations for two cases: 1) Countable action space and finite state space—the result is a pair of dual semi-infinite programs; and 2) Finite action space and countable state space—we obtain a pair of infinite programs. In the latter case we show that no duality gap occurs and obtain duality results comparable to those of finite linear programming.