

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

R
an assignment to the respective variable. The case of a cheating policy, i.e., one that answers during the third stage with another assignment than fixed during the second stage, must be punished". Whenever the variable corresponding to the initial, stored assignment appears the process checks that the stored assignment is consistent with the current assignment. If eventually the whole formula passes the checking, either reward or reward is obtained, depending on whether the formula was satisfied and the policy was not cheating, or not.

c.b be that instance of the third stage where it is checked whether  c always gets Let assignment It is essentially the same deterministic process as defined in the proof of Theorem 4.1, but whenever an assignment to a literal containing c is asked for, if c does not get assignment the process goes to state cheat . Otherwise, the process goes to state end. If the assignment chosen by the policy satisfied the formula, reward is obtained; otherwise the reward is The overall structure of   (Φ) is sketched in Figure 4. Note that the dashed arrows represent random transitions (all of equal probability, irregardless of the action chosen),
solid arrows represent deterministic transitions corresponding to the action True, dotted arrows represent deterministic transitions corresponding to the action False, and dot-dash arrows represent transitions that are forced, whatever the choice of action.

Consider a formula Φ      SSAT with variables n and random quantifiers, and consider
( Φ ). Because the third stage is deterministic, the process has r tra ectories, r of which reach stage . Now, assume that is a policy, which is consistent with the