Visual walkthrough — SARSA algorithm

---

Step 1 — What is an agent even guessing?

WHAT. Picture a tiny robot on a grid. It is sitting on one square (call that its state, written $s$ — just "where I am"). From there it can pick a move like right or up (call that an action, written $a$ — "what I do"). The robot keeps a private notebook. On every page it writes a number:

$Q(s,a)$

Read this out loud: "$Q$ of $s$, $a$". It is the robot's guess of how good it is to do action $a$ while standing on square $s$ — counting all the reward it expects to collect from now until the game ends. Higher number = better idea.

WHY. Before we can correct a guess, we need a guess to correct. $Q(s,a)$ is that guess. Everything in SARSA is just a rule for improving this one number.

PICTURE. The robot on square $s$, an orange arrow showing action $a$, and the sticky-note value $Q(s,a)$ it currently believes.

---

Step 2 — Living through five things: S, A, R, S, A

WHAT. The robot takes one step. Five things happen, in order, and SARSA is literally named after them:

$\underset{\text{where I was}}{\underbrace{S_t}},\underset{\text{what I did}}{\underbrace{A_t}},\underset{\text{reward I got}}{\underbrace{R_{t+1}}},\underset{\text{where I landed}}{\underbrace{S_{t+1}}},\underset{\text{what I do next}}{\underbrace{A_{t+1}}}$

The little subscript $t$ just means "at time step $t$" — think of $t$ as "now" and $t+1$ as "one tick later". So $S_t$ is this square, $R_{t+1}$ is the reward that arrives after the move, $S_{t+1}$ is the next square, and $A_{t+1}$ is the move the robot actually decides to make there.

WHY. SARSA cannot update its guess for $(S_t,A_t)$ until it knows how that move turned out — and "how it turned out" needs the reward and the value of whatever it does next. That is why we must wait for all five.

PICTURE. A timeline: the robot leaves square $S_t$ via arrow $A_t$, collects reward token $R_{t+1}$, lands on $S_{t+1}$, and points a fresh arrow $A_{t+1}$.

---

Step 3 — Where should the guess have landed? (the target)

WHAT. Suppose the robot's guess $Q(S_t,A_t)$ could be perfect. What number would it equal? A perfect guess would say: "the total reward from here = the reward I get right now, plus the total reward from wherever I end up next." In symbols, the perfect value obeys the Bellman equation:

$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[\underset{\text{reward now}}{\underbrace{R_{t+1}}}+\underset{\text{how much I care about the future}}{\underbrace{\gamma }}\underset{\text{value of what happens next}}{\underbrace{Q^{\pi }(S_{t+1},A_{t+1})}}]$

Let us earn every new symbol:

• $\pi$ (Greek "pi") = the policy, the robot's habit of choosing actions. $Q^{\pi }$ means "value if I keep behaving like this".
• $\gamma$ (Greek "gamma"), a number between $0$ and $1$ = the discount factor. It shrinks future rewards: reward tomorrow counts a bit less than reward today. $\gamma =0$ means "I only care about the next reward"; $\gamma$ near $1$ means "the far future matters almost as much."
• ${\mathbb{E}}_{\pi }[\cdots ]$ = the expected (average) value over all the random ways the future might unfold while following $\pi$.

WHY. This gives us a target — a number we wish our guess equalled. Learning = closing the gap between guess and target. Notice the key SARSA choice: the future value is $Q^{\pi }(S_{t+1},A_{t+1})$ — the value of the action we actually take, not the best possible action. SARSA grades the plan it truly follows.

PICTURE. A balance scale: on the pan sits the guess $Q(S_t,A_t)$; on the other pan the target = reward token $R_{t+1}$ stacked on a shrunk-down copy ($\times \gamma$) of $Q(S_{t+1},A_{t+1})$.

---

Step 4 — How wrong was I? (the TD error)

WHAT. Subtract the guess from the target. That gap is the TD error, written ${\delta }_t$ (Greek "delta", meaning "difference"):

${\delta }_t=\underset{\text{Target: where the guess should be}}{\underbrace{R_{t+1}+\gamma Q(S_{t+1},A_{t+1})}}-\underset{\text{Guess: where it is now}}{\underbrace{Q(S_t,A_t)}}$

WHY. One number now tells us both direction and size of our mistake:

• ${\delta }_t>0$: the outcome beat the guess → we were too pessimistic → nudge the guess up.
• ${\delta }_t<0$: the outcome disappointed → we were too optimistic → nudge the guess down.
• ${\delta }_t=0$: guess already matched reality → no change needed (a degenerate but important case: converged states stop moving).

"TD" = temporal difference: a difference between two estimates taken one time step apart.

PICTURE. A number line with the guess and the target marked; a coloured bracket between them labelled ${\delta }_t$, arrows showing which way the guess must slide.

---

Step 5 — Nudge, don't jump (the learning rate)

WHAT. We do not slam the guess all the way to the target. We move only a fraction of the way. That fraction is $\alpha$ (Greek "alpha"), the learning rate, a number in $(0,1]$:

$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha {\delta }_t$

Term by term:

• $Q(S_t,A_t)$ on the left with $\leftarrow$ = "overwrite the old guess with the new one."
• $+\alpha {\delta }_t$ = take a step of size $\alpha$ in the direction the error points.

WHY not jump the whole way ($\alpha =1$)? Because the target itself is noisy — one lucky or unlucky roll of the dice could throw us off. A small $\alpha$ (like $0.1$) averages over many experiences, so the guess settles down smoothly instead of thrashing. Edge cases:

• $\alpha =1$: overwrite completely — fast but jittery in random worlds.
• $\alpha \to 0$: barely move — stable but painfully slow.

PICTURE. The guess as a dot on a track; the target far to the right; the dot slides only $\alpha$ of the distance (a short orange arrow), leaving a gap it will close over future visits.

Substituting ${\delta }_t$ back in gives the full rule the parent note stated:

---

Step 6 — The loop: why $A_{t+1}$ must be chosen before the update

WHAT. The update needs $Q(S_{t+1},A_{t+1})$. But $A_{t+1}$ is a choice — the robot must actually pick the next action before it can look up that value. So the correct order inside the loop is:

1. Take $A_t$, observe $R_{t+1}$ and $S_{t+1}$.
2. Choose $A_{t+1}$ from $S_{t+1}$ using the policy (e.g. $ϵ$-greedy).
3. Now update $Q(S_t,A_t)$ using that $A_{t+1}$.
4. Slide forward: $S_t\leftarrow S_{t+1}$, $A_t\leftarrow A_{t+1}$ — reuse the action you already chose.

WHY. If you updated before choosing $A_{t+1}$, the symbol in your formula would refer to nothing (or to the stale old action). This ordering is exactly what makes SARSA on-policy: it grades the move it is genuinely about to make.

PICTURE. A flow of one loop iteration, highlighting that "choose $A^{\prime }$" happens strictly before "update", and $A^{\prime }$ is carried into the next round.

---

Step 7 — Watch it run: the Windy Gridworld number

WHAT. Let us push real numbers through, matching Example 2 from the parent note. Given: $Q(S_t,A_t)=-15.3$, $R_{t+1}=-1$, $Q(S_{t+1},A_{t+1})=-12.1$, $\alpha =0.1$, $\gamma =0.9$.

Target: $-1+0.9\times (-12.1)=-1+(-10.89)=-11.89$ TD error: ${\delta }_t=-11.89-(-15.3)=+3.41(\text{positive}\Rightarrow \text{too pessimistic, nudge up})$ Update: $Q(S_t,A_t)\leftarrow -15.3+0.1\times 3.41=-15.3+0.341=\boxed{-14.959}$

WHY show this. It makes Steps 3–5 concrete: the guess crept from $-15.3$ toward the target $-11.89$, but only $10\%$ of the way — exactly the cautious nudge Step 5 promised.

PICTURE. A number line from $-16$ to $-11$: guess at $-15.3$, target at $-11.89$, error bracket $3.41$, and the small $0.341$ hop landing at $-14.959$.

Recall Check the second worked example (stochastic slip)

Given $Q(s_1,\text{forward})=5.0$, $R=-2$, $Q(s_2,\text{left})=3.5$, $\alpha =0.2$, $\gamma =0.95$. What is the new $Q$? Target $=-2+0.95\times 3.5=1.325$; $\delta =1.325-5.0=-3.675$; new $Q=5.0+0.2\times (-3.675)=4.265$ ::: $\boxed{4.265}$ — the guess dropped because the slip made "forward" turn out worse than believed.

---

The one-picture summary

Everything above is a single machine: experience → target → error → nudge → repeat.

Recall Feynman retelling — say it like you'd explain to a friend

A robot keeps a guess $Q(s,a)$ for how good each move is. It takes one step and watches five things go by: where it was, what it did, the reward, where it landed, and — crucially — what it decides to do next. It builds a "target" = the reward it just got plus a shrunk-down version of the value of that next move it actually picked. It compares target to guess; the difference $\delta$ says how wrong and which way. Then it slides its guess a small fraction $\alpha$ toward the target — never the whole way, so noise averages out. The one trick that makes it SARSA: it grades the move it's really about to make, not the best imaginable move. That is why it must choose the next action before updating, and that is why it plays it safe — it knows it might explore, so it never over-values walking along the cliff edge.

Recall Rapid self-test

What are the five things SARSA is named after? ::: State $S_t$, Action $A_t$, Reward $R_{t+1}$, next State $S_{t+1}$, next Action $A_{t+1}$. What does ${\delta }_t>0$ tell us to do? ::: The guess was too low (pessimistic); nudge $Q(S_t,A_t)$ up. Why choose $A_{t+1}$ before the update? ::: The update formula needs $Q(S_{t+1},A_{t+1})$, so that action must already exist. What does $\gamma$ do? ::: Discounts future reward — shrinks how much later rewards count versus immediate ones.