Finite-Time Theory for Momentum Q-learning

Weng，Bowen1; Xiong，Huaqing1; Zhao，Lin2; Liang，Yingbin1; Zhang，Wei3

2021

37th Conference on Uncertainty in Artificial Intelligence, UAI 2021

665-674

Existing studies indicate that momentum ideas in conventional optimization can be used to improve the performance of Q-learning algorithms. However, the finite-time analysis for momentum-based Q-learning algorithms is only available for the tabular case without function approximation. This paper analyzes a class of momentum-based Q-learning algorithms with finite-time convergence 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 approximation under Markovian sampling. In particular, we characterize a finite-time convergence rate which is provably faster than the vanilla Q-learning. This is the first finite-time analysis for momentum-based Q-learning algorithms with function approximation. For the tabular case under synchronous sampling, we also obtain a finite-time convergence rate that is slightly better than the SpeedyQ [Azar et al., 2011]. Finally, we demonstrate through various experiments that the proposed MomentumQ outperforms other momentum-based Q-learning algorithms.

其他

英语

EI

20220711617512

Approximation algorithms ; Learning algorithms ; Momentum

Artificial Intelligence:723.4 ; Machine Learning:723.4.2 ; Mathematics:921 ; Mechanics:931.1

2-s2.0-85124314296

Scopus

1.Department of Electrical and Computer Engineering,The Ohio State University,Columbus,United States
2.Department of Electrical and Computer Engineering,National University of Singapore,Singapore,Singapore
3.Department of Mechanical and Energy Engineering,Southern University of Science and Technology,Shenzhen,China

Weng，Bowen,Xiong，Huaqing,Zhao，Lin,et al. Finite-Time Theory for Momentum Q-learning[C],2021:665-674.