
























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 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, NonZero, with a sublinear local-regret guarantee for reaching approximate graph-local optima without enumerating the joint-action space. Empirically, 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.
| Comments: | Accepted by ICML 2026 as Spotlight |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.00751 [cs.LG] |
| (or arXiv:2605.00751v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.00751 arXiv-issued DOI via DataCite (pending registration) |
From: Sizhe Tang [view email]
[v1]
Fri, 1 May 2026 16:02:58 UTC (582 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。