mlsanityData to 7 Oct 2026

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

arXiv 2605.00751 ↗First posted 1 May 2026cs.LGcited by 4

Not on the map. Why?

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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 25 of its 37 references that are in the map. First posted on arXiv 1 May 2026.

Builds on

25 of 37 references.

References · 25

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  2. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
  3. 2016HyperNetworkscited by 1,003
  4. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 903
  5. 2019The StarCraft Multi-Agent Challengecited by 589
  6. 2017Value-Decomposition Networks For Cooperative Multi-Agent Learningcited by 490
  7. 2020Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 475
  8. 2019QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learningcited by 372
  9. 2021Mastering Atari Games with Limited Datacited by 235
  10. 2020Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 197
  11. 2018A Survey and Critique of Multiagent Deep Reinforcement Learningcited by 173
  12. 2022SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learningcited by 118
13 more
  1. 2020Off-Policy Multi-Agent Decomposed Policy Gradientscited by 97
  2. 2019Learning Nearly Decomposable Value Functions Via Communication Minimizationcited by 85
  3. 2021Learning and Planning in Complex Action Spacescited by 76
  4. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  5. 2023MAC-PO: Multi-Agent Experience Replay via Collective Priority Optimizationcited by 20
  6. 2026Agent Alpha: Tree Search Unifying Generation, Exploration and Evaluation for Computer-Use Agentscited by 12
  7. 2024Efficient Multi-agent Reinforcement Learning by Planningcited by 9
  8. 2026Reason in Chains, Learn in Trees: Self-Rectification and Grafting for Multi-turn Agent Policy Optimizationcited by 7
  9. 2024Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstractioncited by 6
  10. 2026Cochain Perspectives on Temporal-Difference Signals for Learning Beyond Markov Dynamicscited by 5
  11. 2023An MCTS-DRL Based Obstacle and Occlusion Avoidance Methodology in Robotic Follow-Ahead Applicationscited by 4
  12. 2026MINT: Minimal Information Neuro-Symbolic Tree for Objective-Driven Knowledge-Gap Reasoning and Active Elicitationcited by 4
  13. 2023BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problemscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Metric-Gradient Projection for Stable Multi-Agent Policy Learningcited by 3
  2. 2026Matrix-Space Reinforcement Learning for Reusing Local Transition Geometrycited by 0
  3. 2026Learning Not to Optimize: Physics-Informed Action-Space Reshaping for Intent-Based Network Controlcited by 0
  4. 2026Differentiable Policy Transport over Multi-Layer Network Feasibility Geometrycited by 0