7.2 The Forward View of TD($\lambda$)

Backups can be done not just toward any -step return, but toward any average of -step returns. For example, a backup can be done toward a return that is half of a two-step return and half of a four-step return: . Any set of returns can be averaged in this way, even an infinite set, as long as the weights on the component returns are positive and sum to 1. The overall return possesses an error reduction property similar to that of individual -step returns (7.2) and thus can be used to construct backups with guaranteed convergence properties. Averaging produces a substantial new range of algorithms. For example, one could average one-step and infinite-step backups to obtain another way of interrelating TD and Monte Carlo methods. In principle, one could even average experience-based backups with DP backups to get a simple combination of experience-based and model-based methods (see Chapter 9).

A backup that averages simpler component backups in this way is called a complex backup. The backup diagram for a complex backup consists of the backup diagrams for each of the component backups with a horizontal line above them and the weighting fractions below. For example, the complex backup mentioned above, mixing half of a two-step backup and half of a four-step backup, has the diagram:

Figure 7.3: The backup digram for TD($\lambda$). If , then the overall backup reduces to its first component, the one-step TD backup, whereas if , then the overall backup reduces to its last component, the Monte Carlo backup.

 

The TD($\lambda$) algorithm can be understood as one particular way of averaging -step backups. This average contains all the -step backups, each weighted proportional to , where (Figure  7.3). A normalization factor of ensures that the weights sum to 1. The resulting backup is toward a return, called the $\lambda$-return, defined by

Figure  7.4 illustrates this weighting sequence. The one-step return is given the largest weight, ; the two-step return is given the next largest weight, ; the three-step return is given the weight ; and so on. The weight fades by $\lambda$ with each additional step. After a terminal state has been reached, all subsequent -step returns are equal to . If we want, we can separate these terms from the main sum, yielding

(7.3)

This equation makes it clearer what happens when . In this case the main sum goes to zero, and the remaining term reduces to the conventional return, . Thus, for , backing up according to the $\lambda$-return is the same as the Monte Carlo algorithm that we called constant-$\alpha$ MC (6.1) in the previous chapter. On the other hand, if , then the $\lambda$-return reduces to , the one-step return. Thus, for , backing up according to the $\lambda$-return is the same as the one-step TD method, TD(0).

Figure 7.4: Weighting given in the $\lambda$-return to each of the -step returns.

 

We define the $\lambda$-return algorithm as the algorithm that performs backups using the $\lambda$-return. On each step, , it computes an increment, , to the value of the state occurring on that step:

(7.4)

(The increments for other states are of course , for all .) As with the -step TD methods, the updating can be either on-line or off-line.

The approach that we have been taking so far is what we call the theoretical, or forward, view of a learning algorithm. For each state visited, we look forward in time to all the future rewards and decide how best to combine them. We might imagine ourselves riding the stream of states, looking forward from each state to determine its update, as suggested by Figure  7.5. After looking forward from and updating one state, we move on to the next and never have to work with the preceding state again. Future states, on the other hand, are viewed and processed repeatedly, once from each vantage point preceding them.

Figure 7.5: The forward or theoretical view. We decide how to update each state by looking forward to future rewards and states.

 

The $\lambda$-return algorithm is the basis for the forward view of eligibility traces as used in the TD($\lambda$) method. In fact, we show in a later section that, in the off-line case, the $\lambda$-return algorithm is the TD($\lambda$) algorithm. The $\lambda$-return and TD($\lambda$) methods use the $\lambda$ parameter to shift from one-step TD methods to Monte Carlo methods. The specific way this shift is done is interesting, but not obviously better or worse than the way it is done with simple -step methods by varying . Ultimately, the most compelling motivation for the $\lambda$ way of mixing -step backups is that there is a simple algorithm--TD($\lambda$)--for achieving it. This is a mechanism issue rather than a theoretical one. In the next few sections we develop the mechanistic, or backward, view of eligibility traces as used in TD($\lambda$).

Example 7.2: $\lambda$-return on the Random Walk Task   Figure  7.6 shows the performance of the off-line $\lambda$-return algorithm on the 19-state random walk task used with the -step methods in Example 7.1. The experiment was just as in the -step case except that here we varied $\lambda$ instead of . Note that we get best performance with an intermediate value of $\lambda$.

Figure 7.6: Performance of the off-line $\lambda$-return algorithm on a 19-state random walk task.

 

Exercise 7.4   The parameter $\lambda$ characterizes how fast the exponential weighting in Figure  7.4 falls off, and thus how far into the future the $\lambda$-return algorithm looks in determining its backup. But a rate factor such as $\lambda$ is sometimes an awkward way of characterizing the speed of the decay. For some purposes it is better to specify a time constant, or half-life. What is the equation relating $\lambda$ and the half-life, , the time by which the weighting sequence will have fallen to half of its initial value?