Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems

DOI10.1016/j.orl.2013.02.002zbMath1286.90162OpenAlexW2097475492MaRDI QIDQ2450614

Jefferson Huang, Eugene A. Feinberg

Publication date: 14 May 2014

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2013.02.002

zbMATH Keywords

Markov decision processsimplex methodlinear programaverage costpolicy iteration algorithmstrongly polynomial

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Markov and semi-Markov decision processes (90C40)

Related Items

Reduction of total-cost and average-cost MDPs with weakly continuous transition probabilities to discounted mdps ⋮ Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming ⋮ Improved bound on the worst case complexity of policy iteration ⋮ On the reduction of total‐cost and average‐cost MDPs to discounted MDPs

Cites Work

• A new polynomial-time algorithm for linear programming
• The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
• A Strongly Polynomial Algorithm for Controlled Queues
• Non-Discounted Denumerable Markovian Decision Models
• Arbitrary State Markovian Decision Processes
• A New Complexity Result on Solving the Markov Decision Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems