# Markovian Foundations for Quasi-Stochastic Approximation in Two Timescales: Extended Version

arXiv: https://arxiv.org/abs/2409.07842 · HTML: https://mlsanity.com/paper/2409.07842/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 7 of its 39 references that are in the map.
- First posted on arXiv 12 Sep 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 7 of 7)

- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Anticorrelated Noise Injection for Improved Generalization](https://mlsanity.com/paper/2202.02831/) (2022)
- [The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2110.14427/) (2021)
- [Optimization Algorithms as Robust Feedback Controllers](https://mlsanity.com/paper/2103.11329/) (2021)
- [The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning](https://mlsanity.com/paper/2309.02944/) (2023)
- [Online Optimization as a Feedback Controller: Stability and Tracking](https://mlsanity.com/paper/1805.09877/) (2018)
- [Markovian Foundations for Quasi-Stochastic Approximation with Applications to Extremum Seeking Control](https://mlsanity.com/paper/2207.06371/) (2022)

## Abstract (arXiv)

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).