Moreover, there exists an optimal solution π˜ that is greedy with respect to v˜ *for which the* policy loss is bounded by:

$$\|v^{*}-v_{\tilde{\pi}}\|_{\infty}\leq{\frac{2}{1-\gamma}}\left(\operatorname*{min}_{v\in{\mathcal{M}}}\|L v-v\|_{\infty}\right).$$

It is important to note that the theorem states that solving the approximate bilinear program is equivalent to minimization over all representable value functions, not only the transitive-feasible ones. This follows by subtracting a constant vector 1 from ˜v to balance the lower bounds on the Bellman residual error with the upper ones. This reduces the Bellman residual by 1/2 without affecting the policy. Finally, note that whenever v
∗ ∈ M,
both ABP and ALP will return the optimal value function v
∗.

To prove the theorem, we first define the following linear program, which solves for the L∞ norm of the Bellman update Lπ for fixed value function v and policy π.

$$f_{1}(\pi,v)=\min_{\lambda,\lambda^{\prime}}\pi^{\mathsf{T}}\lambda+\lambda^{\prime}$$ s.t. $$\mathbf{1}\lambda^{\prime}+\lambda\geq Av-b$$ (6) $$\lambda\geq\mathbf{0}$$

The linear program (6) corresponds to the bilinear program (ABP–L∞) with a fixed policy π and value function v.

Lemma 14. Let v ∈ K be a transitive-feasible value function and let π *be a policy. Then:*

$$f_{1}(\pi,v)\geq\|v-L_{\pi}v\|_{\infty},$$

with an equality for a deterministic *policy* π.

Proof. The dual of the linear program (6) is the following program.

$$\begin{array}{ll}\max&x^{\sf T}(Av-b)\\ \mbox{s.t.}&x\leq\pi\\ &{\bf1}^{\sf T}x=1\\ &x\geq{\bf0}\end{array}\tag{7}$$

Note that replacing 1 Tx = 1 by 1 Tx ≤ 1 preserves the properties of the linear program and would add an additional constraint in (ABP–L∞): λ 0 ≥ 0.

First, we show that f1(π, v) ≥ kLπv − vk∞. Because v is feasible in the approximate bilinear program (ABP–L∞), Av − b ≥ 0 and v ≥ Lv from Lemma 38. Let state s be the state in which t = kLπv − vk∞ is achieved. That is:

$$t=v(s)-\sum_{a\in{\mathcal{A}}}\pi(s,a)\left(r(s,a)+\sum_{s^{\prime}\in{\mathcal{S}}}\gamma P(s^{\prime},s,a)v(s^{\prime})\right).$$

Now let x(*s, a*) = π(*s, a*) for all a ∈ A. This is a feasible solution with value t, from the stochasticity of the policy and therefore a lower bound on the objective value.