Incremental averaging techniques from Chapter 2
Incremental Monte Carlo prediction is organized episode by episode.
From Episodes to Predictions
Incremental Monte Carlo prediction does not wait until every episode has been considered before adjusting a prediction. Instead, it processes experience episode by episode. Each episode supplies return information, that information contributes to the prediction, and the next episode supplies another contribution.
The Episode Update Cycle
Read the process from left to right. The first episode is processed, and its return becomes the information incorporated into the prediction. The prediction is therefore adjusted before the next episode is processed. Episode 2 then contributes another return, creating another update cycle. Incremental Monte Carlo prediction is this repeated organization of experience: episode, return, updated prediction, next episode.
What the Average Contains
Earlier incremental averaging techniques provide the general style of the process: new information is incorporated progressively rather than being handled only in one final calculation. Incremental Monte Carlo prediction extends that style. The important change is the kind of information supplied to the averaging process. Monte Carlo methods average returns, not rewards.
| Averaging process | Quantity incorporated |
|---|---|
| Earlier incremental techniques | Rewards |
| Monte Carlo prediction | Returns |
Tracing One New Return
A generated episode-by-episode illustration
A prediction for a state has already been formed. A new episode visits that state and supplies a return. How should the incremental Monte Carlo process be traced?
1. Process the episode: Treat the episode as the next contribution to the ongoing prediction process.
2. Identify the return: Use the return supplied by that episode as the information for the Monte Carlo averaging process.
3. Connect it to the state: The return contributes to the prediction associated with the state visited in the episode.
4. Continue incrementally: After the prediction is adjusted, the next episode can provide another return and another contribution.
The prediction is updated progressively from episode returns, one episode at a time. The illustration uses no numerical values because the key implementation issue is identifying the return as the quantity incorporated.
The state is the prediction target, while the return is the new information used to improve that prediction. The episode provides the connection between them. This is why a return should not be treated as an unrelated number: it is the episode's contribution to the prediction for the visited state.
Prediction Before and After
The diagram shows the direction of the process rather than a particular numerical formula. A current prediction exists before the new episode information is incorporated. The new return then contributes to an updated prediction. The next episode begins with that updated state of the prediction process.
What do you think happens?
A current prediction is lower than a newly observed return. In this generated illustration, which direction should the updated prediction move?
Reveal answer
Answer: Toward the newly observed return
The new return is the information incorporated into the incremental Monte Carlo update. The exact size of the movement is not specified here; the important point is that the prediction is adjusted using the new return.
Implementation Checks
Averaging an individual reward when implementing Monte Carlo prediction.
The source distinguishes Monte Carlo averaging from the earlier techniques by stating that Monte Carlo methods average returns, not rewards.
Fix:
Identify the return supplied by the episode and use that as the information incorporated into the prediction.Treating incremental Monte Carlo prediction as a completely unrelated method.
The implementation extends earlier incremental techniques by applying their progressive, episode-by-episode style to Monte Carlo returns.
Fix:
Reuse the general idea of progressive updating while checking that the input is an episode return.Updating only once after all episodes have been considered.
Incremental Monte Carlo prediction is organized episode by episode, with each episode contributing information before the next episode is processed.
Fix:
Trace the repeated cycle: process an episode, identify its return, adjust the prediction, and continue with the next episode.Failing to connect a return to the visited state.
The return provides information for the prediction associated with the relevant state.
Fix:
Trace the connection from the visited state to the episode return and then to the updated prediction.
Practice the Distinction
An episode visits a state and provides information that can improve the prediction for that state. In an incremental Monte Carlo implementation, should the averaging process incorporate an individual reward or the return from the episode? Explain the update cycle in order.
Hints
- Recall which quantity Monte Carlo methods average.
- Use the sequence episode, return, updated prediction, next episode.
- Mention the connection between the visited state and the prediction being updated.
Key Takeaways
- Incremental Monte Carlo prediction updates a prediction episode by episode.
- The return supplied by an episode is the quantity incorporated into Monte Carlo averaging.
- Monte Carlo methods average returns, not individual rewards.
- A return from an episode contributes to the prediction associated with a visited state.
- The process extends earlier incremental techniques by applying progressive updates to episode returns.
Key Takeaways
- Incremental Monte Carlo prediction is organized as a repeated episode-by-episode update cycle.
- Each episode supplies a return that contributes to the prediction for a visited state.
- The quantity averaged in Monte Carlo methods is the return, not an individual reward.
- The method extends earlier incremental averaging techniques rather than introducing an unrelated process.
- The most important implementation check is verifying that episode returns are being incorporated.