2. Determine the best action to execute in the initial state only; execute it and observe the resulting state; find the best action in the new state, etc.

Many algorithms for MDPs find a representation of the whole policy, and only a few solve the next-action problem directly (Kearns, Mansour, & **Ng, 2002). Our result formally** proves that the optimal policy cannot be always represented **in polynomial space, unless**
the polynomial hierarchy collapses. This result holds not only for the existing algorithms (such as value iteration or policy iteration), but also for any other algorithm that finds the whole policy all at once.

While the second solution can be theoretically optimal, it involves finding the best action at each time step, and this problem is hard, as proved by Theorem 1. The advantage of the first solution is that the only hard step is to find the optimal policy; finding the action to execute in a state is then polynomial.

The impossibility of always representing the optimal policies in polynomial space raises a new problem: since the size of physical memory is bounded, it is not feasible to search for the best among all policies, but only among those it is possible to store, that is, those bounded in size by the available memory size. The problem of checking whether a succinct MDP has a succinct policy of a given size and reward is proved to be NPPP**-complete, and**
is therefore slightly easier than the same problem without a **bound, which is PSPACEhard (Mundhenk et al., 2000). A similar result has been proved for a slightly different**
formalization of non-deterministic planning by Littman et **al. (1998).**
This complexity result holds only if policies are represented in a particular succinct form, that of circuits giving the next action from the current state and (possibly) the history. Nevertheless, different representations of policies lead to different results. Namely, some algorithms actually find a value function (a function determining the expected reward in each state), which can be considered as a representation of a policy when the states that result from the execution of an action can be listed in polynomial time. In particular, algorithms based on value iteration, when applied with some **form of decomposition, find**
a succinct representation of the value function. Finding a succinct representation of such a function, with a given bound on its size, has been proved easier than finding a succinct policy, when the states that result from the execution of an action can be listed in polynomial time: it is Σp 2
-complete.

This result has two consequences: first, the problem these algorithms solve is in a smaller complexity class than the problem with no bound on size; second, some policies can be represented in polynomial space, while their associated **value functions cannot: there**
exists a trade-off between complexity and ability of finding good solutions. This result is also interesting because it characterizes the complexity of a family of algorithms (those determining the value function in some succinct form) rather than the complexity of a problem. This result is therefore of a kind that is between the efficiency analysis of a single algorithm (e.g., the big-O running time) and the inherent complexity of the problem (e.g., the NP-completeness). As such, it is similar to results about complexity of proof procedures (Beame & Pitassi, 1998; Egly & Tompits, 2001). Our analysis is however limited to the case of exact value functions. Approximation is an interesting open problem. The effects of the various restrictions that can be done on the MDP are interesting open problems as well.