In Reinforcement Learning: An Introduction by Barto and Sutton, there's the statement that by using the update rule $$Q_{n+1} \leftarrow Q_n + \alpha_n(R_n - Q_n)$$ that we only have convergence of $\{Q_n\}$ almost surely if $\sum_{i=1}^\infty \alpha_i= \infty$ and $\sum_{i=1}^\infty \alpha_i^2< \infty$, citing this as a "well-known result in stochastic approximation theory." What is this result, and why is is true? My understanding is that we can expand $$Q_{n+1} = \alpha_nR_n + (1-\alpha_n)\alpha_{n-1}R_{n-1} + (1-\alpha_n)(1-\alpha_{n-1})\alpha_{n-2}R_{n-2} + \cdots$$ but I'm not sure how to proceed from here. Do we need to assume that the $R_i$ are i.i.d.?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.