mlsanityData to 14 Oct 2026

Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning

arXiv 1905.11425 ↗First posted 27 May 2019math.OC cs.LGcited by 67

Not on the map. Why?

Cited by 22 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Motivated by applications in reinforcement learning (RL), we study a nonlinear stochastic approximation (SA) algorithm under Markovian noise, and establish its finite-sample convergence bounds under various stepsizes. Specifically, we show that when using constant stepsize (i.e., αkequiv α), the algorithm achieves exponential fast convergence to a neighborhood (with radius O(αlog(1/α))) around the desired limit point. When using diminishing stepsizes with appropriate decay rate, the algorithm converges with rate O(log(k)/k). Our proof is based on Lyapunov drift arguments, and to handle the Markovian noise, we exploit the fast mixing of the underlying Markov chain. To demonstrate the generality of our theoretical results on Markovian SA, we use it to derive the finite-sample bounds of the popular Q-learning with linear function approximation algorithm, under a condition on the behavior policy. Importantly, we do not need to make the assumption that the samples are i.i.d., and do not require an artificial projection step in the algorithm to maintain the boundedness of the iterates. Numerical simulations corroborate our theoretical results.

Key facts. Cited by 67 papers in the map (data through 14 Oct 2026). First posted on arXiv 27 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 10; 2022: 6; 2023: 10; 2024: 12; 2025: 11; 2026: 18.

67 papers.

Sort:

By area:

  1. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  2. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  3. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 36
  4. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  5. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  6. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 29
  7. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  8. 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 24
  9. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  10. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  11. 2023Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Datacited by 20
  12. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
38 more
  1. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 17
  2. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  3. 2023Distributed TD(0) with Almost No Communicationcited by 13
  4. 2024Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learningcited by 10
  5. 2024Revisiting Step-Size Assumptions in Stochastic Approximationcited by 10
  6. 2023Convergence Rates for Localized Actor-Critic in Networked Markov Potential Gamescited by 9
  7. 2024Computing the Bias of Constant-step Stochastic Approximation with Markovian Noisecited by 9
  8. 2022Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximationcited by 8
  9. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  10. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  11. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  12. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 7
  13. 2025Nonasymptotic CLT and Error Bounds for Linear Two-Time-Scale Stochastic Approximationcited by 6
  14. 2025Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iterationcited by 6
  15. 2021A Reinforcement Learning Approach to Parameter Selection for Distributed Optimal Power Flowcited by 5
  16. 2022Data Sampling Affects the Complexity of Online SGD over Dependent Datacited by 5
  17. 2021Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Gamescited by 4
  18. 2022Does DQN Learn?cited by 4
  19. 2025Central Limit Theorems for Asynchronous Averaged Q-Learningcited by 4
  20. 2022An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithmscited by 3
  21. 2024Approximate Global Convergence of Independent Learning in Multi-Agent Systemscited by 3
  22. 2025A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regressioncited by 3
  23. 2025Auto-exploration for online reinforcement learningcited by 3
  24. 2026Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximationcited by 3
  25. 2023Controlling Federated Learning for Covertnesscited by 2
  26. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  27. 2024Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walkscited by 2
  28. 2024Regularized Q-Learning with Linear Function Approximationcited by 2
  29. 2024DASA: Delay-Adaptive Multi-Agent Stochastic Approximationcited by 2
  30. 2024Nonparametric Sparse Online Learning of the Koopman Operatorcited by 2
  31. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 2
  32. 2025A Robust widetildeO(1/√T) Rate for Unprojected TD Learning with Linear Function Approximationcited by 2
  33. 2026Q-Measure-Learning for Continuous State RL: Efficient Implementation and Convergencecited by 2
  34. 2026A Switching System Theory of Q-Learning with Linear Function Approximationcited by 2
  35. 2026A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averagingcited by 2
  36. 2023Finite-Time Analysis of Temporal Difference Learning with Experience Replaycited by 1
  37. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  38. 2026Periodic Regularized Q-Learningcited by 1

50 most cited of 67 All 67 (JSON)