The analysis with a bound on size has been initially done assuming that the bound is polynomial in the size of the instance. This is justified by **the fact that the resulting**
policy should not be too much larger than the MDP. However, a moderate increase may be tolerated. Therefore, we considered the same problem removing the assumption of polynomiality of the bound. This is a new problem, but is PSPACE-hard just as the problem with no bound on size is. However, it is not EXPTIME-hard unless P 6**= PSPACE.**
This result shows that proving such hardness result is at least as hard as proving a conjecture that has been open for more than twenty years.

Let us now discuss how the results presented in this paper relate to similar ones in the literature. As already remarked in the Introduction, the complexity of problems related to finding a policy does not necessarily imply that policies cannot be compactly represented.

Namely, even a result of undecidability does not forbid compactness of policies. Therefore, our result is not implied by previous complexity results in the literature. On the other hand, a result of non-polynomiality of the size of policies of POMDPs already appeared in the paper by Papadimitriou and Tsitsiklis (1987). Namely, they proved that, unless PSPACE = Σp 2
, there is no algorithm A and mapping µ **from POMDPs in explicit form to**
strings of polynomial length that can be used by A **to compute the optimal action. This** result basically proves the non-polynomiality of policies. However, it cannot imply ours, as it holds for POMDPs in the explicit representation with only **non-positive rewards; the same**
problem that is PSPACE-hard in their formalization is polynomial in ours (Mundhenk et al., 2000). More precisely, the two results cannot be derived from each other. Some related results in the literature are about the "non-representability" (as opposite to the "compactrepresentability" studied in this paper): Littman (1997) has shown that (infinite horizon)
plan existence is EXPTIME-complete, while Littman et al. (1998) have shown that the same problem restricted to looping plans is PSPACE-complete: as a result, infinite-horizon policies cannot be represented at all as looping plans unless EXPTIME=PSPACE.

During the review period of this paper, a different proof of the impossibility of representing the optimal policies of all MDPs in polynomial space **has been published (Allender,**
Arora, Kearns, Moore, & Russell, 2002). This new proof improves over the ones presented in this paper and in its conference version (Liberatore, 2002) in two ways: first, the condition under which the new result holds is PSPACE 6⊆ P/poly instead of NP 6⊆ P/**poly and**
PSPACE 6⊆ NPPP**; second, the proof holds even for approximately optimal policies. The**
other differences (the new proof is for the infinite horizon with a discount factor, the reward function is linear, two-levels Bayes nets are used instead of circuits) are inessential, i.e., the proofs can be modified in such a way they are not affected by these other differences. The current paper also contains results on the problem with a bound on the policy or the value function.

Let us now consider the other complexity results about MDPs in the literature. The problem of deciding whether a succinct MDP with a horizon in unary notation has a policy of a given reward is PSPACE-hard, and is PSPACE-complete **for history-dependent**
policies. The same problem with a bound in unary notation on the size of the policy is NPPP-complete. This class contains the class PPP, which in turn contains the whole polynomial hierarchy. Therefore, a problem that is NPPP**-complete is hard for any class of the**