Efficient Bayes-Adaptive Reinforcement Learning using Sample-Based Search

By Arthur Guez, David Silver, Peter S. Dayan. 2012

183 citations recorded by the source corpus.

Bayesian model-based reinforcement learning is a formally elegant approach to learning optimal behaviour under model uncertainty, trading off exploration and exploitation in an ideal way. Unfortunately, finding the resulting Bayes-optimal policies is notoriously taxing, since the search space becomes enormous. In this paper we introduce a tractable, sample-based method for approximate Bayes-optimal planning which exploits Monte-Carlo tree search. Our approach outperformed prior Bayesian model-based RL algorithms by a significant margin on several well-known benchmark problems - because it avoids expensive applications of Bayes rule within the search tree by lazily sampling models from the current beliefs. We illustrate the advantages of our approach by showing it working in an infinite state space domain which is qualitatively out of reach of almost all previous work in Bayesian exploration.

Subfields: Artificial Intelligence

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

Citations in the corpus

The Uncertainty Bellman Equation and Exploration (2017, background): “However this approach can be computationally intractable for even very small problems [9] while direct computational approximations can fail spectacularly badly [22].”
Deep Exploration via Bootstrapped DQN (2016, background): “However, the exact solution is intractable even for very simple systems[8].”
DARLA: Improving Zero-Shot Transfer in Reinforcement Learning (2017, background): “…source and target domain representations by utilising observation and reward signals from both domains (Tzeng et al., 2016; Daftry et al., 2016; Parisotto et al., 2015; Guez et al., 2012; Talvitie & Singh, 2007; Niekum et al., 2013; Gupta et al., 2017; Finn et al., 2017; Rajendran et al., 2017).”
Count-Based Exploration with Neural Density Models (2017, background): “From a theoretical perspective, exploration is now well-understood (e.g. Strehl & Littman, 2008; Jaksch et al., 2010; Osband et al., 2016), and Bayesian methods have been successfully demonstrated in a number of settings (Deisenroth & Rasmussen, 2011; Guez et al., 2012).”
(More) Efficient Reinforcement Learning via Posterior Sampling (2013, background): “Second, the presence of an explicit prior allows an agent to incorporate known environment structure in a natural way.”
Compress and Control (2014, background): “Noteworthy recent examples include the work of Doshi-Velez (2009), Walsh, Goschin, and Littman (2010), Veness et al. (2010), Veness et al. (2011), Asmuth and Littman (2011), Guez, Silver, and Dayan (2012), Hamilton, Fard, and Pineau (2013) and Tziortziotis, Dimitrakakis, and Blekas (2014).”
DORA The Explorer: Directed Outreaching Reinforcement Action-Selection (2018, methodology): “Counter-based methods are widely used both in practice and in theory (Kolter & Ng, 2009; Strehl & Littman, 2008; Guez et al., 2012; Busoniu et al., 2008).”
Toward an Integration of Deep Learning and Neuroscience (2016, methodology): “Adaptive sampling methods are also known in reinforcement learning that can achieve optimal Bayesian exploration of Markov Decision Process environments (Sun et al., 2011; Guez et al., 2012).”
Active Reinforcement Learning with Monte-Carlo Tree Search (2018, methodology): “BAMCP also uses root sampling and lazy sampling to improve efficiency (Guez et al., 2012).”
Strategic Object Oriented Reinforcement Learning (2018, methodology): “BAMCP will have similar challenges but suffers further in this domain because the true domain is deterministic.”
Hidden Parameter Markov Decision Processes: A Semiparametric Regression Approach for Discovering Latent Task Parametrizations (2013, background): “However, solving POMDPs in high-dimensional, continuous state spaces remains challenging, despite advances in POMDP planning [4, 12, 6], including situations with mixed-observability [13].”
Offline Meta Reinforcement Learning - Identifiability Challenges and Effective Data Collection Strategies (2021, result): “This result is closely related to the discussion in [14, 26], here applied to our particular setting.”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, methodology): “Monte-Carlo tree search approaches have been developed also recently, such as in [10, 66].”
Exploration in Deep Reinforcement Learning: A Survey (2022, methodology): “[120] guess of a prior Policy learning Uncertainty Dearden Maze: 965.”
Efficient exploration with Double Uncertain Value Networks (2017, methodology): “Guez et al. (2012) explicitly plans ahead using Monte Carlo Tree Search over uncertain transition dynamics models.”
Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models (2015, methodology): “Methods based on Monte-Carlo search can also scale gracefully to complex domains [20], and indeed previous work has applied such techniques to the task of playing Atari games from screen images [21].”