Momentum Q-learning with Finite-Sample Convergence Guarantee
  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.
