Subgoal-Based Temporal Abstraction in Monte-Carlo Tree Search

Thomas Gabor, Jan Peter, Thomy Phan, Christian Meyer, Claudia Linnhoff-Popien

TL;DR

Researchers from LMU Munich have developed Subgoal-MCTS (S-MCTS), a method that allows Monte-Carlo Tree Search to automatically discover and optimize "macro-actions" (sequences of moves) on the fly. By using a simple "subgoal predicate" to identify interesting states, the algorithm can plan across much longer time horizons with significantly less computational effort than standard MCTS.

Introduction: The Challenge of Long Horizons

Monte-Carlo Tree Search (MCTS) is the backbone of world-class AI systems like AlphaGo, but it faces a significant "short-sightedness" problem. In complex environments with long time horizons, the search tree becomes too deep and wide to explore effectively using only primitive, one-step actions.

To mitigate this, researchers often employ temporal abstraction—grouping primitive actions into "macro-actions" (e.g., "move to the door" instead of a sequence of individual "up" and "left" moves). However, most existing methods require human experts to manually define every possible macro-action for every state beforehand. This is impractical for games with massive state spaces. S-MCTS addresses this by enabling an agent to discover useful high-level maneuvers locally and automatically during the planning process.

Methodology: S-MCTS

The core innovation is a modification of the standard MCTS Expansion step, introducing a mechanism for on-demand macro-action generation.

  1. Subgoal Predicates: Instead of a pre-defined library, the user provides a simple "subgoal predicate"—a function that returns true if a state is "interesting" (e.g., "the agent is in a doorway" or "a Tetris piece has landed").
  2. Macro-Action Generation: When expanding a node, the algorithm performs random "micro-rollouts" of primitive actions until it hits a state satisfying the subgoal predicate or reaches a time limit.
  3. Local Optimization: If the algorithm finds multiple ways to reach the same subgoal from the same starting point, it retains only the most efficient path (the one with the highest reward).
  4. Statistical Stopping Criterion: To decide when a state is "fully explored," a Bernoulli-trial-based statistical test is used. This ensures the agent finds a diverse set of subgoals without wasting time searching for rare ones.

The paper evaluates two operational modes: Polling (re-planning at every step) and Hierarchical (committing to a full macro-action sequence before re-planning).

Experimental Setup

The approach was evaluated on two classic benchmarks:

  • Gridworld: A navigation task where an agent moves through eight rooms connected by narrow doors. The doors serve as the natural subgoals.
  • Tetris: A high-dimensional puzzle game where the subgoal is defined as "a piece has finished falling." This is a significantly harder test due to the millions of possible landing configurations.
The Gridworld environment used for evaluation, featuring eight rooms connected by narrow doors which serve as subgoals.

Key Results and Insights

S-MCTS demonstrates that you don't need a global map of subgoals. By discovering them locally during expansion, the agent focuses computation only on reachable and relevant states. Surprisingly, the system is robust to "coarse" heuristics; even imperfect subgoal definitions worked reasonably well in Gridworld.

Performance comparison (Return vs. Time per Step) for Gridworld and Tetris. S-MCTS variants achieve high returns with significantly lower computational cost than standard MCTS.
  • Tetris Performance: Standard MCTS is notoriously slow in Tetris because the search tree explodes. S-MCTS achieved near-maximum returns while being significantly faster. In many cases, standard MCTS was computationally intractable for a fair comparison.
  • Gridworld Speedup: In the 8-room task, S-MCTS variants achieved performance competitive with standard MCTS but required 10x to 100x less computation time per step.
  • Efficiency vs. Optimality: While standard MCTS might eventually find a slightly more optimal path by exploring every primitive action, S-MCTS reaches near-optimal solutions orders of magnitude faster by skipping "boring" intermediate states.

Limitations and Future Work

The current implementation assumes a deterministic environment. Adapting S-MCTS to stochastic environments, where actions can fail, would require more complex "closed-loop" macro-actions. Additionally, while the system is robust, it still requires a human to define the subgoal predicate. Future research could involve using machine learning to discover these predicates automatically from raw data. Finally, the authors note that some subgoals might require looking at a history of states (e.g., "completing a circle") rather than just the current state.

Summary updated

Abstract

We propose an approach to general subgoal-based temporal abstraction in MCTS. Our approach approximates a set of available macro-actions locally for each state only requiring a generative model and a subgoal predicate. For that, we modify the expansion step of MCTS to automatically discover and optimize macro-actions that lead to subgoals. We empirically evaluate the effectiveness, computational efficiency and robustness of our approach w.r.t. different parameter settings in two benchmark domains and compare the results to standard MCTS without temporal abstraction.
BibTeX
@inproceedings{gabor2019subgoal,
  author = {Thomas Gabor and Jan Peter and Thomy Phan and Christian Meyer and Claudia Linnhoff-Popien},
  title = {{Subgoal-Based Temporal Abstraction in Monte-Carlo Tree Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/772},
}
Figure