Temporal-Difference Learning

6.1 TD prediction

MC target: $G_t$. TD target: $R_{t+1}+\gamma V(S_{t+1})$. TD(0) is the special case of n-step TD (Ch 7) and TD(λ) (Ch 12).

Input: the policy π to be evaluated
Algorithm parameter: step size α ∈ (0, 1]
Initialize V(s), for all s ∈ S⁺, arbitrarily except that V(terminal) = 0
Loop for each episode:
    Initialize S
    Loop for each step of episode:
        A ← action given by π for S
        Take action A, observe R, S'
        V(S) ← V(S) + α [R + γ V(S') − V(S)]
        S ← S'
    until S is terminal

TD and MC updates are sample updates (one sampled successor); DP uses expected updates (full distribution of successors).

Exercise 6.1 — if $V$ changes during the episode ($V_t$ used at time $t$), the identity gains a correction: $G_t - V_t(S_t) = \sum_{k=t}^{T-1}\gamma^{k-t}\delta_k + \sum_{k=t}^{T-1}\gamma^{k-t+1}\big[V_{k+1}(S_{k+1})-V_k(S_{k+1})\big]$. It is small when α is small.

Example 6.1 — driving home

MC (α = 1) moves every prediction toward the actual outcome 43 — but only after arriving home (e.g. at "exiting highway" the error $G_t-V(S_t)=23-15=8$; with α = ½ the estimate rises by 4). TD moves each prediction toward the next prediction, immediately: changes are proportional to the temporal differences between successive predictions. If stuck in a jam 25 minutes in, TD already shifts the 30-minute estimate toward 50.

Exercise 6.2 — after moving to a new building (same highway entrance), the later states' predictions are already accurate. TD updates for the new early states bootstrap from those good estimates and learn quickly; MC must wait for full returns and absorbs all the noise of the trip. The same happens in the original scenario whenever part of the trajectory is already well-learned.

6.2 Advantages of TD prediction methods

Example 6.2 — random walk

A Markov reward process (MRP — an MDP without actions): states A B C D E, start at C, move left/right with prob. ½; terminate at either end; reward +1 only on the right exit. True values: $\tfrac16,\tfrac26,\tfrac36,\tfrac46,\tfrac56$. Initial $V(s)=0.5$.

6.3 Optimality of TD(0) — batch updating

Batch updating: with a finite amount of experience, present it repeatedly; compute the increments for every step but change V only once per pass, by their sum; repeat until convergence. Then:

• Batch TD(0) converges deterministically to a single answer independent of α (if α small enough). Batch constant-α MC also converges — to a different answer.
• Batch MC → sample averages of observed returns: minimises mean-square error on the training set.
• Batch TD → the certainty-equivalence estimate: the value function that would be exactly correct for the maximum-likelihood model of the Markov process (transition probabilities = observed fractions, rewards = observed averages).

Example 6.4 — you are the predictor

Eight episodes: A,0,B,0; B,1 six times; B,0 once. B was visited 8 times and returned 1 six times, so everyone agrees $V(B)=\tfrac34$. But what is $V(A)$?

Exercise 6.7 — off-policy TD(0): $V(S_t)\leftarrow V(S_t)+\alpha\rho_{t:t}\big[R_{t+1}+\gamma V(S_{t+1})-V(S_t)\big]$, with $\rho_{t:t}=\pi(A_t|S_t)/b(A_t|S_t)$.

6.4 Sarsa: on-policy TD control

Follow GPI with TD for evaluation. Learn action values $q_\pi$ by considering transitions from state–action pair to state–action pair:

$Q(\text{terminal},\cdot)=0$. Convergence w.p. 1 to an optimal policy and $q_*$ requires (2.7) step sizes, all pairs visited infinitely often, and the policy converging to greedy in the limit (e.g. ε-greedy with ε = 1/t) — GLIE.

Algorithm parameters: step size α ∈ (0, 1], small ε > 0
Initialize Q(s,a), for all s ∈ S⁺, a ∈ A(s), arbitrarily except that Q(terminal,·) = 0
Loop for each episode:
    Initialize S
    Choose A from S using policy derived from Q (e.g., ε-greedy)
    Loop for each step of episode:
        Take action A, observe R, S'
        Choose A' from S' using policy derived from Q (e.g., ε-greedy)
        Q(S,A) ← Q(S,A) + α [R + γ Q(S',A') − Q(S,A)]
        S ← S'; A ← A'
    until S is terminal

Example 6.5 — windy gridworld

7×10 grid, upward wind per column 0 0 0 1 1 1 2 2 1 0; reward −1 per step; undiscounted. ε-greedy Sarsa (ε = 0.1, α = 0.5, Q = 0). The greedy policy becomes optimal (15 steps); ε-exploration keeps the average around 17. MC cannot easily be used: termination is not guaranteed for all policies — an episode could last forever. Online methods learn during the episode that such policies are bad.

6.5 Q-learning: off-policy TD control

• $Q$ directly approximates $q_*$, independent of the policy being followed — simplifies analysis; early convergence proofs.
• The behaviour policy still matters: it determines which pairs are visited. Requirement for convergence: all pairs continue to be updated (+ step-size conditions) ⇒ $Q\to q_*$ w.p. 1.
• Off-policy (Ex 6.11): target policy is greedy (the max), behaviour is ε-greedy — and no importance sampling is needed because the target bootstraps from $\max_a Q(S',a)$ rather than a sampled next action.

Algorithm parameters: step size α ∈ (0, 1], small ε > 0
Initialize Q(s,a), for all s ∈ S⁺, a ∈ A(s), arbitrarily except that Q(terminal,·) = 0
Loop for each episode:
    Initialize S
    Loop for each step of episode:
        Choose A from S using policy derived from Q (e.g., ε-greedy)
        Take action A, observe R, S'
        Q(S,A) ← Q(S,A) + α [R + γ max_a Q(S',a) − Q(S,A)]
        S ← S'
    until S is terminal

Example 6.6 — cliff walking

4×12 grid; −1 per step; stepping into the cliff gives −100 and teleports to start. ε-greedy, ε = 0.1.

• Q-learning learns the values of the optimal path along the cliff edge — but, because of ε-greedy exploration, occasionally falls off ⇒ worse online performance.
• Sarsa takes its own exploration into account and learns the longer safer path ⇒ better online reward.
• If ε were gradually reduced, both would converge to the optimal policy.

6.6 Expected Sarsa

• Moves deterministically in the direction Sarsa moves in expectation ⇒ eliminates the variance due to random selection of $A_{t+1}$. More computation per step; generally performs better than Sarsa.
• In cliff walking (deterministic transitions; all randomness from the policy) Expected Sarsa can use α = 1 without degrading asymptotic performance; Sarsa only does well long-run at small α (where short-term performance is poor).
• Can be on- or off-policy. If π is greedy while behaviour is exploratory, Expected Sarsa is exactly Q-learning — it subsumes and generalises Q-learning while reliably improving over Sarsa.

Figure 6.3 — sensitivity to α

Interim performance (first 100 episodes) and asymptotic performance on cliff walking, ε = 0.1: Expected Sarsa is best across α and flat up to α = 1; Sarsa's asymptotic performance degrades at large α; Q-learning's online return is lowest (walks the edge).

6.7 Maximization bias and double learning

Control algorithms build target policies with a max (Q-learning's greedy target; ε-greedy in Sarsa). Using the max of noisy estimates as an estimate of the max of true values gives a positive bias: if all $q(s,a)=0$ but $Q(s,a)$ are noisy, $\max_aQ(s,a)>0$. This is maximization bias.

Example 6.7

From A: right → terminal, reward 0. left → B, reward 0; from B many actions all terminate with reward $\sim\mathcal N(-0.1,1)$. So left is a mistake (expected −0.1), yet Q-learning initially strongly favours it and, even asymptotically, takes it ≈5% more than optimal (ε = 0.1, α = 0.1, γ = 1).

Algorithm parameters: step size α ∈ (0, 1], small ε > 0
Initialize Q₁(s,a) and Q₂(s,a), for all s ∈ S⁺, a ∈ A(s), such that Q(terminal,·) = 0
Loop for each episode:
    Initialize S
    Loop for each step of episode:
        Choose A from S using the policy ε-greedy in Q₁ + Q₂
        Take action A, observe R, S'
        With 0.5 probability:
            Q₁(S,A) ← Q₁(S,A) + α (R + γ Q₂(S', argmax_a Q₁(S',a)) − Q₁(S,A))
        else:
            Q₂(S,A) ← Q₂(S,A) + α (R + γ Q₁(S', argmax_a Q₂(S',a)) − Q₂(S,A))
        S ← S'
    until S is terminal

6.8 Games, afterstates, and other special cases

The tic-tac-toe learner of Chapter 1 learned neither $v$ nor $q$ but an afterstate value function: values of positions after the agent's move. Useful when we know the immediate effect of our actions but not the rest of the dynamics (we know the resulting board, not the opponent's reply).

• More efficient: many (position, move) pairs lead to the same afterstate and must have the same value; an action-value function would learn them separately, an afterstate function shares learning instantly.
• Also arises in queuing (assigning/rejecting customers): actions are defined by their known immediate effects.
• Exercise 6.14 — Jack's car rental: the afterstate is the number of cars at each location after the overnight move. Many (state, action) pairs lead to the same morning configuration — e.g. (10 cars, 5 cars) moving 1 car to the second location and (9, 6) moving none both give (9, 6) — so they share one value ⇒ fewer values to learn and faster convergence.

6.9 Summary — comparison of the TD control methods

Hyperparameters in this chapter

Self-test

Chapter quiz — check your understanding

Scored quiz: pick an answer (or type a number) to get instant feedback and an explanation. Questions marked Exam-style give you values to interpret (sweeps, logs, returns, learning curves), the way exam problems do. Your best score is saved in this browser and shown on the home page. "Shuffle & restart" re-orders the questions.