Introduction

Monte Carlo used a fairly trustworthy target. It ran an episode to completion and then calculated the return $G_t$ that was actually received.

But this creates a problem if one game takes an hour or if the environment never ends. To learn whether the first action was good, the agent must wait an entire hour. A continuously operating environment, such as a temperature-control system, may have no terminal state at all.

Temporal-difference learning, or TD, learns immediately after every step.

$$S_t \xrightarrow{R_{t+1}} S_{t+1}$$

Because the return for the entire episode is not yet known, TD borrows the current estimate $V(S_{t+1})$ for the future after the next state.

$$\text{TD target} = R_{t+1} + \gamma V(S_{t+1})$$

It combines one actual reward with one estimate to correct the current estimate. In the wording of David Silver's lecture, it “updates a guess toward another guess.”

The Targets of Monte Carlo and TD

Placing the two methods side by side makes the difference clear.

Monte Carlo

$$V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t-V(S_t) \right]$$

The target is the actual return, which becomes available after the episode ends.

TD(0)

$$V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$$

The target combines the reward just received with the current value estimate of the next state.

The $(0)$ after TD distinguishes this method from n-step TD and TD($\lambda$), which we will see later. For now, think of TD(0) as the shortest TD method: it observes one actual step and immediately bootstraps the rest.

Bootstrapping Corrects One Estimate with Another

The TD target contains $V(S_{t+1})$. This value is not yet a correct answer; it is another estimate that is still being learned.

$$\underbrace{R_{t+1}}_{\text{observed}} + \gamma \underbrace{V(S_{t+1})}_{\text{estimated}}$$

Replacing the unobserved future after the next state with an existing estimate is called bootstrapping.

The name may be unfamiliar, but the same pattern appears in everyday reasoning. Suppose the first part of a commute actually took 20 minutes, and the remaining trip from that point usually takes 15 minutes. We can revise the estimated total commute to 35 minutes even before arriving at work. We combined an intermediate observation with an estimate of what remains.

Borrowing the next state's estimate can seem unreliable when the current estimates are wrong. Indeed, a TD target can be biased. But as experience accumulates, the next state's estimate is also corrected, and that information propagates to earlier states.

TD Error Measures How Surprising the Outcome Was

The difference between the TD target and the current value is called the TD error and is written as $\delta_t$.

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

The update becomes much shorter.

$$V(S_t) \leftarrow V(S_t) + \alpha\delta_t$$

Let us substitute some numbers.

• Current estimate: $V(S_t)=4$
• Reward received: $R_{t+1}=2$
• Next-state estimate: $V(S_{t+1})=5$
• Discount factor: $\gamma=0.9$
• Learning rate: $\alpha=0.1$

The TD target is

$$2+0.9\times5=6.5.$$

Its difference from the current estimate of $4$ is

$$\delta_t=6.5-4=2.5.$$

The final update is

$$V(S_t) \leftarrow 4+0.1\times2.5 = 4.25.$$

If $\delta_t<0$, the target is smaller than the current estimate and the value decreases. We can interpret the TD error as “how surprisingly the expectation of the future changed after the most recent step.”

How Can One Step Teach Us About the Distant Future?

At first, TD can look too hasty. If the next state's value is only an estimate, how does information from a terminal reward ever reach a distant state?

Consider a short chain.

$$A \rightarrow B \rightarrow C \rightarrow \text{Terminal }(+10)$$

Suppose every initial value is zero.

1. Moving from $C$ to the terminal state reveals $+10$, so $V(C)$ increases.
2. In the next episode, moving from $B$ to $C$ uses the now-higher $V(C)$ as a target, so $V(B)$ increases.
3. Later, moving from $A$ to $B$ borrows $V(B)$, so $V(A)$ increases.

Reward information propagates backward one step at a time along actual experience. This resembles the repeated backups in dynamic programming, but rather than averaging every possible next state according to its probability, TD uses one transition that was actually observed.

The Bias–Variance Difference Between Monte Carlo and TD

Neither Monte Carlo nor TD is always superior.

Monte Carlo Target

$$G_t = R_{t+1} + \gamma R_{t+2} + \cdots$$

Because it uses the actual return, it has no bias from the current value estimate. But it is affected by the randomness of many actions, transitions, and rewards, so its variance is high.

TD Target

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

Because it uses the current estimate $V(S_{t+1})$, it can be biased. It passes through only one step of random outcomes, however, so its variance is generally lower.

In practice, this trade-off affects the speed and stability of learning.

Viewing DP, Monte Carlo, and TD Through Sampling and Bootstrapping

Two questions organize the relationship between the three methods.

1. Does the method average over every possible next state, or use one actual transition as a sample?
2. Does it use the actual return through the end, or bootstrap from an estimate?

Dynamic programming uses a model to calculate the expectation over every outcome. Monte Carlo samples an entire episode and observes it to the end. TD samples one actual transition and folds everything after the next state into an estimate.

Remembering this table makes it easier to identify what later algorithms approximate.

Why Online Learning Is Possible

TD can update after every step, before the episode ends.

$$(S_t,R_{t+1},S_{t+1})$$

These three pieces of information and the current value table are enough. There is no need to keep the entire episode in memory.

This is particularly useful in

• games with extremely long episodes,
• process-control systems that never end,
• systems that must revise state evaluations in real time, and
• environments where episodes are cut off midway or only partial experience is collected.

If Monte Carlo watches an entire film through the ending before revising its rating, TD watches one scene and makes a small revision by comparing it with the previous expectation of the next scene.

From TD Prediction to TD Control

So far, we have estimated the state value of a fixed policy $\pi$.

$$V(s) \approx v_\pi(s)$$

To find a good policy, we need to learn action values and improve the policy.

Replacing $V(S_t)$ in the state-value TD update with $Q(S_t,A_t)$ gives

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ \text{Target} - Q(S_t,A_t) \right].$$

The central question in the next article is which Q-value should enter the target.

• SARSA: $Q(S_{t+1},A_{t+1})$ for the next action actually selected
• Q-Learning: the largest value among the possible next actions, $\max_{a'}Q(S_{t+1},a')$

The updates look the same, but they borrow different futures.

What to Remember

The central idea of this article is

TD learns after every step with a target that combines one actual reward and the value estimate of the next state.

More specifically:

1. The TD target is $R_{t+1}+\gamma V(S_{t+1})$.
2. Correcting one estimate with another is called bootstrapping.
3. The TD error is the difference between the target and the current prediction.
4. TD can update online without waiting for the end of an episode.
5. It can be more biased than Monte Carlo, but generally has lower variance.
6. TD uses both sampling and bootstrapping.

The next article extends TD to a control problem. We will compare the equations for SARSA and Q-Learning and see how the next action whose value enters the target determines whether learning is on-policy or off-policy.

References

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