To bound the error from sampling, we must formally define the samples and how they are used to construct ALPs. We consider the following two types of samples Σ and ˜ **Σ defined as follows.** ¯
Definition 3. One-step simple samples **are defined as**
follows: Σ˜ ⊆ {(s, a,(s1 . . . sn), r(s, a)) s ∈ S, a **∈ A}**,
where s1 . . . sn are selected i.i.d. from the distribution P(s, a, ·). One-step samples with expectation are defined as follows: Σ¯ ⊆ {(s, a, P(s, a, ·), r(**s, a**)) s ∈
S, a **∈ A}**.

Often the samples only include state transitions, as Σ˜ defines. The more informative samples **Σ include the** ¯
probability distribution of the states that follow the given state and action, as follows:

$$\bar{L}(v)(\bar{s})=r(\bar{s},a)+\gamma\sum_{s^{\prime}\in{\cal S}}P(\bar{s},a,s^{\prime})v(s^{\prime}),\tag{3}$$  where $(\bar{s},a,\underset{\cdot}{\cdot}P(\bar{s},a,\cdot),r(\bar{s},a))\in\bar{\Sigma}$. The less 
informative **Σ can be used as follows:** ˜
$$\tilde{L}(v)(\tilde{s})=r(\tilde{s},a)+\gamma\frac{1}{n}\sum_{i=1}^{n}v(s_{i}),\qquad\qquad(4)$$

where (˜s, a,(s1 . . . sn), r(˜s, a)) ∈ **Σ. The corresponding** ˜
transitive-feasible sets K¯ and K˜ **are defined similarly.**
The ALPs can be constructed based on samples as Figure 1 shows. Full ALP **corresponds to the RALP**
formulation in (2), when M **is constricted with** L1 regularization. In comparison, sampled ALP **is missing** some of the constraints while estimated ALP **is both** missing some constraints, and the included constraints may be estimated imprecisely.

The following two assumptions quantify the behavior of the ALP with respect to missing and imprecise constraints respectively. The first assumption limits the error due to missing transitions in the sampled Bellman operator L¯.

Assumption 4 (Constraint Sampling Behavior). The representable value functions satisfy that:

$$\mathcal{K}\cap\mathcal{M}(\psi)\subseteq\bar{\mathcal{K}}\cap\mathcal{M}(\psi)\subseteq\mathcal{K}(\epsilon_{p})\cap\mathcal{M}(\psi),$$

and that for all representable value functions v ∈ M(ψ**) we have that** |(ρ − ρ¯)
Tv| ≤ ǫc(ψ).

The constant ǫp **bounds the potential violation of the**
ALP constraints on states that are not provided as a part of the sample. In addition, all value functions that are transitive-feasible for the full Bellman operator are transitive-feasible in the sampled version; the sampling only removes constraints on the set. The constant ǫc essentially represents the maximal error in estimating the objective value of ALP for any representable value function.

The next assumption quantifies the error on the estimation of the transitions of the estimated Bellman operator L˜.

Assumption 5 **(Constraint Estimation Behavior)**.

The representable value functions satisfy that:

$$\bar{\mathcal{K}}(-\epsilon_{s})\cap\mathcal{M}(\psi)\subseteq\bar{\mathcal{K}}\cap\mathcal{M}(\psi)\subseteq\bar{\mathcal{K}}(\epsilon_{s})\cap\mathcal{M}(\psi),$$

where Σ and ¯ Σ (and therefore ˜ K¯ and K**˜) are defined**
for identical sets of states. These assumptions are quite generic in order to apply in a wide range of scenarios. The main idea behind the assumptions is to bound by how much a feasible solution in the sampled or estimated ALP can violate the true ALP constraints. These assumptions may be easily satisfied, for example, by making the following Lipschitz continuity assumptions.

Assumption 6. Let k : S → R
n **be a map of the**
state-space to a normed vector space. Then for all x, y, z ∈ S and all features (columns) φi ∈ **Φ, we define** Kr, KP , and Kφ **such that**

$$\begin{array}{c}{{|r(x)-r(y)|\leq K_{r}\|k(x)-k(y)\|}}\\ {{|p(z|x,a)-p(z|y,a)|\leq K_{P}\|k(x)-k(y)\|}}\\ {{|\phi_{i}(x)-\phi_{i}(y)|\leq K_{\phi}\|k(x)-k(y)\|}}\end{array}$$

Proposition 7. Assume Assumption 6 **and that for**
any s ∈ S there exists a state s¯ ∈ Σ¯ such that ks¯−sk ≤
c. Then Assumption 4 and Assumption 5 **hold with**
ǫp(ψ) = cKr + cψ(Kφ + γKP )
Because of the technical nature of the proof, it is deferred to the appendix.

The importance of this bound is that the violation on constraints that were not sampled grows linearly with the increasing coefficient ψ**. As we show below, this**
fact can be used to determine the optimal value of ψ.

For the sake of brevity, we do not discuss the estimation error bounds ǫs **in more detail, which can be easily derived from existing results (Petrik & Zilberstein,**
2009). We are now ready to state the following general bounds on the approximation error of a RALP.

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 in-