Unifying Theme in Reinforcement Learning: Stochastic Approximation Methods

In this article, we delve into the fascinating world of stochastic approximation (SA), a powerful tool for analyzing the convergence of various algorithms. SA is based on the idea that instead of using the exact gradient of a function, we can use a noisy version of it to approximate the optimization process. By leveraging this insight, we can develop new methods for analyzing the convergence of stochastic processes, including those in reinforcement learning (RL).
One key aspect of SA is its ability to handle asynchronous updating, where only one component of a system’s state is updated at each time step. This allows us to study both "synchronous" and "asynchronous" versions of SA using a unified framework. Our focus in this article is on demystifying the mathematical concepts underlying SA and explaining them in simple terms.
The article begins by introducing the basic concepts of SA, including its ODE approach and martingale method. We then dive deeper into the ODE approach, which involves showing that, as the step sizes αt → 0, the stochastic sample paths of (1) "approach" the (deterministic) solution trajectories of the associated ODE ˙θ = f (θ). Book-length treatments of this approach can be found in [16, 17, 2, 7].
Next, we explore the martingale method, which directly analyzes the stochastic process and draws conclusions using the theory of supermartingales. We highlight how this approach is applicable to "asynchronous" SA algorithms, where only one component of θt is updated at each time t, and the rest remain the same.
To further illustrate these concepts, we provide examples from reinforcement learning, where SA can act as a common thread to bind together many algorithms. We also mention popular books on RL that mention SA only in passing, highlighting the need for a more comprehensive treatment of SA in this context.
Throughout the article, we strive to strike a balance between simplicity and thoroughness, capturing the essence of SA without oversimplifying it. We hope that our summary will help readers gain a better understanding of this powerful tool and its applications in various fields.