Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2109.03445 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912577061126144 |
|---|---|
| author | Karandikar, Rajeeva L. Vidyasagar, M. |
| author_facet | Karandikar, Rajeeva L. Vidyasagar, M. |
| contents | We begin by briefly surveying some results on the convergence of the Stochastic Gradient Descent (SGD) Method, proved in a companion paper by the present authors. These results are based on viewing SGD as a version of Stochastic Approximation (SA). Ever since its introduction in the classic paper of Robbins and Monro in 1951, SA has become a standard tool for finding a solution of an equation of the form $f(θ) = 0$, when only noisy measurements of $f(\cdot)$ are available. In most situations, \textit{every component} of the putative solution $θ_t$ is updated at each step $t$. In some applications in Reinforcement Learning (RL), \textit{only one component} of $θ_t$ is updated at each $t$. This is known as \textbf{asynchronous} SA. In this paper, we study \textbf{Block Asynchronous SA (BASA)}, in which, at each step $t$, \textit{some but not necessarily all} components of $θ_t$ are updated. The theory presented here embraces both conventional (synchronous) SA as well as asynchronous SA, and all in-between possibilities. We provide sufficient conditions for the convergence of BASA, and also prove bounds on the \textit{rate} of convergence of $θ_t$ to the solution. For the case of conventional SGD, these results reduce to those proved in our companion paper. Then we apply these results to the problem of finding a fixed point of a map with only noisy measurements. This problem arises frequently in RL. We prove sufficient conditions for convergence as well as estimates for the rate of convergence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2109_03445 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Convergence of Batch Asynchronous Stochastic Approximation With Applications to Reinforcement Learning Karandikar, Rajeeva L. Vidyasagar, M. Machine Learning Artificial Intelligence Systems and Control Probability 62L20, 60G17, 93D05 We begin by briefly surveying some results on the convergence of the Stochastic Gradient Descent (SGD) Method, proved in a companion paper by the present authors. These results are based on viewing SGD as a version of Stochastic Approximation (SA). Ever since its introduction in the classic paper of Robbins and Monro in 1951, SA has become a standard tool for finding a solution of an equation of the form $f(θ) = 0$, when only noisy measurements of $f(\cdot)$ are available. In most situations, \textit{every component} of the putative solution $θ_t$ is updated at each step $t$. In some applications in Reinforcement Learning (RL), \textit{only one component} of $θ_t$ is updated at each $t$. This is known as \textbf{asynchronous} SA. In this paper, we study \textbf{Block Asynchronous SA (BASA)}, in which, at each step $t$, \textit{some but not necessarily all} components of $θ_t$ are updated. The theory presented here embraces both conventional (synchronous) SA as well as asynchronous SA, and all in-between possibilities. We provide sufficient conditions for the convergence of BASA, and also prove bounds on the \textit{rate} of convergence of $θ_t$ to the solution. For the case of conventional SGD, these results reduce to those proved in our companion paper. Then we apply these results to the problem of finding a fixed point of a map with only noisy measurements. This problem arises frequently in RL. We prove sufficient conditions for convergence as well as estimates for the rate of convergence. |
| title | Convergence of Batch Asynchronous Stochastic Approximation With Applications to Reinforcement Learning |
| topic | Machine Learning Artificial Intelligence Systems and Control Probability 62L20, 60G17, 93D05 |
| url | https://arxiv.org/abs/2109.03445 |