Proof. The existence of an optimal π that corresponds to a deterministic policy follows from Lemma 15, the correspondence between policies and values π, and the existence of a deterministic greedy policy.

Since v ∈ K, we have for some policy π that:

$$v\geq1$$

v ≥ Lv = Lπv ≥ Lπ˜v.

Assuming that Lπ˜ *< Lv* leads to a contradiction since π is also a feasible solution in the linear program (9) and:

$$v-L_{\tilde{\pi}}>v-L v$$
$$\square$$
$$\|v-L_{\tilde{\pi}}\|_{\infty}>\|v-L v\|_{\infty}.$$

This proves the lemma.

Theorem 13 now easily follows from the lemmas above.

Proof. Let ¯v be a value function with the minimal kLv¯−v¯k∞ feasible in approximate bilinear program (ABP–L∞), and let ¯π be a greedy policy with respect to ¯v. Because ¯v ≥ v
∗, as Lemma 38 shows, we get:
t = kLv¯ − v¯k∞ = kLv¯v¯ − v¯k∞.

Let f
∗ be the optimal objective value of (ABP–L∞). Because both ¯v and ¯π are feasible in
(ABP–L∞), we have that f
∗ ≤ t. Now, assume that ˜v is an optimal solution of (ABP–L∞)
with an objective value ˜f = kLv˜ − v˜k∞ > t. Then, from Lemma 16,˜*f > t* ≥ f
∗, which contradicts the optimality of ˜v.

To show that the optimal policy is deterministic and greedy, let π
∗ be the optimal policy.

Then consider the state s for which ˜π does not define a deterministic greedy action. From the definition of greedy action ¯a:

$$(L_{\bar{a}}\tilde{v})(s)\leq(L_{\tilde{\pi}}\tilde{v})(s).$$

From the bilinear formulation (ABP–L∞), it is easy to show that there is an optimal solution such that:

$$\begin{array}{c}{{(L_{a}\tilde{v})(s)\leq\tilde{\lambda}^{\prime}+\tilde{\lambda}(s,a)}}\\ {{\tilde{\lambda}(s,\bar{a})\leq\tilde{\lambda}(s,a).}}\end{array}$$

Then setting ˜π(s, a¯) = 1 and all other action probabilities to 0, the difference in the objective value function:

$$\check{\lambda}(s,\bar{a})-\sum_{a\in{\mathcal{A}}}\check{\lambda}(s,a)\leq0.$$

Therefore, the objective function for the deterministic greedy policy does not increase. The remainder of the theorem follows directly from Proposition 40, Proposition 41, and Proposition 42. The bounds on the policy loss then follow directly from Theorem 7.