Chapter 113

📝Draft

Q-Learning

Off-policy TD control: learning the optimal policy while exploring

Prerequisites:

SARSA

What You'll Learn

Explain the key difference between SARSA and Q-learning
Implement Q-learning for control
Explain what “off-policy” means and why it matters
Demonstrate Q-learning on Cliff Walking
Identify the “deadly triad” and its implications

SARSA is safe but learns the value of being epsilon-greedy. What if we could learn the optimal policy while still exploring? Q-learning does exactly this—it learns $Q^*$ regardless of what behavior policy we follow. It’s perhaps the most important algorithm in reinforcement learning.

Q-Learning vs SARSA: CliffWalking

Compare how Q-Learning (off-policy) and SARSA (on-policy) learn different paths.

🤖

🎯

Episodes: 0Reward: 0

🤖Agent

🎯Goal

Cliff (-100)

Start

Episodes

Steps

Episode Reward

Speed:SlowFast

Key Insight: Q-Learning learns the optimal policy (walking along the cliff edge) because it uses the maximum Q-value for updates, regardless of the exploration policy. SARSA learns a safer path (going up first) because its updates reflect the actual exploratory actions taken, which might accidentally fall off the cliff.

Why Q-Learning?

Q-learning’s key innovation is using max over next actions instead of the actual next action. This means we’re always learning toward the optimal policy, even while behaving suboptimally. The behavior policy can be anything—as long as it tries all actions eventually.

📖Q-Learning

An off-policy TD control algorithm that learns the optimal action-value function $Q^*$ directly. Unlike SARSA, Q-learning uses the maximum Q-value for the next state, learning about the greedy policy while following an exploratory one.

The Q-Learning Update

∑Mathematical Details

The Q-learning update rule:

$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t) \right]$

The difference from SARSA is just one word: max instead of the actual next action $A_{t+1}$ . But this one change is profound—it means we learn $Q^*$ instead of $Q^\pi$ .

</>Implementation

def q_learning_update(Q, state, action, reward, next_state,
                      alpha=0.1, gamma=0.99, done=False):
    """Single Q-learning update."""
    if done:
        td_target = reward
    else:
        # Key difference from SARSA: use max, not the actual next action
        td_target = reward + gamma * np.max(Q[next_state])

    td_error = td_target - Q[state][action]
    Q[state][action] += alpha * td_error
    return td_error

Chapter Overview

This chapter introduces Q-learning—the foundation of modern deep RL. We’ll cover:

The Q-Learning Idea

Learning optimal values regardless of behavior policy

The Q-Learning Algorithm

Complete algorithm with implementation and examples

SARSA vs Q-Learning

The CliffWalking experiment and when to use each

Convergence and the Deadly Triad

When Q-learning works and when it breaks

Prerequisites

This chapter assumes you’re comfortable with:

SARSA — The on-policy TD control algorithm
Introduction to TD Learning — TD updates and the TD error

Key Questions We’ll Answer

What does “off-policy” mean and why is it powerful?
How does one word change (max vs $A'$ ) transform the algorithm?
Why does Q-learning find the risky path in Cliff Walking?
What is the “deadly triad” and why should we care?

The Big Picture

The relationship between SARSA and Q-learning parallels a fundamental question in RL:

Should we learn about what we do, or what we should do?

SARSA learns about the policy being followed (including exploration)
Q-learning learns about the optimal policy (ignoring exploration)

Both are valid choices with different trade-offs. Q-learning finds the true optimal, but ignores exploration risk. SARSA is safer during training but may not find the best policy.

SARSA

Target:Q(S’, A’)

Learns:Q^π

Type:On-policy

Safety:Safer (accounts for ε)

Optimal:Eventually (as ε→0)

Q-Learning

Target:max_a Q(S’, a)

Learns:Q*

Type:Off-policy

Safety:Riskier during training

Optimal:Yes ✓

Key Takeaways

One word separates Q-learning from SARSA
The target uses max over next actions instead of the actually-taken next action A′.
That max makes it off-policy
Q-learning learns Q* regardless of the behavior policy, as long as all state-action pairs keep being tried.
Optimal values, but exploration risk ignored
On the cliff, Q-learning’s greedy policy hugs the edge—and its online training reward suffers for it.
The deadly triad can cause instability
Off-policy learning + function approximation + bootstrapping together can diverge; any two alone are fine.
Double Q-learning addresses maximization bias
Using max over noisy estimates systematically overestimates; decoupling selection from evaluation fixes it.
Q-learning is the foundation of deep RL
DQN and its descendants are Q-learning with neural networks—plus machinery to tame the triad.

Check Your Understanding

Check your understanding

1. What does it mean that Q-learning is "off-policy"?

It does not use a policy during trainingIt learns about the greedy (optimal) policy while following a different, exploratory behavior policyIt updates the policy less often than SARSA doesIt requires the behavior policy to be uniformly random

2. On Cliff Walking with fixed ε = 0.1, Q-learning finds the optimal path. Which algorithm collects more reward per episode during training, and why?

Q-learning—its policy is optimal, so its training reward must be higher tooSARSA—its safer path means exploratory random actions rarely cause a fall, while Q-learning’s cliff-hugging route falls frequentlyThey collect the same reward since both use ε = 0.1Neither—both fail to reach the goal during training

3. Why does standard Q-learning tend to overestimate action values (maximization bias)?

Because the learning rate is too high by defaultBecause rewards are usually positiveBecause taking a max over noisy estimates picks whichever error happens to be largest, biasing the target upwardBecause the discount factor compounds values over time

4. What is the "deadly triad"?

Exploration, exploitation, and safety—the three competing objectives in RLThe combination of off-policy learning, function approximation, and bootstrapping, which together can make learning divergeThe three hyperparameters (α, γ, ε) that must all be tuned correctlySparse rewards, long horizons, and partial observability

5. With a fixed ε = 0.1 behavior policy, what does Q-learning converge to?

Q^π for the ε-greedy policy, just like SARSAQ*, the optimal action values—the exploration in the behavior policy does not change the targetA mixture of Q^π and Q* weighted by εIt cannot converge while ε is nonzero

Next Chaptern-step Methods and Eligibility Traces→