2008; Kolter & Ng, 2009). In comparison with LARSTD (Kolter & Ng, 2009), an L1 **regularized value function approximation method, we explicitly show the influence of regularization on the sampling error, provide a well-founded method for selecting the regularization parameter, and solve the full control problem. In comparison with existing sampling bounds for**
ALP (de Farias & Van Roy, **2001), we do not assume** that the optimal policy is available, make more general assumptions, and derive bounds that are independent of the number of features.

Our approach is based on approximate linear programming (ALP), which offers stronger theoretical guarantees than some other value function approximation algorithms. We describe ALP in Section 3 **and RALP**
and its basic properties in **Section 4. RALP, unlike**
ordinary ALPs, is guaranteed to compute bounded solutions. We also briefly describe a homotopy algorithm for solving RALP, which exhibits anytime behavior by gradually increasing the norm of feature weights. To develop methods that automatically select features with generalization guarantees, we propose general sampling bounds in **Section 5. These**
sampling bounds, coupled with the homotopy method, can automatically choose the complexity of the features to minimize over-fitting. Our experimental results in Section 6 **show that the proposed approach**
with large feature sets is competitive with LSPI when performed even with small feature spaces hand selected for standard benchmark problems. **Section 7** concludes with future work and a more detailed relationship with other methods.

## 2. Framework And Notation

In this section, we formally define Markov decision processes and linear value function approximation.

A Markov Decision Process is a tuple (S, A**, P, r, γ**),
where S **is the possibly infinite set of states, and** A
is the finite set of actions. P : S × S × A 7→ [0, **1] is** the transition function, where P(s
′, s, a**) represents the**
probability of transiting to state s
′from state s**, given**
action a. The function r : S × A 7→ R **is the reward**
function, and γ is the discount factor. Pa and ra are used to denote the probabilistic transition matrix and reward vector for action a.

We are concerned with finding a value function v that maps each state s ∈ S to the expected total γ**discounted reward for the process. Value functions can**
be useful in creating or analyzing a policy π : **S ×A →**
[0, 1] such that for all s ∈ S,Pa∈A π(s, a**) = 1. The**
transition and reward functions for a given policy are denoted by Pπ and rπ**. The value function update for**
a policy π is denoted by Lπ**, and the Bellman operator**
is denoted by L**. That is:**

$$L_{\pi}v=\gamma P_{\pi}v+r_{\pi}\qquad\qquad L v=\operatorname*{max}_{\pi\in\Pi}L_{\pi}v.$$
$Lv^*=v^*\,$. 
The optimal value function v
∗**satisfies** Lv∗ = v
∗.

We focus on linear value function approximation for discounted infinite-horizon problems, in which the value function is represented as a linear combination of nonlinear basis functions (vectors)**. For each state**
s, we define a vector φ(s**) of features. The rows of the**
basis matrix Φ correspond to φ(s**), and the approximation space is generated by the columns of the matrix.**
That is, the basis matrix Φ, and the value function v are represented as:

$$\Phi=\left(\begin{array}{c c c}{{-}}&{{\phi(s_{1})^{\mathsf{T}}}}&{{-}}\\ {{}}&{{}}&{{}}\\ {{}}&{{\vdots}}&{{}}\end{array}\right)\qquad v=\Phi w.$$

This form of linear representation allows for the calculation of an approximate value function in a lowerdimensional space, which provides significant computational benefits over using a complete basis; if the number of features is small, this framework can also guard against overfitting noise in the samples.

Definition 1. A value function, v, is **representable** if v **∈ M ⊆** R
|S|, where M **= colspan (Φ). The set of**
ǫ-transitive-feasible **value functions is defined for** ǫ ≥ 0 as follows: K(ǫ) = {v ∈ R
|S| v ≥ Lv − ǫ1**. Here** 1 is a vector of all ones. A value function is transitivefeasible when v ≥ Lv **and the set of transitive-feasible**
functions is defined as K = K**(0).**
Notice that the optimal value function v
∗is transitivefeasible, and that M **is a linear space.**

## 3. Approximate Linear Programming

The approximate linear programming (ALP) framework is an approach for calculating a value function approximation for large MDP with a set of features Φ
that define a linear space M **(Schweitzer & Seidmann,** 1985; de Farias & Van Roy, **2003). The ALP takes the** following form:

$$\operatorname*{min}_{v\in{\mathcal{M}}}\quad\sum_{s\in{\mathcal{S}}}\rho(s)v(s)$$ s.t. $$r(s,a)+\gamma\sum_{s^{\prime}\in{\mathcal{S}}}P(s^{\prime},s,a)v(s^{\prime})\leq v(s)$$

where ρ **is a distribution over the initial states and**
the constraints are for all ( P
s, a) ∈ (S, A**); that is**
s∈S ρ(s**) = 1. To ensure feasibility, one of the**
features is assumed to be constant. Therefore, in