SARSA algorithm

What is SARSA?

Core property: SARSA converges to the optimal Q-values for the behavior policy being followed (e.g., $\epsilon$-greedy), not necessarily the optimal gredy policy.

Derivation from First Principles

Step 1: Bellman Equation for Action-Values

The action-value function $Q^\pi(s,a)$ under policy $\pi$ satisfies:

$Q^\pi(s,a) = \mathbb{E}_\pi[R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) \mid S_t=s, A_t=a]$

Why this form? The expected return from $(s,a)$ equals the immediate reward plus the discounted value of where the policy actually takes you next.

Step 2: TD Error for Q-values

The TD error measures how wrong our current estimate is:

$\delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)$

Why this matters?

• If $\delta_t > 0$: We underestimated $Q(S_t, A_t)$ — the outcome was better than expected.
• If $\delta_t < 0$: We overestimated — the outcome was worse.

Key insight: We use $A_{t+1}$ (the action actually chosen at $S_{t+1}$ by the current policy), not $\max_a Q(S_{t+1}, a)$.

Step 3: SARSA Update Rule

Where:

• $\alpha \in (0,1]$ is the learning rate
• $\gamma \in [0,1)$ is the discount factor
• $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ is the experience tuple

Derivation: Apply stochastic gradient descent to minimize $(Q^\pi(s,a) - Q(s,a))^2$. The target is $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$, and we move our estimate toward it by $\alpha \cdot \delta_t$.

The Complete SARSA Algorithm

Initialize Q(s,a) arbitrarily (often 0) for all s∈ S, a ∈ A
Set Q(terminal, ·) = 0

For each episode:
    Initialize S
    Choose A from S using policy derived from Q (e.g., ε-greedy)
    For each step of episode:
        Take action A, observe R, S'
        Choose A' from S' using policy derived from Q (ε-greedy)
        Q(S, A) ← Q(S, A) + α[R + γQ(S', A') - Q(S, A)]
        S ← S'
        A ← A'
    Until S is terminal

WHY the algorithm works this way:

1. Initialize S: Start episode in a valid state
2. Choose A before the loop: We need an action to take the first step
3. Choose A' inside the loop: SARSA needs the next action to update, so we select it before updating
4. Update with A': This is on-policy — we use the action we'll actually take
5. S ← S', A ← A': Move forward with the action we already chose

Worked Examples

Setup:

• Grid world: 4×12, start at (3,0), goal at (3,11)
• Actions: up, down, left, right
• Reward: -1 per step, -100 for cliff (row 3, columns 1-10)
• Policy: $\epsilon$-greedy with $\epsilon=0.1$
• $\alpha=0.5$, $\gamma=1.0$

Episode trace:

Step	$S_t$	$A_t$	$R_{t+1}$	$S_{t+1}$	$A_{t+1}$	Update
1	(3,0)	up	-1	(2,0)	right	$Q((3,0), \text{up}) \leftarrow 0 + 0.5[-1 + 1.0 \cdot 0 - 0] = -0.5$
2	(2,0)	right	-1	(2,1)	right	$Q((2,0), \text{right}) \leftarrow 0 + 0.5[-1 + 0 - 0] = -0.5$

Why these steps?

• Step 1: We go up to avoid the cliff. The TD target is $-1 + 0 = -1$ (next Q-value is 0 because we're at a new state). Our estimate moves from0 to -0.5.
• Step 2: Continue right along the safe path. Same logic applies.

Key observation: SARSA learns the safer path (going up then right) because it accounts for the $\epsilon$-greedy exploration that might accidentally step into the cliff. Q-learning would learn the optimal path right along the cliff edge, which is dangerous during exploration.

Setup:

• State $S_t = (2, 3)$, action $A_t = \text{right}$, $Q(S_t, A_t) = -15.3$
• Wind pushes up 1 cell → $S_{t+1} = (1, 4)$
• Reward $R_{t+1} = -1$
• Policy choses $A_{t+1} = \text{right}$ at $S_{t+1}$, $Q(S_{t+1}, A_{t+1}) = -12.1$
• $\alpha = 0.1$, $\gamma = 0.9$

Step-by-step update:

1. Compute TD target: $\text{Target} = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) = -1 + 0.9 \times (-12.1) = -1 + (-10.89) = -11.89$

   Why this value? We got a reward of -1, and the next state-action pair has value -12.1, discounted by 0.9.

2. Compute TD error: $\delta_t = -11.89 - (-15.3) = 3.41$

   Why positive? Our current estimate (-15.3) was too pessimistic. The actual outcome was better.

3. Update Q-value: $Q(S_t, A_t) \leftarrow -15.3 + 0.1 \times 3.41 = -15.3 + 0.341 = -14.959$

   Why small change? Learning rate of 0.1 means we only move10% toward the new estimate, maintaining stability.

Setup:

• Action "forward" succeds 80% of time, slips left/right 10% each
• $S_t = s_1$, $A_t = \text{forward}$, $Q(s_1, \text{forward}) = 5.0$
• Agent slips right → $S_{t+1} = s_2$ (instead of intended $s_3$)
• $R_{t+1} = -2$ (penalty for slipping), $\alpha = 0.2$, $\gamma = 0.95$
• At $s_2$, policy chooses $A_{t+1} = \text{left}$, $Q(s_2, \text{left}) = 3.5$

Update: $\text{Target} = -2 + 0.95 \times 3.5 = -2 + 3.325 = 1.325$ $\delta_t = 1.325 - 5.0 = -3.675$ $Q(s_1, \text{forward}) \leftarrow 5.0 + 0.2 \times (-3.675) = 5.0 - 0.735 = 4.265$

Why this teaches safety: Even though "forward" is usually good, SARSA learns that sometimes it leads to bad outcomes. Over many episodes, $Q(s_1, \text{forward})$ will reflect the average outcome including slip probabilities, making the policy more cautious.

On-Policy vs Off-Policy: The Key Distinction

Property	SARSA (On-Policy)	Q-Learning (Off-Policy)
Update uses	$Q(S_{t+1}, A_{t+1})$ — action actually taken	$\max_a Q(S_{t+1}, a)$ — best possible action
Learns	Value of the behavior policy (e.g., $\epsilon$-greedy)	Value of the optimal policy
Convergence	To $Q^{\epsilon\text{-greedy}}$	To $Q^*$
Safety	Conservative during exploration	Optimistic, riskier

WHY this matters in practice:

• Robot navigation: SARSA won't learn to drive near cliffs because it knows it might explore randomly. Q-learning assumes perfect future actions.
• Medical treatment: SARSA accounts for "what if the next action isn't perfect?" — safer for experimentation.

Common Mistakes

Wrong update: $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha[R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)]$

Why this feels right: "Shouldn't we always aim for the best action?"

Steel-man defense: This seems logical because we want to learn optimal behavior eventually, and the max represents the best possible outcome.

Why it's wrong: This is Q-learning, not SARSA! SARSA must use the actual next action $A_{t+1}$ chosen by the policy. Using max makes it off-policy and changes convergence properties. You're lying to the algorithm about what it will actually do.

The fix: Always select $A_{t+1}$ using your policy before updating, and use that specific action's Q-value in the update.

Wrong algorithm:

Take action A, observe R, S'
Q(S, A) ← Q(S, A) + α[R + γQ(S', A') - Q(S, A)]  // A' not chosen yet!
Choose A' from S' using ε-greedy

Why this feels right: "We need to update first, then decide what to do next."

Steel-man defense: It seems like we should update our knowledge before making decisions, like learning from experience then acting.

Why it's wrong: The update formula requires $Q(S_{t+1}, A_{t+1})$, but $A_{t+1}$ doesn't exist yet! You'll either use an undefined variable or accidentally use the old value of $A$, breaking the algorithm.

The fix: Choose $A'$ before the update. The action must be selected from $S'$ before you can query $Q(S', A')$.

Wrong expectation: "SARSA will converge to $Q^*$, the optimal action-values."

Why this feels right: "AllRL algorithms should learn the best possible policy."

Steel-man defense: We're doing reinforcement learning to find optimal behavior, so every algorithm should converge to optimality.

Why it's wrong: SARSA learns $Q^\pi$ for the policy you're using. If you use $\epsilon$-greedy with $\epsilon = 0.1$, SARSA learns "what's the value of each action if I keep being $\epsilon$-greedy?" Not "what's the value if I act optimally?"

The fix:

• To learn $Q^*$: Use Q-learning (off-policy), or use SARSA with $\epsilon$ decaying to 0.
• To learn safe behavior under exploration: SARSA with fixed $\epsilon$ is exactly what you want.

Intuitive Mental Model

Recall Explain to a 12-year-old

Imagine you're learning to navigate a maze with your eyes closed, and sometimes you spin around randomly before moving.

Q-learning is like a friend who watches you and says "OK, but if you were perfect and never spun randomly, here's what each move is worth."

SARSA is like a friend who says "Given that you DO spin randomly sometimes, here's what each move is actually worth when you're stumbling around like that."

If there's a pit, Q-learning says "the optimal path is right next to the pit!" because it assumes you'll never randomly spin into it. SARSA says "that path is dangerous because you might randomly spin into the pit, so I'll rate it lower."

You want Q-learning when you're just learning in a simulation and can reset. You want SARSA when you're actually in the maze and can't die.

When to Use SARSA

Choose SARSA when:

1. Safety matters: Real-world systems (robots, medical, finance) where exploration mistakes have consequences
2. Learning online: The agent learns while interacting with the actual environment
3. Stochastic policy: You want to maintain exploration throughout (not decay $\epsilon$ to 0)
4. Policy evaluation: You want to know "how good is my current policy?" not "how good could I be?"

Choose Q-learning when:

1. You want the optimal policy eventually
2. Learning in simulation with resets
3. You can safely explore then switch to gredy execution

Parameter Guidelines

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Chalo isko simple tarike se samajhte hain. Reinforcement learning mein agent ko seekhna hota hai ki kaunse action best hain. Q-learning ek algorithm hai jo hamesha maanke chalta hai ki agent optimal (sabse best) action lega — matlab wo "reckless" hai, thoda over-confident. Lekin real life mein agent exploration karta hai, matlab kabhi-kabhi random action bhi leta hai (isko epsilon-greedy policy kehte hain). Yahin par SARSA kaam aata hai. SARSA ka full form hai State-Action-Reward-State-Action, aur ye "learn what you actually do" wala approach follow karta hai — matlab jo action agent sach mein lega, uske hisaab se value update karta hai, na ki kaal-panik ki optimal action ke hisaab se.

Ab core intuition ye hai ki SARSA update karte time next action $A_{t+1}$ ko use karta hai jo policy ne actually choose kiya hai, jabki Q-learning $\max_a Q$ use karta hai (yani best possible action maan leta hai). Isliye SARSA ko on-policy algorithm kehte hain — wo usi policy ki value seekhta hai jo wo follow kar raha hai. Formula simple hai: TD error ($\delta_t$) nikaalo, jo batata hai humara current estimate kitna galat hai, aur us error ki taraf apne estimate ko learning rate $\alpha$ se thoda shift kar do. Agar outcome expected se accha nikla toh value badha do, kharab nikla toh ghata do — bas yahi loop chalta rehta hai jab tak agent seekh na le.

Ye baat kyun matter karti hai? Cliff Walking example dekho — agent ko goal tak pohonchna hai lekin beech mein cliff hai jahan girne par -100 ka bada penalty hai. Kyunki SARSA exploration ki reality ko consider karta hai, wo samajhta hai ki "agar main cliff ke paas gaya aur galti se random step le liya toh gir sakta hoon", isliye wo ek safe path seekhta hai jo cliff se door rehta hai. Q-learning risky shortcut seekhega jo theory mein optimal hai par practically dangerous. Isliye jab real-world mein safety important ho aur agent actively explore kar raha ho, SARSA zyada reliable aur practical choice ban jaata hai.