Linear Programming formulation of Markov Decision Problems in countable state space: The multichain

The authors present a Linear Programming formulation of Markov Decision Problems with countable state and action spaces and no unichain assumption. This is an extension of the Hordijk and Kallenberg formulation in finite state and action spaces. The authors provide sufficient conditions for both existence of optimal solutions to the primal LP program and absence of duality gap. Then, existence of a (possibly randomized) average optimal policy is also guaranteed. Existence of a stationary average optimal deterministic policy is also investigated.