SARSA algorithm: Question bank — AI-ML deep dive

Before the questions, one shared vocabulary reminder so no symbol here is unearned:

Definition Every symbol used below, defined once

$Q (S, A)$ is the action-value function: a table (or estimate) giving the expected total future reward if you are in state $S$ , take action $A$ , and then keep following your policy. Every question below reads or updates entries of this table.
$α$ (learning rate) is a number in $(0, 1]$ that sets how big a step we take toward each new estimate. Near $1$ = trust the newest sample fully; near $0$ = barely move.
$γ$ (discount factor) is a number in $[0, 1)$ that shrinks future rewards: a reward $n$ steps away counts as $γ^{n}$ of its face value. Near $1$ = far-sighted; $0$ = only the immediate reward matters.
$ϵ$ (epsilon, the exploration rate) is the probability that an $ϵ$ -greedy policy picks a random action instead of the current best one; the rest of the time ( $1 - ϵ$ ) it acts greedily.
$δ_{t}$ (TD error) is the surprise signal $δ_{t} = R_{t + 1} + γ Q (S_{t + 1}, A_{t + 1}) - Q (S_{t}, A_{t})$ : the gap between what actually happened (reward plus discounted next value) and what we had predicted. Positive = pleasant surprise, negative = disappointment.

The SARSA update, once and for all, is $Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α δ_{t}$ .

True or false — justify

TF1. SARSA converges to the optimal greedy policy

Q^{*}

regardless of the exploration used.

False. SARSA converges to

Q^{π}

for the behaviour policy it follows (e.g.

ϵ

-greedy). Only if you decay

ϵ \to 0

over time does that behaviour policy become greedy and

Q^{π} \to Q^{*}

TF2. If

γ = 0

, the SARSA update ignores the next state-action entirely.

True. With

γ = 0

the target collapses to

R_{t + 1}

, so

Q (S_{t}, A_{t})

just learns the immediate reward — the term

γ Q (S_{t + 1}, A_{t + 1})

vanishes and

A_{t + 1}

becomes irrelevant to the update.

TF3. A positive TD error

δ_{t}

always means the reward

R_{t + 1}

was positive.

False.

δ_{t} = R_{t + 1} + γ Q (S_{t + 1}, A_{t + 1}) - Q (S_{t}, A_{t})

. Even with

R_{t + 1} = - 1

you can get

δ_{t} > 0

if the discounted next value beats a very pessimistic current estimate — exactly the Windy Gridworld case where

δ_{t} = + 3.41

TF4. SARSA and Q-learning give identical updates when the policy is fully greedy (

ϵ = 0

True. If

ϵ = 0

then

A_{t + 1} = ar g max_{a} Q (S_{t + 1}, a)

, so

Q (S_{t + 1}, A_{t + 1}) = max_{a} Q (S_{t + 1}, a)

and the two update targets coincide.

TF5. Because SARSA is on-policy, it can never learn a value for an action it did not take.

True for that transition. SARSA only updates the taken pair

(S_{t}, A_{t})

using the taken next action

A_{t + 1}

; actions never chosen in a state get no update from that step and keep their initial value until visited.

TF6. Increasing the learning rate

α

makes SARSA both faster and more stable.

False. Larger

α

moves faster but is less stable — each noisy sample yanks the estimate harder. Stability wants small

α

; the trade-off is exactly why

α = 0.1

moves only 10% toward the target.

TF7. Setting

Q (terminal, \cdot) = 0

is just a convenience; any value would do.

False. It must be

0

because there is no future beyond a terminal state — a nonzero terminal value would inject phantom future return into every episode-ending update and bias all upstream Q-values.

Spot the error

SE1. "SARSA update uses

max_{a} Q (S_{t + 1}, a)

so it always aims for the best next move."

That is Q-learning. SARSA uses

Q (S_{t + 1}, A_{t + 1})

with the actual sampled next action; swapping in the max makes it off-policy and changes what it converges to.

SE2. "Take action A, update

Q (S, A)

, then choose A' from S'."

The update needs

Q (S^{'}, A^{'})

, but

A^{'}

hasn't been chosen yet. You must select

A^{'}

before the update, or you'll reference an undefined / stale action.

SE3. "

γ = 1.2

discounts future rewards a little more strongly."

A discount factor must satisfy

0 \leq γ < 1

for the return to converge.

γ > 1

amplifies future rewards and can make Q-values diverge to infinity — it doesn't discount at all.

SE4. "After the update, we set

A \leftarrow A_{t + 1}^{'}

but re-sample a fresh action next loop anyway."

Then you'd throw away the

A^{'}

you already committed to. On-policy SARSA must take the very

A^{'}

it used in the update — re-sampling breaks the ‘learn what you do' guarantee.

SE5. "

Q (S_{t}, A_{t}) \leftarrow α [R_{t + 1} + γ Q (S_{t + 1}, A_{t + 1}) - Q (S_{t}, A_{t})]

The old estimate

Q (S_{t}, A_{t})

dropped off the front. The correct rule adds the scaled error to the current value:

Q \leftarrow Q + α δ_{t}

, not

Q \leftarrow α δ_{t}

SE6. "With a bad slip, SARSA punishes only the slip state

s_{2}

, not the choice

Q (s_{1}, forward)

Wrong. In the Slip world the slip is baked into the transition out of

s_{1}

; the update lands on

Q (s_{1}, forward)

, lowering it so ‘forward' reflects the average including slip risk.

SE7. "Since SARSA is safer, its learned Q-values are always higher (less negative) than Q-learning's near a cliff."

Backwards. SARSA's cliff-edge Q-values are more negative because it folds in the chance of exploring into the cliff; that pessimism is precisely what steers it to the safe path.

The actual action includes the occasional exploratory (possibly bad) move. Averaging those in makes SARSA value states realistically as ‘what happens if I sometimes act imperfectly', so it avoids fragile optimal-but-risky paths.

WHY4. Why do we choose

A

before the episode loop but

A^{'}

inside it?

The very first step needs an action to execute, so

A

is chosen up front; thereafter each iteration produces the next action

A^{'}

needed for the current update, then hands it off as the next step's

A

WHY5. Why can SARSA's update be read as stochastic gradient descent?

We minimise the squared error

(Q^{π} - Q)^{2}

; its gradient points along

δ_{t}

, and stepping by

α δ_{t}

is one noisy gradient step toward the Bellman-consistent value.

WHY6. Why does the sign of

δ_{t}

decide the direction of the Q change, not the sign of the reward?

The update moves

Q

α δ_{t}

. A negative reward with an even-more-negative old estimate gives

δ_{t} > 0

, so

Q

rises — the comparison to expectation drives the direction, not the raw reward.

Edge cases

EC1. What is the SARSA update on the very first step when all Q-values are initialised to

0

The target is

R_{t + 1} + γ \cdot 0 = R_{t + 1}

and

δ_{t} = R_{t + 1}

, so

Q (S_{t}, A_{t}) \leftarrow α R_{t + 1}

— the first real reward is the seed for everything downstream.

EC2. What happens to the update if

S_{t + 1}

is terminal?

Then

Q (S_{t + 1}, \cdot) = 0

by definition, so the target is just

R_{t + 1}

— no next action is sampled and the future term drops, correctly stopping the return at the episode's end.

EC3. If

α = 1

, what does the SARSA update do to the estimate?

It replaces

Q (S_{t}, A_{t})

entirely with the target

R_{t + 1} + γ Q (S_{t + 1}, A_{t + 1})

, discarding all prior learning — full trust in one noisy sample, usually far too jumpy.

EC4. If

α = 0

, what does SARSA learn?

Nothing. The change

α δ_{t} = 0

, so

Q

never moves from its initialisation regardless of experience.

EC5. In a deterministic environment with

ϵ = 0

, does SARSA still differ from Q-learning?

No. Greedy behaviour makes

A_{t + 1}

the argmax action, so the SARSA and Q-learning targets coincide and both converge to the same values.

EC6. What if the policy at

S_{t + 1}

picks an action whose Q-value is currently a bad initial guess?

SARSA uses that (possibly wrong)

Q (S_{t + 1}, A_{t + 1})

anyway — early updates are biased by initialisation, but repeated visits correct it as those next-state values themselves get updated.

EC7. Two different runs with the same start diverge in learned Q-values — is SARSA broken?

Not necessarily.

ϵ

-greedy exploration is stochastic, so different action samples yield different on-policy values; both can be valid

Q^{ϵ -greedy}

estimates for their own realised experience.

Recall Quick self-test

One target, one direction, one guarantee. SARSA's update target uses which next action? ::: The action $A_{t + 1}$ actually chosen by the current policy, not $max_{a} Q (S_{t + 1}, a)$ . SARSA converges to the value of which policy? ::: The behaviour (on-)policy it follows, e.g. $Q^{ϵ -greedy}$ — only $Q^{*}$ if $ϵ \to 0$ .

Question bank — SARSA algorithm

True or false — justify

Spot the error

Why questions

Edge cases