Module 5 — Temporal difference and Q-learning

Monte Carlo updates only at the end of an episode. Dynamic programming needs the full model. Temporal difference (TD) sits between them: it updates at every step, using the current value estimate as a proxy for the future. Q-learning is TD's most famous form, and it is what will solve FrozenLake in this module and CartPole in module 7.

The TD(0) update

For state values under a policy π, TD(0) writes:

$$V(s_t) \leftarrow V(s_t) + \alpha \, [\, r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \,]$$

The term in brackets is the TD error, δ_t. It is the difference between what the current estimate V(s_t) said and what one step of experience suggests it should be, r_{t+1} + γ V(s_{t+1}). The step size α ∈ (0, 1] controls how much of that error is absorbed.

The magic is in the middle term: V(s_{t+1}) is a bootstrap. Instead of waiting for the true return, TD uses its own noisy estimate at the next state. That introduces bias, but it kills the variance of Monte Carlo and lets you update after every single transition — even on tasks that never end.

SARSA: on-policy TD for Q

For action-values, the on-policy update is:

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \, [\, r_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \,]$$

The a_{t+1} in the target is the action that the current policy actually took at s_{t+1}. That is what the acronym encodes: State, Action, Reward, next State, next Action. SARSA learns the value of the policy it is currently following, exploration included.

Q-learning: off-policy TD for Q

Q-learning changes one term:

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \, [\, r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) \,]$$

The max_{a'} says: assume the agent will take the greedy action at s_{t+1}, whatever action was actually chosen. Q-learning learns the value of the greedy policy — the target policy — while the agent may follow a different behavior policy (typically epsilon-greedy, module 6). That decoupling is what "off-policy" means, and it is what makes Q-learning the workhorse of modules 6 and 7.

SARSA vs Q-learning: the cliff walking difference

The classical illustration is the "cliff walking" gridworld: a strip of cliff cells returns -100 and sends the agent back to start, everything else costs -1, the goal is at the far end. Both algorithms converge, but to different policies.

• SARSA learns to walk away from the cliff. Because its target uses the actual next action, and exploration occasionally sends it off the cliff, it internalizes that cost and prefers a safer route.
• Q-learning learns the optimal (shortest) policy, which walks right along the cliff edge. Because its target uses max, it dreams of behaving greedily and ignores the fact that its own exploration will fall off.

Which is "better" depends on what you are actually going to do at deployment. If you deploy the greedy policy — the usual case — Q-learning is better. If exploration continues in production, SARSA's safer estimate is more honest.

Tabular Q-learning on FrozenLake

import numpy as np
import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=True)
n_states, n_actions = env.observation_space.n, env.action_space.n

Q = np.zeros((n_states, n_actions))
alpha, gamma, epsilon = 0.8, 0.99, 1.0

rewards = []
for episode in range(20_000):
    state, _ = env.reset()
    done, total = False, 0.0
    while not done:
        # Epsilon-greedy behavior policy (see module 6).
        if np.random.rand() < epsilon:
            action = env.action_space.sample()
        else:
            action = np.argmax(Q[state])

        next_state, reward, term, trunc, _ = env.step(action)
        done = term or trunc

        # Q-learning update: target uses the greedy max, not the next action.
        td_target = reward + gamma * (0.0 if done else np.max(Q[next_state]))
        Q[state, action] += alpha * (td_target - Q[state, action])

        state = next_state
        total += reward

    rewards.append(total)
    epsilon = max(0.05, epsilon * 0.9995)      # decay towards greedy

After 20 000 episodes on slippery FrozenLake, the greedy policy argmax(Q, axis=1) reaches the goal about 72 % of the time — within a percent of the theoretical optimum returned by value iteration in module 4. That match is the sanity check: when a tabular algorithm agrees with dynamic programming, the exploration schedule is working.

The three knobs that dominate the result

Learning rate α. Too high and the update overreacts to noisy transitions, Q oscillates. Too low and convergence takes forever. On tabular problems α ∈ [0.1, 0.8] is usual. Theory requires a decaying α_t that satisfies Σ α_t = ∞, Σ α_t² < ∞ for the convergence proof, but in practice a small constant works.

Discount γ. With γ = 0.9, the update is myopic and the agent barely values distant rewards. On sparse-reward FrozenLake, γ < 0.95 prevents propagation of the goal reward back to the start; γ = 0.99 is a safer default for episodic tasks.

Initialization of Q. Zeros are neutral, high positive values create optimistic initialization that itself drives exploration — every unseen action looks tempting until proven otherwise. On some problems that removes the need for epsilon-greedy entirely.

The maximization bias

Q-learning's max overestimates Q*. On slippery FrozenLake this is small enough to ignore; on stochastic environments with many actions per state it is not, and it is the reason Double Q-learning — decoupling the max from its evaluation — exists. We revisit this in module 7 with Double DQN.

Summary

• TD updates at every step using a bootstrap: bias in exchange for lower variance and online learning.
• SARSA is on-policy and internalizes exploration cost; Q-learning is off-policy and estimates the greedy target regardless of what was actually done.
• Tabular Q-learning on FrozenLake matches the dynamic-programming optimum within a percent — the sanity check every implementation should pass.
• The three knobs that dominate the outcome are α, γ and the initialization of Q; optimistic init doubles as an exploration mechanism.

Next module: exploration proper — epsilon-greedy, its decay, and the alternatives when it is not enough.