Comparison of Methods for Solving Finite Markov Decision Problems
Finite Markov decision problems can be approached with dynamic programming, Monte Carlo methods, or temporal-difference learning.
The Choice Behind the Method
Finite Markov decision problems can be approached in three fundamental ways: dynamic programming, Monte Carlo methods, and temporal-difference learning. The methods address the same broad problem family, but they make different trade-offs. The central question is not which method is universally best. It is which information is available and how the computation needs to proceed.
The first useful distinction is model access. Dynamic programming assumes a complete and accurate model. Monte Carlo methods and temporal-difference learning do not require a model. The second distinction is computation style: Monte Carlo methods are episode-based and not well suited to step-by-step incremental computation, whereas temporal-difference learning is fully incremental.
Dynamic Programming and Model Access
Dynamic programming methods assume access to a complete and accurate model of the environment. This model requirement is their defining practical constraint. If the model is available, dynamic programming offers a well-developed mathematical approach. If the model is unavailable, the method's central requirement cannot be met.
Learning from Complete Episodes
Monte Carlo methods take the opposite position on model access from dynamic programming: they require no model. They can learn from complete episodes, using the returns observed from those episodes rather than requiring a complete and accurate model in advance. This makes them attractive when the environment model is unavailable.
Monte Carlo methods exchange the need for a model for a limitation in computation style. They are conceptually simple, but they are not well suited for step-by-step incremental computation.
Incremental Updates and Delayed Returns
The important contrast between Monte Carlo methods and temporal-difference learning is when computation can occur. Monte Carlo methods use complete episodes and are not well suited to step-by-step incremental computation. Temporal-difference learning also needs no model, but it is fully incremental. This means temporal-difference learning can update its computation as experience proceeds rather than depending on the same complete-episode style used by Monte Carlo methods.
| Method class | Model required | Computation style | Important trade-off |
|---|---|---|---|
| Dynamic programming | Yes; a complete and accurate model | Model-based computation | Its defining practical constraint is access to the model |
| Monte Carlo methods | No | Complete-episode learning | Conceptually simple, but not well suited to step-by-step incremental computation |
| Temporal-difference learning | No | Fully incremental learning | More complex to analyze |
Classifying Method Requirements
Choosing from Three Requirements
Classify the most suitable method class for each stated requirement using only model access and computation style.
Requirement 1: A complete and accurate environment model is available. Dynamic programming is the method class defined by this model-based requirement.
Requirement 2: No environment model is available, and conceptual simplicity is especially important. Monte Carlo methods are attractive because they require no model and are conceptually simple.
Requirement 3: No environment model is available, and the computation must be fully incremental. Temporal-difference learning matches that requirement.
Requirement 4: No environment model is available, but the computation is expected to use complete episodes rather than step-by-step incremental updates. Monte Carlo methods match that computation style.
The correct classification depends on the requirement: dynamic programming for access to a complete and accurate model, Monte Carlo methods for model-free and conceptually simple complete-episode learning, and temporal-difference learning for model-free fully incremental computation.
This classification is not a claim that one method always outperforms the others. The supplied material emphasizes that method choice involves multiple trade-offs, including model access, conceptual simplicity, incremental computation, ease of analysis, efficiency, and speed of convergence. It does not assign one fixed ordering to those properties.
Mistakes in Method Selection
Treating Monte Carlo methods as universally better because they do not require a model.
The absence of a model is an advantage, but Monte Carlo methods are not well suited for step-by-step incremental computation.
Fix:
Check both model availability and computation style. If fully incremental computation is required and no model is available, temporal-difference learning matches that requirement.Describing dynamic programming as model-free.
Dynamic programming methods assume access to a complete and accurate model of the environment.
Fix:
Treat model access as dynamic programming's defining practical requirement.Assuming that temporal-difference learning is simply Monte Carlo learning with a different name.
Temporal-difference learning is fully incremental, while Monte Carlo methods are not well suited to step-by-step incremental computation.
Fix:
Use computation timing as a distinguishing feature: complete-episode learning points toward Monte Carlo methods, while fully incremental learning points toward temporal-difference learning.Claiming a fixed winner based on efficiency or convergence speed.
The supplied material identifies trade-offs but does not assign one fixed ordering to efficiency or speed of convergence.
Fix:
Make a comparative choice based on the stated requirement rather than a universal ranking.
Practice the Decision
For each situation, choose dynamic programming, Monte Carlo methods, or temporal-difference learning, then justify your choice using one requirement: model availability, conceptual simplicity, complete-episode computation, or fully incremental computation. Situation A: a complete and accurate environment model is available. Situation B: no model is available and the method should remain conceptually simple. Situation C: no model is available and estimates must be updated incrementally.
Hints
- Start by checking whether a complete and accurate model is available.
- If no model is available, distinguish complete-episode computation from fully incremental computation.
- Do not choose based on a universal claim that one method is always best.
What do you think happens?
A problem has no available environment model, and the computation must be fully incremental. Which method class fits best?
Reveal answer
Answer: Temporal-difference learning
Dynamic programming requires a complete and accurate model. Monte Carlo methods require no model but are not well suited to step-by-step incremental computation. Temporal-difference learning requires no model and is fully incremental.
Final Comparison
- The three fundamental method classes are dynamic programming, Monte Carlo methods, and temporal-difference learning.
- Dynamic programming assumes a complete and accurate environment model, making model access its defining practical constraint.
- Monte Carlo methods require no model and are conceptually simple, but they are not well suited to step-by-step incremental computation.
- Temporal-difference learning also requires no model and is fully incremental, but it is more complex to analyze.
- Method selection should follow the available information and required computation style, not a claim that one class is universally best.
Key Takeaways
- Dynamic programming, Monte Carlo methods, and temporal-difference learning are the three fundamental method classes for finite Markov decision problems.
- Dynamic programming requires a complete and accurate environment model.
- Monte Carlo methods are attractive without a model and are conceptually simple, but they are not well suited to step-by-step incremental computation.
- Temporal-difference learning also works without a model and is fully incremental, although it is more complex to analyze.
- The appropriate method depends on model availability and the required computation style rather than on a universal ranking.