Model based Bayesian Exploration

Richard Dearden, Nir Friedman, David AndreUAI 1999

TL;DR

This paper introduces a Bayesian approach to model-based reinforcement learning, allowing agents to explicitly represent and reason about their uncertainty in the environment's dynamics. By leveraging this uncertainty, the agent can make more informed decisions about exploration, balancing the potential gains of discovering new information against the cost of suboptimal actions, leading to more efficient learning.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents aim to learn optimal policies in dynamic environments, often by balancing exploration (trying new actions to gain information) and exploitation (using known good actions). A key challenge, especially in model-based RL where agents learn a model of the environment, is how to effectively use the agent's uncertainty about this model to guide exploration. Traditional model-based methods often rely on point estimates of the environment's dynamics, ignoring this crucial uncertainty. This paper addresses this gap by proposing a Bayesian framework that explicitly models this uncertainty, enabling more intelligent exploration strategies.

Methods

The core of the paper is the development of a Bayesian approach to model-based reinforcement learning. Instead of maintaining a single point estimate for the environment's transition and reward models, the authors propose maintaining a posterior distribution over possible models. This is achieved by using Dirichlet or sparse-multinomial priors and updating them with experience tuples (state, action, reward, next state) using Bayes' rule.

To leverage this posterior distribution for decision-making, the paper focuses on estimating Q-value distributions. Several methods are proposed:

  • Naive Sampling: This involves sampling multiple MDPs from the posterior distribution, solving each to obtain Q-values, and then using these samples to estimate the Q-value distribution.
  • Importance Sampling: To avoid recomputing Q-values for every new experience, this method re-weights existing samples to reflect the updated belief state. This is efficient because the Q-value distributions for the sampled MDPs are already computed.
  • Repair Sampling: This approach updates sampled MDPs by re-sampling parameters and then using prioritized sweeping to locally update the Q-values affected by the model change. This is presented as a computationally less intensive alternative to global sampling.
  • Global Sampling with Repair: This combines the idea of sampling MDPs with prioritized sweeping to update Q-values.

The paper also discusses Generalization and Smoothing techniques (Gaussian approximation and Kernel estimation) to represent the Q-value distributions more compactly from samples, and how to compute the Value of Perfect Information (VPI) from these generalized distributions.

Datasets

The paper evaluates its algorithms on two newly introduced benchmark domains: a "trap" domain with 18 states and a "maze" domain with 56 states. Both are four-action maze environments where the agent must collect a flag and deliver it to a goal, with penalties for entering trap states.

Key Insights and Ideas

  • Explicitly modeling uncertainty is key for exploration: The paper strongly advocates for moving beyond point estimates of environment models. Representing uncertainty as a probability distribution over models allows for a principled way to quantify the potential benefits of exploration.
  • Bayesian belief states for MDPs: The authors demonstrate how to maintain a Bayesian posterior distribution over possible MDPs, effectively creating a "belief state" that summarizes the agent's knowledge and uncertainty.
  • Value of Information for model-based RL: Adapting the decision-theoretic concept of Value of Information (VPI) to the model-based setting allows the agent to quantify the expected improvement in future decision quality from learning more about specific model parameters or Q-values.
  • Sampling-based Q-value estimation: Since exact computation of Q-value distributions from a posterior over models is intractable, the paper proposes several sampling-based methods (naive, importance, repair) to approximate these distributions.
  • Generalization improves representation: Using techniques like Kernel estimation to smooth and generalize from sampled Q-values can lead to better representations of the true Q-value distribution, especially early in learning.

Key Results

The experimental results on the "trap" and "maze" domains show that the proposed Bayesian model-based exploration methods generally outperform standard prioritized sweeping.

  • Trap Domain: Bayesian methods are more cautious, exploring less in the trap state once its negative value is suspected, leading to better performance.
  • Maze Domain: Global sampling with repair and importance sampling show better performance than prioritized sweeping early in learning, exploring more widely and avoiding traps more effectively.
  • Smoothing Effects: Kernel estimation, when used for smoothing Q-value distributions, significantly improves performance, enabling the agent to find optimal policies more reliably than methods with no smoothing or Gaussian approximation.
  • Computational Trade-offs: Global sampling is computationally intensive but performs well. Importance sampling is faster but converges later. Repair sampling offers a good balance between performance and computational cost.

Limitations and Future Work

  • Computational Cost: While the paper introduces methods to manage computational cost (e.g., importance sampling, repair sampling), global sampling remains computationally demanding.
  • Myopic Exploration: The current approach uses a myopic approximation to the value of information, meaning it considers only the immediate expected gain. The authors suggest that a more challenging future direction is to deal with the "actual value of information" by formulating an MDP over belief states, which would require approximations due to its large state space.
  • Scalability: The authors plan to conduct experiments on larger domains to assess the scalability of their methods.
  • Compact Model Representations: Future work includes applying the Bayesian approach to more compact model representations, such as dynamic Bayesian networks, and to problems with continuous state spaces.
  • Local Sampling: The paper describes a "Local Sampling" approach but notes that its effectiveness is still under investigation.

Summary updated

BibTeX
@inproceedings{dearden1999model,
  author = {Richard Dearden and Nir Friedman and David Andre},
  title = {{Model based Bayesian Exploration}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1999},
}
Figure