the policy and the MDP. If a policy is exponentially larger than the MDP, this means that the MDP is only a logarithmic part of the instance.

Formally, the problem of policy evaluation is: given an MDP, **a policy, and a number** k, decide whether the expected reward of the policy is greater than k**. This is a counting problem, as it amounts to summing up the evaluations that result from computing a polynomial**
function over a set of propositional models. Not surprisingly, it is in PP.

Theorem 4 Given a succinct MDP M = hV, s0, A, t, ri, a horizon T **in unary notation, a**
succinct policy P (either stationary or history dependent), and a number k**, deciding whether** the policy P has expected reward greater than k **is in** PP.

Proof. The expected reward of the policy is a weighted sum of rewards **of states. Let us**
consider the sequence of states s0, s1, . . . , sd**. The probability of this sequence of being the**
actual history can be computed as follows: for each pair of consecutive states si, si+1 **there**
is a factor given by the probability t(si, si+1, a), where a **is the unique action that is chosen**
by the policy in state si (or, when the history is s0, . . . , si**.) Multiplying all these factors,**
the result is the probability of the whole sequence s0, s1, . . . , sd **to be the actual history**
up to point d. Since P(si) denotes the output of the circuit P when si**is its input, then** P(si) represents the action that is executed in the state si**. As a result, the probability of**
s0, s1, . . . , sd **of being the actual sequence of states is as follows:**

$$H(s_{0},s_{1},\ldots,s_{d})=\prod_{i=0,\ldots,d-1}t(s_{i},s_{i+1},P(s_{i}))$$

The same probability for history-dependent policies can be **determined in the same way,**
but P(si) is replaced by P(s0, . . . , si). Given a specific sequence s0, . . . , sd**, it is possible**
to determine H(s0, . . . , sd**) in time polynomial in the size of the sequence plus that of the**
MDP.

The expected reward of the policy can be calculated as the sum **of the expected reward**
of each state sd multiplied by the probability of a sequence ending with sd **being the actual**
history. This sum can be expressed as follows:

$$R(P)=r(s_{0})+\sum_{s_{1},\ldots,s_{d}\in{\mathcal{S}}}^{d=1,\ldots,T}H(s_{0},\ldots,s_{d})\cdot r(s_{d}).$$

The number d ranges from 1 to T **to take into account all sequences up to length**
T**. This is how "intermediate" states of the sequences are dealt with: for each sequence**
s0, . . . , si, . . . , sd, the sum above contains a term for each subsequence s0, . . . , si **as well.**
Roughly speaking, the membership in PP is due to the fact that **the expected reward of**
a policy is the result of a sum of an exponential number of terms, and each of those terms can be determined in polynomial time in a uniform manner. Formally, what is proved is that the problem can be expressed as the sum of terms V (M), where V **is a polynomial** function and M ranges over all propositional interpretations over a given **alphabet. To**
complete the proof, therefore, what is needed is to encode each possible sequence s0**, . . . , s**d as a propositional model, with the constraint that H(s0, . . . , sd) · r(sd**) can be determined**
from this model in polynomial time.