Exercise 4.2.2
TD(0): first-episode update in the random walk
Recall the Random Walk example from the lecture and the book (see Figure 1). Because the task is undiscounted the true value \(v_{\pi}\) of each state is the probability of terminating on the right if starting from that state. So from \(A\) through \(E\) the true value \(v_{\pi}\) is \(\frac{1}{6}, \frac{2}{6}, \frac{3}{6}, \frac{4}{6}, \frac{5}{6}\). Figure 2 shows the estimates \(V(s)\) for all states \(s\) after varying number of episodes. From figure 2 it appears that the first episode results in a change in only \(V(A)\).
-
(a) What does this tell you about what happened in the first episode? Why was only the estimate for this one state changed?
-
(b) By exactly how much was it changed?
Source: Sutton & Barto (2018), Reinforcement Learning: An Introduction, 2nd ed., Exercise 6.3; Example 6.2. The random-walk diagram of Example 6.2 is redrawn from the book. The left graph of Example 6.2 is redrawn from a new run of the book's experiment. Licensed CC BY-NC-ND 2.0.