Value-Based Methods

Imagine predicting tomorrow's weather. One approach: wait until tomorrow, see what happens, then adjust your model. Another approach: make a prediction for tomorrow, then immediately after making another prediction for the moment you step outside, compare the two predictions. If they disagree, learn from the discrepancy now, without waiting for the final outcome.

This is the essence of Temporal Difference (TD) Learning: learning from the difference between successive predictions, rather than waiting for final outcomes. It's a profound idea that bridges the immediate feedback of supervised learning with the delayed rewards of reinforcement learning.

TD learning combines the best of two worlds:

• From Monte Carlo: Learning directly from experience without a model
• From Dynamic Programming: Updating estimates based on other estimates (bootstrapping)

The result is an algorithm family that learns faster than Monte Carlo (updates every step, not episode end) and requires no model like DP. TD methods are the foundation of modern RL success stories, from game playing to robotics.

At its heart, TD learning is about improving predictions using other predictions. Let's build intuition before formalism.

The Prediction Problem

Suppose you predict that state $s$ has value $V(s) = 10$ (expected future reward). From $s$, you take action $a$, receive reward $r = 2$, and transition to $s'$ where your current estimate is $V(s') = 9$.

Question: Was your prediction $V(s) = 10$ accurate?

TD's answer: Compare it to what you now believe: $$\text{New estimate for } V(s) = r + \gamma V(s') = 2 + 0.99 \times 9 = 10.91$$

You predicted 10, but your more informed estimate says 10.91. This discrepancy—the TD error—tells you to increase $V(s)$.

Contrast with Alternatives

Monte Carlo: Wait until episode ends, compute actual return $G_t = r_1 + \gamma r_2 + \gamma^2 r_3 + \ldots$, then update $V(s_t) \to G_t$.

• Pro: Unbiased—uses actual returns
• Con: High variance—accumulates all randomness; must wait for episode end

Dynamic Programming: Compute $V(s) = \sum_{a} \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s') \right]$

• Pro: Uses full knowledge of transitions, no sampling variance
• Con: Requires model $P(s'|s,a)$—usually unavailable

Temporal Difference: Update $V(s_t) \to r_{t+1} + \gamma V(s_{t+1})$ after each step.

• Pro: Low variance (one random reward), no model needed
• Con: Biased—uses estimate $V(s_{t+1})$ instead of true value

Before learning optimal behavior (control), we study prediction: estimating $V^\pi$ for a fixed policy $\pi$. This is the purest form of TD learning.

The TD(0) Update

The simplest TD method, TD(0), updates after each step:

$$V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$$

Components:

• $V(S_t)$: Current estimate for the visited state
• $R_{t+1} + \gamma V(S_{t+1})$: TD target (better estimate)
• $R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$: TD error $\delta_t$
• $\alpha$: Learning rate (step size)

The update moves $V(S_t)$ toward the TD target by a fraction $\alpha$.

The Certainty Equivalence Principle

TD(0) can be viewed through the lens of certainty equivalence: it behaves as if the estimated model were the true model.

Given experience $(s_t, r_{t+1}, s_{t+1})$, TD(0) updates as if:

• $P(s_{t+1} | s_t, a_t) = 1$ (the observed transition is certain)
• $R(s_t, a_t) = r_{t+1}$ (the observed reward is the true reward)

Over many updates, these "certain" estimates average out to the true expectations. This is why TD converges to $V^\pi$ despite treating single samples as if they were certain.

The TD error $\delta_t$ is the heart of TD learning:

$$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$$

This quantity has remarkable properties that explain why TD works and connect to neuroscience.

The TD Error as Prediction Error

$\delta_t$ measures the discrepancy between:

• What you predicted: $V(S_t)$
• What you now predict based on new information: $R_{t+1} + \gamma V(S_{t+1})$

If $\delta_t > 0$: Things were better than expected (increase $V(S_t)$) If $\delta_t < 0$: Things were worse than expected (decrease $V(S_t)$) If $\delta_t = 0$: Prediction was perfect (no change needed)

Key Property: TD Errors Sum to MC Returns

A beautiful result: the sum of TD errors along a trajectory equals the Monte Carlo return minus the initial value estimate:

$$\sum_{k=t}^{T-1} \gamma^{k-t} \delta_k = G_t - V(S_t)$$

Proof: $$ \begin{aligned} \sum_{k=t}^{T-1} \gamma^{k-t} \delta_k &= \sum_{k=t}^{T-1} \gamma^{k-t} [R_{k+1} + \gamma V(S_{k+1}) - V(S_k)] \ &= -V(S_t) + \sum_{k=t}^{T-1} \gamma^{k-t} R_{k+1} + \sum_{k=t}^{T-1} \gamma^{k-t+1} V(S_{k+1}) - \sum_{k=t+1}^{T} \gamma^{k-t} V(S_k) \ &= -V(S_t) + G_t + \gamma^{T-t} V(S_T) \quad \text{(telescoping sum)} \ &= G_t - V(S_t) \quad \text{(since } V(S_T) = 0 \text{ for terminal)}. \end{aligned} $$

This reveals that TD learning with all TD errors is equivalent to Monte Carlo learning—they target the same quantity, just decomposed differently.

TD Error Variance Analysis

The TD error has variance from:

1. Transition randomness: Where you end up ($s'$) is stochastic
2. Reward randomness: What reward you receive is stochastic
3. Value estimate noise: $V(s')$ is itself an estimate with error

Compare to MC error $G_t - V(S_t)$:

• MC accumulates variance from ALL future transitions and rewards
• TD only has variance from ONE step

This variance reduction is TD's key advantage, despite the bias from using $V(s')$ instead of the true value.

TD learning provably converges under appropriate conditions. The theory is more subtle than it might appear because TD uses biased estimates (bootstrapping).

Main Convergence Theorem for TD(0)

Theorem: For policy evaluation (estimating $V^\pi$), TD(0) converges to $V^\pi$ with probability 1 if:

1. The policy $\pi$ generates an ergodic Markov chain (every state visited infinitely often)
2. Learning rates satisfy: $\sum_t \alpha_t = \infty$ and $\sum_t \alpha_t^2 < \infty$

Intuition: The first condition ensures all states are updated infinitely. The second ensures updates eventually become small enough to dampen oscillations while still reaching any value.

Why TD Converges Despite Bias

The bias in TD comes from using $V(S_{t+1})$ instead of true $V^\pi(S_{t+1})$. Why doesn't this cause systematic error?

Key insight: The bias decreases as learning progresses. As $V$ approaches $V^\pi$, the bootstrap estimate $V(S_{t+1})$ approaches $V^\pi(S_{t+1})$, and the bias vanishes.

Formally, define the operator: $$T^\pi V(s) = \mathbb{E}\pi[R{t+1} + \gamma V(S_{t+1}) | S_t = s]$$

This is a $\gamma$-contraction: $|T^\pi V - T^\pi U|\infty \leq \gamma |V - U|\infty$.

TD(0) approximates applying $T^\pi$ using samples. The contraction property ensures that even with noisy samples, the iteration converges.

Convergence Rate: TD vs MC

Which converges faster? It depends on the problem!

TD is faster when:

• Episodes are long (MC must wait until end)
• Initial value estimates are reasonable (bootstrapping helps)
• Transitions are deterministic or low-variance

MC is faster when:

• Episodes are short
• Rewards are the main source of information (not transitions)
• The value function is complex/rapidly changing

Empirical finding (Sutton, 1988): For many problems, especially those with multi-step dependencies and long episodes, TD learns correct values significantly faster than MC.

One-step TD (TD(0)) and full-return MC are endpoints of a spectrum. n-step TD fills the continuum.

n-Step Returns

The n-step return from time $t$: $$G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \ldots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})$$

This uses $n$ actual rewards and bootstraps from step $t+n$.

n-Step TD Update: $$V(S_t) \leftarrow V(S_t) + \alpha \left[ G_{t:t+n} - V(S_t) \right]$$

The Bias-Variance Trade-off

As $n$ increases:

Bias decreases:

• More real rewards, less dependence on estimated values
• At $n = \infty$: No bias (pure MC)

Variance increases:

• More random rewards accumulated
• Each reward adds variance from that step's transition

The optimal $n$ balances these effects and is problem-dependent.

Rather than choosing a single $n$, why not use a weighted average of all n-step returns? This is TD(λ), one of the most elegant ideas in RL.

The λ-Return

The λ-return $G_t^\lambda$ is a weighted average of all n-step returns:

$$G_t^\lambda = (1-\lambda) \sum_{n=1}^{T-t-1} \lambda^{n-1} G_{t:t+n} + \lambda^{T-t-1} G_t$$

The weights $(1-\lambda)\lambda^{n-1}$ are exponentially decaying, summing to 1.

Special cases:

• $\lambda = 0$: Only TD(0) return $G_{t:t+1}$ has weight 1 → TD(0)
• $\lambda = 1$: Only full return $G_t$ has weight 1 → Monte Carlo

Geometric Weighting Intuition

Why exponential decay? Consider the weight on the n-step return:

• 1-step: $(1-\lambda) \cdot 1 = (1-\lambda)$
• 2-step: $(1-\lambda) \cdot \lambda$
• 3-step: $(1-\lambda) \cdot \lambda^2$
• ...

For $\lambda = 0.9$:

• 1-step gets 10% weight
• 2-step gets 9% weight
• ...
• 10-step gets ~4% weight
• 50-step gets ~0.5% weight

This gives preference to shorter (lower variance) returns while still incorporating longer-horizon information.

Why λ Works

TD(λ) interpolates between TD(0) (low variance, high bias) and MC (high variance, no bias):

• Small λ (≈ 0): Predominantly short-horizon, low variance
• Large λ (≈ 1): Predominantly long-horizon, low bias
• Medium λ (≈ 0.8–0.95): Often best of both worlds

Unlike fixed n-step methods, λ-returns are robust: even if the optimal n varies across states, λ-averaging tends to work reasonably everywhere.

So far, we've discussed online TD: updating after each step of experience. Batch TD processes a fixed dataset repeatedly until convergence, revealing theoretical properties more clearly.

Batch TD Algorithm

Given a batch of transitions ${(s_i, r_i, s'i)}{i=1}^{N}$:

1. Initialize $V$ arbitrarily
2. Repeat until convergence:
   • For each transition $(s, r, s')$ in batch:
     • $V(s) \leftarrow V(s) + \alpha[r + \gamma V(s') - V(s)]$
3. Return converged $V$

Batch TD converges to a well-defined fixed point, unlike online TD which depends on visit order.

What Does Batch TD Converge To?

Batch TD converges to the value function that would be optimal for the maximum likelihood MDP estimated from the data.

From the batch, estimate:

• $\hat{P}(s' | s, a) = \frac{#(s, a, s')}{#(s, a)}$
• $\hat{R}(s, a) = \text{mean reward when } (s, a) \text{ observed}$

Then batch TD converges to $V$ satisfying: $$V(s) = \hat{R}(s) + \gamma \sum_{s'} \hat{P}(s' | s) V(s')$$

This is certainty equivalence: TD behaves as if the estimated model is truth.

Example: TD vs MC with Sparse Data

Consider a 3-state MDP where we observe:

• 8 episodes of A → B → C (reward 0 everywhere)
• 1 episode of B → C (reward 1 at C)

MC estimate for V(A):

• Only direct episodes starting at A observed
• All ended with reward 0
• $V_{MC}(A) = 0$

TD estimate for V(A):

• Learns $V(B) \approx 0.11$ from the B→C data (1/9 episodes from B got reward)
• Propagates: $V(A) = 0 + \gamma V(B) \approx 0.11$
• TD leverages the shared B→C transition!

TD's use of the Markov structure extracts more information from limited data.

One of the most remarkable connections in computational neuroscience is between TD learning and the brain's reward system.

The Dopamine Connection

In the mid-1990s, Wolfram Schultz and colleagues made a striking discovery: dopamine neurons in the midbrain fire in patterns that closely match TD errors.

Experimental Setup: Monkeys learn that a light predicts juice reward after a delay.

Dopamine Response Evolution:

1. Before learning: Dopamine neurons fire when reward (juice) arrives (unexpected reward → positive δ)
2. After learning: Neurons fire at the light, not the juice (value prediction updates → light predicts reward)
3. Omitted reward: Neurons are inhibited when expected juice doesn't come (negative δ)

This matches TD error perfectly: positive firing for better-than-expected, negative (inhibition) for worse-than-expected, baseline for as-expected.

The Actor-Critic Architecture in the Brain

Neuroscience also finds evidence for an actor-critic decomposition:

• Critic (value estimation): Ventral striatum and orbitofrontal cortex appear to encode state values
• Actor (policy): Dorsal striatum appears to select actions based on learned associations
• TD error (dopamine): Modulates both, updating value estimates and action preferences

This mirrors the actor-critic RL architecture, where a critic learns $V$ (or $Q$) and TD errors train both the value function and the policy.

The parallel is not exact—brains are far more complex—but the high-level similarity is striking and has driven research in both fields.

Temporal difference learning represents a breakthrough in understanding how to learn from sequential experience. Let's consolidate the key insights:

What's next: We've established the theory of TD learning and seen it in action through Q-learning and SARSA. The next page introduces eligibility traces, the mechanism that makes TD(λ) computationally tractable and provides a beautiful backward view of the λ-return forward view.