# A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2019.

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

- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022)
- [On Rademacher Complexity-based Generalization Bounds for Deep Learning](https://mlsanity.com/paper/2208.04284/) (2022)
- [A Concentration Bound for TD(0) with Function Approximation](https://mlsanity.com/paper/2312.10424/) (2023)
- [Generalization Error Bounds on Deep Learning with Markov Datasets](https://mlsanity.com/paper/2201.11059/) (2021)
- [Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity](https://mlsanity.com/paper/2103.16377/) (2021)
- [Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity](https://mlsanity.com/paper/2103.13147/) (2021)
- [Finite-Time Error Bounds for Distributed Linear Stochastic Approximation](https://mlsanity.com/paper/2111.12665/) (2021)
- [A primal-dual perspective for distributed TD-learning](https://mlsanity.com/paper/2310.00638/) (2023)
- [A Concentration Bound for LSPE(λ)](https://mlsanity.com/paper/2111.02644/) (2021)

## Abstract (arXiv)

Motivated by the widespread use of temporal-difference (TD-) and Q-learning algorithms in reinforcement learning, this paper studies a class of biased stochastic approximation (SA) procedures under a mild "ergodic-like" assumption on the underlying stochastic noise sequence. Building upon a carefully designed multistep Lyapunov function that looks ahead to several future updates to accommodate the stochastic perturbations (for control of the gradient bias), we prove a general result on the convergence of the iterates, and use it to derive non-asymptotic bounds on the mean-square error in the case of constant stepsizes. This novel looking-ahead viewpoint renders finite-time analysis of biased SA algorithms under a large family of stochastic perturbations possible. For direct comparison with existing contributions, we also demonstrate these bounds by applying them to TD- and Q-learning with linear function approximation, under the practical Markov chain observation model. The resultant finite-time error bound for both the TD- as well as the Q-learning algorithms is the first of its kind, in the sense that it holds i) for the unmodified versions (i.e., without making any modifications to the parameter updates) using even nonlinear function approximators; as well as for Markov chains ii) under general mixing conditions and iii) starting from any initial distribution, at least one of which has to be violated for existing results to be applicable.