UCB Momentum Q-learning: Correcting the bias without forgetting

Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, Michal Valko

Abstract

We propose UCBMQ, Upper Confidence Bound Momentum Q-learning, a new algorithm for reinforcement learning in tabular and possibly stage-dependent, episodic Markov decision process. UCBMQ is based on Q-learning where we add a momentum term and rely on the principle of optimism in face of uncertainty to deal with exploration. Our new technical ingredient of UCBMQ is the use of momentum to correct the bias that Q-learning suffers while, at the same time, limiting the impact it has on the second-order term of the regret. For UCBMQ, we are able to guarantee a regret of at most $O(\sqrt{H^3SAT}+ H^4 S A )$ where $H$ is the length of an episode, $S$ the number of states, $A$ the number of actions, $T$ the number of episodes and ignoring terms in poly-$\log(SAHT)$. Notably, UCBMQ is the first algorithm that simultaneously matches the lower bound of $\Omega(\sqrt{H^3SAT})$ for large enough $T$ and has a second-order term (with respect to the horizon $T$) that scales only linearly with the number of states $S$.

Introduction

In Reinforcement Learning (RL), an agent seeks to maximize rewards in an unknown environment, typically modeled as a Markov Decision Process (MDP). Performance is measured by regret: the cumulative difference between the reward an optimal agent would receive and the reward the learning agent actually collects.

Historically, a gap has existed between model-based and model-free algorithms. Model-based algorithms are sample-efficient but suffer from a "correlation" issue that causes their secondary error terms to scale quadratically with the number of states ($S^2$). Conversely, model-free algorithms like Q-learning avoid this $S^2$ dependency but suffer from significant bias. Previous attempts to mitigate this bias often involved "aggressive" learning rates that discarded old data, leading to high variance and sub-optimal performance over long horizons ($H$). UCBMQ (Upper Confidence Bound Momentum Q-learning) is designed to bridge this gap, achieving optimal regret while maintaining linear scaling with respect to the state space.

Methodology

The core innovation of UCBMQ is the introduction of a momentum term to the standard Q-learning update rule.

In standard Q-learning, updates move the value estimate ($Q$) toward a new target using a learning rate $\alpha$. UCBMQ modifies this by using a slow learning rate (approximately $1/n$) to preserve historical data and minimize variance. To address the resulting bias, it incorporates a momentum term that calculates and subtracts the bias inherited from previous, less accurate estimates. This is achieved by maintaining a "bias-value function" for every state-action pair, allowing the algorithm to correct its trajectory in real-time without discarding samples.

Furthermore, UCBMQ employs Bernstein-type bonuses. These statistical tools provide tight confidence intervals, ensuring the agent explores the environment optimally by following the principle of optimism in the face of uncertainty.

Theoretical and Empirical Results

UCBMQ provides a significant theoretical advancement by being the first algorithm to simultaneously match the lower bound of $\Omega(\sqrt{H^3SAT})$ and ensure the second-order regret term scales linearly with $S$. As shown in the comparison below, previous state-of-the-art methods like UCBVI or EULER exhibit $S^2$ or $S^{3/2}$ dependencies in their upper bounds.

Table 1: Comparison of regret upper bounds for various RL algorithms in the non-stationary case.

Empirical Validation

The authors evaluated UCBMQ in a $10 \times 5$ Grid-World environment with non-stationary transitions and a noise factor of $\epsilon = 0.15$. The agent's goal was to reach a specific coordinate to receive a reward. In these simulations, UCBMQ significantly outperformed OptQL, the previous leading model-free approach. While model-based methods like UCBVI may converge faster in small-scale environments due to intensive planning, UCBMQ's linear scaling makes it theoretically superior for larger state spaces.

Figure 1: Cumulative regret comparison in a Grid-World environment. UCBMQ outperforms other model-free approaches like OptQL.

Discussion and Future Work

While UCBMQ achieves linear scaling in $S$, it currently requires $O(HS^2A)$ space complexity to track the bias-value function, similar to model-based methods. Additionally, its second-order term has an $H^4$ dependence, which is slightly higher than the $H^3$ seen in some model-based counterparts. Future research may focus on reducing this horizon dependence to $H^2$ or exploring whether model-based algorithms can be adapted to achieve similar linear scaling in $S$ without the associated correlation issues.

Summary updated

Abstract

We propose UCBMQ, Upper Confidence Bound Momentum Q-learning, a new algorithm for reinforcement learning in tabular and possibly stage-dependent, episodic Markov decision process. UCBMQ is based on Q-learning where we add a momentum term and rely on the principle of optimism in face of uncertainty to deal with exploration. Our new technical ingredient of UCBMQ is the use of momentum to correct the bias that Q-learning suffers while, at the same time, limiting the impact it has on the second-order term of the regret. For UCBMQ, we are able to guarantee a regret of at most $O(\sqrt{H^3SAT}+ H^4 S A )$ where $H$ is the length of an episode, $S$ the number of states, $A$ the number of actions, $T$ the number of episodes and ignoring terms in poly-$\log(SAHT)$. Notably, UCBMQ is the first algorithm that simultaneously matches the lower bound of $\Omega(\sqrt{H^3SAT})$ for large enough $T$ and has a second-order term (with respect to the horizon $T$) that scales only linearly with the number of states $S$.
BibTeX
@inproceedings{menard2021ucb,
  author = {Pierre Ménard and Omar Darwiche Domingues and Xuedong Shang and Michal Valko},
  title = {{UCB Momentum Q-learning: Correcting the bias without forgetting}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=UPwvbpxzoEw},
}
Figure