State-Value Prediction

Two Answers from One Batch

Suppose you receive several complete episodes from an unknown Markov reward process. Your task is to assign a value to each state: the return expected after entering that state. In the source batch, two valid learning methods disagree about state A. Batch Monte Carlo assigns A a value of 0, while batch TD(0) assigns A a value of 3/4. The disagreement is not caused by different episodes. Both methods use the same eight episodes, but they use different evidence from those episodes.

The Episode Evidence

The batch contains eight episodes. One episode begins in A, moves to B with reward 0, and then terminates from B with reward 0. The other seven episodes begin in B and terminate immediately. Across all visits to B, six episodes are followed by a return of 1 and two are followed by a return of 0. Therefore, the estimated value of B is 3/4 under both methods.

Bootstrapping from B

TD(0) does not wait for a complete return before assigning a value to A. It looks at the immediate transition from A to B. The reward on that transition is 0, but the following state B already has an estimated value of 3/4 based on the other episodes. TD(0) treats that next-state estimate as useful evidence about A. In this batch, the resulting value for A is 3/4.

Training Fit and Future Prediction

The two estimates answer different practical questions. If the goal is to reproduce the return already recorded after A, Monte Carlo fits that training observation perfectly: the recorded return was 0, and Monte Carlo assigns A a value of 0. TD(0) does not fit that single recorded return as closely, because it assigns A a value of 3/4. However, the goal of state-value prediction is not merely to memorize the returns in one batch. It is to predict what will happen in future episodes.

The transition from A to B provides information about the process. Because the process is Markov, the future depends on the current state rather than on the earlier history once the current state is known. Therefore, after the process reaches B, the earlier fact that the episode came from A does not remove the usefulness of B's observed value. In the given example, this makes the TD(0) estimate of 3/4 for A the estimate expected to have lower error on future data.

Mistakes About the Estimates

• Assuming both methods must produce the same value for every state.

  The methods use different evidence: complete observed returns for Monte Carlo, and the next state's estimated value for TD(0).

  Fix: Compare the evidence used by the method before comparing the resulting estimates.

• Treating TD(0)'s value for A as the complete return observed after A.

  TD(0) bootstraps from the estimated value of B instead of following only the complete observed return.

  Fix: Separate the observed return after A from the estimate inferred through the transition A to B.

• Choosing the value that fits the recorded batch and calling it automatically the best future prediction.

  Training-data fit and future-data prediction are different goals.

  Fix: Ask whether the task is reproducing observed returns or generalizing to future episodes.

• Ignoring the Markov property when evaluating the transition from A to B.

  In the given Markov process, the future depends on the current state rather than the earlier history once the current state is known.

  Fix: Use B's estimated value as relevant evidence for the transition from A to B.

Check Your Reasoning

What to Remember

1. Monte Carlo estimates a state's value from the complete returns actually observed after visits to that state.
2. TD(0) uses the immediate transition and the estimated value of the following state.
3. In the source batch, B has value 3/4 under both methods, but A has value 0 under Monte Carlo and 3/4 under TD(0).
4. A value that fits the recorded training return best is not necessarily the value that predicts future episodes best.
5. Because the process is Markov, the current state contains the relevant information for using B's value when predicting from the transition A to B.