Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstraction
This work addresses a bottleneck in decision-making algorithms for AI systems, particularly in domains with factored action spaces, though it appears incremental as it builds on existing MCTS and MuZero frameworks.
The paper tackles the problem of Monte Carlo Tree Search (MCTS) performance degradation in vast combinatorial action spaces by proposing a state-conditioned action abstraction method that reduces the search space by discarding redundant sub-actions, resulting in superior sample efficiency compared to vanilla MuZero.
Monte Carlo Tree Search (MCTS) has showcased its efficacy across a broad spectrum of decision-making problems. However, its performance often degrades under vast combinatorial action space, especially where an action is composed of multiple sub-actions. In this work, we propose an action abstraction based on the compositional structure between a state and sub-actions for improving the efficiency of MCTS under a factored action space. Our method learns a latent dynamics model with an auxiliary network that captures sub-actions relevant to the transition on the current state, which we call state-conditioned action abstraction. Notably, it infers such compositional relationships from high-dimensional observations without the known environment model. During the tree traversal, our method constructs the state-conditioned action abstraction for each node on-the-fly, reducing the search space by discarding the exploration of redundant sub-actions. Experimental results demonstrate the superior sample efficiency of our method compared to vanilla MuZero, which suffers from expansive action space.