tive. Therefore, the linear segments are traced until a variable becomes inactive or a constraint becomes active. Then, the dual solution is traced until a constraint becomes inactive or a variable becomes active.

Since the homotopy algorithm solves for the optimal value of the RALP (2) for all values of the regularization coefficient ψ, it is possible to increase the coefficient ψ **until the error increase between sampled constraints balances out the decrease in the error due to**
the restricted feature space as defined in **Theorem 8.** That is, we can calculate the objective value of the linear program (2) for any value of ψ.

It is easy to find ψ **that minimizes the bounds in this**
section. As the following corollary shows, to find the global minimum of the bounds, it is sufficient to use the homotopy method to trace θ(ψ**) while its derivative**
is less than the increase in the error due to the sampling (kvˆ − v˜k1,ρ). Let v(ψ**) be an optimal solution of**
(7) as a function of the regularization coefficient ψ.

Corollary 10. Assume that ǫc(ψ), ǫp(ψ)**, and** ǫs(ψ)
are convex functions of ψ**. Then, the error bound** kv(ψ) − v
∗k1,ρ ≤ f(ψ) for any v(ψ) is:

$$f(\psi)=\theta(\psi)-\rho^{\mathsf{T}}v^{*}+\epsilon_{c}(\psi)+2{\frac{\epsilon_{s}(\psi)+\epsilon_{p}(\psi)}{1-\gamma}}$$

The function f(ψ) **is convex and its sub-differential**1
∇ψf **is independent of** v
∗**. Therefore, a global minimum** ψ
∗ of f is attained when 0 ∈ ∇ψf(ψ
∗) **or when**
ψ
∗ = 0.

The corollary follows directly from Theorem 9 **and the** convexity of the optimal objective value of (2) as a function ψ. Figure 2 **illustrates the functions in the**
corollary. Notice that Proposition 7 **is sufficient to satisfy the conditions of this corollary. In particular, the**
functions ǫs(ψ), ǫp(ψ), ǫc(ψ**) are linear in** ψ.

## 6. Experimental Results

In this section, we present results indicating that RALP effectively selects from rich feature spaces to outperform ALP and other common algorithms, such as LSPI, on several example problems, including the balanced pendulum and the bicycle problems. We also demonstrate the speed and effectiveness of the homotopy method in choosing a value of ψ.

Benefits of Regularization **First, we demonstrate**
and analyze the properties of RALP on a simple chain problem with 200 states, in which the transitions move to the right by one step with a centered Gaussian noise 1Function f **may be non-differentiable**
with standard deviation 3. The reward for reaching the right-most state was +1 and the reward in the 20th state was -3. This problem is small to enable calculation of the optimal value function and to control sampling. We uniformly selected every fourth state on the chain and estimated the sampling bound ǫp(ψ) = 0.05ψ**. The approximation basis in this problem is represented by piecewise linear features, of the** form φ(si) = [i − c]+, for c **from 1 to 200; these features were chosen due to their strong guarantees for**
the sampling bounds. The experimental results were obtained using the proposed homotopy algorithm.

Figure 3 **demonstrates the solution quality of RALP**
on the chain problem as a function of the regularization coefficient ψ**. The figure shows that although the**
objective of RALP keeps decreasing as ψ **increases,**
the sampling error overtakes that reduction. It is clear that a proper selection of ψ **improves the quality of the**
resulting approximation. To demonstrate the benefits of regularization as it relates to overfitting, we compare the performance of ALP and RALP as a function of the number of available features in **Figure 5.**
While ALP performance improves initially, it degrades severely with more features. The value ψ **in RALP is**
selected automatically using Corollary 10 and the sampling bound of ǫp(ψ) = 0.05ψ. Figure 4 **demonstrates**
that RALP may also overfit, or perform poorly when the regularization coefficient ψ **is not selected properly.**
To find the proper value of ψ**, as described in**
Corollary 10, the problem needs to be solved using the homotopy method. We show that the homotopy method performs significantly faster than a commercially available linear program solver Mosek. **Figure 6**
compares the computational time of homotopy method and Mosek, when solving the problem for multiple values of ψ **in increments of 0.5 on the standard mountain**
car problem (Barto & Sutton, **1998) with 901 piecewise linear features and 6000 samples. Even for any**
single value ψ**, the homotopy method solves the linear**
program about 3 times faster than Mosek. The next two experiments, however, do not **use the homotopy**
method. In practice, RALP often works much better than what is suggested by our bounds, which can be loose for sparsely sampled large state spaces. In the following experiments, we determined ψ **empirically by** solving the RALP for several different values of ψ and selecting the one that produced the best policy. This was practical because we could solve the large RALPs in just a few minutes using constraint generation.

Inverted Pendulum We now offer experimental results demonstrating RALP's ability to create effective value functions in balancing an inverted pen-