Q-Learning and SARSA: Model-Free Control

We now combine temporal-difference learning with policy improvement to solve the control problem: learning to act optimally without a model. Two algorithms define the field — SARSA (on-policy) and Q-learning (off-policy). Q-learning, introduced by Chris Watkins in 1989, is arguably the most famous RL algorithm and the foundation of deep Q-networks.

Learning action values with TD#

For control we estimate $Q(s, a)$, because choosing actions from $Q$ requires no model: $\pi(s) = \arg\max_aQ(s, a)$. Exploration comes from an ε-greedy behaviour policy.

SARSA: on-policy TD control#

After experiencing $S_t, A_t, R_{t+1}, S_{t+1}$ and choosing the next action $A_{t+1}$ with the current policy, update:

The name comes from the quintuple $(S, A, R, S', A')$. SARSA learns the value of the policy it actually follows, including its exploratory actions.

Q-learning: off-policy TD control#

The target uses the best next action, regardless of what the agent will actually do. Q-learning therefore learns $Q^*$ — the value of the optimal (greedy) policy — while behaving exploratorily. It is a sample-based version of value iteration. Under tabular representations, sufficient exploration of all state–action pairs and suitably decaying step sizes, Q-learning converges to $Q^*$ with probability 1 (Watkins & Dayan, 1992).

Cliff walking: seeing the difference#

In Sutton and Barto's cliff-walking gridworld, the agent must travel from start to goal along the edge of a cliff. Each step costs −1; stepping into the cliff costs −100 and sends the agent back to start.

import numpy as np
import gymnasium as gym

def train(algo, episodes=500, alpha=0.5, gamma=1.0, eps=0.1, seed=0):
    env = gym.make("CliffWalking-v1")
    rng = np.random.default_rng(seed)
    Q = np.zeros((env.observation_space.n, env.action_space.n))
    choose = lambda s: rng.integers(4) if rng.random() < eps else int(np.argmax(Q[s]))
    returns = []
    for ep in range(episodes):
        s, _ = env.reset(seed=seed + ep); a = choose(s); total, done = 0, False
        while not done:
            s2, r, term, trunc, _ = env.step(a); total += r; done = term or trunc
            a2 = choose(s2)
            if algo == "sarsa":
                target = r + (0 if term else gamma * Q[s2, a2])
            else:                                              # q-learning
                target = r + (0 if term else gamma * np.max(Q[s2]))
            Q[s, a] += alpha * (target - Q[s, a])
            s, a = s2, a2
        returns.append(total)
    return Q, np.mean(returns[-100:])

for algo in ["sarsa", "q-learning"]:
    Q, avg = train(algo)
    print(f"{algo:<10} average return (last 100 episodes, with exploration): {avg:.1f}")

(Older Gymnasium versions name the environment CliffWalking-v0.)

The result is a famous lesson:

• Q-learning learns the optimal path, right along the cliff edge — but because it explores with ε-greedy, it occasionally falls off, so its online return during training is worse.
• SARSA accounts for its own exploration and learns a safer path further from the edge, achieving better online returns.

If ε decays to zero, both converge to the optimal path. The difference matters whenever the agent must act safely while learning — a robot exploring near a staircase, a system learning in production.

Variants#

• Expected SARSA: use the expected value under the policy, $\sum_{a}\pi(a \mid S_{t+1})Q(S_{t+1}, a)$, instead of a sampled $A_{t+1}$ — lower variance, generally better than SARSA, and it includes Q-learning as a special case (greedy target policy).
• Double Q-learning (van Hasselt, 2010): the max operator causes maximisation bias — with noisy estimates, $\max_a Q(s, a)$ systematically overestimates. Keep two estimators $Q_A$, $Q_B$; select the action with one and evaluate it with the other:

• n-step and λ versions (SARSA(λ), Watkins's Q(λ)) speed up credit assignment.

On-policy vs off-policy summary#

Off-policy learning's ability to learn from any data — replayed experience, demonstrations, logs — is what made Q-learning the basis for DQN.

Limits of tabular methods#

A table with one entry per state–action pair is impossible for large or continuous state spaces (an Atari screen has more possible states than can ever be enumerated). The next lectures replace the table with a function approximator — ultimately a deep neural network.