state. An explicit representation of such a domain is always **of size exponential in the**
number of state variables, as it contains an enumeration of all states. This is why succinct representations are used instead: the states are assumed to **be the possible evaluations**
of a set of Boolean variables; the effects of the actions and the rewards of the states are represented in some succinct form. The succinct representation considered in this paper uses circuits (Mundhenk, Goldsmith, Lusena, & Allender, 2000), **but others exist: decision trees,**
stochastic STRIPS **operators, two-stage Bayes networks, variants of BDDs (Boutilier, Dean,**
& Hanks, 1999; Littman, 1997; Dean & Kanazawa, 1989; Dearden **& Boutilier, 1997; Hansen** & Feng, 2000). Littman (1997) has shown that these representations can be polynomially reduced to each other: the choice of circuits is motivated by **their ease of use.**
Typically, scenarios that can be expressed by MDPs can be informally represented in an amount of space that is on the same scale as the number of variables. For example, the domain in which there are ten coins and the ten actions of tossing them can be represented very succinctly: it is only necessary to specify that action ai tosses coin i **(e.g., the result** of ai**is a state in which the side the coin is on is head or tail with probability 0.5 and all**
other state variables are unchanged.) On the other hand, the **explicit representation of this**
domain contains the set of all 210 **states and the representation of the transition function,**
which in turns requires the specification of the probability of each action a **to change a state** s **into a state** s
′for each pair of the 210 **states and each of the ten actions. As a result, the**
transition function contains a set of 2102 10**10 = 10** · 2 20 **probabilities.**
Succinct representations, on the other hand, follow the intuition that a formal representation should not be too much larger than an informal representation of the same domain.

While explicit representations are always exponential in the number of state variables, an informal representation may be very short: if this is the case, it is often also the case that such an informal description can be converted into a formal succinct one that is not too large.

Explicit and succinct representations lead to very different computational properties: for example, some problems (e.g., checking the existence of a policy of a given expected reward) are PSPACE-hard in the succinct representations (Mundhenk **et al., 2000) but polynomial** in the explicit one (Papadimitriou & Tsitsiklis, 1987). This apparent simplification is only due to the fact that complexity is measured relative to the size of the input of the problem, and the explicit representation introduces an artificial blow-up of this size.

In this paper, MDPs are assumed to be in a succinct representation. In particular, states are possible evaluations of a set of Boolean variables (state variables); the effects of the actions and the reward function are described using circuits. Since the number of states is exponential in the number of state variables, and a **policy indicates the action**
to execute in each state, an explicit representation of policies is always exponential in the number of state variables. On the other hand, a succinct representation of an MDP may take only polynomial space in the number of state variables. **If this is the case, the policy** is exponentially larger than the MDP. However, as MDPs can be **succinctly represented in** a small amount of space, policies can be expressed in some succinct form as well (Koller & Parr, 1999). In this paper, policies are represented by circuits that take as input a state and (possibly) the history (the past states), and output the **next action to execute.**
The first result proved in this paper (Section 4) is that optimal policies, even in a succinct representation, may require an amount of space that is exponential in the size of the MDP.