Exercise 4.1.2
Monte Carlo prediction: convergence with probability 1 via Robbins-Monro
In Monte Carlo methods for policy evaluation, the true value of a state \(v_\pi(s)\) is estimated by averaging out the returns observed after visiting that state. We denote this estimate as \(v_n(s)\). Let \(G_t\) be the return after time step \(t\) and assume the return is bounded and the error of the estimate and the actual return has bounded variance. At each visit to the state \(s\), we can update \(v_n(s)\) by \[\begin{align*} v_{n+1}(s)=v_n(s)+\alpha_n (G_t-v_n(s)). \end{align*}\] Assume a stationary environment and let \((\alpha_n) \in (0,1]\) be decreasing and fulfil the conditions \[\begin{align*} \sum_n \alpha_n=\infty \text{ and }\sum_n \alpha_n^2<\infty. \end{align*}\] Show that the sequence of value function estimates \((v_n(s))\) converges to the true value function \(v_\pi(s)\) with probability 1.
Hint: you might find the following theorem useful. If you use it, clearly define why the assumptions of the theorem are satisfied by constructing them and rearranging the update rule for \(v_{n+1}(s)\).
Theorem 1 (Robbins-Monro). Consider the recursively defined stochastic process \[\begin{align*} x_{n+1}=x_n - \alpha_n (L(x_n) + \varepsilon_n), \end{align*}\] where \(L: \mathbb{R} \to \mathbb{R}\) has a unique root \(x_*\) such that \(L(x)(x-x_*) > 0\) for all \(x \not = x_*\), \(\varepsilon_n\) is some random stochastic noise with \(\mathbb{E}(\varepsilon_n|h_n)=0\), where \(h_n\) is the observed history until \(n\), and \(\alpha_n \in (0, 1]\) such that \(\sum_n \alpha_n=\infty\) and \(\sum_n \alpha_n^2<\infty.\) Then, \(x_n \to x_*\) with probability 1.