Exercise 4.2.2

TD(0): first-episode update in the random walk

Reinforcement Learning › Exercises › Lecture 4 · Monte Carlo Methods and TD Learning › 4.2 Temporal-difference learning: TD(0)
MediumWritten

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)\).

randomwalk.png
Figure 1: State diagram of the Random Walk Markov reward process. Transition probabilities are uniform (50% left, 50% right). The initial state is the center state \(C\), and the extreme left and right states are the terminal states. When an episode terminates on the right, a reward of \(+1\) occurs; all other rewards are zero.
randomwalkgraph.png
Figure 2: Values learned after various numbers of episodes on a single run of TD(0) with \(\alpha=0.1\). The red line corresponds to the estimate \(V\) after 1 episode.
  • (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.