mlsanityData to 13 Oct 2026

UCB Momentum Q-learning: Correcting the bias without forgetting

arXiv 2103.01312 ↗First posted 1 Mar 2021stat.ML cs.LGcited by 45

Not on the map. Why?

Cited by 20 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

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(√H3SAT+ H4 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(√H3SAT) 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.

Key facts. Cited by 45 papers in the map (data through 13 Oct 2026). Builds on 17 of its 26 references that are in the map. First posted on arXiv 1 Mar 2021.

Builds on

17 of 26 references.

References · 17

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 501
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  4. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  5. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  6. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  7. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  8. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  9. 2020Adaptive Reward-Free Explorationcited by 77
  10. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  11. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  12. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 43
5 more
  1. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  2. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  3. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  4. 2020Adaptive Discretization for Model-Based Reinforcement Learningcited by 13
  5. 2020Momentum Q-learning with Finite-Sample Convergence Guaranteecited by 4

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 9; 2022: 7; 2023: 7; 2024: 7; 2025: 10; 2026: 5.

45 papers.

Sort:

By area:

  1. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 60
  2. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  3. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  4. 2023DrM: Mastering Visual Reinforcement Learning through Dormant Ratio Minimizationcited by 45
  5. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  6. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  7. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  8. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  9. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  10. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  11. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  12. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
33 more
  1. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  2. 2023Posterior Sampling for Deep Reinforcement Learningcited by 16
  3. 2024ACE : Off-Policy Actor-Critic with Causality-Aware Entropy Regularizationcited by 16
  4. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  5. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  6. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13
  7. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  8. 2023Probabilistic Inference in Reinforcement Learning Done Rightcited by 11
  9. 2021A Reduction-Based Framework for Conservative Bandits and Reinforcement Learningcited by 9
  10. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 9
  11. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  12. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  13. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  14. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  15. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  16. 2021Adaptive Multi-Goal Explorationcited by 4
  17. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  18. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 4
  19. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  20. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  21. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  22. 2021Online Sub-Sampling for Reinforcement Learning with General Function Approximationcited by 1
  23. 2025Q-learning with Posterior Samplingcited by 1
  24. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  25. 2025Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learningcited by 1
  26. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  27. 2026Near-Optimal Sample Complexity for Online Constrained MDPscited by 1
  28. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 1
  29. 2024State-free Reinforcement Learningcited by 0
  30. 2025When a Reinforcement Learning Agent Encounters Unknown Unknownscited by 0
  31. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0
  32. 2026Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPscited by 0
  33. 2026Optimal Multi-Reward Reinforcement Learningcited by 0