Next we show that φ¯2, v¯2 is feasible in (22). This solution is representable, since 1 ∈ M,
and it is feasible by the following simple algebraic manipulation:

$$(\mathbf{I}-\gamma P_{\pi})\bar{v}_{2}+\bar{\phi}_{2}\mathbf{1}=(\mathbf{I}-\gamma P_{\pi})v_{2}-(\mathbf{I}-\gamma P_{\pi})\frac{\phi_{2}}{2(1-\gamma)}\mathbf{1}+\frac{\phi_{2}}{2}\mathbf{1}$$ $$=(\mathbf{I}-\gamma P_{\pi})v_{2}-\frac{\phi_{2}}{2}\mathbf{1}+\frac{1}{2}\bar{\phi}_{2}\mathbf{1}$$ $$=(\mathbf{I}-\gamma P_{\pi})v_{2}$$ $$\geq r_{\pi}$$

and

$$-(\mathbf{I}-\gamma P_{\pi}){\bar{v}}_{2}+{\bar{\phi}}_{2}\mathbf{1}=-(\mathbf{I}-\gamma P_{\pi}){\bar{v}}_{2}+{\frac{\phi_{2}}{2}}\mathbf{1}$$
$$\begin{array}{l l}{{{\bf I}=}}&{{({\bf I}-\gamma P_{\pi})v_{2}+\mathbf{\nabla}_{2}{\bf I}}}\\ {{}}&{{}}\\ {{}}&{{=-({\bf I}-\gamma P_{\pi})v_{2}-({\bf I}-\gamma P_{\pi})\frac{\phi_{2}}{1-\gamma}{\bf1}+\frac{\phi_{2}}{2}{\bf1}}}\\ {{}}&{{}}\\ {{}}&{{=-({\bf I}-\gamma P_{\pi})v_{2}+\phi_{2}{\bf1}}}\\ {{}}&{{}}\\ {{}}&{{\geq-r_{\pi}}}\end{array}$$

It is now easy to shows that φ¯1, v¯1 is optimal by contradiction. Assume that there exists a solution φ2 < φ¯1. But then:
2φ¯2 ≤ φ2 < φ¯1 ≤ 2φ1, which is a contradiction with the optimality of φ1. The optimality of φ¯2, v¯2 can be shown similarly.

Proposition 40. Assumption 10 *implies that:*

$$\operatorname*{min}_{v\in{\mathcal{M}}\cap{\mathcal{K}}}\|L v-v\|_{\infty}\leq2\operatorname*{min}_{v\in{\mathcal{M}}}\|L v-v\|_{\infty}.$$

Proof. Let ˆv be the minimizer of φˆ = minv∈M kLv − vk∞, and let ˆπ be a policy that is greedy with respect to ˆv. Define:

$$\tilde{v}=\hat{v}+\frac{\hat{\phi}}{1-\gamma}.$$

Then from Lemma 39:
1. Value function ˜v is an optimal solution of (23): ˜v ≥ Lπv˜
2. Policy ˆπ is greedy with regard to ˜v: Lπˆv˜ ≥ Lv˜
3. kLπv˜ − v˜k∞ = 2φˆ
Then using a simple algebraic manipulation:
v˜ ≥ Lπˆv˜ = Lv˜
and the proposition follows from Lemma 38.

Proposition 41. Let v˜ *be a solution of the approximate bilinear program* (ABP–L∞) and let:

$$v^{\prime}=v-\frac{1/2}{(1-\gamma)}\|L v-v\|_{\infty}{\bf1}.$$

Then: