To show the equality for a deterministic policy π, we show that f1(π, v) ≤ kLv − vk∞,
using that π ∈ {0, 1}. Then let x
∗ be an optimal solution of (7). Define the index of x
∗
with the largest objective value as:

$$i\in\arg\operatorname*{max}_{\{i\,|\,x^{*}(i)>0\}}(A v-b)(i).$$

Let solution x 0(i) = 1 and x 0(j) = 0 for j 6= i, which is feasible since π(i) = 1. In addition:
(Av − b)(i) = kLπv − vk∞.

Now (x
∗)
T(Av − b) ≤ (x 0)
T(Av − b) = kLπv − vk∞, from the fact that i is the index of the largest element of the objective function.

When the policy π is fixed, the approximate bilinear program (ABP–L∞) becomes the following linear program:

$f_2(\pi)=\underset{\lambda,\lambda^\prime,v^\prime}{\text{min}}$  s.t. 
λ,λ0,vπ
$$\begin{array}{c}{{\pi^{\mathsf{T}}\lambda+\lambda^{\prime}}}\\ {{A v-b\geq\mathbf{0}}}\\ {{\mathbf{1}\lambda+\lambda^{\prime}\geq A v-b}}\end{array}$$
s.t. Av − b ≥ 0
$$v\in{\mathcal{M}}$$
$$\lambda\geq0$$

$$({\mathsf{S}})$$
Using Lemma 38 , this linear program corresponds to:

$$f_{2}(\pi)=\operatorname*{min}_{v\in{\mathcal{M}}\cap\mathcal{K}}f_{1}(\pi,v).$$

Then it is easy to show that:
Lemma 15. Given a policy π, let v˜ *be an optimal solution of the linear program* (8)*. Then:*
f2(π) = kLπv˜ − v˜k∞ ≤ min v*∈M∩K*
kLπv − vk∞.

When v is fixed, the approximate bilinear program (ABP–L∞) becomes the following linear program:

$$\begin{array}{l l}{{f_{3}(v)=\operatorname*{min}}}&{{f_{2}(\pi,v)}}\\ {{\mathrm{s.t.}}}&{{}}&{{B\pi={\bf1}}}\end{array}$$

$$\pi\geq0$$
$$(9)$$

Note that the program is only meaningful if v is transitive-feasible and that the function f2 corresponds to a minimization problem.

Lemma 16. Let v ∈ M ∩ K be a transitive-feasible value function. There exists an optimal solution π˜ *of the linear program* (9) *such that:*
1. π˜ *represents a* deterministic *policy* 2. Lπ˜v = Lv 3. kLπ˜v − vk∞ = minπ∈Π kLπv − vk∞ = kLv − vk∞