Proof. **Let us consider a state that results from a sequence of actions. Since the considered**
policies are history dependent, it is possible to find the optimal choices from this point on by taking the current state as the new initial state of the MDP, reducing the horizon, and determining the optimal policy of this modified MDP.

Since the problem of checking whether an MDP has a policy of a given reward is in PSPACE (Mundhenk et al., 2000), it is in P by assumption. By binary search, it is possible to determine the expected optimal reward of an MDP in polynomial time. Since the expected optimal reward of each state can be computed by finding the expected optimal reward of an MDP, this problem is polynomial as well. The function that determines the optimal expected reward from a state can be therefore represented by a polynomial circuit.

The best action in a state is the one that leads to the best possible next states. It can be determined in polynomial space by checking, for each action, its possible next states, and determining their expected reward. Therefore, the best action to execute is in PSPACE, and is therefore in P by assumption. As a result, this optimal **policy can be represented by**
a polynomial circuit.

The following corollary is an immediate consequence.

Corollary 4 If P = PSPACE**, then the problem of existence of a succinct history-dependent** policy of a given expected reward and with a size bound in binary notation is in P.

Proof. **If P = PSPACE, any MDP has an optimal history-dependent policy of polynomial**
size. The problem can therefore be solved by iterating over all possible circuits whose size is bounded by this polynomial. The problem can therefore be solved with only a polynomial amount of memory, and is therefore in PSPACE. By assumption, **it is in P as well.**
At a first look, this corollary seems to prove that the problem **is in PSPACE. However,**
it does not prove such a result. This is shown by the following **related example: a problem**
that is is Σp 2
-complete is in P if P = NP; however, it is generally believed that Σp 2
-complete problems are not in NP.

An easy consequence of this result is that the EXPTIME-hardness of the problem would imply that P 6**= PSPACE. Indeed, if the problem is EXPTIME-hard then it is not in P, as** these two classes are known to be different thanks to the theorem by Hartmanis and Stearns (1965). As a result, it cannot be that P=PSPACE, which has been proved to imply that the problem is in P. In other words, if the problem of history-dependent policy existence with a size bound in binary notation is EXPTIME-hard then P 6**= PSPACE.**

## 8. Conclusions

It is not always possible to represent the optimal policies of a succinct MDP using circuits of size polynomial in that of the MDP and the horizon. This result affects the choice of how policies are generated and executed. Indeed, planning in a nondeterministic scenario can be done in two ways:
1. Determine the actions to execute in all possible states all at once (i.e., determine the whole policy); in each state, the corresponding action is executed;