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

• URL: http://arxiv.org/abs/2605.00751v1
• Date: Fri, 01 May 2026 16:02:58 GMT
• Title: NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Search
• Abstract summary: NonZero runs surrogate-guided selection over a low-dimensional nonlinear representation.<n>NonZero improves sample efficiency and final performance on MatGame, SMAC, and SMACv2.
• Score: 13.475979777462094
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
  We introduce a novel algorithm titled MultinoulliSCG, which is parameterfree and can achieve the same approximation guarantees as the distorted local-search methods.<n>We also present two novel online algorithms, namely, Multinoulli-CG and Multinoulli-GAGA, for the unexplored online subset selection problems over partition constraints.
  arXiv  Detail & Related papers  (2026-03-23T02:30:01Z)
• Flickering Multi-Armed Bandits [7.465238700168576]
  We introduce Flickering Multi-Armed Bandits (FMAB), a new MAB framework where the set of available arms (or actions) can change at each round.<n>We model this constrained, evolving availability using random graph processes, where arms are nodes and the agent's movement is restricted to its local neighborhood.<n>We show that our algorithm is near-optimal by establishing a matching information-theoretic lower bound for this problem class.
  arXiv  Detail & Related papers  (2026-02-19T12:24:01Z)
• MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planning [8.28864605730277]
  We propose MALinZero, a new approach to leverage low-dimensional representational structures on joint-action returns.<n> MALinZero demonstrates state-of-the-art performance on multi-agent benchmarks such as matrix games, SMAC, and SMACv2.
  arXiv  Detail & Related papers  (2025-11-08T21:27:09Z)
• On the optimal regret of collaborative personalized linear bandits [15.661920010658626]
  This paper investigates the optimal regret achievable in collaborative personalized linear bandits.<n>We provide an information-theoretic lower bound that characterizes how the number of agents, the interaction rounds, and the degree of heterogeneity jointly affect regret.<n>Our results offer a complete characterization of when and how collaboration helps with a optimal regret bound.
  arXiv  Detail & Related papers  (2025-06-19T00:56:31Z)
• Self-Localized Collaborative Perception [49.86110931859302]
  We propose$mathttCoBEVGlue$, a novel self-localized collaborative perception system. $mathttCoBEVGlue$ is a novel spatial alignment module, which provides the relative poses between agents. $mathttCoBEVGlue$ achieves state-of-the-art detection performance under arbitrary localization noises and attacks.
  arXiv  Detail & Related papers  (2024-06-18T15:26:54Z)
• AffineGlue: Joint Matching and Robust Estimation [74.04609046690913]
  We propose AffineGlue, a method for joint two-view feature matching and robust estimation. AffineGlue selects potential matches from one-to-many correspondences to estimate minimal models. Guided matching is then used to find matches consistent with the model, suffering less from the ambiguities of one-to-one matches.
  arXiv  Detail & Related papers  (2023-07-28T08:05:36Z)
• Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs [49.71319907864573]
  In this paper, we propose multi-agent skill discovery which enables the ease of decomposition. Our key idea is to approximate the joint state space as a Kronecker graph, based on which we can directly estimate its Fiedler vector. Considering that directly computing the Laplacian spectrum is intractable for tasks with infinite-scale state spaces, we further propose a deep learning extension of our method.
  arXiv  Detail & Related papers  (2023-07-21T14:53:12Z)
• Cooperative Distribution Alignment via JSD Upper Bound [7.071749623370137]
  Unsupervised distribution alignment estimates a transformation that maps two or more source distributions to a shared aligned distribution. This task has many applications including generative modeling, unsupervised domain adaptation, and socially aware learning. We propose to unify and generalize previous flow-based approaches under a single non-adversarial framework.
  arXiv  Detail & Related papers  (2022-07-05T20:09:03Z)
• Near-Optimal Collaborative Learning in Bandits [15.456561090871244]
  This paper introduces a general multi-agent bandit model in which each agent is facing a finite set of arms. The twist is that the optimal arm for each agent is the arm with largest expected mixed reward, where the mixed reward of an arm is a weighted sum of the rewards of this arm for all agents. We propose a near-optimal algorithm for pure exploration.
  arXiv  Detail & Related papers  (2022-05-31T21:11:47Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.