Bootstrap value estimates from partial trajectories — no model, no completed episodes required. Q-Learning and SARSA are TD at heart, and DQN is TD with a neural network.
Learn online, one step at a time — no model, no complete episodes.
In dynamic programming (DP), we update values using the Bellman equation and a known model. In Monte Carlo (MC), we wait until an episode ends, then update using the actual return Gt. Temporal Difference combines both ideas: update at every step using a bootstrapped estimate of the return.
The key insight: we don’t need to wait until the end of an episode. We can use the value estimate of the next state as a proxy for the future return — just like the Bellman equation, but learned online from experience.
The simplest TD algorithm updates the value function after each (s, a, r, s′) transition:
V(s) ← V(s) + α [r + γ V(s′) − V(s)]
The bracketed term is called the TD error δt: it measures how much the current estimate V(s) differs from the bootstrapped target r + γV(s′). The learning rate α controls how fast we move toward the target. When δt = 0, V(s) is already consistent with the observed transition — no update needed.
| Method | Needs model? | Needs full episode? | Bootstraps? |
|---|---|---|---|
| Dynamic Programming | Yes | No | Yes |
| Monte Carlo | No | Yes | No |
| Temporal Difference | No | No | Yes |
TD combines the best of both: it is model-free like MC, and it can learn online (step-by-step) like DP. This makes it practical for continuing tasks with no natural episode boundary.
SARSA updates the action-value function Q(s,a) using the actual next action taken under the current policy π:
Q(s,a) ← Q(s,a) + α [r + γ Q(s′,a′) − Q(s,a)]
The name comes from the 5-tuple (S, A, R, S′, A′) used in the update. SARSA is on-policy: it evaluates the same policy it improves. If you’re using ε-greedy exploration, SARSA accounts for the exploration noise — safer in environments where unsafe exploratory actions have irreversible consequences.
Q-Learning uses the best possible next action instead of the actual one:
Q(s,a) ← Q(s,a) + α [r + γ maxa′ Q(s′,a′) − Q(s,a)]
This is off-policy: the update target is the optimal policy, regardless of which action was actually taken. Q-Learning converges to the optimal Q* under mild conditions (every state-action pair visited infinitely often, decaying α). The interactive demo above uses Q-Learning on a 4×4 grid world.
TD(0) only uses the immediate next state; Monte Carlo uses all future states. TD(λ) interpolates with eligibility traces:
Gλt = (1−λ) Σn=1∞ λn−1 G(n)t
An eligibility trace e(s) records how recently and frequently a state was visited. When a TD error occurs, all states with high eligibility get updated. λ=0 gives TD(0); λ=1 gives Monte Carlo. Intermediate values (e.g. λ=0.9) often learn faster by propagating errors backward through time.
Tabular methods store Q(s,a) as a table — infeasible for large or continuous state spaces. Function approximation replaces the table with a parameterised function Q(s,a;θ) and updates θ by gradient descent on the TD error:
θ ← θ + α δt ∇θ Q(s,a;θ)
This generalises across similar states, enabling RL to scale to high-dimensional inputs. Linear function approximation with tile coding or radial basis features is still competitive in many settings.
Deep Q-Network (DQN) applies Q-Learning with a deep neural network as Q(s,a;θ). Two key tricks make it stable:
DQN achieved superhuman performance on dozens of Atari games using raw pixels as input — the first clear demonstration that TD + neural networks can match human-level play.
Say the answer out loud before you reveal it — recalling it is what makes it stick.
What is the TD error and what does it mean when it equals zero?
What is the difference between SARSA and Q-Learning?
How does TD(λ) relate to both TD(0) and Monte Carlo?
What two tricks does DQN add to Q-Learning to make it stable with neural networks?
TD error: δ=r+γV(s')−V(s). TD(0): V(s)+=αδ. SARSA (on-policy): Q(s,a)+=α[r+γQ(s',a')−Q(s,a)]. Q-Learning (off-policy): Q(s,a)+=α[r+γmax Q(s',·)−Q(s,a)]. DQN adds experience replay + target network.