The Complexity of Markov Decision Processes I: A Boolean Circuit Is True Iff Its Finite-Horizon Markov Decision Process Has Optimal Expected Cost ZeroResearch Paper
Markov decision processes are the standard model of sequential decision making under uncertainty in operations research, control and artificial intelligence. Their finite-horizon, discounted and average-cost versions are all solvable in polynomial time, by dynamic programming or linear programming. Papadimitriou and Tsitsiklis (The Complexity of Markov…