JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

From Prediction to Control: Sarsa, Q-learning, and Expected Sarsa

Turn value estimation into decision making: learn action-values and improve the policy as you go.

Why control needs action-values

Predicting state values V(s) tells you how good a situation is, but not which action to take next — to pick a better action from V alone you would need a model to look ahead. Model-free control therefore learns the action-value function Q(s, a): the expected return from taking action a in state s and following the policy after. With Q in hand, acting greedily is trivial — pick the action with the highest Q-value.

The overall scheme is generalised policy iteration: alternate between making the value estimate consistent with the current policy (evaluation) and making the policy greedier with respect to the values (improvement). The MC and TD machinery from the last guides supplies the evaluation half; ε-greedy action selection supplies the improvement half.

Control plays out inside the agent–environment loop: the agent acts, the environment returns a reward and next state, and action-values drive the next choice.

Diagram of the reinforcement-learning loop between agent and environment.

Monte Carlo control and the need to explore

Monte Carlo control simply applies MC prediction to Q instead of V: play whole episodes, average the returns following each (state, action) pair, then make the policy greedy. But a purely greedy policy is dangerous — it may never try an action it currently underrates, so it never discovers that the action was actually good. This is the exploration–exploitation dilemma in miniature.

The standard cure is an ε-greedy policy: with probability 1−ε take the greedy action, and with probability ε pick a random action. This guarantees every action keeps being tried, so the Q-estimates stay valid everywhere, while still mostly exploiting what you've learned. ε is usually annealed toward zero as learning progresses.

Sarsa: on-policy TD control

Sarsa is TD control done on-policy. Its name spells out the quintuple driving each update: State, Action, Reward, next State, next Action — (s, a, r, s′, a′). After acting and seeing where you land, you choose the next action a′ from your current ε-greedy policy and bootstrap off Q(s′, a′).

Q(s,a) \leftarrow Q(s,a) + \alpha\left[\, r + \gamma\, Q(s',a') - Q(s,a) \,\right]

The Sarsa update bootstraps off Q(s′,a′) for the action actually taken next, which makes it on-policy.

# Sarsa update (on-policy): a' is the action you will actually take
target = r + gamma * Q[s_next, a_next]
Q[s, a] += alpha * (target - Q[s, a])
Sarsa bootstraps off the action the behaviour policy actually selects next.

Because it learns the value of the policy it is actually following — exploration and all — Sarsa is on-policy. That makes it pleasantly safe: it accounts for the risk of its own exploratory mistakes. In the classic cliff-walking example, Sarsa learns a cautious path that stays away from the edge, precisely because it knows random exploratory steps could send it over.

Q-learning: off-policy TD control

Q-learning makes one small but profound change: instead of bootstrapping off the action it will take, it bootstraps off the best action available at s′ — the max over Q(s′, ·). It learns the value of the greedy (optimal) policy while still behaving with an exploratory ε-greedy policy. That mismatch between the policy being learned and the policy being followed is what makes it off-policy.

Try Q-learning on a gridworld: it bootstraps off the best next action, learning the optimal path even while still exploring.

Interactive Q-learning gridworld widget.

# Q-learning update (off-policy): target uses the greedy action at s'
target = r + gamma * max(Q[s_next, b] for b in actions)
Q[s, a] += alpha * (target - Q[s, a])
Q-learning bootstraps off the best next action, regardless of what it actually does.

On cliff-walking, Q-learning learns the optimal shortest path right along the edge — even though, while still exploring, it occasionally tumbles off and earns lower online returns than cautious Sarsa. As ε is annealed, that optimal policy is what remains. The two algorithms beautifully illustrate the on-policy vs off-policy distinction.

Expected Sarsa: the steadier middle

Expected Sarsa keeps the on-policy spirit but removes a source of noise. Instead of bootstrapping off the single sampled next action a′ (as Sarsa does), it uses the expected value of the next action under the policy: Σ π(b|s′)·Q(s′, b). Averaging out the randomness of which exploratory action got chosen gives lower-variance updates than Sarsa, often letting you use a larger step size.

Q(s,a) \leftarrow Q(s,a) + \alpha\left[\, r + \gamma \sum_{a'} \pi(a' \mid s')\, Q(s',a') - Q(s,a) \,\right]

Expected Sarsa replaces the single sampled next action with the expectation over the policy, cutting the variance of the target.

Q-learning's max gives it real power, but as the next guide shows, that same max quietly introduces a systematic overestimation bias — and off-policy Monte Carlo control needs a correction of its own. Both are the subject of the final guide.