Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning

Abstract

Motivated by applications in reinforcement learning (RL), we study a nonlinear stochastic approximation (SA) algorithm under Markovian noise, and establish its finite-sample convergence bounds under various stepsizes. Specifically, we show that when using constant stepsize (i.e., ${\alpha }_k\equiv \alpha$), the algorithm achieves exponential fast convergence to a neighborhood (with radius $O(\alpha \log (1/\alpha ))$) around the desired limit point. When using diminishing stepsizes with appropriate decay rate, the algorithm converges with rate $O(\log (k)/k)$. Our proof is based on Lyapunov drift arguments, and to handle the Markovian noise, we exploit the fast mixing of the underlying Markov chain. To demonstrate the generality of our theoretical results on Markovian SA, we use it to derive the finite-sample bounds of the popular $Q$-learning with linear function approximation algorithm, under a condition on the behavior policy. Importantly, we do not need to make the assumption that the samples are i.i.d., and do not require an artificial projection step in the algorithm to maintain the boundedness of the iterates. Numerical simulations corroborate our theoretical results.

References in corpus (8)

• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• A Theoretical Analysis of Deep Q-Learning
• Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• Q-learning with Nearest Neighbors
• A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms
• A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints

Cited by in corpus (21)

• Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
• Finite-Time Analysis for Double Q-learning
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
• Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• Momentum Q-learning with Finite-Sample Convergence Guarantee
• Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise
• Online Robust Reinforcement Learning with Model Uncertainty
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Breaking the Deadly Triad with a Target Network
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Distributed TD(0) with Almost No Communication
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms
• Using Echo State Networks to Approximate Value Functions for Control
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• Asymptotic Theory for IV-Based Reinforcement Learning with Potential Endogeneity
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs