Q-learning with Posterior Sampling

2025/06/01 by Priyank Agrawal, Agrawal, Priyank, Shipra Agrawal +3
Computer Science · #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2506.00917

openalex publication_date 2025/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 O(H²√(SAT)), closely matching the known lower bound of Ω(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.

Citations

• Optimistic Q-learning for average reward and episodic reinforcement learning
• Achieving Tractable Minimax Optimal Regret in Average Reward MDPs
• Model-free Posterior Sampling via Learning Rate Randomization
• Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes
• Posterior Sampling for Deep Reinforcement Learning
• Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees
• Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning
• The Bayesian Learning Rule
• UCB Momentum Q-learning: Correcting the bias without forgetting
• Near-Optimal Randomized Exploration for Tabular Markov Decision Processes
• Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions
• Provably Efficient Q-Learning with Low Switching Cost
• Is Q-learning Provably Efficient?
• Efficient Exploration through Bayesian Deep Q-Networks
• Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning
• Learning Unknown Markov Decision Processes: A Thompson Sampling Approach
• Noisy Networks for Exploration
• Thompson Sampling for the MNL-Bandit
• Deep Exploration via Randomized Value Functions
• Minimax Regret Bounds for Reinforcement Learning
• Why is Posterior Sampling Better than Optimism for Reinforcement Learning?
• Deep Exploration via Bootstrapped DQN
• Deep Reinforcement Learning with Double Q-learning
• Generalization and Exploration via Randomized Value Functions
• Playing Atari with Deep Reinforcement Learning
• (More) Efficient Reinforcement Learning via Posterior Sampling
• Thompson Sampling: An Asymptotically Optimal Finite Time Analysis
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs

Related

• Efficient Exploration through Bayesian Deep Q-Networks
• Model-free Posterior Sampling via Learning Rate Randomization
• (More) Efficient Reinforcement Learning via Posterior Sampling
• Provably Efficient and Agile Randomized Q-Learning
• Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Need