SARSA algorithm: Exercises — AI-ML deep dive

Throughout, we reuse the one update rule that defines SARSA:

The single visual idea behind every calculation is below — keep it in view.

The red dot is the old estimate. The target is a fixed point on the number line. Every update slides the red dot a fraction $α$ of the way toward the target. That's all SARSA ever does.

Level 1 — Recognition

Exercise 1.1 (L1)

Which of the five values in the tuple $(S_{t}, A_{t}, R_{t + 1}, S_{t + 1}, A_{t + 1})$ is the one that makes SARSA on-policy rather than off-policy?

Recall Solution

The last element, $A_{t + 1}$ — the next action actually chosen by the policy. Because SARSA plugs that specific action's Q-value into the target (not the maximum over actions), it evaluates the policy the agent is truly following. That is the definition of on-policy.

Exercise 1.2 (L1)

Identify the TD target and the TD error in this expression: $Q \leftarrow Q + α [a 7 + b 0.9 \cdot c 10 - d 4]$

Recall Solution

TD target $= a + b \cdot c = 7 + 0.9 \times 10 = 16$ .
TD error $δ = target - d = 16 - 4 = 12$ . Here $a = R_{t + 1} = 7$ , $b = γ = 0.9$ , $c = Q (S_{t + 1}, A_{t + 1}) = 10$ , $d = Q (S_{t}, A_{t}) = 4$ .

Exercise 1.3 (L1)

A terminal state has been reached. What value does SARSA assign to $Q (terminal, \cdot)$ , and therefore what is the TD target on the final step?

Recall Solution

By convention $Q (terminal, \cdot) = 0$ . So on the step that lands in a terminal state, the target collapses to just the reward: $R_{t + 1} + γ \cdot 0 = R_{t + 1}$ .

Level 2 — Application

Exercise 2.1 (L2)

Given $Q (S_{t}, A_{t}) = 2.0$ , $R_{t + 1} = - 1$ , $γ = 0.9$ , $Q (S_{t + 1}, A_{t + 1}) = 5.0$ , $α = 0.5$ . Compute the updated $Q (S_{t}, A_{t})$ .

Recall Solution

Target $= - 1 + 0.9 \times 5.0 = - 1 + 4.5 = 3.5$ . $δ = 3.5 - 2.0 = 1.5$ . $Q \leftarrow 2.0 + 0.5 \times 1.5 = 2.0 + 0.75 = 2.75$ .

Exercise 2.2 (L2)

A terminal-step update. $Q (S_{t}, A_{t}) = - 4.0$ , reward $R_{t + 1} = + 10$ , next state is terminal, $α = 0.2$ , $γ = 1.0$ . Find the new $Q (S_{t}, A_{t})$ .

Recall Solution

Terminal ⇒ $Q (S_{t + 1}, \cdot) = 0$ , so target $= 10 + 1.0 \times 0 = 10$ . $δ = 10 - (- 4.0) = 14$ . $Q \leftarrow - 4.0 + 0.2 \times 14 = - 4.0 + 2.8 = - 1.2$ .

Exercise 2.3 (L2)

The Windy Gridworld numbers from the parent note: $Q (S_{t}, A_{t}) = - 15.3$ , $R_{t + 1} = - 1$ , $Q (S_{t + 1}, A_{t + 1}) = - 12.1$ , $α = 0.1$ , $γ = 0.9$ . Reproduce the update.

Recall Solution

Target $= - 1 + 0.9 \times (- 12.1) = - 1 - 10.89 = - 11.89$ . $δ = - 11.89 - (- 15.3) = 3.41$ (positive: we were too pessimistic). $Q \leftarrow - 15.3 + 0.1 \times 3.41 = - 15.3 + 0.341 = - 14.959$ .

Level 3 — Analysis

Exercise 3.1 (L3)

Show algebraically that the SARSA update is a weighted average: $Q_{new} = (1 - α) Q_{old} + α (target) .$ Then use it to explain why $Q_{new}$ always lies between $Q_{old}$ and the target when $α \in (0, 1)$ .

Recall Solution

Start from $Q_{new} = Q_{old} + α (target - Q_{old})$ . Distribute: $Q_{new} = Q_{old} + α target - α Q_{old} = (1 - α) Q_{old} + α target .$ Since $α \in (0, 1)$ , both weights $(1 - α)$ and $α$ are positive and sum to 1 — this is a convex combination. A convex combination of two numbers always sits on the segment joining them (look at the red dot in the figure sliding along that segment). Hence $Q_{new}$ can never overshoot past the target.

Exercise 3.2 (L3)

With target fixed at $T = 3.5$ and $Q_{old} = 2.0$ , compute $Q_{new}$ for $α = 0.25$ , then again for $α = 1.0$ . Interpret what $α = 1.0$ does.

Recall Solution

$α = 0.25$ : $Q_{new} = (0.75) (2.0) + (0.25) (3.5) = 1.5 + 0.875 = 2.375$ . $α = 1.0$ : $Q_{new} = (0) (2.0) + (1) (3.5) = 3.5$ . With $α = 1$ we discard the old estimate entirely and jump straight onto the target. That is maximally fast but maximally unstable — one noisy target and the estimate lurches with it.

Exercise 3.3 (L3)

The sign of the TD error tells a story. For each case say whether we over- or **under-**estimated and whether $Q$ moves up or down: (a) $δ = + 2.4$ (b) $δ = - 0.7$ (c) $δ = 0$ .

Recall Solution

(a) $δ > 0$ : outcome better than expected ⇒ we underestimated ⇒ $Q$ moves up (by $α \cdot 2.4$ ). (b) $δ < 0$ : outcome worse than expected ⇒ we overestimated ⇒ $Q$ moves down (by $α \cdot 0.7$ ). (c) $δ = 0$ : estimate already matched the target ⇒ $Q$ does not move. This is the fixed point the algorithm hunts for.

Level 4 — Synthesis

Exercise 4.1 (L4)

Run a two-step episode by hand. All Q-values start at $0$ . $α = 0.5$ , $γ = 1.0$ . Step 1: $S_{0} = A$ , $A_{0} = right$ , $R_{1} = - 1$ , $S_{1} = B$ , $A_{1} = right$ . Step 2: $S_{1} = B$ , $A_{1} = right$ , $R_{2} = - 1$ , $S_{2} = terminal$ . Compute $Q (A, right)$ and $Q (B, right)$ after both updates, in order.

Recall Solution

Step 1 update for $Q (A, right)$ : at update time $Q (B, right)$ is still $0$ . Target $= - 1 + 1.0 \times 0 = - 1$ . $δ = - 1 - 0 = - 1$ . $Q (A, right) \leftarrow 0 + 0.5 \times (- 1) = - 0.5$ . Step 2 update for $Q (B, right)$ : next state terminal ⇒ target $= - 1 + 0 = - 1$ . $δ = - 1$ . $Q (B, right) \leftarrow 0 + 0.5 \times (- 1) = - 0.5$ . Note the ordering: SARSA updates the earlier pair using the later pair's value, and here that value was still $0$ because $B$ hadn't been visited yet — reward information propagates backward only across future episodes.

Exercise 4.2 (L4)

Repeat the same episode a second time (values now start at the $- 0.5$ from Exercise 4.1, same trajectory, same $α = 0.5$ , $γ = 1.0$ ). Compute the new $Q (A, right)$ . Does the terminal reward finally reach state $A$ ?

Recall Solution

Now at the moment we update $Q (A, right)$ , the value $Q (B, right) = - 0.5$ (learned last episode). Target $= - 1 + 1.0 \times (- 0.5) = - 1.5$ . $δ = - 1.5 - (- 0.5) = - 1.0$ . $Q (A, right) \leftarrow - 0.5 + 0.5 \times (- 1.0) = - 1.0$ . Yes — the cost of the second step ( $B$ 's $- 0.5$ ) has now flowed back into $A$ . Each replay lets information seep one step further back. This backward trickle is the heartbeat of temporal-difference learning.

Exercise 4.3 (L4)

Stochastic-slip case (parent Example 3): "forward" from $s_{1}$ slips to $s_{2}$ . $Q (s_{1}, forward) = 5.0$ , $R_{t + 1} = - 2$ , at $s_{2}$ the policy picks $A_{t + 1} = left$ with $Q (s_{2}, left) = 3.5$ , $α = 0.2$ , $γ = 0.95$ . Find the new $Q (s_{1}, forward)$ and explain why SARSA now knows "forward is riskier than it looks."

Recall Solution

Target $= - 2 + 0.95 \times 3.5 = - 2 + 3.325 = 1.325$ . $δ = 1.325 - 5.0 = - 3.675$ (negative: this outing was worse than the stored optimism). $Q (s_{1}, forward) \leftarrow 5.0 + 0.2 \times (- 3.675) = 5.0 - 0.735 = 4.265$ . Because slips happen occasionally, SARSA folds their bad outcomes into the average value of "forward". Over many episodes $Q (s_{1}, forward)$ settles at the mean over both lucky and slippery results — the estimate is honest about risk.

Level 5 — Mastery

Exercise 5.1 (L5)

Same transition, two algorithms. State $S_{t + 1}$ has action-values $Q (S_{t + 1}, \cdot)$ : {left $= 3.5$ , right $= 8.0$ , up $= - 2.0$ }. The $ϵ$ -greedy policy happened to sample $A_{t + 1} = left$ . Given $Q (S_{t}, A_{t}) = 5.0$ , $R_{t + 1} = - 2$ , $α = 0.2$ , $γ = 0.95$ , compute the update under SARSA and under Q-learning. Explain the gap.

Recall Solution

SARSA uses the sampled action left ( $= 3.5$ ): Target $= - 2 + 0.95 \times 3.5 = 1.325$ ; $δ = 1.325 - 5.0 = - 3.675$ ; $Q \leftarrow 5.0 + 0.2 \times (- 3.675) = 4.265$ . Q-learning uses $max_{a} Q (S_{t + 1}, a) = 8.0$ : Target $= - 2 + 0.95 \times 8.0 = - 2 + 7.6 = 5.6$ ; $δ = 5.6 - 5.0 = 0.6$ ; $Q \leftarrow 5.0 + 0.2 \times 0.6 = 5.12$ . The gap: SARSA lowers the value because the actually taken action (left) was mediocre; Q-learning raises it because it optimistically assumes the best action (right) will be taken next. SARSA describes the world as it is explored; Q-learning describes an idealised greedy future.

Exercise 5.2 (L5)

Under what single condition do the SARSA and Q-learning updates become identical for a given transition? Prove it from the two targets.

Recall Solution

They coincide exactly when the sampled next action is a greedy action: $Q (S_{t + 1}, A_{t + 1}) = max_{a} Q (S_{t + 1}, a) .$ Then both targets equal $R_{t + 1} + γ max_{a} Q (S_{t + 1}, a)$ , so both $δ$ 's and both updates match. Practically this happens whenever the $ϵ$ -greedy coin lands on "exploit", or in the limit $ϵ \to 0$ where SARSA's policy becomes greedy and SARSA $\to$ Q-learning.

Exercise 5.3 (L5)

Fixed-point reasoning. Suppose $Q (S_{t}, A_{t})$ has converged so that the expected TD error is zero. Write the equation this implies and name it. Then argue why, for SARSA, that equation is the Bellman equation for the behaviour policy and not for the optimal policy.

Recall Solution

Expected error zero means $Q (s, a) = E_{π} [R_{t + 1} + γ Q (S_{t + 1}, A_{t + 1}) ∣ S_{t} = s, A_{t} = a],$ the Bellman expectation equation for $Q^{π}$ . Because $A_{t + 1}$ is drawn from the same policy $π$ that generated the data (e.g. $ϵ$ -greedy), the expectation is taken under $π$ , not under a max. Therefore the fixed point is $Q^{π}$ — the value of the policy actually being followed — which includes the cost of its own exploration, not the optimistic $Q^{*}$ that a max would produce.

Exercise 5.4 (L5)

Cliff-walking intuition made numeric. A state $s$ sits one cell above the cliff, with an action set of exactly 4 actions {up, down, left, right}. The greedy action is "right" (reward $- 1$ ), while "down" steps into the cliff (reward $- 100$ ). The agent runs $ϵ$ -greedy with $ϵ = 0.1$ and uniform exploration over all 4 actions. Using $γ = 1$ and the continuation values $Q (s^{'}, right after) = - 5$ for the right-branch and $Q (cliff, \cdot) = 0$ (episode ends after the fall), estimate the SARSA expected next-value contribution from the "right" and "down" branches only, and contrast it with the Q-learning target.

Recall Solution

First fix the action probabilities. Under $ϵ$ -greedy with $ϵ = 0.1$ and 4 actions, the greedy action gets $P (right) = (1 - ϵ) + \frac{ϵ}{4} = 0.9 + \frac{0.1}{4} = 0.9 + 0.025 = 0.925,$ and every non-greedy action (including "down") gets $P (down) = \frac{ϵ}{4} = \frac{0.1}{4} = 0.025.$ Why we look at only two branches: "left" and "up" are also possible (each with probability $0.025$ ), but the exercise asks only for the contribution of the risky "down" versus the good "right", so we form a partial expected value from those two terms. This is an intuition estimate, not the full expectation — the remaining two actions would add their own small terms.

SARSA partial expected next-value (reward folded in, $γ = 1$ ):

"right" branch value: $- 1 + (- 5) = - 6$ , weighted by $0.925$ .
"down" branch value: $- 100 + 0 = - 100$ , weighted by $0.025$ . $E [partial] \approx 0.925 \times (- 6) + 0.025 \times (- 100) = - 5.55 - 2.5 = - 8.05 .$ Q-learning target takes only the best branch, ignoring the slip risk entirely: $target = max_{a} (R + Q (s^{'}, a)) = - 1 + (- 5) = - 6 .$ Intuition: SARSA's estimate ( $- 8.05$ ) is worse (more negative) than Q-learning's ( $- 6$ ) because SARSA charges the state for the small-but-real chance of exploring "down" into the cliff. That extra pessimism makes SARSA down-value cliff-edge states and steer the learned policy onto the safer route — which is exactly why SARSA "walks the safe path."