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(\alphalog(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 tha

Stats

• citations23
• S2 citations—
• github stars0
• HF likes0
• heat score10.35
• arxiv keychen2019finite

Related papers

• Finite Time Analysis Of Linear Two-timescale Stochastic Approximation With Markovian Noise (2020)0.00
• Finite Sample Analysis Of Two-timescale Stochastic Approximation With Applications To Reinforcement Learning (2017)0.00
• Finite-sample Analysis Of Stochastic Approximation Using Smooth Convex Envelopes (2020)0.00
• Constant Stepsize Q-learning: Distributional Convergence, Bias And Extrapolation (2024)0.00
• Stochastic Approximation With Delayed Updates: Finite-time Rates Under Markovian Sampling (2024)0.00
• Sample Complexity Bounds For Two Timescale Value-based Reinforcement Learning Algorithms (2020)0.00
• Finite-sample Analysis For SARSA With Linear Function Approximation (2019)0.00
• Non-asymptotic Analysis Of Biased Stochastic Approximation Scheme (2019)0.00