Full ALP
Sampled ALP
Estimated ALP

$$\rho={\frac{1}{|S|}}\sum_{s\in S}\phi(s)$$  $$\begin{array}{l l l}{\operatorname*{min}}&{\rho^{\mathsf{T}}v}\\ {\operatorname*{s.t.}}&{v\in\mathcal{K}}&{}\end{array}$$

![0_image_1.png](0_image_1.png)

$$\bar{\rho}=\frac{1}{|\Sigma|}\sum_{(s,\ldots)\in\Sigma}\phi(s)\bar{\rho}=\frac{1}{|\Sigma|}\sum_{(s,\ldots)\in\Sigma}\phi(s)$$ $$\min_{v}\bar{\rho}^{\top}v$$ s.t. $$v\in\bar{\mathcal{K}}\qquad v\in\mathcal{M}(\psi)\bar{\rho}=\frac{1}{|\Sigma|}\sum_{(s,\ldots)\in\Sigma}\phi(s)$$ $$\min_{v}\bar{\rho}^{\top}v$$ s.t. $$v\in\bar{\mathcal{K}}\qquad v\in\mathcal{M}(\psi)\bar{\rho}=\frac{1}{|\Sigma|}\sum_{(s,\ldots)\in\Sigma}\phi(s)$$ $$\min_{v}\bar{\rho}^{\top}v$$ s.t. $$v\in\bar{\mathcal{K}}\qquad v\in\mathcal{M}(\psi)$$

![0_image_0.png](0_image_0.png)

![0_image_2.png](0_image_2.png)

Figure 1. **Constructing ALP From Samples**
equalities hold:

$$\begin{array}{l}{{\|\hat{v}-v^{*}\|_{1,\rho}\leq\epsilon}}\\ {{{}}}\\ {{\|\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}}}\end{array}$$

Because of the technical nature of the proof, it is deferred to the appendix.

Notice that because the weight ρ is often chosen arbitrarily, the bounds may be simply derived for **k · k**1,ρ¯.

In that case, ǫc **= 0. Unlike most of the existing ALP**
bounds, we focus on bounding the error of the value function, instead of bounding the number of violated constraints. Consider the implications of these bounds combined with the Lipschitz assumptions of **Proposition 7. It is**
clear that reducing ψ tightens **Theorem 8, but causes** the set M(ψ**) to shrink and become more restrictive;**
this suggests a tradeoff to be considered when setting the regularization parameter. The bound also illustrates the importance of covering the space with samples; as the distance between the samples c **approaches zero, the bound tightens. In short, the Lipschitz assumptions limit how quickly the constraints**
can change between sampled states. As sampled states get closer or the reward, feature, and probability functions become smoother, constraints between samples become more and more restricted; however, smoother basis functions may mean a less expressive space. Similar tradeoffs are likely to appear however Assumption 4 and Assumption 5 **are fulfilled.**
The offline error bounds in Theorem 8 **can be used to**
guarantee the performance of a RALP for a fixed number of samples and the regularization coefficient ψ**. It** does not, however, prescribe how to choose the regularization coefficient for a given set of samples. To do that, we have to derive bounds for an actual value function v**. When the samples are known, these bounds are**
typically tighter than the offline error bound.

![0_image_3.png](0_image_3.png)

Theorem 9 (Online Error Bound). **Assume**
Assumption 2 and let v ∈ K ∩ M ˜ (ψ) be an arbitrary feasible solution of the estimated ALP (7).

Then:

$$\|v^{*}-v\|_{1,\rho}\leq\bar{\rho}^{\mathsf{T}}v-\rho^{\mathsf{T}}v^{*}+\epsilon_{c}(\psi)+2\frac{\epsilon_{s}(\psi)+\epsilon_{p}(\psi)}{1-\gamma}.$$

Because of the technical nature of the proof, it is deferred to the appendix.

Here we briefly introduce a homotopy method that not only speeds the computation of the RALP solution, but also can be used to find the optimal value of ψ.

Because the homotopy method only relies on standard linear programming analysis and is somewhat technical, the detailed description is provided in **Appendix B**
in the appendix.

The main idea of the homotopy method is to first calculate θ(0) and then trace the optimal solution for increasing values of ψ. The optimal solution w(ψ**) of**
the RALP (2) is a piecewise linear function of ψ**. At**
any point in time, the algorithm keeps track of a set of active - or non-zero - variables w **and a set of active constraints, which are satisfied with equality. In**
the linear segments, the number of active constraints and variables are identical, and the non-linearity arises when variables and constraints become active or inac-