between U and S **can be made differently in different states: a policy can execute** U or S

![0_image_1.png](0_image_1.png)

depending on the state that results from the 3m **executions of** A.

![0_image_0.png](0_image_0.png)

Let us now consider the state after the 3m executions of A**. Since each execution of**
A generates a random literal, at this point the state is a sequence of 3m **literals. Such a** sequence represents the set of clauses that is later used by the reward function. Intuitively, at this point the optimal policy should execute U **if the set of clauses is unsatisfiable, and**
S **if it is satisfiable.**
Let s be a state that results from the execution of A for 3m times, and let C(s**) be the**
corresponding formula. The expected reward of s **in the policy that executes the sequence**
U, a1, . . . , an **is 2 because this sequence leads to states that have all reward 2. On the other**
hand, the reward of s when the policy executes A, a1, . . . , an **depends on the satisfiability**
of the formula represented by the state. Namely, this sequence leads to a state for each possible truth interpretation over X; the reward of such a state is 1 if C(s**) is not satisfied**
by the model, and 2n+1 otherwise. This means that the reward of s **in this policy is 1 if the**
formula is unsatisfiable, and at least (2n − 1)/2 n + 2n+1/2 n **= (2**n − 1)/2 n **+ 2 if the formula**
has at least one model.

The optimal choice in s is therefore U if the formula C(s**) is unsatisfiable (reward 2) and**
S **otherwise (reward greater than or equal to (2**n − 1)/2 n + 2n+1/2 n > **2). Since the history**
can be inferred from the state, the optimal choice does not depend on whether stationary or history-dependent policies are considered.

Incidentally, this theorem implies that choosing the next action optimally is NP-hard.

What is important, however, is that the function f **can be used to prove that the problem** of choosing the next action optimally cannot be simplified to **P thanks to a preprocessing** step working on the MDP and the horizon only. This, in turn, implies the nonexistence of a polynomially sized circuit representing the optimal policy.

A polynomial reduction from 3sat **to a problem does not necessarily prove that the**
problem cannot be efficiently preprocessed. Consider, however, the case in which the problem instances can be divided in two parts. The reduction itself can be decomposed in two separate functions, one generating the part of the instance **that can be preprocessed and** one generating the rest of the instance. In our case, M and T **form the part that can be**
preprocessed, while the state s and the action a **are the rest of the instance. As a result, if**
f(Π) = hM, T, s, ai**, the two functions are defined by:**

$$\Pi)\quad=\quad\langle{\mathcal M},T\rangle$$
