mlsanityData to 14 Oct 2026

Minimax-Optimality of Posterior Sampling for Reinforcement Learning

arXiv 2609.33246 ↗First posted 27 Sep 2026cs.LG stat.MLcited by 0

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

Abstract (arXiv)

Posterior sampling for reinforcement learning (PSRL) is one of the simplest and most effective exploration methods, but a basic question has remained open: does unmodified PSRL achieve minimax regret without structural assumptions on the prior? We answer yes. Exact vanilla PSRL is minimax optimal in leading-order Bayesian regret under arbitrary correlated priors. The difficulty is that a posterior-sampled transition model is coupled with its own continuation value. We overcome this with a common empirical transition reference that isolates the resulting value mismatch and a Bellman-based variance argument that controls it without an extra leading-order state-space factor. For finite-horizon, time-inhomogeneous tabular MDPs with unknown stochastic rewards, this yields the minimax widetildeO(√SAH3K) regret rate under arbitrary joint priors over rewards and transitions. The same proof principle gives the minimax widetildeO(d√H3K) rate for linear-mixture MDPs under arbitrary joint parameter priors.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 25 of its 41 references that are in the map. First posted on arXiv 27 Sep 2026.

Builds on

25 of 41 references.

Closest ancestors · 3

Same direction, newest first

  1. 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces9 Mar
  2. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes23 Oct
  3. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximation17 Mar

Other references · 22

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  3. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  4. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  5. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  6. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  7. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  8. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  9. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  10. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  11. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  12. 2019Information-Theoretic Confidence Bounds for Reinforcement Learningcited by 51
10 more
  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  2. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  3. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 31
  4. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  5. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  6. 2020Model-based Reinforcement Learning for Continuous Control with Posterior Samplingcited by 21
  7. 2021Thompson Sampling with a Mixture Priorcited by 16
  8. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  9. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  10. 2025Best Policy Learning from Trajectory Preference Feedbackcited by 5

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Q-learning with Posterior Sampling
  2. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  3. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learning
  4. 2024Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality
  5. 2024Thompson Sampling for Infinite-Horizon Discounted Decision Processes
  6. 2024Horizon-Free Regret for Linear Markov Decision Processes
  7. 2025Sample-efficient and Scalable Exploration in Continuous-Time RL
  8. 2026Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence