Momentum Q-learning with Finite-Sample Convergence Guarantee

Abstract

Existing studies indicate that momentum ideas in conventional optimization can be used to improve the performance of Q-learning algorithms. However, the finite-sample analysis for momentum-based Q-learning algorithms is only available for the tabular case without function approximations. This paper analyzes a class of momentum-based Q-learning algorithms with finite-sample guarantee. Specifically, we propose the MomentumQ algorithm, which integrates the Nesterov's and Polyak's momentum schemes, and generalizes the existing momentum-based Q-learning algorithms. For the infinite state-action space case, we establish the convergence guarantee for MomentumQ with linear function approximations and Markovian sampling. In particular, we characterize the finite-sample convergence rate which is provably faster than the vanilla Q-learning. This is the first finite-sample analysis for momentum-based Q-learning algorithms with function approximations. For the tabular case under synchronous sampling, we also obtain a finite-sample convergence rate that is slightly better than the SpeedyQ \citep{azar2011speedy} when choosing a special family of step sizes. Finally, we demonstrate through various experiments that the proposed MomentumQ outperforms other momentum-based Q-learning algorithms.

References in corpus (12)

• Playing Atari with Deep Reinforcement Learning
• A Theoretical Analysis of Deep Q-Learning
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
• Stochastic approximation with cone-contractive operators: Sharp ${\ell }_{\infty }$-bounds for $Q$-learning
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithms
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• Momentum in Reinforcement Learning
• Periodic Q-Learning

Cited by in corpus (4)

• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Finite-Time Analysis for Double Q-learning
• UCB Momentum Q-learning: Correcting the bias without forgetting
• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs