The Complexity of Markov Decision Processes II: The Optimal Average Cost of a Deterministic Process Is the Least Mean Cost of a Cycle Reachable from the Initial StateResearch Paper
A Markov decision process describes repeated choices whose costs and subsequent states depend on the current state. Such models are used when a decision affects both today's expense and the options available tomorrow. Papadimitriou and Tsitsiklis studied how the computational difficulty of finding an optimal policy changes between stochastic and…