# Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning

arXiv: https://arxiv.org/abs/2004.11410 · HTML: https://mlsanity.com/paper/2004.11410/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2020.

## Built on by (most cited first, 19 of 19)

- [Goal-Conditioned Reinforcement Learning with Imagined Subgoals](https://mlsanity.com/paper/2107.00541/) (2021)
- [Learning Neuro-Symbolic Relational Transition Models for Bilevel Planning](https://mlsanity.com/paper/2105.14074/) (2021)
- [Decomposing the Enigma: Subgoal-based Demonstration Learning for Formal Theorem Proving](https://mlsanity.com/paper/2305.16366/) (2023)
- [Model-Based Reinforcement Learning via Latent-Space Collocation](https://mlsanity.com/paper/2106.13229/) (2021)
- [Subgoal Search For Complex Reasoning Tasks](https://mlsanity.com/paper/2108.11204/) (2021)
- [Horizon Generalization in Reinforcement Learning](https://mlsanity.com/paper/2501.02709/) (2025)
- [Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search](https://mlsanity.com/paper/2206.00702/) (2022)
- [Transitive RL: Value Learning via Divide and Conquer](https://mlsanity.com/paper/2510.22512/) (2025)
- [DISC: Dynamic Decomposition Improves LLM Inference Scaling](https://mlsanity.com/paper/2502.16706/) (2025)
- [Hybrid Search for Efficient Planning with Completeness Guarantees](https://mlsanity.com/paper/2310.12819/) (2023)
- [Advancing Autonomous VLM Agents via Variational Subgoal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2502.07949/) (2025)
- [Diverse, Top-k, and Top-Quality Planning Over Simulators](https://mlsanity.com/paper/2308.13147/) (2023)
- [Goal-Conditioned Supervised Learning with Sub-Goal Prediction](https://mlsanity.com/paper/2305.10171/) (2023)
- [SEGO: Sequential Subgoal Optimization for Mathematical Problem-Solving](https://mlsanity.com/paper/2310.12960/) (2023)
- [Generation of Geodesics with Actor-Critic Reinforcement Learning to Predict Midpoints](https://mlsanity.com/paper/2407.01991/) (2024)
- [Recursive Value Learning for Long-Horizon Offline Goal-Conditioned RL](https://mlsanity.com/paper/2609.02237/) (2026)
- [Improving Reliable Navigation under Uncertainty via Predictions Informed by Non-Local Information](https://mlsanity.com/paper/2307.14501/) (2023)
- [DHP: Discrete Hierarchical Planning for Hierarchical Reinforcement Learning Agents](https://mlsanity.com/paper/2502.01956/) (2025)
- [GTRL: Grounding Divide-and-Conquer Value Learning with Temporal Differences](https://mlsanity.com/paper/2609.33259/) (2026)

## Abstract (arXiv)

Standard planners for sequential decision making (including Monte Carlo planning, tree search, dynamic programming, etc.) are constrained by an implicit sequential planning assumption: The order in which a plan is constructed is the same in which it is executed. We consider alternatives to this assumption for the class of goal-directed Reinforcement Learning (RL) problems. Instead of an environment transition model, we assume an imperfect, goal-directed policy. This low-level policy can be improved by a plan, consisting of an appropriate sequence of sub-goals that guide it from the start to the goal state. We propose a planning algorithm, Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS), for approximating the optimal plan by means of proposing intermediate sub-goals which hierarchically partition the initial tasks into simpler ones that are then solved independently and recursively. The algorithm critically makes use of a learned sub-goal proposal for finding appropriate partitions trees of new tasks based on prior experience. Different strategies for learning sub-goal proposals give rise to different planning strategies that strictly generalize sequential planning. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds as well as in challenging continuous control environments.