Monte Carlo Methods in Reinforcement Learning
λ identifies important endpoint cases of the λ-return.
Two Ways to Approach Reinforcement Learning
Reinforcement learning can approach a problem by estimating how valuable states or actions are, or by comparing the complete behavior produced by different policies. The λ-return connects two important return-based cases: when λ = 1, it produces the conventional return associated with the Monte Carlo algorithm; when λ = 0, it produces the one-step return associated with the one-step TD method. Evolutionary methods take a different route altogether: they compare whole policies according to the reward obtained during an agent's lifetime rather than constructing a value function.
The safest way to classify a λ-return case is to simplify the return first, then identify the method associated with the resulting return.
Reading the λ-Return Endpoints
λ is best understood by examining the two endpoint settings of the λ-return. At λ = 1, backing up according to the λ-return becomes a Monte Carlo algorithm because the return becomes the conventional return. At λ = 0, the λ-return becomes G (1) t, the one-step return, and backing up according to it becomes the one-step TD method.
Separating the Two Endpoint Methods
| λ setting | Simplified return | Associated method |
|---|---|---|
| λ = 1 | Conventional return | Monte Carlo algorithm |
| λ = 0 | G (1) t, the one-step return | One-step TD method |
Treating λ = 1 as merely similar to Monte Carlo learning.
The stated property is stronger: after the λ = 1 simplification, the return is the conventional return, and backing up according to it is identified as a Monte Carlo algorithm.
Fix:
State the complete chain: λ = 1, conventional return, Monte Carlo algorithm.Associating λ = 0 with the Monte Carlo algorithm.
The λ = 0 endpoint produces G (1) t, the one-step return.
Fix:
State the complete chain: λ = 0, one-step return, one-step TD method.Naming a method before simplifying the return.
The classification depends on which return the λ-return produces at that setting.
Fix:
First identify the simplified return; then identify the associated method.
What do you think happens?
A λ-return is evaluated at λ = 0. Which method should be associated with it?
Reveal answer
Answer: The one-step TD method
At λ = 0, the λ-return becomes G (1) t, the one-step return. Backing up according to that return leads to the one-step TD method.
Policy Search Without Value Estimates
Evolutionary methods approach reinforcement learning without estimating state values or action values. Instead of asking how valuable one particular state or action is, they compare complete policies. A candidate agent follows its policy while interacting with the environment, receives reward for the behavior produced during its lifetime, and is judged by that result.
In this context, an evolutionary method is a policy-search approach in which candidate policies are evaluated by lifetime reward, compared with one another, and used to guide further search toward candidates associated with better results.
The unit being evaluated is the agent's lifetime behavior. The method can search by comparing whole policies even when it never constructs a value function.
From Population to Selected Policies
A population-based evolutionary process begins with a collection of agents or candidate policies. Each candidate can use a different policy to decide how it interacts with the environment. During its lifetime, the individual agent does not improve through learning. After the interaction period ends, the method evaluates the reward obtained by that complete behavior. Candidates associated with more reward are favored, while weaker candidates are not favored for the next stage of the search.
Comparing Three Candidate Policies
Imagine three non-learning agents, each using a different policy. Their complete interactions with the environment produce different lifetime rewards.
Evaluate: Allow each candidate to follow its policy during its interaction period and record the reward obtained by that complete behavior.
Compare: Compare the candidates according to the reward associated with their lifetime behavior.
Select: Favor the candidates that obtain more reward as the basis for further search.
The process searches over policies by comparing whole-agent performance, not by estimating the value of an isolated state or action.
Lifetime Scores Versus Value Estimates
| Evaluation viewpoint | What is evaluated | What guides the decision |
|---|---|---|
| Value-function approach | A state or an action | An estimate of its value |
| Evolutionary approach | An entire policy's lifetime behavior | The reward obtained by the complete behavior |
These viewpoints evaluate different units. A value function estimates the value of a state or action. An evolutionary method asks how well an entire policy performed over its interaction period. The second approach does not require the first, although both approaches can be used to address reinforcement learning problems.
When Evolutionary Search Fits
Evolutionary methods may be effective when the policy space is small, when the policy space can be organized so that good policies are common or easy to find, or when substantial time is available for searching. These conditions make it more plausible that comparison and selection will encounter useful policies.
They may also be useful when the learning agent cannot accurately sense the state of its environment. Methods that depend on accurate environmental sensing may face difficulty in that situation, while evolutionary evaluation can still compare the behavior produced by different policies according to the reward obtained.
- The policy space is small.
- Good policies are common or easy to find within the policy space.
- Substantial time is available for searching.
- The agent cannot accurately sense the state of the environment.
Check Your Reasoning
Classify each case using the source-grounded chain: identify the return first, then identify the method. Case A: λ = 1. Case B: λ = 0. Case C: a population of agents is compared using the reward obtained by each agent's complete lifetime behavior.
Hints
- For Case A, ask what the λ-return becomes at the upper endpoint.
- For Case B, look for the one-step return G (1) t.
- For Case C, decide whether the evaluation unit is an individual state or action, or an entire policy.
Practice Answers
Resolve the three cases by identifying the return or evaluation unit.
Case A: λ = 1 produces the conventional return, so the associated method is the Monte Carlo algorithm.
Case B: λ = 0 produces G (1) t, the one-step return, so the associated method is the one-step TD method.
Case C: The candidates are being evaluated by complete lifetime behavior and reward, which is the evolutionary policy-search viewpoint rather than value-function estimation.
The endpoint cases are distinguished by their simplified returns, while the evolutionary case is distinguished by its whole-policy lifetime evaluation.
Key Takeaways
- λ identifies important endpoint cases of the λ-return.
- At λ = 1, the λ-return becomes the conventional return and the associated method is Monte Carlo.
- At λ = 0, the λ-return becomes G (1) t, the one-step return, and the associated method is one-step TD.
- Evolutionary methods compare complete policies using lifetime reward rather than estimating state values or action values.
- Evolutionary search may be effective with small or searchable policy spaces, substantial search time, or limited environmental sensing.
Key Takeaways
- Classify λ-return cases by simplifying the return before naming the method.
- λ = 1 gives the conventional return and the Monte Carlo algorithm.
- λ = 0 gives the one-step return G (1) t and the one-step TD method.
- Evolutionary methods evaluate whole-policy lifetime behavior and compare rewards without requiring a value function.
- Small policy spaces, available search time, and limited state sensing can make evolutionary methods effective.