Finite-Time Error Bounds for Biased Stochastic Approximation with Application to Q-Learning

Research output: Contribution to journalConference articlepeer-review

7 Scopus citations


Inspired by the widespread use of Q-learning algorithms in reinforcement learning (RL), this present paper studies a class of biased stochastic approximation (SA) procedures under an 'ergodic-like' assumption on the underlying stochastic noise sequence. Leveraging a multistep Lyapunov function that looks ahead to several future updates to accommodate the gradient bias, we prove a general result on the convergence of the iterates, and use it to derive finite-time bounds on the mean-square error in the case of constant stepsizes. This novel viewpoint renders the finite-time analysis of biased SA algorithms under a broad family of stochastic perturbations possible. For direct comparison with past works, we also demonstrate these bounds by applying them to Q-learning with linear function approximation, under the realistic Markov chain observation model. The resultant finite-time error bound for Q-learning is the first of its kind, in the sense that it holds: i) for the unmodified version (i.e., without making any modifications to the updates), and ii), for Markov chains starting from any initial distribution, at least one of which has to be violated for existing results to be applicable.

Original languageEnglish (US)
Pages (from-to)3015-3024
Number of pages10
JournalProceedings of Machine Learning Research
StatePublished - 2020
Externally publishedYes
Event23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020 - Virtual, Online
Duration: Aug 26 2020Aug 28 2020

Bibliographical note

Publisher Copyright:
Copyright © 2020 by the author(s)


Dive into the research topics of 'Finite-Time Error Bounds for Biased Stochastic Approximation with Application to Q-Learning'. Together they form a unique fingerprint.

Cite this