Temporal Difference Learning
TD(0), TD(λ), SARSA vs Q-learning, deadly triad, divergence with FA
Consider a stock trading system. After each trade you receive a reward — profit or loss. But the final profit of a multi-leg strategy is not known until all positions close, potentially hours later. You cannot wait for the episode to end before updating your value estimates. You need to learn from partial information, updating as you go. Temporal difference learning does exactly this: update V(s_t) based on the observed reward R_{t+1} and the current estimate V(s_{t+1}), without waiting for the final return.
The TD(0) update is V(s_t) ← V(s_t) + α [R_{t+1} + γ V(s_{t+1}) - V(s_t)]. The term in brackets is the TD error δ_t — the difference between what you predicted and what the next step says you should have predicted. V(s_{t+1}) is a bootstrapped estimate: you are using one estimate to update another. This is the fundamental difference from Monte Carlo, which waits for the full return G_t = R_{t+1} + γR_{t+2} + ... before updating.
The tradeoff is bias versus variance. Monte Carlo is unbiased because it uses actual future rewards, but it has high variance because the full trajectory includes noise from every subsequent step. TD is biased because V(s_{t+1}) is an approximation, but it has lower variance because only one step of noise is introduced per update. TD can update after every step — online learning. Monte Carlo requires complete episodes. For long-horizon tasks where episode lengths are in the hundreds or thousands, Monte Carlo gradient variance is too high to train reliably — TD is not just faster, it is the only practical option.
TD(λ) interpolates between the two. λ = 0 is pure one-step TD. λ = 1 is Monte Carlo. Values in between accumulate a geometric average of n-step returns via eligibility traces — each state's update is weighted by how recently and frequently it was visited. λ around 0.7–0.9 typically outperforms both extremes.
NOT this: TD is just a faster version of Monte Carlo. The bias-variance distinction is not an implementation detail. In long-horizon tasks — game episodes of 1000+ steps, multi-day trading strategies — the variance of a full Monte Carlo return is enormous, and the gradient signal becomes noise. TD's bias from an imperfect V estimate is a feature, not a bug: it gives you a low-variance signal every step.
Key points
- Use TD(λ) with λ around 0.7–0.9 for most tasks. The λ-return balances the bias of one-step TD against the variance of full Monte Carlo returns. Both extremes are dominated by intermediate values in long-horizon tasks. λ = 0.9 means you are accumulating roughly 10 steps of real rewards before heavily relying on the value estimate.
- A learning rate α that is too large will cause TD updates to diverge — this is the first thing to check when Q-values oscillate or explode. TD convergence requires α to decrease according to the Robbins-Monro conditions: Σ αₜ = ∞ and Σ αₜ² < ∞. In practice, start with α = 0.01 and decay by a factor of 0.99 every epoch. If training is unstable, halve α before changing anything else.
- Plot the TD error over training — it is a direct diagnostic of whether learning is happening. TD error should be initially large and variable, then decrease and stabilize as the value function converges. If it oscillates at a persistently high value, the learning rate is too large or the function approximator is unstable. If it drops to near zero immediately, the critic is not being updated often enough relative to the policy.
TD learning updates value estimates after every step using a bootstrapped target — trading some bias for dramatically lower variance than Monte Carlo, enabling online learning in long-horizon tasks where waiting for full episode returns is impractical.
Recap
- TD updates every step, no full episode needed: $V(s_t) \leftarrow V(s_t) + \alpha[R_{t+1} + \gamma V(s_{t+1}) - V(s_t)]$.
- Bracket = TD error $\delta_t$; $V(s_{t+1})$ is a bootstrapped estimate (one estimate updating another).
- Bias-variance tradeoff: MC unbiased/high variance, TD biased/low variance. Long horizons -> TD is the only option.
- TD(λ) interpolates: λ=0 one-step TD, λ=1 Monte Carlo; use 0.7–0.9.
- SARSA (on-policy, uses $A_{t+1}\sim\pi$) vs Q-learning (off-policy, uses $\max_{a'}$).
- Learning rate too large = divergence: check $\alpha$ first; needs Robbins-Monro ($\sum\alpha=\infty, \sum\alpha^2<\infty$).
- Deadly triad = off-policy + bootstrapping + FA (Baird's counterexample); plot TD error as your diagnostic.
Check your understanding
Q1. SARSA and Q-learning have identical updates except for one term. Which two of the following statements about that difference are correct?
- A) SARSA is on-policy: it bootstraps off Q(s_{t+1}, A_{t+1}) with A_{t+1} ~ π, so it converges to Q^π, the value of the policy actually being followed (including its exploration)
- B) Q-learning is off-policy: it bootstraps off max_{a'} Q(s_{t+1}, a'), converging to Q*, but this max-based target is more prone to the deadly triad when paired with function approximation
- C) SARSA converges to the globally optimal Q* under any behavior policy, including a purely random one, identically to how Q-learning converges regardless of exploration strategy
- D) Q-learning requires explicit importance-sampling correction on every single-step TD update in order to remain unbiased, exactly as SARSA does
Q2. Explain Baird's counterexample intuitively. Why does Q-learning with linear function approximation diverge even in a simple MDP?
- A) The projected Bellman operator TΠ is a γ-contraction only under on-policy state weighting; off-policy weighting makes TΠ a non-contraction, so repeated application diverges; fix with importance sampling or gradient-TD methods (GTD, GTD2)
- B) Baird's counterexample shows divergence purely because Q-learning with linear function approximation always uses a learning rate that is too high for that specific seven-state MDP structure, and the only documented fix is a much smaller, hand-tuned constant step size
- C) Divergence in Baird's counterexample occurs because the reward signal is exactly zero everywhere in the seven-state chain, causing the Q-function to receive no gradient signal at all and drift randomly under floating-point numerical noise accumulated over iterations
- D) The counterexample demonstrates that linear function approximation cannot represent the optimal Q-function accurately in this MDP, so approximation error compounds multiplicatively over successive Bellman backups until the values diverge to infinity
Q3. You are training a Q-learning agent on a game environment and observe that the Q-values grow from ~10 to ~10^6 over 500k steps, with training reward staying flat. Diagnose and fix.
- A) Q-values growing while reward stays flat means the agent is actually learning successfully but the reward function simply has a numerical scaling bug; multiply every observed reward by a fixed constant factor to bring the Q-values back into a visually reasonable range
- B) This is a deadly-triad symptom: off-policy replay + bootstrapping + FA creates a feedback loop where max Q overestimates → inflates the target → inflates Q further; fix in order: target network, Huber/gradient clipping, lower learning rate, then Double DQN
- C) The divergence is caused entirely by having too large a replay buffer; old transitions collected under a much weaker earlier policy corrupt the current training signal by overestimation, so reduce the buffer size to keep only the most recent 10k transitions
- D) Flat reward with growing Q-values indicates the exploration rate ε is set too high, causing the agent to take mostly random actions that generate artificially high Q-estimates for states it has barely visited; reduce ε toward zero immediately to fix this
Try it interactively
ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.
Open ML Systems Lab →