Gradient Monte Carlo Methods

The Delayed Update

Linear gradient Monte Carlo prediction associates an update with each time step in an episode. However, every one of those updates depends on the episode's final reward or return. That information does not exist while the episode is still unfolding, so the algorithm cannot change its weight vector during those earlier steps. It waits until the episode ends and the final return is available.

The Eligibility Trace

An eligibility trace is an additional vector memory. As the episode progresses, it summarizes the vectors seen so far. Instead of saving every feature or state vector and processing all of them after termination, the algorithm maintains this accumulated summary during the episode.

The trace does not replace the final return. It records earlier vector information, while the final return remains the information needed to evaluate the whole episode. When the return becomes available, the accumulated trace is used to recreate the same overall Monte Carlo update that the original sequence of updates would have produced.

Work Distributed Across Time

The trace-based organization divides the work into two phases. Before the episode ends, auxiliary vectors are updated at each time step. At the terminal time, the return is observed and the accumulated quantities are used to compute the new weight vector. This means more supporting computation occurs during the episode and less computation remains for the end.

The important result is not a different learning outcome. According to the source, the trace-based implementation preserves the same overall Monte Carlo update as the less efficient organization. It changes when supporting work happens and what must be stored, not the final learning result.

Per-Step Complexity

The source describes the trace-based algorithm as having time and memory complexity per step of O(n), where n refers to the vector-sized quantity used by the algorithm. In practical terms, the work and additional memory at a step scale with the size of the vectors, rather than with the number of earlier time steps that would otherwise need to be retained and processed later.

This organization avoids storing every feature vector from every time step. Instead, the algorithm stores and updates an additional vector memory: the eligibility trace. Computation is distributed across the episode, so the end of the episode is not left with one poorly distributed operation over all previously encountered vectors.

Eligibility Trace Families

Common Misunderstandings

• Assuming the weight vector changes at every time step in linear gradient Monte Carlo.

  Each Monte Carlo update depends on the final reward or return, which is unavailable before the episode ends.

  Fix: Separate the time steps that gather episode information from the terminal time when the final return enables the weight update.

• Treating the eligibility trace as the final return.

  The trace summarizes earlier vector information, while the final return remains necessary for evaluating the episode.

  Fix: Think of the trace and the final return as two different pieces of the terminal computation.

• Assuming a trace-based implementation changes the learning result.

  The source states that the trace-based organization preserves the same overall Monte Carlo update.

  Fix: Describe the trace as a reorganization of computation and storage.

• Treating eligibility trace and Dutch trace as unrelated terms.

  The Dutch trace is identified as a particular type of eligibility trace.

  Fix: Use eligibility trace for the broader category and Dutch trace for the specified member of that category.

• Interpreting O(n) per step as complexity proportional to the full episode length.

  In the source, n refers to the vector-sized quantity used by the algorithm.

  Fix: Keep the complexity statement tied to the vector dimension or vector-sized quantity, not to the episode history length.

Check Your Understanding

Key Takeaways

1. Linear gradient Monte Carlo waits until an episode ends because its updates depend on the final return.
2. An eligibility trace is an additional vector memory that summarizes vectors encountered so far.
3. The trace-based organization performs supporting computation during each time step and leaves less work for the terminal time.
4. The trace avoids storing every earlier feature vector while preserving the same overall Monte Carlo update.
5. A Dutch trace is a specific type of eligibility trace, and the trace-based implementation is described as O(n) in time and memory per step.