An analytic solution to discrete Bayesian reinforcement learning

By Pascal Poupart, Nikos A. Vlassis, Jesse Hoey, Kevin Regan. 2006

343 citations recorded by the source corpus.

Reinforcement learning (RL) was originally proposed as a framework to allow agents to learn in an online fashion as they interact with their environment. Existing RL algorithms come short of achieving this goal because the amount of exploration required is often too costly and/or too time consuming for online learning. As a result, RL is mostly used for offline learning in simulated environments. We propose a new algorithm, called BEETLE, for effective online learning that is computationally efficient while minimizing the amount of exploration. We take a Bayesian model-based approach, framing RL as a partially observable Markov decision process. Our two main contributions are the analytical derivation that the optimal value function is the upper envelope of a set of multivariate polynomials, and an efficient point-based value iteration algorithm that exploits this simple parameterization.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Curiosity-Driven Exploration by Self-Supervised Prediction (2017, background): “L G ] 1 5 M ay 2 01 7 et al., 2012; Poupart et al., 2006) or, 2) encourage the agent to perform actions that reduce the error/uncertainty in the agent’s ability to predict the consequence of its own actions (i.e. its knowledge about the environment) (Houthooft et al., 2016; Mohamed & Rezende, 2015;…”
EPOpt: Learning Robust Neural Network Policies Using Model Ensembles (2016, background): “Application of this idea in its full general form is difficult, and requires either restrictive assumptions like finite MDPs (Poupart et al., 2006), gaussian dynamics (Ross et al., 2008), or task specific innovations.”
Large-Scale Study of Curiosity-Driven Learning (2018, background): “Examples of intrinsic reward include “curiosity” [11, 22, 27, 35, 40] which uses prediction error as reward signal, and “visitation counts” [3, 20, 24, 30] which discourages the agent from revisiting the same states.”
Efficient Exploration in Reinforcement Learning (2017, methodology): “This includes Factored MDPs [4], Metric MDPs [2], Continuous MDPs[1], and MDPs with a Bayesian prior [6].”
Temporal Difference Bayesian Model Averaging: A Bayesian Perspective on Adapting Lambda (2010, background): “In addition to GPTD, there are numerous other Bayesian RL approaches, e.g. (Dearden et al., 1998; 1999; Wang et al., 2005; Poupart et al., 2006).”
Neuroevolutionary reinforcement learning for generalized control of simulated helicopters (2011, background): “Though an agent can in principle always compute a Bayes-optimal strategy for exploration [63, 95], doing so is typically computationally intractable.”
Convex Optimization: Algorithms and Complexity (2015, unknown): “The method was applied successfully to solve simulated dialogue management problems; computational scalability was achieved via a number of structural constraints, including the parameter tying method proposed by [Poupart et al., 2006].”
Bayesian Policy Search for Multi-Agent Role Discovery (2010, unknown): “Previous work on Bayesian RL has considered priors on the domain dynamics in model-based RL (Dearden, Friedman , and Andre 1999; Strens 2000; Poupart et al. 2006; Wilson et al. 2007) and priors on expected returns, action-value functions, and policy gradients in model-free RL (Dearden, Friedman,…”
A Bayesian Sampling Approach to Exploration in Reinforcement Learning (2009, background): “A state-of-the-art belief-lookahead approach is BEETLE (Poupart et al., 2006), which plans in the continuous belief space deﬁned by the agent’s uncertainty.”
A unifying framework for computational reinforcement learning theory (2009, methodology): “In reinforcement learning, an environment is often modeled as a Markov decision process or MDP [Puterman 1994], where the history of the environment can be summarized in a sufficient statistic called state. MDPs are natural abstraction of many real-life problems such as those investigated by Puterma”
Variance-Based Rewards for Approximate Bayesian Reinforcement Learning (2010, methodology): “The BEETLE algorithm (Poupart et al., 2006) directly approximates full Bayesian planning by compressing the information state space.”
What Can Learned Intrinsic Rewards Capture? (2019, unknown): “…et al., 2007; Gordon & Ahissar, 2011; Mirolli & Baldassarre, 2013; Pathak et al., 2017), surprise (Itti & Baldi, 2006), weight change (Linke et al., 2019), and state-visitation counts (Sutton, 1990; Poupart et al., 2006; Strehl & Littman, 2008; Bellemare et al., 2016; Ostrovski et al., 2017).”
Planning to Explore via Self-Supervised World Models (2020, background): “…it is efﬁciently addressed with exploration bonuses based on state visitation counts (Strehl & Littman, 2008; Jaksch et al., 2010) or fully Bayesian approaches (Duff & Barto, 2002; Poupart et al., 2006), however these approaches are hard to generalize to high-dimensional states, such as images.”