Episodes, Returns, and State-Value Estimates

Read a backup diagram from the value being updated outward. The top node is the root state, and the nodes below it show the information that contributes to the update.

Programming

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?

Key point

Read a backup diagram from the value being updated outward. The top node is the root state, and the nodes below it show the information that contributes to the update.

What information flows toward the root state whose value estimate is being updated?

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.

How does a root state connect to every subsequent state, action, and reward in one sampled episode?

Worked example

Tracing a Monte Carlo Diagram

Suppose a generated diagram begins at root state S0 and shows the sampled path S0, A0, R1, S1, A1, R2, terminal state. What does the diagram tell you?

1
Find the root
S0 is the root state, so its state-value estimate is the one being updated.
2
Follow the displayed path
Read the connected states, actions, and rewards as one selected trajectory rather than as a list of alternatives.
3
Check the endpoint
The path reaches a terminal state, so the displayed trajectory extends through the complete sampled episode.
4
Identify the update information
The rewards and later state information shown along this trajectory are the information represented as contributing to the update of the root estimate.

Result

The diagram represents one complete sampled episode beginning at S0, not every path that could have followed S0.

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.

What is the difference between following one sampled episode and branching over all possible one-step transitions?

Question to ask	Monte Carlo diagram	Dynamic Programming diagram
What transition information is shown?	One sampled episode	All possible one-step transitions
How far does the displayed information extend?	From the root through the terminal state	One step outward from the state
What does the structure look like?	A single selected trajectory	A set of possible successor transitions

Use both the included transitions and their extent when classifying a backup diagram.

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.

Does the diagram show a single trajectory that occurred, or every successor state and outcome that could occur next?

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.

How do rewards after a visited state become update information for that state's value estimate?

Common Classification Errors

Common mistake
Treating a Monte Carlo diagram as a list of every possible path
What it looks like
Assuming that several nodes shown along one connected route represent all outcomes that could have occurred.
Why it fails
A Monte Carlo backup diagram records the single trajectory selected for one episode.
Do this instead
Look for one sampled path that extends from the root through the terminal state.
Common mistake
Ignoring how far the transitions extend
What it looks like
Classifying a diagram only by whether it contains branches.
Why it fails
The classification depends on both which transitions are included and how far those transitions extend.
Do this instead
Check whether the information reaches the terminal state or represents all possible one-step transitions.
Common mistake
Starting the interpretation at a leaf instead of at the top node
What it looks like
Reading the diagram as a general episode description without identifying the state being updated.
Why it fails
The top node is the root: the state node whose estimate is being updated.
Do this instead
Locate the root first, then read outward to the transitions and leaf nodes.
Common mistake
Confusing sampled episode data with possible transitions
What it looks like
Calling every successor shown beneath a state part of one episode.
Why it fails
A Dynamic Programming diagram represents all possible one-step transitions, while a Monte Carlo diagram follows one sampled episode.
Do this instead
Determine whether the diagram shows one selected trajectory or a set of possible one-step outcomes.

Practice Classification

EASY

A diagram has root state S0. From S0, it shows one connected sequence of states, actions, and rewards, and the sequence ends at a terminal state. Is this diagram best classified as Monte Carlo or Dynamic Programming? Explain which two visual clues support your answer.

Hints

Check whether the diagram shows one selected path or all possible one-step transitions.
Check whether the displayed path continues through a terminal state.

Your attempt (not saved)

What do you think happens?

A diagram branches from a root state to several possible successor states, with the displayed structure limited to those one-step transitions. Which structure does this represent?

A Monte Carlo backup through one complete sampled episode
A Dynamic Programming backup over all possible one-step transitions
A single sampled trajectory through a terminal state

Reveal answer

Answer:

A Dynamic Programming backup over all possible one-step transitions

The defining clues are the set of possible one-step transitions and the absence of a single displayed trajectory extending through a terminal state.

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.

At a glance

Backup diagrams identify the information used to update a root state's value estimate.
Monte Carlo diagrams show one complete sampled episode, not every path that could have occurred.
Dynamic Programming diagrams show all possible one-step transitions from a state.
Classify a diagram by inspecting both its transition choices and the distance those transitions extend.
Rewards, estimated values, and leaf-node information are represented as contributors to the root update.

Related concepts

More concepts starting with E