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

2019/05/27 by Zaiwei Chen, Chen, Zaiwei, Sheng Zhang +7 · 9 citations
Computer Science · Decision Sciences · Neuroscience · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Neural dynamics and brain function #Optimization and Control (math.OC) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1905.11425

openalex publication_date 2019/05/27 · openalex created_date 2020/07/10 · openalex updated_date 2026/07/28

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., α_k≡ α), the algorithm achieves exponential fast convergence to a neighborhood (with radius O(αlog(1/α))) 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.

Citations

• A Stochastic Approximation Method
• Q-learning with Nearest Neighbors
• A Theoretical Analysis of Deep Q-Learning

Cited by

• Auto-exploration for online reinforcement learning
• Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noise
• Functional Critic Modeling for Provably Convergent Off-Policy Actor-Critic
• Central Limit Theorems for Asynchronous Averaged Q-Learning
• Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates
• Asymptotic Theory for IV-Based Reinforcement Learning with Potential Endogeneity
• Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
• Stochastic Online Feedback Optimization for Networks of Non-Compliant Agents
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model

Related

• Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem
• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise
• A Lyapunov Theory for Finite-Sample Guarantees of Markovian Stochastic Approximation
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes