Worked examples — SARSA algorithm

This page is the practice ground for the SARSA algorithm. If you want the theory of why the update rule looks the way it does, read the parent note first. Here we hunt down every kind of situation the SARSA update can face and work each one to a number. (Prefer Hinglish? See the Hinglish version.)

Before anything else, let's re-anchor the one formula everything here depends on. From the parent:

Four plain-word reminders, because we will never use a symbol we have not re-earned:

• $R_{t+1}$ is the reward — a single number the environment hands back right after the agent takes action $A_t$ at state $S_t$. The subscript $t+1$ is just bookkeeping: the action happens "at time $t$," the reward arrives "one tick later," so we tag it $t+1$. Think of it as "the immediate payoff for the move I just made." A negative $R_{t+1}$ is a penalty, a positive one is a treat.
• $\alpha$ (the learning rate) is a number between 0 and 1. It is the size of the step we take toward the new estimate. $\alpha =1$ means "trust the new number completely"; $\alpha =0.1$ means "move only 10% of the way."
• $\gamma$ (the discount factor) is a number between 0 and 1. It is how much we care about the future. $\gamma =1$ means a reward tomorrow is worth as much as one today; $\gamma =0$ means we only care about the reward right now.
• $Q(S_{t+1},A_{t+1})$ is the value of the action we actually chose next — never the best action. That "actually chose" is the whole soul of SARSA.

---

The scenario matrix

Every SARSA update is built from a handful of independent "dials." The table below lists each dial and the values it can take. To claim we've covered everything, we must hit each row at least once across our examples.

Cell class	What varies	Values we must show
A. Sign of TD error	Was reality better or worse than the guess?	${\delta }_t>0$ (pleasant surprise), ${\delta }_t<0$ (disappointment), ${\delta }_t=0$ (nothing to learn)
B. Terminal next state	Does the episode end on this step?	$Q(S_{t+1},\cdot )=0$ forced to zero
C. Discount extremes	How much future matters	$\gamma =0$ (myopic), $0<\gamma <1$ (normal), $\gamma =1$ (undiscounted)
D. Learning-rate extremes	Step size	$\alpha =1$ (full jump), small $\alpha$ (gentle)
E. Exploration action	Next action is not the greedy one	$A_{t+1}\ne \arg {\max }_{a}Q(S_{t+1},a)$
F. Word problem	Real domain (safety)	Cliff-walking safe-path story
G. Exam twist	SARSA vs Q-learning on same tuple	Compute both, compare

We will now work 8 examples that, taken together, light up every cell.

---

Forecast: Reward is a big $+10$ and the old guess was negative — do you expect $Q$ to go up or down, and by roughly how much with $\alpha =0.1$?

1. Target. $\text{Target}=R_{t+1}+\gamma Q(S_{t+1},A_{t+1})=10+1\cdot 0=10$. Why this step? The next state is terminal, so there is no future value to add — the $Q$ of any action at a terminal state is defined to be $0$. This is cell B.
2. TD error. ${\delta }_t=10-(-4.0)=14.0$. Why this step? ${\delta }_t$ is (target − old guess). It is strongly positive (cell A+): the outcome crushed our pessimistic $-4.0$ estimate.
3. Update. $Q\leftarrow -4.0+0.1\times 14.0=-4.0+1.4=-2.6$. Why this step? We only step 10% of the way (cell D-small), so the guess climbs from $-4.0$ toward $10$ but only reaches $-2.6$.

Verify: New value $-2.6$ lies between old $-4.0$ and target $10$ — a valid convex step. Distance closed $=|-4.0-(-2.6)|=1.4$, exactly $\alpha \cdot |{\delta }_t|=0.1\times 14$. ✓

---

Forecast: The next Q ($-12.1$) is less negative than the current one ($-15.3$). Will ${\delta }_t$ be positive or negative?

1. Target. $-1+0.9\times (-12.1)=-1-10.89=-11.89$. Why this step? We add the reward $R_{t+1}=-1$ to the future value, but first shrink that future value by $\gamma =0.9$ (cell C, normal γ) — a future worth $-12.1$ only counts as $-10.89$ from here.
2. TD error. ${\delta }_t=-11.89-(-15.3)=3.41$. Why this step? ${\delta }_t$ is (target − old guess). It is positive (cell A+): even though every number is negative, the target ($-11.89$) is higher than the old guess ($-15.3$), so our estimate was too pessimistic.
3. Update. $Q\leftarrow -15.3+0.1\times 3.41=-14.959$. Why this step? We nudge the old guess upward by 10% of the error (cell D-small): $0.1\times 3.41=0.341$, so $-15.3$ climbs to $-14.959$ — small and cautious.

Verify: $-14.959$ sits between $-15.3$ and $-11.89$, a valid convex step. Distance closed $=|-15.3-(-14.959)|=0.341=\alpha \cdot |{\delta }_t|$. ✓ Matches parent note exactly.

---

Forecast: Old guess is a rosy $+5.0$. The reward is a penalty and future value only $3.5$. Guess should drop — but how far with $\alpha =0.2$?

1. Target. $-2+0.95\times 3.5=-2+3.325=1.325$. Why this step? Immediate reward is the penalty $R_{t+1}=-2$; to it we add the discounted future, $0.95\times 3.5=3.325$. The two combine to $1.325$.
2. TD error. ${\delta }_t=1.325-5.0=-3.675$. Why this step? ${\delta }_t$ is (target − old guess). It is negative (clean cell A−): reality ($1.325$) fell far short of our optimistic $5.0$.
3. Update. $Q\leftarrow 5.0+0.2\times (-3.675)=5.0-0.735=4.265$. Why this step? A negative error drags the value down: $0.2\times (-3.675)=-0.735$, so the rosy $5.0$ deflates to $4.265$. This is exactly how SARSA learns to distrust the slippery "forward."

Verify: $4.265$ is between target $1.325$ and old $5.0$, moved down by $0.735=0.2\times 3.675$. ✓

---

Forecast: Compute the target first. If it equals the old guess, what happens to $Q$?

1. Target. $2.0+1.0\times 6.0=8.0$. Why this step? With $\gamma =1$ the future value $6.0$ is added at full weight, plus the reward $2.0$, giving exactly $8.0$.
2. TD error. ${\delta }_t=8.0-8.0=0$. Why this step? ${\delta }_t$ is (target − old guess), and here they coincide. When our guess already satisfies the Bellman relation, there is nothing to correct.
3. Update. $Q\leftarrow 8.0+0.5\times 0=8.0$. Why this step? Any $\alpha$ times zero is zero, so the value does not budge — a zero error means "leave it alone."

Verify: No change at all — this is the fixed point SARSA converges toward, where every ${\delta }_t$ has averaged out to zero. ✓ (cell A=0 covered.)

---

Forecast: With $\gamma =0$, does that enormous future value of $100$ matter at all?

1. Target. $7.0+0\times 100=7.0$. Why this step? $\gamma =0$ erases the future entirely — the agent only cares about the immediate reward. The $100$ is multiplied away.
2. TD error. ${\delta }_t=7.0-1.0=6.0$. Why this step? ${\delta }_t$ is (target − old guess): $7.0-1.0=6.0$, a positive surprise driven purely by the reward.
3. Update. $Q\leftarrow 1.0+1.0\times 6.0=7.0$. Why this step? $\alpha =1$ (cell D-full) means we throw away the old guess and jump straight onto the target — the full error is applied at once.

Verify: With $\alpha =1$ the new $Q$ equals the target exactly: $7.0=7.0$. ✓ Under $\gamma =0$, SARSA degenerates into "learn only the immediate reward" — a sanity check on the extreme.

---

Forecast: Q-learning would use the best ($9.0$). SARSA uses what we actually did ($2.0$). Which gives a smaller target — and therefore teaches more caution?

1. Target (SARSA). $0+0.9\times 2.0=1.8$. Why this step? SARSA is honest about the exploratory action it took — it plugs in $Q(S_{t+1},\text{down})=2.0$, not the max. This is cell E and the entire personality of SARSA.
2. TD error. ${\delta }_t=1.8-5.0=-3.2$. Why this step? ${\delta }_t$ is (target − old guess): $1.8-5.0=-3.2$, negative because the exploratory detour is worth less than we assumed.
3. Update. $Q\leftarrow 5.0+0.5\times (-3.2)=5.0-1.6=3.4$. Why this step? Half the negative error is applied: $0.5\times (-3.2)=-1.6$, pulling $5.0$ down to $3.4$ — SARSA lowers the value of a state whose exploration can hurt.

Verify: Had we (wrongly) used the max $9.0$, the target would be $0+0.9\times 9=8.1$ and $Q$ would rise to $6.55$. SARSA's honest number instead lowers the value, penalising the risky region where exploration hurts. The two answers differ — proof that on-policy ≠ off-policy. ✓

---

Figure 1 — what to look for. The grid below shows the same $4\times 12$ world. The coral band along the bottom (marked "CLIFF, reward -100") is the danger zone. Trace the two routes from S (bottom-left) to G (bottom-right): the lavender solid line is SARSA's route — it climbs up one row first, runs safely across the top, then drops to the goal, never touching the cliff. The red dashed line is Q-learning's route — it hugs the cliff edge along the bottom row, one slip away from a $-100$. The mint arrow at the start is the single step we compute below: $A_t=\text{up}$, taking the agent from $(3,0)$ to $(2,0)$ and updating $Q$ to $-0.5$.

Forecast: From the figure, why would SARSA prefer the upper lavender route over the direct red edge route that Q-learning loves?

1. Target. $R_{t+1}+\gamma Q((2,0),\text{right})=-1+1\cdot 0=-1$. Why this step? One step of movement costs $R_{t+1}=-1$; the next state $(2,0)$ is fresh, so its chosen-action value is still $0$, and $\gamma =1$ keeps it at full weight.
2. TD error. ${\delta }_t=-1-0=-1$. Why this step? ${\delta }_t$ is (target − old guess): the initial guess was $0$, so the error is just the step cost, $-1$.
3. Update. $Q((3,0),\text{up})\leftarrow 0+0.5\times (-1)=-0.5$. Why this step? Half the error is applied: $0.5\times (-1)=-0.5$, so the "up" action from the start now carries a small cost estimate of $-0.5$.

Verify: Matches parent note Step 1 exactly ($-0.5$). Why SARSA stays safe: along the cliff edge (the red route), an $ϵ$-greedy slip sometimes costs $-100$. Because SARSA plugs in the action it actually risks taking next (Example 6's logic), the cliff-edge cells accumulate that occasional $-100$, pushing their $Q$ far down. The upper lavender route never touches the cliff, so its expected value stays higher — SARSA climbs. ✓

---

Forecast: Both share reward and old guess. The only difference is which next-Q they use: SARSA uses $3.0$ (chosen), Q-learning uses $\max =10.0$. Predict which ends higher.

1. SARSA target. $1.0+0.8\times 3.0=3.4$. → $\delta =3.4-4.0=-0.6$ → $Q_{\text{SARSA}}=4.0+0.5\times (-0.6)=3.7$. Why this step? SARSA uses the actually taken left action ($3.0$). Its error is $-0.6$, and half of that ($-0.3$) drops the value from $4.0$ to $3.7$.
2. Q-learning target. $1.0+0.8\times 10.0=9.0$. → $\delta =9.0-4.0=5.0$ → $Q_{\text{QL}}=4.0+0.5\times 5.0=6.5$. Why this step? Q-learning uses ${\max }_{a}Q(S_{t+1},a)=10.0$, ignoring what was really done. Its error is a big $+5.0$, and half ($+2.5$) lifts the value from $4.0$ to $6.5$.
3. Difference. $6.5-3.7=2.8$. Why this step? Subtracting the two updated values isolates the cost of honesty: Q-learning's optimistic assumption inflates the value by $2.8$ over SARSA's cautious one.

Verify: $Q_{\text{SARSA}}=3.7$, $Q_{\text{QL}}=6.5$, gap $=2.8$. On-policy honesty produces the more conservative value. ✓

---

Recall

Recall What forces the next-state value to zero, and when?

A terminal state — by definition $Q(\text{terminal},\cdot )=0$, so the TD target collapses to just $R_{t+1}$. Which cell used this ::: Example 1 (cell B).

Recall If

$\alpha =1$, what does the new $Q$ equal? Exactly the TD target — we discard the old estimate entirely and jump onto it (Example 5).

Recall SARSA and Q-learning disagree only because of which quantity?

The next-state value: SARSA uses $Q(S_{t+1},A_{t+1})$ of the action actually chosen; Q-learning uses ${\max }_{a}Q(S_{t+1},a)$ (Examples 6 and 8).