Bayesian Policy Search with Policy Priors

David Wingate, Noah D. Goodman, Daniel M. Roy, Leslie Pack Kaelbling, Joshua B. TenenbaumIJCAI 2011 · OpenReview

Abstract

We consider the problem of learning to act in partially observable, continuous-state-and-action worlds where we have abstract prior knowledge about the structure of the optimal policy in the form of a distribution over policies. Using ideas from planning-as-inference reductions and Bayesian unsupervised learning, we cast Markov Chain Monte Carlo as a stochastic, hill-climbing policy search algorithm. Importantly, this algorithm's search bias is directly tied to the prior and its MCMC proposal kernels, which means we can draw on the full Bayesian toolbox to express the search bias, including nonparametric priors and structured, recursive processes like grammars over action sequences. Furthermore, we can reason about uncertainty in the search bias itself by constructing a hierarchical prior and reasoning about latent variables that determine the abstract structure of the policy. This yields an adaptive search algorithm--our algorithm learns to learn a structured policy efficiently. We show how inference over the latent variables in these policy priors enables intra- and intertask transfer of abstract knowledge. We demonstrate the flexibility of this approach by learning meta search biases, by constructing a nonparametric finite state controller to model memory, by discovering motor primitives using a simple grammar over primitive actions, and by combining all three.

Introduction

Reinforcement learning (RL) in environments characterized by partial observability and continuous action spaces presents a significant challenge. In these settings, the policy search space is vast, and traditional gradient-based or value-iteration methods often falter due to the lack of a clear optimization landscape, particularly when policies require discrete logic or structured action sequences.

A key hurdle is the integration of abstract prior knowledge. For instance, in a navigation task, an agent might benefit from knowing that "moving in straight lines" is generally effective, even without knowing the specific environment layout. This paper proposes a framework to incorporate such "common sense" search biases by reframing policy search as a Bayesian inference problem.

Methodology: Policy Search as Inference

The authors introduce a planning-as-inference reduction that leverages the strengths of Bayesian modeling for RL.

1. Probabilistic Mapping

The value of a policy $V(\pi)$ is mapped to a probability distribution. A likelihood is defined as $p(R=1|\pi) \propto \exp(V(\pi))$, where $R=1$ signifies the achievement of a reward.

A prior $p(\pi)$ encodes structural beliefs about the policy, such as simplicity or the reuse of specific action sequences. Instead of standard optimization, the framework uses Markov Chain Monte Carlo (MCMC), specifically Metropolis-Hastings, to sample from the posterior $p(\pi | R=1)$. This effectively turns policy search into a stochastic hill-climbing process where the search bias is explicitly defined by the prior.

3. Hierarchical and Nonparametric Models

To enable adaptive learning, the authors employ:

  • Hierarchical Priors: By placing a prior on the prior itself (via latent variables $\theta$), the agent can adapt its search bias based on experience—a process of "learning to learn."
  • Nonparametric Models: Dirichlet Processes (DP) and Hierarchical Dirichlet Processes (HDP) allow the agent to learn an appropriately sized Finite State Controller (FSC) for memory and discover an unknown number of "motor primitives" (reusable action sequences).

Experimental Evaluation

The approach was tested across three simulated environments: a Simple Maze for testing hierarchical priors, a Memory Maze requiring internal state, and a high-dimensional Snake Robot Maze.

Performance comparison in a simple maze showing how a learned hierarchical prior matches the performance of a hand-tuned 'North bias' prior.

Key Insights

The Blessing of Abstraction

Contrary to the intuition that hierarchical complexity hinders learning, this work demonstrates a "blessing of abstraction." Learning at a higher level (e.g., discovering that "wiggling" is a useful primitive) simplifies the lower-level search space, making complex tasks more tractable.

Search Bias as a Prior

The paper establishes a mathematical equivalence between search heuristics and Bayesian priors. This allows the use of the "Bayesian toolbox"—including grammars and nonparametrics—to design sophisticated search biases.

Comparison of policy values and search efficiency with and without learned options (motor primitives) in the Memory Maze.

Results and Discussion

In the Simple Maze, the hierarchical agent ("Learned bias") rapidly matched the performance of an agent with a hand-tuned "perfect" prior, demonstrating effective transfer of abstract knowledge. In the Memory Maze, the use of motor primitives (options) was crucial; agents using these primitives found the goal even after shaping rewards were removed, whereas those without them failed.

For the Snake Robot, the most complex model (FSC with DP-shared primitives) was the only one to solve the maze reliably. It showed a characteristic "elbow" in performance, where the discovery of abstract structure led to a rapid improvement in policy quality. While promising, the MCMC-based search is computationally intensive, and future work will focus on more efficient inference engines.

Summary updated

Abstract

We consider the problem of learning to act in partially observable, continuous-state-and-action worlds where we have abstract prior knowledge about the structure of the optimal policy in the form of a distribution over policies. Using ideas from planning-as-inference reductions and Bayesian unsupervised learning, we cast Markov Chain Monte Carlo as a stochastic, hill-climbing policy search algorithm. Importantly, this algorithm's search bias is directly tied to the prior and its MCMC proposal kernels, which means we can draw on the full Bayesian toolbox to express the search bias, including nonparametric priors and structured, recursive processes like grammars over action sequences. Furthermore, we can reason about uncertainty in the search bias itself by constructing a hierarchical prior and reasoning about latent variables that determine the abstract structure of the policy. This yields an adaptive search algorithm--our algorithm learns to learn a structured policy efficiently. We show how inference over the latent variables in these policy priors enables intra- and intertask transfer of abstract knowledge. We demonstrate the flexibility of this approach by learning meta search biases, by constructing a nonparametric finite state controller to model memory, by discovering motor primitives using a simple grammar over primitive actions, and by combining all three.
BibTeX
@inproceedings{wingate2011bayesian,
  author = {David Wingate and Noah D. Goodman and Daniel M. Roy and Leslie Pack Kaelbling and Joshua B. Tenenbaum},
  title = {{Bayesian Policy Search with Policy Priors}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=rk7yZmG_Wr},
}
Figure