Skip to content
Tutorials Center
My learning

Topics

Lesson 89 of 111 · Reinforcement Learning

Q-Learning, SARSA and Model-Free Methods

Compare Q-learning and SARSA on the cliff-walking gridworld, learn what on-policy and off-policy mean, and see how Monte Carlo and TD learning differ.

In Reinforcement Learning Basics you saw value iteration solve a tiny world whose rules were known. Real agents rarely get the rulebook. They have to learn from experience: try an action, see the reward and the next state, adjust. Algorithms that do this without ever building a model of the environment are called model-free.

This lesson compares the two classic model-free control methods, Q-learning and SARSA, which differ by a single term in one line of code yet behave differently. We put both on the famous cliff-walking gridworld and watch one learn a risky shortcut and the other a safe detour. Then we compare two ways of estimating values from experience, Monte Carlo and temporal-difference (TD) learning. Everything is plain Python and NumPy. If you want the neural-network versions (DQN, policy gradients) go to Neural Networks in Reinforcement Learning, which also builds a first Q-table; this lesson goes a different way and focuses on how the update rule changes what is learned.

Two update rules, one difference

Q-learning Learns about the best next action.
SARSA Learns about the action it really takes.
Cliff walking Shows where they disagree.
1 / 2

The action-value update

Both algorithms keep a table Q(s, a) with one number per state-action pair, and after every step they move the entry a little toward a target:

Q(s, a) ← Q(s, a) + α · (target − Q(s, a))

α is the learning rate. The difference target − Q(s, a) is the TD error: how surprised the agent is. The two methods differ only in the target, using the reward r, the next state s' and the discount γ:

Method Target What it assumes about the future
Q-learning r + γ · max over a' of Q(s', a') The agent will act greedily from s' on
SARSA r + γ · Q(s', a') The agent takes the action a' it actually picks next (hence State, Action, Reward, State, Action)

Both pick actions with an epsilon-greedy policy while learning, so the agent explores. Here lies the difference. Q-learning is off-policy: it learns the value of the greedy policy while behaving differently (with random exploration). SARSA is on-policy: it learns the value of the policy it is really following, exploration mistakes included.

flowchart LR
    S["state s, action a"] --> R["reward r, next state s'"]
    R --> QL["Q-learning target: r + gamma * max Q(s', ·)"]
    R --> SA["SARSA target: r + gamma * Q(s', a')"]
    QL --> U["move Q(s, a) toward the target"]
    SA --> U

The only difference is the term for the next state's value.

The cliff-walking world

The environment is a grid of 4 rows and 12 columns. The agent starts at the bottom-left corner and wants to reach the bottom-right goal. Every step costs a reward of -1, so shorter routes are better. The bottom row between start and goal is a cliff: stepping on it gives -100 and sends the agent back to the start. The shortest path hugs the cliff edge. With random exploration, walking along the edge is dangerous because one random move down is a disaster.

The code below defines the world, both algorithms with a shared training loop, and prints the greedy path each learned. S is the start, G the goal, C a cliff cell, and arrows show the learned best action. We also report the average reward the agent earned while learning, over the last 100 episodes.

Python Q-learning vs SARSA on the cliff

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The results match the textbook story. Q-learning learned the optimal route, 13 steps along the row just above the cliff (the path of > arrows from S up, across and down to G), yet while it was still learning it earned only -49.8 per episode on average, because its exploring moves kept dropping it off the edge. SARSA learned a longer, safer route of 19 steps that keeps away from the cliff and earned a better -28.1 per episode during training. (Arrows in squares the agent rarely visits are not meaningful; only follow the path from S.)

This is the key idea: the learned values depend on the policy used to gather experience. Q-learning estimates the value of an agent that never makes a mistake, so it happily plans the cliff edge; the behaving agent, still exploring, keeps falling in. SARSA's values include the cost of its own exploration, so it keeps a safe distance. If you later turn exploration off (ε = 0), the Q-learning route is the better one, and a decaying ε makes SARSA converge to it too. Which method is "better" depends on whether mistakes during learning are expensive: in a simulator they cost nothing, on a real robot a fall might break it.

A third relative, Expected SARSA, uses the average of Q(s', a') under the current policy as the target. It has lower variance than SARSA and can be used on- or off-policy. Q-learning is the special case where the target policy is greedy.

Why the table does not scale

The Q-table needs one row per state. The cliff world has 48 states; a chess position has more than 10⁴⁰, and a camera image is not even a countable state. For large problems the table is replaced by a function approximator, usually a neural network, which is how Deep Q-Networks work. Stability problems arise (the target moves while you learn it), and the techniques that tame them (replay buffers, target networks) are in the deep learning RL lesson.

Monte Carlo versus temporal-difference learning

So far every update happened after a single step. There are two ways to turn experience into a value estimate for a policy:

  • Monte Carlo (MC): run the whole episode, compute the actual return G from each state onward, and move V(s) toward G. It uses real outcomes only, so it is unbiased, but it must wait for the episode to end and its estimates are noisy, because one return depends on many random steps.
  • Temporal-difference (TD(0)): after one step, move V(s) toward r + γ · V(s'). This bootstraps: it uses its own current estimate of the next state as part of the target. It updates immediately, even in tasks that never end, and its targets are less noisy, but they are biased while V(s') is still wrong.

The classic test is the random walk: five states in a row, A to E, with a terminal square at each end. The walker moves left or right with equal probability and gets reward 1 only if it exits on the right. The true value of a state is the probability of finishing on the right: 1/6, 2/6, 3/6, 4/6, 5/6 for A to E. The experiment runs both methods with several learning rates and measures the root-mean-square error against these true values after 100 episodes, averaged over 100 repetitions.

Python Monte Carlo vs TD(0) on a random walk

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Temporal-difference learning has the lower error at every learning rate. Its best setting here (α = 0.05) reaches an error of 0.036, while Monte Carlo's best (α = 0.02) is 0.085, and Monte Carlo gets worse as α grows because every update chases a noisy full return. TD's targets are less noisy, which usually outweighs the bias from bootstrapping. Learning rate is a genuine tuning knob: too small is slow, too large is noisy.

Which method should you use?

Situation Reasonable choice
Small discrete states, safe to explore Q-learning
Mistakes during learning are costly SARSA (or Expected SARSA)
Episodes are short and rewards come at the end Monte Carlo is simple and unbiased
Long or endless tasks TD methods, which update every step
Huge or continuous states Deep Q-learning or policy gradients, see deep learning RL

Common choices to tune are α (too high is noisy, too low is slow), γ, and the exploration schedule: start with a large ε and decay it as the Q-table improves.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the only difference between the Q-learning and SARSA update targets?

    Q-learning bootstraps from max Q(s', a'), SARSA from Q(s', a') for the action the epsilon-greedy policy actually selected.
  2. 2. In cliff walking with epsilon-greedy exploration, why does SARSA learn the safer, longer path?

    SARSA is on-policy: it learns the value of the policy it follows, including random missteps, so the cliff edge looks expensive.
  3. 3. Which statement about Monte Carlo and TD(0) is correct?

    TD bootstraps from V(s') and can update immediately. Monte Carlo uses the actual return, so it must wait for the episode to finish.
  4. 4. What does 'off-policy' mean?

    Q-learning learns the greedy policy's values while following an exploring policy, which is what makes it off-policy.

Summary

  • Model-free methods learn from experience without knowing the transition rules; Q-learning and SARSA both update Q(s, a) toward a one-step target.
  • Q-learning's target uses the best next action (off-policy); SARSA's uses the next action actually taken (on-policy).
  • On the cliff, Q-learning finds the optimal edge path but earns less reward while learning; SARSA takes a safer detour.
  • TD methods bootstrap and update every step; Monte Carlo waits for the full return, which is unbiased but noisier.
  • Tables only work for small state spaces; large problems use function approximation (deep RL).
  • Tune α, γ and an exploration schedule; decay ε over time.

You have now finished the Reinforcement Learning chapter. Continue to the final hands-on chapter with Project: Churn Prediction, or revisit the neural-network approach in Neural Networks in Reinforcement Learning.