Semi-Gradient SARSA in RL

SARSA for continuous states: learn action values with a weight vector, updating from the action you actually take next instead of the best imaginable one.

One semi-gradient SARSA step turns reward 2.0 plus bootstrapped next value into target 2.90, error 0.90, and weights [1.18, 0.86]

Why Does This Exist?

Tabular SARSA keeps one number per state action pair. That works while states are countable, and it breaks the moment a state holds a continuous reading like a velocity or a joint angle. You cannot build a table with infinitely many rows.

You still need action values, not just state values. A state value says this situation is good. An action value says this move in this situation is good. Without a model of the world, only the second one tells you what to do, so continuous control needs a way to learn $\hat{q}(s, a, \mathbf{w})$ directly.

This page covers that way: the on-policy SARSA target with function approximation, the linear update, and one hand-computed step. The prediction-only cousin is semi-gradient TD(0), the tabular origin is Q-learning and SARSA, and the features it leans on are tile coding.

The one idea you need first

A weight vector $\mathbf{w}$ plus a feature vector $\mathbf{x}(s, a)$ gives a predicted value through a dot product: $\hat{q} = \mathbf{w}^T \mathbf{x}$ . The gradient of that prediction with respect to $\mathbf{w}$ is just $\mathbf{x}$ itself. If that feels shaky, read value function approximation first.

Think of It Like This

Grading a restaurant by the dish you actually ordered next

You judge tonight's dinner partly by the meal you already plan to eat tomorrow at the same place. You ate the pasta, it was good, and you know tomorrow you are having the soup, which you expect to be decent. So you raise your rating of tonight.

That is on-policy bootstrapping. You valued tonight using the plan you will actually follow, not the best dish on the menu. If tomorrow you planned the tasting menu instead, tonight's rating would move differently. SARSA works the same way: it updates the current action's value from the next action it truly intends to take.

Where the analogy stops: you can re-taste a dish, while the agent cannot revisit a transition. And your rating is one number, while SARSA moves a whole shared weight vector that shifts values for states it has never visited.

How It Actually Works

At step $t$ the agent sees $S_t$ , takes $A_t$ , gets reward $R_{t+1}$ , lands in $S_{t+1}$ , and picks its next action $A_{t+1}$ from its own policy, often epsilon-greedy. Here $\gamma$ in $[0, 1]$ discounts the future and $\alpha > 0$ is the step size.

The SARSA target treats the next estimate as a fixed number:

$U_t = R_{t+1} + \gamma \hat{q}(S_{t+1}, A_{t+1}, \mathbf{w}_t)$

If $S_{t+1}$ is terminal, the target is just $R_{t+1}$ . The weights then move along the current features by the TD error $\delta_t = U_t - \hat{q}(S_t, A_t, \mathbf{w}_t)$ :

$\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \, \delta_t \, \nabla_{\mathbf{w}} \hat{q}(S_t, A_t, \mathbf{w}_t)$

For a linear model the gradient is the feature vector, so the update is $\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \, \delta_t \, \mathbf{x}(S_t, A_t)$ . It is called semi-gradient because the target's dependence on $\mathbf{w}$ is deliberately ignored, the same shortcut semi-gradient TD(0) takes.

Why on-policy matters

SARSA evaluates the action it will actually take, $A_{t+1}$ . Swap that for a max over actions and you get Q-learning instead: off-policy, more ambitious, and far easier to destabilize with function approximation. The trio of approximation plus bootstrapping plus off-policy data is exactly the deadly triad. SARSA stays on-policy to dodge one leg of it.

Worked example

Two features, $\gamma = 0.9$ , $\alpha = 0.2$ , weights $\mathbf{w} = [1.0, 0.5]$ . Current features $\mathbf{x}(S_t, A_t) = [1.0, 2.0]$ , next features $\mathbf{x}(S_{t+1}, A_{t+1}) = [0.5, 1.0]$ , reward $R_{t+1} = 2.0$ .

Current estimate: $1.0 \times 1.0 + 0.5 \times 2.0 = 2.0000$ . Next estimate: $1.0 \times 0.5 + 0.5 \times 1.0 = 1.0000$ .

Target: $2.0 + 0.9 \times 1.0000 = 2.9000$ . Error: $2.9000 - 2.0000 = 0.9000$ .

Update: $[1.0, 0.5] + 0.2 \times 0.9 \times [1.0, 2.0] = [1.0 + 0.18, 0.5 + 0.36] = [1.1800, 0.8600]$ . Recompute the current pair under the new weights: $1.18 \times 1.0 + 0.86 \times 2.0 = 2.9000$ , exactly the target for this step size and feature norm.

Code

One SARSA step in plain Python, matching the numbers above:

1w = [1.0, 0.5]2x_now = [1.0, 2.0]3x_next = [0.5, 1.0]4reward, gamma, alpha = 2.0, 0.9, 0.25
6q_now = sum(a * b for a, b in zip(w, x_now))7q_next = sum(a * b for a, b in zip(w, x_next))8target = reward + gamma * q_next9delta = target - q_now10w = [a + alpha * delta * b for a, b in zip(w, x_now)]11
12print(f"q_now {q_now:.4f}")    # -> q_now 2.000013print(f"q_next {q_next:.4f}")  # -> q_next 1.000014print(f"target {target:.4f}")  # -> target 2.900015print(f"delta {delta:.4f}")    # -> delta 0.900016print(f"w [{w[0]:.4f}, {w[1]:.4f}]")  # -> w [1.1800, 0.8600]

Watch Out For

Swapping in a max target turns SARSA into unstable Q-learning

Replacing the next action's value with $\max_a \hat{q}(S_{t+1}, a)$ feels like a one-word upgrade. With function approximation it changes the algorithm into Q-learning and invites the divergence SARSA was avoiding. The symptom is weights that grow without bound late in training while tabular runs on the same task stayed calm.

Fix it by keeping the target on-policy while you learn the basics. If you truly need the max, add a target network and read the deadly triad before trusting the run.

Forgetting the terminal-state rule inflates values at episode ends

At a terminal state there is no next estimate, so the target is the reward alone. Code that always adds $\gamma \hat{q}(S_{t+1}, \cdot)$ keeps bootstrapping from a garbage next vector past the goal. The symptom is goal-adjacent values that sit far above any return the agent ever actually collects.

Fix it with an explicit branch: when the episode ends, set the target to $R_{t+1}$ and skip the next features entirely.

The Quick Version

Semi-gradient SARSA learns action values $\hat{q}(s, a, \mathbf{w})$ so continuous states can still pick actions without a world model.
Its target uses the next action actually taken, $R_{t+1} + \gamma \hat{q}(S_{t+1}, A_{t+1})$ , which keeps learning on-policy.
The linear update pushes weights along the current features: $\mathbf{w} + \alpha \, \delta \, \mathbf{x}(S_t, A_t)$ .
In the worked step, reward 2.0 and next value 1.00 give target 2.90, error 0.90, and weights [1.18, 0.86].
Staying on-policy is the point: a max target converts the method into Q-learning and its instability.