Constrained markov decision processes with compact state and action spaces: the average case (Q4512756)

In a previous paper, the first author investigated the linear programming formulation when the state space is compact and Doeblin's condition holds. M. Kurano (1989) proved the existence of an optimal stationary policy for unconstrained Markov Decision Processes (MDPs) with average cost criterion by extracting a randomized stationary policy from a limit point of empirical processes. Continuing these results, the present paper considers constrained MDPs with average criteria in a similar framework, and associates to them the linear programm (P) and its dual \((\text{P}^*)\). A corresponding Lagrange function is defined and the saddle-point theorem for constrained MDPs is given, relying on the absence of a duality gap between (P) and \((\text{P}^*)\) under compactness assumptions. The saddle-point result is then applied to prove the existence of a constrained optimal pair of initial state distribution and policy, and to obtain its functional characterization under the Doeblin's hypothesis.