Data to 7 Oct 2026

(More) Efficient Reinforcement Learning via Posterior Sampling

arXiv 1306.0940 ↗First posted 4 Jun 2013stat.ML cs.LGcited by 233

Not on the map. Why?

Abstract (arXiv)

Most provably-efficient learning algorithms introduce optimism about poorly-understood states and actions to encourage exploration. We study an alternative approach for efficient exploration, posterior sampling for reinforcement learning (PSRL). This algorithm proceeds in repeated episodes of known duration. At the start of each episode, PSRL updates a prior distribution over Markov decision processes and takes one sample from this posterior. PSRL then follows the policy that is optimal for this sample during the episode. The algorithm is conceptually simple, computationally efficient and allows an agent to encode prior knowledge in a natural way. We establish an tildeO(τ S √AT) bound on the expected regret, where T is time, τ is the episode length and S and A are the cardinalities of the state and action spaces. This bound is one of the first for an algorithm not based on optimism, and close to the state of the art for any reinforcement learning algorithm. We show through simulation that PSRL significantly outperforms existing algorithms with similar regret bounds.

Key facts. Cited by 233 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Jun 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 39; 2022: 37; 2023: 55; 2024: 33; 2025: 39; 2026: 29.

233 papers.

Sort:

By area:

2023Supervised Pretraining Can Learn In-Context Reinforcement Learningcited by 137
2021Why Generalization in RL is Difficult: Epistemic POMDPs and Implicit Partial Observabilitycited by 102
2021Recent Advances in Reinforcement Learning in Financecited by 102
2021Reward is enough for convex MDPscited by 82
2025Outcome-based Exploration for LLM Reasoningcited by 79
2021A Survey of Exploration Methods in Reinforcement Learningcited by 68
2024Self-Exploring Language Models: Active Preference Elicitation for Online Alignmentcited by 63
2021Reinforcement Learning, Bit by Bitcited by 59
2021Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domaincited by 57
2022Offline RL Policies Should be Trained to be Adaptivecited by 52
2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46

38 more

2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 42
2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
2024EVOLvE: Evaluating and Optimizing LLMs For In-Context Explorationcited by 33
2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
2023Approximate Thompson Sampling via Epistemic Neural Networkscited by 31
2023Thompson sampling for improved exploration in GFlowNetscited by 31
2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
2023On the Importance of Exploration for Generalization in Reinforcement Learningcited by 30
2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
2023Emergence of In-Context Reinforcement Learning from Noise Distillationcited by 26
2023PECAN: Leveraging Policy Ensemble for Context-Aware Zero-Shot Human-AI Coordinationcited by 25
2021Information Directed Reward Learning for Reinforcement Learningcited by 24
2021MURAL: Meta-Learning Uncertainty-Aware Rewards for Outcome-Driven Reinforcement Learningcited by 24
2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
2022An Analysis of Ensemble Samplingcited by 23
2022GFlowOut: Dropout with Generative Flow Networkscited by 22
2023Causal Reinforcement Learning: A Surveycited by 22
2023Efficient Exploration in Continuous-time Model-based Reinforcement Learningcited by 21
2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
2021Exploration-exploitation trade-off for continuous-time episodic reinforcement learning with linear-convex modelscited by 18
2022A Bayesian Framework for Digital Twin-Based Control, Monitoring, and Data Collection in Wireless Systemscited by 18
2021Online Learning for Unknown Partially Observable MDPscited by 17
2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
2021Model-based Meta Reinforcement Learning using Graph Structured Surrogate Modelscited by 16
2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
2022Grounding Aleatoric Uncertainty for Unsupervised Environment Designcited by 16
2023Posterior Sampling for Deep Reinforcement Learningcited by 16
2021Thompson Sampling with a Mixture Priorcited by 15
2023Model-Based Uncertainty in Value Functionscited by 15

50 most cited of 233 All 233 (JSON)