Where Monte Carlo Meets Dynamic Programming: The Magic of Temporal-Difference Learning

If Monte Carlo (MC) methods are the patient storytellers of reinforcement learning — waiting until an episode ends before revealing the full return — and Dynamic Programming (DP) is the all-knowing planner who computes expectations using a perfect model. Temporal-Difference (TD) Learning is the impatient pragmatist who cannot wait. It updates its beliefs step by step, learning from raw experience without ever needing to see the ending.

TD Learning elegantly blends the strengths of both MC and DP. It learns from experience like MC, and it bootstraps from its own value estimates like DP.

TD Learning as a middle path — created by author

In this article, we focus exclusively on prediction — estimating the value function​ of a fixed policy. The next article will move to control, where TD learning is incorporated into either on policy control (aka SARSA) or off policy control (aka Q-learning) to learn optimal policies.

1. The Prediction Problem

For a fixed policy π, the value of a state s is:

with the return defined as:

We want to estimate v_π​​ using experience generated by following π. We will now show how temporal-difference learning enjoys the practicality of MC methods and the efficiency of DP using the GridWorld example.

2. The Gridworld: Returning to a Familiar Friend

We reuse the same 5×5 Gridworld from previous articles. As a quick recap, the Gridworld has

• 25 states arranged in a grid
• Four actions: North, South, East, West
• Off-grid moves: stay in place, reward = −1
• Valid in-grid moves: reward = 0

Two teleport states:

• A (state 1) → A′ (state 21), reward = +10
• B (state 3) → B′ (state 13), reward = +5

Discount factor: γ = 0.9 Policy: Uniform random

Using DP and linear algebra, we solve for the true value function v_π​ (as explained in my first article). This gives us a ground truth for evaluating TD and MC numerically without the need to use a model.

3. Monte Carlo vs TD(0): Core Algorithms

Below pseudo-code blocks to illustrate how MC and TD differ.

TD(0) pseudo code:

Monte Carlo (Every Visit) Prediction:

4. TD(0) Learning: Numerical Comparison in Gridworld

Using these two algorithms on the same experience stream, we ran:

• 500 episodes
• 50 steps per episode
• α = 0.1
• Same random policy
• RMS error vs true v_π​ computed after each episode

This gives the learning curves below.

Simulation by author

Interpretation:

• TD(0) rapidly reduces RMS error within the first ~50 episodes
• MC learns more slowly and exhibits higher variance throughout
• TD(0) stabilizes to a consistently lower error band

In many problems, especially continuing tasks like Gridworld, the lower variance of TD leads to faster overall learning.

5. Why TD Learning Works: Targets, Errors, and the Nature of Learning

To understand why Temporal-Difference learning performs so well in practice, it helps to step back and ask a deceptively simple question:

What does it actually mean for an RL agent to “learn”?

All prediction methods covered so far — Monte Carlo, TD, and Dynamic Programming — share a common structure:

Learning happens by reducing prediction error: adjusting V(St) toward a better estimate of the return. The key distinction between methods lies entirely in how they construct the target and when it becomes available.

5.1 How Each Method Constructs Its Target

Monte Carlo uses the complete return:

This target reflects exactly what unfolded in the episode. But it is only available after the episode terminates.

MC’s target is the full return from this state to the end of the episode — a quantity revealed only once the entire episode has played out.

DP uses the model to compute:

This is a low-variance, expectation-based target — but it requires a perfect model of the environment.

TD(0) uses the one-step bootstrapped target:

This target is available immediately, during the episode.

TD updates during interaction by using the next reward and its current estimate of the next state’s value.

This makes TD both incremental and online — uniquely suited for continuing tasks.

5.2 Information Propagation: When Does Learning Flow Backward?

• Monte Carlo: Information propagates after the episode ends, flowing backward from the final rewards.
• Dynamic Programming: Information propagates everywhere at once through full sweeps using the model.
• TD(0): Information propagates one step at a time, continually nudging predictions as the agent interacts.

This difference in timing of updates is one reason TD appears to “learn sooner”: it simply doesn’t wait for an episode-ending signal.

5.3 Memory Requirements: How Much Must Each Method Store?

Memory demands are often ignored, but they shape what learning methods can realistically do.

DP must store: Full value table, Full transition model P(s′∣s,a) and reward model

Memory requirement: O(|S| + |S||A||S|)

Often infeasible outside small tabular environments.

MC must store full episodes: (S_0, A_0, R_1),….,(S_T)

Memory grows with the episode length: O(T)

Episodes can be extremely long — or infinite — in continuing tasks.

TD only needs: Current state, next state, reward, the value table V(s)

Memory per interaction: O(1)

TD’s constant memory footprint makes it ideal for online, streaming, and continual tasks.

5.4 Learning Through the Bias–Variance Trade-Off

Each method reflects a different balance:

• MC: Unbiased targets, high variance
• DP: Low variance, requires a model
• TD: Biased (bootstrapped) targets, much lower variance

This explains the empirical result from our Gridworld experiment: TD often converges in fewer episodes than MC, even if both use the same experience.

5.5 Why TD Often Works Better in Practice

Bringing all these ideas together:

1. TD updates during the episode → Learning begins immediately, not after termination.
2. TD uses low-variance, one-step targets → It typically makes better use of each sample.
3. TD requires only constant memory → Scales better to long or continuing tasks.
4. TD bootstraps value information efficiently → Information spreads across the state space faster.

This combination — incremental updates, low variance, low memory, and rapid propagation — explains why TD(0) is widely regarded as the most practical and foundational method for value prediction in reinforcement learning.

6. Why TD Converges: An Intuition for the “Magic” of Bootstrapping

One of the most surprising facts about TD learning is that — even though it updates from incomplete returns, and even though its targets are biased because they rely on the current value estimates — it still converges to the true value function v_π​ under mild assumptions.

When we say TD converges under mild assumptions, we simply mean that the agent must eventually visit all relevant states often enough, and the environment’s rules shouldn’t be changing while learning. Under these natural conditions, TD’s repeated corrections tend to stabilize around the true value function

How can a method that learns from its own guesses get the answer right?

Let’s build an intuition step by step.

6.1 The Fixed Point View: Chasing the Bellman Equation

The true value function v_π satisfies the Bellman equation:

This equation is a fixed point: the value function that, when plugged into the right-hand side, reproduces itself.

TD(0) tries to make our estimate V satisfy the same relationship:

Each TD update:

nudges V(s) toward its own Bellman backup.

Do this repeatedly, across all states, and the only stable place left to land is the same fixed point that v_π​ satisfies.

This is convergence by bootstrapped correction.

6.2 TD Error as a “Directional Signal” Toward the Truth

The TD error:

is not the true error — it’s an estimate of the true Bellman error. But it has a powerful property:

On average, the TD error points toward the direction in which V must be adjusted to reduce true prediction error.

Even though each step is noisy or biased, the expectation of the TD target is correct. The TD update moves V(St) in the right direction on average, and learning rates ensure those movements become smaller over time.

This is just like gradient descent with noisy gradients: each individual step may be imperfect, but the aggregate motion is toward a stable solution.

6.3 Experience Averages Out the Noise

TD relies on single-step samples like:

but over many samples, randomness in the transition, noise in the environment and suboptimal early estimates, all tend to cancel out.

What remains is the underlying expectation of the Bellman operator. Repeated application of this operator is a contraction mapping — meaning each application brings us closer to the fixed point.

This is why TD works even in messy environments: No matter how noisy individual updates are, the expected update points directly at the true value function.

6.4 Bootstrapping Causes Faster Propagation of Value Information

A big part of convergence speed — not just correctness — comes from the following:

• Monte Carlo waits for the future to actually happen.
• TD learns from a one-step guess about the future.

This means TD starts adjusting values long before full returns are available. Value information ripples through the state space early and often.

This accelerates convergence: TD doesn’t need to see full episodes, just enough transitions for the law of large numbers to kick in.

6.5 Why Bootstrapping Doesn’t Break Convergence

At first glance, TD learning looks circular:

• We update our guess using another guess.
• That second guess is also being updated using the first.

Why doesn’t this spiral into nonsense?

The answer is: bounded, diminishing updates + a contraction operator.

• Because every update reduces — or contracts — the gap between your estimate and the truth, repeated updates gradually home in on the correct values.
• The TD update is a stochastic approximation to this contraction.
• Learning rates ensure updates get smaller over time, eliminating oscillation.

The combination of these facts guarantees that TD iterates converge to the unique fixed point: the true value function.

6.6 An Intuitive Analogy: Learning by Forward Correction

Imagine hiking toward a landmark hidden in the fog.

• Monte Carlo says: “Walk the entire path, see where you ended up, then update your belief about the starting point.”
• TD says: “After every step, check whether you’re moving in the right direction. If the next landmark is closer or further than expected, adjust your belief immediately.”

Even though your compass may wobble or you may be uncertain, each course correction is:

• small,
• directional,
• guided by immediate feedback,
• and averaged over many trials.

Over time, these corrections align you exactly with the true path.

This is TD learning’s magic.

7. Coming Up Next: From Prediction to Control

Now that we understand how TD updates a value function for a fixed policy, we’re ready to let the policy itself start evolving.

In the next article:

• On-policy TD control → SARSA Learn action-value functions while following the same policy you’re evaluating.
• Off-policy TD control → Q-learning Learn the greedy policy while behaving according to an exploratory one.

Both are powered by the same TD error you saw in this article — but now extended to finding optimal policies.

If you found this article valuable, consider following for more deep dives into the mathematical foundations of reinforcement learning and AI.