Now we do not know the MDP. With neither transitions nor rewards known, we estimate the value of a given policy from experience alone, gathered by interacting with the environment. The two broad branches are Monte-Carlo and temporal-difference learning.

Lecture slides: PDF

Monte-Carlo (MC)

We wait until the episode ends, then pull the value toward the return $G_t$ we actually received.

$$V(S_t) \leftarrow V(S_t) + \alpha\,(G_t - V(S_t))$$

Complete episodes are required (there has to be an end). A single episode may step through the same state more than once: count only the first visit to that state and you get first-visit MC; count every visit and you get every-visit MC. Both converge to the true value as visits accumulate.

Originally MC is a plain average of returns. Rewriting it as an incremental update, the moment you put a constant $\alpha$ where $1/N$ stood, the meaning shifts slightly. $1/N$ is a true average that reflects every past episode equally, while a constant $\alpha$ forgets old episodes exponentially. In problems where the environment drifts (non-stationary), forgetting is the better choice.

Silver’s example is Blackjack. Knowing neither the dealer’s rules nor the probabilities, you play many hands for real and score the value of each situation (your card sum, the dealer’s showing card, whether you hold a usable ace) as the average of wins and losses. With no model, the value map fills in from experience alone.

Temporal-Difference learning (TD)

Rather than waiting until the end, we look just one step ahead and then update an estimate from an estimate (bootstrapping). TD(0) reads:

$$V(S_t) \leftarrow V(S_t) + \alpha\,\big(R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\big)$$

The term inside the parentheses is the TD error. We learn online at every step, even before the episode ends.

Silver’s example is the drive home. You drive while predicting how long it takes to get home: you get in the car expecting 30 minutes, hit rain, and correct it on the spot to 40. If MC is fixing your prediction only once you arrive (episode end), TD revises the prediction immediately, at every moment, with new information. Learning without seeing the end is the power of TD.

MC and TD: which, and when

  • MC: actual return, unbiased, high variance, requires termination, insensitive to initial values.
  • TD: bootstraps, biased, low variance, online, sensitive to initial values, and exploits the Markov property.

The intuition sharpens once you see where the difference in bias and variance comes from. A single return $G_t$ contains every random action, transition, and reward all the way to the end of the episode. That makes it unbiased but wildly variable (high variance). The TD target $R + \gamma V(S')$ contains the randomness of exactly one step. In exchange, it leans on a still-wrong estimate $V(S')$, which introduces bias, but it fluctuates far less (low variance).

What the two converge to also differs. Silver’s famous A, B example brings this out. Give only eight short experiences and learn from them in batch: MC tries to match the average of observed returns alone, so it puts the value of A at 0 (the return of the one episode where A appeared was 0). TD stitches together the structure “B follows A, and B usually gives reward” and puts the value of A at 0.75, by way of B. MC finds the average of what was experienced (least squares); TD finds the answer of the MDP built from what was experienced (certainty equivalence). So when Markov structure is present TD has the edge, and when it is absent MC is safer.

Random walk. Start in the center, walk left or right at random, and touch the right end for reward +1. The true values are 1/6, 2/6, …, 5/6 for A through E (dashed). Step through the episodes and compare how quickly the MC and TD(0) estimates (solid) approach the true values. TD usually catches up faster.

The unified view: bootstrapping and sampling

Place DP, MC, and TD on one set of coordinates and a map appears. There are two axes. The first is whether we bootstrap, that is, whether the estimate of the next state goes into the target. The second is whether we sample, that is, whether we sweep across all the next states by probability (full width) or use only the one actually experienced (sample).

  • Dynamic programming: bootstraps yes, full width (no sampling). Knows the model and sweeps shallowly.
  • Monte-Carlo: bootstraps no, samples yes. No model, goes deep to the end.
  • Temporal-difference learning: bootstraps yes, samples yes. No model, sweeps shallowly.

Nearly every method in reinforcement learning sits somewhere on these two axes. This lecture has, in effect, set up three corners of that map.

n-step and TD(λ)

One step (TD) and all the way to the end (MC) are just the two extremes. The n-step return, looking n steps ahead, connects them. And mixing the returns of every n at once gives the λ-return, which weights the n-step return by $(1-\lambda)\lambda^{n-1}$. Because this shape is largest at the most recent step and shrinks geometrically toward the back, the infinite sum can be computed recursively and efficiently. At $\lambda=0$ only the first term survives, giving TD(0); at $\lambda=1$ it is close to MC.

TD(λ) has two faces. The forward view uses the λ-return above as its target. The intuition is clear, but it must see the whole future, so it is computed only once the episode ends. The backward view accomplishes the same thing online, with eligibility traces.

Eligibility traces solve the credit-assignment problem. If a bell rang three times and a light flashed once before an electric shock arrived, what brought on the shock? It is reasonable to suspect both the signal that occurred often (frequency) and the one that occurred just now (recency). The eligibility trace multiplies the two and leaves the product on each state.

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

Step on a state and the trace jumps up by 1, then decays by a factor of $\gamma\lambda$ at every subsequent step. And the TD error of each step spreads back to past states in proportion to this trace. Remarkably, the forward view and the backward view give exactly the same update offline.

So far we have only evaluated a policy (prediction). In the next lecture we take these tools onward, to control: finding the optimal policy.