# Concentration of Contractive Stochastic Approximation and Reinforcement Learning

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 45 references that are in the map.
- First posted on arXiv 27 Jun 2021.

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

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness](https://mlsanity.com/paper/2003.10973/) (2020)
- [A Concentration Bound for Stochastic Approximation via Alekseev's Formula](https://mlsanity.com/paper/1506.08657/) (2015)
- [Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform sampling](https://mlsanity.com/paper/1306.2557/) (2013)
- [A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation](https://mlsanity.com/paper/1909.04299/) (2019)

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

- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Reinforcement Learning in Non-Markovian Environments](https://mlsanity.com/paper/2211.01595/) (2022)
- [A Concentration Bound for TD(0) with Function Approximation](https://mlsanity.com/paper/2312.10424/) (2023)
- [Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2405.14285/) (2024)
- [Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise](https://mlsanity.com/paper/2503.18391/) (2025)
- [Full Gradient Deep Reinforcement Learning for Average-Reward Criterion](https://mlsanity.com/paper/2304.03729/) (2023)
- [O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2504.19375/) (2025)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging](https://mlsanity.com/paper/2505.21796/) (2025)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (2025)
- [Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis](https://mlsanity.com/paper/2501.10806/) (2025)
- [Solving Stochastic Fixed-Point Equations with High Probability](https://mlsanity.com/paper/2607.09097/) (2026)
- [Equilibrium Bandits: Learning Optimal Equilibria of Unknown Dynamics](https://mlsanity.com/paper/2302.13653/) (2023)
- [Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains](https://mlsanity.com/paper/2602.16274/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [A Concentration Bound for LSPE(λ)](https://mlsanity.com/paper/2111.02644/) (2021)
- [Finite-Time Accuracy of Temporal-Difference Learning Under Schur-Stable Recursions](https://mlsanity.com/paper/2204.10479/) (2022)
- [Concentration bounds for SSP Q-learning for average cost MDPs](https://mlsanity.com/paper/2206.03328/) (2022)
- [A Concentration Bound for Distributed Stochastic Approximation](https://mlsanity.com/paper/2210.04253/) (2022)
- [On the Optimality of Tracking Fisher Information in Adaptive Testing with Stochastic Binary Responses](https://mlsanity.com/paper/2510.07862/) (2025)

## Abstract (arXiv)

Using a martingale concentration inequality, concentration bounds `from time n0 on' are derived for stochastic approximation algorithms with contractive maps and both martingale difference and Markov noises. These are applied to reinforcement learning algorithms, in particular to asynchronous Q-learning and TD(0).