polynomial hierarchy. This means that a bound on size in unary notation does not decrease the complexity of the problem much. On the other hand, bounding the size of the value function representation decreases the complexity more, as **the problem is Σ**p 2
-complete.

To conclude, observe that negative results (impossibility **of polynomial policies and**
hardness results) hold for POMDPs, since MDPs are special cases of POMDPs in which everything is observable. Our results, however, only apply **to the case in which both the** POMDP and the policy are in succinct form. The case of explicit representation has been studied by Papadimitriou and Tsitsiklis (1987) (their results are discussed above), and by Mundhenk (1999), who considered the problem of deciding whether a POMDP in explicit form has a c-small policy, given c, where c**-small-ness includes a bound on size depending** on c.

## Acknowledgments

Many thanks to Michael Littman and the anonymous referees for their suggestions. Part of this work appeared in the proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-2002).

## References

Allender, E., Arora, S., Kearns, M., Moore, C., & Russell, A. (2002). A note on the representational incompatability of function approximation **and factored dynamics. In**
Proceedings of the Sixteenth Annual Conference on Neural Information Processing Systems (NIPS 2002).

Beame, P., & Pitassi, T. (1998). Propositional proof complexity: Past, present and future. Tech. rep. 067, Electronic Colloquium on Computational Complexity, http://www.eccc.uni-trier.de/eccc/.

Bellman, R. (1957). Dynamic Programming**. Princeton University Press.**
Boppana, R., & Sipser, M. (1990). The complexity of finite functions. In van Leeuwen, J. (Ed.), Handbook of Theoretical Computer Science**, Vol. A, chap. 14, pp. 757–804.**
Elsevier Science Publishers (North-Holland), Amsterdam.

Boutilier, C., Dean, T., & Hanks, S. (1999). Decision-theoretic planning: Structural assumptions and computational leverage. **Journal of Artificial Intelligence Research**,
11**, 1–94.**
Cadoli, M., Donini, F. M., Liberatore, P., & Schaerf, M. (2002). Preprocessing of intractable problems. Information and Computation, 176**(2), 89–120.**
Cassandra, A., Littman, M., & Zhang, N. (1997). Incremental **pruning: a simple, fast, exact**
method for partially observable Markov decision processes. In **Proceedings of the** Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI'97)**, pp. 54–61.**
Dean, T., & Kanazawa, K. (1989). A model for reasoning about persistence and causation.

Computational Intelligence, 5**(3), 142–150.**