Markovian Foundations for Quasi-Stochastic Approximation in Two Timescales: Extended Version
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914947909287936 |
|---|---|
| author | Lauand, Caio Kalil Meyn, Sean |
| author_facet | Lauand, Caio Kalil Meyn, Sean |
| contents | Many machine learning and optimization algorithms can be cast as instances of stochastic approximation (SA). The convergence rate of these algorithms is known to be slow, with the optimal mean squared error (MSE) of order $O(n^{-1})$. In prior work it was shown that MSE bounds approaching $O(n^{-4})$ can be achieved through the framework of quasi-stochastic approximation (QSA); essentially SA with careful choice of deterministic exploration. These results are extended to two time-scale algorithms, as found in policy gradient methods of reinforcement learning and extremum seeking control. The extensions are made possible in part by a new approach to analysis, allowing for the interpretation of two timescale algorithms as instances of single timescale QSA, made possible by the theory of negative Lyapunov exponents for QSA. The general theory is illustrated with applications to extremum seeking control (ESC). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_07842 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Markovian Foundations for Quasi-Stochastic Approximation in Two Timescales: Extended Version Lauand, Caio Kalil Meyn, Sean Optimization and Control Many machine learning and optimization algorithms can be cast as instances of stochastic approximation (SA). The convergence rate of these algorithms is known to be slow, with the optimal mean squared error (MSE) of order $O(n^{-1})$. In prior work it was shown that MSE bounds approaching $O(n^{-4})$ can be achieved through the framework of quasi-stochastic approximation (QSA); essentially SA with careful choice of deterministic exploration. These results are extended to two time-scale algorithms, as found in policy gradient methods of reinforcement learning and extremum seeking control. The extensions are made possible in part by a new approach to analysis, allowing for the interpretation of two timescale algorithms as instances of single timescale QSA, made possible by the theory of negative Lyapunov exponents for QSA. The general theory is illustrated with applications to extremum seeking control (ESC). |
| title | Markovian Foundations for Quasi-Stochastic Approximation in Two Timescales: Extended Version |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.07842 |