NP-hardness of checking the unichain condition in average cost MDPs

DOI10.1016/J.ORL.2006.06.005MaRDI QIDQ2467470zbMATHOpenAlexFDO

Authors John N. Tsitsiklis

Publication date 21 January 2008

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

Full work available at URL http://hdl.handle.net/1721.1/69999

zbMATH Keywords

Markov decision processesaverage costunichain condition

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40)

Recommendations

• On polynomial cases of the unichain classification problem for Markov decision processes
• The Complexity of Markov Decision Processes
• scientific article; zbMATH DE number 4102842
• scientific article; zbMATH DE number 2189770
• A condition for strong average optimality of MDP with non-uniformly bounded costs

Cites work

• scientific article; zbMATH DE number 1348599 (Why is no real title available?)
• scientific article; zbMATH DE number 475591 (Why is no real title available?)
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 2189770 (Why is no real title available?)
• Dynamic programming and optimal control. Vol. 2.
• On the Empirical State-Action Frequencies in Markov Decision Processes Under General Policies

Cited in

(4)

• On polynomial cases of the unichain classification problem for Markov decision processes
• Derman's book as inspiration: some results on LP for MDPs
• Markov reward models and Markov decision processes in discrete and continuous time: performance evaluation and optimization
• On the reduction of total-cost and average-cost MDPs to discounted mdps

This page was built for publication: NP-hardness of checking the unichain condition in average cost MDPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467470)