This theorem implies that the next-action problem is hard for the compilability class k❀NP. In turn, this result implies that some MDPs do not have any **optimal succinct policy**
of size polynomial in that of the MDP and the horizon. More specifically, there is no way for storing the optimal actions for all states in such a way the required space is polynomial and the time needed to determine the action to execute in a state is polynomial as well.

Theorem 3 **If there exists a data structure, of size polynomial in that of the MDP and the** horizon, that allows computing the best action to execute (either from the current state or from the history) for any given MDP and horizon in unary notation in polynomial time, then NP ⊆ P/**poly**.

Proof. If such a data structure exists, the next-action problem is in k❀**P: given the fixed**
part of the problem only (the MDP and the horizon), it is possible determine such a data structure in the preprocessing step; the result of this step **makes determining the next action**
a polynomial task. As a result, the next-action problem is in k❀**P. On the other hand,**
the existence of a monotonic polynomial reduction from propositional satisfiability to the next-action problem implies that if this problem is in k❀P, then k❀NP=k❀**P (Liberatore,**
2001, Theorem 3). In turn, this result implies that NP ⊆ P/**poly (Cadoli et al., 2002,**
Theorem 2.12).

Note that NP ⊆ P/**poly implies that Σ**p 2 = Πp 2 **= PH, i.e., the polynomial hierarchy**
collapses to its second level (Karp & Lipton, 1980). As a result, the above theorem implies that one can always represent the optimal policies in space polynomial in that of the MDP and the horizon only if the polynomial hierarchy collapses. **Since the succinct representation** of policies based on circuits is a subcase of data structures **allowing the determination of**
the next action in polynomial time, the following corollary **holds.**
Corollary 1 If there exists a polynomial p such that every succinct MDP M **with horizon**
T **has succinct optimal policies (either stationary or history dependent) of size bounded by** p(||M|| + T), then NP ⊆ P/poly and Σ
p 2 = Πp 2 **= PH**.

## 5. Finding And Evaluating Succinct Policies

The problem considered in this section is that of checking the existence of succinct policies of a given size and reward.

A subproblem of interest is that of evaluating a policy, that **is, calculating its expected**
reward. While Mundhenk et al. (2000) found the complexity of **this problem for various** cases, they left open the case of full observability and succinct representation, which is the one considered in this paper. This problem has instead been analyzed by Littman, Goldsmith, and Mundhenk (1998) considering the succinct representation of plans based on the ST plan representation (which is also equivalent to other succinct representation.) The proof presented in the current paper could follow along similar lines.

Does the evaluation problem make sense, given that some MDPs **do not have optimal**
succinct policies of polynomial size? From a theoretical point of view, super-polynomiality does not forbid a complexity analysis. Indeed, complexity is measured relative to the total size of the problem instances; the instances of the policy evaluation problem include both