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.
- 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").
- 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.
- 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).
- 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.
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.
- 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