Tibshirani, Robert. Regression shrinkage and selection via the LASSO. Journal of the Royal Statistical Society. Series B (Methodological)**, pp. 267–288, 1996.**
Vanderbei, Robert J. Linear Programming: Foundations and Extensions**. Springer, 2nd edition, 2001.**

Wang, Hua O., Tanaka, Kazuo, and Griffin, Michael F.

An approach to fuzzy control of nonlinear systems: Stability and design issues. **IEEE Transactions on** Fuzzy Systems**, 4(1):14–23, 1996.**

## A. Proofs A.1. Sampling Bounds

The following lemmas summarize the basic properties of the Bellman operator. We include them without proofs, which use standard techniques.

Lemma 11 (Bellman Operator). Let 1 and v **be a**
constant vector of an appropriate size. Then:
L(v + ǫ1) = γǫ1 + Lv.

Lemma 12 **(Transitive Feasible are Upper Bound)**.

Assume an ǫ**-transitive-feasible value function** v ∈ K(ǫ)**. That is:**
v ≥ Lv − ǫ1.

Then:

$$v\geq v^{*}-{\frac{\epsilon}{1-\gamma}}\mathbf{1}.$$

Lemma 13. Assume Assumption 2 and that there exists v ∈ M **such that**
kv − v
∗k∞ ≤ ǫ.

Then, there exists v
′ ∈ M ∩ K **such that**

$$\|v^{\prime}-v^{*}\|_{\infty}\leq\frac{2\epsilon}{1-\gamma}.$$

Theorem 8. [Offline Error Bound] Assume Assumptions 2, 4, and 5. Let vˆ, v¯, v˜ **be the optimal solutions**
of (5), (6), and (7), respectively (see **Figure 1). Let**
ǫ =2 1−γ minv∈M(ψ) kv − v
∗k∞ **Then, the following inequalities hold:**
kvˆ − v
∗k1,ρ ≤ ǫ

$\|\bar{v}-v^{*}\|_{1,\rho}\leq\epsilon+2\epsilon_{c}(\psi)+2\frac{\epsilon_{p}(\psi)}{1-\gamma}$  $\|\bar{v}-v^{*}\|_{1,\rho}\leq\epsilon+2\epsilon_{c}(\psi)+\frac{3\epsilon_{s}(\psi)+2\epsilon_{p}(\psi)}{1-\gamma}$
Proof. To simplify the notation, we omit ψ in the notation of ǫ **in the proof.**
Proof of kvˆ − v
∗k1,ρ:
Let v **be the minimizer of min**v∈M kv − v
∗k∞**. Then**
from Lemma 13, Lemma 12, and kxk1,ρ ≤ kxk∞ **there**
exists v
′ ∈ M ∩ K **such that:**

$$\|v^{\prime}-v^{*}\|_{\infty}\leq{\frac{2}{1-\gamma}}\|v-v^{*}\|_{\infty}$$

From **Lemma 12, we have that:**
kvˆ − v
∗k1,ρ = ρ T
(ˆv − v
∗) = ρ T
vˆ − ρ T
v
∗ ≤ ρ T
v
′ − ρ T
v
∗
≤ kv
′ − v
∗k1,ρ.