(More) Efficient Reinforcement Learning via Posterior Sampling

By Ian Osband, Daniel Russo, Benjamin Van Roy. 2013

595 citations recorded by the source corpus.

Most provably-efficient reinforcement 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 O(τS/√AT) bound on 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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

RL$^2$: Fast Reinforcement Learning via Slow Reinforcement Learning (2016, methodology): “We compare our approach with the following methods: • Random: the agent chooses an action uniformly at random for each time step; • PSRL (Strens, 2000; Osband et al., 2013): this is a direct generalization of Thompson sampling to MDPs, where at the beginning of each episode, we sample an MDP from…”
Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling (2018, background): “Thompson Sampling (Thompson, 1933) and its extension to reinforcement learning, known as Posterior Sampling, provide an elegant approach that tackles the exploration-exploitation dilemma by maintaining a posterior over models and choosing actions in proportion to the probability that they are optima”
The Uncertainty Bellman Equation and Exploration (2017, background): “Other works have suggested that a Bayesian posterior sampling approach may not suffer from these inefficiencies and can lead to performance improvements over OFU methods [34, 25].”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, methodology): “We can rewrite the regret from concentration via the Bellman operator (section 5.2 of [20]), Bounding the contribution from | w R | is relatively straightforward.”
Deep Exploration via Bootstrapped DQN (2016, methodology): “This is a natural adaptation of the Thompson sampling heuristic to RL that allows for temporally extended (or deep) exploration [21, 13].”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “Policies that perform deep exploration can learn much faster [38, 43].”
Implicit Quantile Networks for Distributional Reinforcement Learning (2018, methodology): “At this point, it is important to highlight the difference between intrinsic uncertainty , captured by the distribution over returns, and parametric uncertainty , the uncertainty over the value estimate typically associated with Bayesian approaches such as PSRL (Osband et al., 2013) and Kalman TD (G”
Behaviour Suite for Reinforcement Learning (2019, background): “[48] Ian Osband, Daniel Russo, and Benjamin Van Roy.”
Randomized Prior Functions for Deep Reinforcement Learning (2018, background): “1This heuristic is general in the sense that Thompson sampling can be theoretically justified in many of the domains where these other approaches fail [1, 48, 34, 58].”
Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variables (2019, methodology): “In classical RL, posterior sampling (Strens, 2000; Osband et al., 2013) begins with a prior distribution over MDPs, computes a posterior distribution conditioned on the experience it has seen so far, and executes the optimal policy for a sampled MDP for the duration of an episode as an efﬁcient…”
Generalization and Exploration via Randomized Value Functions (2014, background): “RLSVI bears a close connection to PSRL (Osband et al., 2013), which maintains and samples from a posterior distribution over MDPs and is a direct application of Thompson sampling to RL.”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, methodology): “On the other hand, more sophisticated strategies have mostly been limited to low dimensional MDPs.”
BBQ-Networks: Efficient Exploration in Deep Reinforcement Learning for Task-Oriented Dialogue Systems (2016, methodology): “Following Schatzmann, Thomson, and Young (2007), we represent utterances as dialog-acts, consisting of a single act and a (possibly empty) collection of (slot=value) pairs, some of which are informed while others are requested (value omitted).”
A Tutorial on Thompson Sampling (2017, background): “Subsequent papers have further developed this theory [43, 44, 45] and have studied extensions of Thompson sampling to reinforcement-learning [35, 46, 47, 48].”
Minimax Regret Bounds for Reinforcement Learning (2017, methodology): “Previous works have argue for the potential benefits of such PSRL methods over existing optimistic approaches (Osband et al., 2013; Osband & Van Roy, 2016b) but they come with guarantees on the Bayesian regret only.”
Plan Online, Learn Offline: Efficient Learning and Exploration via Model-Based Control (2018, background): “Deep exploration strategies [47] sample a value function from the posterior and use it for greedy action selection.”
Deep Exploration via Randomized Value Functions (2017, background): “Subsequent papers proposed and analyzed alternative tabular algorithms that carry out deep exploration with varying degrees of efficacy (Brafman and Tennenholtz, 2002; Auer and Ortner, 2006; Strehl et al., 2006; Jaksch et al., 2010; Osband et al., 2013; Dann and Brunskill, 2015; Azar et al., 2017).”
Offline Evaluation of Online Reinforcement Learning Algorithms (2016, methodology): “Inthissetting,theestimatesitreturnedindicated that PSRL was learning much more quickly than it would in reality.”
Near-optimal Reinforcement Learning in Factored MDPs (2014, background): “M L ] 1 5 M ar 2 Any learning algorithm over Markov decision processes (MDPs) will have worst-case regret Ω( √”
Thompson Sampling for Learning Parameterized Markov Decision Processes (2014, background): “There is little work on rigorous performance analysis of Thompson sampling schemes for reinforcement learning apart from a line of work in the Bayesian RL setting, in which the true MDP is assumed to be sampled episodically from a prior completely known to the algorithm (Osband et al., 2013; Osband ”