Theorem 6 Given a succinct MDP, a horizon in unary notation, a size bound z **in unary**
notation, and a reward bound k**, checking the existence of a succinct policy of size bounded**
by z and expected reward greater than or equal to k is NPPP**-complete.**
Proof. Membership is easy to prove: guess a circuit of size z **representing a policy and check**
whether its expected reward is greater than k. Note that z **being in unary is essential.**
Hardness is proved by reduction from e-majsat**, a problem defined by Littman et al.**
(1998) as follows: given a formula Q over variables X ∪ Y **, decide whether there exists a** truth assignment over X **such that at least half of the interpretations extending it satisfy**
Q. This problem is NPPP**-complete (Littman et al., 1998).**
Given an instance of e-majsat**, its corresponding MDP is defined as follows: states**
represent sequences of literals over X ∪ Y (we assume, w.l.o.g., that |X| = |Y | = n**.) There**
is an action aifor each variable in Y . Each ai adds the literal yi or ¬yi **to the sequence**
representing the current state with the same probability. Each variable xi**is associated with** the actions bi and ci, which add xi and ¬xi **to the state, respectively. The reward of a state**
is 1 only if it represents a sequence of the form [¬]x1, [¬]x2, . . . , [¬]yn **and all its literals**
satisfy Q**, that is, the sequence is a complete interpretation that satisfies** Q.

A policy with expected reward greater than 0 can only be made of a sequence whose i-th element (1 ≤ i ≤ n) is either bi or ci, and its i + n-th element (1 ≤ i ≤ n**) is** ai.

The expected reward of this policy over a horizon T = 2n **is 1 only if at least half of the**
completions of the model defined by the actions bi and cj satisfy Q**. Therefore, the MDP**
has a policy of reward 1 if and only if Q **is in** e-majsat.

This result can be used for an alternative proof of the claim that not all MDPs admit polynomially sized optimal succinct policies. This proof is interesting because it employs a different technique, and because it is conditioned differently than the previous one.

Theorem 7 **If all MDPs have optimal succinct policies (either stationary or history dependent) of size polynomial in the sum of the size of the MDP and the length of the horizon**
then **PSPACE** ⊆ NPPP.

Proof. **Checking the existence of a policy of a given expected reward, regardless of its**
size, is PSPACE-hard (Mundhenk et al., 2000). On the other hand, if all policies can be represented in polynomial space, this problem coincides with that of checking the existence of a policy with a given bound on its size, and the latter problem is in NPPP.

Theorem 7 is proved using the fact that the problems of evaluating a policy of a given size and deciding the existence of a policy have different complexity characterizations. The same technique has been used by Papadimitriou and Tsitsiklis (1987) for the case of POMDPs in the explicit representation.

Precisely, the proof is composed of the following sequence of statements:

1. Evaluating the expected reward of a succinct policy is C1-complete, where C1 **is a**
complexity class; 2. Deciding the existence of a policy (with no size bound) with a given expected reward is C2-complete, where C2 **is a complexity class;**