Relative Loss Bounds for Temporal-Difference Learning.
Foster and Vovk proved relative loss bounds for linear regression where the total loss of the on-line algorithm minus the total loss of the best linear predictor (chosen in hindsight) grows logarithmically with the number of trials. We give similar bounds for temporal-difference learning. Learning takes place in a sequence of trials where the learner tries to predict discounted sums of future reinforcement signals. The quality of the predictions is measured with the square loss and we bound the total loss of the on-line algorithm minus the total loss of the best linear predictor for the whole sequence of trials. Again the difference of the losses is logarithmic in the number of trials. The bounds hold for an arbitrary (worst-case) sequence of examples. We also give a bound on the expected difference for the case when the instances are chosen from an unknown distribution. For linear regression a corresponding lower bound shows that this expected bound cannot be improved substantially.
Introduction
Consider the following model of temporal-difference learning: Learning
proceeds in a sequence of trials :, where at trial t,
\Gamma the learner receives an instance vector x t 2 R n ,
\Gamma the learner makes a prediction "
\Gamma the learner receives a reinforcement signal r t 2 R.
A pair called an example. The Learner tries to predict the
outcomes y t 2 R. For a fixed discount rate parameter fl 2 [0; 1), y t is
the discounted sum
s=t
of the future reinforcement signals 1 . For example, if r t is the profit of a
company in month t, then y t can be interpreted as an approximation of
the company's worth at time t. The discounted sum takes into account
that profits in the distant future are less important than short term
profits. Note that the outcome y t as defined in (1.1) is well-defined if
the reinforcement signals are bounded.
In an episodic setting one can also define the outcomes y t as finite
discounted sums. This is discussed briefly in Section 7.
A strategy that chooses predictions for the learner is called an on-line
learning algorithm. The quality of a prediction is measured with
the square loss: The loss of the learner at trial t is (y
and the
loss of the learner at trials 1 through T is
We want to compare the loss of the learner against the losses of
linear functions. A linear function is represented by a weight vector
and the loss of w at trial t is (y Ideally we want to
bound the additional loss of the learner over the loss of the best linear
predictor for arbitrary sequences of examples, i.e. we want to bound
for arbitrary T and arbitrary sequences of examples
The first sum in (1.2) is the total loss of the learner at trials 1 through
T . The argument of the infimum is the total loss of the linear function
Alternatively y t could be defined as (1 \Gamma fl)
s=t
rs , which makes y t a
convex combination of the reinforcement signals r t , r t+1 , . The alternate definition
amounts to a simple rescaling of the outcomes and predictions.
Relative Loss Bounds for Temporal-Difference Learning 3
w at trials 1 through T . Thus (1.2) is the additional total loss of the
learner over the total loss of the best linear function.
Following Vovk (1997) we also examine the more general problem of
bounding
for a fixed constant a  0. Here akwk 2 is a measure of the complexity
of w, i.e. the infimum in (1.3) includes a charge for the complexity of
the linear function. For larger values of a it is obviously easier to show
bounds on (1.3).
Bounds on (1.2) or (1.3) that hold for arbitrary sequences of examples
are called relative loss bounds. Relative loss bounds for the
temporal-difference learning setting were first shown by Schapire and
Warmuth (1996). An overview of their results is given in Section 4.
They also show how algorithms that minimize (1.2) can be used for
value function approximation of Markov processes. This is an important
problem in reinforcement learning which is also called policy evaluation.
The Markov processes can have continuously many states which are
represented by real vectors. If one wants to predict state values then
our instances x t correspond to states of the environment, if action
values are predicted then an instance corresponds to both a state of
the environment and an action of the agent. For an introduction to
reinforcement learning see Sutton and Barto (1998).
The paper is organized as follows. We discuss previously known
relative loss bounds for linear regression and for temporal-difference
learning in Sections 3 and 4. In Section 5, we propose a new second
order learning algorithm for temporal-difference learning (the TLS
algorithm), and we prove relative loss bounds for this algorithm in
Section 6. In Section 7, we adapt the TLS algorithm to the episodic
case, where the trials are divided into episodes and where an outcome
is a discounted sum of the future reinforcement signals from the same
We discuss previous second order algorithms for temporal-difference
learning in Section 8, and give lower bounds on the relative
loss in Section 9.
2. Notation and preliminaries
For is the set of n-dimensional real vectors. For m;n 2 N,
R m\Thetan is the set of real matrices with m rows and n columns. In this
paper vectors x 2 R n are column vectors and x 0 denotes the transpose
4 J. FORSTER AND M. K. WARMUTH
of x. The scalar product of two vectors w;x 2 R n is w
the Euclidean norm of a vector x 2 R n is
We recall some basic facts about positive (semi-)definite matrices:
n\Thetan is called positive definite if x
holds for all vectors x 2 R n n f0g.
n\Thetan is called positive semi-definite if
\Gamma The sum of two positive semi-definite matrices is again positive
semi-definite. The sum of a semi-definite matrix and a positive
definite matrix is positive definite.
Every positive definite matrix is invertible.
\Gamma For matrices A; B 2 R n\Thetan we write A  B if B \Gamma A is positive
semi-definite. In this case x 0 Ax  x 0 Bx for all vectors x 2 R n .
\Gamma The Sherman-Morrison formula (see Press, Flannery, Teukolsky,
holds for every positive definite matrix A 2 R n\Thetan and every vector
For example, the unit matrix I 2 R n\Thetan is positive definite and for every
vector x 2 R n the matrix xx 0 2 R n\Thetan is positive semi-definite.
To find a vector w 2 R n that minimizes the term
that appears in the relative loss (1.3) we define
k=s
Because (2.2) is convex in w, it is minimal if and only if its gradient
is zero, i.e. if and only if A t . If a ? 0, then A t is invertible and
is the unique vector that minimizes (2.2). If a
Relative Loss Bounds for Temporal-Difference Learning 5
A t might not be invertible and the equation A t might not have
a unique solution. The solution with the smallest Euclidean norm is
t is the pseudoinverse of A t . For the definition of
the pseudoinverse of a matrix see, e.g., Rektorys (1994). There it is also
shown how the pseudoinverse of a matrix can be computed with the
singular value decomposition. We give a number of properties of the
pseudoinverse A
t in the appendix.
If a ? 0, then applying the Sherman-Morrison formula (2.1) to A
t shows that
A
A
A
3. Known relative loss bounds for linear regression
First note that linear regression is a special case of our setup since
when t. The standard algorithm
for linear regression is the ridge regression algorithm which predicts
x t at trial t. Relative loss bounds for this algorithm
(similar to the bounds given in the below two theorems) have been
proven in Foster (1991), Vovk (1997) and Azoury and Warmuth (1999).
The bounds obtained for ridge regression are weaker than the ones
proven for a new algorithm developed by Vovk. We will give a simple
motivation of this algorithm and then discuss the relative loss bounds
that were proven for it.
We have seen in Section 2 that the best linear functions for trials 1
through t (i.e. the linear function that minimizes (2.2)) would make the
prediction b 0
x t at trial t. Note that via b t and A t this prediction
depends on the examples However, only the examples
and the instance x t are known to the
learner when it makes the prediction for trial t. If we set the unknown
outcome y t to zero we get the prediction b 0
This prediction
was introduced in Vovk (1997) using a different motivation. The above
motivation follows Azoury and Warmuth (1999). Forster (1999) gives an
alternate game theoretic motivation. Vovk proved the following bound
on (1.3) for his prediction algorithm.
THEOREM 3.1. Consider linear regression
any sequence of examples in R n
with the predictions " y
6 J. FORSTER AND M. K. WARMUTH
a
A T
Y
a
an
where x t;i is the i-th component of the vector x t and where
In Vovk's version of Theorem 3.1 the term X 2
n is replaced by the
larger is a bound on the supremum norms of the
instances . The last inequality in Theorem 3.1 follows from
Y
a
an
-z
an
where the first inequality holds because the geometric mean is always
smaller than the arithmetic mean.
Azoury and Warmuth (1999) and Forster (1999) give the following
refined bound for Vovk's linear regression algorithm. There only the
case a ? 0 is considered. We will show that the case a = 0 of Theorem
3.2 (i) follows from the case a ? 0 by letting a go to zero.
THEOREM 3.2. Consider linear regression
any sequence of examples in R n \Theta R.
(i) If a  0, then with the predictions "
(ii) If a ? 0, then
a
A T
for all vectors x
Relative Loss Bounds for Temporal-Difference Learning 7
Proof. We only have to show that the equality in (i) also holds for
the case a = 0. We do this by showing that both sides of the equality
are continuous in a 2 [0; 1). Because of Lemma A.2 we only have to
check that for t 2 Tg the term
is continuous in a 2 [0; 1). If x t 2 X t\Gamma1 , this again follows from Lemma
A.2. Otherwise x
. Then by Lemma A.3, the expression (3.1) is
zero for a = 0. We have to show that (3.1) converges to zero for a & 0.
For a ? 0, we can rewrite (3.1) by applying (2.5):
(b 0
The factor (b 0
converges because of Lemma A.2. Because of
Lemma A.4, the term x 0
goes to zero as a & 0. Together
this shows that (3.1) indeed goes to zero as a &
The learning algorithm of Theorem 3.1 and Theorem 3.2 is a second
order algorithm in that it uses second derivatives. There is a simpler
first order algorithm called the Widrow-Hoff or Least Mean Square algorithm
(Widrow & Stearns, 1985). This algorithm maintains a weight
vector w t 2 R n and predicts with "
. The weight vector is
updated by gradient descent. That is, w
for some learning rates
A method for setting the learning rates for the purpose of obtaining
good relative loss bounds is given in Cesa-Bianchi, Long and Warmuth
(1996) and in Kivinen and Warmuth (1997). In this method the learner
needs to know an upper bound X on the Euclidean norms of the
instances and needs to know parameters W , K such that there is a
vector w 2 R n with norm kwk  W and loss
For any such vector w the bound
holds. As noted by Vovk (1997) this bound is incomparable to the
bounds of Theorem 3.1 (See also the next section). The bound (3.3)
also holds for the ridge regression algorithm (Hassibi, Kivinen, & War-
muth, 1995). There the parameter a is set depending on W and K. We
believe that with a proper tuning of a such bounds also hold for Vovk's
8 J. FORSTER AND M. K. WARMUTH
4. Known relative loss bounds for temporal-difference
learning
For the case that the discount rate parameter fl is not assumed to be
zero, Schapire and Warmuth (1996) have given a number of different
relative loss bounds for the learning algorithm TD
The first order algorithm TD   () is essentially a generalization of the
Widrow-Hoff algorithm. It is a slight modification of the learning algorithm
TD() proposed by Sutton (1988). Schapire and Warmuth show
that the loss of TD   (1) with a specific setting of its learning rate is
(where c
and that the loss of the algorithm TD   (0) with a
specific setting of its learning rate is
for every vector w 2 R n with kwk  W and
The setting of the learning rate depends on an upper bound X on the
Euclidean norms of the instances and on W and K. The learner needs
to know these parameters in advance.
The loss of the best linear function will often grow linearly in T , e.g.
if the examples are corrupted by Gaussian noise. In this case the relative
loss bounds in (3.3), (4.1) and (4.2) will grow like
T . The second
order learning algorithm we propose for temporal-difference learning
has the advantage that the relative loss bounds we can prove for it
grow only logarithmically in T . Also, our algorithm does not need to
know parameters like K and W . However, it needs to know an upper
bound Y on the absolute values of the outcomes y t .
TD   () can be sensitive to the choice of . Another advantage of
our algorithm is that we do not have to choose a parameter like the
of the TD   () algorithm.
5. A new second order algorithm for temporal-difference
learning
In this section we propose a new algorithm for the temporal-difference
learning setting. We call this algorithm the temporal least squares
algorithm, or shorter the TLS algorithm.
Relative Loss Bounds for Temporal-Difference Learning 9
We assume that the absolute values of the outcomes y t are bounded
by some constant Y , i.e.
and assume that the bound Y , the discount rate parameter fl, and
the parameter a are known to the learner. Knowing Y the learner can
"clip" a real number y 2 R using the function
5.1. Motivation of the TLS algorithm
The new second-order algorithm for temporal-difference learning is
given in Table I. We call this algorithm the Temporal Least Squares
(TLS) algorithm. The motivation for the TLS algorithm is the same
as the motivation from Azoury and Warmuth (1999) that we gave for
Vovk's prediction for linear regression in Section 3. We will use the
equality
k=s
that holds for all s  t. The best linear function for trials 1 through t
that minimizes (2.2) would make the prediction
k=s
at trial t. We set the unknown outcome y t to zero and get the prediction
e
k=s
The TLS algorithm predicts with "
clipping
function assures that the prediction lies in the bounded range
In the following we will show that the relative loss (1.3) of
TLS is at most
J. FORSTER AND M. K. WARMUTH

Table

I. The temporal least squares (TLS) algorithm.
At trial t, the learner knows
ffl the parameters Y , fl, a,
ffl the instances
ffl the reinforcement signals
TLS predicts with
where
k=s
rk
and CY given by (5.2) clips the prediction to the interval [\GammaY; Y ].
If A t is not invertible, then the inverse A \Gamma1
of A t must be replaced
by the pseudoinverse A
and we will use this result to get worst and average case relative loss
bounds that are easier to interpret.
5.2. Implementation of the TLS algorithm
For the case a ? 0 a straightforward implementation of the TLS algorithm
would need O(n 3 ) arithmetic operations at each trial to compute
the inverse of the matrix A t . In Table II we give an implementation that
only needs O(n 2 ) arithmetic operations per trial. This is achieved by
computing the inverse of A t iteratively using the Sherman-Morrison
formula (2.5).
This implementation makes the correct predictions because at the
end of each FOR-loop
This follows from the Sherman-Morrison formula (2.5) and from the
equality
Relative Loss Bounds for Temporal-Difference Learning 11

Table

II. Implementation of TLS for a ? 0.
A inv := 1
a
I 2 R n\Thetan
z
Receive instance vector x t 2 R n
A inv := A inv \Gamma
t A inv x t
Predict with " y
Receive reinforcement signal r t 2 R
z
6. Relative loss bounds for the TLS algorithm
In the temporal-difference learning setting we do not know the outcomes
when we need to predict at trial t. So we cannot run
Vovk's linear regression algorithm which uses these outcomes in its pre-
diction. The TLS algorithm approximates Vovk's prediction by setting
the future reinforcement signals to zero (It also clips the prediction into
the range [\GammaY; Y ]). We will show that the loss of the TLS algorithm
is not much worse than the loss of Vovk's algorithm for which good
relative loss bounds are known.
We start by showing two lemmas. The first is a technical lemma. We
use it for proving the second lemma in which we bound the absolute
values of the differences between Vovk's prediction b 0
and the
unclipped prediction e
of the TLS algorithm.
LEMMA 6.1. If a  0, then s  t and any vectors x
Proof. From
it follows that
If a ? 0, then the pseudoinverses are inverses and the Sherman-Morrison
formula (2.5) shows that
A
J. FORSTER AND M. K. WARMUTH
Thus A \Gamma1
s and x 0
This proves the lemma for
a ? 0. For the case a = 0 we use Lemma A.2 and let a go to 0. 2
LEMMA 6.2.
Proof. Note that
Thus
Lemma 6:1
YT
-z
-z
now show our main result.
THEOREM 6.1. Consider temporal-difference learning with
and a  0. Let any sequence of examples in
R n \Theta R such that the outcomes y lie in the
real interval [\GammaY; Y ]. Then with the predictions "
the TLS algorithm,
Relative Loss Bounds for Temporal-Difference Learning 13
Proof. Let
. Because of y
we know that (y i.e. the relative loss bound of
Theorem 3.2 (i) also holds for the clipped predictions C Y (p t ). Thus it
suffices to show that
This holds because
4Y
Lemma 6:2
:In the next two subsections we apply Theorem 6.1 to show relative
loss bounds for the worst case and for the average case.
6.1. Worst case relative loss bound
COROLLARY 6.1. Consider temporal-difference learning with
[0; 1) and a ? 0. Let any sequence of examples
in R n \Theta R such that the outcomes y lie in the
real interval [\GammaY; Y ]. Then with the predictions "
the TLS algorithm,
a
A T
an
14 J. FORSTER AND M. K. WARMUTH
Proof. The first inequality follows from Theorem 6.1 and Theorem
3.2 (ii). The second follows from Theorem 3.1. 2
6.2. Average case relative loss bound
If we assume that the outcomes y lie in [\GammaY; Y ] and that the
instances are i.i.d. with some unknown distribution on R n , we
can show an upper bound on the expectation of the relative loss (1.2)
for trials 1 through T that only depends on n; Y; fl; T . In particular
we do not need the term akwk 2 that measures the complexity of the
vector w in the relative loss (1.3), and we do not need to assume that
the instances are bounded. To show this result we will use Theorem 6.1
and will then bound sums of terms x 0
with the
following theorem (Tr(A) is the trace of a square matrix A and dim(X)
is the dimensionality of a vector space X).
THEOREM 6.2. For any t vectors x linear span
Proof. We first look at the case a = choose
any orthonormal basis e em of X t . Then
The above can also be written as
This means that if we interpret the matrix
n\Thetan as a
linear function from R n to R n , it is the identity function on X t . The
assertion for the case a = 0 now follows from
1i;jm
1i;jm
1i;jm
Relative Loss Bounds for Temporal-Difference Learning 15
1jm
1jm
1jm
1jm
To prove the theorem for the case a ? 0 we choose an arbitrary
orthonormal basis e apply the result for a = 0 to
the vectors x 1\Gamman := First note
that
s=1\Gamman x s x 0
. From the case
we have
s=1\Gamman x 0
since the vectors fx 1\Gamman have
rank n. The equality for a ? 0 now follows from
s=1\Gamman x 0
a
t ). The first inequality for the case a ? 0
follows from aTr(A \Gamma1
COROLLARY 6.2. Consider the temporal-difference learning setting
with Assume that the instances x are
i.i.d. with unknown distribution on R n and that the outcomes y
given by (1.1) lie in the real interval [\GammaY; Y ]. Then with the predictions
of the TLS algorithm, the expectation of (1.2) is
Proof. Because of Theorem 6.1 the expected relative loss is at most
Because are i.i.d. and because of Theorem 6.2:
This proves the first inequality of Corollary 6.2. The second follows
from
J. FORSTER AND M. K. WARMUTH

Table

III. The temporal least squares (TLS) algorithm for episodic learning.
At trial t, TLS predicts with
where
rk
CY given by (5.2) clips the prediction to the interval [\GammaY; Y ] and start(k)
is the first trial in the same episode to which trial k belongs.
If A t is not invertible, then the inverse A \Gamma1
t of A t must be replaced by
the pseudoinverse A
t .
7. Episodic learning
Until now we studied a setting where the outcomes y
s=t
are discounted sums of all future reinforcement signals. If we use our
algorithm for policy evaluation in reinforcement learning, this corresponds
to looking at continuing tasks (see Sutton and Barto (1998)).
For episodic tasks the trials are partitioned into episodes of finite length.
Now an outcome depends only on reinforcement signals that belong to
the same episode.
Let t be a trial. The first trial that is in the same episode as trial t
is denoted by start(t) and the last by end(t). With this notation and
with a discount rate parameter fl 2 [0; 1], the outcome y t in the episodic
setting is defined as
s=t
This replaces the definition of y t given in (1.1) for the continuous
setting. The definitions of the relative loss (1.2) and (1.3) remain un-
changed. Note that the continuous setting is essentially the episodic
setting with one episode of infinite length.
With the same motivation as in Section 5 we get the TLS algorithm
for episodic learning which is presented in Table III. An implementation
of this algorithm is given in Table IV. We can check the correctness of
this implementation by verifying that
Relative Loss Bounds for Temporal-Difference Learning 17

Table

IV. Implementation of TLS for episodic learning.
A inv := 1
a
I 2 R n\Thetan
If a new episode starts at trial t, then set z := 0 2 R n
Receive instance vector x t 2 R n
A inv := A inv \Gamma
t A inv x t
Predict with " y
Receive reinforcement signal r t 2 R
z
hold after every iteration of the FOR-loop. This follows from (2.5) and
the equality
A note for the practitioner: If a = 0 and if t is small, then the matrix
A t might not be invertible and our algorithm uses the pseudoinverse of
A t . In practice we suggest to use a ? 0 and tune this parameter. Then
A t is always invertible and the calculation of pseudoinverses can be
avoided. We also conjecture that the clipping is not needed for practical
data.
We now show relative loss bounds for episodic learning. Again we
assume that a bound Y on the outcomes is known to the learner in
advance. The proof of the following theorem is very similar to the proof
of Theorem 6.1.
THEOREM 7.1. Consider temporal-difference learning with episodes
of length at most ' and let a  0. Let
sequence of examples in R n \Theta R such that the outcomes y
given by (7.1) lie in the real interval [\GammaY; Y ]. Then with the predictions
of the TLS algorithm of Table III,
J. FORSTER AND M. K. WARMUTH
If a ? 0, then (7.2) is bounded by
an
If the instances x are i.i.d. with some unknown distribution
on R n , then the expectation of (7.2) is at most
A lower bound corresponding to (7.3) is shown in Theorem 9.2.
Note that Theorem 7.1 does not exploit the fact that different episodes
have varying length. Related theorems that depend on the actual lengths
of the episodes can easily be developed.
8. Other second order algorithms
Second order algorithms for temporal-difference learning have been
proposed by Bradtke and Barto (1996) and Boyan (1999). We compare
the algorithms in the episodic setting. Their algorithms maintain weight
vectors w t and predict with "
at trial t.
Bradtke and Barto's Least-squares TD, or shorter LSTD, algorithm
uses the weight vectors
r s x s
Boyan's LSTD() algorithm (he only considers the case
a parameter  2 [0; 1] like the TD() algorithm. It uses the weight
vectors
z s
where
In contrast our TLS algorithm uses the weight vectors
s
Relative Loss Bounds for Temporal-Difference Learning 19
and the prediction of the TLS algorithm at trial t is "
the above formulas the inverse must be replaced by the pseudoinverse
if the matrix is not invertible.)
Note that the TLS algorithm does not have a parameter  like TD()
or LSTD() and that for the case the algorithms LSTD and
are identical. An important difference of the TLS algorithm to
TD() and LSTD() is that it does not use differences in the definition
of the "covariance" matrix.
Bradtke, Barto and Boyan experimentally compare their algorithms
to TD(). Under comparatively strong assumptions Bradtke and Barto
also show that the w t of their algorithm converge asymptotically.
The TLS algorithm we proposed in this paper was designed to minimize
the relative loss (1.3), and our relative loss bounds show that TLS
does this well. We do not know whether similar relative loss bounds hold
for the LSTD and LSTD() algorithms. An experimental comparison
would be useful.
9. Lower bounds
In this section we give lower bounds for linear regression and for episodic
temporal-difference learning. First consider the case of linear regression,
i.e. In this case the outcomes y t are equal to the reinforcement
signals. If the outcomes y t lie in [\GammaY; Y ], then Corollary 6.2 gives the
upper bound of
on the expected relative loss (1.2). Here the examples are i.i.d. with
respect to an arbitrary distribution.
In the next theorem we show that the bound (9.1) cannot be improved
substantially. Our proof is very similar to the proof of Theorem
2 of Vovk (1997). However, if the dimension n of the instances is greater
than one, the examples in his proof are generated by a stochastic
strategy and are not i.i.d.
THEOREM 9.1. Consider linear regression
there is a constant C and a distribution D on the set
of examples R n \Theta [\GammaY; Y ] such that for all T and for every learning
algorithm the expectation of the relative loss (1.2) is
where the examples are i.i.d. with distribution D.
J. FORSTER AND M. K. WARMUTH
Proof. For a fixed parameter ff  1 we generate a distribution D on
the examples with the following stochastic strategy: A vector ' 2 [0;
is chosen from the prior distribution Beta(ff; ff) n , i.e. the components
of ' are i.i.d. with distribution Beta(ff; ff). Then is the distribution
for which the example
n and the example
n . Here e are the unit vectors of R n .
In each trial the examples are generated i.i.d. with D ' . We can calculate
the Bayes optimal learning algorithm for which the expectation of the
loss in trials 1 through T is minimal. The expectation of the relative
loss of this algorithm gives the lower bound of Theorem 9.1.
Details of the proof are given in the appendix. 2
Now consider the setting discussed in Section 7. Here the
trials are partitioned into episodes and the outcomes are given by y
s=t . The following lower bound is proven by a reduction to
the previous lower bound for linear regression.
THEOREM 9.2. Consider episodic temporal-difference learning where
all episodes have fixed length '. Let [\GammaY; Y ] be a range for the outcomes.
Then for every " ? 0 there is a constant C and a stochastic strategy
that generates instances x 1 , x reinforcement signals r 1 ,
such that the outcomes lie in [\GammaY; Y ] and for all T divisible by
' and for every learning algorithm the expectation (over the stochastic
choice of the examples) of the relative loss (1.2) is
Proof. We modify the stochastic strategy used in the proof of Theorem
9.1. When this strategy generates an instance x t and an outcome
y t in trial t, we now generate a whole episode of ' trials with instances
reinforcement signals . The outcomes
for this episode are fl
Consider just the q-th trials from each episode fore some 1  q  '.
In these trials the learner essentially processes the scaled examples
the lower bound of Theorem 9.1 applies with a factor
of fl 2('\Gammaq) . All ' choices of q lead to a factor of 1
the lower bound. 2
Relative Loss Bounds for Temporal-Difference Learning 21
10. Conclusion and open problems
We proposed a new algorithm for temporal-difference learning, the
TLS algorithm. Contrary to previous second order algorithms, the new
algorithm does not use differences in the definition of its "covariance
matrix", see discussion in Section 8. The main question is whether these
differences are really helpful. We proved worst and average case relative
loss bounds for the TLS algorithm. It would be interesting to know how
tight our bounds are for some practical data.
In our bounds the class of linear functions serves as a comparison
class. We use a second order algorithm and its additional loss over
the loss of the best comparator is logarithmic in the number of trials.
We conjecture that even for linear regression there is no first order
algorithm with adaptive learning rates for which the additional loss is
logarithmic in the number of trials.
The algorithms analyzed here can be applied to the case when the
instances are expanded to feature vectors and the dot product between
two feature vectors is given by a kernel function (see Saunders, Gam-
merman, & Vovk, 1998). Also Fourier or wavelet transforms can be used
to extract information from the instances, see Walker (1996) and Graps
(1995). With these linear transforms one can reduce the dimensionality
of the comparison class which leads to smaller relative loss bounds.
So far we compared the total loss of the on-line algorithm to the
total loss of the best linear predictor on the whole sequence of examples.
Now suppose that the comparator is produced by partitioning the data
sequence into k segments and picking the best linear predictor for each
segment. Again we aim to bound the total loss of the on-line algorithm
minus the total loss of the best comparator of this form. Such bound
have been obtained by Herbster and Warmuth (1998) for the case of
linear regression using first-order algorithms. We would like to know
whether there is a simple second-order algorithm for linear regression
that requires O(n 2 ) update time per trial and for which the additional
loss grows with the sums of the logs of the section lengths.
Most of our paper focused on continuous learning, where each outcome
is an infinite discounted sum of future reinforcement signals. In
Section 7 we discussed how the TLS algorithm can be adapted to
the setting. Here the outcomes only depend on reinforcement
signals from the same episode:
s=t
For some applications it might make more sense to let the outcomes
y t be convex combinations of the future reinforcement signals of the
22 J. FORSTER AND M. K. WARMUTH
episode and define
s=t
In the case when each outcome would be the average of the future
reinforcement signals. We do not know of any relative loss bounds for
the case when y t is defined as (10.1).
On a more technical level we would like to know if it is really necessary
to clip the predictions of the temporal-difference algorithm we
proposed. Our proofs are reductions to the previous proofs for linear
regression. Direct proofs might avoid clipping.
Another open technical question is discussed at the end of Section
3. We conjecture that the parameter a in Vovk's linear regression algorithm
can be tuned to obtain bounds of the form (3.3) proven for
the (first order) Widrow-Hoff algorithm. Similarly we believe that the
parameter a in the new (second order) learning algorithm of the paper
can be tuned to obtain the bound (4.1) proven for the (first order)
TD   () algorithm of Schapire and Warmuth.
Finally, note that we do not have lower bounds for the continuous
setting with fl ? 0. It should be possible to show a lower bound of
on the expected relative loss (1.2). (See Theorem
9.2 for a corresponding lower bound in the episodic case.)

Acknowledgements

Jurgen Forster was supported by a "DAAD Doktorandenstipendium im
Rahmen des gemeinsamen Hochschulsonderprogramms III von Bund
und Landern". Manfred Warmuth was supported by the NSF grant
CCR-9821087. Thanks to Nigel Duffy for valuable comments.



--R

Relative loss bounds for on-line density estimation with the exponential family of distributions
Linear analysis: An introductory course.



On relative loss bounds in generalized linear regression.
Prediction in the worst case.
An introduction to wavelets.
Unpublished manuscript.
Department of Computer Science
Tracking the best regressor.
Additive versus exponentiated gradient updates for linear prediction

Numerical recipes in pascal.
Survey of applicable mathematics
Ridge regression learning algorithm in dual variables.
On the Worst-case Analysis of Temporal-Difference Learning Algorithms
Learning to predict by the methods of temporal differences.
Reinforcement learning: An introduction.
Competitive on-line linear regression
Fast Fourier transforms
Adaptive signal processing.
--TR
temporal-difference learning;relative loss bounds;on-line learning;machine learning