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.
2. Policy Priors and MCMC Search
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.
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.
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