# Provably Efficient and Agile Randomized Q-Learning

arXiv: https://arxiv.org/abs/2506.24005 · HTML: https://mlsanity.com/paper/2506.24005/

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

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 26 of 26)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Noisy Networks for Exploration](https://mlsanity.com/paper/1706.10295/) (2017)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [Deep Reinforcement Learning for Robotics: A Survey of Real-World Successes](https://mlsanity.com/paper/2408.03539/) (2024)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.10904/) (2022)
- [Regret Bounds for Information-Directed Reinforcement Learning](https://mlsanity.com/paper/2206.04640/) (2022)
- [Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/2010.12163/) (2020)
- [Efficient Model-free Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/1905.00475/) (2019)
- [Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees](https://mlsanity.com/paper/2209.14414/) (2022)
- [More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling](https://mlsanity.com/paper/2406.12241/) (2024)
- [Q-SFT: Q-Learning for Language Models via Supervised Fine-Tuning](https://mlsanity.com/paper/2411.05193/) (2024)
- [Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning](https://mlsanity.com/paper/2310.20007/) (2023)
- [Model-free Posterior Sampling via Learning Rate Randomization](https://mlsanity.com/paper/2310.18186/) (2023)

## Built on by (most cited first, 2 of 2)

- [Efficient Restarts in Non-Stationary Model-Free Reinforcement Learning](https://mlsanity.com/paper/2510.11933/) (2025)
- [ReversedQ: Opportunities for Faster Q-Learning in Episodic Online Reinforcement Learning](https://mlsanity.com/paper/2605.20592/) (2026)

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