Temporal-Difference Learning: TD(0)

Temporal-difference learning is a method for estimating a value function from experience generated by interacting with an environment, without requiring a model of that environment. Recall that the state-value function under a fixed policy $\pi$ is defined as the expected discounted return from a state:

Monte Carlo Prediction estimates $v_\pi(s)$ by averaging complete sampled returns $G_t$ following visits to $s$. This requires waiting until an episode terminates before any return is known, and the resulting estimates have high variance because a single return depends on every reward and every random transition for the rest of the episode. TD(0) makes one conceptual substitution: instead of using the full return $G_t$, it uses a one-step lookahead estimate called the TD target:

Here $V$ is the current estimate of the value function — the same object being updated. The agent replaces "the true remaining return from $S_{t+1}$ onward" with "my current best guess of it," namely $V(S_{t+1})$. This is called bootstrapping: building an estimate partly from another estimate, a hallmark shared with dynamic programming, foreshadowed further in Bootstrapping in TD Learning. The discrepancy between the TD target and the current value estimate is the TD error:

TD(0) nudges $V(S_t)$ toward the TD target by a step-size $\alpha \in (0, 1]$:

This single line is the entire learning rule. It can be applied after every transition — the agent observes $S_t, R_{t+1}, S_{t+1}$, computes $\delta_t$, and immediately updates $V(S_t)$. No episode needs to finish; TD(0) works identically in continuing tasks with no terminal state, and it works in episodic tasks by simply treating a terminal state's value as fixed at zero.

TD(0) is used for prediction: given a fixed policy $\pi$, estimate $v_\pi$. The agent does not choose actions to optimize reward here — it simply follows $\pi$ and learns to evaluate it. (Choosing actions to improve the policy is control, covered in SARSA: On-Policy TD Control.) The algorithm maintains a table $V(s)$ for every state, typically initialized arbitrarily (often to zero), with any terminal state fixed at $V(\text{terminal}) = 0$. Each episode (or, in a continuing task, each fixed-length chunk of interaction) proceeds by taking an action dictated by $\pi$, observing the reward and next state, and updating immediately. ``` Algorithm: TD(0) Prediction for estimating v_π Input: policy π to be evaluated, step-size α ∈ (0, 1], discount γ ∈ [0, 1] Initialize: V(s) ← arbitrary, for all non-terminal s V(terminal) ← 0 Repeat (for each episode): S ← initial state of episode Repeat (for each step of episode), until S is terminal: A ← action given by π for S Take action A; observe reward R and next state S' δ ← R + γ V(S') - V(S) # TD error V(S) ← V(S) + α δ # TD(0) update S ← S' ``` Two implementation subtleties matter for correctness. First, $V(S')$ must be the value stored before any update happens in that step — the update uses the pre-update estimate as its bootstrap target. Second, terminal states must always evaluate to exactly $0$, since by definition no reward accrues after termination; forgetting this is a common source of silent bugs (see pitfalls below). The diagram below shows the information flow of a single TD(0) update: one real transition supplies the reward $R_{t+1}$, and the stored value of the next state supplies the rest of the target, in contrast to Monte Carlo, which would need the entire rest of the trajectory.

Time complexity. Each TD(0) update touches exactly one table entry, computes one reward, one lookup of $V(S')$, and one arithmetic combination: $O(1)$ per transition. An episode of length $T$ costs $O(T)$ total, and $T$ never needs to be finite — the algorithm applies unchanged to continuing tasks. This is the key practical advantage over Monte Carlo, whose per-episode update also costs $O(T)$ but which cannot produce any update until the episode ends; TD(0) produces $T$ incremental updates spread across the episode's duration, enabling learning in real time and in tasks without a natural end.

Space complexity. A tabular implementation stores $V(s)$ for each state: $O(|\mathcal{S}|)$ space. No model of transition probabilities or rewards is stored, distinguishing TD(0) from dynamic-programming methods that require the full $O(|\mathcal{S}|^2 |\mathcal{A}|)$ transition model.

Correctness — bias/variance tradeoff. The Monte Carlo target $G_t$ is an unbiased estimate of $v_\pi(S_t)$ by definition of $v_\pi$ as an expectation, but it has high variance because it is a function of many random rewards and transitions across an entire trajectory. The TD target $R_{t+1} + \gamma V(S_{t+1})$ has much lower variance — it depends on only one random reward and one random next state — but it is biased whenever $V \neq v_\pi$, since it bootstraps from a possibly-wrong estimate. As $V$ converges toward $v_\pi$ during learning, this bias vanishes. This is the fundamental tradeoff TD(0) makes: it accepts transient bias in exchange for a large variance reduction, which in practice usually yields faster and more stable learning.

Convergence proof sketch (tabular case). Fix a policy $\pi$ generating an ergodic Markov chain over states. Consider TD(0)'s expected update at state $s$:

where $T^\pi$ is the Bellman expectation operator for $\pi$:

The operator $T^\pi$ is a $\gamma$-contraction in the max norm (for $\gamma < 1$): $\|T^\pi V_1 - T^\pi V_2\|_\infty \le \gamma \|V_1 - V_2\|_\infty$, and its unique fixed point is exactly $v_\pi$, i.e. $T^\pi v_\pi = v_\pi$ (the Bellman equation). TD(0)'s expected update thus pushes $V$ toward this fixed point in expectation, sampling a stochastic approximation of the operator $T^\pi$ rather than computing it exactly (which would require the full model, as in policy evaluation via Value functions). Formally, TD(0) is an instance of stochastic approximation for finding the root of $T^\pi V - V = 0$. Under the classical Robbins–Monro step-size conditions —

for every state $s$ (each state visited infinitely often) — standard stochastic approximation theory guarantees $V(s) \to v_\pi(s)$ with probability 1. Intuitively: the sum-to-infinity condition ensures the step size never shrinks so fast that learning stalls before reaching the fixed point, while the square-summable condition ensures the noise from single-sample updates eventually averages out rather than causing permanent oscillation. In practice a small constant $\alpha$ is often used instead, which does not satisfy these conditions exactly and yields convergence to a neighborhood of $v_\pi$ rather than exact convergence — a standard, deliberate tradeoff favoring adaptability in nonstationary settings.

Honest tradeoffs. TD(0) requires $\gamma < 1$ or a properly terminating task for the contraction argument to apply cleanly; with function approximation instead of a table, this convergence guarantee weakens substantially (bootstrapping combined with off-policy sampling and function approximation can even diverge — the so-called "deadly triad," a topic beyond this article). TD(0) also introduces a hyperparameter, $\alpha$, whose tuning affects both speed and final estimation error, whereas tabular Monte Carlo's only real hyperparameter is how counts are used to average returns.

Consider Sutton and Barto's classic random-walk chain: five non-terminal states $A, B, C, D, E$ arranged in a line, with terminal states on both ends. From any state, the agent moves left or right with probability $\tfrac12$ each. Reaching the right terminal yields reward $+1$; reaching the left terminal yields reward $0$; all other rewards are $0$. Under this fully random policy, the true values are known analytically: $v_\pi(A,B,C,D,E) = (1/6, 2/6, 3/6, 4/6, 5/6)$. Initialize all $V(s) = 0.5$ for $s \in \{A,B,C,D,E\}$, with $\alpha = 0.1$, $\gamma = 1$. Suppose one episode produces the trajectory:

Trace the TD(0) updates step by step (all values start at $0.5$):

After this single episode, only $V(E)$ changed, moving from $0.5$ to $0.55$ — a step toward its true value of $5/6 \approx 0.833$. Notice $V(C)$ and $V(D)$ did not change on this episode even though they lay on the path to the reward, because their bootstrap targets exactly matched their current values (both neighbors were still at $0.5$). This is a genuinely instructive contrast with Monte Carlo: a Monte Carlo update on this same episode would immediately push $V(C)$ and $V(D)$ toward the observed return of $1$ as well, since Monte Carlo uses the actual final outcome for every visited state in the episode. TD(0) instead only "notices" the surprise ($\delta_t \ne 0$) exactly at the boundary where the current value table disagrees with reality — namely at $E$, adjacent to the terminal reward. Over many more episodes, this asymmetry corrects itself: as $V(E)$ rises above $0.5$, the next time $D \to E$ occurs, $\delta_t$ at $D$ becomes nonzero too, and the correction propagates backward one state per episode, like a wave. This staged, local propagation of information — updating only where a genuine discrepancy in one-step prediction was observed — is precisely what makes TD(0) computationally cheap and is also why it can take many episodes for information to travel far from a reward source, a limitation partially addressed by multi-step methods in n-Step Bootstrapping Methods.

TD(0) prediction is inseparable from the broader story of temporal-difference learning, developed principally by Richard Sutton in the early 1980s while exploring how animals and machines might learn predictions incrementally from experience, inspired partly by psychological theories of classical conditioning.

TD(0) prediction underlies value estimation in nearly every modern reinforcement learning system, even when the surface algorithm looks quite different. Deep Q-Networks estimate action-values using a TD-style target built from a bootstrapped next-state estimate, extending the same $\delta_t$ signal to neural function approximators. Actor-critic architectures, used across robotics and simulated control, train their critic network with a TD(0)-like loss, often literally $(\delta_t)^2$, to provide a low-variance baseline for policy gradient updates. TD-Gammon demonstrated decades ago that a TD-trained value function alone could reach expert-level performance in backgammon, foreshadowing the value networks later used in AlphaGo and its successors. Beyond games, TD-style bootstrapping appears in recommendation systems that continuously update estimates of long-term user engagement from streaming click data, in industrial process control where feedback must be incorporated online rather than after an artificial "episode" ends, and in financial and operations models that treat ongoing decision processes as continuing tasks with no terminal state. Any system that must learn a long-horizon prediction from an unbounded or very long stream of experience, without waiting for a final outcome, is a natural candidate for TD-style prediction — which is precisely why it remains foundational to control methods such as SARSA: On-Policy TD Control and multi-step generalizations in n-Step Bootstrapping Methods.

Ask the tutor: How does TD(0)'s bias-variance tradeoff change as you move to n-step TD or TD(λ) methods?