Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 3015-3024 |
Number of pages | 10 |
Journal | Proceedings of Machine Learning Research |
Volume | 108 |
State | Published - 2020 |
Externally published | Yes |
Event | 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020 - Virtual, Online Duration: Aug 26 2020 → Aug 28 2020 |
Bibliographical note
Publisher Copyright:Copyright © 2020 by the author(s)