Learning is planning: near Bayes-optimal reinforcement learning via Monte-Carlo tree search

John Asmuth, Michael L. Littman

Abstract

Reinforcement learning (RL) traditionally separates learning from decision-making. This paper presents Bayesian Forward Search Sparse Sampling (BFS3), an algorithm that unifies these processes by treating RL as a planning problem within a belief-MDP. By leveraging a variant of Monte-Carlo Tree Search (MCTS), BFS3 achieves near Bayes-optimal behavior. The algorithm provides a "computational knob" to balance performance and resource usage and supports complex, structured priors, enabling efficient generalization in high-dimensional state spaces.

Introduction

The exploration-exploitation tradeoff is central to reinforcement learning. While Bayes-optimal behavior—where an agent incorporates its own uncertainty into its state representation—is the theoretical ideal, it is typically computationally intractable. Most practical RL algorithms rely on heuristics like RMAX or simple priors that may lead to sub-optimal exploration. This work introduces BFS3, a general-purpose algorithm that approximates Bayes-optimal behavior by planning through the agent's internal belief space.

The BFS3 Algorithm

BFS3 operates by maintaining a posterior distribution (belief) over possible world models. Instead of solving the belief-MDP analytically, it uses a generative approach within a search tree.

The BFS3 search tree structure, where nodes represent belief states and edges represent actions and simulated transitions.

As shown in Figure 1, the algorithm performs a forward search. For each simulated step, the agent samples a specific MDP from its current posterior, simulates a transition, and updates the simulated history to create a new belief state for the next level of the tree. This "learning is planning" paradigm allows the agent to account for the value of information naturally. A "computational knob" allows the agent to scale from a fast approximate learner to a near-perfect Bayes-optimal planner by adjusting the search depth and branching factor.

Experimental Evaluation

The authors tested BFS3 across three distinct environments:

  • 5x5 Grid World: A benchmark for handling unknown reward functions where BFS3 matched or outperformed established algorithms like BEB and RMAX.
  • Paint/Polish World: A task with binary object features designed to test generalization via structured priors.
  • Wumpus World: A partially observable maze environment testing inference under uncertainty, where performance scaled directly with computational resources.

Key Results and Insights

BFS3 demonstrates significant advantages in generalization and flexibility. In the Paint/Polish world, the use of a Factored-Object prior allowed the agent to learn significantly faster than a standard Flat-Dirichlet-Multinomial (FDM) prior.

Comparison of cumulative reward in the Paint/Polish world. The Factored-Object prior enables BFS3 to find a good policy much faster than the FDM prior.

As illustrated in Figure 3, the Factored-Object prior allows the agent to generalize knowledge across different objects, reaching a positive cumulative reward trajectory within approximately 40 trials, while the FDM approach struggles as the state space grows. This highlights the algorithm's ability to leverage domain-specific knowledge through structured priors.

Conclusion

BFS3 provides a robust framework for near Bayes-optimal RL. By framing learning as a planning problem in belief space, it eliminates the need for ad-hoc exploration strategies. While computationally intensive, its ability to handle complex priors and provide theoretical guarantees makes it a powerful tool for structured RL tasks. Future work will focus on improving sampling efficiency and extending the framework to continuous state-action spaces.

Summary updated

BibTeX
@inproceedings{asmuth2011learning,
  author = {John Asmuth and Michael L. Littman},
  title = {{Learning is planning: near Bayes-optimal reinforcement learning via Monte-Carlo tree search}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
}
Figure