Regularization and Feature Selection in
Least-Squares Temporal Difference Learning

J. Zico Kolter
Andrew Y. Ng
Computer Science Department, Stanford University, CA 94305

Abstract
We consider the task of reinforcement learning with linear value function approximation.
Temporal difference algorithms, and in particular the Least-Squares Temporal Difference (LSTD) algorithm, provide a method
for learning the parameters of the value function, but when the number of features is large
this algorithm can over-fit to the data and iscomputationally expensive. In this paper, we
propose a regularization framework for the
LSTD algorithm that overcomes these difficulties. In particular, we focus on the caseof l1 regularization, which is robust to irrelevant features and also serves as a method forfeature selection. Although the l1 regularized LSTD solution cannot be expressed as aconvex optimization problem, we present analgorithm similar to the Least Angle Regression (LARS) algorithm that can efficiently
compute the optimal solution. Finally, wedemonstrate the performance of the algorithm experimentally.

1. Introduction
We consider the task of reinforcement learning (RL)in large or infinite state spaces. In such domains it is
not feasible to represent the value function explicitly,and instead a common strategy is to employ function
approximation to represent the value function using
some parametrized class of functions. In particular, weconsider linear value function approximation, wherethe value function is represented as a linear combination of some set of basis functions. For this task, theTemporal Difference (TD) family of algorithms (Sutton, 1988), and more specifically the Least-Squares TD
Appearing in Proceedings of the 26 th International Conference on Machine Learning, Montreal, Canada, 2009. Copyright 2009 by the author(s)/owner(s).

kolter@cs.stanford.edu
ang@cs.stanford.edu(LSTD) algorithms (Bradtke & Barto, 1996; Boyan,
2002; Lagoudakis & Parr, 2003), provide a method forlearning the value function using only trajectories generated by the system. However, when the number offeatures is large compared to the number of training
samples, these methods are prone to over-fitting andare computationally expensive.
In this paper we propose a regularization framework
for the LSTD family of algorithms that allows us to
avoid these problems. We specifically focus on thecase of l1 regularization, which results in sparse solutions and therefore serves as a method for feature
selection in value function approximation. Our framework differs from typical applications of l1 regularization in that solving the l1 regularized LSTD problem
cannot be formulated as a convex optimization problem; despite this, we show that a procedure similar to
the Least Angle Regression (LARS) algorithm (Efron
et al., 2004) is able to efficiently compute the optimal
solution.
The rest of this paper is organized as follows. In Section 2 we present preliminaries and review the LSTD
algorithm. Section 3 contains the main contributionof this paper: we present a regularized version of the
LSTD algorithm and give an efficient algorithm forsolving the l1 regularized case. In Section 4 we present
experimental results. Finally, in Section 5 we discuss
relevant related work and conclude the paper in Section 6.

2. Background and Preliminaries
A Markov Decision Process (MDP) is a tuple(S, A, P, d, R, γ), where S is a set of states; A is a setof actions; P : S × A × S → [0, 1] is a state transition
probability function where P (s, a, s′ ) denotes the probability of transitioning to state s′ when taking actiona from state s; d is a distribution over initial states;
R : S → R is a reward function; and γ ∈ [0, 1] is a
discount factor. For simplicity of presentation, we willRegularized Least-Squares Temporal Difference Learning

assume that S and A are finite, though potentially verylarge; this merely permits us to use matrix rather thanoperator notation, though the results here hold withminor technicalities in infinite state spaces. A policy
is π : S → A is a mapping from states to actions.
The notion of a value function is of central importance in reinforcement learning; in our setting, for agiven policy π, the value of a state s is defined as the
expected discounted sum of rewards obtained whenπstarting
P∞ int state s and following policy π: V (s) =E[ t=0 γ R(st )|s0 = s, π]. It is well-known that thevalue function must obey Bellman’s equationX
P (s′ |s, π(s))V π (s′ )V π (s) = R(s) + γ
s′such that the resulting value function “approximately”
satisfies the Bellman equation. Although R + γP π Φw
may not lie in the span of the bases, we can find theclosest approximation to this vector that does lie in the
span of the bases by solving the least-squares problem,
min kΦu − (R + γP π Φw)k2D

(2)

u∈Rk

where D is a non-negative diagonal matrix indicating a
distribution over states.1 The TD family of algorithms
in general, including LSTD, attempt to find a fixed
point of the above operation; that is, they attempt tofind w such thatw = f (w) = arg min kΦu − (R + γP π Φw)k2D .
u∈Rk

(3)

or expressed in vector form
V π = R + γP π V π(1)where V, R ∈ R|S| are vectors containing the state values and rewards respectively, and P π ∈ R|S|×|S| isa matrix encoding the transitions probabilities of theπ= P (s′ = j|s = i, π(s)). If both the repolicy π, Pi,jwards and transition probabilities are known, then we
can solve for the value function analytically by solving
the linear system V π = (I − γP π )−1 R.
However, in the setting that we consider in this paper,
the situation is significantly more challenging. First,
we consider a setting where the transition probability
matrix is not known, but where we only have accessto a trajectory, a sequence of states s0 , s1 , . . . wheres0 ∼ d and si+1 ∼ P (si , π(si )). Second, as mentioned
previously, we are explicitly interested in the setting
where the number of states is large enough that thevalue function cannot be expressed explicitly, and so
instead we must resort to function approximation. We
focus on the case of linear function approximation, i.e.,V π (s) ≈ wT φ(s)where w ∈ Rk is a parameter vector and φ(s) ∈ Rk is
a feature vector corresponding to the state s. Again
adopting vector notation, this can be written V π ≈ Φw
where Φ ∈ R|S|×k is a matrix whose rows contains thefeature vectors for every state. Unfortunately, whenapproximating V π in this manner, there is usually no
way to satisfy the Bellman equation (1) exactly, because the vector R + γP π Φw may lie outside the spanof the bases Φ.

We now briefly review the LSTD algorithm. We firstnote that since P π is unknown, and since the full Φmatrices are too large to form anyway, we cannot solve(3) exactly. Instead, given a trajectory consisting ofstates, actions, and next-states, (si , ai , s′i ), i = 1 . . . mcollected from the MDP of interest, we define the sample matrices






r1
φ(s′1 )Tφ(s1 )T
 . 




..
..
′
Φ̃ ≡ 
 , R̃ ≡  ..  .
 , Φ̃ ≡ 
.
.
rm

(4)
Given these samples, LSTD finds a fixed point of theapproximationw = f˜(w) = arg min kΦ̃u − (R̃ + γ Φ̃′ w)k2 .
u∈Rk

(5)

It is straightforward to show that with probability one,as the number of samples m → ∞, the fixed point of
the approximation (5) equals the fixed point of the true
equation (3), where the diagonal entries of D are equal
to the distribution over samples (Bradtke & Barto,
1996).
In addition, since the minimization in (5) contains onlya Euclidean norm, the optimal u can be computed
analytically asf˜(w) = u⋆ = (Φ̃T Φ̃)−1 Φ̃T (R̃ + γ Φ̃′ w).
Now we can find the fixed point w = f˜(w) by simply
solving a linear systemw = (Φ̃T Φ̃)−1 Φ̃T (R̃ + γ Φ̃′ w)
−1Φ̃T R̃ = Ã−1 b̃= Φ̃T (Φ̃ − γ Φ̃′ )2.1. Review of Least-Squares Temporal
Difference Methods
The Least-Squares Temporal Difference (LSTD) algorithm presents a method for finding the parameters w

φ(s′m )Tφ(sm )T1

The squared norm k · k2D is defined as kxk2D = xT Dx.

Regularized Least-Squares Temporal Difference Learningwhere we define Ã ∈ Rk×k and b̃ ∈ Rk as
Ã ≡ Φ̃T (Φ̃ − γ Φ̃′ ) =mXφ(si ) (φ(si ) − γφ(s′i ))i=1

Tb̃ ≡ Φ̃ R̃ =

m
X

T

(6)

respectively (or possibly a combination of the two).
With this modification, it is no longer immediately
clear if there exist fixed points w = f˜(w) for all β, and
it is also unclear how we may go about finding this
fixed point, if it exists.

φ(si )ri .

i=1

Given a collection of samples, the LSTD algorithm
forms the Ã and b̃ matrices using above formula, thensolves the k×k linear system w = Ã−1 b̃. When k is relatively small solving this linear system is very fast, so
if there are a sufficiently large number of samples to estimate these matrices, the algorithm can perform very
well. In particular LSTD has been demonstrated tomake more efficient use of samples than the standard
TD algorithm, and it requires no tuning of a learning rate or initial guess of w (Bradtke & Barto, 1996;
Boyan, 2002).
Despite its advantages, LSTD also has several drawbacks. First, if the number of basis functions is verylarge, then LSTD will require a prohibitively large
number of samples in order to obtain a good estimateof the parameters w; if there is too little data available,
then it can over-fit significantly or fail entirely — forexample, if m < k, then the matrix Ã will not be fullrank. Furthermore, since LSTD requires storing andinverting a k × k matrix, the method is not feasible if
k is large (there exist extensions to LSTD that alleviate this problem slightly from a run-time perspective(Geramifard et al., 2006), but the methods still requirea prohibitively large amount of storage).

3. Temporal Difference with
Regularized Fixed Points
In this section we present a regularization frameworkthat allows us to overcome the difficulties discussed in
the previous section. While the general idea of applying regularization for feature selection and to avoid
over-fitting is of course a common theme in machinelearning and statistics, applying it to the LSTD algorithm is challenging due to the fact that this algorithm
is based on finding a fixed-point rather than optimizing some convex objective.
We begin by augmenting the fixed point function of the
LSTD algorithm (5) to include a regularization term1f˜(w) = arg min kΦ̃u − (R̃ + γ Φ̃′ w)k2 + βν(u) (7)ku∈R 2
where β ∈ [0, ∞) is a regularization parameter andν : Rk → R+ is a regularization penalty function — inthis work, we specifically consider l2 and l1 regularization corresponding to ν(u) = 12 kuk22 and ν(u) = kuk1

3.1. l2 Regularization
The case of l2 regularization is fairly straightforward,
but we include it here for completeness. When ν(u) =1
2
2 kuk2 , the optimal u can again be solved for in closed
form, as in standard LSTD. In particular, it is straightforward to show thatf˜(w) = (Φ̃T Φ̃ + βI)−1 Φ̃T (R̃ + γ Φ̃′ w)
so the fixed point w = f˜(w) can be found by
−1
w = Φ̃T (Φ̃ − γ Φ̃′ ) + βI
Φ̃T R̃ = (Ã + βI)−1 b̃.
Clearly, such a fixed point exists with probability 1,
since A + βI is invertible unless one of the eigenvaluesof A is equal to −β, which constitutes a set of measure zero. Indeed, many practical implementations of
LSTD already implement some regularization of thistype to avoid the possibility of singular Ã. However,this type of regularization does not address the concerns from the previous section: we still need to form
and invert the entire k × k matrix, and as we will show
in the next section, this method still performs poorly
when the number of samples is small compared to thenumber of features.
3.2. l1 Regularization
We now come to the primary algorithmic contributionof the paper, a method for finding the fixed point of(7) when using l1 regularization, ν(u) = kuk1 . Since l1
regularization is known to produce sparse solutions, it
can both allow for more efficient implementation andbe effective in the context of feature selection — many
experimental and theoretical results confirm this assertion in the context of supervised learning (Tibshirani,
1996; Ng, 2004). To give a brief overview of the mainideas in this section, it will turn out that finding the l1
regularized fixed point cannot be expressed as a convex optimization problem. Nonetheless, it is possible
to adapt an algorithm known as Least Angle Regression (LARS) (Efron et al., 2004) to this task.
Space constrains preclude a full discussion, but briefly,
the the LARS algorithm is a method for solving l1
regularized problem least-squares problems
min kAw − bk2 + βkwk1 .
w

Although the l1 objective here is non-differentiable,ruling out an analytical solution like the l2 regular-

Regularized Least-Squares Temporal Difference Learning

ized case, it turns out that the optimal solution w canbe built incrementally, updating one element of w at
a time, until we reach the exact solution of the optimization problem. This is the basic idea behind the
LARS algorithm, and in the remainder of this section,
we will show how this same intuition can be applied
to find l1 regularized fixed points of the TD equation.
To begin, we transform the l1 optimization problem (7)into a set of optimality conditions, following e.g. Kim
et al. (2007) — these optimality conditions can be derived from sub-differentials, but the precise derivationis unimportant−β ≤ (Φ˜T ((R̃ + γ Φ̃′ w) − Φ̃u))i ≤ β
T

∀i

′

(Φ̃ ((R̃ + γ Φ̃ w) − Φ̃u))i = β ⇒ ui ≥ 0(Φ̃T ((R̃ + γ Φ̃′ w) − Φ̃u))i = −β ⇒ ui ≤ 0(8)−β < (Φ̃T ((R̃ + γ Φ̃′ w) − Φu))i < β ⇒ ui = 0.

Algorithm LARS-TD({si , ri , s′i }, φ, β, γ)Parameters:{si , ri , s′i }, i = 1, . . . , m: state transition andreward samples
φ : S → Rk value function basis
β ∈ R+ : regularization parameterγ ∈ [0, 1]: discount factor
Initialization:
1. Set w ←P0 and initialize the correlation vectormc ← i=1 φ(si )ri .
2. Let {β̄, i} ← maxj {|cj |} and initialize theactive set I ← {i}.
While (β̄ > β):
1. Find update direction ∆wI :∆wI ← Ã−1
I,I sign(cI )Pm
TÃI,I ≡ i=1 φI (si ) (φI (si ) − γφI (s′i ))2. Find step size to add element
to theo active set:nc −β̄Since the optimization problem (7) is convex, these
conditions are both necessary and sufficient for the
global optimality of a solution u — i.e., if we can findsome u satisfying these conditions, then it is a solution
to the optimization problem. Therefore, in order fora point w to be a fixed point of the equation (7) withl1 regularization, it is necessary and sufficient that theabove equations hold for u = w — i.e., the following
optimality conditions must hold−β ≤ (Φ̃T R̃ − Φ̃T (Φ̃ − γ Φ̃′ )w)i ≤ β∀i(Φ̃T R̃ − Φ̃T (Φ̃ − γ Φ̃′ )w)i = β ⇒ wi ≥ 0(Φ̃T R̃ − Φ̃T (Φ̃ − γ Φ̃′ )w)i = −β ⇒ wi ≤ 0(9)−β < (Φ̃T R̃ − Φ̃T (Φ̃ − γ Φ̃′ )w)i < β ⇒ wi = 0.
It is also important to understand that the substitutions performed here are not the same as solving
the optimization problem (7) with the additional constraint that u = w; rather, we first find the optimality
conditions of the optimization problem and then substitute u = w. Indeed, because Φ̃T (Φ̃ − γ Φ̃′ ) is not
symmetric, the optimality conditions (9) do not correspond to any optimization problem, let alone a convex
one. Nonetheless, as we will show, we are still able tofind solutions to this optimization problem. The resulting algorithm is very efficient, since we form only
those rows and columns of the Ã matrix corresponding
to non-zero coefficients in w, which is typically sparse.

c +β̄

j
j
{α1 , i1 } ← min+j ∈I/
dj −1 , dj +1
PmTd ≡ i=1 φ(si ) (φI (si ) − γφI (s′i )) ∆wI
3. Find step size to reachnzero coefficient:owj{α2 , i2 } ← min+j∈I − ∆wj
4. Update weights, β̄, and correlation vector:
wI ← wI + α∆wI , β̄ ← β̄ − α, c ← c − αdwhere α = min{α1 , α2 , β̄ − β}.
5. Add i1 or remove i2 from active set:S
If (α1 < α2 ), I ← I {i1 }else, I ← I − {i2 }.
Return w.

Figure 1. The LARS-TD algorithm for l1 regularized
LSTD. See text for description and notation.

set I = {i1 , . . . , i|I| }, corresponding to the non-zerocoefficients w. At each step, the algorithm obtains
a solution to the optimality conditions (9) for someβ̄ ≥ β, and continually reduces this bound until it isequal to β.
We describe the algorithm inductively. Suppose thatat some point during execution, we have the index set
I and corresponding coefficients wI which satisfy the
optimality conditions (9) for some β̄ > β — note thatthe vector w = 0 is guaranteed to satisfy this condition
for some β̄. We define the “correlation coefficients” (orjust “correlations”) c ∈ Rk asc ≡ Φ̃T R̃ − Φ̃T (Φ̃ − γ Φ̃′ )w = Φ̃T R̃ − Φ̃T (Φ̃I − γ Φ̃′I )w

We call our algorithm LARS-TD to highlight the connection to LARS and give pseudo-code for the algorithm in Figure 1.2 The algorithm maintains an active

where for a vector or matrix xI denotes the rows of x
corresponding to the indices in I.

2
Here and in the text min+ denotes the minimum taken
only over non-negative elements. In addition {x, i} ← minindicates that x should take the value of the minimum element, while i takes the value of the corresponding index.

Regularized Least-Squares Temporal Difference Learning

By the optimality conditions, we know that cI = ±β̄
and that |ci | < β̄ for all i ∈/ I. Therefore, when updating w we must ensure that all the cI terms are adjusted
equally, or the optimality conditions will be violated.
This leads to the update direction−1∆w = Φ̃TI (Φ̃I − γ Φ̃′I )sign(cI )where sign(cI ) denotes the vector of {−1, +1} entries
corresponding to the signs of cI . Given this update
direction for w, we take as large a step in this direction
as possible until some ci for i ∈/ I also reaches thebound. This step size can be found analytically as
ci − β̄ ci + β̄+,,
α1 = mindi − 1 di + 1
i∈I
/
where
d ≡ Φ̃T (Φ̃I − γ Φ̃′I )∆w(here d indicates how much a step in the direction ∆w
will affect the correlations c). At this point ci is at thebound, so we add i to the active set I.
Lastly, the optimality conditions requires that for alli, the signs of the coefficients agree with the signs of
the correlations. To prevent this condition from being
violated we also look for any points along the update
direction where the sign of any coefficient changes; thesmallest step-size for which this occurs is given bywi
α2 = min+ −i∈I∆wi(if no such positive elements exist, then we take α2 =∞). If α1 < α2 , then no coefficients would change signduring our normal update, so we proceed as before.
However, if α2 < α1 , then we update w with a step sizeof α2 , and remove the corresponding zero coefficientfrom the active set. This completes the description of
the LARS-TD algorithm.
Computational complexity and extensions to
LSTD(λ) and LSTDQ. One iteration of the LARSTD algorithm presented above has time complexity
O(mkp3 ) — or O(mkp2 ) if we use an LU factorization update/downdate to invert the ÃI,I matrix —and space complexity O(k + p2 ) where p is the number of non-zero coefficients of w, m is the number ofsamples, and k is the number of basis functions. In
practice, the algorithm typically requires a number of
iterations that is about equal to some constant factor
times the final number of active basis functions, so thetotal time complexity of an efficient implementation
will be approximately O(mkp3 ). The crucial property
here is that the algorithm is linear in the number ofbasis function and samples, which is especially important in the typical case where p ≪ m, k.

For the sake of clarity, the algorithm we have presented
so far is a regularized generalization of the LSTD(0)algorithm. However, our algorithm can be extended
to LSTD(λ) (Boyan, 2002) by the use of eligibility
traces, or to LSTDQ (Lagoudakis & Parr, 2003), whichlearns state-action value functions Q(s, a). Space constraints preclude a full discussion, but the extensions
are straightforward.
3.3. Correctness of LARS-TD, P -matrices, andthe continuity of l1 fixed points
The following theorem shows that LARS-TD finds an
l1 regularized fixed point under suitable conditions.
Due to space constraints, the full proof is presented in
an appendix, available in the full version of the paper(Kolter & Ng, 2009). However, the algorithm is notguaranteed to find a fixed point for the specified valueof β in every case, though we have never found thisto be a problem in practice. A sufficient condition for
LARS-TD to find a solution for any value of β is forÃ = Φ̃T (Φ̃ − γ Φ̃′ ) to be a P -matrix 3 as formalized by
the following theorem.
Theorem 3.1 If Ã = Φ̃T (Φ̃ − γ Φ̃′ ) is a P -matrix,
then for any β ≥ 0, the LARS-TD algorithm finds
a solution to the l1 regularized fixed-point optimality
conditions (9).
Proof (Outline) The proof follows by a similar inductive argument as we used to describe the algorithm,
but requires two conditions that we show to hold whenÃ is a P -matrix. First, we must guarantee that when
an index i is added to the active set, the sign of its
coefficient is equal to the sign of its correlation. Second, if an index i is removed from the active set, itscorrelation will still be at bound initially and so its
correlation must be decreased at a faster rate than thecorrelations in the active set.

A simple two-state Markov chain, shown in Figure2(a), demonstrates why LARS-TD may not find thesolution when Ã is not a P -matrix. Suppose that werun the LARS-TD algorithm using a single basis function Φ = [10.0 2.0]T , γ = 0.95, and uniform sampling3
A matrix A ∈ Rn×n is a P -matrix if all its principle
minors (the determinants of sub-matrices formed by taking
some subset of the rows and columns) are positive (Horn &Johnson, 1991). The class of P -matrices is a strict supersetof the class of positive definite (including non-symmetricpositive definite) matrices, and we use the former in order
to include various cases not covered by the positive definite
matrices alone. For example, in the case that the bases are
simply the identity function or a grid, ΦT (Φ − γP π Φ) =(I−γP ), and while this matrix is often not positive definite,
it is always a P -matrix.

Regularized Least-Squares Temporal Difference Learning
7

Average discounted reward

6.5

(a)

6
5.5
5

L1 Regularization
L2 Regularization

4.5
4
3.5
3
2.5
2
0

1000

2000

3000

4000

5000

Number of samples

Figure 2. (a) The MDP used to illustrate the possibility
that LARS-TD does not find a fixed point. (b) Plot indicating all the fixed points of the regularized TD algorithm
given a certain basis and sampling distribution. (c) The
fixed points for the same algorithm when the sampling is
on-policy.

D = diag(0.5, 0.5). We can then compute A and b
A = ΦT D(Φ − γP π Φ) = −5.0,

(a)

(c)

b = ΦT DR = 5.0,

7
6.5

Average discounted reward(b)

L1 Regularization
L2 Regularization

6
5.5
5
4.5
4
3.5
3
2.5

There are several ways to ensure that Ã is a P -matrix
and, as mentioned, we have never found this to bea problem in practice. First, as shown in (Tsitsiklis& Roy, 1997), when the sampling distribution is onpolicy in that D equals the stationary distribution of
the Markov chain, A (and therefore Ã, given enoughsamples) is positive definite and therefore a P -matrix;
in our chain example, this situation is demonstrated in
Figure 2(c). However, even when sampling off-policy
we can also ensure that Ã is a P -matrix by additionallyadding some amount of l2 regularization; this is known
as elastic net regularization (Zou & Hastie, 2005). Finally, we can check if the optimality conditions are violated at each step along the regularization path andsimply terminate if continuous path exists from thecurrent point to the LSTD solution. This general technique of stopping a continuation method if it reaches
a discontinuity has been proposed in other settings aswell (Corduneanu & Jaakkola, 2003).

4. Experiments
4.1. Chain domain with irrelevant features
We first consider a simple discrete 20-state “chain”
MDP, proposed in (Lagoudakis & Parr, 2003), to

2
0

500

1000

1500

2000

2500

3000

3500

4000

3500

4000

Number of irrelevant features(b)
Runtime per LSTD/LARS−TD iteration (sec)so A matrix is not a P -matrix. Figure 2(b) shows all
the fixed points for the l1 regularized TD equation (7).
Note that there are multiple fixed point for a given
value of β, and that there does not exist a continuous
path from the null solution w = 0 to the LSTD solution
w = 1; this renders LARS-TD unable to find the fixed
points for all β.

8070

L1 Regularization
L2 Regularization

60
50
40
30
20
10
0
0

500

1000

1500

2000

2500

3000

Number of irrelevant features(c)Figure 3. (a) Average reward versus number of samples for1000 irrelevant features on the chain domain. (b) Averagereward versus number of irrelevant features for 800 samples. (c) Run time versus number of irrelevant features for
800 samples.

demonstrate that l1 regularized LSTD can cope withmany irrelevant features. The MDP we use consistsof 20 states, two actions, left and right, and a reward
of one at each of the ends of the chain. To represent
the value function, we used six “relevant” features —five RBF basis functions spaced evenly across the domain and a constant term — as well as some numberof irrelevant noise features, just containing Gaussian
random noise for each state. To find the optimal policy, we used the LSPI algorithm with the LARS-TD
algorithm, modified to learn the Q function. Regular-

Regularized Least-Squares Temporal Difference Learning

ization parameters for both the l1 and l2 cases were
found by testing a small number of regularization parameters on randomly generated examples, though thealgorithms performed similarly for a wide range of parameters. Using no regularization at all — i.e., standard LSPI — performed worse in all cases. All results
above were averaged over 20 runs, and we report 95%
confidence intervals.
As shown in Figures 3(a) and 3(b) both l2 and l1 regularized LSTD perform well when there are no irrelevant features, but l1 performs significantly better using
significantly less data in the presence of many irrelevant features. Finally, Figure 3(c) shows the run-timeof one iteration of LSTD and LARS-TD. For 2000 irrelevant features, the runtime of LARS-TD is morethan an order of magnitude less than that of l2 regularized LSTD, in addition to achieving better performance; furthermore, the time complexity of LARS-TD
is growing roughly linearly in the total number of features, confirming the computational complexity boundpresented earlier.
4.2. Mountain car
We next consider the classic “mountain car” domain(Sutton & Barto, 1998), consisting of a continuous
two-dimensional state space. In continuous domains,practitioners frequently handcraft basis functions torepresent the value function; a common choice is to useradial basis functions (RBFs), which are evenly spaced
grids of Gaussian functions over the state space. However, picking the right grid, spacing, etc, of the RBFs
is crucial to obtain good performance, and often takes
a significant amount of hand-tuning. Here we use themountain car domain to show that our proposed l1 regularization algorithm can alleviate this problem significantly: we simply use many different sets of RBFs in
the problem, and let the LARS-TD algorithm pick themost relevant. In particular, we used two-dimensional
grids of 2, 4, 8, 16, and 32 RBFs, plus a constantoffset, for a total of 1365 basis functions. We thencollected up to 500 samples by executing 50 episodes
starting from a random state and executing a random
policy for up to 10 time steps. Using only this data, weused policy iteration and off-policy LSTD/LARS-TD
to find a policy.
Table 1 summarizes the results: despite the fact that
we have a relatively small amount of training data andmany basis functions, LARS-TD is able to find a policythat successfully brings the car up the hill 100% of thetime (out of 20 trials). As these policies are learned
from very little data, they are not necessarily optimal:
they reach the goal in an average of 142.25 ± 9.74
steps, when starting from the initial state. However,Table 1. Success probabilities and run times for LARS-TD
and l2 LSTD on the mountain car.

Algorithm
Success %Iteration Time (sec)

LARS-TD
100% (20/20)
1.20 ± 0.27l2 LSTD
0% (0/20)
3.42 ± 0.04

in contrast, LSTD with l2 regularization or with noregularization at all is never able to find a successfulpolicy.

5. Related WorkIn addition to the work on least-squares temporal difference methods as well as l1 regularization methods
that we have mentioned already in this paper, there
has been some recent work on regularization and feature selection in Reinforcement Learning. For instance, (Farahmand et al., 2009) consider a regularized version of TD-based policy iteration algorithms,
but only specifically consider l2 regularization — their
specific scheme for l2 regularization varies slightly fromours, but the general idea is quite similar to the l2 regularization we present. However, the paper focuses
mainly on showing how such regularization can guarantee theoretical convergence properties for policy iteration, which is a mainly orthogonal issue to the l1
regularization we consider here.
Another class of methods that bear some similarity
to our own are recent methods for feature generation
based on the Bellman error (Menache et al., 2005;
Keller et al., 2006; Parr et al., 2007). In particular (Parr et al., 2007) analyze approaches that continually add new basis functions to the current set,
based upon their correlation with the Bellman residual. The comparison between this work and our own isroughly analogous to the comparison between the classical “forward-selection” feature-selection method andl1 based feature selection methods; these two general
methods are compared in the supervised least-squares
setting by Efron et al. (2004), and the l1 regularized
approach is typically understood to have better statistical estimation properties.
The algorithm presented in (Loth et al., 2007) bears
a great deal similarity to our own, as they also workwith a form of l1 regularization. However, the detailsof the algorithm are quite different: the authors do
not consider fixed points of a Bellman backup, but instead just optimize the distance to the standard LSTD
solution plus an additional regularization term. The
solution then loses all interpretation as a fixed point,
which has proved very important for the TD solution,
and also loses much of the computational benefit ofRegularized Least-Squares Temporal Difference Learning

LARS-TD, since, using the notation from Section 3,
they need to compute entire columns of the ÃT Ã matrix. Therefore, it is unclear whether this approach
can be implemented efficiently (i.e., in time and memory linear in the number of features). Furthermore,this previous work focuses mainly on kernel features,
so that the approach is more along the lines of those
discussed in the next paragraph, where the primary
goal is selecting a sparse subset of the samples.
There has also been work on feature selection andsparsification in kernelized RL, but this work is only
tangentially related to our own. For instance, in (Xuet al., 2007), the authors present a kernelized versionof the LSPI algorithm, and also include a techniqueto sparsify the algorithm — a similar approach is alsopresented in (Jung & Polani, 2006). However, the motivation and nature of their algorithm is quite different
from ours and not fully comparable: as they are working in the kernel domain, the primary concern is obtaining sparsity in the samples used in the kernelized
solution (similar to support vector machines), and they
use a simple greedy heuristic, whereas our algorithm
obtains sparsity in the features using a regularization
formulation.

6. Conclusion
In this paper we proposed a regularization framework
for least-squares temporal difference learning. In particular, we proposed a method for finding the temporal
difference fixed point augmented with an l1 regularization term. This type of regularization is an effective
method for feature selection in reinforcement learning,
and we demonstrated this experimentally.

Acknowledgments
This work was supported by the DARPA Learning Locomotion program under contract number FA8650-05C-7261. We thank the anonymous reviews for helpfulcomments. Zico Kolter is partially supported by an
NSF Graduate Research Fellowship.

(2004). Least angle regression. Annals of Statistics, 32,
407–499.
Farahmand, A. M., Ghavamzadeh, M., Szepesvari, C., &Mannor, S. (2009). Regularized policy iteration. Neural
Information Processing Systems.
Geramifard, A., Bowling, M., & Sutton, R. (2006). Incremental least-squares temporal difference learning. Proceedings of the American Association for Artitical Intelligence.
Horn, R. A., & Johnson, C. R. (1985). Matrix analysis.
Cambridge University Press.
Horn, R. A., & Johnson, C. R. (1991). Topics in matrix
analysis. Cambridge University Press.
Johnson, C. R., & Smith, R. L. (2005). Closure properties. In F. Zhang (Ed.), The schur complement and its
applications. Springer.
Jung, T., & Polani, D. (2006). Least squares svm for leastsquares td learning. Proceedings of the European Conference on Artificial Intelligence.
Keller, P. W., Mannor, S., & Precup, D. (2006). Automatic
basis function construction for approximate dynamic
programming and reinforcement learning. Proceedingsof the International Conference on Machine Learning.
Kim, S., Koh, K., Lustig, M., Boyd, S., & Gorinevsky,
D. (2007). An interior-point method for large-scale l1regularized least squares. IEEE Journal on Selected Topics in Signal Processing, 1, 606–617.
Kolter, J. Z., & Ng, A. Y. (2009).
Regularization and feature selection in least-squares temporal difference learning (full version).
Available at
http://ai.stanford.edu/˜kolter.
Lagoudakis, M., & Parr, R. (2003). Least-squares policy iteration. Journal of Machine Learning Research, 4,1107–1149.
Loth, M., Davy, M., & Preux, P. (2007). Sparse temporal
difference learning using lasso. Proceedings of the IEEE
Symposium on Approximate Dynamic Programming andReinforcement Learning.
Menache, I., Mannor, S., & Shimkin, N. (2005). Basisfunction adaptation in temporal difference reinforcement
learning. Annals of Operations Research, 134.
Ng, A. (2004). Feature selection, l1 vs. l2 regularization,and rotational invariance. Proceedings of the International Conference on Machine Learning.

References

Parr, R., Painter-Wakefield, C., Li, L., & Littman, M.
(2007). Analyzing feature generation for value-function
approximation. Proceedings of the International Conference on Machine Learing.

Boyan, J. (2002). Technical update: Least-squares temporal difference learning. Machine Learning, 49, 233–246.

Sutton, R. (1988). Learning to predict by the methods of
temporal differences. Machine Learning, 3, 9–44.

Bradtke, S., & Barto, A. (1996). Linear least-squares algorithms for temporal difference learning. Machine Learning, 22, 33–57.

Sutton, R., & Barto, A. (1998). Reinforcement learning:
An introduction. MIT Press.

Corduneanu, A., & Jaakkola, T. (2003). On information
regularization. Proceedings of the Conference on Uncertainty in Artificial Intelligence.
Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R.

Tibshirani, R. (1996). Regression shrinkage and selection
via the lasso. Journal of the Royal Statistical Society B,
58, 267–288.
Tsitsiklis, J., & Roy, B. V. (1997). An analysis of temporaldifference learning with function approximation. IEEE
Transactions on Automatic Control, 42, 674–690.

Regularized Least-Squares Temporal Difference Learning
Xu, X., Hu, D., & Lu, X. (2007). Kernel-based least squares
policy iteration for reinforcement learning. IEEE Transactions on Neural Networks, 18, 973–992.
Zou, H., & Hastie, T. (2005). Regularization and variableselection via the elastic net. Journal of the Royal Statistical Society B, 67, 301–320.

A. Appendix
A.1. Proof of Theorem 3.1
As mentioned in Section 3, the proof of the correctnessof LARS-TD involves showing that two properties holdwhenever Φ̃T (Φ̃−γ Φ̃′ ) is a P -matrix. In this section we
prove both these properties. To begin, we also provea very simple lemma which shows that certain Schurcomplements of P -matrices are always positive. Thisis the fundamental property of P -matrices that allows
us to show that the conditions necessary for LARS-TD
hold.
Lemma A.1 Let A ∈ Rn×n be a P -matrix, and let
AI,I be the matrix formed by considering only somesubset I of the rows and columns of A. Furthermore,
suppose AI,I is written in block form as
AI,I =



X
vT

u
y



Proof The update direction ∆w′ given by LARS-TDis
−1∆w′ = Φ̃TI ′ (Φ̃′I ′ − γ Φ̃′I ′ )sign(cI ′ )where we note that we need not distinguish between
the correlations of the two iterations of LARS-TD,
since the sign of the correlations does not change between these two updates. The matrix Φ̃TI ′ (Φ̃I ′ − γ Φ̃′I ′ )can be written in block form as TΦ̃I (Φ̃I − γ Φ̃′I ) Φ̃TI (Φ̃i − γ Φ̃′i )Φ̃TI ′ (Φ̃I ′ − γ Φ̃′I ′ ) =Φ̃Ti (Φ̃I − γ Φ̃′I ) Φ̃Ti (Φ̃i − γ Φ̃′i )


X u
≡
vT y
so that by a standard formula for block matrix inversion (Horn & Johnson, 1985),


−1 
(X − vuT /y)−1 −X −1 u/s′TΦ̃I ′ (Φ̃I ′ − γ Φ̃I ′ )=−v T X −1 /s
1/s
where
s ≡ y − v T X −1 u.
Therefore,
∆wi′

=
=



 sign(cI )1
−v T X −1 1sign(ci )s1sign(ci ) − Φ̃Ti (Φ̃I − γ Φ̃′I )∆ws
1(sign(ci ) − di )sfor X ∈ R(|I|−1)×(|I|−1) , u, v ∈ R|I|−1 , and y ∈ R.
Then the Schur complement=y − v T X −1 u > 0.

where we use the fact that

Proof By the definition of P -matrices, A being a P matrix implies that AI,I is also a P -matrix. Positivity of the Schur complement follows from the fact thatthe set of P -matrices is closed under the Schur complement (Johnson & Smith, 2005), and from the factthat a singleton matrix is a P -matrix if and only if theelement is strictly positive.

Now we show that the two required properties hold inorder for LARS-TD to find the correct solution for any
regularization parameter.
Lemma A.2 Suppose that at some iteration, the
LARS-TD algorithm has active set I and update direction ∆w, and then adds the element S
i to the active
set, leading to a new active set I ′ = I {i} and new
update direction ∆w′ . Then if Φ̃T (Φ̃ − γ Φ̃′ ) is a P matrix, the sign of the update for coefficient i agrees
in sign with the correlation coefficient, i.e.,sign(∆wi′ ) = sign(ci ).

X −1 sign(cI ) = ∆w.
Since s is a Schur complement of the form presented
in Lemma A.1, it is positive. Therefore it is sufficient
to show that we cannot have sign(di ) = sign(ci ) and|di | > |ci |. But if this were the case, then the absolutevalue of the correlation |ci | would be decreasing at a
rate faster than the correlation of the elements in theactive set, meaning that the previous update could nothave caused element i to join the active set. Since theelement did join the active set, this shows that ∆wi′must agree in sign with ci .
Lemma A.3 Suppose that at some iteration, the
LARS-TD algorithm has active set I and update direction ∆w, and then removes the element i from theactive set, leading to a new active set I ′ = I − {i} andnew update direction ∆w′ . Then if Φ̃T (Φ̃ − γ Φ̃′ ) is a
P -matrix, the correlation ci must decrease at a rate
faster than the correlation in the new active set, i.e.,sign(d′i ) = sign(ci ),and |d′i | > 1.

Regularized Least-Squares Temporal Difference Learning

Proof The update directions ∆w and ∆w′ are given
by

 


X u
sign(cI ′ )
∆wI ′
=
∆wi
sign(ci )vT yandX∆w′ = sign(cI ′ )where, similar to the previous proof, we define


  T
X u
Φ̃I ′ (Φ̃I ′ − γ Φ̃′I ′ ) Φ̃TI ′ (Φ̃i − γ Φ̃′i ).
≡vT yΦ̃Ti (Φ̃I ′ − γ Φ̃′I ′ ) Φ̃Ti (Φ̃i − γ Φ̃′i )From the equations above we have,
X∆wI ′ + u∆wi = sign(cI ′ ) = X∆w′
so∆w′ = ∆wI ′ + X −1 u∆wi
andv T ∆wI ′ + y∆wi = sign(ci ).
Therefore,d′i= Φ̃Ti (Φ̃I ′ − γ Φ̃′I ′ )∆w′ = v T ∆w′= v T ∆wI ′ + v T X −1 u∆wi
= sign(ci ) − (y − v T X −1 u)∆wi .

By Lemma A.1, y −v T X −1 u is positive, and ∆wi musthave the opposite sign as ci because in the previous
step, wi was adjusted so as to reach zero and it musthave had sign equal to ci previously. Therefore, |d′i | >1, and it agrees in sign with ci , as required.
Given these two lemmas, the proof follows in the samemanner as the description of the LARS-TD algorithm
given in Section 3.2. In particular, from this description it should be clear that at each point time step,
LARS-TD maintains a solution that satisfies the optimality conditions for some β̄ > β. The above two lemmas show that these conditions will never be violated
when the algorithm either adds or removes an elementfrom the active set. Since the algorithm decreases β̄
at each iteration, it necessarily finds a solution of the
optimality conditions, as desired.