The LP approach in average reward MDPs with multiple cost constraints: The countable state case

The objective of this paper is to study the linear programming for countable state average reward Markov decision processes with multiple cost constraints. A corresponding linear programming and its dual are formulated and their solvability and absence of a duality gap are proved under some reasonable conditions. Also, the ergodic assumption leads to the existence of a constrained optimal stationary policy.