Progressive Widening for Search in Continuous Action Spaces

This direction is split into other directions: progressive widening. Its last version stays readable and citable here.

Version 1 of 150 papers56 conceptsfrozen 2026-10-04

Monte Carlo Tree Search (MCTS) is famously effective in discrete, finite domains like Go or Chess. In these games, an algorithm can enumerate every possible move from a given state, assign a value to each, and use the Upper Confidence Bound (UCB) to decide which branch to explore next.

However, when we move from the game board to the physical world—controlling a robot arm, navigating a drone, or optimizing a chemical reaction—the action space becomes continuous. There are infinitely many ways to move a joint or steer a vehicle. If a standard MCTS tried to expand every possible action, the search tree would become "flat": it would have an infinite number of children at the root and a depth of only one. The algorithm would spend all its time sampling new, random actions and never gain the "lookahead" depth that makes MCTS powerful.

Progressive Widening (PW) and its extension, Double Progressive Widening (DPW), solve this by artificially restricting the search tree's growth, forcing the algorithm to prioritize depth over breadth.

The Intuition: Depth Before Breadth

The core problem in continuous spaces is the "curse of dimensionality." As J. Daniel Griffith and Mykel Kochenderfer observe in A Comparison of Monte Carlo Tree Search and Mathematical Optimization for Large Scale Dynamic Resource Allocation, standard search methods struggle when the branching factor is high.

Progressive widening introduces a simple rule: a node is only allowed to have a small number of children. As the algorithm visits a node more frequently, it "earns" the right to add more children. This is typically governed by a power-law schedule: the number of children $k$ is proportional to $N^\alpha$, where $N$ is the number of times the parent node has been visited and $\alpha$ is a hyperparameter (often around 0.5).

This mechanism creates a virtuous cycle:

  1. Initial Focus: When a node is first reached, the search is restricted to just one or two sampled actions.
  2. Exploitation: The algorithm performs many simulations through these few actions, allowing it to look deep into the future and see if those actions lead to good outcomes.
  3. Refinement: Once the algorithm has a high-confidence estimate of the current actions, the widening schedule allows it to sample a new action. If this new action is better, the search shifts; if not, it continues refining the existing ones.

By turning an infinite action space into a sequence of increasingly dense finite approximations, PW allows MCTS to function in environments where it would otherwise fail.

Handling Stochasticity with Double Progressive Widening

In many real-world problems, the environment itself is uncertain. This is often modeled as a Partially Observable Markov Decision Process (POMDP). In these cases, even if you take the same action twice, you might end up in different states or receive different observations.

In POMCPOW: An online algorithm for POMDPs with continuous state, action, and observation spaces, Mykel Kochenderfer introduces Double Progressive Widening. Just as PW limits the number of actions (branches) from a state, DPW also limits the number of observations (outcomes) that the search tree tracks for each action.

Without this, a search tree in a continuous observation space would never reuse a node. Every simulation would result in a slightly different observation, creating a new branch every time. This is known as "belief collapse." DPW prevents this by forcing the search to "alias" or group similar outcomes together until enough simulations have been run to justify branching into a more complex belief representation. Zachary N. Sunberg demonstrates in Efficiency and Safety in Autonomous Vehicles Through Planning With Uncertainty that this strategic sampling is the only way to maintain sufficient search depth in complex autonomous driving scenarios.

Scaling to High-Dimensional Control

The power of this approach is most evident in high-dimensional robotics. Thomas Hubert and David Silver applied these principles to Sampled MuZero, extending the MuZero architecture to handle 56-dimensional humanoid control. By planning over a small subset of sampled actions and dynamically expanding that set, they showed that lookahead planning can outperform pure policy-based reinforcement learning in continuous domains.

Similarly, in the realm of offline reinforcement learning, Jiayu Chen and Jeff Schneider use DPW in Bayes Adaptive Monte Carlo Tree Search for Offline Model-based Reinforcement Learning. Their algorithm, BA-MCTS, uses widening to manage the branching factor while the agent "plans to learn," adapting its belief about the world model during the search itself.

Beyond Robotics: LLMs and Data Pipelines

The concept of progressive widening is now moving beyond physical control into the "infinite" action spaces of language and logic.

Conclusion

Progressive widening works because it acknowledges a fundamental truth of search: you cannot know everything at once. By intentionally limiting the breadth of the search tree, we allow the algorithm to discover the deep, long-term consequences of a few actions. As the algorithm gathers more evidence, it naturally and gradually expands its horizons, ensuring that the search remains both tractable and thorough.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_progressive_widening_for_search_in_conti_5e6fd512,
  title = {Progressive Widening for Search in Continuous Action Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/progressive-widening-for-search-in-continuous-action-spaces/rdr_5e6fd5121bd14983950c7f6c05316ef9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_progressive_widening_for_search_in_conti_5e6fd512_v1,
  title = {Progressive Widening for Search in Continuous Action Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/progressive-widening-for-search-in-continuous-action-spaces/rdr_5e6fd5121bd14983950c7f6c05316ef9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}