Finite-time theory for momentum Q-learning

Bowen Weng, Huaqing Xiong, Lin Zhao, Yingbin Liang, Wei ZhangUAI 2021 · OpenReview

Abstract

While momentum-based optimization is a staple in deep learning, its theoretical application to Reinforcement Learning (RL) has largely been confined to tabular settings. This paper introduces MomentumQ, a generalized algorithm integrating Nesterov’s and Polyak’s momentum schemes. We provide the first finite-time convergence analysis for momentum-based Q-learning with linear function approximation under Markovian sampling. Our results demonstrate that MomentumQ achieves a provably faster convergence rate than vanilla Q-learning and outperforms existing accelerated methods in empirical benchmarks.

Introduction

Q-learning remains a fundamental algorithm in RL, yet its convergence speed often limits its practical utility in complex environments. In convex optimization, momentum methods like Nesterov’s Accelerated Gradient are renowned for accelerating convergence. However, translating these benefits to RL is non-trivial due to the stochastic nature of Bellman updates and the bias introduced by sequential (Markovian) data collection. Previous theoretical work on accelerated Q-learning was restricted to tabular representations and i.i.d. sampling, leaving a significant gap between theory and the function approximation methods used in practice.

The MomentumQ Algorithm

MomentumQ addresses these challenges by blending two classical momentum concepts:

  1. Nesterov’s Momentum: Utilizes the difference between consecutive Bellman operator applications to refine the gradient estimate.
  2. Polyak’s Momentum (Heavy-ball): Leverages historical iteration data to stabilize updates and mitigate the "overshoot" common in purely Nesterov-based methods like SpeedyQ.

A key innovation is the introduction of a hyperparameter $m$, which provides flexibility in the learning rate schedule, allowing for better tuning than previous fixed-rate accelerated algorithms.

Theoretical Contributions

The core of this work is the rigorous finite-time analysis of MomentumQ in two primary settings:

Linear Function Approximation

We establish a convergence rate of $O(\log T / \sqrt{T})$ under Markovian sampling. This is particularly significant as it accounts for the inherent bias in RL trajectories, where the current state depends on the previous action. We developed a novel lemma to bound this non-zero bias, providing a solid theoretical foundation for momentum in large-scale RL.

Tabular Case

Under synchronous sampling, MomentumQ achieves a convergence rate of $\tilde{O}(\frac{\sqrt{(T-m-1) \log n}}{(1-\gamma)^2 T})$. This rate is order-wisely superior to the $O(1/\sqrt{T})$ rate of standard SpeedyQ, establishing MomentumQ as the new theoretical benchmark for accelerated tabular Q-learning.

Experimental Evaluation

We evaluated MomentumQ on the FrozenLake environment across various scales (4x4, 8x8, and 128x128).

Empirical Return vs. Steps for i.i.d. and Markovian sampling.

As shown in the empirical return plots above, MomentumQ demonstrates superior performance under both i.i.d. and realistic Markovian sampling conditions. The algorithm reaches higher return levels faster than vanilla Q-learning, regardless of whether constant or diminishing stepsizes are employed.

Loss curves for FrozenLake-4x4 and 8x8 comparing MomentumQ with baselines.

In tabular comparisons, MomentumQ effectively smooths the initial performance spikes (overshoots) seen in SpeedyQ. By integrating Polyak’s momentum, it maintains a more stable descent toward the optimal Q-function, resulting in lower final loss and reduced variance compared to Nesterov Stochastic Approximation (NeSA).

Conclusion and Future Work

MomentumQ bridges the gap between momentum-based optimization theory and practical RL with function approximation. While we provide strong guarantees for linear models, extending this finite-time analysis to non-linear function approximators like deep neural networks remains an open challenge. Additionally, proving the boundedness of the Q-function iterates without external assumptions is a priority for future research, potentially utilizing the ODE method to characterize the system's stability.

Summary updated

Abstract

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., NIPS 2011). Finally, we demonstrate through various experiments that the proposed MomentumQ outperforms other momentum-based Q-learning algorithms.
BibTeX
@inproceedings{weng2021finite,
  author = {Bowen Weng and Huaqing Xiong and Lin Zhao and Yingbin Liang and Wei Zhang},
  title = {{Finite-time theory for momentum Q-learning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=AWP0s7kHHW},
}
Figure