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

DOI10.1016/J.ORL.2006.06.005zbMATH Open1169.90478OpenAlexW2022585556MaRDI QIDQ2467470FDOQ2467470

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

Recommendations

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

zbMATH Keywords

Markov decision processesaverage costunichain condition

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40)

Cites Work

• Title not available (Why is that?)
• Dynamic programming and optimal control. Vol. 2.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Markov Reward Models and Markov Decision Processes in Discrete and Continuous Time: Performance Evaluation and Optimization
• Derman's book as inspiration: some results on LP for MDPs
• 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)