In this paper, T **is assumed in unary notation. This assumption has been called "short**
horizon" or "polynomial horizon" in other papers.

The size of the explicit representation of every policy for a **succinct MDP is exponential in the number of state variables. However, some policies take less space in succinct**
representations. In this paper, the succinct representation employing circuits is considered:
their input is the current state and (possibly) the history; **their output is the next action** to execute. An example of a policy with a small succinct representation is that of always executing the same action; such a policy is exponential in the explicit representation it is necessary to specify an action for each state and the number of states is exponential in the number of state variables.

The first question considered in this paper is whether it is always possible to represent the optimal policy of a succinct MDP with a circuit of size polynomial in the size of the MDP. Namely, a succinct policy is defined as a circuit that outputs, given the current state, an action.

Definition 2 A succinct stationary policy P **is a circuit that takes a state as input and**
outputs the action to execute in the state.

A succinct policy is a circuit that represents a function from states to actions. Since (nonsuccinct) policies are functions from states to actions, succinct and non-succinct policies are in correspondence. The expected reward of a succinct policy **and its optimality can therefore**
be defined in terms of the analogous concepts for non-succinct policies.

Succinct history-dependent policies are defined in a similar way: they are circuits from sequences of states to actions (such a representation is possible because of the finite horizon.)
The expected reward and the optimality of a succinct history-dependent policy are defined from the corresponding concepts for non-succinct policies.

The first result of this paper is that, if all MDPs have optimal succinct policies of polynomial size, then the polynomial hierarchy coincides with its **complexity class Π**p 2
(considered unlikely). The proof is based on compilability classes and reduction, which are summarized in the next section.

## 3. Complexity, Compilability, And Circuits

The reader is assumed to be familiar with the complexity classes P, NP, and the other classes of the polynomial hierarchy (Stockmeyer, 1976; Garey & Johnson, 1979). Some counting classes are also used in this paper: PP is the class of the problems that can be polynomially reduced to the problem of checking whether a formula is satisfied by at least half of the possible truth assignments over its set of variables. An alternative definition is that a problem is in PP if and only if it can be polynomially reduced to that of checking whether P V (M) ≥ k, where k is an integer, V **is a function from propositional interpretations to**
integers that can be calculated in polynomial time, and the sum ranges over all possible propositional interpretations (Johnson, 1990). The class NPPP **is defined in terms of oracles:**
it is the class of problems that can be solved in polynomial time by a non-deterministic Turing machine that has access to a PP-oracle, which is a device that can solve a problem in PP in one time unit.