The purpose of state ¯s is to ensure that v(s(ci)) ≥ 2 − γ, as we assume in the remainder of the proof.

First, we show that if the SAT problem is satisfiable, then minv*∈M∩K* kLv − vk∞ < 1.

The value function ˜v ∈ K is constructed as a linear sum of the features as: v = Φy, where y = (y1*, . . . , y*m, y¯). Here yk corresponds to φk and ¯y corresponds to φ¯. The coefficients yk are constructed from the truth value of the variables as follows:

$$\begin{array}{l l}{{y_{k}=\begin{cases}\gamma&{\mathrm{if~}}x_{k}=\mathrm{true}\\ -\gamma&{\mathrm{if~}}x_{k}=\mathrm{false}\end{cases}}}\\ {{\bar{y}=2-\gamma.}}\end{array}$$
Now define the *deterministic* policy π as:
π(s(Ci)) = aj where lij = true .

The true literals are guaranteed to exist from the satisfiability. This policy is greedy with respect to ˜v and satisfies that kLπv˜ − v˜k∞ ≤ 1 − γ 2.

The Bellman residuals for all actions and states, given a value function v, are defined as:
v(s) − γv(s 0) − r, where t(*s, a*) = (s 0, r). Given the value function ˜v, the residual values are:

$\lambda=(\omega^{I},\omega)$, Cii. 
here $t(s,a)=(s^{\prime},\tau)$. Given the value function $v$, the residual values are:  $$t(s(C_{i}),a_{j})=(s(l_{ij}),1-\gamma):\begin{cases}2-\gamma-\gamma^{2}+(1-\gamma)=1-\gamma^{2}&\text{if}\quad l_{ij}=\text{true}\\ 2-\gamma+\gamma^{2}+(1-\gamma)=1+\gamma^{2}&\text{if}\quad l_{ij}=\text{false}\end{cases}$$ $$t(s(l_{ij}),a)=(s(l_{ij}),(1-\gamma)):\begin{cases}\gamma-\gamma^{2}+1-\gamma=1-\gamma^{2}&\text{if}l_{ij}=\text{true}\\ -\gamma+\gamma^{2}+1-\gamma=(1-\gamma)^{2}>0&\text{if}l_{ij}=\text{false}\end{cases}$$ $$t(\bar{s},a)=(\bar{s},1-\gamma):(1-\gamma)+\gamma-1=0$$
It is now clear that π is greedy and that:

$$\|L\tilde{v}-\tilde{v}\|_{\infty}=1-\gamma^{2}<1.$$

We now show that if the SAT problem is not satisfiable then minv*∈K∩M* kLv − vk∞ ≥
1 −
γ 2 2
. Now, given a value function v, there are two possible cases for each v(s(lij )): 1) a positive value, 2) a non-positive value. Two literals that share the same variable will have the same sign, since there is only one feature per each variable.

Assume now that there is a value function ˜v. There are two possible cases we analyze:
1) all transitions of a greedy policy are to states with positive value, and 2) there is at least one transition to a state with a non-positive value. In the first case, we have that
∀i ∃j, v˜(s(lij )) > 0.

That is, there is a function q(i), which returns the positive literal for the clause j. Now, create a satisfiable assignment of the SAT as follows:

$$x_{k}=\begin{cases}\mathrm{true}&\mathrm{if}\ l_{i q(i)}=x_{k}\\ \mathrm{false}&\mathrm{if}\ l_{i q(i)}=\neg x_{k}\end{cases},$$
