The Convergence of TD(MYAMPERSANDlambda;) for General MYAMPERSANDlambda;.
The method of temporal differences (TD) is one way of making consistent predictions about the future. This paper uses some analysis of Watkins (1989) to extend a convergence theorem due to Sutton (1988) from the case which only uses information from adjacent time steps to that involving information from arbitrary ones.It also considers how this version of TD behaves in the face of linearly dependent representations for statesdemonstrating that it still converges, but to a different answer from the least mean squares algorithm. Finally it adapts Watkins' theorem that \cal Q-learning, his closely related prediction and action learning method, converges with probability one, to demonstrate this strong form of convergence for a slightly modified version of TD.
Introduction
Many systems operate in temporally extended circumstances, for which whole sequences
of states rather than just individual ones are important. Such systems may frequently have
to predict some future outcome, based on a potentially stochastic relationship between it
and their current states. Furthermore, it is often important for them to be able to learn
these predictions based on experience.
Consider a simple version of this problem in which the task is to predict the expected
ultimate terminal values starting from each state of an absorbing Markov process, and for
which some further random processes generate these terminating values at the absorbing
states. One way to make these predictions is to learn the transition matrix of the chain and
the expected values from each absorbing state, and then solve a simultaneous equation
in one fell swoop. A simpler alternative is to learn the predictions directly, without first
learning the transitions.
The methods of temporal differences (TD), first defined as such by Sutton [16, 17], fall
into this simpler category. Given some parametric way of predicting the expected values
of states, they alter the parameters to reduce the inconsistency between the estimates
from one state and the estimates from the next state or states. This learning can happen
incrementally, as the system observes its states and terminal values. Sutton [17] proved
some results about the convergence of a particular case of a TD method.
Many control problems can be formalised in terms of controlled, absorbing, Markov pro-
cesses, for which each policy, ie mapping from states to actions, defines an absorbing
Markov chain. The engineering method of dynamic programming (DP) [4] uses the predictions
of the expected terminal values as a way of judging and hence improving policies,
and TD methods can also be extended to accomplish this. As discussed extensively by
Watkins [19] and Barto, Sutton and Watkins [3], TD is actually very closely related to DP
in ways that significantly illuminate its workings.
This paper uses Watkins' insights to extend Sutton's theorem from a special case of TD,
which considers inconsistencies only between adjacent states, to the general case in which
arbitrary states are important, weighted exponentially less according to their temporal
distance. It also considers what TD converges to if the representation adopted for states
is linearly dependent, and proves that one version of TD prediction converges with
probability one, by casting it in the form of Q-learning.
Some of the earliest work in temporal difference methods was due to Samuel [14, 15]. His
checkers (draughts) playing program tried to learn a consistent function for evaluating
board positions, using the discrepancy between the predicted values at each state based
on limited depth games-tree searches, and the subsequently predicted values after those
numbers of moves had elapsed. Many other proposals along similar lines have been made;
Sutton acknowledged the influence of Klopf [9, 10] and in [17] discusses Holland's bucket
brigade method for classifier systems [8], and a procedure by Witten [22]. Hampson [6, 7]
presented empirical results for a quite similar navigation task to the one described by
Barto, Sutton and Watkins [3]. Barto, Sutton and Anderson [2] described an early TD
system which learns how to balance an upended pole, a problem introduced in a further
related paper by Michie and Chambers [11]. Watkins [19] also gave further references.
The next section defines TD(-), shows how to use Watkins' analysis of its relationship
with DP to extend Sutton's theorem, and makes some comments about unhelpful state
representations. Section 3 looks at Q-learning, and uses a version of Watkins' convergence
theorem to demonstrate in a particular case the strongest guarantee known for the
behaviour of TD(0).
Sutton [17] developed the rationale behind TD methods for prediction, and proved that
TD(0), a special case with a time horizon of only one step, converges in the mean for
observations of an absorbing Markov chain. Although his theorem applies generally, he
illustrated the case in point with anexample of the simple random walkshown in figure ??.
Here, the chain always starts at state D, and moves left or right with equal probabilities
from each state until it reaches the left absorbing barrier A or the right absorbing barrier
G. The problem facing TD is estimating the probability it absorbs at the right hand barrier
rather than the left hand one, given any of the states as a current location.
Insert figure 1 about here
The raw information available to the system is a collection of sequences of states and
terminal locations generated from the random walk - it initially has no knowledge of the
transition probabilities. Sutton described the supervised least mean squares (LMS) [21]
technique, which works by making the estimates of the probabilities for each place visited
on a sequence closer to 1 if that sequence ended up at the right hand barrier, and closer
to 0 if it ended up at the left hand one. He showed that this technique is exactly TD(1),
one special case of TD, and contrasted it with TD(-) and particularly TD(0), which tries
to make the estimate of probability from one state closer to the estimate from the next,
without waiting to see where the sequence might terminate. The discounting parameter
- in TD(-) determines exponentially the weights of future states based on their temporal
distance - smoothly interpolating between which only the next state is relevant,
the LMS case, for which all states are equally weighted. As described in the
introduction, it is its obeisance to the temporal order of the sequence that marks out TD.
The following subsections describe Sutton's result for TD(0) and separate out the algorithm
from the vector representation of states. They then show how Watkins' analysis provides
the wherewithal to extend it to TD(-)and finally re-incorporate the original representation.
2.1 The Convergence Theorem
Following Sutton [17], consider the case of an absorbing Markov chain, defined by sets
and values:
T terminal states
non-terminal states
vectors representing non-terminal states.
expected terminal value from state j
probabilities of starting at state i,
where P
The payoff structure of the chain shown in figure ?? is degenerate, in the sense that the
values of the terminal states A and G are deterministically 0 and 1 respectively. This
makes the expected value from any state just the probability of absorbing at G.
The estimation system is fed complete sequences x of observation vectors,
together with their scalar terminal value z. It has to generate for every non-terminal state
a prediction of the expected value E[zji] for starting from that state. If the transition
matrix of the Markov chain were completely known, these predictions could be computed
as:
Again, following Sutton, let [M] ab
denote the ab th entry of any matrix M, [u] a
denote the
a th component of any vector u, Q denote the square matrix with components [Q] ab =
denote the vector whose components are [h] a =
a 2 N . Then from equation (1):
(2)
As Sutton showed, the existence of the limit in this equation follows from the fact that Q
is the transition matrix for the non-terminal states of an absorbing Markov chain, which,
with probability one will ultimately terminate.
During the learning phase, linear TD(-) generates successive vectors w -
changing
after each complete observation sequence.
as the prediction
Here and subsequently, a superscript - is used to indicate a TD(-based estimator.
of the terminal value starting from state i, at stage n in learning. Then, during one such
sequence,
are the intermediate predictions of these terminal values, and, abusing
notation somewhat, define also
z, the observed terminal value. Note that in
[17], Sutton used P n
according to:
where ff is the learning rate.
Sutton showed that TD(1) is just the normal LMS estimator [21], and also proved that the
following theorem:
Theorem T For any absorbing Markov chain, for any distribution of starting
probabilities - i such that there are no inaccessible states, for any outcome
distributions with finite expected values - z j , and for any linearly independent
set of observation vectors fx i ji 2 Ng, there exists an ffl ? 0 such that, for all
positive ff ! ffl and for any initial weight vector, the predictions of linear TD(-)
(with weight updates after each sequence) converge in expected value to the
ideal predictions (2); that is, if w -
n denotes the weight vector after n sequences
have been experienced, then
lim
is true in the case that - = 0. This paper proves theorem T for general -.
2.2 Localist Representation
Equation (3) conflates two issues; the underlying TD(-) algorithm and the representation
of the prediction functions V -
n . Even though these will remain tangled in the ultimate
proof of convergence, it is beneficial to separate them out, since it makes the operation of
the algorithm clearer.
Consider representing V -
n as a look-up table, with one entry for each state. This is equivalent
to choosing a set of vectors x i for which just one component is 1 and all the others
are 0 for each state, and no two states have the same representation. These trivially satisfy
the conditions of Sutton's theorem, and also make the wn easy to interpret, as each
component is the prediction for just one state. Using them also prevents generalisation.
For this representation, the terms rwn V -
in the sum
just reduce to counting the number of times the chain has visited each state, exponentially
weighted in recency by -. In this case, as in the full linear case, these terms do not depend
on n, only on the states the chain visits. Define a characteristic function for state j:
and the prediction function V -
n (i) as the entry in the look-up table for state i at stage n
during learning. Then equation (3) can be reduced to its elemental pieces
in which the value for each state is updated separately.
To illustrate this process, consider the punctate representation of the states B, C, D, E and
F in figure ??: 3
A
If the observed sequence is D; C; D; E; F; E; F; G, then the sums
after each step are:
@-
A
and component i in this sum is clearly
at time t.
3 States A and G are absorbing and so are not represented.
2.3 Contraction Mappings
Watkins [19] showed that a fruitful way of looking at TD estimators is through dynamic
programming and its associated contraction mappings. The method starts from the
current prediction function Vn (i); 8i 2 N , shows how to define a whole collection of
statistically better estimators Vn+1 (i); 8i 2 N based on an observed sequence, and then
uses for TD(-) a linear combination of these estimators. Except where explicitly noted,
this section follows Watkins exactly - the equations developed have their exact analogues
for the linear representation, as will be seen in subsection 2.5.
Imagine the chain starts at some state i 0 , and runs forward through states ultimately
absorbing. Define the r-step estimate of i 0 as either the estimate Vn (i r ) of state i r ,
if the chain has not absorbed after r steps and so i r 2 N , or the observed terminal value z
of the sequence, if the chain has absorbed before this time.
Formally, define the random variables
Vn (i 1
z otherwise
Vn
z otherwise
Vn (i r
z otherwise (5)
is the first state accessed by the Markov chain in one particular sequence starting
from is the second and so on, and z is the observed terminal value if the chain gets
absorbed before time step r is reached. These are random variables, since they depend on
the particular sequence of states which will be observed. Naturally, they also depend on
the values Vn (i).
The point of these is that if the chain absorbs after completing s steps from i 0 , then each
of the V r
, for r - s will be based on the terminal value provided by the world, rather
than one derived from the 'bootstraps' Vn (i). V r
should therefore on average to be more
accurate than Vn , and so can be used incrementally to improve it. This can be shown by
looking at the difference between E
and E[zji 0 ], the ideal predictions.
Here:
tr2T
Vn (i r ) (6)
whereas it can easily be shown that
tr2T
Therefore,
Watkins actually treated a slightly different case, in which the target values of the predictors
are based on discounted future values whose contribution diminishes exponentially
with the time until they happen. In this case it is easier to see how the reduction in error
is brought about. His analogue of equation was:
is the discount factor. Since P
as Q is the matrix of a Markov
chain, Watkins could guarantee that
which provides a (weak) guarantee that the error of V r
n will be less than that of Vn .
The non-discounted case, when different. Here, for some initial states
there is a non-zero probability that the chain will absorb before finishing r steps. In
this case, the value of V r
, being z, will be unbiased, and so should provide for error
reduction. Even if the chain does not absorb, its value can be no further from what
it should be than is the most inaccurate component of Vn . Although there is no error
reduction due to fl, it is guaranteed that
with inequality for all those states from which it is possible to absorb within r steps.
This does not ensure that
since the maximum could be achieved, pathologically, at a state fromwhich it is impossible
to absorb in only r steps. However, the estimates for the states that are within r steps of
absorption will, on average, improve, and this should, again on average, filter back to the
other states.
Watkins demonstrated that TD(-) is based on a weighted average of the V a
. Consider
which is also a valid estimator of the terminal value starting at i 0 . He points out that in
choosing the value of -, there is a trade off between the bias caused by the error in Vn ,
and the variance of the real terminal value z. The higher -, the more significant are the V r
for higher values of r, and the more effect the unbiased terminal values will have. This
leads to higher variance and lower bias. Conversely, the lower -, the less significant are
the contributions from higher values of r, and the less the effect of the unbiased terminal
values. This leads to smaller variance and greater bias.
It remains to be shown that TD(-) is indeed based on this combination estimator. Expanding
out the sum in equation (10),
Vn (i 0 Vn (i
Vn (i 1
Vn (i 2
defining Vn (i s
The whole point of defining V -
is so that it can be used to make V more accurate. The
obvious incremental update rule to achieve this has
Vn+1 (i 0 Vn (i
Vn (i 0 )
From equation (11) it is apparent that the changes to Vn (i 0 ) involve summing future values
of Vn (i t+1 Vn (i t ) weighted by powers of -. Again following Watkins, these differences
can be calculated through an activity trace based on the characteristic functions - i (t) that
were defined earlier as a way of counting how often and how recently the chain has
entered particular states. Using index t for the members of the observed sequence, the
on-line version of the TD(-) rule has
For the problem that Sutton treated, the change to Vn is applied off-line, after a complete
sequence through the chain. Therefore, if the states through which the chain passes on one
sequence are i absorbs with terminal value Vn (i m
and Vn+1 is the new estimator after experiencing the sequence, then
Vn+1 (i 0 Vn (i
ff [Vn (i t+1 Vn (i t )]
Vn+1 (i 1 Vn (i 1
ff [Vn (i t+1 Vn (i t )]
Vn+1 (i Vn (i Vn (i
summing over terms where i
). Note that these expressions are exactly
the same as the TD(-) weight change formula in equation (4).
Thus, the actual TD(-) algorithm is based on the exponentially weighted sum defined in
equation (10) of the outcomes of the V r
random variables. Themean contraction properties
of these variables will therefore determine the mean contraction properties of the overall
TD(-) estimator.
2.4 Linear Representation
The previous subsection considered the TD(-) algorithm isolated from the representation
Sutton used. Although a number of different representations might be employed, the
simplest is the linear one he adopted. Identifying the vectors x with the states they
represent
Vn wn :x
where wn is the weight vector at stage n of learning.
The basic algorithm is concerned with the V -
predictor random variables rather than how
their values can be used to change the initial predictor Vn . Under the new representation,
equation (12) no longer makes sense since the states cannot be separated in the appropriate
manner. Rather, the information about the error has to be used to update all the weights
on which it depends. The appropriate formula, derived from the delta-rule is
Vn (i 0 )
rwn Vn (i 0 )
weighting the error due to state i 0 by the vector representation of i 0 . Then the equivalent
of equation (13) is just Sutton's main TD(-) equation (3).
More sophisticated representations such as kd-trees (see [13] for a review) or CMACs
may lead to faster learning and better generalisation, but each requires a separate
convergence proof. [5] compares the qualities of certain different representations for
Barto, Sutton and Watkins' grid task [3].
2.5 The Proof of Theorem T
The strategy for proving theorem T is to follow Sutton [17] in considering the expected
value of the new prediction weight vector given the observation of a complete sequence,
and to follow Watkins in splitting this change into the components due to the equivalents
of the V r random variables, and then summing them. Mean error reduction over iterations
will be assured by the equivalent of equation (9) for the linear representation.
Define the V r
:;: random variables as in equation (5) as
z otherwise
where x i are identified with the states in the observed sequence, w r
n is the current weight
vector defining the estimated terminal values, and z is the actual value. Then, after
observing the whole sequence, w r
n is updated as:
visited
Vn (i)] rwn Vn (i)
visited
An exact parallel of Sutton's proof procedure turns out to apply to w r . Define j s
ij as the
number of times the s-step transition
occurs, for any intermediate states x kt 2 N . The sum in equation (14) can be regrouped
in terms of source and destination states of the transitions:
ff
z
where z j indicates that the terminal value is generated from the distribution due to state
j, and the extra terms are generated by the possibility that, from visiting any x i 2 N , the
chain absorbs before taking r further steps.
Taking expected values over sequences, for i 2 N
ik q kj for
ik q kj for
where d i is the expected number of times the Markov chain is in state i in one sequence.
For an absorbing Markov chain, it is known that the dependency of this on the probabilities
- i of starting in the various states is:
Substituting into equation (15), after taking expectations on both sides, noting that the
dependence of E[w r
n
n is linear, and using -
w to denote expected values, a close
relation of equation (6) emerges for the linear representation:
z
Define X to be the matrix whose columns are x i , so [X] ab = [x a and D to be the diagonal
ab d a , where ffi ab is the Kronecker delta. Remembering that h
and converting to matrix form,
since X
as this covers all the possible options for r\Gammastep moves from state i.
Define the correct predictions [- e   then also, from equation (2),
e
where the sum converges since the chain is absorbing. This is another way of writing
equation (7).
Multiplying equation (17) on the left by X T ,
Subtracting -
e   from both sides of the equation, and noting that from equation (18)
this gives the update rule, which is the equivalent of
equation
e
e
e
The Watkins construction of TD(-) developed in equation (10) in the previous section
reveals that, starting from w r
Therefore, since
e
io h
e
e
w - are the expected weights from the TD(-) procedure. The sum
converges since
then the truth of theorem T will be shown if it can be demonstrated that 9ffl ? 0 such that
e
!1, and all the estimates
will tend to be correct.
Almost of all of Sutton's proof of this in [17] applies mutatis mutandis to the case that - 6= 0,
always provided the crucial condition holds that X has full rank. For completeness, the
entire proof is given in the appendix. Overall it implies that the expected values of the
estimates will converge to their desired values as more sequences are observed under the
conditions stated in theorem T.
2.6 Non-Independence of the x i
In moving from Watkins' representation-free proof to Sutton's treatment of the linear
case, one assumption was that the x i , the vectors representing the states, were indepen-
dent. If they are not, so that matrix X does not have full rank, the proof breaks down.
is still positive, however X T XD
will
no longer have a full set of eigenvalues with positive real parts, since the null subspace
is not empty. Any non-zero member of this is an eigenvector with eigenvalue 0 of
Saying what will happen to the expected values of the weights turns out to be easier than
understanding it. Choose a basis:
with being a basis for Y.
Then the proof in the appendix applies exactly to b that is there exists some
lim
Also, h
by the definition of Y.
Writing
e
then
e
and so
XD
e
To help understand this result, consider the equivalent for the LMS rule, TD(1). There
XD
e
and so, since D is symmetric,
@
e
e
e
e
by equation (21). For weights w, the square error for state i is
, and the
expected number of visits to i in one sequence is d i . Therefore the quadratic form
e
e
is just the loaded square error between the predictions at each state and their desired
values, where the loading factors are just the expected frequencies with which the Markov
chain hits those states. The condition in equation (24) implies that the expected values of
the weights tend to be so as to minimise this error.
This does not happen in general for - 6= 1. Intuitively, the trade-off between bias and
variance has returned. For the case where X is full rank, Sutton shows that it is harmless
to use the inaccurate estimates from the next state x i t+1 :w to criticise the estimates for the
current state x i t :w. Where X is not full rank, these successive estimates become biased
on account of what might be deemed their 'shared' representation. The amount of extra
bias is then related to the amount of sharing and the frequency with which the transitions
happen from one state to the next.
Formalising this leads to a second issue; the interaction between the two statistical processes
of calculating the mean weight and calculating the expected number of transitions.
Comparing equations (20) and (21), one might expect
lim
@
e
However, the key step in proving equation (24) was the transition between equations (22)
and (23), which relied on the symmetry of D. Since Q is not in general symmetric, this
will not happen. Defining
@
@w
e
e
e
all that will actually happen is that g( -
Although the behaviour described by equation (25) is no more satisfactory than that
described by equation (26), it is revealing to consider what happens if one attempts to
arrange for it to hold. This can be achieved through 'completing' the derivative, ie by
having a learning rule whose effect is
e
e
The Q T term effectively arranges for backwards as well as forwards learning to occur, so
that not only would state i t adjust its estimate to make it more like state i t+1 , but also state
would adjust its estimate to make it more like state i t .
Werbos [20] and Sutton (personal communication) both discussed this point in the context
of the gradient descent of TD(-) rather than its convergence for non-independent x i .
Werbos presented an example based on a learning technique very similar to TD(0), in
which completing the derivative in this manner makes the rule converge away from
the true solution. He faulted this procedure for introducing the unhelpful correlations
between the learning rule and the random moves from one state to the next which were
mentioned above. He pointed out the convergence in terms of functions g in equation (26)
in which the w 0 weights are fixed.
Sutton presented an example to help explain the result. At first sight, augmenting TD(-)
seems quite reasonable; after all it could quite easily happen by random chance of the
training sequences that the predictions for one state are more accurate than the predictions
for the next at some point. Therefore, training the second to be more like the first would
be helpful. However, Sutton pointed out that time and choices always move forward,
not backwards. Imagine the case shown in figure ??, where the numbers over the arrows
represent the transition probabilities, and the numbers at the terminal nodes represent
terminal absorbing values.
Insert figure 2 about here
Here, the value of state A is reasonably 1=2, as there is 50% probability of ending up at
either Y or Z. The value of state B, though should be 1, as the chain is certain to end up at
Y. Training forwards will give this, but training backwards too will make the value of B
tend to 3=4. In Werbos' terms, there are correlations between the weights and the possible
transitions that count against the augmented term. Incidentally, this result does not affect
TD(1), because the training values, being just the terminal value for the sequence, bear no
relation to the transitions themselves, just the number of times each state is visited.
Coming back to the case where X is not full rank. TD(-) for - 6= 1 will still converge, but
away from the 'best' value, to a degree that is determined by the matrix
3 Convergence with Probability One
Sutton's proof and the proofs in the previous section accomplish only the nadir of stochastic
convergence, viz convergence of the mean, rather than the zenith, viz convergence with
probability one. Watkins [19] proved convergence with probability one for a form of prediction
and action learning he called Q-learning. This section shows that this result can
be applied almost directly to the discounted predictive version of TD(0), albeit without
the linear representation, and so provides the first strong proof for a temporal difference
method.
Like dynamic programming (DP), Q-learning combines prediction and control. Consider
a controlled, discounted, non-absorbing Markov-process, ie one in which at each state
there is a finite set of possible actions a 2 A. Taking one action leads to an
immediate reward, which is a random variable r i (a) whose distribution depends on both
i and a, and a stochastic transition according to a Markov matrix P ij (a) for j 2 N . If an
agent has some policy -(i) 2 A, which determines which action it would perform at state
defining the value of i under - as V - (i), this satisfies:
where fl is the discount factor. Define the Q value of state i and action a under policy -
as:
which is the value of taking action a at i followed by policy - thereafter. Then the theory
of DP [4] implies that a policy which is as least as good as - is to take the action a   at state
i such that a  b)g, and to follow - in all other states. In this fact lies
the utility of the Q values. For discounted problems, it turns out that there is at least one
optimal policy -   ; define Q
a).
Q-learning is a method of determining Q   , and hence an optimal policy, based on exploring
the effects of actions at states. Consider a sequence of observations (i n ; an
the process at state i n is probed with action an , taking it to state j n and giving reward z n .
Then define recursively:
an ,
Qn (i; a) otherwise (27)
for any starting values Q 0 (i; a), where Un (j n b)g. The ff n are a set of
learning rates that obey standard stochastic convergence criteria:X
a) is the k th time that i and an = a. Watkins [19] proved that if, in
addition, the rewards are all bounded, then, with probability one:
lim
Consider a degenerate case of a controlled Markov process in which there is only one
action possible from every state. In that case, the Q - , V - , and the (similarly defined)
U - values are exactly the same and equal to Q   , and equation (27) is exactly the on-line
form of TD(0) for the case of a non-absorbing chain in which rewards (ie the terminal
values discussed above in the context of absorbing Markov chains) arrive from every state
rather than just some particular set of absorbing states. Therefore, under the conditions of
Watkins' theorem, the on-line version of TD(0) converges to the correct predictions, with
probability one.
Although clearly a TD procedure, there are various differences between this and the one
described in the previous section. Here, learning is on-line, that is the V(= Q) values
are changed for every observation. Also, learning need not proceed along an observed
sequence - there is no requirement that j so uncoupled or disembodied
moves can be used. 4 The conditions in equation (28) have as a consequence that every
state must be visited infinitely often. Also note that Sutton's proof, since it is confined to
showing convergence in the mean, works for a fixed learning rate ff, whereas Watkins', in
common with all other stochastic convergence proofs, requires ff n to tend to 0.
Also, as stated, the Q-learning theorem only applies to discounted, non-absorbing, Markov
chains, rather than the absorbing ones with of the previous section.
4 This was one of Watkins' main motivations, as it allows his system to learn about the effects of actions
it believes to be sub-optimal.
the important r -
ole in Watkins' proof of bounding the effect of early Qn values. It is fairly
easy to modify his proof to the case of an absorbing Markov chain with as the
ever increasing probability of absorption achieves the same effect. Also, the conditions
of Sutton's theorem imply that every non-absorbing state will be visited infinitely often,
and so it suffices to have one set of ff i that satisfy the conditions in (28) and apply them
sequentially for each visit to each state in the normal running of the chain.
Conclusions
This paper has used Watkins' analysis of the relationship between temporal difference (TD)
estimation and dynamic programming to extend Sutton's theorem that TD(0) prediction
converges in the mean to the case of theorem T; TD(-) for general -. It also demonstrated
that if the vectors representing the states are not linearly independent, then TD(-) for
converges to a different solution from the least means squares algorithm.
Further, it has applied a special case of Watkins' theorem that Q-learning, his method of
incremental dynamic programming, converges with probability one, to show that TD(0)
using a localist state representation, also converges with probability one. This leaves
open the question of whether TD(-), with punctate or distributed representations, also
converges in this manner.


Appendix

Existence of appropriate ff
Defining
it is necessary to show that there is some ffl such that for
In
the case that (for which this formula remains correct), and X has full rank, Sutton
proved this on pages 26-28 of [17], by showing successively that D(I \Gamma Q) is positive, that
has a full set of eigenvalues all of whose real parts are positive, and finally
that ff can thus be chosen such that all eigenvalues of I \Gamma ffX T XD(I \Gamma Q) are less than 1 in
modulus. This proof requires little alteration to the case that - 6= 0, and its path will be
followed exactly.
The equivalent of D(I \Gamma Q) is D
. This will be positive definite,
according to a lemma by Varga [18] and an observation by Sutton, if
can be shown to be strictly diagonally dominant with positive diagonal entries. This is
the part of the proof that differs from Sutton, but even here, its structure is rather similar.
Then
since Q is the matrix of an absorbing Markov chain, and so Q r has no diagonal elements
- 1. Therefore S r has positive diagonal elements.
Also, for i 6= j,
since all the elements of Q, and hence also those of Q r , are positive.
In this case, S r is be strictly diagonally dominant if, and only if, P
strict
inequality for some i.
where equation (29) follows from equation (16), equation (30) holds since
and equation (31) holds since P
1, as the chain is absorbing, and [Q s
Also, there exists at least one i for which - i ? 0, and the inequality is strict for that i.
strictly diagonally dominant for all r - 1,
-
is strictly diagonally dominant too, and therefore D
is positive
definite.
The next stage is to show that X T XD
has a full set of eigenvalues
all of whose real parts are positive. X T X, D and
are all non-
singular, which ensures that the set is full. Let / and u be any eigenvalue-eigenvector
pair, with
where '   ' indicates the conjugate transpose. This implies that
Re
Re (/(Xv)   Xv)
or equivalently,
a
b:
Since the right side (by positive definiteness) and (Xv)   Xv are both strictly positive, the
real part of / must be strictly positive too.
Furthermore, u must also be an eigenvector of
since
Therefore, all the eigenvalues of I \Gamma ffX T XD
are of the
positive AE. Take
for all eigenvalues /, and then all the eigenvalues 1 \Gamma ff/ of the iteration matrix are
guaranteed to have modulus less than one. By another theorem of Varga [18]
lim
0:



--R

A new approach to manipulator control: the Cerebellar Model Articulation Controller (CMAC).
Neuronlike elements that can solve difficult learning problems.
Learning and sequential decision making.
Applied Dynamic Programming.
Reinforcing Connectionism: Learning the Statistical Way.
A Neural Model of Adaptive Behavior.
Connectionistic Problem Solving: Computational Aspects of Biological Learning.
Escaping brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems
Brain Function and Adaptive Systems - A Heterostatic Theory
The Hedonistic Neuron: A Theory of Memory
BOXES: An experiment in adaptive control.
Efficient Memory-based Learning for Robot Control
Efficient algorithms with neural network behaviour.
Some studies in machine learning using the game of checkers.
Some studies in machine learning using the game of checkers II: Recent Progress.
Temporal Credit Assignment in Reinforcement Learning.
Learning to predict by the methods of temporal difference.
Matrix Iterative Analysis.
Learning from Delayed Rewards.
Consistency of HDP applied to a simple reinforcement learning problem.
Adaptive Signal Processing.
An adaptive optimal controller for discrete-time Markov environments
--TR

--CTR
Claude-Nicolas Fiechter, Efficient reinforcement learning, Proceedings of the seventh annual conference on Computational learning theory, p.88-97, July 12-15, 1994, New Brunswick, New Jersey, United States
Fernando J. Pineda, Mean-field theory for batched TD (&lgr;), Neural Computation, v.9 n.7, p.1403-1419, Oct. 1, 1997
Vladislav B. Tadi, Asymptotic analysis of temporal-difference learning algorithms with constant step-sizes, Machine Learning, v.63 n.2, p.107-133, May       2006
Satinder Singh , Peter Dayan, Analytical Mean Squared Error Curves for Temporal DifferenceLearning, Machine Learning, v.32 n.1, p.5-40, July 1998
Vladislav Tadi, Convergence analysis of temporal-difference learning algorithms with linear function approximation, Proceedings of the twelfth annual conference on Computational learning theory, p.193-202, July 07-09, 1999, Santa Cruz, California, United States
Satinder Singh , Tommi Jaakkola , Michael L. Littman , Csaba Szepesvri, Convergence Results for Single-Step On-PolicyReinforcement-Learning Algorithms, Machine Learning, v.38 n.3, p.287-308, March 2000
Vladislav Tadi, On the Convergence of Temporal-Difference Learning with Linear Function Approximation, Machine Learning, v.42 n.3, p.241-267, March 2001
Peter Auer , Philip M. Long, Structural Results About On-line Learning Models With and Without Queries, Machine Learning, v.36 n.3, p.147-181, Sept. 1999
Kazunori Iwata , Kazushi Ikeda , Hideaki Sakai, The asymptotic equipartition property in reinforcement learning and its relation to return maximization, Neural Networks, v.19 n.1, p.62-75, January 2006
John W. Sheppard, Colearning in Differential Games, Machine Learning, v.33 n.2-3, p.201-233, Nov./Dec. 1998
David Choi , Benjamin Roy, A Generalized Kalman Filter for Fixed Point Approximation and Efficient Temporal-Difference Learning, Discrete Event Dynamic Systems, v.16 n.2, p.207-239, April     2006
Craig Boutilier, Planning, learning and coordination in multiagent decision processes, Proceedings of the 6th conference on Theoretical aspects of rationality and knowledge, March 17-20, 1996, The Netherlands
Florentin Wrgtter , Bernd Porr, Temporal Sequence Learning, Prediction, and Control: A Review of Different Models and Their Relation to Biological Mechanisms, Neural Computation, v.17 n.2, p.245-319, February 2005
temporal differences;reinforcement learning;asynchronous dynamic programming