15  Q-Learning

Core idea. Q-learning is the canonical off-policy temporal-difference control algorithm. It learns the optimal action-value function \(Q^*\) from sampled transitions, even when the behavior policy is exploratory. Its update is

\[ 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 mathematical idea is simple but powerful: replace the expectation in the Bellman optimality equation by a sample, and replace the unknown fixed point \(Q^*\) by the current estimate \(Q_t\).

15.1 Learning goals

After reading this chapter, students should be able to:

1. state the Bellman optimality equation for \(Q^*\);
2. derive the Q-learning update from a sample approximation to that equation;
3. explain precisely why Q-learning is off-policy;
4. distinguish the behavior policy from the target greedy policy;
5. implement tabular Q-learning for a finite discounted MDP;
6. state the main convergence conditions for tabular Q-learning;
7. explain the role of exploration and GLIE schedules;
8. compare Q-learning with SARSA and Expected SARSA;
9. describe maximization bias and the motivation for Double Q-learning;
10. use AI tools to audit Q-learning code without confusing the max target with an on-policy target.

15.2 12.1 From SARSA to Q-learning

In Chapter 11, SARSA used the one-step target

\[ R_{t+1}+\gamma Q(S_{t+1},A_{t+1}), \]

where \(A_{t+1}\) is the action actually selected by the current behavior policy. This makes SARSA an on-policy method.

Q-learning changes only one part of the target. Instead of using the next action that was actually taken, it uses the best action according to the current action-value table:

\[ R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a'). \]

This small change has a large conceptual consequence. Q-learning can learn about the greedy target policy while the data are generated by a different exploratory behavior policy.

SARSA estimates the value of the policy that generates the data. Q-learning estimates the value of the greedy policy suggested by the current action-value function.

To see the contrast, suppose the next state is \(s'\) and the current next-state action values are

\[ Q(s',a_1)=1.0,\qquad Q(s',a_2)=2.5,\qquad Q(s',a_3)=0.5. \]

If the behavior policy happens to choose \(a_3\), then SARSA uses \(Q(s',a_3)=0.5\). Q-learning uses \(\max_a Q(s',a)=2.5\). Thus Q-learning asks: what would happen if we acted greedily from the next state onward?

15.2.1 Interactive: SARSA target versus Q-learning target

The two algorithms observe the same transition, but they use different next-state values. SARSA uses the sampled next action. Q-learning uses the maximum over next actions.

15.3 12.2 Optimal action values

For a finite discounted MDP, the optimal state-value function is

\[ V^*(s)=\sup_\pi V^\pi(s). \]

The optimal action-value function is

\[ Q^*(s,a)= \mathbb E\left[ R_{t+1}+\gamma V^*(S_{t+1}) \mid S_t=s,A_t=a \right]. \]

Since \(V^*(s)=\max_a Q^*(s,a)\) in the finite-action case, we can write the Bellman optimality equation for action values as

\[ Q^*(s,a)= \sum_{s'}P(s'\mid s,a) \left[ r(s,a,s')+\gamma\max_{a'}Q^*(s',a') \right]. \]

Define the optimal action-value Bellman operator \(T_Q\) by

\[ (T_Q Q)(s,a)= \sum_{s'}P(s'\mid s,a) \left[ r(s,a,s')+\gamma\max_{a'}Q(s',a') \right]. \]

Then \(Q^*\) is the unique fixed point of

\[ T_QQ=Q. \]

The operator \(T_Q\) is a \(\gamma\)-contraction in the supremum norm on state-action functions:

\[ \lVert T_QQ_1-T_QQ_2\rVert_\infty \leq \gamma\lVert Q_1-Q_2\rVert_\infty. \]

Indeed, for any \((s,a)\),

\[ \begin{aligned} \left|(T_QQ_1)(s,a)-(T_QQ_2)(s,a)\right| &\leq \gamma\sum_{s'}P(s'\mid s,a) \left| \max_{a'}Q_1(s',a')-\max_{a'}Q_2(s',a') \right| \\ &\leq \gamma\sum_{s'}P(s'\mid s,a) \max_{a'}|Q_1(s',a')-Q_2(s',a')| \\ &\leq \gamma\lVert Q_1-Q_2\rVert_\infty. \end{aligned} \]

This contraction result gives uniqueness and motivates iterative approximation.

15.4 12.3 Q-value iteration and its sample analogue

If the full MDP model is known, we can apply the operator \(T_Q\) directly:

\[ Q_{k+1}=T_QQ_k. \]

In finite form,

\[ Q_{k+1}(s,a)= \sum_{s'}P(s'\mid s,a) \left[ r(s,a,s')+\gamma\max_{a'}Q_k(s',a') \right]. \]

This is Q-value iteration. It is a model-based dynamic programming method.

Q-learning is the model-free stochastic approximation version. Suppose that from \((S_t,A_t)\) we observe one sample \((R_{t+1},S_{t+1})\). The sampled target is

\[ Y_t^Q=R_{t+1}+\gamma\max_{a'}Q_t(S_{t+1},a'). \]

The corresponding temporal-difference error is

\[ \delta_t^Q = R_{t+1}+\gamma\max_{a'}Q_t(S_{t+1},a')-Q_t(S_t,A_t). \]

The tabular Q-learning update is

\[ Q_{t+1}(s,a)= \begin{cases} Q_t(s,a)+\alpha_t\delta_t^Q, & (s,a)=(S_t,A_t),\\ Q_t(s,a), & \text{otherwise}. \end{cases} \]

When \(S_{t+1}\) is terminal, the future term is set to zero:

\[ \delta_t^Q=R_{t+1}-Q_t(S_t,A_t). \]

Tabular Q-learning

1. Initialize \(Q(s,a)\), commonly \(0\) for all nonterminal state-action pairs.
2. For each episode, choose an initial state \(S_0\).
3. At time \(t\), choose \(A_t\) using a behavior policy, often \(\epsilon\)-greedy with respect to \(Q\).
4. Observe \(R_{t+1}\) and \(S_{t+1}\).
5. Update

\[ 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]. \]

6. Continue until a terminal state or a chosen horizon is reached.
7. Return the greedy policy

\[ \pi_Q(s)\in\arg\max_a Q(s,a). \]

15.5 12.4 Off-policy learning

A central mathematical distinction is between the behavior policy and the target policy.

The behavior policy \(b(a\mid s)\) generates data:

\[ A_t\sim b(\cdot\mid S_t). \]

The target policy is the greedy policy associated with the current action-value estimate:

\[ \pi_Q(s)\in\arg\max_a Q(s,a). \]

Q-learning is off-policy because the update target uses \(\pi_Q\) through the maximum operator, even if the observed action sequence was generated by \(b\).

This is different from SARSA, whose target is

\[ R_{t+1}+\gamma Q(S_{t+1},A_{t+1}), \]

where \(A_{t+1}\) is actually sampled from the behavior policy. The Q-learning target is

\[ R_{t+1}+\gamma Q(S_{t+1},\pi_Q(S_{t+1})). \]

Therefore, Q-learning separates how the data are collected from which policy is being learned.

15.5.1 Interactive: behavior policy versus greedy target policy

Q-learning can use exploratory actions to gather data while updating toward a greedy target. The behavior probabilities change with \(\epsilon\), but the target still uses the maximum action value.

15.6 12.5 Conditional expectation interpretation

The Q-learning update is a noisy approximation to the Bellman optimality operator. Conditional on \(S_t=s\), \(A_t=a\), and the current table \(Q_t\), the expected target is

\[ \mathbb E\left[ R_{t+1}+\gamma\max_{a'}Q_t(S_{t+1},a') \mid S_t=s,A_t=a,Q_t \right] = (T_QQ_t)(s,a). \]

Thus the update can be written as

\[ Q_{t+1}(S_t,A_t) = Q_t(S_t,A_t)+\alpha_t \left[ (T_QQ_t)(S_t,A_t)-Q_t(S_t,A_t)+M_{t+1} \right], \]

where \(M_{t+1}\) is a martingale-difference noise term. This connects Q-learning to stochastic approximation.

For MA Applied Math students, the key structure is a noisy fixed-point iteration. For MS Statistics students, the key structure is conditional expectation plus dependent sampling noise.

15.7 12.6 Convergence intuition

In the finite tabular setting, Q-learning converges to \(Q^*\) under standard assumptions:

1. the state and action spaces are finite;
2. rewards are bounded;
3. \(0\leq \gamma<1\);
4. every state-action pair is visited infinitely often;
5. the learning rates satisfy the Robbins-Monro conditions

\[ \sum_{t=0}^{\infty}\alpha_t(s,a)=\infty, \qquad \sum_{t=0}^{\infty}\alpha_t(s,a)^2<\infty \]

for each state-action pair \((s,a)\).

The first condition ensures finite-dimensional approximation. The second controls noise. The discount condition makes \(T_Q\) a contraction. Infinite visitation ensures that no state-action value is permanently ignored. The step-size conditions balance persistence and variance reduction.

A typical state-action specific learning rate is

\[ \alpha_t(s,a)=\frac{1}{N_t(s,a)}, \]

where \(N_t(s,a)\) is the number of times \((s,a)\) has been visited up to time \(t\).

15.7.1 Interactive: Q-learning convergence with noisy samples

This stylized simulation shows how repeated noisy updates move an action-value estimate toward its fixed point. Larger learning rates adapt quickly but remain noisy; smaller learning rates stabilize more slowly.

15.8 12.7 Exploration and GLIE behavior

Q-learning learns about the greedy target policy, but it still needs sufficient exploration to discover good actions. A common behavior policy is \(\epsilon\)-greedy:

\[ b_t(a\mid s)= \begin{cases} 1-\epsilon_t+\dfrac{\epsilon_t}{|\mathcal A(s)|}, & a\in\arg\max_b Q_t(s,b),\\ \dfrac{\epsilon_t}{|\mathcal A(s)|}, & \text{otherwise}. \end{cases} \]

A useful theoretical idea is GLIE, which stands for greedy in the limit with infinite exploration. Informally, a GLIE schedule satisfies two competing requirements:

1. every state-action pair continues to be explored sufficiently often;
2. the behavior policy becomes greedy in the limit.

A simple decay schedule is

\[ \epsilon_t=\frac{c}{c+t}. \]

In practice, one often uses slower decay, a fixed minimum exploration level, or problem-dependent schedules. The mathematically important point is that fast decay can cause the algorithm to stop exploring before it has reliable value estimates.

15.8.1 Interactive: exploration decay and action probabilities

A decaying \(\epsilon\) makes the behavior policy increasingly greedy. The figure shows how the probability of a greedy action and a non-greedy action change over time.

15.9 12.8 Maximization bias

The maximum of noisy estimates is usually biased upward. Suppose the true action values at a state are all zero:

\[ q(a)=0, \qquad a=1,\ldots,m. \]

Let the estimates be noisy:

\[ \widehat q(a)=q(a)+\varepsilon_a, \]

where the noise variables have mean zero. Then

\[ \mathbb E[\widehat q(a)]=0 \]

for each fixed action, but generally

\[ \mathbb E\left[\max_a \widehat q(a)\right]>0. \]

This matters because Q-learning uses the same estimated values both to choose the maximizing action and to evaluate that action:

\[ \max_{a'}Q(S_{t+1},a'). \]

This can lead to overestimation, especially in noisy environments.

15.9.1 Interactive: maximization bias

Even when each action-value estimate is unbiased, the maximum of several noisy estimates tends to be positively biased. The bias grows with the number of actions and with noise variance.

15.10 12.9 Double Q-learning

Double Q-learning reduces maximization bias by separating action selection from action evaluation. Maintain two tables, \(Q^A\) and \(Q^B\). On an update to \(Q^A\), select the maximizing action using \(Q^A\) but evaluate it using \(Q^B\):

\[ A^* = \arg\max_a Q^A(S_{t+1},a), \]

\[ Q^A(S_t,A_t) \leftarrow Q^A(S_t,A_t)+\alpha \left[ R_{t+1}+\gamma Q^B(S_{t+1},A^*)-Q^A(S_t,A_t) \right]. \]

On other updates, reverse the roles of \(Q^A\) and \(Q^B\). The final estimate is often taken as

\[ Q=\frac{1}{2}(Q^A+Q^B). \]

The idea is statistical: action selection and action evaluation should not use exactly the same noise if we want to reduce upward bias.

15.11 12.10 Relationship to value iteration

Value iteration updates the state-value function using a full model:

\[ V_{k+1}(s)=\max_a\sum_{s'}P(s'\mid s,a) \left[r(s,a,s')+\gamma V_k(s')\right]. \]

Q-value iteration updates action values using a full model:

\[ Q_{k+1}(s,a)=\sum_{s'}P(s'\mid s,a) \left[r(s,a,s')+\gamma\max_{a'}Q_k(s',a')\right]. \]

Q-learning replaces the expectation over \(s'\) and \(r\) with a single observed transition:

\[ Q_{t+1}(S_t,A_t)=Q_t(S_t,A_t)+\alpha_t \left[ R_{t+1}+\gamma\max_{a'}Q_t(S_{t+1},a')-Q_t(S_t,A_t) \right]. \]

Thus Q-learning is to Q-value iteration what TD learning is to policy evaluation: a sample-based stochastic approximation to a Bellman fixed point.

15.12 12.11 Python example: exact \(Q^*\) by dynamic programming

We first solve a small finite MDP exactly by Q-value iteration. This gives a reference solution for later Q-learning experiments.

import numpy as np

states = [0, 1, 2]
actions = [0, 1]
terminal = 2
gamma = 0.9

# P[s, a] is a list of (probability, next_state, reward)
P = {
    (0, 0): [(0.8, 0, -0.1), (0.2, 1, 0.0)],
    (0, 1): [(0.2, 0, -0.1), (0.8, 1, 0.0)],
    (1, 0): [(0.7, 0, -0.2), (0.3, 2, 1.0)],
    (1, 1): [(0.1, 0, -0.2), (0.9, 2, 1.0)],
    (2, 0): [(1.0, 2, 0.0)],
    (2, 1): [(1.0, 2, 0.0)],
}

Q = np.zeros((len(states), len(actions)))
errors = []

for k in range(200):
    Q_new = np.zeros_like(Q)
    for s in states:
        for a in actions:
            Q_new[s, a] = sum(
                prob * (reward + gamma * np.max(Q[sp]))
                for prob, sp, reward in P[(s, a)]
            )
    errors.append(np.max(np.abs(Q_new - Q)))
    Q = Q_new

print("Q* approximation:")
print(np.round(Q, 4))
print("Greedy actions:", np.argmax(Q, axis=1))
print("Final Bellman change:", errors[-1])

Q* approximation:
[[0.6766 0.8125]
 [0.6719 0.9531]
 [0.     0.    ]]
Greedy actions: [1 1 0]
Final Bellman change: 0.0

The greedy action at state \(s\) is

\[ \pi^*(s)\in\arg\max_a Q^*(s,a). \]

In this example, action \(1\) tends to move the system toward the rewarding terminal state more directly, so it becomes preferred in the nonterminal states.

15.13 12.12 Python example: tabular Q-learning

Now we learn from samples rather than from the known transition law.

import numpy as np

rng = np.random.default_rng(7243)

def step(s, a):
    transitions = P[(s, a)]
    probs = np.array([x[0] for x in transitions], dtype=float)
    idx = rng.choice(len(transitions), p=probs)
    _, sp, reward = transitions[idx]
    done = (sp == terminal)
    return sp, reward, done

def epsilon_greedy(Q, s, epsilon):
    if rng.random() < epsilon:
        return rng.integers(Q.shape[1])
    best = np.flatnonzero(Q[s] == np.max(Q[s]))
    return int(rng.choice(best))

Q_learn = np.zeros((len(states), len(actions)))
alpha = 0.15
epsilon = 0.20
episode_returns = []

for episode in range(3000):
    s = 0
    total = 0.0
    discount = 1.0
    for t in range(50):
        a = epsilon_greedy(Q_learn, s, epsilon)
        sp, reward, done = step(s, a)
        target = reward if done else reward + gamma * np.max(Q_learn[sp])
        Q_learn[s, a] += alpha * (target - Q_learn[s, a])
        total += discount * reward
        discount *= gamma
        s = sp
        if done:
            break
    episode_returns.append(total)

print("Learned Q table:")
print(np.round(Q_learn, 4))
print("Greedy actions:", np.argmax(Q_learn, axis=1))
print("Mean return over last 200 episodes:", np.mean(episode_returns[-200:]))

Learned Q table:
[[0.6819 0.8354]
 [0.6343 0.9995]
 [0.     0.    ]]
Greedy actions: [1 1 0]
Mean return over last 200 episodes: 0.7540608406000001

The learned table is not exactly equal to the dynamic programming solution because it is based on random samples, finite training, and a constant learning rate. With more episodes and a decaying learning rate, the estimates typically stabilize further.

15.14 12.13 Python example: Q-learning and maximization bias

The next simulation illustrates the statistical reason for overestimation. Suppose every action has true value zero, but each estimate is corrupted by independent Gaussian noise.

import numpy as np

rng = np.random.default_rng(5110)
trials = 50_000
noise_sd = 1.0
num_actions_grid = [2, 4, 8, 16, 32]

biases = []
for m in num_actions_grid:
    estimates = rng.normal(loc=0.0, scale=noise_sd, size=(trials, m))
    max_estimates = estimates.max(axis=1)
    biases.append(max_estimates.mean())

for m, bias in zip(num_actions_grid, biases):
    print(f"actions={m:2d}, estimated E[max noise]={bias:.3f}")

actions= 2, estimated E[max noise]=0.567
actions= 4, estimated E[max noise]=1.030
actions= 8, estimated E[max noise]=1.422
actions=16, estimated E[max noise]=1.765
actions=32, estimated E[max noise]=2.070

The true values are all zero, but the expected maximum is positive. This is not a programming bug. It is a property of the maximum of noisy estimates.

15.15 12.14 Python example: cliff walking comparison

Q-learning often learns a greedy path that is optimal under no exploration, while SARSA accounts for the risk induced by exploratory actions. The following small example compares their qualitative behavior in the cliff-walking environment.

import numpy as np

rng = np.random.default_rng(2026)
height, width = 4, 12
start = (3, 0)
goal = (3, 11)
actions_grid = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def to_id(pos):
    return pos[0] * width + pos[1]

def is_cliff(pos):
    return pos[0] == 3 and 1 <= pos[1] <= 10

def grid_step(state_id, action_id):
    row, col = divmod(state_id, width)
    dr, dc = actions_grid[action_id]
    nr = min(max(row + dr, 0), height - 1)
    nc = min(max(col + dc, 0), width - 1)
    next_pos = (nr, nc)
    if is_cliff(next_pos):
        return to_id(start), -100.0, False
    if next_pos == goal:
        return to_id(goal), -1.0, True
    return to_id(next_pos), -1.0, False

def eps_greedy_table(Q, s, eps):
    if rng.random() < eps:
        return rng.integers(Q.shape[1])
    best = np.flatnonzero(Q[s] == np.max(Q[s]))
    return int(rng.choice(best))

def train_q_learning(episodes=500, alpha=0.5, eps=0.1):
    n_states = height * width
    n_actions = len(actions_grid)
    Q = np.zeros((n_states, n_actions))
    returns = []
    for _ in range(episodes):
        s = to_id(start)
        total = 0.0
        for _ in range(300):
            a = eps_greedy_table(Q, s, eps)
            sp, r, done = grid_step(s, a)
            target = r if done else r + gamma * np.max(Q[sp])
            Q[s, a] += alpha * (target - Q[s, a])
            total += r
            s = sp
            if done:
                break
        returns.append(total)
    return Q, np.array(returns)

Q_cliff, returns = train_q_learning()
print("Mean return in first 50 episodes:", returns[:50].mean())
print("Mean return in last 50 episodes:", returns[-50:].mean())
print("Greedy action at start:", np.argmax(Q_cliff[to_id(start)]))

Mean return in first 50 episodes: -121.54
Mean return in last 50 episodes: -41.5
Greedy action at start: 0

The learned greedy policy tends to move near the cliff because the greedy target ignores the future exploratory risk. SARSA, by contrast, tends to learn a safer route when exploration remains present.

15.16 12.15 Diagnostics and common implementation errors

Several bugs appear frequently in Q-learning code.

First, the target should use the maximum over the next-state actions:

\[ R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a'). \]

Using the next sampled action gives SARSA, not Q-learning.

Second, terminal states should not bootstrap from future values. The terminal target is just the observed reward:

\[ Y_t=R_{t+1}. \]

Third, exploration must be applied when choosing behavior actions, not when computing the Q-learning target. The target is greedy even if the behavior is exploratory.

Fourth, if action values are initialized optimistically, early behavior may explore without an explicit large \(\epsilon\). This can be useful, but it should be recognized as an exploration mechanism.

15.16.1 AI-assisted code audit: Q-learning target

Ask an AI assistant to inspect a Q-learning implementation using the following checklist.

1. Does the target use max(Q[next_state]) rather than the sampled next action?
2. Are terminal states handled without bootstrapping?
3. Is the behavior policy exploratory during training?
4. Are state and action indices consistent throughout the code?
5. Is the learning rate applied only to the visited state-action pair?
6. Is evaluation performed with the greedy policy, not with the exploratory training policy?

Then ask the assistant to identify which lines implement behavior, target construction, bootstrapping, and policy extraction.

15.17 12.16 AI component: modeling from natural language

Real reinforcement learning projects often begin with an informal description. AI tools can help convert informal goals into MDP objects, but the mathematical model must be checked.

15.17.1 AI-assisted modeling task

Consider the prompt:

A warehouse robot must move packages from storage shelves to a loading station. Moving costs battery power, collisions are dangerous, and late deliveries are penalized.

Ask an AI assistant to propose:

1. a state space;
2. an action space;
3. a reward function;
4. terminal conditions;
5. whether Q-learning is appropriate;
6. what exploration risks are present.

Then critique the answer mathematically. In particular, check whether the proposed state representation is Markovian and whether the reward function creates unintended incentives.

15.18 12.17 Summary

Q-learning is a sample-based method for approximating the fixed point of the Bellman optimality equation for action values. Its central update is

\[ 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 method is off-policy because the data may be generated by an exploratory behavior policy while the target is greedy. In finite discounted MDPs, with sufficient exploration and appropriate learning rates, tabular Q-learning converges to \(Q^*\). Its strengths are simplicity and model-free control; its weaknesses include sensitivity to exploration, maximization bias, and instability when combined naively with function approximation.

15.19 Conceptual exercises

1. Explain in your own words why Q-learning is off-policy.
2. Compare the SARSA target and the Q-learning target for the same observed transition.
3. Why is exploration still necessary if Q-learning learns a greedy target policy?
4. Explain why terminal states require special treatment in the update.
5. What is maximization bias, and why does it matter for Q-learning?
6. Why can Q-learning and SARSA learn different policies in cliff walking?
7. Explain the difference between Q-value iteration and Q-learning.
8. Why is the contraction property important for the mathematical interpretation of Q-learning?

15.20 Mathematical exercises

1. Prove that \(T_Q\) is a \(\gamma\)-contraction in the supremum norm.
2. Show that if \(Q^*\) is known, then an optimal deterministic policy is given by \(\pi^*(s)\in\arg\max_aQ^*(s,a)\).
3. Derive the conditional expectation identity

\[ \mathbb E\left[ R_{t+1}+\gamma\max_{a'}Q_t(S_{t+1},a') \mid S_t=s,A_t=a,Q_t \right] = (T_QQ_t)(s,a). \]

4. Suppose two actions have noisy estimates \(\widehat q_1\) and \(\widehat q_2\) with true means zero. Explain why \(\mathbb E[\max(\widehat q_1,\widehat q_2)]\geq 0\).
5. For a deterministic finite MDP, simplify the Q-learning target.
6. Let \(\gamma=0\). What does Q-learning estimate?
7. If rewards are bounded by \(|R_t|\leq R_{\max}\), show that \(|Q^*(s,a)|\leq R_{\max}/(1-\gamma)\).
8. State the Robbins-Monro learning-rate conditions and explain their roles.

15.21 Computational exercises

1. Modify the Python example so that \(\epsilon\) decays over episodes. Compare the final greedy policy with the constant-\(\epsilon\) version.
2. Implement Double Q-learning for the small three-state MDP in this chapter.
3. Compare Q-learning and SARSA on the cliff-walking environment.
4. Add confidence bands to the return curves using repeated random seeds.
5. Change the discount factor \(\gamma\) and study how it affects learning speed.
6. Create a diagnostic plot of the Bellman error using the exact transition model.
7. Compare constant learning rates with \(\alpha_t(s,a)=1/N_t(s,a)\).
8. Implement optimistic initialization and compare it with \(\epsilon\)-greedy exploration.

15.22 AI-assisted exercises

1. Ask an AI assistant to explain why Q-learning is off-policy. Then identify whether the answer distinguishes behavior policy from target policy.
2. Give an AI assistant an intentionally incorrect Q-learning implementation that uses the SARSA target. Ask it to locate the error.
3. Ask an AI assistant to design a reward function for a robot navigation problem. Then critique whether the proposed reward could encourage unsafe shortcuts.
4. Ask an AI assistant to compare Q-learning, SARSA, and Expected SARSA in one table. Check every formula manually.
5. Ask an AI assistant to produce pseudocode for Double Q-learning. Verify that action selection and evaluation use different tables.

15.23 Notes for instructors

This chapter is a good place to emphasize three mathematical themes. First, Q-learning is a stochastic approximation to a contraction fixed point. Second, off-policy learning requires a careful distinction between the distribution that generates data and the policy whose value is being estimated. Third, the max operator is both the source of optimal control and the source of maximization bias.

For MA Applied Math students, emphasize fixed points, contraction mappings, and dynamic programming. For MS Statistics students, emphasize conditional expectation, sampling noise, exploration-induced dependence, and bias from nonlinear transformations of noisy estimates.