# A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 56 references that are in the map.
- First posted on arXiv 29 Sep 2021.

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

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [Finite-Time Analysis and Restarting Scheme for Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/1912.10583/) (2019)
- [Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation](https://mlsanity.com/paper/2106.07472/) (2021)
- [On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost](https://mlsanity.com/paper/1907.06246/) (2019)
- [Convergence of a Stochastic Subgradient Method with Averaging for Nonsmooth Nonconvex Constrained Optimization](https://mlsanity.com/paper/1912.07580/) (2019)
- [Finite-Time Convergence Rates of Decentralized Stochastic Approximation with Applications in Multi-Agent and Multi-Task Learning](https://mlsanity.com/paper/2010.15088/) (2020)
- [Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise](https://mlsanity.com/paper/2104.01627/) (2021)
- [Two Timescale Stochastic Approximation with Controlled Markov noise and Off-policy temporal difference learning](https://mlsanity.com/paper/1503.09105/) (2015)
- [Finite-Time Performance of Distributed Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/1912.10155/) (2019)

## Built on by (most cited first, 24 of 24)

- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2205.13746/) (2022)
- [Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes](https://mlsanity.com/paper/2110.11383/) (2021)
- [Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guarantees](https://mlsanity.com/paper/2202.00048/) (2022)
- [Robust Markov Decision Processes without Model Estimation](https://mlsanity.com/paper/2302.01248/) (2023)
- [Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems](https://mlsanity.com/paper/2112.09579/) (2021)
- [Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning](https://mlsanity.com/paper/2405.09660/) (2024)
- [Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise](https://mlsanity.com/paper/2503.18391/) (2025)
- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)
- [Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexity](https://mlsanity.com/paper/2401.12764/) (2024)
- [Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications](https://mlsanity.com/paper/2410.13743/) (2024)
- [Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theorems](https://mlsanity.com/paper/2303.12981/) (2023)
- [Learning in Herding Mean Field Games: Single-Loop Algorithm with Finite-Time Convergence Analysis](https://mlsanity.com/paper/2408.04780/) (2024)
- [Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis](https://mlsanity.com/paper/2501.10806/) (2025)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)
- [Preventing Learning Stagnation in PPO by Scaling to 1 Million Parallel Environments](https://mlsanity.com/paper/2603.06009/) (2026)
- [Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks](https://mlsanity.com/paper/2401.09665/) (2024)
- [Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization](https://mlsanity.com/paper/2509.02937/) (2025)
- [Rethinking Neural Network Learning Rates: A Stackelberg Perspective](https://mlsanity.com/paper/2605.15530/) (2026)
- [Why does the two-timescale Q-learning converge to different mean field solutions? A unified convergence analysis](https://mlsanity.com/paper/2404.04357/) (2024)
- [Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2405.02456/) (2024)
- [Mission-Aligned Learning-Informed Control of Autonomous Systems: Formulation and Foundations](https://mlsanity.com/paper/2507.04356/) (2025)
- [Actor-Critic Learning for Risk-Constrained Linear Quadratic Regulation](https://mlsanity.com/paper/2510.22267/) (2025)
- [(Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulator](https://mlsanity.com/paper/2609.19712/) (2026)

## Abstract (arXiv)

We study a new two-time-scale stochastic gradient method for solving optimization problems, where the gradients are computed with the aid of an auxiliary variable under samples generated by time-varying MDPs controlled by the underlying optimization variable. These time-varying samples make gradient directions in our update biased and dependent, which can potentially lead to the divergence of the iterates. In our two-time-scale approach, one scale is to estimate the true gradient from these samples, which is then used to update the estimate of the optimal solution. While these two iterates are implemented simultaneously, the former is updated "faster" than the latter. Our first contribution is to characterize the finite-time complexity of the proposed two-time-scale stochastic gradient method. In particular, we provide explicit formulas for the convergence rates of this method under different structural assumptions, namely, strong convexity, PL condition, and general non-convexity. We apply our framework to various policy optimization problems. First, we look at the infinite-horizon average-reward MDP with finite state and action spaces and derive a convergence rate of O(k-2/5) for the online actor-critic algorithm under function approximation, which recovers the best known rate derived specifically for this problem. Second, we study the linear-quadratic regulator and show that an online actor-critic method converges with rate O(k-2/3). Third, we use the actor-critic algorithm to solve the policy optimization problem in an entropy regularized Markov decision process, where we also establish a convergence of O(k-2/3). The results we derive for both the second and third problem are novel and previously unknown in the literature. Finally, we briefly present the application of our framework to gradient-based policy evaluation algorithms in reinforcement learning.