3. If any policy could be succinctly represented in space polynomial in the size of the MDP and the value of the horizon, the second problem could be solved by guessing a policy and then evaluating it; since the policy to guess has size polynomial in the size of the instance of B**, then C**2 ⊆ NPC1.
What makes the proof worthy is the (probable) falsity of the conclusion C2 ⊆ NPC1.

In other words, the same proof can be applied to prove that a given data structure is not always polynomially large if:
1. there is a problem A that is C1**-complete;**

2. there is a problem B that is C2**-complete;**
3. problem B **can be expressed as: "there exists a data structure satisfying problem** A".

This proof schema is simply the generalization of the one above: the data structure is the succinct policy; the first problem is that of evaluating a succinct policy; the second problem is that of deciding the existence of a policy giving a given expected reward. By definition, an instance satisfying B implies the existence of a data structure satisfying A**. If it is possible** to replace "the existence of a data structure" with "the existence of a polynomial-size data structure" in this sentence, then C2 ⊆ NPC1, as B **can be solved by guessing that data** structure and then checking whether A **is satisfied or not. If the conclusion C**2 ⊆ NPC1 is false, then there are instances satisfying B **that are not related to any data structure** satisfying A **that have size polynomial in the size of the instance of** B.

## 6. Bounding The Value Function

Bounding the policy size is motivated by the fact that we are only interested in policies that can actually be stored: a policy can be used only if its size is less than or equal to the available storage space. In this section, a similar constraint is considered, motivated by how some algorithms for MDPs work. Namely, programs based on the **popular value iteration**
algorithm (Littman et al., 1995; Cassandra et al., 1997; Koller & Parr, 1999; Zhang & Zhang, 2001) work by finding the value function, which is the function giving the expected reward that can be obtained from each state by executing the actions according to a given policy.

Definition 5 The value function E of an MDP M = hS, s0, A, t, ri with horizon T and policy P is the function that gives the expected reward of a state s at i **steps before the**
horizon:

$$\left\{\begin{array}{l l}{r(s)}&{{\mathrm{if~}}i=0}\\ {r(s)+\sum_{s^{\prime}\in{\mathcal{S}}}t(s,s^{\prime},P(s))\cdot E(s^{\prime},i-1)}&{{\mathrm{otherwise.}}}\end{array}\right.$$
$$E(s,i)=$$

A similar definition can be given for history-dependent policies by including the history in the arguments of the value function and of the policy:

$r(s_{j})$ if $i=0$; $r(s_{j})+\sum_{s^{\prime}\in\mathcal{S}}t(s_{j},s^{\prime},P(s_{0},\ldots,s_{j}))\cdot E(s^{\prime},i-1)$ otherwise.  
$$E(s_{0},\ldots,s_{j},i)=\,i$$