78 - Q-Learning: Learning the Optimal Policy Without Knowing the Model

In the previous articles we computed the optimal policy with value iteration, but under a heavy condition: knowing the environment, that is holding the table P(s′|s,a). In real problems we do not have it: a robot does not know in advance what the floor will do under its wheels, a player does not know the opponent's moves. What we have is experience: we can try an action and see what happens. Q-Learning (Watkins, 1989) is the algorithm that turns the Bellman optimality equation into a rule for learning from experience: after every step the agent corrects its estimate of the value of that action a little, and after enough steps the table converges to the optimal value, without the model ever having been written down. Here you derive the rule step by step, implement it in twenty lines, check it against the exact solution (error 0.000), see the effect of α and ε and discover the difference between learning "the best possible" and learning "the best given that I am still exploring", with the comparison between Q-Learning and SARSA on the cliff.

The vocabulary you need

The Q table is a matrix with one row per state and one column per action: the cell Q[s, a] is the current estimate of q(s, a), the expected return of doing a in s and then behaving optimally. An experience (or transition) is the four-tuple (s, a, r, s′): I was in s, I did a, I received r, I ended up in s′. Temporal-difference learning (TD learning) updates an estimate using the difference between what was expected and what was observed one step later, without waiting for the end of the episode; bootstrapping is the use, in the target, of one's own estimate of the next state instead of a real final outcome. The TD error δ is the difference between target and current estimate (if positive, the outcome went better than expected) and the learning rate α (0 < α ≤ 1) is the part of the error that is corrected at each update.

The ε-greedy policy chooses a random action with probability ε, otherwise the one with the highest Q, as in the 10-armed bandit. Finally the behaviour policy is the one that generates the experience (here ε-greedy) and the target policy is the one whose value you are learning to evaluate. An algorithm is off-policy if it learns a target policy different from the behaviour policy (Q-Learning learns the greedy policy while behaving ε-greedy), on-policy if it evaluates the same one it follows (SARSA).

The analogy: the satnav that corrects itself while driving

Remember the satnav of the Bellman article: it estimated the time left as "time to the next junction plus time left from there". Now imagine the satnav does not know the map: it only has initial estimates (perhaps all equal to zero) and corrects them as it travels. At every junction it asks itself: "I expected 20 minutes to go from here; I took 3 minutes to reach the junction and from there my estimate says 15: total 18. I was wrong by 2 minutes, I correct my estimate a bit towards 18". After thousands of trips the estimates coincide with the true times. It never needed the map: the trips were enough.

From Bellman optimality to the update rule

From the Bellman article we know that the optimal action value satisfies:

q*(s, a) = Σ_{s′} P(s′|s,a) · [ R(s,a,s′) + γ · max_{a′} q*(s′, a′) ]
         = E[ R + γ · max_{a′} q*(S′, a′) | S = s, A = a ]

The second line is the same formula read as an expected value: the value of (s, a) is the average, over all the possible responses of the world, of the quantity R + γ max q*(S′, ·). Now we apply the idea of the bandit article: an average is estimated with the incremental update, Q ← Q + α (sample − Q), where the "sample" is a single outcome of the quantity whose average we want. A single experiment gives us one sample of that quantity: r + γ max_{a′} q*(s′, a′), with r and s′ observed. The problem is that we do not know q*: we replace it with our current estimate Q (bootstrapping). The result is the Q-Learning rule:

Q(s, a) ← Q(s, a) + α · [ r + γ · max_{a′} Q(s′, a′) − Q(s, a) ]
                          └────────── target ──────────┘   └ estimate ┘
                          └───────────── TD error  δ ────────────────┘

If s′ is terminal there is no future and the target is simply r. Three things to note. No P appears: the agent does not need to know with what probability things happen, because the probabilities are embedded in the frequency with which it observes them and in the average that the update builds over time. It is the exact analogue of the bandit update, with the difference that the target contains the estimate of another state. The max, finally, is the difference from SARSA: the target assumes that from s′ onwards the best action is taken, whatever the agent really does.

The drawing walks through the update with illustrative numbers. The agent was in cell 5, moved right, received −1 and ended up in cell 6. It looks at the row of 6 in the table: the best value is −2. The target is therefore −1 + 1·(−2) = −3. Its current estimate of Q(5, right) was −4: the TD error is −3 − (−4) = +1 (it went better than expected). With α = 0.5 the estimate becomes −4 + 0.5·1 = −3.5: it moves halfway towards the target.

The code: twenty lines

To make this article runnable on its own, I reproduce in compact form the 4×4 GridWorld of the MDP article (16 states, terminals in the corners, reward −1 at every step, P[s][a] as a list of tuples). With slip=0.0 every action has a single outcome; with slip > 0 the action veers sideways. The MOVES dictionary will also be used for the cliff.

import numpy as np

# Actions: 0=up, 1=right, 2=down, 3=left
MOVES = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}

class GridWorld:
    """A small MDP written out explicitly: P[s][a] = list of (probability, next_state, reward, done)."""
    def __init__(self, n=4, terminals=(0, 15), step_reward=-1.0, slip=0.0):
        self.n, self.terminals, self.n_states, self.n_actions = n, set(terminals), n * n, 4
        self.P = {s: {a: self._transitions(s, a, step_reward, slip) for a in range(4)} for s in range(self.n_states)}

    def _move(self, s, a):
        r, c = divmod(s, self.n)
        dr, dc = MOVES[a]
        r2, c2 = r + dr, c + dc
        if not (0 <= r2 < self.n and 0 <= c2 < self.n):       # bumping into a wall: stay where you are
            r2, c2 = r, c
        return r2 * self.n + c2

    def _transitions(self, s, a, step_reward, slip):
        if s in self.terminals:                                # terminal states: absorbing, no reward
            return [(1.0, s, 0.0, True)]
        outcomes = {}                                          # next_state -> probability
        for a2, p in [(a, 1.0 - slip), ((a + 1) % 4, slip / 2), ((a - 1) % 4, slip / 2)]:   # intended, or slip to a side
            if p > 0:
                s2 = self._move(s, a2)
                outcomes[s2] = outcomes.get(s2, 0.0) + p
        return [(p, s2, step_reward, s2 in self.terminals) for s2, p in outcomes.items()]

The SampledEnv class serves one purpose only: to hide the model from the agent. It receives the table P and offers only reset() and step(a), like a real environment (the same idea as Gymnasium, with simpler signatures than its own). The agent can only try and observe.

import numpy as np

class SampledEnv:
    """Wraps a model P[s][a] so that the AGENT can only call reset() and step(a): it never sees the probabilities."""
    def __init__(self, model, start_states, rng):
        self.model, self.start_states, self.rng, self.state = model, start_states, rng, None
    def reset(self):
        self.state = int(self.rng.choice(self.start_states))
        return self.state
    def step(self, a):
        outcomes = self.model.P[self.state][a]
        p, s2, r, done = outcomes[self.rng.choice(len(outcomes), p=[o[0] for o in outcomes])]
        self.state = s2
        return s2, r, done

def q_learning(env, n_states, n_actions, episodes, alpha=0.5, gamma=1.0, epsilon=0.1, seed=0, max_steps=500, log_at=()):
    rng = np.random.default_rng(seed)
    Q = np.zeros((n_states, n_actions))
    snapshots = {}
    for ep in range(1, episodes + 1):
        s = env.reset()
        for _ in range(max_steps):
            if rng.random() < epsilon:
                a = int(rng.integers(n_actions))                      # explore
            else:
                best = np.flatnonzero(Q[s] == Q[s].max())             # exploit, breaking ties at random
                a = int(rng.choice(best))
            s2, r, done = env.step(a)
            target = r if done else r + gamma * Q[s2].max()           # no bootstrapping after a terminal step
            Q[s, a] += alpha * (target - Q[s, a])                     # THE Q-learning update
            s = s2
            if done:
                break
        if ep in log_at:
            snapshots[ep] = Q.copy()
    return Q, snapshots

In step the environment draws an outcome according to its probabilities (rng.choice with p=…) and returns it as (next state, reward, end): the agent does not see the probabilities. In q_learning the table Q starts at zero. For each episode: reset, then, at each step, the ε-greedy choice of the action (rng.random() < epsilon → at random; otherwise the action with the maximum Q, with ties broken at random, because at the start they are all zero and always choosing the first would bias the exploration); then env.step(a); then the target target = r if done else r + gamma * Q[s2].max(), where the if done clause handles the terminal case; finally the update Q[s, a] += alpha * (target − Q[s, a]). The log_at parameter saves snapshots of the table at certain episodes, to watch the convergence; max_steps avoids an infinite episode if the agent never reaches the goal.

Check: does it find the exact solution?

We use the 4×4 grid, but this time the agent does not see P. Separately, with value iteration, we compute the exact table q* and measure how far the learned table is from it (maximum error over the non-terminal cells). All the generators have a fixed seed, so two runs give the same output.

# Learn the 4x4 grid WITHOUT being told the model, and compare with the exact answer from value iteration (lesson 76)
model = GridWorld()
env = SampledEnv(model, start_states=[s for s in range(16) if s not in model.terminals], rng=np.random.default_rng(1))

# exact q*, computed with the model (for checking only)
V_star = np.zeros(16)
for _ in range(100):
    for s in range(16):
        V_star[s] = max(sum(p * (r + V_star[s2] * (not d)) for p, s2, r, d in model.P[s][a]) for a in range(4))
Q_star = np.array([[sum(p * (r + V_star[s2] * (not d)) for p, s2, r, d in model.P[s][a]) for a in range(4)] for s in range(16)])

Q, snaps = q_learning(env, 16, 4, episodes=5000, alpha=0.5, gamma=1.0, epsilon=0.2, log_at=(10, 50, 200, 1000, 5000))
nt = [s for s in range(16) if s not in model.terminals]
for ep, Qe in snaps.items():
    err = np.abs(Qe[nt] - Q_star[nt]).max()
    print(f"after {ep:5d} episodes: max |Q - q*| = {err:6.3f}")
print("learned state values max_a Q(s,a):")
print(np.round(Q.max(axis=1).reshape(4, 4), 1))

# Output (two consecutive runs, same output):
# after    10 episodes: max |Q - q*| =  3.500
# after    50 episodes: max |Q - q*| =  2.094
# after   200 episodes: max |Q - q*| =  1.891
# after  1000 episodes: max |Q - q*| =  0.125
# after  5000 episodes: max |Q - q*| =  0.000
# learned state values max_a Q(s,a):
# [[ 0. -1. -2. -3.]
#  [-1. -2. -3. -2.]
#  [-2. -3. -2. -1.]
#  [-3. -2. -1.  0.]]

The code computes V_star and Q_star with value iteration (only for checking: the agent does not see them), then trains with ε = 0.2 and α = 0.5 and compares at five moments. The error falls from 3.5 after 10 episodes to 1.9 after 200, 0.125 after 1000 and 0.000 after 5000: the learned table is q* (to rounding at three decimals). The final print of the maximum values per state is exactly the v* of the Bellman article (−1, −2, −3 …, the distance from the goal). An algorithm that learns only from experience has found again the result of the one that knew the model. Note that the error at 200 episodes (1.891) is almost the one at 50 (2.094): the convergence is not smooth, because it depends on when the agent visits for the first time the pairs far from the goal.

On the theory side, Sutton and Barto report that Q-Learning converges to q* with probability 1 provided all state-action pairs continue to be updated and a variant of the usual stochastic approximation conditions on the steps α holds (the sum of the steps diverges and the sum of their squares converges). The original proof is attributed to Watkins and Dayan (1992), which I did not consult. Two practical consequences: you need exploration forever, or at least until everything has been seen, and a constant α is a compromise, not a guarantee.

What α and ε do (measured)

The function final_error repeats the training with ten seeds and averages the final error: first it varies α with ε = 0.2, then it varies ε with α = 0.5. The listing takes a few minutes in pure Python (about 3 minutes for the whole sequence of this article on this machine, one trial).

# How much do the learning rate alpha and the exploration rate epsilon matter?  (4x4 grid, error against the exact q*, mean of 10 seeds)
def final_error(alpha, epsilon, episodes, seeds=10):
    errs = []
    for seed in range(seeds):
        e = SampledEnv(model, start_states=nt, rng=np.random.default_rng(100 + seed))
        Q, _ = q_learning(e, 16, 4, episodes=episodes, alpha=alpha, epsilon=epsilon, seed=seed)
        errs.append(np.abs(Q[nt] - Q_star[nt]).max())
    return np.mean(errs)

print("error after 1000 episodes, epsilon=0.2:")
for alpha in (0.01, 0.1, 0.5, 1.0):
    print(f"  alpha={alpha:4.2f}  max|Q-q*| = {final_error(alpha, 0.2, 1000):6.3f}")
print("error after 1000 episodes, alpha=0.5:")
for epsilon in (0.0, 0.05, 0.2, 0.5):
    print(f"  epsilon={epsilon:4.2f}  max|Q-q*| = {final_error(0.5, epsilon, 1000):6.3f}")

# Output (two consecutive runs, same output):
# error after 1000 episodes, epsilon=0.2:
#   alpha=0.01  max|Q-q*| =  2.716
#   alpha=0.10  max|Q-q*| =  1.667
#   alpha=0.50  max|Q-q*| =  0.327
#   alpha=1.00  max|Q-q*| =  0.000
# error after 1000 episodes, alpha=0.5:
#   epsilon=0.00  max|Q-q*| =  1.944
#   epsilon=0.05  max|Q-q*| =  1.794
#   epsilon=0.20  max|Q-q*| =  0.327
#   epsilon=0.50  max|Q-q*| =  0.000

On the learning rate: with α = 0.01 the agent has learned little in 1000 episodes (error 2.7), with 0.5 much more (0.33), with α = 1 the error is even zero. This last result is not generalisable: the grid is deterministic, and with α = 1 the old value is overwritten with the new target, which in a world without noise is always the right one. On exploration: with ε = 0 the error stays high (1.94) because the agent does not visit all the state-action pairs, and as ε rises the error falls to zero at 0.5 in 1000 episodes. Here abundant exploration pays because the problem is tiny and there is nothing to lose by exploring; in problems with heavy penalties (the cliff, further below) exploration has a cost.

With noise, α = 1 is a disaster

Let us make the world slippery: 30% of the moves veer sideways. We compute the exact q* of the slippery world and redo the comparison on the learning rate (3000 episodes, 10 seeds).

# The same question when the world is NOISY: a slippery grid (30% of the moves slip sideways), exact q* computed with the model
slippery = GridWorld(slip=0.3)
Vs = np.zeros(16)
for _ in range(500):
    for s in range(16):
        Vs[s] = max(sum(p * (r + Vs[s2] * (not d)) for p, s2, r, d in slippery.P[s][a]) for a in range(4))
Qs = np.array([[sum(p * (r + Vs[s2] * (not d)) for p, s2, r, d in slippery.P[s][a]) for a in range(4)] for s in range(16)])

def error_slippery(alpha, episodes=3000, seeds=10):
    errs = []
    for seed in range(seeds):
        e = SampledEnv(slippery, start_states=nt, rng=np.random.default_rng(200 + seed))
        Q, _ = q_learning(e, 16, 4, episodes=episodes, alpha=alpha, epsilon=0.2, seed=seed)
        errs.append(np.abs(Q[nt] - Qs[nt]).max())
    return np.mean(errs)

for alpha in (0.02, 0.1, 0.3, 1.0):
    print(f"slippery world, alpha={alpha:4.2f}: max|Q-q*| after 3000 episodes = {error_slippery(alpha):6.3f}")

# Output (two consecutive runs, same output):
# slippery world, alpha=0.02: max|Q-q*| after 3000 episodes =  1.769
# slippery world, alpha=0.10: max|Q-q*| after 3000 episodes =  0.597
# slippery world, alpha=0.30: max|Q-q*| after 3000 episodes =  1.158
# slippery world, alpha=1.00: max|Q-q*| after 3000 episodes =  5.338

Now the picture is reversed: α = 1.0 gives the worst error (5.34), because every update throws away the past and chases the last noisy sample: if the last move slipped sideways, the estimate adapts to that outcome. α = 0.02 is too slow (1.77 after 3000 episodes), α = 0.1 is the best of the four (0.60), 0.3 is intermediate (1.16). It is the classic compromise: a small α is an average over many samples (stable estimate but slow to learn), a large α is responsive but noisy. With noise in the environment, α should be small or decrease over time: with α = 1/n you recover the sample mean of the bandit.

The cliff: on-policy against off-policy

So far Q-Learning has learned the optimal policy, but it does so while behaving differently (ε-greedy, hence with random moves). What happens if the random moves are dangerous? This is the Cliff Walking problem of Sutton and Barto (example 6.6 of their text): a 4×12 grid; you start at the bottom left, the goal is at the bottom right; between the two there is a cliff (the row of cells at the bottom): setting foot there costs −100 and sends you back to the start. Every other step costs −1.

We compare two algorithms. Q-Learning uses the target with the max: it evaluates the greedy (best) policy, regardless of what it will really do. SARSA (the name is the five letters of the quintuple S, A, R, S′, A′) uses in the target the action a′ that it will really choose at the next step, random moves included:

Q-Learning:  Q(s,a) ← Q(s,a) + α [ r + γ · max_{a′} Q(s′,a′)  − Q(s,a) ]     (off-policy)
SARSA:       Q(s,a) ← Q(s,a) + α [ r + γ · Q(s′, a′)            − Q(s,a) ]     (on-policy, a′ chosen with ε-greedy)

The difference is one line of code, but it changes what is learned. The listing implements the environment, the two algorithms with the same loop (only the target differs) and measures them with ε = 0.1 kept throughout the training.

class CliffWalking:
    """Sutton & Barto's cliff: a 4x12 grid. Start bottom-left, goal bottom-right, the cells between them are a cliff.
    Every step costs -1; stepping into the cliff costs -100 and sends the agent back to the start (the episode goes on)."""
    ROWS, COLS = 4, 12
    def __init__(self):
        self.start, self.goal = 3 * 12, 3 * 12 + 11
        self.cliff = {3 * 12 + c for c in range(1, 11)}
        self.n_states, self.n_actions = 48, 4
    def reset(self):
        self.s = self.start
        return self.s
    def step(self, a):
        r, c = divmod(self.s, self.COLS)
        dr, dc = MOVES[a]
        r, c = min(max(r + dr, 0), self.ROWS - 1), min(max(c + dc, 0), self.COLS - 1)
        s2 = r * self.COLS + c
        if s2 in self.cliff:
            self.s = self.start
            return self.s, -100.0, False
        self.s = s2
        return s2, -1.0, s2 == self.goal

def run_td(env, episodes, algorithm, alpha=0.5, gamma=1.0, epsilon=0.1, seed=0, max_steps=1000):
    """algorithm = 'q-learning' (off-policy) or 'sarsa' (on-policy). Returns Q and the reward collected in each episode."""
    rng = np.random.default_rng(seed)
    Q = np.zeros((env.n_states, env.n_actions))
    def act(s):
        if rng.random() < epsilon:
            return int(rng.integers(env.n_actions))
        return int(rng.choice(np.flatnonzero(Q[s] == Q[s].max())))
    returns = []
    for ep in range(episodes):
        s = env.reset(); a = act(s); total = 0.0
        for _ in range(max_steps):
            s2, r, done = env.step(a)
            total += r
            a2 = act(s2)                                              # the action it WILL take next (with exploration)
            if algorithm == "q-learning":
                bootstrap = Q[s2].max()                               # value of the BEST next action
            else:
                bootstrap = Q[s2, a2]                                 # value of the action it will ACTUALLY take
            target = r if done else r + gamma * bootstrap
            Q[s, a] += alpha * (target - Q[s, a])
            s, a = s2, a2
            if done:
                break
        returns.append(total)
    return Q, np.array(returns)

def greedy_path(env, Q, max_steps=60):
    s, path = env.reset(), []
    for _ in range(max_steps):
        a = int(np.argmax(Q[s])); path.append("^>v<"[a])
        s, r, done = env.step(a)
        if done or r == -100.0:
            return "".join(path) + ("  (fell off the cliff!)" if r == -100.0 else "")
    return "".join(path)

cliff = CliffWalking()
for algo in ("q-learning", "sarsa"):
    all_returns = np.array([run_td(cliff, 500, algo, seed=s)[1] for s in range(100)])
    Q, _ = run_td(cliff, 500, algo, seed=0)
    print(f"{algo:10s} mean reward per episode while learning (episodes 100-500, 100 runs): {all_returns[:, 100:].mean():7.1f}")
    print(f"           greedy path of the final policy: {greedy_path(CliffWalking(), Q)}")

# Output (two consecutive runs, same output):
# q-learning mean reward per episode while learning (episodes 100-500, 100 runs):   -49.1
#            greedy path of the final policy: ^>>>>>>>>>>>v
# sarsa      mean reward per episode while learning (episodes 100-500, 100 runs):   -28.0
#            greedy path of the final policy: ^^^>>>>>>>>>>v>vv

CliffWalking.step implements the rules: 4×12 grid, the "cliff" cell sends you back to the start with −100 and the episode continues; the goal ends the episode. run_td runs Q-Learning or SARSA: the only difference is the line bootstrap = Q[s2].max() against bootstrap = Q[s2, a2], where a2 is the action the agent will execute (drawn with ε-greedy before updating). greedy_path follows the final policy without exploring and prints the arrows. The numbers are averages over 100 independent runs, over episodes 100 to 500; the path shown is that of seed 0.

Q-Learning learns the shortest path, of 13 steps (^ up, eleven >, v down): hugging the cliff, because according to its target (which assumes it no longer explores) that is the best path. But during training it behaves ε-greedy: every so often, along the edge, a random move makes it fall (−100), and its average gain per episode is −49.1. SARSA learns a longer path, which climbs to the top row and descends only at the end, far from the edge: its target includes the random moves it will really make, and it knows that walking near the cliff with ε = 0.1 is dangerous. Its average gain during training is −28.0, much better.

There is no absolute winner: it depends on what you want. If in the end you will stop exploring (ε = 0) and use the greedy policy, the Q-Learning one is better (13 steps, that is −13, against −17 for the SARSA path, which takes 17). If instead the agent will keep exploring even in production, or if its performance during learning matters (a real robot that falls off the cliff breaks), SARSA is the safer choice. In short: Q-Learning learns "what I would do if I acted at my best", SARSA learns "what pays given that I sometimes get it wrong".

The trade-offs

The table Q requires one cell for every state-action pair: perfect for 16 or 48 states, impossible for an image. It is the limit tackled by the article on Gymnasium, with larger environments, and by the one on Deep Q-Learning. Off-policy reuses experience better (it can learn from data collected by any policy) but can be unstable with approximators; on-policy is more cautious. As for α and ε, constants are simple but leave residual noise and a permanent exploration cost, decreasing ones are more precise but require choosing the decay schedule.

Real pitfalls

1. Forgetting the terminal case. If you bootstrap even after the end of the episode, Q includes "future" that does not exist and the values are inflated.
2. Always choosing the first action among ties. At the start all the Q are 0: argmax always returns the first action and exploration is distorted. Break ties at random (as in the code).
3. Evaluating with ε > 0. When evaluating the learned policy, exploration is switched off (ε = 0), otherwise you measure a noisy policy different from the learned one. The comparison "−49.1 against −28.0" is during learning, a different measure.
4. α = 1 in noisy environments. As seen: error 5.34 against 0.60 with α = 0.1.
5. Confusing on-policy and off-policy. Q-Learning does not evaluate the policy it follows. If the behaviour policy is dangerous, the policy it learns does not take it into account (Cliff Walking).
6. A single seed. The averages on the cliff are over 100 runs; with only one they would be very noisy (falling or not is a matter of luck).

The first two pitfalls are implementation errors that you see by looking at the code; the last three are measurement and interpretation errors that no automatic test flags, because the numbers come out anyway. If you have to check a Q-Learning written by someone else, start from the terminal case and the way ties are resolved, then ask with which ε and over how many seeds the measurements were made.

A worked example by hand: two episodes of Q-Learning on a three-state chain

A corridor of three cells: s0 (start), s1 and the goal G (terminal). Actions: right (R) and left (L). Every step costs −1; γ = 1, α = 0.5; the whole table starts at 0.

Episode 1. From s0 we do R and arrive in s1 with reward −1. Target: −1 + max Q(s1, ·) = −1 + 0 = −1. Update: Q(s0, R) = 0 + 0.5·(−1 − 0) = −0.5. From s1 we do R and arrive in G (terminal) with reward −1. Target: −1 (no future). Q(s1, R) = 0 + 0.5·(−1 − 0) = −0.5.

Episode 2. From s0 again R towards s1 (reward −1). Now the row of s1 is [Q(L) = 0, Q(R) = −0.5], so max = 0. Target: −1 + 0 = −1. Q(s0, R) = −0.5 + 0.5·(−1 + 0.5) = −0.75. In s1, this time we explore (ε) and do L, returning to s0 with reward −1: target −1 + max Q(s0, ·) = −1 + max(Q(L) = 0, Q(R) = −0.75) = −1. Q(s1, L) = 0 + 0.5·(−1 − 0) = −0.5.

Let us stop and look at what happened. The values of the actions that were tried have fallen below zero (−0.75, −0.5, −0.5) because all the rewards are negative; the untried actions (Q(s0, L)) stay at 0, which looks better than any tried action: the agent is "optimistic" towards what it does not know, and this pushes it to explore. The target of Q(s0, R) in episode 2 uses the value 0 of an action never tried in s1: bootstrapping uses the estimates as they are, even immature ones, and that is why many episodes are needed for the information to propagate (the true value of Q(s0, R) is −2: two steps to pay). The order of the updates matters, finally: updating from the goal to the start propagates the information in a single pass.

Exercises with solutions

1. Q(s, a) = 2, r = 1, γ = 0.9, max Q(s′, ·) = 4, α = 0.5. What is the new Q(s, a)?
   Solution: target 1 + 0.9·4 = 4.6; error 4.6 − 2 = 2.6; new 2 + 0.5·2.6 = 3.3.
2. What is the difference, in the update, between Q-Learning and SARSA?
   Solution: Q-Learning uses the value of the best action in s′ (max); SARSA uses the value of the action a′ that it will really choose (including any random move).
3. Why does the Q table not require knowing P?
   Solution: because the transition probabilities are embedded in the frequency with which the various outcomes occur: the incremental update builds over time the weighted average that in the Bellman equation was computed with P.
4. The agent has ε = 0 and all the Q at zero at the start, with negative rewards. What behaviour do you expect?
   Solution: the tried actions become negative and the never-tried ones stay at zero (they look better): for a while the agent tries all the actions, in a sort of involuntary "optimistic" exploration; but without explicit exploration it can still get stuck on a sub-optimal choice.

The first exercise is update arithmetic, the second and the third fix the two ideas that separate Q-Learning from dynamic programming (the max and the absence of P). The fourth is the most useful in practice, because it connects the initialisation of the table to the exploratory behaviour.

Frequently asked questions

Why do we say Q-Learning "converges" if the values oscillate?

With constant α the estimates oscillate around the true value, like the moving average of a noisy signal. Exact convergence requires a decreasing α; in practice a small oscillation is accepted.

Does Q-Learning work without an ε-greedy policy?

Any policy that visits all the state-action pairs will do, because the algorithm is off-policy: it can learn from data collected in a different way (by another agent, by an expert, from a log). This flexibility is its strength.

And if the state space is enormous?

The table does not hold and you move to approximation with neural networks, as in Deep Q-Learning, with new stability problems.

Why α = 0.5 in the examples and not 0.01?

To make the updates visible with few steps. In real problems, and in particular with noise, values such as 0.01-0.1 are more typical; the table of measurements above shows why (0.10 was the best in the slippery world).

How do you choose γ for Q-Learning?

As for Bellman: it is part of the problem, as the article on delayed rewards shows. With short, finite episodes you can also use 1, as here.

Can you learn Q directly from data already collected, without interacting?

It is offline reinforcement learning: possible, but delicate, because the agent may overestimate actions never seen in the data. We did not cover it and I measured nothing about it here.

What you can do now

You can write Q-Learning, Q(s,a) ← Q(s,a) + α [ r + γ max Q(s′,·) − Q(s,a) ], and say what the TD error and bootstrapping are and why no transition probability appears. On the grid you saw it find q* again with error 0.000 after 5000 episodes without seeing P. You know that with noise α = 1 is disastrous (5.34 against 0.60 with α = 0.1), and you can choose between Q-Learning and SARSA: on the cliff the first learns the shortest path but pays for it during training (−49.1), the second a more prudent path (−28.0). The limit remains the table: in the next article we use the Gymnasium library for larger environments (Taxi and FrozenLake), with serious evaluation protocols.