Temporal-Difference Learning and Q-Learning, machine learning lesson

A warehouse robot moves from the dock into an aisle and pays a step cost. It does not know the transition probabilities of the warehouse, so it cannot solve the Bellman equations directly, yet this one observed step already says something about the value of the dock. Temporal-difference learning turns each observed transition into an update of a value table, and Q-learning does the same for action values in order to find good actions. This lesson computes such updates by hand, separates on-policy from off-policy targets, handles transitions into a terminal state correctly and states the conditions under which tabular updates converge. The warehouse and its numbers are constructed for illustration.

Key terms

Temporal-difference learning

Definition Temporal-difference learning estimates values from sampled transitions instead of from a known model. In tabular TD(0) policy evaluation, a fixed policy $\pi$ acts in an MDP whose transition probabilities and rewards need not be known, and the learner keeps a table with one estimate $V(s)$ per state. After each observed transition from $S_t$ to $S_{t+1}$ with reward $R_{t+1}$ , it changes only the entry of $S_t$ ,

\begin{aligned} &V(S_t) \leftarrow V(S_t) + \alpha \bigl[R_{t+1} \\[0.4em] &\quad + \gamma V(S_{t+1}) - V(S_t)\bigr], \end{aligned}

where the step size, or learning rate, satisfies $0 < \alpha \le 1$ , and $V(S_{t+1})$ is taken as $0$ when $S_{t+1}$ is terminal. The quantity $R_{t+1} + \gamma V(S_{t+1})$ is the TD target. For a finite MDP with bounded rewards and $0 \le \gamma < 1$ , the estimates converge to $V^{\pi}$ with probability $1$ if every state is updated infinitely often and the step sizes $\alpha_n(s)$ used at the $n$ th update of each state $s$ satisfy

\begin{gathered} \sum_{n} \alpha_n(s) = \infty, \\[0.4em] \sum_{n} \alpha_n(s)^2 < \infty . \end{gathered}

In plain words TD learning updates after every step instead of waiting for an episode to end. It moves the estimate for the current state part of the way toward a target built from the reward just observed and the current estimate for the next state. Unlike the Bellman updates of a known model, it needs no transition probabilities, because the environment supplies one sampled next state at a time. The step size sets how much of each discrepancy is absorbed. With $\alpha = 1$ the old estimate is replaced by the target, and a smaller $\alpha$ blends old and new evidence. A constant step size such as $\alpha = 0.25$ fails the second condition, so the convergence result does not cover it, and in a random environment the estimates keep fluctuating with each new sample.

Example A constructed warehouse has the states dock and aisle and a terminal state exit. Under the policy being evaluated, the robot moves from the dock to the aisle with reward $-1$ , a modeled step cost. With $\gamma = 0.9$ , $\alpha = 0.25$ and the current estimates $V(\text{dock}) = 2$ and $V(\text{aisle}) = 4$ , the TD target is $-1 + 0.9 \times 4 = 2.6$ , and the update gives

\begin{aligned} &2 + 0.25 \times (2.6 - 2) \\[0.4em] &\quad = 2.15 . \end{aligned}

The estimate for the aisle stays at $4$ , since only the state that was left is updated. The starting estimates are chosen for the arithmetic and are not claimed to be correct values.

TD error

Definition For a value table $V$ and an observed transition, the TD error is

\begin{aligned} \delta_t &= R_{t+1} + \gamma V(S_{t+1}) \\[0.4em] &\quad - V(S_t), \end{aligned}

the TD target minus the current estimate, with $V(S_{t+1}) = 0$ when $S_{t+1}$ is terminal. The TD(0) update is $V(S_t) \leftarrow V(S_t) + \alpha\,\delta_t$ . If $V$ equals the true value function $V^{\pi}$ and the transitions follow $\pi$ , the Bellman expectation equation gives $E[\delta_t \mid S_t = s] = 0$ for every state $s$ . Single TD errors are still generally nonzero, because rewards and next states are random.

In plain words The TD error says how much better or worse a step turned out than the current estimate predicted. A positive error raises the estimate and a negative error lowers it. The sign of the error need not match the sign of the reward, since a negative reward can still give a positive error when the next state’s estimate is high. Small TD errors during training show only that the estimates agree with their own targets. They do not show that the values are correct or that a policy behaves well, which needs an evaluation of its returns on separate episodes.

Example For the transition from the dock, $\delta = 2.6 - 2 = 0.6$ , and the update adds $0.25 \times 0.6 = 0.15$ . The reward was $-1$ , yet the error is positive, because the aisle’s estimate of $4$ outweighs the step cost. If the aisle’s estimate were $2$ instead, the target would be $-1 + 0.9 \times 2 = 0.8$ , the error would be $0.8 - 2 = -1.2$ , and the dock’s estimate would fall to $2 - 0.3 = 1.7$ .

Bootstrapping

Definition An update bootstraps when its target contains current estimates, as the TD target $R_{t+1} + \gamma V(S_{t+1})$ contains $V(S_{t+1})$ . The Monte Carlo alternative waits until the episode ends and uses the observed return $G_t$ , the discounted sum of all remaining rewards, as its target. In an episodic task that follows $\pi$ , the return $G_t$ is an unbiased sample of $V^{\pi}(S_t)$ . The TD target has expected value $V^{\pi}(S_t)$ given $S_t$ when the estimates of the next states equal their true values, and it is generally biased otherwise, but it depends on only one random reward and transition and so usually varies less than $G_t$ .

In plain words Bootstrapping learns a guess from a guess. It lets learning start before an episode ends and works in tasks that never end, but an error in one estimate passes into the targets of others, and every change to the table changes later targets. When bootstrapping is combined with function approximation and off-policy data, the updates can even diverge, so guarantees proved for tables do not carry over automatically.

Example Suppose the episode continues from the aisle into the exit with reward $5$ . The Monte Carlo target for the dock is the observed return $-1 + 0.9 \times 5 = 3.5$ , available only after the episode has ended, and it would move the dock’s estimate from $2$ to $2 + 0.25 \times 1.5 = 2.375$ . The TD target $2.6$ was available right after the first step, because it used the aisle’s estimate $4$ in place of the rest of the episode.

Q-learning

Definition Q-learning keeps a table of action-value estimates $Q(s, a)$ . In state $S_t$ it chooses $A_t$ with a behavior policy, often epsilon-greedy with respect to $Q$ , observes $R_{t+1}$ and $S_{t+1}$ , and forms the target

\begin{aligned} y_t &= R_{t+1} \\[0.4em] &\quad + \gamma \max_{a'} Q(S_{t+1}, a'), \end{aligned}

with $y_t = R_{t+1}$ when $S_{t+1}$ is terminal. It then changes only the entry of the pair it used,

\begin{aligned} &Q(S_t, A_t) \leftarrow Q(S_t, A_t) \\[0.4em] &\quad + \alpha \bigl[ y_t - Q(S_t, A_t) \bigr]. \end{aligned}

The target is a sampled form of the Bellman optimality equation for the optimal action values $Q^*$ . For a finite MDP with bounded rewards and $0 \le \gamma < 1$ , the table converges to $Q^*$ with probability $1$ if every state-action pair is updated infinitely often and, for each pair, the step sizes lie in $[0, 1)$ and satisfy the two sum conditions of TD learning, for example $\alpha = 1/(n + 1)$ at the $n$ th update of the pair. A policy that is greedy with respect to $Q^*$ is then optimal.

In plain words Q-learning aims each update at the value of acting as well as possible from the next state on, whatever the behavior policy actually does next. That is why it can learn optimal action values while it explores. Exploration is still necessary, because an action that is never taken never has its entry updated, and its estimate stays wherever it started. The theorem needs all of its conditions. A constant step size such as $0.25$ fails the second sum condition, and when a neural network replaces the table, as in deep Q-learning, the tabular guarantee does not apply and training can be unstable.

Example At the dock the robot takes the action right, pays $-1$ and reaches the aisle, whose actions forward and back have estimates $4$ and $1$ . With $Q(\text{dock}, \text{right}) = 2$ , $\gamma = 0.9$ and $\alpha = 0.25$ , the target is $-1 + 0.9 \times 4 = 2.6$ , and the entry becomes

2 + 0.25 \times 0.6 = 2.15 .

This matches the state-value example only because the numbers were chosen alike. The two updates estimate different things, the value of a state under a fixed policy and the value of an action followed by optimal behavior. Every other entry of the table, such as the dock’s other action, stays as it was.

On-policy and off-policy learning

Definition The behavior policy is the policy that chooses the actions and so generates the data. The target policy is the policy whose values are being learned. A method is on-policy when the two are the same, so that it learns the values of the policy that is acting, exploration included, and off-policy when they differ. SARSA, named after the sequence $S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}$ , is the on-policy counterpart of Q-learning. Its target uses the next action $A_{t+1}$ actually chosen by the behavior policy,

\begin{aligned} y_t &= R_{t+1} \\[0.4em] &\quad + \gamma Q(S_{t+1}, A_{t+1}), \end{aligned}

again with $y_t = R_{t+1}$ when $S_{t+1}$ is terminal, and the same update of $Q(S_t, A_t)$ . Q-learning uses the maximum over next actions instead, so it learns about the greedy policy while behaving differently, which makes it off-policy.

In plain words The two methods differ in one place, the continuation term of the target. A sampled next action makes the target follow the exploring policy, so the values SARSA learns include the cost of the exploration it actually does. A maximum makes the target follow the best estimated action, whatever is done next. An off-policy method can also learn from transitions recorded under other policies, including older versions of its own, provided the records are real transitions of the same task and include the actions the target policy would take.

Example Take the same transition from the dock, with $Q(\text{dock}, \text{right}) = 2$ , reward $-1$ , $\gamma = 0.9$ and $\alpha = 0.25$ , and suppose the exploring behavior policy next chooses back, whose estimate is $1$ . The SARSA target is $-1 + 0.9 \times 1 = -0.1$ , so the entry becomes

\begin{aligned} &2 + 0.25 \times (-0.1 - 2) \\[0.4em] &\quad = 1.475 . \end{aligned}

Q-learning uses the maximum $4$ instead and moves the same entry to $2.15$ . One observed transition gives two different updates, because the two targets answer different questions.

Terminal state

Definition In an episodic task, a terminal state ends the episode. No actions are taken in it and no rewards follow it, so its value is defined as $0$ , both $V(\text{terminal}) = 0$ and $Q(\text{terminal}, a) = 0$ , and the target of a transition into a terminal state is the reward $R_{t+1}$ alone. The reward of that final transition still counts. A time limit that stops recording while the process would go on is a truncation, not a terminal state, and there the target keeps the discounted estimate for the next state.

In plain words Two different mistakes happen at the end of an episode. Bootstrapping past the end adds a continuation value that does not exist, for example a leftover number in the terminal row of a table. Dropping the final reward loses the one payoff that the last transition really had. Treating a time limit as a true ending makes the states near the limit look as if nothing could follow them, which biases their values.

Example From the aisle the robot moves forward into the exit with reward $5$ , and $Q(\text{aisle}, \text{forward}) = 4$ with $\alpha = 0.25$ . The target is $5$ , the TD error is $1$ , and the new estimate is $4 + 0.25 \times 1 = 4.25$ . If the exit row of the table held a leftover value of $3$ and the update used it, the target would become $5 + 0.9 \times 3 = 7.7$ and the estimate $4.925$ , which is too high. Dropping the reward instead would give the target $0$ and the estimate $3$ . The function below checks the terminal flag before it takes any maximum, and it reproduces the Q-learning update at the dock and this terminal update.

def q_update(Q, s, a, r, s_next, terminal, alpha, gamma):
    """One tabular Q-learning update of the entry (s, a)."""
    if terminal:
        target = r                       # nothing follows a terminal state
    else:
        if not Q[s_next]:
            raise ValueError("a nonterminal state needs at least one action")
        target = r + gamma * max(Q[s_next].values())
    Q[s][a] += alpha * (target - Q[s][a])

Q = {"dock": {"right": 2.0, "left": 7.0},
     "aisle": {"forward": 4.0, "back": 1.0},
     "exit": {"stale": 3.0}}              # leftover entry, never used
q_update(Q, "dock", "right", -1, "aisle", False, alpha=0.25, gamma=0.9)
q_update(Q, "aisle", "forward", 5, "exit", True, alpha=0.25, gamma=0.9)
print(Q["dock"], Q["aisle"])   # {'right': 2.15, 'left': 7.0} {'forward': 4.25, 'back': 1.0}

Check yourself

An entry $Q(s, a) = 3$ is updated with $\alpha = 0.2$ and $\gamma = 0.8$ after a transition with reward $-2$ into a terminal state. The terminal row of the table still holds the value $6$ from its initialization. Find the correct Q-learning update, and the result of a mistaken update that bootstraps from that row.

Show the answer

The next state is terminal, so the target is the reward $-2$ alone. The TD error is $-2 - 3 = -5$ , and the new value is

3 + 0.2 \times (-5) = 2 .

The mistaken update uses the target $-2 + 0.8 \times 6 = 2.8$ , with error $-0.2$ , and gives $3 - 0.04 = 2.96$ . The leftover $6$ is not the value of anything, because no rewards follow a terminal state.

Another entry with $Q(s, a) = 3$ , $\alpha = 0.2$ and $\gamma = 0.8$ sees reward $1$ and a nonterminal next state whose two actions have estimates $2$ and $5$ . The behavior policy then chooses the action with estimate $2$ . Find the Q-learning update and the SARSA update, and say which policy each one learns about.

Show the answer

Q-learning uses the largest next estimate. Its target is $1 + 0.8 \times 5 = 5$ , the error is $2$ , and the new value is $3 + 0.2 \times 2 = 3.4$ .

SARSA uses the next action actually chosen. Its target is $1 + 0.8 \times 2 = 2.6$ , the error is $-0.4$ , and the new value is $3 + 0.2 \times (-0.4) = 2.92$ .

Q-learning learns about the greedy policy, which would take the action with estimate $5$ , while the data come from a policy that explored, so it is off-policy. SARSA learns about the behavior policy itself, exploration included, so it is on-policy. In both cases a continuation term appears because the next state is not terminal, which the terminal flag decides, not the size of the reward.

A robot runs Q-learning with the constant step size $0.25$ and a purely greedy behavior policy, and its training TD errors become small. A colleague cites the tabular convergence theorem to claim that the table now holds the optimal action values. Which conditions of the theorem fail, what would satisfy them, and what else is needed before the learned policy can be trusted?

Show the answer

Two conditions fail. With a constant step size the squares add up to $0.0625 + 0.0625 + \cdots$ , which is infinite, so the square-summability condition fails. A purely greedy policy can stop trying some actions altogether, and their entries are then never updated again, so not every state-action pair is updated infinitely often.

Step sizes such as $1/(n + 1)$ at the $n$ th update of each pair satisfy both sum conditions, and a behavior policy that keeps trying every action in every state, for example epsilon-greedy with $\epsilon > 0$ in a task where every state keeps being visited, supplies the updates. Even then the theorem describes the limit and promises nothing after a fixed number of steps.

Small TD errors show only that the estimates agree with their own bootstrapped targets. Trusting the learned policy needs an evaluation of the greedy policy on separate episodes, with its returns and their spread, together with checks of which actions were actually tried, of terminal handling and of whether the reward measures what matters.

Temporal-Difference Learning and Q-Learning

Key terms

Temporal-difference learning

TD error

Bootstrapping

Q-learning

On-policy and off-policy learning

Terminal state

Check yourself

How this lesson connects

Builds on