UCB Momentum Q-learning: Correcting the bias without forgetting

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

TL;DR

Upper Confidence Bound Momentum Q-learning (UCBMQ) is a novel reinforcement learning algorithm that introduces a momentum term to Q-learning to achieve state-of-the-art theoretical performance. It is the first algorithm to match the optimal "first-order" regret lower bound while ensuring that its "second-order" error term scales only linearly with the number of states. This effectively solves a long-standing efficiency gap in model-free reinforcement learning.

The Challenge: Bias vs. Variance in Q-Learning

In reinforcement learning (RL), an agent learns to maximize rewards by interacting with an environment, typically modeled as a Markov Decision Process (MDP). A primary metric for success is minimizing regret—the difference between the reward an optimal agent would collect and what the learning agent actually achieves.

Existing algorithms generally fall into two categories, each with distinct theoretical hurdles:

  1. Model-based algorithms: These estimate the environment's transition probabilities directly. While highly sample-efficient, their theoretical regret bounds often contain a "second-order" term that scales with the square of the number of states ($S^2$). This makes them potentially sub-optimal for environments with massive state spaces.
  2. Model-free algorithms (e.g., Q-learning): These estimate the value of actions directly without modeling transitions. However, standard Q-learning suffers from bias because it uses past, potentially inaccurate estimates to update current ones. Previous attempts to fix this bias involved "forgetting" old data using aggressive learning rates. Unfortunately, discarding data increases variance, leading to sub-optimal regret.

The authors aim to create an algorithm that enjoys the low bias of aggressive learning without the high variance of forgetting, specifically targeting a regret bound that scales linearly with $S$.

The UCBMQ Approach

The authors propose UCBMQ, which modifies the standard Q-learning update rule by incorporating a momentum term.

  • Momentum for Bias Correction: Instead of using a fast learning rate to "wash away" old biased estimates, UCBMQ retains all past samples to keep variance low. It then uses a momentum term to explicitly correct the bias introduced by those older samples.
  • Bias-Value Function: To calculate this momentum adjustment, the algorithm maintains a separate "bias-value function" for every state-action pair, tracking the bias of previous estimates.
  • Optimism (UCB): To encourage exploration, UCBMQ adds an "optimistic" bonus to the Q-values. The authors utilize a sophisticated bonus based on a Freedman-Bernstein-type inequality, allowing for a tighter fit to the problem's actual variance compared to simpler Hoeffding-based methods.

Key Insights

  • Correcting Without Forgetting: The central breakthrough is realizing that old data doesn't need to be discarded to eliminate bias. By carefully designing a momentum term, an algorithm can maintain the low variance of a large dataset while mathematically subtracting the bias.
  • Breaking the $S^2$ Curse: Model-based algorithms often hit an $S^2$ bottleneck because their transition estimates and value functions become correlated. Because UCBMQ is model-free (it doesn't explicitly estimate transition probabilities), it avoids this correlation issue, leading to a second-order term that is linear in $S$.

Key Results

The paper provides both theoretical proofs and empirical evidence to support UCBMQ's efficacy.

Theoretical Bounds

UCBMQ achieves a regret bound of $\tilde{O}(\sqrt{H^3SAT} + H^4SA)$. This matches the theoretical lower bound for the first-order term while maintaining a linear dependency on $S$ in the second-order term.

Comparison of regret upper bounds for various RL algorithms. UCBMQ achieves the optimal first-order term with a second-order term linear in S.

Empirical Performance

The algorithm was evaluated using a Grid-world environment (a 10x5 grid with noisy transitions). The goal was to reach a specific target state to receive a reward.

In these simulations, UCBMQ significantly outperformed OptQL, a previous state-of-the-art model-free algorithm. While it did not surpass model-based algorithms like UCBVI in this specific low-state simulation, it successfully demonstrated that the momentum approach effectively improves sample efficiency in model-free contexts.

Regret of UCBMQ compared to baselines. UCBMQ outperforms the previous model-free approach, OptQL, though model-based UCBVI remains highly efficient.

Limitations and Future Work

While UCBMQ represents a significant theoretical step forward, it has a few limitations:

  • Memory Footprint: Although UCBMQ updates values in a "model-free" manner, it requires $O(HS^2A)$ space to store the bias-value functions. This matches the space complexity of model-based algorithms, which could be a hurdle for extremely large state spaces.
  • Computational Complexity: The update rule is more complex than standard Q-learning, leading to a time complexity of $O(H(S+A)T)$.
  • The "Horizon" Gap: The authors conjecture that the optimal second-order term should be $H^2SA$, whereas UCBMQ currently achieves $H^4SA$. Reducing this dependency on the episode length ($H$) remains an open challenge.
  • Model-Based Linear $S$: A major open question raised by this work is whether a true model-based algorithm can be designed to achieve a second-order term that scales linearly with $S$.

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