Problem: Let \(p(r_{t+1},\mathbf x_{t+1}|\mathbf x_t)\) be a Markov reward process. Compare constant-\(\alpha\) Monte Carlo (MC) evaluation and \(n\)-step constant-\(\alpha\) temporal difference (TD) evaluation.
Solution: Essentially, TD is a bootstrapped version of MC, and indeed it turns out \(\lim_{n\to\infty}\text{TD}_{(n,\alpha)}=\text{MC}_{\alpha}\). That is, both TD and MC are model-free methods for evaluating the value function \(\langle R_t|\mathbf x_t\rangle\), but whereas MC patiently waits for each episode to reach a terminal state before the value functions of the visited states are simultaneously updated \(\Delta\langle R_t|\mathbf x_t\rangle=\alpha(\sum_{\text{visits }i\text{ to }\mathbf x_t}R_i-\langle R_t|\mathbf x_t\rangle)\), \(n\)-step TD is more impatient and instead replaces the empirical return \(R_i\mapsto r_{t+1}+…+\gamma^{n-1}r_{t+n}+\gamma^n\langle R_{t+n}|\mathbf x_{t+n}\rangle\) with a bootstrapped estimate depending on the estimated value \(\langle R_{t+n}|\mathbf x_{t+n}\rangle\) (this is not to be confused with the RL definition of dynamic programming (DP) which like TD also relies on recursive bootstrapping, but unlike TD is model-based rather than model-free. Also, don’t confuse the concept of DP in RL with DP in CS which simply means recursion with memoization).
Problem: Explain why, in practice, TD outperforms MC at value function estimation.
Solution: A useful analogy is to imagine a carnival (MRP) with \(2\) games (states) \(A,B\). Game \(A\) always returns reward \(r_A=0\) but also asserts the player has to proceed to game \(B\) (i.e. \(p(r_{t+1}=0,\mathbf x_{t+1}=B|\mathbf x_t=A)=1\)), and game \(B\) can return reward \(r_B\in\{0,1\}\) with (say) \(50:50\) odds but after that the player must go home. Imagine a batch of \(8\) carnival players/”episodes”, \(2\) of which are initialized at game \(A\), and the other \(6\) are initialized at game \(B\). It turns out that both of the players who begin at game \(A\) then receive \(r_A=0\) as expected, and then proceed to game \(B\) and happen to receive \(r_B=0\) and go home. On the other hand, of the \(6\) players who begin at game \(B\), \(4\) of them get \(r_B=1\) while the remaining \(2\) get \(r_B=0\). Assuming undiscounted return \(\gamma=1\), the Monte Carlo approach would look at the \(2\) episodes that passed through game \(A\), and conclude that game \(A\) has no value \(\langle R_t|\mathbf x_t=A\rangle=0\), whereas game \(B\) seems to have value \(\langle R_t|\mathbf x_t=B\rangle=4/8=1/2\). By contrast, a TD approach would say that both games \(A\) and \(B\) have value \(1/2\) because anyone who plays game \(A\) has to play game \(B\). Thus, TD is about finding the maximum likelihood for the MRP, whereas MC is about minimizing mean-squared error.
(aside: to illustrate this more clearly, consider \(n=1\)-step TD where \(\Delta\langle R_t|\mathbf x_t\rangle=\alpha(r_{t+1}+\gamma\langle R_{t+1}|\mathbf x_{t+1}\rangle-\langle R_t|\mathbf x_t\rangle)\) for each visit to state \(\mathbf x_t\). Then the total bootstrap on the value over all times \(t\) when \(\mathbf x_t\) was visited would be given by: \(\sum_t\Delta\langle R_t|\mathbf x_t\rangle=0\) at equilibrium, so rearranging, one finds a Bellman-like equation \(v(\mathbf x)=\hat r_{t+1}+\gamma\hat{v}(\mathbf x_{t+1})\). This result is sometimes called Sutton’s theorem).