The ordering over states in the definitions above is also assumed to be consistent. The sampled version of the bilinear program (ABP–L∞) is then:

$$\begin{array}{ll}\min_{\pi\,\uparrow\lambda,\lambda^{\prime},x}&\pi^{\mathsf{T}}\lambda+\lambda^{\prime}\\ \mbox{s.t.}&\tilde{B}\pi=\mathbf{1}&\tilde{A}\Phi x-b\geq\mathbf{0}\\ &\pi\geq\mathbf{0}&\lambda+\lambda^{\prime}\mathbf{1}\geq\tilde{A}\Phi x-\tilde{b}\\ &\lambda,\lambda^{\prime}\geq\mathbf{0}\end{array}$$ (s-ABP-$L_{\infty}$)
The size of the bilinear program (s–ABP–L∞) scales with the number of samples and features, not with the size of the full MDP, because the variables λ and π are defined only for state - action pairs in Σ. That is ˜ |π| = |λ| = |{(*s, a*) ∈ Σ}|. The number of constraints in (s–ABP–L∞) is approximately three times the number of variables λ. Finally, the number of variables x corresponds to the number of approximation features.

Theorem 13 shows that sampled robust ABP minimizes kv − Lv˜ k∞ or kv − Lv¯ k∞,
depending on the samples used. It is then easy to derive sampling bounds that rely on the sampling assumptions defined above.

Theorem 31. *Let the optimal solutions to the sampled and precise Bellman residual minimization problems be:*

$$v_{1}\in\operatorname*{min}_{v\in\mathcal{M}\cap\mathcal{K}}\|v-Lv\|_{\infty}\qquad v_{2}\in\operatorname*{min}_{v\in\mathcal{M}\cap\mathcal{K}}\|v-\bar{L}v\|_{\infty}\qquad v_{3}\in\operatorname*{min}_{v\in\mathcal{M}\cap\mathcal{K}}\|v-\bar{L}v\|_{\infty}$$

Value functions v1, v2, v3 *correspond to solutions of instances of robust approximate bilinear* programs for the given samples. Also let vˆi = vπi
, where πi is greedy with respect to vi*. Then,*
given Assumptions 10, 29, and *30, the following holds:*

$$\begin{array}{l}{{\|v^{*}-{\hat{v}}_{1}\|_{\infty}\leq\frac{2}{1-\gamma}\operatorname*{min}_{v\in\mathcal{M}}\|v-L v\|_{\infty}}}\\ {{\|v^{*}-{\hat{v}}_{2}\|_{\infty}\leq\frac{2}{1-\gamma}\left(\operatorname*{min}_{v\in\mathcal{M}}\|v-L v\|_{\infty}+\epsilon_{p}\right)}}\\ {{\|v^{*}-{\hat{v}}_{3}\|_{\infty}\leq\frac{2}{1-\gamma}\left(\operatorname*{min}_{v\in\mathcal{M}}\|v-L v\|_{\infty}+\epsilon_{p}+2\epsilon_{s}\right)}}\end{array}$$

These bounds show that it is possible to bound policy loss due to incomplete samples.

As mentioned above, existing bounds on constraint violation in approximate linear programming (de Farias and van Roy, 2004) typically do not easily lead to policy loss bounds.

Sampling guarantees for other bilinear program formulations are very similar. Because they also rely on an approximation of the initial distribution and the policy loss, they require additional assumptions on uniformity of state-samples.

Proof. We show bounds on kvi −Lvik∞; the remainder of the theorem follows directly from Theorem 13. The second inequality follows from Assumption 29 and Lemma 36, as follows:

$$\begin{array}{c}{{v_{2}-L v_{2}\leq v_{2}-\bar{L}v_{2}}}\\ {{\qquad\leq v_{1}-\bar{L}v_{1}}}\\ {{\qquad\leq v_{1}-L v_{1}+\epsilon_{p}{\bf1}}}\end{array}$$
