Analysis of Q-learning with Adaptation and Momentum Restart for Gradient Descent

Bowen Weng, Huaqing Xiong, Yingbin Liang, Wei Zhang

Abstract

Existing convergence analyses of Q-learning mostly focus on the vanilla stochastic gradient descent (SGD) type of updates. Despite the Adaptive Moment Estimation (Adam) has been commonly used for practical Q-learning algorithms, there has not been any convergence guarantee provided for Q-learning with such type of updates. In this paper, we first characterize the convergence rate for Q-AMSGrad, which is the Q-learning algorithm with AMSGrad update (a commonly adopted alternative of Adam for theoretical analysis). To further improve the performance, we propose to incorporate the momentum restart scheme to Q-AMSGrad, resulting in the so-called Q-AMSGradR algorithm. The convergence rate of Q-AMSGradR is also established. Our experiments on a linear quadratic regulator problem demonstrate that the two proposed Q-learning algorithms outperform the vanilla Q-learning with SGD updates. The two algorithms also exhibit significantly better performance than the DQN learning method over a batch of Atari 2600 games.

Introduction

Reinforcement Learning (RL) practitioners have long favored adaptive optimizers like Adam for training Q-learning agents due to their empirical success. However, a significant gap has existed between this practice and theoretical understanding: most convergence proofs for Q-learning rely on simpler Stochastic Gradient Descent (SGD) updates. This paper bridges that gap by providing the first non-asymptotic convergence guarantees for Q-learning using Adam-type updates, specifically AMSGrad, and introduces a novel momentum restart mechanism to further stabilize training.

The Challenge of Adaptive Q-Learning

Q-learning presents a unique challenge for optimization because it involves a "moving target." To update the value of a current state, the algorithm uses an estimate of the value of the subsequent state. This inherent instability is traditionally managed in Deep Q-Networks (DQN) through complex target networks and nested update loops.

While adaptive methods like Adam improve convergence in supervised learning, they can diverge in certain RL scenarios. AMSGrad was developed to address this by maintaining a non-decreasing second-moment estimate, providing the stability necessary for theoretical analysis. The authors address two primary issues: the lack of convergence proofs for AMSGrad-based Q-learning and the potential for adaptive momentum to replace the computationally expensive target-network fitting used in DQN.

Proposed Methods: Q-AMSGrad and Q-AMSGradR

The authors analyze two primary algorithms within the framework of linear function approximation:

  1. Q-AMSGrad: This algorithm integrates Q-learning with the AMSGrad update rule. By ensuring the learning rate does not increase unexpectedly, AMSGrad provides the stability required for a $O(1/\sqrt{T})$ convergence rate proof, matching the rates of simpler SGD-based methods.
  2. Q-AMSGradR (Restart): This variant introduces a "momentum restart" scheme. In RL, the gradient direction shifts as the policy improves, rendering historical momentum data "stale." Q-AMSGradR periodically resets the momentum ($m_t$) and second-moment ($v_t$) buffers to zero, allowing the agent to adapt more effectively to the evolving Q-function landscape.

Both algorithms utilize an alternating update style—one step of Bellman update followed by one step of parameter optimization—which is significantly simpler than the nested-loop structure of standard DQN.

Experimental Evaluation

The proposed algorithms were evaluated on two distinct environments: a Linear Quadratic Regulator (LQR) problem for theoretical validation and a suite of 23 Atari 2600 games to test deep learning performance.

Performance on Atari Benchmarks

In the Atari 2600 suite, both Q-Adam and Q-AdamR significantly outperformed the DQN baseline. On average, these adaptive methods achieved a 50% higher normalized return than DQN.

Normalized return of DQN, Q-Adam, and Q-AdamR across Atari games, showing the superior performance of adaptive methods.

A key finding was the reliability of the restart mechanism. While Q-Adam (without restarts) failed on specific tasks like Amidar and Assault, Q-AdamR remained stable across all games with notably lower variance.

Convergence in LQR

In LQR experiments, the adaptive methods demonstrated rapid convergence. Notably, Q-AdamR converged even faster than the model-based Value Iteration (DARE) solution, which is typically viewed as the performance upper bound for such problems.

Loss convergence comparison between vanilla Q-learning, Q-Adam, Q-AdamR, and the DARE baseline.

Conclusion

This work provides a critical theoretical foundation for the use of adaptive optimizers in Q-learning. By establishing convergence rates for Q-AMSGrad and introducing the momentum restart scheme in Q-AMSGradR, the authors offer a more stable and efficient alternative to traditional DQN. Future research may explore adaptive restart mechanisms that trigger based on gradient signals rather than fixed intervals, as well as extending formal non-asymptotic proofs to non-linear function approximations.

Summary updated

Abstract

Existing convergence analyses of Q-learning mostly focus on the vanilla stochastic gradient descent (SGD) type of updates. Despite the Adaptive Moment Estimation (Adam) has been commonly used for practical Q-learning algorithms, there has not been any convergence guarantee provided for Q-learning with such type of updates. In this paper, we first characterize the convergence rate for Q-AMSGrad, which is the Q-learning algorithm with AMSGrad update (a commonly adopted alternative of Adam for theoretical analysis). To further improve the performance, we propose to incorporate the momentum restart scheme to Q-AMSGrad, resulting in the so-called Q-AMSGradR algorithm. The convergence rate of Q-AMSGradR is also established. Our experiments on a linear quadratic regulator problem demonstrate that the two proposed Q-learning algorithms outperform the vanilla Q-learning with SGD updates. The two algorithms also exhibit significantly better performance than the DQN learning method over a batch of Atari 2600 games.
BibTeX
@inproceedings{weng2020analysis,
  author = {Bowen Weng and Huaqing Xiong and Yingbin Liang and Wei Zhang},
  title = {{Analysis of Q-learning with Adaptation and Momentum Restart for Gradient Descent}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=X8EeyHBwev},
}
Figure