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 show 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

In the field of Reinforcement Learning (RL), Q-learning serves as a foundational algorithm. While its mathematical roots are grounded in simple Stochastic Gradient Descent (SGD), modern practical applications almost exclusively utilize Adam, an adaptive optimizer that excels at handling noisy gradients. This creates two significant gaps in the current literature:

  1. The Theory Gap: Most convergence proofs for Q-learning assume SGD updates. Non-asymptotic convergence guarantees for Q-learning using Adam-type updates have been largely absent.
  2. The Stability Gap: Q-learning is notoriously unstable. Standard Deep Q-Networks (DQN) attempt to mitigate this using complex mechanisms like "target networks" and "experience replay." This research explores whether a simpler, alternating update rule—enhanced by superior optimization techniques—can achieve comparable or superior stability.

Proposed Methodology

The authors bridge the gap between theory and practice by analyzing and proposing two primary algorithms that utilize an alternating update (one step of Bellman update followed by one step of parameter fitting) rather than heavy nested loops.

Q-AMSGrad

The authors adapt AMSGrad—a variant of Adam that ensures the learning rate does not increase unexpectedly—to the Q-learning framework. They provide a formal proof that this algorithm converges at a rate of $O(1/\sqrt{T})$ under linear function approximation.

Q-AMSGradR (Momentum Restart)

Momentum-based optimizers like Adam rely on historical gradient information. In RL, the "target" being learned changes over time; if the optimizer retains too much "memory" of early, incorrect gradient directions, it can lead to instability. The authors propose a Momentum Restart scheme where the optimizer's moving averages of gradients are periodically wiped clean. This "forgetting" mechanism acts as a critical stabilizer.

Experimental Evaluation

The researchers evaluated their algorithms across two distinct domains:

  1. Linear Quadratic Regulator (LQR): A classic control theory problem used to validate theoretical convergence under linear function approximation.
  2. Atari 2600 Games: A suite of 23 games (including Asterix and Seaquest) used to test the algorithms in high-dimensional environments using deep neural networks.

Key Results and Insights

Superior Convergence in Control Tasks

In LQR experiments, Q-AdamR demonstrated exceptional efficiency. It converged faster than vanilla Q-learning and even surpassed the model-based Value Iteration (DARE) solution, which is typically considered the performance upper bound for such problems.

Figure 2: Loss reduction over steps in the LQR task. Q-AdamR (red) converges significantly faster than vanilla Q-learning and the DARE baseline.

Performance Gains in Deep RL

On the Atari 2600 suite, Q-Adam and Q-AdamR outperformed the standard DQN baseline by an average of 50%. While standard Q-Adam (without restarts) failed on specific games due to instability, the Restart version (Q-AdamR) succeeded in every task, demonstrating much lower variance and higher consistency.

Figure 1: Normalized return across training steps for Atari games. Q-Adam and Q-AdamR show higher returns and better stability compared to DQN.

Conclusion and Future Work

This paper provides the first non-asymptotic convergence rate for Adam-type Q-learning, proving it reaches the global optimum under standard assumptions. The results suggest that sophisticated optimization (AMSGradR) can replace some of the architectural complexity (like nested loops) found in algorithms like DQN.

Future work remains in extending these theoretical proofs beyond linear function approximation to the non-linear/neural network case. Additionally, while fixed restart periods ($r$) proved effective, developing an adaptive restart mechanism that triggers based on real-time instability signals could further optimize performance.

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 show 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