mlsanityData to 14 Oct 2026

Provably Efficient and Agile Randomized Q-Learning

arXiv 2506.24005 ↗First posted 30 Jun 2025cs.LGcited by 2

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

While Bayesian-based exploration often demonstrates superior empirical performance compared to bonus-based methods in model-based reinforcement learning (RL), its theoretical understanding remains limited for model-free settings. Existing provable algorithms either suffer from computational intractability or rely on stage-wise policy updates which reduce responsiveness and slow down the learning process. In this paper, we propose a novel variant of Q-learning algorithm, refereed to as RandomizedQ, which integrates sampling-based exploration with agile, step-wise, policy updates, for episodic tabular RL. We establish an widetildeO(√H5SAT) regret bound, where S is the number of states, A is the number of actions, H is the episode length, and T is the total number of episodes. In addition, we present a logarithmic regret bound under a mild positive sub-optimality condition on the optimal Q-function. Empirically, RandomizedQ exhibits outstanding performance compared to existing Q-learning variants with both bonus-based and Bayesian-based exploration on standard benchmarks.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 26 of its 38 references that are in the map. First posted on arXiv 30 Jun 2025.

Builds on

26 of 38 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling18 Jun

Other references · 25

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2016Deep Exploration via Bootstrapped DQNcited by 527
  3. 2018Is Q-learning Provably Efficient?cited by 487
  4. 2017Noisy Networks for Explorationcited by 266
  5. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  6. 2018Randomized Prior Functions for Deep Reinforcement Learningcited by 219
  7. 2024Deep Reinforcement Learning for Robotics: A Survey of Real-World Successescited by 176
  8. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  9. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  10. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  11. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  12. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
13 more
  1. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  2. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  3. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  4. 2020Q-learning with Logarithmic Regretcited by 60
  5. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  6. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 31
  7. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  8. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19
  9. 2019Efficient Model-free Reinforcement Learning in Metric Spacescited by 18
  10. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  11. 2024Q-SFT: Q-Learning for Language Models via Supervised Fine-Tuningcited by 10
  12. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  13. 2023Model-free Posterior Sampling via Learning Rate Randomizationcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Efficient Restarts in Non-Stationary Model-Free Reinforcement Learningcited by 0
  2. 2026ReversedQ: Opportunities for Faster Q-Learning in Episodic Online Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Q-learning with Posterior Sampling
  2. 2024Optimistic Q-learning for average reward and episodic reinforcement learning
  3. 2026Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding
  4. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation
  5. 2025Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design
  6. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs
  7. 2026Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation
  8. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximation