NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Search
Sizhe Tang, Zuyuan Zhang, Mahdi Imani, Tian Lan
Abstract
Monte Carlo Tree Search (MCTS) scales poorly in cooperative multi-agent domains because expansion must consider an exponentially large set of joint actions, severely limiting exploration under realistic search budgets. We propose \textsc{NonZero}, which keeps multi-agent MCTS tractable by running surrogate-guided selection over a low-dimensional nonlinear representation using an interaction-guided proposal rule, instead of directly exploring the full joint-action space. Our exploration uses an interaction score: single-agent deviations are ranked by predicted gain, while two-agent deviations are scored by a mixed-difference measure that reveals coordination benefits even when no single agent can improve alone. We formalize candidate proposal as a bandit problem over local deviations and derive a proposal rule, \textsc{NonUCT}, with a sublinear local-regret guarantee for reaching approximate graph-local optima without enumerating the joint-action space. Empirically, \textsc{NonZero} improves sample efficiency and final performance on MatGame, SMAC, and SMACv2 relative to strong model-based and model-free baselines under matched search budgets.
BibTeX
@inproceedings{
tang2026nonzero,
title={NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Search},
author={Sizhe Tang and Zuyuan Zhang and Mahdi Imani and Tian Lan},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=Jh6gq9QsFa}
}