# NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Search

arXiv: https://arxiv.org/abs/2605.00751 · HTML: https://mlsanity.com/paper/2605.00751/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 37 references that are in the map.
- First posted on arXiv 1 May 2026.

## Builds on (most cited first, 25 of 25)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [HyperNetworks](https://mlsanity.com/paper/1609.09106/) (2016)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Mastering Atari Games with Limited Data](https://mlsanity.com/paper/2111.00210/) (2021)
- [Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.10800/) (2020)
- [A Survey and Critique of Multiagent Deep Reinforcement Learning](https://mlsanity.com/paper/1810.05587/) (2018)
- [SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2212.07489/) (2022)
- [Off-Policy Multi-Agent Decomposed Policy Gradients](https://mlsanity.com/paper/2007.12322/) (2020)
- [Learning Nearly Decomposable Value Functions Via Communication Minimization](https://mlsanity.com/paper/1910.05366/) (2019)
- [Learning and Planning in Complex Action Spaces](https://mlsanity.com/paper/2104.06303/) (2021)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [MAC-PO: Multi-Agent Experience Replay via Collective Priority Optimization](https://mlsanity.com/paper/2302.10418/) (2023)
- [Agent Alpha: Tree Search Unifying Generation, Exploration and Evaluation for Computer-Use Agents](https://mlsanity.com/paper/2602.02995/) (2026)
- [Efficient Multi-agent Reinforcement Learning by Planning](https://mlsanity.com/paper/2405.11778/) (2024)
- [Reason in Chains, Learn in Trees: Self-Rectification and Grafting for Multi-turn Agent Policy Optimization](https://mlsanity.com/paper/2604.07165/) (2026)
- [Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstraction](https://mlsanity.com/paper/2406.00614/) (2024)
- [An MCTS-DRL Based Obstacle and Occlusion Avoidance Methodology in Robotic Follow-Ahead Applications](https://mlsanity.com/paper/2309.16884/) (2023)
- [Cochain Perspectives on Temporal-Difference Signals for Learning Beyond Markov Dynamics](https://mlsanity.com/paper/2602.06939/) (2026)
- [MINT: Minimal Information Neuro-Symbolic Tree for Objective-Driven Knowledge-Gap Reasoning and Active Elicitation](https://mlsanity.com/paper/2602.05048/) (2026)
- [BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems](https://mlsanity.com/paper/2312.15864/) (2023)

## Built on by (most cited first, 5 of 5)

- [Metric-Gradient Projection for Stable Multi-Agent Policy Learning](https://mlsanity.com/paper/2605.18809/) (2026)
- [Matrix-Space Reinforcement Learning for Reusing Local Transition Geometry](https://mlsanity.com/paper/2605.14304/) (2026)
- [Minimal Markovization via Stable Quotients in Holonomy-Cover Decision Processes](https://mlsanity.com/paper/2607.27132/) (2026)
- [Learning Not to Optimize: Physics-Informed Action-Space Reshaping for Intent-Based Network Control](https://mlsanity.com/paper/2608.00908/) (2026)
- [Differentiable Policy Transport over Multi-Layer Network Feasibility Geometry](https://mlsanity.com/paper/2609.26068/) (2026)

## Abstract (arXiv)

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.