Here \unlikely" means \unless some complexity classes collapse," where the collapses considered are P NP, P PSPACE, or P EXP. Until or unless these collapses are shown to hold, any control-policy designer must choose between such performance guarantees and ecient computation. In this work, we show that uncertainty breeds uncertainty: In a controlled stochastic system with uncertainty (as modeled by a partially observable Markov decision process, for example), plans can be obtained eciently or with quality guarantees, but rarely both. Planning over stochastic domains with uncertainty is hard (in some cases PSPACEhard or even undecidable, see Papadimitriou & Tsitsiklis, 1987; Madani, Hanks, & Condon, 1999). Given that it is hard to nd an optimal plan or policy, it is natural to try to nd one that is \good enough". In the best of all possible worlds, this would mean having an algorithm that is guaranteed to be fast and to produce a policy that is reasonably close to the optimal policy.

We show that for several variations of partially observable Markov decision processes, polynomial-time algorithms for finding control policies are unlikely to or simply don't have guarantees of finding policies within a constant factor or a constant summand of optimal. Here ``unlikely'' means ``unless some complexity classes collapse,'' where the collapses considered are P=NP, P=PSPACE, or P=EXP. Until or unless these collapses are shown to hold, any control-policy designer must choose between such performance guarantees and efficient computation.