Lemma 20. Let value function v *be feasible in the bilinear program* (ABP–U)*, and let* π be an arbitrary policy. Then:

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

with an equality for a deterministic policy.

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

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

We have that f1(π, v) ≥ kLπv − vk1,u¯ since x = U
Tπ is a feasible solution. To show the equality for a deterministic policy π, let x
∗ be an optimal solution of linear program (11).

Since Av ≥ b and U is non-negative, an optimal solution satisfies x = U
Tπ. The optimal value of the linear program thus corresponds to the definition of the weighted L1 norm.

The proof of Theorem 19 is similar to the proof of Theorem 13, but using Theorem 8 instead of Theorem 7 to bound the policy loss. The existence of a deterministic and greedy optimal solution ˜π follows also like Theorem 13, omitting λ 0 and weighing λ by ¯u.

## 4.3 Hybrid Formulation

While the robust bilinear formulation (ABP–L∞) guarantees to minimize the robust approximation error it may be overly pessimistic. The bilinear program (ABP–U), on the other hand, optimizes the average performance, but does not provide strong guarantees. It is possible to combine the advantages (and disadvantaged) of these programs using a hybrid formulation. The hybrid formulation minimizes the hybrid norm of the Bellman residual, defined as:

$$\|x\|_{k,c}=\operatorname*{max}_{\{y\,|\,{\bf1}^{\intercal}y=k,{\bf1}\geq y\geq{\bf0}\}}\sum_{i=1}^{n}y(i)c(i)|x(i)|,$$

where n is the length of vector x and c ≥ 0. It is easy to show that this norm represents the c-weighted L1 norm of the k largest components of the vector. As such, it is more robust than the plain L1 norm, but is not as sensitive to outliers as the L∞ norm. Notice that the solution may be fractional when k /∈ Z - that is, some elements are counted only partially.

The bilinear program that minimizes the hybrid norm is defined as follows.

$$\min_{\pi\,|\lambda,\lambda^{\prime},v}\pi^{\mathsf{T}}U\lambda+k\lambda^{\prime}$$ s.t. $$B\pi=\mathbf{1}Av-b\geq\mathbf{0}$$ $$\pi\geq\mathbf{0}\lambda+\lambda^{\prime}U^{-1}\mathbf{1}\geq Av-b$$ (ABP-h) $$\lambda,\lambda^{\prime}\geq\mathbf{0}$$ $$v\in\mathcal{M}$$

Here U is a matrix that maps a policy to bounds on state-action visitation frequencies, for example, as defined in Remark 18.