Denumerable constrained Markov decision processes and finite approximations

The purpose of this paper is two fold. First to establish the theory of discounted constrained Markov decision processes with a countable state and action spaces with general multi-chain structure. Second, to introduce finite approximation methods. The paper defines the occupation measures and obtains properties of the set of all achievable occupation measures under the different admissible policies. It establishes the optimality of stationary policies for the constrained control problem, and obtains and LP with a countable number of decision variables through which stationary optimal policies are computed. Since for such an LP one cannot expect to find an optimal solution in a finite number of operations, the paper presents two schemes for finite approximations and establishes the convergence of optimal values and policies for both the discounted and the expected average cost, with unbounded cost. Sometimes it turns out to be easier to solve the problem with infinite state space than the problem with finite yet large state space. Based on the optimal policy for the problem with infinite state space, the paper constructs policies which are almost optimal for the problem with truncated state space. This method is applied to obtain an ∈-optimal policy for a problem of optimal priority assignment under constraints for a system of K finite queues.