Because this task is undiscounted and episodic, the true value of each state is just the probability of terminating on the right if starting from that state. Thus, the true value of the center state is . The true values of all the states, A through E , are , and . In all cases the approximate value function was initialized to the intermediate value , for all s . A small Markov process for generating random walks.
Walks start in the center, then move randomly right or left until entering a terminal state.
The final estimate is about as close as the estimates ever get to the true values. The performance measure shown is the squared error between the value function learned and the true value function, averaged over the five states. These data are averages over 100 different sequences of episodes. This is a exercise to help develop your intuition about why TD methods are often more efficient than MC methods. Consider the driving-home example and how it is addressed by TD and MC methods.