mlsanityData to 14 Oct 2026

Q-learning with Posterior Sampling

arXiv 2506.00917 ↗First posted 1 Jun 2025cs.LGcited by 1

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

Abstract (arXiv)

Bayesian posterior sampling techniques have demonstrated superior empirical performance in many exploration-exploitation settings. However, their theoretical analysis remains a challenge, especially in complex settings like reinforcement learning. In this paper, we introduce Q-Learning with Posterior Sampling (PSQL), a simple Q-learning-based algorithm that uses Gaussian posteriors on Q-values for exploration, akin to the popular Thompson Sampling algorithm in the multi-armed bandit setting. We show that in the tabular episodic MDP setting, PSQL achieves a regret bound of tilde O(H2√SAT), closely matching the known lower bound of Omega(H√SAT). Here, S, A denote the number of states and actions in the underlying Markov Decision Process (MDP), and T=KH with K being the number of episodes and H being the planning horizon. Our work provides several new technical insights into the core challenges in combining posterior sampling with dynamic programming and TD-learning-based RL algorithms, along with novel ideas for resolving those difficulties. We hope this will form a starting point for analyzing this efficient and important algorithmic technique in even more complex RL settings.

Key facts. Cited by 1 paper 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 33 of its 47 references that are in the map. First posted on arXiv 1 Jun 2025.

Builds on

33 of 47 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Optimistic Q-learning for average reward and episodic reinforcement learning18 Jul

Other references · 32

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,745
  3. 2016Deep Exploration via Bootstrapped DQNcited by 527
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2017Noisy Networks for Explorationcited by 266
  7. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  8. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  9. 2017Deep Exploration via Randomized Value Functionscited by 156
  10. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  11. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  12. 2014Generalization and Exploration via Randomized Value Functionscited by 112
20 more
  1. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  2. 2021The Bayesian Learning Rulecited by 99
  3. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  4. 2018Efficient Exploration through Bayesian Deep Q-Networkscited by 67
  5. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  6. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  7. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  8. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  9. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
  10. 2017Thompson Sampling for the MNL-Banditcited by 35
  11. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 32
  12. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 31
  13. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  14. 2020Model-based Reinforcement Learning for Continuous Control with Posterior Samplingcited by 21
  15. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19
  16. 2023Posterior Sampling for Deep Reinforcement Learningcited by 16
  17. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 15
  18. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 15
  19. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  20. 2023Model-free Posterior Sampling via Learning Rate Randomizationcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentumcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learning
  2. 2025Provably Efficient and Agile Randomized Q-Learning
  3. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximation
  4. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  5. 2026ReversedQ: Opportunities for Faster Q-Learning in Episodic Online Reinforcement Learning
  6. 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces
  7. 2026Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding
  8. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes