Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning

Abstract

We consider a general asynchronous Stochastic Approximation (SA) scheme featuring a weighted infinity-norm contractive operator, and prove a bound on its finite-time convergence rate on a single trajectory. Additionally, we specialize the result to asynchronous $Q$-learning. The resulting bound matches the sharpest available bound for synchronous $Q$-learning, and improves over previous known bounds for asynchronous $Q$-learning.

References in corpus (7)

• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Variance-reduced $Q$-learning is minimax optimal
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes

Cited by in corpus (9)

• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Is Pessimism Provably Efficient for Offline RL?
• Finite-Time Analysis for Double Q-learning
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
• Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning
• Momentum Q-learning with Finite-Sample Convergence Guarantee
• Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise
• An Adiabatic Theorem for Policy Tracking with TD-learning