Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning

Abstract

We consider the dynamics of a linear stochastic approximation algorithm driven by Markovian noise, and derive finite-time bounds on the moments of the error, i.e., deviation of the output of the algorithm from the equilibrium point of an associated ordinary differential equation (ODE). We obtain finite-time bounds on the mean-square error in the case of constant step-size algorithms by considering the drift of an appropriately chosen Lyapunov function. The Lyapunov function can be interpreted either in terms of Stein's method to obtain bounds on steady-state performance or in terms of Lyapunov stability theory for linear ODEs. We also provide a comprehensive treatment of the moments of the square of the 2-norm of the approximation error. Our analysis yields the following results: (i) for a given step-size, we show that the lower-order moments can be made small as a function of the step-size and can be upper-bounded by the moments of a Gaussian random variable; (ii) we show that the higher-order moments beyond a threshold may be infinite in steady-state; and (iii) we characterize the number of samples needed for the finite-time bounds to be of the same order as the steady-state bounds. As a by-product of our analysis, we also solve the open problem of obtaining finite-time bounds for the performance of temporal difference learning algorithms with linear function approximation and a constant step-size, without requiring a projection step or an i.i.d. noise assumption.

Fixed a few minor typos and added a reference

References in corpus (1)

• Finite Sample Analyses for TD(0) with Function Approximation

Cited by in corpus (18)

• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent Advances
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
• Zap Q-Learning With Nonlinear Function Approximation
• Instance-dependent ${\ell }_{\infty }$-bounds for policy evaluation in tabular reinforcement learning
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms
• Target-Based Temporal Difference Learning
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis
• System Identification via Meta-Learning in Linear Time-Varying Environments
• Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization