SARSA — On-Policy TD Control

🎯 Core Concept

SARSA learns an action-value function Q(s, a) by bootstrapping from the transition it actually experiences. Its name is literally the tuple it uses to update: State → Action → Reward → next State → next Action. Because the update uses the action the agent will really take next, SARSA is on-policy: it evaluates and improves the very policy it follows, exploration included.

Mental model: the cautious hiker. SARSA learns the value of the path it walks — including its own risky wanderings — so it prefers routes that stay safe even while exploring. Q-Learning, by contrast, dreams of the perfect path it might take if it never slipped.

🔑 Key Components

The SARSA quintuple

(s, a, r, s', a') — the update needs the next action a' chosen by the current policy, not the max over actions.

TD update rule

Move Q(s,a) a step toward the observed reward plus the discounted value of the next state-action actually chosen.

ε-greedy exploration

Mostly pick the greedy action; with probability ε roll the dice and explore. That exploration is baked into what SARSA learns.

α and γ

Learning rate α sets step size; discount γ weighs future rewards. Both shape stability and horizon.

⚙️ How It Works

Q(s,a) ← Q(s,a) + α [ r + γ·Q(s',a') − Q(s,a) ]

Observe state s; choose action a via ε-greedy on Q.
Take a, receive reward r, land in next state s'.
Choose next action a' — again via ε-greedy (this is the on-policy part).
Update Q(s,a) toward the TD target r + γ·Q(s',a').
Set s ← s', a ← a' and repeat until the episode ends.

SARSA (on-policy)

Learns value of the policy it follows. Accounts for exploration risk → safer, more conservative paths (walks away from the cliff edge).

Q-Learning (off-policy)

Uses max over next actions. Learns the greedy optimum regardless of exploration → bolder paths (hugs the cliff).

🌎 Real-World Applications

Robot navigation Safe autonomous control Traffic signal control Game-playing agents Adaptive routing Energy management

🧪 Checkpoint Questions

1. Why is SARSA called “on-policy” while Q-Learning is “off-policy”?

Hint: look at which next action enters the update — the one actually taken, or the greedy best?

2. In the cliff-walking problem, why does SARSA choose the longer, safer route while Q-Learning walks the cliff edge?

Hint: think about whose exploration risk gets folded into each algorithm's learned values.

3. What happens to SARSA's learned policy as ε is annealed toward 0 over training?

Hint: consider how the followed policy and the target policy converge as exploration fades.