Foundations — SARSA algorithm

Before you can read a single line of the SARSA update, you need to own a small pile of symbols. This page builds every one of them from nothing, in an order where each rests on the previous. Nothing is used before it is drawn.

1. The agent and the world (the picture everything sits on)

Look at the grid figure below. Each cell is a state. The little robot sits in one cell. The arrows leaving it are the actions it could pick. When it moves, a number pops out — that is the reward.

Why the topic needs this. SARSA is entirely a bookkeeping system over "state → action → reward → new state." If you cannot see that loop as a picture, every later symbol is floating in air.

2. Symbols for state and action: $s$, $a$, and the time subscript $t$

Think of $t$ as frame numbers in a flip-book. In frame $t$ the robot is in state $S_t$ and picks action $A_t$. Then the world advances the flip-book to frame $t+1$, where the robot is now in state $S_{t+1}$.

Why the topic needs this. The whole experience tuple $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$ is just these letters strung along the clock. Reading it fluently is reading SARSA.

3. Reward over time: $R_{t+1}$

Picture it as: you push a button at tick $t$, and the coin drops at tick $t+1$. The coin belongs to the transition, so we label it with the arriving moment.

Why the topic needs this. SARSA's whole job is to predict the total future reward. It starts from the one reward it can see right now, $R_{t+1}$, and folds in a guess about everything after.

4. The Q-value: $Q(s,a)$

Picture a giant spreadsheet: rows are states, columns are actions, each cell holds one number. See the figure.

The letter $Q$ just names that spreadsheet. $Q(S_t,A_t)$ reads off the one cell for "the state I'm in now, the action I just chose."

Why the topic needs this. SARSA is a rule for editing one cell of this table at a time. Everything else is machinery to decide the new number.

5. Total future reward and the discount factor $\gamma$

Rewards keep arriving forever. Adding infinitely many numbers can blow up, and a reward far in the future is less certain than one right now. So we shrink each future reward before adding it.

• If $\gamma =0$: only the immediate reward counts (the robot is totally short-sighted).
• If $\gamma$ close to $1$: rewards far away still matter a lot (far-sighted).
• $\gamma =1$: no shrinking at all — only safe when episodes end (like the cliff grid).

Why the topic needs this. The SARSA target $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$ has exactly this shape: one reward now, plus a discounted estimate of everything later. The $\gamma$ is the shrink knob.

6. The policy $\pi$ and $ϵ$-greedy exploration

A greedy policy always picks the action with the biggest $Q$. But if you only ever pick your current favourite, you never try alternatives that might be better. So we add a pinch of randomness.

Why the topic needs this. This is the beating heart of the on-policy idea. Because the robot sometimes moves randomly, it might stumble off a cliff. SARSA learns using the moves it actually makes (random ones included), so it learns to stay away from cliffs. That is the entire "safety" story of the parent note.

7. Expectation: ${\mathbb{E}}_{\pi }[\cdot ]$

If flipping a coin pays \1$forheadsand$$0$fortails,$\mathbb{E}[\text{pay}] = 0.5$.Youneveractuallyget$0.5$ on one flip — it's the long-run average.

Why the topic needs this. The world (and the $ϵ$-greedy policy) is random, so a single move's outcome is noisy. The Bellman equation defines $Q$ as an expectation — the true long-run average. SARSA can't compute that average directly, so it samples one outcome and nudges toward it repeatedly; over many nudges the noise averages out.

8. The learning rate $\alpha$

Picture walking toward a target: $\alpha$ is the fraction of the remaining distance you cover each step. Small $\alpha$ = slow but steady (averages out noise); big $\alpha$ = fast but jumpy.

Why the topic needs this. In the update $Q\leftarrow Q+\alpha {\delta }_t$, the $\alpha$ decides how much of the "surprise" ${\delta }_t$ actually changes the table cell.

9. The TD error ${\delta }_t$ — the surprise

• ${\delta }_t>0$: reality beat the guess → nudge the cell up.
• ${\delta }_t<0$: reality was worse → nudge down.
• ${\delta }_t=0$: perfect guess → leave it alone.

Why the topic needs this. Every SARSA update is literally "old value plus $\alpha$ times surprise." Once you own ${\delta }_t$, the update rule reads itself: $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha {\delta }_t.$

10. The ${\max }_a$ operator (so you can tell SARSA from Q-learning)

Why the topic needs this. Q-learning uses ${\max }_{a}Q(S_{t+1},a)$ (the best possible next value). SARSA instead uses $Q(S_{t+1},A_{t+1})$ (the value of the action it actually takes). Knowing what ${\max }_a$ does lets you see exactly the one symbol that separates the two algorithms.

Prerequisite map

Equipment checklist

State what each symbol means without peeking, then reveal:

Return to the parent when these are solid: SARSA algorithm.