Monte Carlo Prediction Methods

The Waiting-Time Difference

Monte Carlo and temporal difference methods differ in when they can learn. Monte Carlo methods wait until an episode ends, because only then is the complete return known. TD methods need to wait only one time step before learning from a transition. The central issue is therefore learning speed during an episode, not a claim that one method is always preferable.

Updates During an Episode

After a transition is observed, a TD method can update its value estimate after one time step. A Monte Carlo method cannot yet use the complete return for that episode, so it waits. If the episode continues for many more transitions, the difference in waiting time becomes increasingly important: TD learning may already have performed updates while Monte Carlo learning is still waiting.

Online Incremental Learning

The shorter waiting time makes TD methods naturally online and fully incremental. Online learning means that learning can begin while experience is still arriving. Incremental learning means that each newly available transition can contribute to learning rather than requiring the method to wait for an entire episode before starting its update process.

Very Long and Continuing Tasks

The online, incremental advantage matters especially when an episode is very long. Waiting for the complete return could delay learning for a substantial period. It also matters for continuing tasks without episodes, because there may be no natural episode ending at which a Monte Carlo method could obtain a complete return. TD methods can continue learning from transitions as they arrive instead of depending on such an endpoint.

Experimental Actions

TD methods can learn from transitions even when later actions are experimental. Once the transition caused by such an action has been observed, the TD method can use that transition after one time step. It does not need to wait for the episode's complete return before beginning to learn from the experience.

Target Information

This comparison should be kept precise. The source of TD's advantage here is the timing of the update: TD methods use each transition as it becomes available, while Monte Carlo methods postpone learning based on that episode until the complete return is known. This timing difference explains the online, incremental, long-task, and experimental-action advantages described above.

Common Timing Mistakes

• Treating TD and Monte Carlo methods as if they must wait for the same event.

  TD methods need to wait only one time step, whereas Monte Carlo methods wait until the episode ends because the complete return is then known.

  Fix: For each method, identify the earliest point at which its required learning information is available.

• Thinking that online learning means TD methods update before observing any transition.

  TD methods learn from transitions, so they still need an observed transition and one time step.

  Fix: Use the more precise description: TD methods learn transition by transition as experience becomes available.

• Ignoring the importance of episode length.

  A long wait before the episode ends can delay Monte Carlo learning while TD methods continue to update from transitions.

  Fix: Ask whether an episode is very long or whether the task has no natural episode ending.

• Assuming experimental actions prevent TD learning.

  TD methods can learn from transitions even when later actions are experimental.

  Fix: Recognize that an observed transition can support TD learning before the episode ends.

Check Your Understanding

Key Takeaways

1. TD methods learn transition by transition after waiting one time step.
2. Monte Carlo methods wait until an episode ends because the complete return is then known.
3. The shorter TD waiting time makes TD learning naturally online and fully incremental.
4. This timing advantage matters for very long episodes and continuing tasks without episodes.
5. TD methods can learn from observed transitions involving experimental actions before the episode ends.