Q-learning algorithm: Exercises — AI-ML deep dive

Formula The one rule everything here uses

$Q (s, a) \leftarrow Q (s, a) + α [TD target r + γ a^{'} max Q (s^{'}, a^{'}) - Q (s, a)]$ Reading it in plain words: the new value of taking action $a$ in state $s$ is the old value, nudged a fraction $α$ of the way toward a target. The target is "the reward $r$ you just got, plus a shrunk-down ( $γ$ ) estimate of the best you could do from the next state $s^{'}$ ." The bracket is the TD error $δ$ — how wrong we were.

$s, a$ = the current state and the action taken in it; $s^{'}$ = the state you land in next; $a^{'}$ = a candidate action in that next state.
$r$ = the immediate reward observed on this transition.
$α$ = learning rate, the step size, $0 < α \leq 1$ .
$γ$ = discount factor, how much we care about the future, $0 \leq γ \leq 1$ .
$max_{a^{'}} Q (s^{'}, a^{'})$ = the value of the best action available in the next state (this is what makes Q-learning off-policy).
$δ$ = TD error $= r + γ max_{a^{'}} Q (s^{'}, a^{'}) - Q (s, a)$ , i.e. the whole bracket — how far the target sits above (or below) the old estimate.
$Q^{⋆}$ = the optimal action-value, the fixed point everything converges to.

The figure below turns that rule into a single picture — read it left to right before touching any exercise.

Level 1 — Recognition

Exercise 1.1

Here $P (s^{'} ∣ s, a)$ means the transition probability: the chance that, taking action $a$ in state $s$ , the environment sends you to state $s^{'}$ (see Markov Decision Processes). For each property, name it: (a) Q-learning does not need to know $P (s^{'} ∣ s, a)$ . (b) Q-learning can follow an $ε$ -greedy policy yet still learn the optimal one. (c) Q-learning updates one estimate using another estimate.

Recall Solution

(a) Model-free — it never needs the transition probabilities $P (s^{'} ∣ s, a)$ ; it learns straight from sampled experience. (b) Off-policy — the behaviour policy (exploring) differs from the target policy (greedy/optimal) baked in by the $max$ . (c) Temporal-difference / bootstrapping.

Exercise 1.2

In the update rule, point to (a) the TD target and (b) the TD error, and (c) say what $Q (terminal, \cdot)$ equals and why.

Recall Solution

(a) TD target $= r + γ max_{a^{'}} Q (s^{'}, a^{'})$ . (b) TD error $δ = r + γ max_{a^{'}} Q (s^{'}, a^{'}) - Q (s, a)$ . (c) $Q (terminal, \cdot) = 0$ — once the episode ends there is no future reward to collect, so the "best future value" term is exactly zero.

Level 2 — Application

Exercise 2.1

$Q (s, a) = 0$ . You take $a$ , get $r = - 1$ , land in $s^{'}$ where $max_{a^{'}} Q (s^{'}, a^{'}) = 0$ . With $α = 0.1, γ = 0.9$ , compute the new $Q (s, a)$ .

Recall Solution

TD target $= - 1 + 0.9 \cdot 0 = - 1$ . TD error $= - 1 - 0 = - 1$ . $Q (s, a) \leftarrow 0 + 0.1 \cdot (- 1) = - 0.1$

Exercise 2.2

Late in training, $s = (2, 1)$ , $a = right$ , current $Q = - 0.4$ , $r = - 1$ , next state is the goal with $max_{a^{'}} Q (s^{'}, a^{'}) = 10$ . With $α = 0.1, γ = 0.9$ , compute the update.

Recall Solution

Target $= - 1 + 0.9 \cdot 10 = 8.0$ . Error $= 8.0 - (- 0.4) = 8.4$ . $Q \leftarrow - 0.4 + 0.1 \cdot 8.4 = - 0.4 + 0.84 = 0.44$ This is reward propagating backward: the goal's high value now leaks one step upstream. The figure below is drawn with these exact numbers — the teal dot sits at the old $- 0.4$ , the orange dot at the target $8.0$ , and the plum dot at the new $0.44$ , only a tenth of the way across because $α = 0.1$ .

Exercise 2.3

Same state twice in a row with $α = 0.5, γ = 1$ . $Q (s, a) = 2$ . First transition $r = 0$ , $max Q (s^{'}, \cdot) = 4$ . Then the update lands you back at the same $(s, a)$ and you observe $r = 0$ , $max Q (s^{'}, \cdot) = 4$ again. Give $Q (s, a)$ after both updates.

Recall Solution

Update 1: target $= 0 + 1 \cdot 4 = 4$ , error $= 4 - 2 = 2$ , $Q \leftarrow 2 + 0.5 \cdot 2 = 3$ . Update 2: target $= 4$ , error $= 4 - 3 = 1$ , $Q \leftarrow 3 + 0.5 \cdot 1 = 3.5$ . Each pass closes half the remaining gap ( $2 \to 3 \to 3.5 \to \dots \to 4$ ).

Level 3 — Analysis

Exercise 3.1 (Off-policy vs on-policy)

State $s$ : optimal action $a^{⋆}$ with $Q (s, a^{⋆}) = 5$ , suboptimal $a_{1}$ with $Q (s, a_{1}) = 2$ . Exploration forces the agent to take $a_{1}$ , gets $r = - 1$ , next state has $max_{a^{'}} Q (s^{'}, a^{'}) = 6$ but the action SARSA would actually take next has value $Q (s^{'}, a^{'}) = 3$ . With $α = 0.1, γ = 0.9$ , compute the update for Q-learning and for SARSA, and explain the difference.

Recall Solution

Q-learning (uses $max$ ): target $= - 1 + 0.9 \cdot 6 = 4.4$ , error $= 4.4 - 2 = 2.4$ , $Q (s, a_{1}) \leftarrow 2 + 0.1 \cdot 2.4 = 2.24$ SARSA (uses the actually chosen next action's value $3$ ): target $= - 1 + 0.9 \cdot 3 = 1.7$ , error $= 1.7 - 2 = - 0.3$ , $Q (s, a_{1}) \leftarrow 2 + 0.1 \cdot (- 0.3) = 1.97$ Difference: Q-learning bootstraps off the best possible future ( $6$ ), so it estimates the value under an optimal future even though it acted suboptimally. SARSA bootstraps off what it will really do next ( $3$ ), so it learns the value of its own exploratory policy. That is exactly the on-policy vs off-policy distinction.

Exercise 3.2 (Contraction / convergence rate)

Two pieces of notation first. The symbol $∥ f ∥_{\infty}$ is the supremum norm — the single biggest absolute value $f$ takes over all its inputs; here $∥ Q_{1} - Q_{2} ∥_{\infty}$ is "the largest gap between the two Q-tables over every state-action pair." The symbol $T$ is the Bellman optimality operator: a machine that eats a Q-table and returns an improved one, $[T Q] (s, a) = \sum_{s^{'}} P (s^{'} ∣ s, a) [r (s, a, s^{'}) + γ max_{a^{'}} Q (s^{'}, a^{'})] = E_{s^{'} \sim P (\cdot ∣ s, a)} [r + γ max_{a^{'}} Q (s^{'}, a^{'})] .$ Here the expectation $E$ is taken over the next state $s^{'}$ drawn from the transition distribution $P (s^{'} ∣ s, a)$ — that is what makes it a well-defined average and not just a single sample. It is one full "sweep" of the update applied everywhere at once.

Why is $T$ a contraction (why $γ < 1$ matters)? Take any two Q-tables $Q_{1}, Q_{2}$ . For a fixed $(s, a)$ the immediate-reward terms cancel, leaving $[T Q_{1}] (s, a) - [T Q_{2}] (s, a) = γ \sum_{s^{'}} P (s^{'} ∣ s, a) (max_{a^{'}} Q_{1} (s^{'}, a^{'}) - max_{a^{'}} Q_{2} (s^{'}, a^{'})) .$ Two facts finish it: (i) $∣ max_{a^{'}} Q_{1} (s^{'}, a^{'}) - max_{a^{'}} Q_{2} (s^{'}, a^{'}) ∣ \leq max_{a^{'}} ∣ Q_{1} (s^{'}, a^{'}) - Q_{2} (s^{'}, a^{'}) ∣ \leq ∥ Q_{1} - Q_{2} ∥_{\infty}$ (the biggest-gap bound), and (ii) $\sum_{s^{'}} P (s^{'} ∣ s, a) = 1$ (probabilities sum to one). So the whole right side is $\leq γ ∥ Q_{1} - Q_{2} ∥_{\infty}$ . Taking the max over all $(s, a)$ gives $∥ T Q_{1} - T Q_{2} ∥_{\infty} \leq γ ∥ Q_{1} - Q_{2} ∥_{\infty} .$ Because $γ < 1$ , each sweep strictly shrinks the biggest gap, so repeated sweeps drive any two tables together to one unique fixed point $Q^{⋆}$ (this is the Banach fixed-point idea). If $γ = 1$ the factor is $1$ and nothing is guaranteed to shrink — that is exactly why $γ < 1$ is required.

Question. If the initial max error is $∥ Q_{0} - Q^{⋆} ∥_{\infty} = 20$ and $γ = 0.9$ , how many exact Bellman sweeps guarantee the max error drops below $1$ ?

Recall Solution

After $k$ sweeps the error is at most $20 \cdot 0. 9^{k}$ . Solve $20 \cdot 0. 9^{k} < 1$ : $0. 9^{k} < 0.05 \Rightarrow k > \frac{l n 0.05}{l n 0.9} = \frac{- 2.9957}{- 0.10536} \approx 28.43.$ So $k = 29$ sweeps suffice. This is why $γ < 1$ is required: it forces the map to shrink distances by a fixed factor, guaranteeing a unique fixed point $Q^{⋆}$ . See Bellman Equations and Temporal Difference Learning.

Exercise 3.3 (Learning-rate schedule)

Which of these $α_{t}$ schedules satisfy the Robbins–Monro conditions $\sum_{t} α_{t} = \infty$ and $\sum_{t} α_{t}^{2} < \infty$ ? (a) $α_{t} = 1/ t$ , (b) $α_{t} = 1/ t$ , (c) $α_{t} = 0.1$ (constant).

Recall Solution

(a) $\sum 1/ t = \infty$ ✓ and $\sum 1/ t^{2} = π^{2} /6 < \infty$ ✓ → valid. (b) $\sum 1/ t = \infty$ ✓ but $\sum (1/ t)^{2} = \sum 1/ t = \infty$ ✗ → fails the square-summable part. (c) $\sum 0.1 = \infty$ ✓ but $\sum 0.01 = \infty$ ✗ → fails; a constant $α$ never converges to the exact $Q^{⋆}$ , it keeps jittering. Only (a) satisfies both.

Level 4 — Synthesis

Exercise 4.1 (Maximization bias — quantify it)

Two next-state actions each have true value $0$ . Your unbiased estimates are noisy: sample estimates come out $Q_{A} = + 1$ and $Q_{B} = - 1$ . (a) What does single-Q-learning use as the future value via $max$ ? (b) What is the true best future value? (c) Explain the sign of the bias, then state how Double Q-learning removes it.

Recall Solution

(a) $max (Q_{A}, Q_{B}) = max (1, - 1) = + 1$ . (b) True best future value $= max (0, 0) = 0$ . (c) The estimate ( $+ 1$ ) overshoots the truth ( $0$ ) — a positive maximization bias, because taking a $max$ over noisy numbers systematically grabs the luckily-overestimated one. Double Q-learning fix: keep two independent tables $Q_{1}, Q_{2}$ . Pick the action with one, $a^{⋆} = ar g max_{a^{'}} Q_{1} (s^{'}, a^{'})$ ; evaluate it with the other, target $= r + γ Q_{2} (s^{'}, a^{⋆})$ . Because selection and evaluation use independent noise, the lucky pick in $Q_{1}$ is not systematically lucky in $Q_{2}$ , so the bias cancels in expectation.

Exercise 4.2 (Backward reward propagation, multi-step)

A deterministic chain $s_{0} \to s_{1} \to s_{2} \to goal$ . Each step $r = 0$ except reaching the goal gives $r = 10$ . $γ = 0.9$ . There is a single move-forward action at each state, so we write $Q (s_{i})$ as shorthand for $Q (s_{i}, forward)$ — the action argument is dropped only because there is exactly one action. Compute $Q (s_{2}), Q (s_{1}), Q (s_{0})$ at convergence.

Recall Solution

Work backward. At $s_{2}$ the next state is the goal (terminal, value $0$ after), reward is $10$ : $Q (s_{2}) = 10 + 0.9 \cdot 0 = 10.$ At $s_{1}$ : reward $0$ , best next value is $Q (s_{2}) = 10$ : $Q (s_{1}) = 0 + 0.9 \cdot 10 = 9.$ At $s_{0}$ : $Q (s_{0}) = 0 + 0.9 \cdot 9 = 8.1.$ So $Q (s_{2}) = 10, Q (s_{1}) = 9, Q (s_{0}) = 8.1$ — the reward decays by $γ$ each step further from the goal. This is the Markov Decision Processes value smearing across states, and it is what Monte Carlo RL would also arrive at (via full returns instead of bootstrapping).

Exercise 4.3 (Design $ε$ -decay)

You want $ε = 1/ n$ where $n$ is the episode number (1-indexed). (a) Give $ε$ at episodes 1, 10, 100. (b) Over episodes $1 \dots 100$ , does the total exploration $\sum ε$ diverge, guaranteeing "infinitely often" visits if continued forever?

Recall Solution

(a) $ε_{1} = 1, ε_{10} = 0.1, ε_{100} = 0.01$ . (b) $\sum_{n = 1}^{\infty} 1/ n$ is the harmonic series $= \infty$ , so exploration never fully dies out in the summed sense — this supports the requirement that all $(s, a)$ be visited infinitely often. See Exploration-Exploitation Trade-off.

Level 5 — Mastery

Exercise 5.1 (Full single episode, from scratch)

$2$ -state chain: states $A, B$ ; single action each moves right. Start at $A$ . $A \to B$ gives $r = 0$ ; $B \to goal$ gives $r = 10$ (goal terminal). $α = 0.5, γ = 1$ , all $Q$ init $0$ . Run two episodes and give $Q (A), Q (B)$ after each.

Recall Solution

Episode 1. Step $A$ : target $= 0 + 1 \cdot max Q (B) = 0 + 0 = 0$ ; $Q (A) \leftarrow 0 + 0.5 (0 - 0) = 0$ . Step $B$ : target $= 10 + 1 \cdot 0 = 10$ ; $Q (B) \leftarrow 0 + 0.5 (10 - 0) = 5$ . After ep 1: $Q (A) = 0, Q (B) = 5$ . Episode 2. Step $A$ : target $= 0 + 1 \cdot Q (B) = 5$ ; $Q (A) \leftarrow 0 + 0.5 (5 - 0) = 2.5$ . Step $B$ : target $= 10$ ; $Q (B) \leftarrow 5 + 0.5 (10 - 5) = 7.5$ . After ep 2: $Q (A) = 2.5, Q (B) = 7.5$ . Notice the reward from the goal took one full episode to reach $A$ : $Q (A)$ was stuck at $0$ during ep 1 because $Q (B)$ was still $0$ when $A$ updated. Bootstrapping propagates value one hop per episode.

Exercise 5.2 (Off-policy convergence target)

In the $2$ -state chain of 5.1 but with $γ = 0.9$ , what are the exact converged values $Q^{⋆} (A), Q^{⋆} (B)$ ?

Recall Solution

Start from $B$ , whose next state is the terminal goal (value $0$ afterwards) with reward $10$ : $Q^{⋆} (B) = 10 + 0.9 \cdot 0 = 10.$ Then $A$ , whose reward is $0$ and whose best next value is $Q^{⋆} (B) = 10$ : $Q^{⋆} (A) = 0 + 0.9 \cdot Q^{⋆} (B) = 0.9 \cdot 10 = 9.$ So $Q^{⋆} (A) = 9, Q^{⋆} (B) = 10$ . Every finite run of 5.1's updates crawls toward these fixed points; the contraction (Ex 3.2) guarantees it.

Exercise 5.3 (Stochastic reward — why $α < 1$ )

Taking action $a$ in $s$ (terminal next) yields reward $+ 10$ with prob $0.5$ and $- 2$ with prob $0.5$ . (a) What is $Q^{⋆} (s, a)$ ? (b) If $α = 1$ , what does $Q (s, a)$ equal right after any single update? (c) Why does small $α$ help?

Recall Solution

(a) $Q^{⋆} (s, a) = E [r] = 0.5 \cdot 10 + 0.5 \cdot (- 2) = 5 - 1 = 4$ . (b) With $α = 1$ the update replaces: $Q \leftarrow r$ , so $Q$ is $+ 10$ or $- 2$ depending on the last sample — it never settles, pure high variance. (c) Small $α$ makes each update a running average, so noisy $+ 10/ - 2$ samples average toward the true mean $4$ . This is why $α = 1$ is only safe in deterministic worlds.

Exercise 5.4 (Compare families)

For each task pick the most natural algorithm from the list and give a one-line reason: (a) huge image-state Atari game, (b) needing an on-policy value that respects your own exploration risk, (c) continuous action steering of a robot arm.

Recall Solution

(a) Deep Q-Networks (DQN) — states are raw pixels, so tabular Q is impossible; use Function Approximation with a neural net (e.g. Atari Game Playing). (b) SARSA — on-policy, so its values include the cost of exploratory mistakes. (c) Policy Gradient Methods — continuous actions make $max_{a^{'}}$ intractable; parameterise the policy directly (e.g. Robot Control). Q-learning's $max$ needs a finite/enumerable action set.