The minimization minv∈M kLv − vk∞ for a policy π can be represented as the following linear program.

$\phi$  $({\bf I}-\gamma P_{\pi})v+{\bf1}\phi\geq r_{\pi}$  $-({\bf I}-\gamma P_{\pi})v+{\bf1}\phi\geq-r_{\pi}$
$$\begin{array}{c c}{{\operatorname*{min}}}&{{\phi}}\\ {{\phi,v}}&{{}}\\ {{\mathrm{s.t.}}}&{{\mathrm{(I)}}}\end{array}$$
v ∈ M
Consider also the following linear program.

$$\begin{array}{c c}{{\mathrm{min}}}&{{\phi}}\\ {{\phi,v}}&{{}}\\ {{\mathrm{s.t.}}}&{{\mathrm{(I)}}}\end{array}$$
s.t. $({\bf I}-\gamma P_{\pi})v\geq r_{\pi}$ (23) $$-({\bf I}-\gamma P_{\pi})v+{\bf1}\phi\geq-r_{\pi}$$
$$v\in M$$

Next we show that the optimal solutions of (22) and (23) are closely related.

Lemma 39. Assume Assumption 10 and a given policy π*. Let* φ1, v1 and φ2, v2 *optimal* solutions of linear programs (22) and (23) *respectively. Define:*

$$\bar{v}_{1}=v_{1}+\frac{\phi_{1}}{1-\gamma}\qquad\qquad\qquad\bar{v}_{2}=v_{1}-\frac{\phi_{2}}{2(1-\gamma)}{\bf1}$$
Then:
1. 2φ1 = φ2
* $v_{2}$ is an optimal solution in (22). * 4. Greedy policies with respect to $v_{1}$ and $\bar{v}_{1}$ are identical. * 5. Greedy policies with respect to $v_{2}$ and $\bar{v}_{2}$ are identical.  
1. $\omega_{1}-\omega_{2}$ 2. $\bar{v}_{1}$ _is an optimal solution in (_23_)._ 3. $\bar{v}_{2}$ _is an optimal solution in (_22_)._
Proof. Let φ¯1 = 2φ1 and φ¯2 =
φ2 2
. We first show φ¯1, v¯1 is feasible in (23). It is representable since 1 ∈ M and it is feasible by the following simple algebraic manipulation:

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

and

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

$$\begin{array}{l l}{{}}&{{}}\\ {{}}&{{=-(\mathbf{I}-\gamma P_{\pi})v_{1}-(\mathbf{I}-\gamma P_{\pi}){\frac{\phi_{1}}{1-\gamma}}\mathbf{1}+2\phi_{1}\mathbf{1}}}\\ {{}}&{{=-(\mathbf{I}-\gamma P_{\pi})v_{1}-\phi_{1}\mathbf{1}+2\phi_{1}\mathbf{1}}}\\ {{}}&{{\geq-\phi_{1}\mathbf{1}-r_{\pi}+2\phi_{1}\mathbf{1}}}\\ {{}}&{{=-r_{\pi}}}\end{array}$$

33