Towards Low-Dimensional Search for Mastering Multi-Agent Planning

Abstract

Monte Carlo Tree Search (MCTS) faces a severe scalability bottleneck in Multi-Agent Planning (MAP) due to the combinatorial explosion of joint action spaces. In this position paper, we argue that the key to tractable planning lies in leveraging low-dimensional representational structures to guide the tree search, rather than enumerating the raw action space. Specifically, under a linear approximation of joint-action returns, we demonstrate that the node expansion problem can be effectively cast and solved as a linear contextual bandit, providing theoretical regret guarantees. Empirical results on complex benchmarks confirm that this structure-aware search significantly outperforms state-of-the-art baselines, offering a scalable path for neuro-symbolic multi-agent planning. We further discuss promising extensions, including integrating dynamic agent grouping and coalition formation mechanisms to further reduce the effective branching factor.