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

2019/05/28 by Huizhen Yu, Yu, Huizhen
Business, Management and Accounting · Decision Sciences · #90C46 #90C48 #93E20. Secondary: 90C05 #Auction Theory and Applications #FOS: Mathematics #Optimization and Control (math.OC) #Primary: 90C40 #Risk and Portfolio Optimization #Supply Chain and Inventory Management

paper · doi:10.48550/arxiv.1905.12095

openalex publication_date 2019/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• On Markov Decision Processes with Borel Spaces and an Average Cost Criterion
• Average-Cost MDPs with Infinite State and Action Sets: New Sufficient Conditions for Optimality Inequalities and Equations
• Average-Cost Optimality Results for Borel-Space Markov Decision Processes with Universally Measurable Policies
• Average-Cost Markov Decision Processes with Weakly Continuous Transition\n Probabilities
• Average optimality for continuous-time Markov decision processes under weak continuity conditions