Learning values from experience: Monte Carlo and temporal-difference prediction

Before this lesson: lesson 01 (returns, $V^\pi$ and the Bellman expectation equation), lesson 02 (iterative policy evaluation and the operator $T^\pi$) and lesson 03 (the incremental mean). Monte Carlo estimation, bias and variance, and importance sampling are in probability 14; we restate what we need. Time: about 70 minutes, plus the notebook.

---

Why this matters #

Dynamic programming needs the model $P$ and $R$. A robot, a game engine or a user population gives us only samples. Estimating the value of a policy from samples, called prediction or policy evaluation, is half of almost every RL algorithm:

• Critics and value heads. Actor-critic methods, PPO and the value model in RLHF train a value network on TD targets or λ-returns; GAE (lesson 08) is the λ-return idea applied to advantages.
• Q-learning and DQN (lesson 05, lesson 06) are TD learning for action values; Rainbow uses n-step returns.
• Off-policy evaluation with importance sampling estimates how a new policy (a recommender, a treatment rule) would perform, using logs of the old one. The ratio $\rho$ returns in PPO (lesson 09).
• Neuroscience. The TD error $\delta_t$ matches the firing of dopamine neurons, which signal reward prediction errors (Schultz, Dayan and Montague, 1997). TD-Gammon (Tesauro, 1995) learned world-class backgammon with TD(λ).

1. Predict first #

2. The picture #

Prediction from samples #

A policy $\pi$ is fixed. We do not know the MDP, but we can run $\pi$ and observe episodes $s_0, a_0, r_0, s_1, a_1, r_1, \dots, s_T$, where $r_t$ is the reward after $(s_t, a_t)$ and $s_T$ is terminal. (Sutton and Barto write this reward $R_{t+1}$; see lesson 01.) We want

The recursion $G_t = r_t + \gamma G_{t+1}$ suggests two targets for $V(s_t)$:

• Monte Carlo: wait for the end of the episode and use the actual return $G_t$.
• TD(0): after one step, replace the unknown rest $G_{t+1}$ by the current estimate $V(s_{t+1})$, and use $r_t + \gamma V(s_{t+1})$. Using your own estimate inside the target is bootstrapping.

Both then take a step toward the target, exactly like the incremental mean of lesson 03:

The random walk #

Our running example is the random walk of Sutton and Barto (Example 6.2). Five states A, B, C, D, E lie in a row, with a terminal state at each end. Every episode starts in C. At each step the agent moves left or right with probability 1/2. The reward is +1 for leaving on the right, and 0 for every other step; $\gamma = 1$.

The true value of a state is the probability of leaving on the right. Number the positions 0 to 6 (0 and 6 are the terminals), so $V(0) = 0$ and $V(6) = 1$. The Bellman equation of each inner state is $V(k) = \frac12 V(k-1) + \frac12 V(k+1)$: the values lie on a straight line from 0 to 1, so $V(k) = k/6$. Hence $V^\pi(A), \dots, V^\pi(E) = 1/6, 2/6, 3/6, 4/6, 5/6$.

Interactive figure: loading…

3. Definitions and main results #

Monte Carlo prediction #

After an episode ends, compute the returns backward: $G_T = 0$ and $G_t = r_t + \gamma G_{t+1}$ for $t = T-1, \dots, 0$ (one pass, from the end). Then

• first-visit MC uses, for each state, only the return after its first visit in the episode;
• every-visit MC uses the returns after all its visits.

The estimate is the average of the used returns (sample average), or a constant-α update $V(s_t) \leftarrow V(s_t) + \alpha (G_t - V(s_t))$.

Properties.

• Each first-visit return is an unbiased sample of $V^\pi(s)$, and returns from different episodes are independent. So the first-visit average converges to $V^\pi(s)$ by the law of large numbers, with standard error $\sigma / \sqrt n$ after $n$ episodes that visit $s$.
• Returns after different visits in the same episode are dependent, so every-visit MC is biased for a finite number of episodes, but it also converges to $V^\pi(s)$ (Singh and Sutton, 1996).
• MC needs complete episodes: no update before the end. It does not use the Markov property; it only averages what followed each state.

TD(0) #

TD(0) updates after every step:

with $V(s_{t+1}) = 0$ when $s_{t+1}$ is terminal. The quantity $\delta_t$ is the TD error: the difference between the one-step target and the current estimate.

TD(0) is sampled dynamic programming. Given $s_t = s$, the expected target is

the Bellman expectation operator of lesson 02. Iterative policy evaluation applies $T^\pi$ to all states with the model; TD(0) applies one noisy sample of it to the visited state. The expected update is zero exactly when $V = T^\pi V$, that is, at $V = V^\pi$. In the tabular case, TD(0) converges to $V^\pi$ with probability 1 if every state is visited infinitely often and the step sizes satisfy $\sum \alpha = \infty$, $\sum \alpha^2 < \infty$ (Dayan 1992; Jaakkola, Jordan and Singh 1994; Tsitsiklis 1994). With a small constant $\alpha$, the values converge in the mean and keep fluctuating around $V^\pi$.

The MC error is a sum of TD errors. If $V$ does not change during the episode, then

Proof.

1. Write out the sum, using the definition of $\delta_k$:

2. The first sum is $G_t$.
3. In the second sum, shift the index ($j = k + 1$): it is $\sum_{j=t+1}^{T} \gamma^{j-t} V(s_j)$. It cancels the third sum except for two end terms: $\gamma^{T-t} V(s_T) - V(s_t)$.
4. $V(s_T) = 0$ because $s_T$ is terminal. So the sum is $G_t - V(s_t)$. $\blacksquare$

So MC sends each state the whole chain of future TD errors, and TD(0) only the first one. TD(λ) below sends a decaying part of the chain.

Bias and variance #

	Monte Carlo	TD(0)
target for $V(s_t)$	$G_t$	$r_t + \gamma V(s_{t+1})$
bias	none: $\mathbb E[G_t \mid s_t] = V^\pi(s_t)$	yes, while $V \ne V^\pi$: the target's mean is $(T^\pi V)(s_t)$
variance of the target	high: a sum of many random rewards and transitions	low: one reward and one transition
needs	complete episodes	one transition $(s_t, r_t, s_{t+1})$; works online and in continuing tasks
Markov property	not used	used: $V(s_{t+1})$ must summarize the future
sensitive to the initial $V$	no	yes (the bias comes from it)

On the random walk, TD(0) usually learns faster than MC (Sutton and Barto, Figure 6.2). In our simulation (100 runs, 100 episodes, values start at 0.5) the best TD(0) step size, $\alpha = 0.05$, reaches an RMS error of about 0.036, while the best first-visit constant-α MC ($\alpha = 0.03$ or $0.04$) is at about 0.059. A larger $\alpha$ learns faster at first but stays noisier, so compare the methods at their best step sizes.

Batch MC and batch TD #

With a fixed, finite set of episodes, we can replay the data again and again. In batch updating, each sweep sums the increments $\alpha(\text{target} - V)$ over all the data and applies them at the end of the sweep. For a small $\alpha$ both methods converge, but to different values.

Theorem (batch limits).

1. Batch MC converges to the average of the observed returns from each state. This minimizes the squared error on the training returns.
2. Batch TD(0) converges to the value function of the maximum-likelihood Markov model of the data: with $\hat P(s' \mid s)$ the fraction of transitions from $s$ that go to $s'$, and $\hat r(s)$ the average reward after $s$,

This is the certainty-equivalence estimate: the value we would compute if the estimated model were exactly right.

Proof (of the fixed points). At the limit the summed increments are 0 for every state $s$.

• MC: $\sum_{\text{visits } i \text{ of } s} (G_i - V(s)) = 0$, so $V(s)$ is the mean of the returns $G_i$.
• TD: $\sum_{\text{transitions } i \text{ from } s} (r_i + \gamma V(s'_i) - V(s)) = 0$. Divide by the number of transitions from $s$: $\hat r(s) + \gamma \sum_{s'} \hat P(s' \mid s) V(s') - V(s) = 0$, the Bellman equation of the estimated model (with $V = 0$ at terminal states). $\blacksquare$

Example. Six episodes: "A, 0, B, 1" once; "B, 1" three times; "B, 0" twice ($\gamma = 1$).

• $V(B)$: six returns from B (one in the first episode, five in the others), four of them equal to 1. Both methods give $V(B) = 4/6 = 2/3$.
• Batch MC: the only return observed from A is 1, so $V(A) = 1$.
• Batch TD: in the data, A always goes to B with reward 0, so $V(A) = 0 + V(B) = 2/3$.

Which is better? MC fits the training returns exactly. TD uses what the data says about B, from all the episodes, to judge A. When the process really is Markov, TD's answer usually generalizes better. (Sutton and Barto's Example 6.4 uses eight episodes and gets MC $V(A) = 0$ against TD $V(A) = 3/4$.)

Interactive figure: loading…

n-step returns and the λ-return #

The n-step return uses $n$ real rewards, then bootstraps:

If the episode ends before $t + n$ ($t + n \ge T$), then $G_t^{(n)} = G_t$, the full return. $n = 1$ gives the TD(0) target; $n \ge T - t$ gives the MC target. n-step TD updates $V(s_t)$ toward $G_t^{(n)}$, $n$ steps later. A middle $n$ is often better than both ends.

The λ-return averages all n-step returns, with weights that decay geometrically, for $\lambda \in [0, 1]$:

The first part gives weight $(1-\lambda)\lambda^{n-1}$ to $G_t^{(n)}$. Every n-step return with $n \ge T - t$ equals $G_t$, so all their weight, $\lambda^{T-t-1}$, goes to the full return. The weights add up to 1: $(1-\lambda)\frac{1 - \lambda^{T-t-1}}{1-\lambda} + \lambda^{T-t-1} = 1$. With $\lambda = 0$, $G_t^\lambda = G_t^{(1)}$ (TD(0)); with $\lambda = 1$, $G_t^\lambda = G_t$ (MC).

Interactive figure: loading…

TD(λ): eligibility traces #

The λ-return needs the future, so it can only be computed at the end of the episode (the forward view). TD(λ) gets the same effect online with one number per state, the eligibility trace $z(s)$, which records how recently and how often $s$ was visited (the backward view).

At the start of each episode set $z(s) = 0$ for all $s$. At every step $t$:

1. $z(s) \leftarrow \gamma \lambda\, z(s)$ for every state (all traces decay);
2. $z(s_t) \leftarrow z(s_t) + 1$ (an accumulating trace);
3. $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$;
4. $V(s) \leftarrow V(s) + \alpha\, \delta_t\, z(s)$ for every state.

So the current TD error is sent back to a state visited $k$ steps ago with weight $(\gamma\lambda)^k$, and a state visited twice gets the sum of both weights.

Interactive figure: loading…

Theorem (forward view = backward view, offline). If the values are updated only at the end of the episode (offline), then for every state $s$ the sum of the TD(λ) updates equals the sum of the λ-return updates $\alpha\,(G_t^\lambda - V(s_t))$ over the visits $t$ of $s$.

Proof

1. Extend the identity for MC: with $V$ fixed during the episode, $G_t^\lambda - V(s_t) = \sum_{k=t}^{T-1} (\gamma\lambda)^{k-t}\, \delta_k$. (For $\lambda = 1$ this is the MC identity above; the general case follows from the same telescoping, using $G_t^\lambda = r_t + \gamma\big[(1-\lambda) V(s_{t+1}) + \lambda G_{t+1}^\lambda\big]$.)
2. Sum the forward-view updates of state $s$: $\alpha \sum_t \mathbb 1[s_t = s] \sum_{k \ge t} (\gamma\lambda)^{k-t} \delta_k$.
3. Swap the two sums: $\alpha \sum_k \delta_k \sum_{t \le k} (\gamma\lambda)^{k-t}\, \mathbb 1[s_t = s]$.
4. The inner sum is exactly the accumulating trace $z_k(s)$ after step $k$: each visit adds 1, and each step multiplies by $\gamma\lambda$. So the total is $\alpha \sum_k \delta_k z_k(s)$, the sum of the TD(λ) updates. $\blacksquare$

Two special cases: $\lambda = 0$ gives TD(0), and $\lambda = 1$ with offline updates gives every-visit MC (the identity $G_t - V(s_t) = \sum_k \gamma^{k-t}\delta_k$). With online updates the two views differ slightly, because $V$ changes during the episode; true online TD(λ) (van Seijen and Sutton, 2014) removes this difference with a modified trace.

Off-policy prediction with importance sampling #

Often the data comes from a behaviour policy $\pi_b$ (an old system, an exploring agent), but we want $V^\pi$ for a different target policy $\pi$. We need coverage: $\pi(a \mid s) > 0$ must imply $\pi_b(a \mid s) > 0$. The importance-sampling ratio of the rest of an episode is

Theorem. $\mathbb E_{\pi_b}[\rho_{t:T-1}\, G_t \mid s_t = s] = V^\pi(s)$.

Proof.

1. The probability of the trajectory $a_t, s_{t+1}, \dots, s_T$ under a policy $\mu$ is $\prod_{k=t}^{T-1} \mu(a_k \mid s_k)\, P(s_{k+1} \mid s_k, a_k)$.
2. In the ratio of this probability under $\pi$ and under $\pi_b$, the unknown transition probabilities cancel. What is left is $\rho_{t:T-1}$: we can compute it without the model.
3. So $\mathbb E_{\pi_b}[\rho G_t] = \sum_\tau \Pr_{\pi_b}(\tau)\, \frac{\Pr_\pi(\tau)}{\Pr_{\pi_b}(\tau)}\, G_t(\tau) = \sum_\tau \Pr_\pi(\tau)\, G_t(\tau) = V^\pi(s)$. $\blacksquare$

With $n$ returns $G_i$ from $s$ and their ratios $\rho_i$:

• ordinary importance sampling $\;V(s) = \frac{1}{n}\sum_i \rho_i G_i$: unbiased, but its variance can be huge (a product of many ratios), even infinite;
• weighted importance sampling $\;V(s) = \frac{\sum_i \rho_i G_i}{\sum_i \rho_i}$: biased for finite $n$ (with one return it simply gives that return), but the bias goes to 0 as $n$ grows. It is a weighted average of returns, so it always stays within their range, and in practice its variance is much lower.

Example. One step: "right" has return 1, "left" return 0. Target $\pi(\text{right}) = 0.9$, so $V^\pi = 0.9$; behaviour $\pi_b(\text{right}) = 0.5$. The ratios are $0.9/0.5 = 1.8$ for right and $0.1/0.5 = 0.2$ for left. Data: right, left, right, right.

• Ordinary: $(1.8 + 0 + 1.8 + 1.8)/4 = 1.35$: above 1, outside the range of possible returns.
• Weighted: $(1.8 \cdot 3)/(1.8 \cdot 3 + 0.2) = 5.4/5.6 = 0.964$.

Answers to section 1. (1) Monte Carlo. MC moves the state toward the return 1 at once. TD(0) moves only the last state before the reward in this episode; the information reaches earlier states over later episodes, one step per episode. (2) Yes. Batch MC converges to the average observed return of each state; batch TD converges to the values of the maximum-likelihood Markov model. In the A/B example, $V(A) = 1$ against $V(A) = 2/3$.

4. Worked example #

The random walk with all values 0.5, $\alpha = 0.1$, $\gamma = 1$, and one episode C → B → C → D → E → right end (+1). The transitions are (C, 0, B), (B, 0, C), (C, 0, D), (D, 0, E), (E, 1, end).

(a) TD(0). Every TD error before the last step is $0 + 0.5 - 0.5 = 0$. The last one is $\delta_4 = 1 + 0 - 0.5 = 0.5$. Only E moves: $V(E) = 0.5 + 0.1 \cdot 0.5 = 0.55$.

(b) TD(λ) with λ = 0.5. Here $\gamma\lambda = 0.5$. The traces after each step (decay first, then add 1):

step $t$	state	$z(B)$	$z(C)$	$z(D)$	$z(E)$	$\delta_t$
0	C	0	1	0	0	0
1	B	1	0.5	0	0	0
2	C	0.5	0.25 + 1 = 1.25	0	0	0
3	D	0.25	0.625	1	0	0
4	E	0.125	0.3125	0.5	1	0.5

Only the last TD error is nonzero, and $\alpha\delta_4 = 0.05$. So $V(E) = 0.5 + 0.05 \cdot 1 = 0.55$, $V(D) = 0.5 + 0.05 \cdot 0.5 = 0.525$, $V(C) = 0.5 + 0.05 \cdot 0.3125 = 0.515625$, and $V(B) = 0.5 + 0.05 \cdot 0.125 = 0.50625$. Note $z(C) = 0.5^4 + 0.5^2$: one term per visit.

(c) Check with the forward view. C is visited at $t = 0$ and $t = 2$. Since $V = 0.5$ everywhere during the episode, every n-step return that bootstraps is 0.5, and the full return is 1.

• At $t = 0$ (end 5 steps later): $G_0^\lambda = (1 - 0.5^4) \cdot 0.5 + 0.5^4 \cdot 1 = 0.9375 \cdot 0.5 + 0.0625 = 0.53125$.
• At $t = 2$ (end 3 steps later): $G_2^\lambda = (1 - 0.5^2) \cdot 0.5 + 0.5^2 \cdot 1 = 0.625$.
• Total update of C: $0.1\,(0.53125 - 0.5) + 0.1\,(0.625 - 0.5) = 0.003125 + 0.0125 = 0.015625 = 0.05 \cdot 0.3125$. ✓

(d) First-visit MC. Every visited state has return 1, so B, C, D and E all move to $0.5 + 0.1 \cdot (1 - 0.5) = 0.55$.

(e) TD(1). With λ = 1 the traces do not decay: $z(C) = 2$, $z(B) = z(D) = z(E) = 1$. So $V(C) = 0.5 + 0.05 \cdot 2 = 0.6$: two MC increments of 0.05, one per visit. This is offline every-visit MC.

5. In code #

NumPy checks the hand computations. The notebook implements MC, TD(0) and TD(λ) for whole data sets.

import numpy as np

# random walk: states A..E = 0..4; the episode C, B, C, D, E, right end (+1) as (s, r, s_next, done)
episode = [(2, 0, 1, False), (1, 0, 2, False), (2, 0, 3, False), (3, 0, 4, False), (4, 1, -1, True)]

def td_lambda(episode, lam, alpha=0.1, gamma=1.0):
    V, z = np.full(5, 0.5), np.zeros(5)
    for s, r, s2, done in episode:
        delta = r + (0.0 if done else gamma * V[s2]) - V[s]   # TD error; V = 0 after the end
        z *= gamma * lam                                       # all traces decay
        z[s] += 1.0                                            # accumulating trace
        V += alpha * delta * z
    return V, z

print(td_lambda(episode, 0.0)[0])     # [0.5  0.5  0.5  0.5  0.55]        TD(0): only E moves
V, z = td_lambda(episode, 0.5)
print(V)                              # [0.5  0.50625  0.515625  0.525  0.55]
print(z)                              # [0.  0.125  0.3125  0.5  1.]   final traces
print(td_lambda(episode, 1.0)[0])     # [0.5  0.55  0.6  0.55  0.55]       TD(1)

# first-visit constant-alpha MC: every visited state has the return G = 1
V = np.full(5, 0.5)
for s in dict.fromkeys(s for s, *_ in episode):   # each state once, in order of first visit
    V[s] += 0.1 * (1.0 - V[s])
print(V)                              # [0.5  0.55 0.55 0.55 0.55]

# importance sampling: target pi(right) = 0.9, behaviour pi_b(right) = 0.5
G = np.array([1.0, 0.0, 1.0, 1.0])                # right, left, right, right
rho = np.where(G == 1.0, 0.9 / 0.5, 0.1 / 0.5)    # 1.8 or 0.2
print(np.mean(rho * G), np.sum(rho * G) / np.sum(rho))   # 1.35 0.964...

6. Where it shows up #

• Value networks in deep RL. DQN regresses on one-step TD targets; Rainbow uses 3-step returns. A2C and PPO train their critic on n-step returns or λ-returns; GAE (lesson 08) is the λ-weighting of this lesson applied to advantages, with typical values $\gamma = 0.99$, $\lambda = 0.95$.
• RL for language models. When a response gets one reward at the end and $\gamma = 1$, every token's return equals that final reward: a Monte Carlo setting. A learned value model adds TD-style bootstrapping (lesson 09).
• Off-policy evaluation. Recommenders, ad systems and medical decision rules estimate the value of a new policy from logged data of the old one with (weighted, clipped or doubly robust) importance sampling, before any user sees it.
• Neuroscience. Dopamine neurons respond to unexpected reward and, after learning, to the cue that predicts it, as the TD error does (Schultz, Dayan and Montague, 1997).
• ML for science. Long simulations (molecular dynamics, climate, games) are expensive to run to the end; bootstrapped value estimates let an agent learn from partial runs.

7. Common mistakes #

• Bootstrapping past the end. The value after a terminal step is 0, not $V$ of some state. Use the "done" flag: $\delta_t = r_t + \gamma (1 - d_t) V(s_{t+1}) - V(s_t)$.
• Forward loops for returns. Returns need one backward pass, $G_t = r_t + \gamma G_{t+1}$; a forward loop that recomputes each sum is slow and error-prone.
• "TD is unbiased." Its target uses the current estimate, so it is biased until $V = V^\pi$. MC is unbiased (first-visit) but has high variance.
• Traces not reset. Eligibility traces start at 0 in every episode; old traces would send new TD errors to states of the previous episode.
• Decay and increment in the wrong order, or forgetting $\gamma$. The trace decays by $\gamma\lambda$, not by $\lambda$ alone.
• λ-return weights that do not sum to 1. At the end of an episode the remaining weight $\lambda^{T-t-1}$ goes to the full return $G_t$.
• Reward timing. Here $r_t$ follows $(s_t, a_t)$; in Sutton and Barto it is $R_{t+1}$. The TD error is $r_t + \gamma V(s_{t+1}) - V(s_t)$ in our notation and $R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ in theirs.
• Importance sampling without coverage. If $\pi_b(a \mid s) = 0$ for an action that $\pi$ uses, the data says nothing about it, and no reweighting can fix that.

8. Check yourself #

1. Write the MC target and the TD(0) target for $V(s_t)$. Which one bootstraps, and what does that mean?
   Answer

   MC: $G_t$. TD(0): $r_t + \gamma V(s_{t+1})$. TD bootstraps: it uses its own current estimate $V(s_{t+1})$ in place of the rest of the return.
2. Rewards $(0, 0, 2)$ then the end, $\gamma = 0.5$, and $V \equiv 1$ at the non-terminal states $s_0, s_1, s_2$. Compute $G_0$, $G_0^{(1)}$ and $G_0^{(2)}$.
   Answer

   $G_0 = 0 + 0.5 \cdot 0 + 0.25 \cdot 2 = 0.5$. $G_0^{(1)} = 0 + 0.5 \cdot V(s_1) = 0.5$. $G_0^{(2)} = 0 + 0.5 \cdot 0 + 0.25 \cdot V(s_2) = 0.25$.
3. Why does TD(0) usually have lower variance than MC?
   Answer

   Its target depends on one random reward and one random transition. The MC target $G_t$ sums all the random rewards until the end, and their variances add up.
4. What does batch TD(0) converge to, and why can it differ from batch MC?
   Answer

   The values of the maximum-likelihood Markov model of the data (certainty equivalence). MC fits each state's own observed returns and ignores that its successor states were also observed from other episodes.
5. With accumulating traces and $\gamma\lambda = 0.5$, a state is visited at steps 0 and 3. What is its trace after step 5?
   Answer

   $0.5^5 + 0.5^2 = 0.03125 + 0.25 = 0.28125$: one term per visit, each decayed by the number of steps since that visit.
6. Why is ordinary importance sampling unbiased, and why is weighted importance sampling used anyway?
   Answer

   Because $\mathbb E_{\pi_b}[\rho G] = \sum_\tau \Pr_\pi(\tau) G(\tau) = V^\pi$: the ratio turns behaviour probabilities into target probabilities. But its variance can be huge or infinite. Weighted IS is biased for finite $n$ (consistent), stays within the range of the returns, and usually has far lower variance.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Write the TD error $\delta_t$.

   Show answer

2. What does bootstrapping mean in TD learning?

   Show answer

3. Compare the bias and variance of the MC and TD(0) targets.

   Show answer

4. What does batch TD(0) converge to?

   Show answer

5. Batch data: "A, 0, B, 1" once, "B, 1" three times, "B, 0" twice. Give $V(A)$ for batch MC and batch TD.

   Show answer

6. Write the n-step return $G_t^{(n)}$.

   Show answer

7. What weight does the λ-return give to $G_t^{(n)}$, and where does the rest go at the end of an episode?

   Show answer

8. State the accumulating-trace update of TD(λ).

   Show answer

9. What are TD(λ) with λ = 0 and with λ = 1?

   Show answer

10. Ordinary vs weighted importance sampling: which is unbiased, and which stays in the range of the returns?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "MC vs TD: bias and variance?" — MC is unbiased with high variance and needs episode ends; TD is biased, has low variance, learns online and uses the Markov property. TD usually learns faster.
• "What is bootstrapping, and why can it be dangerous?" — Using your own estimate in the target. It speeds learning, but errors in $V$ feed back into the targets; with function approximation and off-policy data this can diverge (the deadly triad, lesson 06).
• "What does λ do in TD(λ) or GAE?" — It interpolates between one-step TD (λ = 0, low variance, high bias) and Monte Carlo (λ = 1, no bias, high variance), with geometric weights on n-step returns.
• "Explain eligibility traces." — A decaying memory of visited states; each TD error is sent back to them in proportion to their trace. Offline it equals the λ-return.
• "How do you evaluate a new policy from logged data?" — Importance sampling with $\rho$; prefer weighted or per-decision IS, clip large ratios, and check coverage.

10. Practice #

The notebook for this lesson runs in Colab. It has five exercises, each with a check cell and a folded solution:

1. td0_prediction: online TD(0) over a list of episodes; check the worked example.
2. mc_prediction: first-visit and every-visit, sample average (batch) and constant α; check the A/B batch example and Sutton and Barto's Example 6.4.
3. td_lambda_prediction: accumulating traces; check that λ = 0 equals TD(0) and the worked example.
4. Reproduce the RMS-error-vs-episodes plot on the random walk for several α, and check that TD(0) beats constant-α MC.
5. importance_sampling_estimates: ordinary and weighted IS; measure their bias and variance by simulation.

11. Watch and read #

Monte Carlo And Off-Policy Methods | Reinforcement Learning Part 3Mutual Information · 27 min

Monte Carlo prediction and importance sampling, with clear pictures.

Temporal Difference Learning (including Q-Learning) | Reinforcement Learning Part 4Mutual Information · 29 min

TD(0), bootstrapping and n-step methods; the Q-learning part belongs to lesson 05.

RL Course by David Silver - Lecture 4: Model-Free PredictionGoogle DeepMind · David Silver's RL course · 1 h 37 min

MC, TD(0), the AB batch example, n-step returns and TD(λ) with both views.

DeepMind x UCL RL Lecture Series - Model-free Prediction [5/13]Google DeepMind · Hado van Hasselt · 1 h 42 min

The same topics with more on bias, variance and the choice of λ.

• Sutton and Barto, Reinforcement Learning: An Introduction, 2nd edition, free PDF: §5.1 (MC prediction), §5.5 (importance sampling), §6.1–6.3 (TD(0), Examples 6.2 and 6.4, batch updating), §7.1 (n-step TD), §12.1–12.2 (λ-return, TD(λ)).
• Singh and Sutton, Reinforcement learning with replacing eligibility traces (1996): first-visit and every-visit MC, and the bias of every-visit MC.
• van Seijen and Sutton, True online TD(λ) (ICML 2014).
• Schultz, Dayan and Montague, A neural substrate of prediction and reward (Science, 1997): the TD error in dopamine neurons.