Exercise 4.3.4

TD(0): Monte Carlo error as a sum of TD errors when V changes

Reinforcement Learning › Exercises › Lecture 4 · Monte Carlo Methods and TD Learning › 4.3 MC vs TD: bias and variance, batch updates
HardWritten

Recall the following derivation from the value function: \[\begin{array}{l l l} v_{\pi}(s) &= \mathbb{E}_{\pi}[G_t | S_t=s] \\ & = \mathbb{E}_{\pi}[R_{t+1} + \gamma G_{t+1} | S_t=s] \\ & = \mathbb{E}_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t=s]. \end{array}\] Let \(V\) denote a tabular estimate of \(v_{\pi}\). One step temporal difference learning, TD(0), for estimating \(v_{\pi}\) uses an estimate of the last derivation as a target for the update rule: \[\begin{equation*} \tag{1} V(S_t) \leftarrow V(S_t) + \alpha \big[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t)], \end{equation*}\] where \(\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\) is called the TD error. The idea is that we can get “closer" to the true value function by aligning the estimate with the definition of the true value function. \(\delta_t\) is called the TD error as it measures the difference between the current estimate \(V(S_t)\) and the better estimate \(R_{t+1} + \gamma V(S_{t+1})\). Similarly, Monte-Carlo methods use the first derivation, \(\mathbb{E}_{\pi}[G_t|S_t=s]\) as a target. As it turns out, the Monte Carlo error can be written as a sum of TD errors: \[\begin{array}{l l l} \underbrace{G_t - V(S_t)}_{\text{Target - Current Estimate}} &= R_{t+1} + \gamma G_{t+1} - V(S_t) + \gamma V(S_{t+1}) - \gamma V(S_{t+1}) \\ &= \delta_t + \gamma (G_{t+1} - V(S_{t+1})) \\ &= \delta + \gamma \delta_{t+1} + \gamma^2(G_{t+2} - V(S_{t+2})) \\ &= \delta_t + \gamma \delta_{t+1} + \gamma^2 \delta_{t+2} + \ldots + \gamma^{T - t - 1} \delta_{T-1} + \gamma^{T-t}(G_T - V(S_T)) \\ &= \delta_t + \gamma \delta_{t+1} + \gamma^2 \delta_{t+2} + \ldots + \gamma^{T-t-1} \delta_{T-1} + \gamma^{T-t} (0-0) \\ & = \sum^{T-1}_{k=t} \gamma^{k-t} \delta_k. \end{array}\] Generalizations of the resulting identity, \[G_t - V(S_t) = \sum^{T-1}_{k=t} \gamma^{k-t} \delta_k, \quad (I)\] play an important role in the theory and algorithms of TD learning.

If \(V\) changes during the episode, then \((I)\) only holds approximately; what would the difference be between the two sides? Let \(V_t\) denote the array of state values used at time \(t\) in TD error and in the TD update. Redo the derivation above to determine the additional amount that must be added to the sum of TD errors in order to equal the Monte Carlo error.

Source: Sutton & Barto (2018), Reinforcement Learning: An Introduction, 2nd ed., Exercise 6.1. Licensed CC BY-NC-ND 2.0.