# Concentration bounds for two time scale stochastic approximation

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2018.

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

- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities](https://mlsanity.com/paper/2305.17568/) (2023)
- [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)
- [Finite-Time Error Bounds for Greedy-GQ](https://mlsanity.com/paper/2209.02555/) (2022)
- [Regularized Q-Learning with Linear Function Approximation](https://mlsanity.com/paper/2401.15196/) (2024)
- [A dynamic view of some anomalous phenomena in SGD](https://mlsanity.com/paper/2505.01751/) (2025)
- [Finite-Time Error Bounds for Distributed Linear Stochastic Approximation](https://mlsanity.com/paper/2111.12665/) (2021)

## Abstract (arXiv)

Viewing a two time scale stochastic approximation scheme as a noisy discretization of a singularly perturbed differential equation, we obtain a concentration bound for its iterates that captures its behavior with quantifiable high probability. This uses Alekseev's nonlinear variation of constants formula and a martingale concentration inequality and extends the corresponding results for single time scale stochastic approximation.