Monte-Carlo Planning in Large POMDPs

David Silver, Joel VenessNeurIPS 2010 · OpenReview

In the realm of Reinforcement Learning, Partially Observable Markov Decision Processes (POMDPs) are notoriously difficult to solve. Unlike standard MDPs where an agent has perfect knowledge of its environment, a POMDP agent receives only noisy, partial observations. To act optimally, it must track a belief state—a probability distribution over all possible states.

Traditional POMDP solvers face two massive computational hurdles:

  1. The Curse of Dimensionality: In an environment with $n$ states, the belief state is an $n$-dimensional continuous space. Tracking this exactly is computationally brutal.
  2. The Curse of History: To plan ahead, the agent must consider every possible sequence of future actions and observations, a tree that grows exponentially with the planning horizon.

Because most existing solvers require explicit probability distributions (knowing exactly how likely every transition is), they struggle to scale beyond a few thousand states. This paper introduces POMCP (Partially Observable Monte-Carlo Planning), an algorithm that brings the power of Monte-Carlo Tree Search to partially observable environments, successfully scaling to problems with up to $10^{56}$ states.

The POMCP Approach

The authors propose combining two key ideas to bypass traditional bottlenecks:

  • PO-UCT (Partially Observable UCT): This extends the famous UCT algorithm (used in systems like AlphaGo) to search through histories rather than states. Instead of calculating the value of a specific state, it evaluates sequences of actions and observations using a "best-first" search that focuses computational effort on the most promising paths.
  • Monte-Carlo Belief Updates: Instead of performing complex, exact Bayesian updates on a probability distribution, POMCP uses an unweighted particle filter. It represents the belief state simply as a collection of sample states (particles).

Crucially, POMCP only requires a black-box simulator. The agent does not need explicit transition matrices; it only needs a function where it inputs a state and action, and receives a simulated next state, observation, and reward.

Illustration of the POMCP search tree update process. As the agent takes an action and receives an observation, the tree is pruned to form the new root, and particles are naturally filtered.

Dual-Purpose Simulations

A brilliant efficiency gain in POMCP is that the simulations used to build the search tree are simultaneously used to update the agent's belief state. When a simulation traverses the tree and matches the real-world observation the agent actually receives, that simulated state is added to the particle filter for the next step. By sampling start states from the belief and transitions from the simulator, POMCP bypasses the need to ever explicitly represent the full belief distribution or transition model.

Scaling to Massive Environments

The authors evaluated POMCP on three main benchmarks, proving its ability to handle raw, unfactored representations of massive problems:

  1. RockSample: A classic benchmark where a robot must sample rocks on Mars. The authors scaled this up to a (15, 15) grid with over 7 million states.
  2. Battleship: A 10x10 version of the classic game, featuring approximately $10^{18}$ states—far too large for traditional solvers.
  3. PocMan: A partially observable version of Pac-Man. With $10^{56}$ states, it represents a massive leap in complexity for POMDP planning.
Performance of POMCP across Rocksample, Battleship, and PocMan benchmarks. POMCP achieves high returns and scales significantly better than traditional rollout or offline methods.

Key Results

  • Unprecedented Scaling: On RockSample (11, 11), POMCP achieved the same performance in just 4 seconds of online planning that the state-of-the-art offline solver (SARSOP) required 1,000 seconds to compute.
  • Conquering New Benchmarks: POMCP was the first general-purpose planner to achieve high performance on Battleship and PocMan. In PocMan, it achieved an undiscounted return of 260 without domain knowledge, compared to just 130 for simple rollout methods.
  • Flexibility: While POMCP works "out of the box" with no prior knowledge, injecting simple heuristics (preferred actions) into the tree initialization speeds up convergence without sacrificing the ability to find the optimal policy.

Limitations and Future Work

While POMCP represents a massive leap forward, it is not without limitations. In very large or long-horizon problems, the particle filter can suffer from particle deprivation—a scenario where no simulated particles match the actual observation received, leaving the agent "blind." The authors suggest "particle reinvigoration" (adding noise or artificial particles) as a fix, but extremely sparse observation spaces remain a challenge.

Additionally, while relying on a black-box simulator is a strength for general applicability, it means the algorithm cannot exploit the internal mathematical structure of a model if that structure is actually known. Nonetheless, POMCP establishes a powerful new paradigm for scaling POMDPs to real-world complexities.

Summary updated

Abstract

This paper introduces a Monte-Carlo algorithm for online planning in large POMDPs. The algorithm combines a Monte-Carlo update of the agent's belief state with a Monte-Carlo tree search from the current belief state. The new algorithm, POMCP, has two important properties. First, Monte-Carlo sampling is used to break the curse of dimensionality both during belief state updates and during planning. Second, only a black box simulator of the POMDP is required, rather than explicit probability distributions. These properties enable POMCP to plan effectively in significantly larger POMDPs than has previously been possible. We demonstrate its effectiveness in three large POMDPs. We scale up a well-known benchmark problem, Rocksample, by several orders of magnitude. We also introduce two challenging new POMDPs: 10x10 Battleship and Partially Observable PacMan, with approximately 10^18 and 10^56 states respectively. Our Monte-Carlo planning algorithm achieved a high level of performance with no prior knowledge, and was also able to exploit simple domain knowledge to achieve better results with less search. POMCP is the first general purpose planner to achieve high performance in such large and unfactored POMDPs.
BibTeX
@inproceedings{silver2010monte,
  author = {David Silver and Joel Veness},
  title = {{Monte-Carlo Planning in Large POMDPs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=ryVCquZuZS},
}
Figure