On Linear Programming for Constrained and Unconstrained Average-Cost Markov Decision Processes with Countable Action Spaces and Strictly Unbounded Costs

Abstract

We consider the linear programming approach for constrained and unconstrained Markov decision processes (MDPs) under the long-run average cost criterion, where the class of MDPs in our study have Borel state spaces and discrete countable action spaces. Under a strict unboundedness condition on the one-stage costs and a recently introduced majorization condition on the state transition stochastic kernel, we study infinite-dimensional linear programs for the average-cost MDPs and prove the absence of a duality gap and other optimality results. Our results do not require a lower-semicontinuous MDP model. Thus, they can be applied to countable action space MDPs where the dynamics and one-stage costs are discontinuous in the state variable. Our proofs make use of the continuity property of Borel measurable functions asserted by Lusin's theorem.

33 pages; to appear in Mathematics of Operations Research (this is the accepted version before the galley proof)

References in corpus (3)

• Average Cost Optimality Inequality for Markov Decision Processes with Borel Spaces and Universally Measurable Policies
• On the Minimum Pair Approach for Average-Cost Markov Decision Processes with Countable Discrete Action Spaces and Strictly Unbounded Costs
• On Markov Decision Processes with Borel Spaces and an Average Cost Criterion

Cited by in corpus (2)

• On the Minimum Pair Approach for Average-Cost Markov Decision Processes with Countable Discrete Action Spaces and Strictly Unbounded Costs
• Average cost optimal control under weak ergodicity hypotheses: Relative value iterations