Bayes-Adaptive Simulation-based Search with Value Function Approximation

Arthur Guez, Nicolas Heess, David Silver, Peter Dayan

The Challenge of Model Uncertainty in RL

In Reinforcement Learning (RL), an agent often faces a "model uncertainty" problem: it doesn't know exactly how the environment will react to its actions. The gold standard for solving this is Bayes-Adaptive (BA) planning, which treats the agent's "belief" about the world as part of the state. This allows the agent to mathematically calculate the value of "exploring" to gain information.

However, BA planning suffers from the "curse of history." Standard algorithms (like BAMCP) build a search tree where every unique sequence of events is a separate node. In continuous worlds, an agent almost never sees the exact same sequence twice. Consequently, the tree grows exponentially, and the agent fails to realize that two slightly different histories might lead to the same conclusion. This makes traditional Bayesian RL nearly impossible to use for tasks like robotics or complex navigation.

To address this, the authors introduce BAFA (Bayes-Adaptive planning with Function Approximation), a method that allows RL agents to plan effectively even when they don't know the rules of their environment. By combining simulation-based search with value function approximation, BAFA enables agents to generalize across similar "beliefs," allowing Bayesian RL to scale to complex, continuous state spaces.

Introducing BAFA

BAFA replaces the rigid, exponentially growing search tree with a flexible Value Function Approximator.

Key components of the methodology include:

  • Value Function Approximation: Instead of storing a value for every node in a tree, BAFA uses a parametric model: $Q(h, s, a; W) = z^U(h)^T W \phi(s, a)$. This formula allows the agent to generalize; if it learns something about one history ($h$), it can apply that knowledge to similar histories.
  • History Features ($z^U(h)$): To turn a messy history of events into a mathematical vector, the authors use a set of "particles" (hypothetical models of the world). The features are essentially the "importance weights" of these particles given the history. This maps complex beliefs into a finite-dimensional space, bypassing the need for "sufficient statistics" which are often impossible to find for complex models.
  • Root Sampling: Updating a Bayesian belief at every single step of a simulation is computationally crushing. To keep simulations fast, BAFA uses root sampling: at the start of a simulation, it picks one possible model of the world and sticks with it for the duration of that "thought experiment." The paper provides a new proof showing this is mathematically valid even in continuous spaces.
  • Incremental Updates: During the search, the agent uses standard RL techniques (like Monte-Carlo control) to update the weights ($W$) of its value function on the fly.

Experimental Results

The authors evaluated BAFA on three distinct simulated environments, demonstrating significant improvements in efficiency and scalability.

1. Bernoulli Bandit

In this classic discrete task, BAFA was compared against the theoretical "Gittins index" (the gold standard for optimal exploration). BAFA reached near-optimal performance with significantly fewer simulations than the previous state-of-the-art tree-search method (BAMCP).

Weighted decision error comparison between BAFA and BAMCP.

2. Height Map Navigation

This 2D continuous navigation task required the agent to find "high reward" regions on a map it hadn't seen before, modeled using a Gaussian Process. BAMCP struggled because the search tree exploded due to discretized observations. In contrast, BAFA's function approximation allowed it to handle long planning horizons (up to 75 steps) smoothly.

Performance of BAFA vs BAMCP on the continuous navigation task across different planning horizons.

3. Under-actuated Pendulum Swing-up

In this classic control problem, an agent must swing a hanging weight until it balances upright. BAFA learned to balance the pole in just a few seconds of interaction. The authors also created a "Hard" version with a hidden "cost" variable to test non-myopic (long-term) planning. BAFA succeeded 80% of the time, while the tree-based BAMCP only succeeded 35% of the time, and non-Bayesian methods failed almost entirely.

Limitations and Future Work

While BAFA represents a major step forward for Bayesian RL in continuous spaces, it has a few limitations:

  • Feature Dependency: The performance of BAFA relies heavily on the choice of state features ($\phi$) and the set of particles ($U$) used to represent the belief. If these are poorly chosen, the approximation will fail.
  • Exploration within Search: The current implementation uses simple $\epsilon$-greedy exploration during the simulation. Integrating more sophisticated methods (like UCT) into the function approximation framework could yield better results.
  • Action Spaces: While this paper successfully tackles continuous states, it still uses a discrete set of actions. Extending this to continuous action spaces (e.g., using Policy Gradient methods within the search) is a logical and promising next step.

Summary updated

Abstract

Bayes-adaptive planning offers a principled solution to the exploration-exploitation trade-off under model uncertainty. It finds the optimal policy in belief space, which explicitly accounts for the expected effect on future rewards of reductions in uncertainty. However, the Bayes-adaptive solution is typically intractable in domains with large or continuous state spaces. We present a tractable method for approximating the Bayes-adaptive solution by combining simulation-based search with a novel value function approximation technique that generalises over belief space. Our method outperforms prior approaches in both discrete bandit tasks and simple continuous navigation and control tasks.
BibTeX
@inproceedings{guez2014bayes,
  author = {Arthur Guez and Nicolas Heess and David Silver and Peter Dayan},
  title = {{Bayes-Adaptive Simulation-based Search with Value Function Approximation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure