Dynamics of Temporal Difference Learning

1 Temporal Difference Learning

We consider here a mathematical treatment of a problem in behavioural biology. This problem has been described e.g. in [Dayan and Abbott 2001] as learning to predict a reward. It is Pavlovian in the sense that classical conditioning is adressed, however reward is not immediate, but after a series of stimuli there is a latency time, followed by a series of rewards. Using a simple linear rule, we will show that the subject is able to predict the remaining rewards by that rule, repeating the same stimuli-reward pattern over a series of trials. A review of learning theory related to these problems can be found in [Sutton and Barto 1998].

There are recent experimental biological correlates with this mathematical model, e.g. in the activity of primate dopamine cells during appetitive conditioning tasks, together with the psychological and pharmacological rationale for studying these cells. A review was given in [Schultz 1998], the connection to temporal difference learning can be found in [Montague et al. 1996].

In this paper, the focus is on two mathematical issues: a) to provide a direct constructive proof of convergence by giving an explicit dependence of the prediction error over trials, b) to minimize the learning time by giving a formula for optimal setting of the learning rate. Hence, the paper contributes as well to temporal difference learning as a purely mathematical issue, which may be valuable also without reference to behavioural biology and reinforcement learning. It can also be understood in a Dynamic Programming sense, see [Watkins 1989] and later work, e.g. [Gordon 2001] and [Szepesvari and

Dynamics of Temporal Difference Learning

Andreas Wendemuth

Otto-von-Guericke-University, 39016 Magdeburg, Germany

Cognitive Systems Group andreas.wendemuth@e-technik.uni-magdeburg.de

Smart 2004]. We adopt the following notation in the course of this paper, following [Dayan and Abbott 2001]:

• Stimulus u(t)
• Future reward r(t)
• Sum of future rewards R(t)
• Weights w(k)
• Predicted reward v(t)

We want to compute, for all trials n of duration T , and for any time of trial t, the predicted reward vn (t). The (extended) stimulus u(t) is given at times tu,min . . . tu,max , the (extended) reward r(t) is presented at times tr,min . . . tr,max. Stimulus and reward do not overlap, i.e. tr,min > tu,max.

The subject is to learn the total remaining reward at time t,

The brackets 〈〉 refer, in general, to stochastic values of R(t), if not exactly the same rewards are given at each trial, but when there are fluctuations.

All previous stimuli u(t) are weighted to give a linear prediction model [Sutton and Barto 1990]:

An update rule for the Sutton-Barto-formula can easily be derived from the mean square error [Dayan and Abbott 2001]:

using the partial derivative with respect to any weight w(α),

Updates are made in discrete steps in the direction of the negative gradient, providing the following rule:

Obviously, the total future reward R(t) is not known to the subject at time t. We can use R(t) = r(t) +R(t + 1). In this formulation, again R(t + 1) is not known. The subject can approximate the value by his prediction v(t + 1). This will provide the so-called

Temporal difference rule at time t:

The updates can be made sequentially, after each time step t, or in parallel, sampling the weight updates for all times in a given trial, and then updating at the end of the trial. The two alternatives do not substantially differ in the final result after many trials. For computational reasons, we use the parallel version of the update rule. Other learning schedules may be adopted, however we use eq. (4) since this is widely accepted in the community, following [Dayan and Abbott 2001]. Let us denote the trial number by superscripts n.

2 Dynamics of temporal difference learning

The parallel temporal difference rule eq. (4) was obtained, using an approximation to gradient descent. Therefore, convergence is not guaranteed and shall be proven in the course of this paper, where a compact notation will be introduced. We proceed as follows:

• Incorporate the rule into the prediction formula, yielding a recursive formula for all predictions vn(t) at trial n.
• Make this a closed formula vn(t).
• Show convergence vn(t) → R(t) for large N.
• Choose an optimal learning rate ε for maximally fast convergence.

We obtain for the predictions vn+1 (t) at trial n + 1 the following recursive formula. Summation limits explicitely state situations where stimuli and reward phases may overlap, we will restrict to non-overlapping cases later.

where δn(t) = r(t) + vn(t + 1) - vn (t) and

Since we are interested whether the subject will make proper predictions after all stimuli have been given, we will restrict our analysis to times t > tu,max. Then g(t, y) will become independent of t, giving

This can be written in matrix notation as follows, with E the unit matrix:

where we shall now use the total time T = tr,max-tu,max+1:

with any real values u(k) and u(tu,max) ̸= 0, and T × T - matrices

where the "0" in G refers to the full remaining upper and lower triangle, respectively, and in A all entries except for the two diagonals are 0. We can further write this in compact notation (vectors have component index t):

Only if (-GA) is a Hurwitz (stability) matrix (all eigenvalues have negative real part), a suitable ε can be chosen such that (EεG A)(N+1) will vanish with large N. A similar approach, relying on Hurwitz matrices, was followed in [Sutton 1988], however there the Hurwitz property was not shown immediately on the matrix structure of eq. (9). Our aim here is to provide an explicit proof, which will establish as an interesting result in its own right a general property of Toeplitz matrices with correlation entries.

We will show the Hurwitz property later, and we will give values for ε for which convergence is assured and for which it is optimal. Continuing with the large N-behaviour, we obtain vN+1 N→∞ -→ A-1 r . This holds no matter what the stimulus! With

we obtain

which is the desired result. This proves convergence in full generality. We need to show that (-GA) is a Hurwitz matrix, i.e. that all eigenvalues of that matrix have negative real part. Further, we want to give values for ε which provide maximum speed of convergence.

3 Proof of convergence

In previous approaches in the literature, temporal difference (TD) learning was extended to TD(λ) learning where the parameter λ refers to an exponential weighting with recency. Learning and convergence issues were considered e.g. in [Dayan 1992] and [Dayan and Sejnowski 1994]. In the TD(λ) framework, what we consider here is TD(0)-learning where in contrast to the mentioned literature we concentrate on a direct proof of convergence by establishing a general property of Toeplitz matrices with correlation entries.

The proof proceeds as follows: we will show first that G is positive definite. Then, we will show that all eigenvalues of (G A) have positive real part. Hence, we will have established the Hurwitz property required for convergence.

In order to see that G is positive definite, we consider any nonzero real vector x and show that xTGx is always positive. We first extract from G the diagonal matrix GD and the upper triangular matrix G+. Then we have

where in order to keep summation limits easy it is understood that xi = 0 for i < 0 and i > N ("zero padding"). There are 2k+1 Toeplitz bands, k being the number of stimuli. Shifting the time index in eq. (8) from tu,min to 0, g(j) arises from the k stimuli for u(k) ̸= 0, u(t) real as

hence xTGx can be written as

-

Rearranging the inner sums with

and using vectors u of dimension (k + 1) with components ut = u(t) leads to

where the matrices ˜X(i) are (k +1) × (k + 1) band matrices with entries ˜X(i) m,m+n = xixi+n for all m and n ≥ 0, and 0 otherwise. Symmetrizing the matrix products, we can write

The matrix elements of the second term are, for -k ≤ n ≤ 0:

where the summation limits in the last result were taken, for convenience, larger than necessary for covering all cases of n for which the summand is nonzero (note that n is nonpositive), the extra terms being zero due to the zero padding convention for the xi. As a result, the matrix elements of the first and the second term in eq. (16) have identical format, for nonnegative and nonpositive n, respectively.

Making use of eq. (16) and eq. (17), and incorporating the first sum in eq. (15) leads to

where the matrices ˆX(i) are band matrices with entries ˆX(i) m,m+n = xixi+n for positive and negative n.

We can now write the sum of matrices in eq. (18) in a different way. Denote vectors ˜x(i) of dimension (k + 1) with components ˜x(i) m = xi+m, m = 0...k, where, as before, it is understood that xj = 0 for j < 0 and j > N. Hence, these vectors will have nonzero components only for i = -k...N .

Notice that the following covariance matrices are generated by these vectors:

Then we have for (m = 0 . . . k, n = -m. . . k - m):

and

which establishes that

Then we can rewrite eq. (18), using eq. (22):

This sum is certainly nonnegative. We will now show that it cannot become zero.

The proof is by contradiction. Suppose the sum is zero. Then all individual terms must be zero. Start with the first term. We have from the definition

This becomes zero, since uk ̸= 0 (eq. (12)), only for x0 = 0. Now proceed with the second term:

where the previous result x0 = 0 was used. This becomes zero, since uk ̸= 0 (eq. (12)), only for x1 = 0. Continuing in this vein, after N steps, we end with the product

where all the previous results were used. Hence xN = 0, which in total means that x = 0. This is a contradiction, since x must be a nonzero vector.

With this result, we have established that xTGx > 0, hence we have established:

Symmetric Toeplitz matrices of the structure of G after eq. (9), with correlation entries gj after eq. (12), are positive definite.

We now turn our attention to showing that all eigenvalues of (GA) have positive real part. We will look at any real A and any G which is real, symmetric and positive definite. (We will not require the stronger condition that the structure of G is after eq. (9), and we say nothing about the entries gj .)

Under these premises, the proof will first give a sufficient condition for the sign of the real part of the eigenvalues of (GA). Then we will show that this sign is indeed positive for the A at hand.

Let y be any eigenvector of (GA) and λ be the corresponding eigenvalue. Since (GA) is real, y and λ are either both real or both complex. In the complex case, there exists a further eigenvector y∗ and corresponding eigenvalue λ∗ , where ()∗ denotes complex conjugated and transposed.

Let us denote z = Ay and write

Also, with G real and symmetric, we have G = G∗ and

The summation of eqns. 26 and 27 gives

With G real, symmetric and positive definite, we have for any complex z that z∗Gz is real and positive. This can be used as follows.

Case 1: y and λ are both real.

hence

Case 2: y and λ are both complex.

Let us write y = v+iw and λ = g+ih. Then from eq. (28), with real A, we obtain

from which follows with sign(Re(λ)) = sign(g): sign(Re(λ)) = sign {vT [AT + A] v + wT [AT + A] w} (34)

The results for both cases, eqns. 30 and 34, allow the following sufficient condition:

Let G be a real, symmetric and positive definite matrix, and A be a real square matrix. If the matrix [AT + A] is positive definite, then the real parts of the eigenvalues of (G A) are positive.

Let us now turn our attention to the specific matrix A given in eq. (9). We have

It can be shown that the matrix Q = AT + A is positive definite, by using the previous result of this paper: matrices of the structure of G are positive definite. Noting that Q has the structure of G, using eq. (12) with k = 1 and u = (1,-1), immediately gives the desired result. This completes our proof that (-G A) is a Hurwitz matrix.

4 Learning rate ε for fast convergence

The convergence behaviour of the temporal difference rule is known from eq. (10). For large number of trials, convergence speed will be dominated by the eigenvalue of (E - εG A) with the largest modulus, for which convergence speed is slowest. We have for the eigenvalues (ev):

where the same notation for the eigenvalues of G A as in the previous section, λ = g + i h, was used.

Hence, the first task to do is to compute the eigenvalues of GA which are only dependent on the given stimuli u(k) and on the total time T . Note that GA defines the special structure of an unsymmetric Toeplitz matrix with 2k + 2 bands. It is well known that a closed solution for the eigenvalues of Toeplitz matrices exists only for not more than three bands, they are given for symmetric and asymmetric cases e.g. in [Beam and Warming 1993]. Hence only for k = 0 can a closed solution been given, which we do in sec. 5. For k > 0 numerical values must be obtained, special methods for the solution, and for the asymptotic structure of the eigenvalues for large T , are given in [Beam and Warming 1993].

The square modulus m of the eigenvalues is given by

We will first give a choice for ε for which convergence is always assured and which also serves as a good rough value for setting ε without much computational effort.

Note first that m(ε = 0) = 1 for all eigenvalues. Further, since (-G A) is Hurwitz, g > 0 for all eigenvalues, and for small ε > 0, m(ε) < 1 for all eigenvalues due to eq. (37). Lastly, for large ε, m(ε) will increase again beyond all bounds for all eigenvalues, since m(ε) ∝ ε2 for large ε and all eigenvalues.

After this sketch of the general behaviour of m(ε), it is clear that for each eigenvalue k there is a ε(k) ̸= 0 for which m(ε(k)) = 1 and m(ε(k)) is rising with ε(k). Computing these values from eq. (37) for eigenvalues λk = gk + ihk gives

Hence, m(ε) < 1 for 0 < ε < mink ε(k), and a good choice ˜ ε for convergent behaviour is therefore the mean value of the bounds,

Note again that whenever hk ̸= 0, there is an additional eigenvalue gk - i hk for which the minimum in eq. (39) is identical and needs not be computed.

We now turn to finding the optimal value ε∗ for fastest convergence. This is given by

This optimization problem has no closed solution. However, a simple line search algorithm can be given to find the solution in finitely many (less than T ) steps.

The general idea is to start at ε = 0 and increase ε until we reach ε∗ . In all of this process, we select a k and go along curves m(ε(k)), ensuring the condition that our chosen k satisfies maxk m(ε(k)).

At ε = 0, all m(ε(k)) = 1 and decreasing with ε. The slope is given by -2gk < 0. We start by choosing the k∗ for which k∗ = argmink gk, which ensures that the condition maxk m(ε(k)) is satisfied by our choice of k∗ . Our current position is εc = 0. Then we apply the following procedure:

[START]

Continuing on curve k∗ , we would reach the minimum for

if everywhere between our current position εc and the proposed position ε∗k∗ the maximum condition maxk m(ε(k)) is satisfied for k∗ . In order to check this, we compute the intersections of our curve under inspection k∗ to all other curves k.

After eq. (37), these intersections are given at values εk according to

or

Now we inspect the intersection which is closest to our current position of εc, i.e. for which ˆ k = argmink{ εk, εk > εc}.

If εˆk > ε∗k∗, then ε∗k∗ after eq. (41) is indeed the solution (free minimum). [STOP]

Else, there is an intersection prior to reaching ε∗k∗ . If the curve that is intersecting is rising at ε(ˆ k), this means that we are done, since we actually have reached the condition of eq. (40). The solution is

(boundedminimum). [STOP]

Else, if the curve that is intersecting is falling at ε(ˆ k), we must continue on that new curve which now satisfies the maximum condition in eq. (40). To this end, we set εc = ε(ˆ k) and k∗ = ˆ k and continue (change in falling curves with maximum modulus). [GO TO START]

Fig. 1 illustrates the behaviour with free minimum, fig. 2 with bounded minimum. Both figures have a change in falling curves with maximum modulus.

This algorithm terminates after finitely many steps, either at the minimum of the curve k∗ or at an intersection of a falling with a rising curve. It is clear that one of the two possibilities exist since all curves eventually rise with large ε.

5 One stimulus

We look at the special case where only one stimulus u is present, hence k = 0. Then, eq. (10) takes a particularly simple form, where (E-A) is the unit shift matrix:

After eq. (38), any 0 < ε < 2u-2 will ensure convergence with exponential error decay over time, except for the case when choosing the optimal learning rate εu2 = 1. In this case we obtain for N ≤ T :

and for N > T we have vN+1 = A-1 r. Hence, after finitely many (T) steps, convergence is reached when choosing the optimal learning rate. This is due to the fact that (GA) has only one degenerate eigenvalue, and T generalized eigenvectors of algebraic multiplicity 1 . . . T .

6 Conclusion

We have presented a closed formula of the prediction of rewards at trial time t within trial n and shown its convergence, where two general formulae for Toeplitz matrices and eigenvalues of products of matrices were derived and utilized. We have given learning rates which optimally speed up the learning process.