Assumption 14. Assume that samples **Σ are avail-** ¯
able. Assume also that features and transitions satisfy Lipschitz-type constraints:

$$\|\phi(\bar{s})-\phi(s)\|_{\infty}\leq K_{\phi}\|k(s)-k(\bar{s})\|$$ $$|r(\bar{s})-r(s)|\leq K_{r}\|k(s)-k(\bar{s})\|$$ $$\|P(\bar{s},a)^{\mathsf{T}}\phi_{i}-P(s,a)^{\mathsf{T}}\phi_{i}\|_{\infty}\leq K_{p}\|k(s)-k(\bar{s})\|\quad\forall a\in\mathcal{A}\,.$$

Here φi **denotes a vector representation of a feature**
across all states. It is easy to show the following:
Proposition 15. Assume Assumption 6 **and that**
kφik1 = 1. Then Assumption 14 **holds with the identical constants.**
The proof is simple and relies on the trivial version of Holder's inequality to combine kP(¯**s, a**)
Tφi −
P(**s, a**)
Tφik∞ **with** kφik1.

While Assumption 14 **characterizes general properties**
of the MDP, the following assumption unifies the assumptions on the MDP and the sampling.

Assumption 16 (Sufficient Sampling). **Assume that**
for ∀s ∈ S, there exists ∃s¯ ∈ S**¯, such that:**

* $||\phi(\bar{s})-\phi(s)||_{\infty}\leq\delta_{\phi}$ * $|r(\bar{s})-r(s)|\leq\delta_{r}$ * $||P(\bar{s},a)^{\top}\phi_{i}-P(s,a)^{\top}\phi_{i}||_{\infty}\leq\delta_{p}\quad\forall a\in{\cal A}$.  
where P(s, a) represents the vector of transition probabilities from states s **given action** a.

Theorem 17. Assume Assumption 2 and Assumption 16. Let the value function v be represented as v ∈ M such that kxk1 ≤ ψ**. Then**
Assumption 4 **is satisfied with the following constraints:**

$$\epsilon_{p}=\delta_{r}+\psi(\delta_{\phi}+\gamma\delta_{p})$$

The theorem also holds if a column of Φ is 1 **and the**
corresponding element of x **is not included in the norm.**
Proof. **From the assumptions in the theorem, we have**
that v ≥ Lv¯ **and we need to show that** v ≥ Lv − ǫp1.

Then we get, using Holder's inequality that:
min s∈S
(v − Lv)(s) ≥

≥ min
s∈S ≥ − max s∈S,a∈A |((φ(s) − γP(s, a) TΦ) − (φ(¯s) − γP(¯s, a) TΦ)x) − r(s) + r(¯s)| ≥ − max s∈S,a∈A k(φ(s) − γP(s, a) TΦ) − (φ(¯s) − γP(¯s, a) TΦ)k∞kxk1 + |r(s) + r(¯s)| ≥ − max s∈S,a∈A k(φ(s) − γP(s, a) TΦ)
(v − Lv)(s) − (v − Lv¯ )(¯s)
s∈S,a∈A − (φ(¯s) − γP(¯s, a) TΦ)k∞ψ + δr ≥ − max s∈S,a∈A k(φ(s) − φ(s)k1 + γkP(s, a) TΦ) − (φ(¯s) − P(¯s, a) TΦ)k∞ψ + δr ≥ −(δφ + δp)ψ − δr
The following then summarizes the results.

Theorem 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 )
Proof. **The corollary follows simply by setting the following values.**

$$\begin{array}{c}{{\delta_{\phi}=c K_{\phi}}}\\ {{\delta_{r}=c K_{r}}}\\ {{\delta_{p}=c K_{P}}}\end{array}$$

Notice that for simplicity, we did not provide any bounds on ǫc**. These bounds require additional assumptions on the sampling procedure. That is the**
sampling must not only cover the whole space, but must also be uniformly distributed over it. Without such distribution, the objective function ρ **must be a**
weighted **sum of the states.**

## B. Homotopy Continuation Method

The homotopy algorithm is similar to sensitivity analysis of the standard simplex algorithm. However, the basic feasible solutions in simplex are of the size of the number of variables. Because we are interested in solving very large linear programs, this is often impractical. The homotopy method we propose instead