mlsanityData to 14 Oct 2026

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

arXiv 2409.07842 ↗First posted 12 Sep 2024math.OCcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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

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.

Builds on

7 of 39 references.

References · 7

  1. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
  2. 2022Anticorrelated Noise Injection for Improved Generalizationcited by 42
  3. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 32
  4. 2021Optimization Algorithms as Robust Feedback Controllerscited by 9
  5. 2023The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learningcited by 7
  6. 2018Online Optimization as a Feedback Controller: Stability and Trackingcited by 5
  7. 2022Markovian Foundations for Quasi-Stochastic Approximation with Applications to Extremum Seeking Controlcited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes
  2. 2026Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning
  3. 2025Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise
  4. 2024The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise
  5. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework
  6. 2025Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis
  7. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications
  8. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise