Good policies for partially-observable Markov decision processes are hard to find

Optimal policy computation in finite-horizon Markov decision processes is a classical problem in optimization with lots of pratical applications. For stationary policies and infinite horizon it is known to be solvable in polynomial time by linear programming, whereas for finite-horizon it is a longstanding open problem. We consider this problem for a slightly generalized model, namely partially-observable Markov decision processes (POMDPs). We show that it is NP-complete and that -- unless P = NP -- the optimal policy cannot be polynomial time "-approximated for any " ! 1. A similar result is shown for the average policy. The problem of whether the average performance is positive is shown to be PPcomplete for stationary policies, and PL-complete for time-dependent policies, and of whether the median performance is positive is PP-complete for both types of policies. Furthermore, we systematically investigate the complexity of stationary, time- and history-dependent policy existence pr..