提出非零探索策略，让多智能体MCTS在有限预算下高效寻找协作解。
NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Search
- 用交互得分替代全联合动作空间搜索，降低计算复杂度。
- 在MatGame、SMAC等任务上，样本效率和最终表现优于基线方法。
- 适合需要高效协作决策的多智能体强化学习场景。
蒙特卡洛树搜索（MCTS）在合作型多智能体领域扩展性差，因需考虑指数级增长的联合动作空间，严重限制了实际搜索预算下的探索能力。我们提出NonZero，通过在低维非线性表示上运行代理引导的选择，而非直接探索完整联合动作空间，使多智能体MCTS保持可计算性。该方法使用交互得分：单智能体偏离按预测收益排序，双智能体偏离则采用混合差异度量，揭示即使单个智能体无法提升时的协同优势。我们将候选提议形式化为局部偏离上的多臂赌博机问题，并推导出具有次线性局部遗憾保证的提议规则NonZero，可在不枚举联合动作空间的情况下逼近图局部最优。实验表明，在与强基线匹配的搜索预算下，NonZero在MatGame、SMAC和SMACv2任务中均提升了样本效率和最终性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。