

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

observations from the steps during the second stage, i.e., whenever it is asked" to give an assignment to a variable (during the third stage), it does so according to the observations during the second stage and therefore it assigns the same value to every appearance of a variable in k.a. Because Φ    SSAT, a fraction of more than 1      -c of the tra ectories that reach stage correspond to a satisfying assignment and are continued under this policy to state  end where they receive reward  . Hence, the history-dependent value of   (Φ) is
- (1
= 1 For Φ    SSAT, an inconsistent (or cheating ) policy on   (Φ) may have performance greater than 1 - c . Therefore, we have to perform a probability amplification as in the proof of Theorem 4.7 that punishes cheating.  We construct     k (Φ) from    copies of (Φ) (the exact value of    will be determined later), such that the initial state of    k(Φ) is the initial state of I is and the initial state of I is the final state end of I i If in some repetition a tra ectory is caught cheating, then it is sent to the  penalty box" and is not continued in the following repetitions. Hence, it cannot collect any more rewards. More formally, the states cheat of all the js are identified as a unique sink state of k ( Φ ).

If Φ   SSAT, then in each round (or repetition), expected rewards    1
- can be collected, and hence the value of   k(Φ) is
(1 Consider a formula Φ    SSAT. Then a non-cheating policy for    k(Φ) has performance
-c. Cheating policies may have better performances. We claim that for all less than the value of     k ( Φ ) is at most 
( 
which has the same value as     (Φ). Hence, the value of      (Φ) is at most 1. As an inductive hypothesis, let us assume that    k ( Φ ) has value at most we consider k (Φ), i.e. (Φ) followed by k(Φ). Assume that a policy j cheats on of the  r assignments. From the   tra ectories that correspond to an assignment, at least 11 is trapped for cheating under a cheating policy, and at most l may obtain reward Then the reward obtained in the first round is at most
- 
7, and the rewards