Episodes, Returns, and State-Value Estimates

Reading the Update

A backup diagram is a visual explanation of an update to a state-value estimate. Begin with the state whose estimate is being updated, then inspect the experience or transition information shown beneath it. The diagram answers a practical question: which rewards, estimated values, and transitions are being used to revise this particular state estimate?

One Sampled Episode

A Monte Carlo backup diagram represents one sampled episode from the root state through the terminal state. It does not list every path that might have occurred. Instead, it records the single trajectory selected for that episode.

Transition Structure

Monte Carlo and Dynamic Programming diagrams differ in the transition information they display. A Monte Carlo diagram follows one sampled episode from the root through the terminal state. A Dynamic Programming diagram represents all possible one-step transitions from a state.

Classifying the Diagram

To classify an unfamiliar backup diagram, inspect two features together. First, ask which transitions are included. Second, ask how far those transitions extend. A single trajectory that continues from the root through a terminal state indicates sampled episode data. A diagram that branches over all possible one-step transitions indicates the Dynamic Programming structure described in the source.

1. Locate the top node and name it the root state.
2. Count the transition choices shown immediately below the root.
3. Check whether the diagram follows one selected path or displays all possible one-step transitions.
4. Check how far the displayed transitions extend: through a terminal state or only one step.
5. Classify the diagram using both observations, not just its visual shape.

From Rewards to Estimates

In a backup diagram, later rewards and state information are shown as inputs to the update of the root state estimate. For a Monte Carlo diagram, these inputs are attached to the one complete sampled episode that begins at the root and reaches the terminal state. The diagram therefore connects the episode's later information to the value estimate for the state from which the episode was traced.

Common Classification Errors

• Treating a Monte Carlo diagram as a list of every possible path

  A Monte Carlo backup diagram records the single trajectory selected for one episode.

  Fix: Look for one sampled path that extends from the root through the terminal state.

• Ignoring how far the transitions extend

  The classification depends on both which transitions are included and how far those transitions extend.

  Fix: Check whether the information reaches the terminal state or represents all possible one-step transitions.

• Starting the interpretation at a leaf instead of at the top node

  The top node is the root: the state node whose estimate is being updated.

  Fix: Locate the root first, then read outward to the transitions and leaf nodes.

• Confusing sampled episode data with possible transitions

  A Dynamic Programming diagram represents all possible one-step transitions, while a Monte Carlo diagram follows one sampled episode.

  Fix: Determine whether the diagram shows one selected trajectory or a set of possible one-step outcomes.

Practice Classification

Key Takeaways

1. A backup diagram shows what information feeds an update to a root state node.
2. The root is the state whose value estimate is being updated.
3. A Monte Carlo backup follows one sampled episode from the root through the terminal state.
4. A Dynamic Programming diagram represents all possible one-step transitions.
5. To classify a diagram, inspect both the transitions included and how far they extend.