(More) Efficient Reinforcement Learning via Posterior Sampling

Abstract

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 $\tilde{O}(\tau S\sqrt{AT})$ bound on the expected regret, where $T$ is time, $\tau$ 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.

10 pages

References in corpus (4)

• Thompson Sampling for Contextual Bandits with Linear Payoffs
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search
• Learning to Optimize Via Posterior Sampling

Cited by in corpus (78)

• Implicit Quantile Networks for Distributional Reinforcement Learning
• Bayesian Reinforcement Learning: A Survey
• Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain
• UCB Exploration via Q-Ensembles
• VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learning
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Near-optimal Reinforcement Learning in Factored MDPs
• A Bayesian Framework for Digital Twin-Based Control, Monitoring, and Data Collection in Wireless Systems
• A Tutorial on Thompson Sampling
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Personalized HeartSteps: A Reinforcement Learning Algorithm for Optimizing Physical Activity
• Cover Tree Bayesian Reinforcement Learning
• Policy Certificates: Towards Accountable Reinforcement Learning
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions
• Variational Bayesian Reinforcement Learning with Regret Bounds
• Randomized Value Functions via Multiplicative Normalizing Flows
• Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon
• Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
• Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
• ROI-Constrained Bidding via Curriculum-Guided Bayesian Reinforcement Learning
• Provably Efficient Reinforcement Learning with Aggregated States
• Bayesian model predictive control: Efficient model exploration and regret bounds using posterior sampling
• Why Generalization in RL is Difficult: Epistemic POMDPs and Implicit Partial Observability
• Assumed Density Filtering Q-learning
• MetaCURE: Meta Reinforcement Learning with Empowerment-Driven Exploration
• Tightening Exploration in Upper Confidence Reinforcement Learning
• Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning
• Long-Term Visitation Value for Deep Exploration in Sparse Reward Reinforcement Learning
• No-regret Exploration in Contextual Reinforcement Learning
• Online Learning for Unknown Partially Observable MDPs
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function
• Online Learning of Energy Consumption for Navigation of Electric Vehicles
• Temporal Difference Uncertainties as a Signal for Exploration
• Stochastic Neural Network with Kronecker Flow
• Delegative Reinforcement Learning: learning to avoid traps with a little help
• Reward Biased Maximum Likelihood Estimation for Reinforcement Learning
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Causal Markov Decision Processes: Learning Good Interventions Efficiently
• Influence-Based Multi-Agent Exploration
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting
• A Survey of Exploration Methods in Reinforcement Learning
• Reinforcement Learning, Bit by Bit
• Online Learning in Kernelized Markov Decision Processes
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
• Reinforcement Learning for Joint Optimization of Multiple Rewards
• Thompson Sampling with a Mixture Prior
• Local Differential Privacy for Regret Minimization in Reinforcement Learning
• On the Theory of Reinforcement Learning with Once-per-Episode Feedback
• Better Optimism By Bayes: Adaptive Planning with Rich Models
• Stable Reinforcement Learning with Unbounded State Space
• Unifying Ensemble Methods for Q-learning via Social Choice Theory
• Posterior sampling for reinforcement learning: worst-case regret bounds
• Temporally-Extended ε-Greedy Exploration
• Sample-Efficient Reinforcement Learning with Maximum Entropy Mellowmax Episodic Control
• Posterior Sampling for Anytime Motion Planning on Graphs with Expensive-to-Evaluate Edges
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits
• Randomised Bayesian Least-Squares Policy Iteration
• Markov Decision Process modeled with Bandits for Sequential Decision Making in Linear-flow
• Reward is enough for convex MDPs
• Markov Decision Processes with Long-Term Average Constraints
• Biomanufacturing Harvest Optimization with Small Data
• Reinforcement Learning in the Wild with Maximum Likelihood-based Model Transfer
• Improved Exploration in Factored Average-Reward MDPs
• Model-based Meta Reinforcement Learning using Graph Structured Surrogate Models
• Note on Thompson sampling for large decision problems
• Continuous Control With Ensemble Deep Deterministic Policy Gradients
• Uncertainty Quantification and Exploration for Reinforcement Learning
• Optimal Network Control in Partially-Controllable Networks
• BelMan: Bayesian Bandits on the Belief--Reward Manifold
• Near-optimal Bayesian Solution For Unknown Discrete Markov Decision Process
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Deep Reinforced Attention Regression for Partial Sketch Based Image Retrieval
• Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descent
• Angrier Birds: Bayesian reinforcement learning
• Efficient Online Decision Tree Learning with Active Feature Acquisition
• Communication Efficient Parallel Reinforcement Learning
• Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem