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

Abstract

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.

arXiv comment28 Pages

References in corpus (11)

• An Analysis of Reinforcement Learning with Function Approximation
• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Lyapunov Theory for Discrete Time Systems
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Lyapunov Criterion for Stochastic Systems and Its Applications in Distributed Computation
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
• On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulator

Cited by in corpus (11)

• Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
• Reanalysis of Variance Reduced Temporal Difference Learning
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation
• Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity
• Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
• Distributed TD(0) with Almost No Communication
• Finite-Time Error Bounds for Distributed Linear Stochastic Approximation
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis
• On Convergence of Gradient Expected Sarsa($\lambda$)
• A priori guarantees of finite-time convergence for Deep Neural Networks