-
Notifications
You must be signed in to change notification settings - Fork 1
Bardtke and barto least squares temporal difference learning (lstd)
Excerpted from: Boyan, Justin. Learning Evaluation Functions for Global Optimization. Ph.D. thesis, Carnegie Mellon University, August 1998. (Available as Technical Report CMU-CS-98-152.)
**Least-Squares Temporal Difference Learning**
> * is a popular family of algorithms for approximate policy evalua-
tion in large MDPs. TD works by incrementally updating the valuefunction after each observed transition. It has two major drawbacks: itmakes inefficient use of data, and it requires the user to manually tunea stepsize schedule for good performance. For the case of linear value, the Least-Squares TD (LSTD) al-function approximations andgorithm of Bradtke and Barto [5] eliminates all stepsize parameters andimproves data efficiency.This paper extends Bradtke and Barto’s work in three significant ways.First, it presents a simpler derivation of the LSTD algorithm. Second, itgeneralizes from to arbitrary values of ; at the extreme ofthe resulting algorithm is shown to be a practical formulation of super-vised linear regression. Third, it presents a novel, intuitive interpretationof LSTD as a model-based reinforcement learning technique.1 BACKGROUNDThis paper addresses the problem of approximating the value functionin a large Markov decision process [2, 13]. This is an important subproblem of severalalgorithms for sequential decision making, including policy iteration [2] and STAGE [4].simply predicts the expected long-term sum of future rewards obtained when theprocess starts in state and follows policy until termination. This function is well-definedas long as is proper, i.e., guaranteed to terminate.1- For small Markov chains whose transition probabilities are all explicitly known, computing
is a trivial matter of solving a system of linear equations. However, in many practical- applications, the transition probabilities of the chain are available only implicitly—either in
- the form of a simulation model or in the form of an agent’s actual experience executing in
- its environment. In either case, we must compute
) solely from a collection of trajectories sampled from the chain. This is where the- TD family of algorithms applies.
- [2, 13]. For each state on each observed trajectory, TD
- efficients of
6753¥©1 ( §% #20)'&$¡¡""££ ¡¤¢Justin A. BoyanCMU Computer Science DepartmentPittsburgh, PA 15213jab@cs.cmu.edu
**Abstract**
> * TD
,of a fixed policyTD was introduced in [10]; excellent summaries may now be found in several books¤¢incrementally adjusts the co-1For improper policies,£ ¡£ ¡¤¢!- nentially reduces future rewards; however, for simplicity I will assume here that 5
6 is undiscounted.4!£ ¡¤¢¡¥¡§©¡¥§̈¦¡¥£ ¡¤¢or an approximation thereof (denotedtoward new target values. The target values depend on the parameter. At , the target at each visited state is the “Monte-Carlo return,” i.e., themay be made well-defined by the use of a discount factor that expo-- sition, the algorithm computes the scalar one-step TD error
£ )4Y # !`§&£% ¥ £X£ ¦¤44¥ £¦¤4(§¥@(£¤¢II¤¢ ̈ # H £EDF F FG(mapping states to feature vectors, END
Table 1: Ordinary TD
6
¢
and next state
. /* inner product */
for linearly approximating the undiscounted value function of a
§2¤GG0f2(
£
!¡
S
b
¥
£
. Ta-
£
7
¤
2 '
3
¤4
4
£ ¡
4
54
41
1
1
'
4
# !
§&£
% ¥ £
£ ¦¤4
3¡ 4
£ ¡
¤¢
# ! £
$"¤¢ $¤¢
# £
£
!
£ ¡
¤¢
¡
¡
£
¢
¥ £
¦¤4
¡
4
4
"
§
$¡¥
END . This is an unbiased sample
, the target value is set by a sampled one-step looka-
,
TD
)
0¥
for approximate policy evaluation:
0;
0 (or an arbitrary initial estimate)
Set
Set
Set S e
#
b
propagates
.
.
To what weights does TD
after an observed trajectory
6 2 6 2
'
£
¢
¢ '
% ¥
£ ¦£ w u
s
V
1 x Uv¥
! Y
�
�y
1 1 1 1
g
e
pD
£ £
t ¡ # s ¡ q
ciUAr¤
Choose a start state
Simulate one step of the chain, producing a reward
Set
¡ #
ih¥ @
#
fixed proper policy.
g ( F F F ( ¥
£ ¡
¤¢
£ ¡
¤¢
§¦D
¡ #
dc¥ @
, where
¡
£ ¡
¥¦£¤) a4 ' ¡
¢
W4 G4 ' ¡
V ¡
R
£ )
4
#
4
R
#
a featurizer 120()'%&$¡
§ 9 #
@
A
CB
9
8
a parameter ; and
a sequence of stepsizes for incremental coefficient updating.
.
.
do:
.
.
.
END, do:
� y
�"1
.
(1)
and zero-mean noise. The expectations are taken with respect to the distribution of
2
s
¥
t
w u
1 x Uv¥ q
g
(
( (
¥@
4 ¥
¥ £
@ S ¦¤4 S'
¥@
T¥
U4
'
¥ 4
@
9
S
§ ¥
@ P
¥@
F F F Q
G( "(
¥
@
#
8
8
8
.
6
"(
(
¡
£ ¡
¤¢
£ 4
¢
actual observed sum of future rewards
of , but may have significant variance since it depends on a long stochastic sequence of
rewards. At the other extreme,
head: . This value has lower variance—the only random component is
a single state transition—but is biased by the potential inaccuracy of the lookahead estimate
. The parameter trades off between bias and variance. Empirically, intermediate
of
values of seem to perform best [10, 13].
TD provably converges to a good approximation of when linear architectures are
used, assuming a suitable decreasing schedule of stepsizes for the incremental weight up-
dates [14]. Linear architectures—which include lookup tables, state aggregation meth-
ods, CMACs, radial basis function networks with fixed bases, and multi-dimensional poly-
nomial regression—approximate by first mapping the state to a feature vector
, and then computing a linear combination of those features,
ble 1 gives a convenient form of TD that exploits this representation. On each tran-
and apportions that error among all state features according to their respective eligibilities
. The eligibility vector may be seen as an algebraic trick by which TD
rewards backward over the current trajectory without having to remember the trajectory
, where is the time at which the current trajectory started.
Given: a simulation model for a proper policy in MDP ;
Output: a coefficient vector for which
Set
for
Set
Set
while
converge? Examining the update rule for in Table 1, it is
END have the form
D
(
¥
©§¦¤4 ¢4
¡ ̈ ̈ ̈ ¡ ¥ £
¡
explicitly. Each feature’s eligibility at time depends on the trajectory’s history and on :
not difficult to see that the coefficient changes made by TD
trajectories through the Markov chain. It is shown in [2] that is negative definite and
that the noise has sufficiently small variance, which together with the stepsize conditions
mentioned above, imply that converges to a fixed point satisfying
effect, TD solves this system of equations by performing stochastic gradient descent on
a potential function . It never explicitly represents or . The changes to
depend only on the most recent trajectory, and after those changes are made, the trajectory
and its rewards are simply forgotten. This approach, while requiring little computation per
iteration, wastes data and may require sampling many trajectories to reach convergence.
One technique for using data more efficiently is “experience replay” [6]: explicitly remem-
ber all trajectories ever seen, and whenever asked to produce an updated set of coefficients,
perform repeated passes of TD
plicit estimates of the matrix and vector (actually, estimates of a constant multiple of
.
Set .
while END, do:
§
£
¥
¦¡
§
©
̈ ̈ ©
̈
£
!
#
§
§
¥
@
#
¥
¦4
b
(
¥@
'
£
¥ £4
¦¤) ¥ £
¡a4 ' ¡ ¥ @ ¦¤4
4
4 ' ¡ § ¥@ §
4 ¢
4
¥@
T¥
U4
¥ 4
@
¥
(
@
is an unbiased estimate of . Thus, can be estimated as
§
P
#
s
%
P
¥ 4
6 2
¥
1x
4
2 THE LEAST-SQUARES TD
that TD does. However, instead of performing gradient descent, LSTD
q
s
£ ¡
¤¢
t
0. In
over all the saved trajectories until convergence. This
ALGORITHM
algorithm, or LSTD , converges to the same coefficients
builds ex-
and ), and then solves 0 directly. The actual data structures that LSTD
builds from experience are the matrix (of dimension , where is the number of
(2)
,
and . I use
Singular Value Decomposition to invert robustly [8]. The complete LSTD algorithm
is specified in Table 2.
LSTD for approximate policy evaluation:
Given: a simulation model, featurizer, and as in ordinary TD ; no stepsizes necessary.
Output: a coefficient vector for which .
Set
P
0 0 .
£
7
¤
P
s
do:
for
b
Choose a start state
and next state .
/* outer product /
. / Use SVD. */
§
£ ¡
¤¢
has dimension
.
£ ¡
¤¢
§
When , LSTD reduces precisely to Bradtke and Barto’s LSTD algorithm, which
, LSTD
£ ¢
§ ¥
¡
'
(
¡
' ¡
'
£ )
4
R
F F F Q
G( "(
@ §
(
( ¥
¥@ @
1
produces the same and that would be
£
3
%
4
¥ £
¦¤4 R
9
4
¥
#
¡
q
6 2
§
' ¥ '
1x
1 1
4
̈
̈ ©
§
£
!¡ ¥ # s
Uh¡ q
q
£
!¡
The Least-Squares TD
(compare Table 1). Note that
, and , , , and all have dimension
£ ¡
¤¢
#
technique is similar to the batch training methods commonly used to train neural networks.
However, in the case of linear function approximators, there is another way.
£
¤¢ II¤¢
̈ # H £
£
!¡
¢
¢
¥ %
¦£ V
! Y £ ¦£
1 1
̈ ̈
¥ £
¦¤¢
£ ¡
¤¢
# s q E ¡ dI# ¡ # %
features) and the vector (of dimension ):
Whenever updated coefficients are desired: Set
Table 2: A least-squares version of TD
£
!¡
4
)
! ¥
&£ £ ¦£
they derived using a different approach based on regression with instrumental variables [5].
At the other extreme, when
#
§
£ ¡
¤¢
¥
# A¡ q
s # #
After independent trajectories have been observed, is an unbiased estimate of
Simulate one step of the chain, producing a reward
Set .
Set .
Set .
Set .
£ ¡
¤¢
produced by supervised linear regression on training pairs of state features
Monte-Carlo returns (see [3] for proof). Thanks to the algebraic trick of the eligibility vec-
tors, LSTD builds the regression matrices fully incrementally—without having to store
the trajectory while waiting to observe the eventual outcome. When trajectories through
the chain are long, this provides significant memory savings over linear regression.
The computation per timestep required to update and is the same as least-squares
linear regression: , where is the number of features. LSTD must also per-
form a matrix inversion at a cost of whenever ’s coefficients are needed—in the
case of STAGE, once per complete trajectory. (If updated coefficients are required more
cost can be avoided by recursive least-squares [5] or Kalman-
frequently, then the
LSTD is more computationally expensive than incremental TD , which updates the
coefficients using only computation per timestep. However, LSTD offers several
advantages, as pointed out by Bradtke and Barto in their discussion of LSTD [5]:
Least-squares algorithms are “more efficient estimators in the statistical sense”
because “they extract more information from each additional observation.”
TD ’s convergence can be slowed dramatically by a poor choice of the stepsize
parameters . LSTD eliminates these parameters.
TD ’s performance is sensitive to
the initial estimate for . LSTD
TD is also sensitive to the ranges of the individual features. LSTD
in terms of
and model-based reinforcement learning. To begin, let us
restrict our attention to the case of a small discrete state space , over which
from simulated trajectory data would proceed as follows:
1. From the state transitions and rewards observed so far, build in memory an empirical
model of the Markov chain. The sufficient statistics of this model are as follows:
A matrix recording the observed state-transition counts:
was seen to directly follow .
A vector recording the sum of all observed one-step rewards from each state. 8
̈
§
8
s
8
¦
£ ¡
¤¢
£ ¡
¤¢
¥
¤
¥¢
8
£ ¡
#
8
£ ¡
¤¢
e D
£ ¡
¤¢
£ ¡
¤¢
£
£
!¡
£
¢ ̈
£
£
observed
.)
init , the distance between and
requires no arbitrary initial estimate.
is not.
8
8
AS MODEL-BASED REINFORCEMENT LEARNING
¤¢
can be
how many times
2. Whenever a new estimate of the value function
Bellman equations corresponding to the current empirical model. Writing
£ ¡
¤¢
̈
©
£
F
s
I%
¥ 4
the solution vector of
¥
¦
©
£
¥
1
§
¥
s
1
9
£ ¡
£ ¡
¤¢
¡
#
#
% # ¡
diag ,
(3)
This model-based technique contrasts with TD , a model-free approach to the same prob-
lem. TD does not maintain any statistics on observed transitions and rewards; it simply
£ ¡
¤¢
£ ¡
¤¢
with LSTD
is desired, solve the linear system of
values is given by
both converge to the optimal . The advantage of TD is its low computational bur-
4
§
̈
£ ¡
¤¢
£
!¡
£
¡
̈
E
£ ¡
¤¢ £
data efficiency.
LSTD
3
Before giving experimental results with LSTD , I would like to point out an interesting
connection between LSTD
represented and learned exactly by a lookup table. A classical model-based algorithm for
learning
A vector recording the number of times each state has been visited.
¤¢
#
£
#
¡¢ ̈
̈
§
Section 4 below presents experimental results comparing TD
den per step; the advantage of the classical model-based method is that it makes the most
£ ¡
¤¢
£ ¢
̈
E
£
filtering techniques [2, 3.2.2], which update on each timestep at a cost of only
updates the components of directly. In the limit, assuming a lookup-table representation,
of the available training data. The empirical advantages of model-based and model-free
reinforcement learning methods have been investigated in, e.g., [11, 7, 1].
fit in? Let us first consider the case of
Where does LSTD
means that we have one independent feature
per state: the feature vector corresponding to state 1 is
to state 2 is
£ ¥
¥
¦4
! ©£ ¦4 £ !
̈ ©
£ £
s %
¥
¦4
̈ ©
r%
£ £
s
%
£
¦ © ! ©£
£ ¡
¤¢
©
£
!¡
on the element
performs the inversion
Thus, when effectively record a model of
all the observed transitions. What about when ? Again, and record the sufficient
statistics of an empirical Markov model—but in this case, the model being captured is one
backup op-
erations. That is, the model links each state to all the downstream states that follow on
according
The lookup-table representation for
£
¤¢
£
!¡
£
¤¢
"
£ ¡
¤¢
§
§
¡
§
¡
¢
§
¥
@
#
¥ 4
4
̈
¥
@
¡
( §
0)¢
. In this case, perhaps
; corresponding
4
£
!¡
(4)
.
, the TD backups correspond to the one-step transitions,
,
, we can view the LSTD algorithm as doing these two steps:
would perform on the data.
is intractable in practical problems; in practice,
LSTD
£
as implicitly building a compressed version
and summed-reward vector :
(5)
£ ¡
¤¢
, the and matrices built by LSTD
to TD . In the case of
resulting in the equivalence described above. The opposite extreme, the case of
is also interesting: the empirical Markov model corresponding to TD ’s backups is the
operates on states only via their (linearly dependent) feature representations
¥
$¡
¥
whose single-step transition probabilities directly encode the multi-step TD
£
!¡
compressed empirical model, LSTD
¥
¥
(6)
would be equivalent to the empirical optimal coefficients
. The empirical optimal coefficients are those that would be found by building the full
uncompressed empirical model (represented by
£ ¥
£
s
#
§
¥ ¥
#
¥
" ̈
9
¥
̈! ¤ £
"
£
!¡ §
©¡¥
̈ £ s
c%
¥
¦4
£ ¢
§
©
¥ £
¦¤4
%
¡ § does in the classical technique.
each observed transition gives
£ #
©
"
§
©
s %
© , meanwhile, accumulates the statistics
; and all the rest zeroes. Summing one such sparse matrix for
. Finally, LSTD
, giving the same solution as in Equation 3.
chain where each state leads directly to absorption, and then simply computes the aver-
age Monte-Carlo return at each state. In short, if we assume a lookup-table representation
for the function
where is the
#
§
̈9 § matrix representation of the function . From the
computes the following coefficients for :
and ), using a lookup table to solve
, and then performing a least-squares
£
s
%
§
§
Clearly, the role of is to sum all the rewards observed at each state, exactly as the vector
To see this, note that the outer product in Eq. 4 is a matrix consisting of an entry of
on the single diagonal element corresponding to state ; an entry of
in row , column
£ £
¢
4 ¥ £ 4 ¢
@
¥ £
¦¤4 %
¦£
!
£ ¢ § § (
F F ( §
)2(
Ideally, these coefficients
£
£ 2)F
for that model’s value function
linear fit from the state features to the lookup-table value function:
¦4
§
"
; etc. LSTD performs the following operations upon each
̈ (7)
5
£
s
c%
© ! £ £ ! ©£
¥
¦4
£
F
̈!
£
¥
¦4
@
§
£ ¥
s
%
!
¦ © ¥
̈
compactly models all the backups that TD
£
s
c%
£
!¡
£ ¡
¤¢
#
4
£ 4 ¢
¡
£ § (
2. It solves the chain by performing a matrix inversion.
F
£
£
¥
¡
F F F ( § ( §
G)2)2(
surprisingly, it precisely duplicates the classical model-based method sketched above. The
assumed lookup-table representation for
observed transition (cf. Table 2):
1. It implicitly uses the observed simulation data to build a Markov chain. This chain
. In this case, we can view LSTD
§
¥
¡
any trajectory, and records how much influence each has on estimating
of the empirical model’s transition matrix £ F § ¡ �¢ e 6 £ 3 e ̈¥ § ¡ ( ¡ Q % ¤¢U5 This section reports experimental results comparing TD and LSTD chain illustrated in Figure 1. The chain consists of 13 states, and we seek to represent its value function compactly as a linear function of four state features as shown. In fact, this domain has been contrived so that the optimal function is exactly linear in these features: the optimal coefficients are . This condition guarantees that will converge with probability 1 to the optimal for any setting of . -3.0 -3.0 -3.0 START 11 10 3 2 12 -3.0 -3.0 -3.0 [1/2, 1/2, 0, 0] [1, 0, 0, 0] [0, 0, 1/2, 1/2] [0, 0, 3/4, 1/4] [3/4, 1/4, 0, 0] Figure 1: A simple Markov chain. Each state is represented by four features as shown. is also guaranteed convergence to the optimal , under the additional condition TD that an appropriate schedule of stepsizes is chosen. I ran each TD , where determines the initial stepsize, and determines how gradually the stepsize decreases lambda = 0.4 1 TD: a0=0.1, n0=10^6 TD: a0=0.1, n0=10^3 TD: a0=0.1, n0=10^2 0.8 TD: a0=0.01, n0=10^6 RMS error of Vpi over all states on the Markov £ !¡
¡
, because
0 so is diagonal. However, for the case of
4 EXPERIMENTAL COMPARISON OF TD
-3.0
0
-2.0
[0, 0, 0, 1]
[0, 0, 1/4, 3/4]
experiment with
P
e D . The parameter
. Figure 3 summarizes the
6
§
£ ¡
¤¢
Perfor-
mance of TD
TD: a0=0.01, n0=10^3
TD: a0=0.01, n0=10^2
Least-Squares TD
on
0.6
0.4
£
F
¡ §§
e
£
!¡
1
and LSTD
the sample domain.
Note the log scale on
the -axis. All points
0.2
100
depends critically on the stepsize schedule chosen, and that
will perform on practi-
£ ¡
¤¢
¡
6 P
#
AND LSTD
LSTD
0
£
!¡
£
!¡ ¡
£
!¡
The plots show that LSTD
¡
£
!¡
-3.0
Figure 2:
plotted represent the
average of 10 trials.
1000 10000
trajectory number
learns a good approximation to in fewer trials than any
of the TD experiments, and performs better asymptotically as well, across all values of
£
!¡
and LSTD
6
¥
£ ¢
It can be shown that Equations 6 and 7 are indeed equivalent for the case of ¡
that setting of implies that
results over six settings of .
. They also show that TD
©
¥
s
0% s
, solving the compressed empirical model does not in general produce the optimal
least-squares fit to the solution of the uncompressed model.
six different schedules of the form
over time. Figure 2 plots learning curves for the case of
varying has a relatively small effect on LSTD ’s performance. Because the sample do-
main is so small and the optimal value function is exactly linear over the available features,
these results may not be representative of how TD
cal problems. If a domain has many features and simulation data is available cheaply, then
F § ¥
¡ §©¡
(
¥
F F F (
G)Q
¥
¦£ 3
#
£ § (
¥ ( £
¦% )¤ %
£
!¡
£ ¡
¤¢
¥ ¤¢
£
£
¥
©¡
incremental methods may have better real-time performance than least-squares methods 0.01 Figure 3: Summary of results at six settings of . At each setting, seven algorithms are compared: TD (with six different stepsize schedules) and LSTD . The plotted seg- ment shows the mean RMS value function approximation error after 100 trajectories (top of segment) and 10,000 trajectories (bottom of segment). Note the log scale on the -axis. LSTD is best in all cases. LSTD has been successfully applied in the context of STAGE, a reinforcement-learning algorithm for combinatorial optimization [3]. An exciting possibility for future work is to apply LSTD problems. LSTD optimistic policy iteration [2]. Acknowledgments: Thanks to Andrew Moore and Jeff Schneider for helpful comments. References [1] C. G. Atkeson and J. C. Santamaria. A comparison of direct and model-based reinforcement learning. In International Conference on Robotics and Automation, 1997. ¢ £¡ £ !¡ £ ¡ ¤¢ £ !¡
£ ¡
¤¢
RMS error of Vpi at traj #100 and traj #10000
100
10
1
0.1
0.0 0.2 0.4
lambda
¡
TD: a0=0.1, n0=10^6
TD: a0=0.1, n0=10^3
TD: a0=0.1, n0=10^2
TD: a0=0.01, n0=10^6
TD: a0=0.01, n0=10^3
TD: a0=0.01, n0=10^2
Least-Squares TD
0.6 0.8 1.0
[12]. On the other hand, some reinforcement-learning applications have been successful
with very small numbers of features (e.g., [9, 4]), and in these situations LSTD
be superior.
£
!¡
£
!¡
should
in the context of approximation algorithms for general Markov decision
could provide an efficient alternative to TD in the inner loop of
£
!¡
£
!¡
[2] D. Bertsekas and J. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, Belmont, MA, 1996. [3] J. A. Boyan. Learning Evaluation Functions for Global Optimization. PhD thesis, Carnegie Mellon University, 1998. [4] J. A. Boyan and A. W. Moore. Learning evaluation functions for global optimization and Boolean satisfiability. In Proceed- ings of the Fifteenth National Conference on Artificial Intelligence (AAAI), 1998. [5] S. J. Bradtke and A. G. Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 22(1/2/3):33–57, 1996. [6] L.-J. Lin. Reinforcement Learning for Robots Using Neural Networks. PhD thesis, Carnegie Mellon University, 1993. [7] A. W. Moore and C. G. Atkeson. Prioritized sweeping: Reinforcement learning with less data and less time. Machine Learning, 13:103–130, 1993. [8] W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, second edition, 1992. [9] S. Singh and D. Bertsekas. Reinforcement learning for dynamic channel allocation in cellular telephone systems. In M. C. Mozer, M. I. Jordan, and T. Petsche, editors, NIPS-9, page 974. The MIT Press, 1997. [10] R. S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3, 1988. [11] R. S. Sutton. Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. In Proceedings of the Seventh International Conference on Machine Learning. Morgan Kaufmann, 1990. [12] R. S. Sutton. Gain adaptation beats least squares. In Proceedings of the 7 Yale Workshop on Adaptive and Learning Systems, pages 161–166, 1992. [13] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998. [14] J. N. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function approximation. Technical Report LIDS-P-2322, MIT, 1996. 7