Incremental Monte Carlo Methods

From Episode to Estimate

Incremental Monte Carlo prediction updates a state prediction progressively instead of waiting to perform one final calculation after all experience has been collected. The process is organized episode by episode: an episode produces returns, and those returns provide the information used to adjust the prediction.

State Before the New Return

Consider one state that has already appeared in earlier experience. The returns G_1 through G_n−1 that began in this state have already been processed. Their information is summarized by two stored quantities: V_n−1, the current weighted-average estimate, and C_n−1, the cumulative weight assigned to the previously processed returns.

Adding G_n Incrementally

When the next return G_n arrives, it is paired with its corresponding weight W_n in the off-policy setting. The learner does not treat G_n as an isolated observation, and it does not rebuild the estimate from every earlier return. Instead, it combines the stored estimate and stored cumulative weight with this one new return-weight pair.

The sequence matters. Before the update, the stored information represents the first n−1 returns and their weights. After the update, the cumulative weight must represent the first n weights, and V_n must represent the weighted-average estimate after G_n has been included.

Why C_n Matters

The cumulative weight sum C_n tells the update how much weighted information has already been incorporated. It accumulates the weights of the first n returns. Therefore, the newest return is combined with an estimate that already summarizes earlier weighted returns, rather than being treated as though it were the only observation.

Returns, Not Rewards

Incremental techniques can be used in more than one setting, but the quantity being averaged changes with the method. Earlier incremental techniques may average rewards observed at individual time steps. Monte Carlo methods average returns. A return is the information produced for the state from the episode, and that return is what the Monte Carlo prediction process incorporates.

Implementing the Update Cycle

An incremental implementation follows a repeated cycle. Process an episode, obtain the returns associated with the states encountered, pair each return with its corresponding weight when the off-policy setting supplies one, and update the stored prediction and cumulative weight for the relevant state. The next episode then contributes another update.

• Maintain V for each state as the current prediction.
• Maintain C for each state as the cumulative sum of the associated weights.
• After an episode, identify the returns that provide the episode's prediction information.
• In the off-policy setting, use each return together with its corresponding random weight.
• Update the state information so that the estimate and cumulative weight include the new contribution.

Mistakes to Avoid

• Averaging immediate rewards instead of returns

  Monte Carlo methods average returns, and the return is the information supplied by the episode for the state.

  Fix: Identify and incorporate the return associated with the state.

• Discarding the previous estimate

  The new return must be combined with the information already summarized by the stored estimate.

  Fix: Use the previous estimate together with the new return and its weight.

• Resetting the cumulative weight to the newest weight

  C_n must represent the cumulative weights for the first n returns, not only the newest contribution.

  Fix: Extend the previous cumulative weight to include the new return's weight.

• Updating only one state-wide value without tracking state-specific information

  The source specifies that V_n and C_n must be maintained for each state as new returns arrive.

  Fix: Maintain the current estimate and cumulative weight separately for each state.

Check Your Understanding