Week 4: Monte Carlo and Temporal-Difference Learning

Purpose of this lecture#

The central question of this lecture: How can we learn the value of a state without ever seeing the end of an episode?

Dynamic programming (Week 3) showed how to solve finite MDPs exactly — but only when the environment's transition dynamics are fully known. In practice, agents must learn from experience: observing transitions, collecting rewards, and updating value estimates without access to $P$ or $R$.

On the surface, this seems impossible. The Bellman equation says $V(s) = \mathbb{E}[r + \gamma V(s')]$, which requires knowledge of next-state values — a future value that may depend on a distant reward. How can we improve estimates without that information?

The answer splits into two families of methods with radically different philosophies:

• Monte Carlo (MC) methods take the direct route: wait until the episode ends, observe the true return, and use it as an unbiased target. This guarantees correctness but suffers from high variance and cannot handle continuing tasks.
• Temporal-Difference (TDTemporal Difference) methods take a radical shortcut: bootstrap from current estimates. Use your own (wrong) value predictions to improve themselves. Philosophically strange — how can a wrong estimate help? — but it works, with lower variance than MC at the cost of bias.

These two approaches embody a fundamental tension in statistical learning: the bias-variance tradeoff. Every deep RLReinforcement Learning algorithm — DQNDeep Q-Network, PPOProximal Policy Optimisation, SACSoft Actor-Critic, actor-critic — is built on these ideas.

Learning from experience#

Assume the agent interacts with the environment and observes trajectories:

We aim to estimate value functions using sampled returns, rather than expectations over known transition probabilities. The Bellman equations from Week 3 remain the target — we are now computing them from data rather than from a model.

Three key design questions structure the space of methods:

• Do we wait until the episode ends before updating, or update incrementally?
• Do we use the true return or bootstrap from current estimates?
• How do we handle data collected under a different policy than the one we want to learn?

A worked example#

Before developing the theory, we trace both MC and TDTemporal Difference(0) through a single episode on the 4-state chain from Week 3. Suppose the current value estimates are:

$V = [V(s_1), V(s_2), V(s_3), V(s_4)] = [-0.5,\; 0.0,\; 0.3,\; 1.0]$

and we observe the episode: $s_2 \xrightarrow{R, r=0} s_3 \xrightarrow{R, r=0} s_4 \xrightarrow{\text{terminal}, r=+1}$

with $\gamma = 0.9$ and learning rate $\alpha = 0.1$.

Monte Carlo update for $s_2$:

The actual return from $s_2$: $G = 0 + 0.9 \cdot 0 + 0.9^2 \cdot 1 = 0.81$

MC update: $V(s_2) \leftarrow 0.0 + 0.1(0.81 - 0.0) = 0.081$

TDTemporal Difference(0) update for $s_2$ (using the one-step target $r + \gamma V(s_3)$): $\delta = 0 + 0.9 \cdot 0.3 - 0.0 = 0.27$ $V(s_2) \leftarrow 0.0 + 0.1 \cdot 0.27 = 0.027$

The MC update is larger because it uses the actual observed return, which is higher than the current estimate $V(s_3) = 0.3$ implies. The TDTemporal Difference update is smaller and biased by the inaccuracy in $V(s_3)$. As $V(s_3)$ improves toward $V^\pi(s_3)$, the TDTemporal Difference updates will converge to the same target as MC — but they do so earlier, one step at a time.

Monte Carlo methods#

Monte Carlo methods estimate value functions by averaging observed returns from complete episodes.

Return definition#

For time step $t$ in an episode of length $T$:

This is a direct sample of the target quantity $V^\pi(s_t) = \mathbb{E}_\pi[G_t \mid s_t]$.

First-visit vs every-visit Monte Carlo#

• First-visit MC: update the value estimate for $s$ using only the return from the first visit to $s$ in each episode. Samples across episodes are independent, making the estimator a standard i.i.d. average. Converges to $V^\pi(s)$ by the law of large numbers.
• Every-visit MC: update using the return from every visit to $s$ within an episode. Within-episode visits are correlated (the state was reached from the same history), so the samples are not independent. Despite this, every-visit MC is also consistent — it converges to $V^\pi$ — but the convergence analysis is less clean. First-visit MC is the standard choice when independence matters for theoretical guarantees.

Monte Carlo policy evaluation#

For a fixed policy $\pi$:

where $G_t$ is the observed return following a visit to $s$.

Key properties:

• Unbiased: $G_t$ is an unbiased sample of $V^\pi(s_t)$; no approximation of future values enters the target.
• High variance: $G_t$ is a sum of up to $T$ random variables. Variance scales with episode length and reward stochasticity. In long or high-variance episodes, single-sample MC estimates can be far from the true mean.
• Episode-terminal: updates are only possible after the episode ends. Cannot be used for continuing tasks.

Temporal-Difference learning#

Temporal-Difference learning combines:

• MC's ability to learn from experience (no model required)
• DP's ability to update before episode termination (bootstrapping)

Rather than waiting for the full return, TDTemporal Difference uses the current value estimate of the next state as a proxy for the remaining return.

TDTemporal Difference(0): the one-step update#

The TDTemporal Difference error $\delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t)$ is the discrepancy between:

• the one-step bootstrap target $r_{t+1} + \gamma V(s_{t+1})$, and
• the current estimate $V(s_t)$.

If $V = V^\pi$, then $\mathbb{E}[\delta_t] = 0$ — the Bellman equation is satisfied and there is no average error. TDTemporal Difference learning drives $\delta_t$ toward zero.

TDTemporal Difference(0) convergence#

Theorem: Under a fixed policy $\pi$, tabular TDTemporal Difference(0) converges to $V^\pi$ with probability 1, provided the step sizes satisfy the Robbins-Monro conditions:

Why it converges — the contraction argument: TDTemporal Difference(0) is a stochastic approximation of the fixed-point equation $V = T^\pi V$, where $T^\pi$ is the Bellman expectation operator from Week 3. Each TDTemporal Difference update is a noisy step in the direction of $T^\pi V - V$. Because $T^\pi$ is a $\gamma$-contraction (as established in Week 3), the fixed point $V^\pi$ is unique and the stochastic iterates converge to it — the contraction ensures the systematic signal toward $V^\pi$ dominates the noise over time.

The Robbins-Monro conditions encode two requirements: step sizes must be large enough to overcome noise (first condition: the series diverges) but must decay fast enough that the algorithm eventually settles (second condition: the sum of squares converges). A constant step size $\alpha$ satisfies neither in the limit but is used in practice for non-stationary problems.

Contrast with MC convergence: MC converges because it computes a sample mean of an unbiased estimator — no Bellman operator, no contraction required. The theoretical justification is simpler (law of large numbers) but the practical performance is worse due to high variance. TDTemporal Difference's convergence is more subtle because the target itself depends on the current estimate, but the contraction of $T^\pi$ is what ensures this circular dependency converges rather than diverges.

Bias-variance tradeoff: MC vs TDTemporal Difference vs n-step TDTemporal Difference#

The core distinction between MC and TDTemporal Difference is a bias-variance tradeoff that can be made precise.

Monte Carlo: unbiased, high variance#

The MC target $G_t$ satisfies $\mathbb{E}[G_t \mid s_t] = V^\pi(s_t)$ — it is an unbiased estimator of $V^\pi$. But $G_t = \sum_{k=0}^{T-t-1} \gamma^k r_{t+k+1}$ is a sum of $T - t$ random variables. With rewards bounded by $R_{\max}$, the return itself is bounded by $|G_t| \leq R_{\max}(1 + \gamma + \gamma^2 + \cdots) = R_{\max}/(1-\gamma)$, so

and variance grows in practice with the number of stochastic steps between $s_t$ and termination.

TDTemporal Difference(0): biased, low variance#

The TDTemporal Difference target $r_{t+1} + \gamma V(s_{t+1})$ uses the current estimate $V(s_{t+1})$, which equals $V^\pi(s_{t+1})$ only if the value function has converged. Before convergence, this introduces bootstrapping bias: the target is wrong by $\gamma(V(s_{t+1}) - V^\pi(s_{t+1}))$. However, the target depends on only one random variable ($r_{t+1}$, since $s_{t+1}$ is determined by $s_t$ and $a_t$), giving much lower variance than MC.

As $V \to V^\pi$, bootstrapping bias vanishes. TDTemporal Difference is asymptotically unbiased — in the limit, TDTemporal Difference and MC converge to the same value function.

n-step TDTemporal Difference: interpolating the tradeoff#

The $n$-step return uses $n$ actual rewards before bootstrapping:

• Bias: $\gamma^n (V(s_{t+n}) - V^\pi(s_{t+n}))$ — decays exponentially in $n$ because the bootstrap contribution is discounted over $n$ steps. Increasing $n$ reduces bias.
• Variance: scales with the sum of $n$ reward terms — increasing $n$ increases variance.

The update rule:

Special cases: $n = 1$ gives TDTemporal Difference(0); $n \to \infty$ gives Monte Carlo. The optimal $n$ depends on the environment's reward variance and current estimation accuracy — both unknown in practice, which motivates TDTemporal Difference(λ).

TDTemporal Difference(λ) and eligibility traces#

TDTemporal Difference(λ) generalizes n-step TDTemporal Difference by combining all n-step returns simultaneously, with weights that decay exponentially in $n$:

The λ-return#

The factor $(1-\lambda)$ normalizes the weights so they sum to 1. The λ-return is a geometric mixture: each n-step return contributes, with longer returns weighted by $\lambda^{n-1}$. For $\lambda = 0$: only the 1-step return contributes → TDTemporal Difference(0). For $\lambda = 1$: the mixture collapses to the full Monte Carlo return $G_t$.

The λ-return requires the full episode to compute, since it involves all $G_t^{(n)}$. Eligibility traces provide an online, incremental implementation.

Eligibility traces: the backward view#

Rather than computing the λ-return forward in time, eligibility traces distribute the TDTemporal Difference error backward through time to recently visited states.

The accumulating eligibility trace for state $s$:

• At each step, all traces decay by $\gamma\lambda$.
• The trace for the current state $s_t$ is incremented by 1.

The value update applies the current TDTemporal Difference error $\delta_t$ to all states, scaled by their trace:

Intuition: the trace is a decaying memory of recent visits, so a received reward shares credit ($\delta_t$) among recent states in proportion to how recently they were visited. This is temporal credit assignment implemented efficiently online.

The forward view (λ-return) and backward view (eligibility traces) are equivalent in expectation for linear function approximation — this equivalence is what justifies using the online trace algorithm as an efficient implementation of TDTemporal Difference(λ).

On-policy vs off-policy learning: formal definitions#

Before discussing control, we need to pin down the relationship between the policy that generates experience and the policy being learned.

• On-policy learning: the behavior policy $\mu$ (used to generate experience) equals the target policy $\pi$ (the policy being evaluated or improved). The agent learns about the policy it is currently following.
• Off-policy learning: the behavior policy $\mu \neq \pi$. The agent follows one policy to generate experience while learning about a different (typically better) policy.

This distinction has concrete consequences:

• On-policy methods are simpler and more stable, but the learned value function reflects the behavior policy, which may be exploratory and suboptimal.
• Off-policy methods can learn about the optimal policy while following a safe or exploratory behavior policy. They can also learn from data generated by any source — old policies, human demonstrations, replay buffers — making them far more data-efficient in practice. The cost is additional complexity and, in some cases, instability.

Control with TDTemporal Difference methods#

Control extends value estimation to policy improvement: learning optimal policies directly from experience.

On-policy control: SARSAState-Action-Reward-State-Action#

SARSAState-Action-Reward-State-Action updates the action-value function $Q(s,a)$ using the action actually taken under the current policy:

The name SARSAState-Action-Reward-State-Action records the five quantities involved in the update: $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$.

Since $a_{t+1}$ is sampled from the current policy, SARSAState-Action-Reward-State-Action evaluates the behavior policy. Under GLIE conditions (Greedy in the Limit with Infinite Exploration — the policy must explore all state-action pairs infinitely often and eventually become greedy), SARSAState-Action-Reward-State-Action converges to $Q^*$.

Practical consequence: SARSAState-Action-Reward-State-Action is conservative. In stochastic environments with dangerous actions, SARSAState-Action-Reward-State-Action learns to avoid them because it accounts for the possibility of taking them under the exploratory policy. This makes it suitable when safety during training matters.

Off-policy control: Q-learning#

Q-learning updates using the greedy action in the next state, regardless of which action the behavior policy actually takes:

The target $r_{t+1} + \gamma\max_{a'} Q(s_{t+1}, a')$ corresponds to the Bellman optimality equation for $Q^*$ — Q-learning is directly applying the model-free, sampled version of the value iteration update from Week 3.

Convergence: Q-learning converges to $Q^*$ with probability 1 under the Robbins-Monro conditions and the assumption that every state-action pair is visited infinitely often (coverage). Convergence holds regardless of the behavior policy — the $\max$ operator in the target decouples learning about the optimal policy from the policy used to collect data. This is what makes Q-learning off-policy.

Practical consequence: Q-learning can learn $Q^*$ from data collected by any exploratory policy, including $\epsilon$-greedy, random, or even human demonstrations. This is what lets DQNDeep Q-Network train from a replay buffer filled by older versions of the policy.

SARSAState-Action-Reward-State-Action vs Q-learning: a summary#

Exploration in control#

Tabular Q-learning converges only if every $(s, a)$ is visited infinitely often — but the greedy policy $\arg\max_a Q(s,a)$ revisits what it already believes, so without deliberate exploration the $Q$ table has permanent blind spots and the "optimal" policy is optimal only over visited states. Conversely pure exploration never converts knowledge into return. The rest of this section prices the tradeoff: ε-greedy's uniform noise wastes samples in large action spaces, UCB directs visits by uncertainty bonus, and in control (unlike bandits) each exploratory action reshapes the future state distribution — the callout below makes that coupling precise.

ε-greedy policies#

The simplest exploration strategy is ε-greedy: with probability $1 - \varepsilon$ take the greedy action $\arg\max_a Q(s, a)$; with probability $\varepsilon$ take a uniformly random action.

Properties:

• Every action has probability $\geq \varepsilon / |\mathcal{A}| > 0$, so coverage is guaranteed — every state-action pair is eventually visited.
• $\varepsilon = 0$ is fully greedy (no exploration); $\varepsilon = 1$ is uniform random (no exploitation).
• In practice, $\varepsilon$ is annealed over training: high early (to explore broadly), low late (to exploit learned values).

GLIE: the theoretical requirement for convergence#

Greedy in the Limit with Infinite Exploration (GLIE) states two conditions:

1. Every state-action pair is visited infinitely often: $\lim_{t \to \infty} N_t(s,a) = \infty$ for all $(s, a)$.
2. The policy converges to greedy: $\lim_{t \to \infty} \pi_t(a \mid s) = \mathbf{1}[a = \arg\max_{a'} Q(s, a')]$.

An ε-greedy policy satisfies GLIE if $\varepsilon_t \to 0$ as $t \to \infty$ and $\sum_t \varepsilon_t = \infty$ (e.g., $\varepsilon_t = 1/t$). Under GLIE, SARSA converges to $Q^*$ with probability 1.

The exploration problem in practice#

GLIE provides convergence guarantees but offers little guidance on how fast to anneal $\varepsilon$. In practice:

• Too fast: the agent commits to a suboptimal policy before discovering better options. Common in environments with sparse rewards where the high-reward region is rarely reached by random exploration.
• Too slow: the agent spends excessive time on random actions after the value function is already well-estimated. Sample efficiency suffers.

For deep RL, these issues are amplified: neural network approximators are initially poorly calibrated, and large action spaces make uniform random exploration impractical. Week 8 covers structured exploration strategies (UCB, Thompson sampling, curiosity-driven exploration) that address these limitations.

Importance sampling for off-policy learning#

When the behavior policy $\mu$ differs from the target policy $\pi$, updates must correct for the distributional mismatch.

The importance sampling ratio#

For off-policy TDTemporal Difference(0), the corrected update is:

When $\pi(a_t|s_t) = \mu(a_t|s_t)$, the ratio is 1 and we recover the standard TDTemporal Difference update. When $\pi$ assigns higher probability to $a_t$ than $\mu$ did, the update is amplified; when lower, it is dampened.

The variance explosion problem#

For multi-step returns, the importance sampling correction requires the product of ratios over all steps:

If $\pi$ and $\mu$ differ at each step, each ratio may be greater than 1, and their product grows exponentially in $n$. For full MC returns ($n = T$), the variance of the importance-weighted estimator can be so large as to make learning impractical — a single trajectory with a large product weight can dominate the entire estimate.

This variance explosion is a fundamental obstacle to off-policy learning with long trajectories, not an implementation detail.

The advantage function#

Before writing the PPOProximal Policy Optimisation objective, we need one more quantity: the advantage function, $A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s,a)$. It compares the value of taking a specific action $a$ in state $s$ and then following $\pi$, against the value of just following $\pi$ from $s$ — in one sentence, how much better (or worse) action $a$ is than the policy's average action in state $s$. $A^\pi(s,a) > 0$ means $a$ outperforms the policy's average behavior; $A^\pi(s,a) < 0$ means $a$ underperforms it. In the objectives below, $A_t$ denotes an estimate of $A^\pi(s_t, a_t)$ computed from sampled returns and a learned value function — this is the same $A_t$ referenced in Conceptual Question 5.

PPOProximal Policy Optimisation as a solution to variance explosion#

Proximal Policy Optimization (PPOProximal Policy Optimisation) — the algorithm used to fine-tune language models in RLHFReinforcement Learning from Human Feedback — addresses this directly by clipping the importance ratio:

where $\rho_t(\theta) = \pi_\theta(a_t|s_t) / \pi_{\theta_{\text{old}}}(a_t|s_t)$ is the ratio between the current and previous policy, and $A_t$ is the advantage estimate. Clipping the ratio to $[1-\epsilon, 1+\epsilon]$ prevents any single transition from contributing an outsized update — it controls the variance explosion at the cost of introducing a small bias. This is the direct application of importance sampling theory to policy optimization: the ratio $\rho_t$ appears in PPOProximal Policy Optimisation for exactly the same reason it appears in off-policy TDTemporal Difference — to correct for the fact that data was collected under a different (older) policy.

The deadly triad#

Week 5 introduces function approximation — replacing tables with neural networks. Before doing so, we need to see why combining the techniques of this lecture with function approximation can cause instability.

The deadly triad (Sutton & Barto) refers to the combination of three elements that, when present simultaneously, can cause divergence in value function learning:

1. Function approximation (representing $V$ or $Q$ with a neural network)
2. Bootstrapping (using current value estimates as targets — i.e., TDTemporal Difference methods)
3. Off-policy learning (learning about a target policy from data generated by a different behavior policy)

Each element alone is manageable: supervised regression with function approximation converges; tabular TDTemporal Difference(0) converges; tabular off-policy Q-learning converges. But the three together remove the convergence guarantees. The problem is that the combination of bootstrapping and function approximation creates a moving target (the target depends on the current parameters), and the off-policy distribution mismatch means the function approximator is trained on a distribution that does not match the on-policy distribution of the target policy — creating systematic bias that compounds.

DQNDeep Q-Network (Week 5) directly addresses the deadly triad through two mechanisms:

• Replay buffers decorrelate updates and stabilize the training distribution.
• Target networks freeze the bootstrap target temporarily, preventing the moving target problem from destabilizing training.

Understanding the deadly triad explains why these engineering choices are necessary — not as tricks, but as principled responses to a known theoretical obstacle.

Key takeaways#

The lecture develops a unified view of learning from experience through the lens of backup depth and policy alignment. Monte Carlo uses full-trajectory backups: unbiased but high variance, requiring complete episodes. TDTemporal Difference(0) uses one-step bootstrapped backups: lower variance but biased, converging by the contraction argument on the Bellman expectation operator. n-step TDTemporal Difference interpolates via a bias-variance tradeoff that decays bias exponentially in $n$. TDTemporal Difference(λ) resolves the tradeoff adaptively by combining all n-step returns, implemented online via eligibility traces that assign temporal credit backward through recent state visits.

SARSAState-Action-Reward-State-Action is on-policy TDTemporal Difference for control: it evaluates the behavior policy and converges to $Q^*$ only if the policy becomes greedy in the limit (GLIE). Q-learning is off-policy TDTemporal Difference: it targets $Q^*$ directly via the Bellman optimality operator and converges regardless of the behavior policy. Exploration is the mechanism that satisfies GLIE — $\varepsilon$-greedy policies guarantee coverage but introduce a tradeoff between exploration speed and exploitation quality. Importance sampling corrects for distribution mismatch in off-policy learning but suffers from exponential variance growth over long trajectories — the exact problem that PPOProximal Policy Optimisation's clipped ratio objective addresses in RLHFReinforcement Learning from Human Feedback. And the deadly triad of function approximation, bootstrapping, and off-policy learning identifies why combining these ingredients requires careful engineering, previewing the DQNDeep Q-Network stabilization techniques in Week 5.

Conceptual questions#

1. Trace through the worked example at the start of the lecture but for state $s_3$ in the same episode. Compute both the MC update and the TDTemporal Difference(0) update for $V(s_3)$. Which update moves $V(s_3)$ further from its current value, and why?

2. TDTemporal Difference(0) converges to $V^\pi$ while MC also converges to $V^\pi$. If they converge to the same target, why would you ever prefer TDTemporal Difference over MC? Give two distinct reasons, one theoretical and one practical.

3. An agent is learning in an environment where episodes are very long (thousands of steps) and rewards are sparse (most $r_t = 0$, with occasional large rewards). Should you use MC, TDTemporal Difference(0), or n-step TDTemporal Difference? Justify your answer in terms of the bias-variance tradeoff and the practical effect of episode length on each method.

4. Q-learning converges to $Q^*$ even when the behavior policy is $\epsilon$-greedy with $\epsilon = 0.5$ (i.e., random half the time). SARSAState-Action-Reward-State-Action with the same behavior policy converges to something other than $Q^*$. Explain precisely what SARSAState-Action-Reward-State-Action converges to and why the $\max$ operator in Q-learning's target makes the difference.

5. A language model is fine-tuned using PPOProximal Policy Optimisation. The old policy (used to collect rollouts) and the new policy (being updated) begin to diverge significantly during training. Explain why this causes the importance ratio $\rho_t$ to become large, why large $\rho_t$ is harmful in the context of the variance explosion problem, and how PPOProximal Policy Optimisation's clipping mechanism addresses this. What does the clipping introduce in return?

6. (Extension) The eligibility trace update is $e_t(s) = \gamma\lambda\, e_{t-1}(s) + \mathbf{1}[s_t = s]$. Show that when $\lambda = 0$, the $\text{TD}(\lambda)$ update with eligibility traces reduces exactly to the standard $\text{TD}(0)$ update. Then show that when $\lambda = 1$ and $\gamma = 1$, the update is equivalent to Monte Carlo.

7. (Extension) Double Q-learning maintains two independent Q-value estimates $Q_A$ and $Q_B$. When updating $Q_A$, the greedy action is selected using $Q_A$ but evaluated using $Q_B$: the target is $r + \gamma Q_B(s', \arg\max_{a'} Q_A(s', a'))$. Explain why standard Q-learning suffers from maximization bias, and how the decoupling in Double Q-learning addresses it.

Browser lab: first-visit Monte Carlo prediction#

Implement first-visit MC policy evaluation for a simple chain MDP. The environment has states $\{0, 1, 2, 3, 4\}$ where state 4 is terminal with reward $+1$ and all other transitions give reward $0$.

Runnable demos (complete solutions). Change n_episodes or alpha and re-run to see MC vs TD variance, or Q-learning vs SARSA near the cliff.

import numpy as np
from collections import defaultdict

def first_visit_mc(policy, n_episodes=3000, gamma=0.9, alpha=0.05):
    """First-visit Monte Carlo policy evaluation on a 5-state chain."""
    V = defaultdict(float)
    for _ in range(n_episodes):
        episode = []
        state = 0
        # Guard against infinite stay loops under pure "stay" policies
        for _ in range(200):
            if state == 4:
                break
            action = policy(state)
            next_state = state + 1 if action == 1 else state
            reward = 1.0 if next_state == 4 else 0.0
            episode.append((state, reward))
            state = next_state
        visited = set()
        G = 0.0
        for t in reversed(range(len(episode))):
            state, reward = episode[t]
            G = reward + gamma * G
            if state not in visited:
                visited.add(state)
                V[state] += alpha * (G - V[state])
    return V

np.random.seed(0)
policy = lambda s: np.random.choice([0, 1])
V_mc = first_visit_mc(policy)
print("MC values:", {s: round(v, 3) for s, v in sorted(V_mc.items())})
print("Notice: values rise toward the goal (state 4); early states have lower V.")

Browser lab: TD(0) prediction#

Same chain MDP — TD updates after every transition (no full return required).

import numpy as np
from collections import defaultdict

def td_zero(policy, n_episodes=3000, gamma=0.9, alpha=0.05):
    """TD(0) policy evaluation on the 5-state chain."""
    V = defaultdict(float)
    for _ in range(n_episodes):
        state = 0
        for _ in range(200):
            if state == 4:
                break
            action = policy(state)
            next_state = state + 1 if action == 1 else state
            reward = 1.0 if next_state == 4 else 0.0
            # δ = r + γ V(s') − V(s)
            delta = reward + gamma * V[next_state] - V[state]
            V[state] += alpha * delta
            state = next_state
    return V

np.random.seed(0)
V_td = td_zero(lambda s: np.random.choice([0, 1]))
print("TD(0) values:", {s: round(v, 3) for s, v in sorted(V_td.items())})
print("Notice: TD bootstraps from V(s') so it can learn before episodes finish.")

Compare MC and TD with the same random seed and episode budget. TD often looks smoother earlier; MC has higher variance but unbiased full returns.

Browser lab: Q-learning vs SARSA#

Chain with a "cliff" at state 3 (−5). Off-policy Q-learning uses $\max_{a'} Q(s',a')$; on-policy SARSA uses the action actually taken next under $\varepsilon$-greedy.

import numpy as np

def q_learning(n_episodes=1000, gamma=0.9, alpha=0.1, epsilon=0.1):
    """Off-policy Q-learning on a short chain with a cliff penalty."""
    n_states, n_actions = 8, 2  # 0=left, 1=right; state 7 terminal
    Q = np.zeros((n_states, n_actions))
    for _ in range(n_episodes):
        state = 0
        steps = 0
        while state != 7 and steps < 200:
            steps += 1
            action = np.random.randint(n_actions) if np.random.random() < epsilon else int(np.argmax(Q[state]))
            next_state = min(state + 1, 7) if action == 1 else max(state - 1, 0)
            reward = 10.0 if next_state == 7 else (-5.0 if next_state == 3 else 0.0)
            next_value = 0.0 if next_state == 7 else float(np.max(Q[next_state]))
            Q[state, action] += alpha * (reward + gamma * next_value - Q[state, action])
            state = next_state
    return Q

def sarsa(n_episodes=1000, gamma=0.9, alpha=0.1, epsilon=0.1):
    """On-policy SARSA."""
    n_states, n_actions = 8, 2
    Q = np.zeros((n_states, n_actions))
    for _ in range(n_episodes):
        state = 0
        action = int(np.argmax(Q[state])) if np.random.random() > epsilon else np.random.randint(n_actions)
        steps = 0
        while state != 7 and steps < 200:
            steps += 1
            next_state = min(state + 1, 7) if action == 1 else max(state - 1, 0)
            reward = 10.0 if next_state == 7 else (-5.0 if next_state == 3 else 0.0)
            next_action = (
                int(np.argmax(Q[next_state])) if np.random.random() > epsilon else np.random.randint(n_actions)
            )
            next_value = 0.0 if next_state == 7 else Q[next_state, next_action]
            Q[state, action] += alpha * (reward + gamma * next_value - Q[state, action])
            state, action = next_state, next_action
    return Q

np.random.seed(1)
Q_ql = q_learning()
Q_sarsa = sarsa()
print("Q-learning greedy actions (states 0–6):", [int(np.argmax(Q_ql[s])) for s in range(7)])
print("SARSA greedy actions (states 0–6):     ", [int(np.argmax(Q_sarsa[s])) for s in range(7)])
print("Q near cliff (state 2→3): QL", np.round(Q_ql[2], 2), "SARSA", np.round(Q_sarsa[2], 2))
print("Notice: SARSA accounts for ongoing ε-greedy risk; Q-learning is greedier about the optimal path.")

Looking ahead#

The next lecture introduces function approximation: replacing lookup tables with parametric models, and specifically neural networks. We will see that the deadly triad makes naive deep TDTemporal Difference learning unstable, and study how Deep Q-Networks (DQNDeep Q-Network) addresses this through target networks and experience replay — each of which can be understood as a direct engineering response to one component of the triad.

Further reading#

• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.), MIT Press. Chapters 5–7 cover MC methods, TD learning, and n-step TD in depth. Freely available online.
• Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning. (The paper that introduced Q-learning).
• Rummery, G. A., & Niranjan, M. (1994). On-line Q-learning using connectionist systems. (The technical report that introduced SARSAState-Action-Reward-State-Action).
• Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning. (The foundation of TDTemporal Difference learning).

Knowledge Check#

Test your understanding of Monte Carlo, TD, and eligibility traces.