This result is new for MDPs in succinct form; in particular, the hardness of finding an optimal policy does not imply anything about the policy size. Indeed, even in those cases in which finding an optimal policy is undecidable (Madani, Hanks, & Condon, 1999), the policy itself may be very short. Many hard problems, even some undecidable ones, are known to have very short solutions: for example, the solution of the halting problem is a single bit, but finding it is undecidable. Therefore, the impossibility **of representing the solutions of a** problem in polynomial space does not follow from the complexity of the problem.

Given that optimal policies cannot always be represented in **space polynomial in the**
size of the MDP, a reasonable request is the best possible policy that can be represented within a given space bound (Section 5). We show that bounding **the size of policies simplifies the policy existence problem. Bounding the size of the succinct representation of**
the value function (the function giving the expected reward **of the states) further simplifies**
the problem (Section 6). This second bound is intended to shed light on the complexity of algorithms that work by estimating the expected reward of each state, such as the value iteration algorithm (Littman et al., 1995; Cassandra et al., 1997; Zhang & Zhang, 2001). We complete the analysis (Section 7) by considering the problem of finding policies of a given size and reward, when the size can be exponentially larger than the MDP. Implications and discussions of the results of this paper are given in the last **section (Section 8).**

## 2. Markov Decision Processes

Markov Decision Processes formalize problems of planning in probabilistic domains. Their components are: a set of states, a set of probabilistic actions, and a function that evaluates states according to a notion of goodness (reward function).

Formally, an MDP is a 5-tuple M = hS, s0, A, t, ri, where: S is a set of states, s0 **is a**
distinguished state (the initial state), A is a set of actions, t **is a function representing the**
effects of the actions, and r **is a function giving the reward of the states.**
The effects of the actions are not known for sure, but only according to a probability distribution. Therefore, the effects of actions cannot be represented using a function that maps a state into another state, given a specific action. The function t **is instead a function**
from actions and pairs of states to numbers in the interval [0, **1]. Such a function represents**
the probability of transitions: t(s1, s2, a) = p **means that the result of executing the action**
a in the state s1 is the state s2 with probability p**. The reward function is a measure of how**
much a state matches our goals. Formally, it is a function from states to integer numbers.

MDPs are assumed to be represented in a succinct form. Namely, the states are assumed to be represented by tuples of Boolean variables (state variables), i.e., the set of states is the set of propositional interpretations over this set of variables. The functions t and r are represented by Boolean circuits. While other representations are more commonly used in practice (e.g., probabilistic STRIPS **operators, two-stage Bayes network, etc.) Boolean**
circuits have the advantage of being able to encode exactly all polynomial-time computable functions. This fact makes them very suitable for a computational analysis: indeed, if a transition or reward function is polynomial, then it can be encoded by a polynomial-size circuit without having to show the details of the encoding (Mundhenk et al., 2000; Boutilier et al., 1999). In order to encode some of the polynomial-time **functions, on the other hand,**