3. The sum of k *largest errors*: This formulation represents a hybrid between the robust and expected formulations. It is more robust than simply minimizing the expected performance but is not as sensitive to worst-case performance.

The appropriateness of each formulation depends on the particular circumstances of the domain. For example, minimizing robust bounds is advantageous when the initial distribution is not known and the performance must be consistent under all circumstances. On the other hand, minimizing expected bounds on the value function is useful when the initial distribution is known.

In the formulations described below, we initially assume that samples of all states and actions are used. This means that the precise version of the operator L is available. To solve large problems, the number of samples would be much smaller; either simply subsampled or reduced using the structure of the MDP. Reducing the number of constraints in linear programs corresponds to simply removing constraints. In approximate bilinear programs it also reduces the number of some variables, as Section 6 describes.

The formulations below denote the value function approximation generically by v ∈ M.

That restricts the value functions to be representable using features. Representable value functions v can be replaced by a set of variables x as v = Φx. This reduces the number of variables to the number of features.

## 4.1 Robust Policy Loss

The solution of the robust approximate bilinear program minimizes the L∞ norm of the Bellman residual kv − Lvk∞. This minimization can be formulated as follows.

$$\begin{array}{c c c}{{\operatorname*{min}_{\pi\,\mid\lambda,\lambda^{\prime},v}}}&{{\pi^{\mathsf{T}}\lambda+\lambda^{\prime}}}\\ {{\mathrm{s.t.}}}&{{B\pi=\mathbf{1}}}&{{A v-b\geq\mathbf{0}}}\\ {{}}&{{\pi\geq\mathbf{0}}}&{{\lambda+\lambda^{\prime}\mathbf{1}\geq A v-b}}\\ {{}}&{{}}&{{\lambda,\lambda^{\prime}\geq\mathbf{0}}}\\ {{}}&{{v\in\mathcal{M}}}\end{array}\qquad\qquad\qquad\mathrm{(ABP-}L_{\infty})$$

All the variables are vectors except λ 0, which is a scalar. The matrix A represents constraints that are identical to the constraints in (ALP–L1). The variables λ correspond to all state-action pairs. These variables represent the Bellman residuals that are being minimized. This formulation offers the following guarantees.

Theorem 13. Given Assumption 10, any optimal solution (˜π, v, ˜ λ, ˜ λ˜0) of the approximate bilinear program (ABP–L∞) *satisfies:*

$$\tilde{\pi}^{\mathsf{T}}\tilde{\lambda}+\tilde{\lambda}^{\prime}=\|L\tilde{v}-\tilde{v}\|_{\infty}\leq\operatorname*{min}_{v\in\mathcal{M}\cap\mathcal{M}}\|Lv-v\|_{\infty}$$ $$\leq2\operatorname*{min}_{v\in\mathcal{M}}\|Lv-v\|_{\infty}$$ $$\leq2(1+\gamma)\operatorname*{min}_{v\in\mathcal{M}}\|v-v^{*}\|_{\infty}.$$
$$10$$
