Introduction

Monte Carlo and TD(0) appeared to be two endpoints for learning a value.

TD(0)

It observes only one actual reward and immediately bootstraps.

$$G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1})$$

Monte Carlo

It observes every actual reward through the terminal state.

$$G_t = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-t-1}R_T$$

Must we choose only one of them?

We could observe two rewards before bootstrapping, or observe five. Once $n$ determines how much real experience to use, we can construct many targets between TD and Monte Carlo.

This article connects the two methods with the n-step return. It then introduces TD($\lambda$), which blends returns of several lengths, and eligibility traces, which calculate the same idea online.

The n-Step Return

The $n$-step return observes the next $n$ rewards and then bootstraps the rest of the future from the value of $S_{t+n}$.

$$\begin{aligned} G_t^{(n)} =& R_{t+1} + \gamma R_{t+2} + \cdots \\ & + \gamma^{n-1}R_{t+n} + \gamma^n V(S_{t+n}) \end{aligned}$$

We can read the terms in temporal order.

• The first reward is used as-is.
• The second reward is multiplied by $\gamma$ once.
• The $n$th reward is multiplied by $\gamma^{n-1}$.
• The rest of the future is folded into $\gamma^n V(S_{t+n})$.

Only the target in the update changes to $G_t^{(n)}$.

$$V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t^{(n)} - V(S_t) \right]$$

n=1 and n=∞

Substituting $n=1$ gives

$$G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1}),$$

which is the TD(0) target.

When $n$ extends all the way to the end of an episode, no value remains from which to bootstrap.

$$G_t^{(\infty)} = G_t$$

This is the Monte Carlo return.

$$\text{TD(0)} \longleftrightarrow \text{n-step TD} \longleftrightarrow \text{Monte Carlo}$$

$n$ is a control that balances how much we trust actual rewards against estimates.

Calculating a 3-Step Return

Suppose the next three rewards are

$$R_{t+1}=1, \quad R_{t+2}=2, \quad R_{t+3}=3,$$

and

$$V(S_{t+3})=5, \qquad \gamma=0.9.$$

The 3-step return is

$$\begin{aligned} G_t^{(3)} &= 1 + 0.9\times2 + 0.9^2\times3 + 0.9^3\times5 \\ &= 1+1.8+2.43+3.645 \\ &= 8.875. \end{aligned}$$

The first three rewards were observed directly. For the future after the fourth step, we borrowed the current estimate $V(S_{t+3})=5$.

If the third reward were followed immediately by a terminal state, the final bootstrap term would be zero.

$$G_t^{(3)} = 1+1.8+2.43 = 5.23$$

Is a Larger n Always More Accurate?

As $n$ grows, the target uses more actual rewards, so bootstrapping bias tends to decrease. At the same time, it becomes exposed to the randomness in more actions, transitions, and rewards, so its variance may increase.

The best $n$ depends on the environment and the accuracy of the current value estimate.

If the initial values are very inaccurate, TD(0) can quickly spread bad information by borrowing the estimate only one step ahead. Conversely, if episodes are long and rewards are noisy, a return with a large $n$ may fluctuate severely.

Can We Blend Several n-Step Returns?

Instead of choosing one $n$, we can average returns of different lengths.

For example, an equal blend of the 2-step and 4-step returns is

$$\frac{1}{2}G_t^{(2)} + \frac{1}{2}G_t^{(4)}.$$

TD($\lambda$) takes a geometrically weighted average of every n-step return.

$$G_t^\lambda = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)}$$

The weight of the $n$th return is

$$(1-\lambda)\lambda^{n-1}.$$

For $0\leq\lambda\leq1$, a small $\lambda$ concentrates weight on short returns. As $\lambda$ approaches $1$, longer returns receive more weight.

In an episodic task, the remaining weight is assigned to the final Monte Carlo return through the terminal state so that all weights sum to $1$.

The Two Ends of λ

When $\lambda=0$, only the first return remains.

$$G_t^0 = G_t^{(1)}$$

This is TD(0).

As $\lambda$ approaches $1$, most of the weight moves to returns that extend to the end of the episode, making the result resemble Monte Carlo.

$$\lambda=0 \quad\Rightarrow\quad \text{short backup}$$ $$\lambda\rightarrow1 \quad\Rightarrow\quad \text{long backup}$$

$\gamma$ determines the temporal importance of future rewards. $\lambda$ determines how much the learning target blends returns of different lengths. Their roles are distinct.

• $\gamma$: How important are future rewards in the objective of the problem?
• $\lambda$: How much should value learning use long backups?

The Forward View and Its Computational Problem

The formulation of TD($\lambda$) above is called the forward view because it looks from the present into several n-step returns unfolding in the future.

$$G_t^{(1)}, G_t^{(2)}, G_t^{(3)}, \ldots$$

This is conceptually easy to understand, but calculating $G_t^\lambda$ exactly requires future rewards. We seem to lose the online advantage of TD because we must wait until the episode ends.

The backward view calculates the same effect in the opposite temporal direction. It distributes the TD error that occurs now among recently visited states.

This is where eligibility traces enter the picture.

An Eligibility Trace Is a Mark Left on Past States

For every state $s$, we maintain a trace $E_t(s)$. Initially, every trace is zero.

$$E_0(s)=0$$

When state $S_t$ is visited at time $t$, we add $1$ to that state's trace and decay every earlier trace by $\gamma\lambda$.

$$E_t(s) = \gamma\lambda E_{t-1}(s) + \mathbf{1}(S_t=s)$$

$\mathbf{1}(S_t=s)$ is an indicator function.

• It is $1$ when the current state is $s$.
• It is $0$ otherwise.

A state visited just now has a large trace, while a state visited long ago gradually receives a smaller one. Repeated visits to the same state accumulate in its trace.

David Silver's lecture describes this as a combination of recency and frequency heuristics.

• A state visited more recently has a larger trace.
• A state visited more frequently has its trace increased several times.

Sending the TD Error to Every Trace

The TD error for the current step is the same as in TD(0).

$$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$$

Instead of updating only the current state, however, we update every state in proportion to its trace.

$$V(s) \leftarrow V(s) + \alpha \delta_t E_t(s) \qquad \forall s$$

For example, suppose the current error is $\delta_t=2$ and three states have traces

$$E_t(A)=0.1, \quad E_t(B)=0.4, \quad E_t(C)=1.0.$$

With $\alpha=0.1$, the update sizes are

$$\Delta V(A)=0.1\times2\times0.1=0.02,$$ $$\Delta V(B)=0.1\times2\times0.4=0.08,$$ $$\Delta V(C)=0.1\times2\times1.0=0.2.$$

State C, which is closest to the current state, changes the most. The older state A changes only a little.

The Credit-Assignment Problem

When a large reward appears at the end of an episode, which past states and actions deserve credit for it?

TD(0) propagates reward information backward one step at a time. Reaching a distant state may take several episodes.

With eligibility traces, the current TD error is delivered to several recently visited states at once. Credit can spread more quickly in an environment where rewards arrive late.

If $\lambda$ is too large, however, many old states are affected by one update and variance may increase. If it is too small, credit moves slowly, as in TD(0).

Thus $\lambda$ is another hyperparameter that balances bias, variance, and the speed of credit propagation.

Accumulating and Replacing Traces

The equation above adds $1$ whenever a state is visited. This is an accumulating trace.

$$E_t(s) = \gamma\lambda E_{t-1}(s) + 1 \qquad \text{if }S_t=s$$

If the same state is visited repeatedly within a short period, its trace can exceed $1$.

A replacing trace sets the visited state's trace to $1$.

$$E_t(s)=1 \qquad \text{if }S_t=s$$

The traces of every other state continue to decay by $\gamma\lambda$.

The two methods differ in how strongly they represent repeated visits. It is enough to understand the main structure of TD($\lambda$) first and distinguish these variants later, during implementation.

Why the Forward and Backward Views Agree

The forward view updates the current state with a weighted average of several n-step returns.

The backward view distributes the TD error from every step to past states through eligibility traces.

They appear to point in opposite directions, but under the appropriate conditions, the updates accumulated over an entire episode produce the same result.

In the wording of David Silver's lecture, the forward view provides the theory and the backward view provides the mechanism.

Extending the Idea to SARSA(λ)

Extending a state-value trace to a state-action pair gives SARSA($\lambda$).

$$E_t(s,a) = \gamma\lambda E_{t-1}(s,a) + \mathbf{1}(S_t=s,A_t=a)$$

The SARSA TD error is

$$\delta_t = R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t),$$

and every state-action value is updated in proportion to its trace.

$$Q(s,a) \leftarrow Q(s,a) + \alpha\delta_tE_t(s,a)$$

The TD error from the current experience is delivered to several state-action pairs visited recently.

What to Remember

The central idea of this article is

n-step TD controls how many actual rewards to observe, TD($\lambda$) blends returns of several lengths, and eligibility traces calculate the same effect online in the backward direction.

More specifically:

1. The $n$-step return observes $n$ rewards and then bootstraps from $V(S_{t+n})$.
2. $n=1$ gives TD(0), while extending to the end of an episode gives Monte Carlo.
3. A small $n$ tends to have lower variance, while a large $n$ tends to have less bootstrapping bias.
4. The $\lambda$-return is a weighted average of all n-step returns.
5. An eligibility trace gives more credit to states visited recently and frequently.
6. The forward view explains the meaning; the backward view shows how to compute it online.

This completes the basic flow of model-free reinforcement learning when values are stored in a table. If a state is an image or a continuous robot pose, however, there are too many states to store every $V(s)$ or $Q(s,a)$ in its own entry.

The next article replaces the value table with a parameterized function and introduces value function approximation. This is where linear functions and neural networks enter reinforcement learning.

References

• David Silver, Lecture 4: Model-Free Prediction
• David Silver, Lecture 5: Model-Free Control
• Seoul National University DSBA Lab, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition