A Bayesian Sampling Approach to Exploration in Reinforcement Learning

By John Asmuth, Lihong Li, Michael L. Littman, Ali Nouri, David Wingate. 2009

192 citations recorded by the source corpus.

We present a modular approach to reinforcement learning that uses a Bayesian representation of the uncertainty over models. The approach, BOSS (Best of Sampled Set), drives exploration by sampling multiple models from the posterior and selecting actions optimistically. It extends previous work by providing a rule for deciding when to re-sample and how to combine the models. We show that our algorithm achieves near-optimal reward with high probability with a sample complexity that is low relative to the speed at which the posterior distribution converges during learning. We demonstrate that BOSS performs quite favorably compared to state-of-the-art reinforcement-learning approaches and illustrate its flexibility by pairing it with a non-parametric model that generalizes across states.

Subfields: Artificial Intelligence, Reinforcement Learning, Probabilistic & Bayesian Methods

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 Reinforcement Learning

In Probabilistic & Bayesian Methods

Citations in the corpus

Surprising Negative Results for Generative Adversarial Tree Search (2018, background): “The exploration-exploitationtrade-off is extensively studied in RL literature (Kearns & Singh, 2002; Brafman & Tennenholtz, 2003; Asmuth et al., 2009).”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, neutral): “This algorithm “Optimistic PSRL” is spiritually very similar to BOSS [2] and previous work had suggested that K > 1 could lead to improved performance.”
Efficient Exploration Through Bayesian Deep Q-Networks (2018, background): “The complexity of the exploration-exploitation trade-off has been deeply investigated in RL literature [16], [3], [17].”
Learning Awareness Models (2018, methodology): “A sea of other methods have been proposed for exploration (MacKay, 1992; Ghavamzadeh et al., 2015; Asmuth et al., 2009; Gal, 2016; Stachniss et al., 2005; Plappert et al., 2017; Fu et al., 2017).”
Offline Evaluation of Online Reinforcement Learning Algorithms (2016, positive): “A convenient way to incorporate this kind of knowledge, and also simplify the choice of prior, is the relative outcomes framework (Asmuth et al. 2009).”
Bayesian Optimal Control of Smoothly Parameterized Systems (2015, background): “…to add an exploration bonus to the rewards while using the mean estimates for the transition probabilities and considers a ﬁnite horizon setting, Asmuth et al. (2009) consider discounted total rewards and a variant of posterior sampling, originally due to Thompson (1933) and ﬁrst adapted to…”
Better Optimism By Bayes: Adaptive Planning with Rich Models (2014, methodology): “Other myopic sample-based exploration strategies, such as Bayesian DP (Strens 2000) or BOSS (Asmuth et al. 2009), would suffer from similar forms of unwarranted optimism — since they also rely on sampling one or more posterior samples according to which they act greedily (see A yet more challenging…”
An Optimistic Posterior Sampling Strategy for Bayesian Reinforcement Learning (2013, methodology): “We propose a strategy based on two main assumptions: (i) a posterior distribution can be maintained over the set of all possible transition models, and (ii) one can easily sample and solve MDPs drawn according to this posterior.”
A Bayesian Approach for Learning and Planning in Partially Observable Markov Decision Processes (2011, background): “For the specific case of exploration in reinforcement learning, Asmuth et al. (2009) presented a fully Bayesian analysis of the performance of a sampling approach.”
Efﬁcient Exploration for Dialogue Policy Learning with BBQ Networks & Replay Buffer Spiking (2016, background): “While provably efﬁcient exploration strategies are known for problems with ﬁnite states/actions or problems with nice structures [Kakade, 2003, Asmuth et al., 2009, Jaksch et al., 2010, Li et al., 2011], not much is known for the general case, especially when nonlinear function approximation is…”
Convex Optimization: Algorithms and Complexity (2015, unknown): “As per other model-based Bayesian RL approaches presented above, BOSS [Asmuth et al., 2009] maintains uncertainty over the model parameters using a parametric posterior distribution and incorporates new information by updating the posterior.”
Programmation et apprentissage bayésien pour les jeux vidéo multi-joueurs, application à l'intelligence artificielle de jeux de stratégies temps-réel. (Bayesian Programming and Learning for Multi-Player Video Games, Application to RTS AI) (2012, background): “It implies making up challenging scenarii and dealing with huge sampling spaces [Asmuth et al., 2009].”
Learning and Using Models (2012, background): “BOSS on the other hand, samples k models from the model posterior distribution whenever it collects sufficient data for some part of the model.”
A Tutorial on Ultrareliable and Low-Latency Communications in 6G: Integrating Domain Knowledge Into Deep Learning (2021, methodology): “There are many sophisticated methods to balance exploitation and exploration, such as ε -greedy methods [241], optimistic initial values [68], and the Bayesian sampling approach [242].”
Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search (2012, unknown): “…Dearden’s Maze BAMCP 387.6 ± 1.5 72.9 ± 3 32.7 ± 3 965.2 ± 73 BFS3 [2] 382.2 ± 1.5 66 ± 5 10.4 ± 2 240.9 ± 46 SBOSS [5] 371.5 ± 3 59.3 ± 4 21.8 ± 2 671.3 ± 126 BEB [18] 386 ± 0 67.5 ± 3 10 ± 1 184.6 ± 35 Bayesian DP* [23] 377 ± 1 - - - Bayes VPI+MIX* [8] 326 ± 31 - - 817.6 ± 29 IEQL+* [20] 264”
Reinforcement learning with limited reinforcement: using Bayes risk for active learning in POMDPs (2008, unknown): “More recent work in Bayesian MDPs have provided a formal characterization of the sample complexity required to achieve near-optimal reward [38, 39, 40], including for cases where the learner has access to a teacher (similar to an oracle to achieve efficient uses the notion of teacher (similar to an ”
Learning and exploration in action-perception loops (2013, background): “BOSS is a state-of-the-art model-based reinforcement learning algorithm (Asmuth et al., 2009).”