Bayesian Policy Search for Stochastic Domains

David Tolpin, Yuan Zhou, Hongseok Yang

TL;DR

This paper tackles the challenge of learning optimal policies for agents operating in uncertain environments (stochastic domains) by framing policy search as a Bayesian inference problem. They introduce a novel adaptation of the Lightweight Metropolis-Hastings (LMH) algorithm, called Stochastic LMH, which allows for more robust and general inference in these complex probabilistic models, outperforming existing methods on benchmark tasks.

What Problem Does This Paper Address?

In many real-world scenarios, agents (like robots or AI systems) need to make decisions in environments where outcomes are not perfectly predictable. These are known as "stochastic domains." Traditional approaches to teaching these agents how to act optimally (policy search) often struggle with this uncertainty. Previous work has explored using probabilistic programming languages to model these problems, but often relied on specific inference algorithms that were tied to the model structure or required complex gradient computations. Furthermore, handling nested probabilistic structures, common in these domains, posed a significant challenge for existing inference techniques. This paper aims to bridge this gap by providing a more general and robust Bayesian framework for policy search in stochastic domains, specifically addressing the complexities of nested probabilistic models.

Methods

The core contribution of this paper is framing policy search in stochastic domains as a Bayesian inference problem, encoded using nested probabilistic programs. They propose a novel inference algorithm called Stochastic Lightweight Metropolis-Hastings (Stochastic LMH). This algorithm is an adaptation of the existing LMH method, specifically designed to handle stochastic choices within the probabilistic program.

Key methodological aspects include:

  • Bayesian Inference: Instead of just optimizing policy parameters, the paper treats policy learning as inferring a posterior distribution over these parameters, reflecting uncertainty.
  • Nested Probabilistic Programs: The problem is modeled using probabilistic programs that can have nested structures, allowing for more expressive representations of complex stochastic environments.
  • Flattening Nested Conditioning: They show how certain forms of nested conditioning can be "flattened," enabling the use of more standard inference techniques like importance sampling.
  • Stochastic LMH: This is the main algorithmic innovation. It's a Markov Chain Monte Carlo (MCMC) method that adapts LMH to handle stochastic choices within the model. The key idea is to treat these stochastic choices as "random variables" that can be updated alongside the policy parameters, allowing for more efficient exploration of the posterior distribution. This adaptation is achieved by accepting updates to stochastic choices with probability 1, simplifying the acceptance ratio.

Datasets

The paper evaluates their proposed method on two case studies previously introduced in the literature:

  • Canadian Traveller Problem (CTP): A graph traversal problem where edges can be missing at random.
  • RockSample POMDP: A problem where an agent navigates a grid to collect "good" rocks while avoiding "bad" ones, with uncertain sensing capabilities.

The authors implemented their versions of these probabilistic programs and the inference algorithm in the probabilistic programming language Anglican.

Key Insights and Ideas

  • Bayesian approach is crucial for policy inference: The paper emphasizes that a Bayesian treatment of policy inference is essential, especially in domains like the Canadian Traveller Problem, where prior knowledge about likely directions can significantly improve learning.
  • Nested conditioning is natural but challenging for inference: While nested probabilistic programs offer a powerful way to model stochastic domains, they pose significant inference challenges.
  • Stochastic LMH offers a more general and robust inference solution: The proposed Stochastic LMH algorithm provides a scalable and more general alternative to existing methods, particularly for models with nested conditioning, without requiring gradient computations.
  • Simpler inference can yield comparable results: Despite using a simpler inference algorithm compared to some prior work, the proposed method achieves policies of similar quality on benchmark tasks.

Key Results

The paper demonstrates that their Stochastic LMH algorithm, applied to the Canadian Traveller Problem and RockSample POMDP, learns policies of comparable quality to those found by existing methods.

  • Canadian Traveller Problem: Figure 1 shows that their inferred policies achieve mean travel distances that are significantly better than random agents and approach the performance of a clairvoyant agent (one with perfect knowledge). The performance improves as the temperature parameter in their inference process is decreased.
  • RockSample POMDP: Figure 2 illustrates that their inferred policies achieve higher expected rewards across various problem sizes and temperatures, outperforming random policies and approaching optimal performance.

The numerical results are reported to be similar to those reported in prior work [11].

Limitations and Future Work

  • Limitations of Importance Sampling: The paper acknowledges that while their method allows for flattening of nested conditioning and the use of importance sampling, this technique's performance degrades exponentially with the dimensionality of the probability space. This is a significant limitation for policies with many parameters.
  • Future Work - Gradient-Based Variants: The authors suggest that their Stochastic LMH adaptation can be extended to gradient-based MCMC variants when gradient information is available, potentially leading to even faster inference.
  • Broader Applicability: They believe their approach is applicable to a wider class of probabilistic programs with nested conditioning, not just those related to policy search.
  • Prior Knowledge Exploitation: The discussion highlights the potential for incorporating more sophisticated priors, beyond simple uniform ones, to further improve policy search efficiency, especially in deterministic domains.

Summary updated

Abstract

AI planning can be cast as inference in probabilistic models, and probabilistic programming was shown to be capable of policy search in partially observable domains. Prior work introduces policy search through Markov chain Monte Carlo in deterministic domains, as well as adapts black-box variational inference to stochastic domains, however not in the strictly Bayesian sense. In this work, we cast policy search in stochastic domains as a Bayesian inference problem and provide a scheme for encoding such problems as nested probabilistic programs. We argue that probabilistic programs for policy search in stochastic domains should involve nested conditioning, and provide an adaption of Lightweight Metropolis-Hastings (LMH) for robust inference in such programs. We apply the proposed scheme to stochastic domains and show that policies of similar quality are learned, despite a simpler and more general inference algorithm. We believe that the proposed variant of LMH is novel and applicable to a wider class of probabilistic programs with nested conditioning.
BibTeX
@misc{tolpin2020bayesian,
  author = {David Tolpin and Yuan Zhou and Hongseok Yang},
  title = {{Bayesian Policy Search for Stochastic Domains}},
  year = {2020},
  eprint = {2010.00284},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.00284},
}

Loading related content...

Figure