NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Search Sizhe Tang 1 Zuyuan Zhang 1 Mahdi Imani 2 Tian Lan 1
arXiv:2605.00751v1 [cs.LG] 1 May 2026
Abstract
et al., 2017) and MuZero (Schrittwieser et al., 2020), MCTS can be applied effectively in large state spaces by refining decisions online under a fixed simulation budget.
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 N ON Z ERO, which keeps multi-agent MCTS tractable by running surrogate-guided selection over a lowdimensional nonlinear representation using an interaction-guided proposal rule, instead of directly exploring the full joint-action space. Our exploration uses an interaction score: singleagent deviations are ranked by predicted gain, while two-agent deviations are scored by a mixeddifference 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, N ON UCT, with a sublinear localregret guarantee for reaching approximate graphlocal optima without enumerating the joint-action space. Empirically, N ON Z ERO improves sample efficiency and final performance on MatGame, SMAC, and SMACv2 relative to strong modelbased and model-free baselines under matched search budgets.
Scaling MCTS to cooperative multi-agent planning is challenging because action selection is combinatorial. With n agents and d actions per agent, the joint-action set has size |A| = dn , so naive expansion induces an exponential branching factor and quickly exhausts practical simulation budgets (Lowe et al., 2017; Hernandez-Leal et al., 2019; Kwak et al., 2024; Liu et al., 2024). This bottleneck is especially challenging when returns exhibit strong interaction effects, where high-value outcomes may require coordinated deviations that are unlikely to be found by uninformed sampling. Prior work alleviates this burden only partially by addressing different aspects of the problem. MAZero (Liu et al., 2024) improves model learning and distributed planning components, but tree expansion still fundamentally depends on which joint actions are selected at each node. MALinZero (Tang et al., 2025) reduces joint-action search by exploiting linear return structure, enabling efficient exploration when improvements arise from independent singleagent changes; however, this assumption can miss coordinated improvements when returns are non-additive. Related value factorization approaches, such as VDN (Sunehag et al., 2017) and QMIX (Rashid et al., 2020b), similarly impose structural constraints on the joint value, but they are not designed to support the uncertainty-aware action expansion required by tree search.
1. Introduction Monte Carlo Tree Search (MCTS) is a widely used planning method, with successes in game playing (Sironi et al., 2018; Silver et al., 2017; Schrittwieser et al., 2020), robotics (Leisiazar et al., 2023), and combinatorial optimization (Xiao et al., 2023). Its effectiveness in standard MCTS stems from Upper Confidence Bound for Trees (UCT) selection, which concentrates computation on promising parts of the search tree while still exploring uncertain actions through confidence bonuses (Kocsis & Szepesvári, 2006). When combined with learned predictors, as in AlphaZero (Silver
We propose N ON Z ERO, a multi-agent MCTS framework that keeps search tractable without enumerating the |A| = dn joint-action space. At each node, N ON Z ERO runs surrogate-guided selection over a low-dimensional nonlinear representation using an interaction-guided proposal rule. To drive candidate expansion, N ON Z ERO fits a compact lowdimensional nonlinear predictor of joint-action returns and evaluates structured one- and two-agent deviations from the current candidates. Single-agent deviations are prioritized by predicted gain, while coordinated two-agent deviations are scored using a mixed-difference interaction measure that targets coordination benefits even when no single agent can improve alone (coordination traps), enabling targeted
1 The George Washington University 2 Northeastern University. Correspondence to: Sizhe Tang <[email protected]>.
Preprint. May 4, 2026.
1
NonZero: Nonlinear Search for Multi-Agent RL
coordination search while keeping the per-node branching factor fixed.
Zhou et al., 2022). Under the Centralized Training with Decentralized Execution (CTDE) paradigm, VDN (Sunehag et al., 2017) approximates the global value function Qtot via a linear sum of local utilities. This approach has been extended to monotonic nonlinear combinations in QMIX (Rashid et al., 2020b) and nearly-decomposable structures in NDQ (Wang et al., 2019). Further advancements include policy-based factorizations (DOP (Wang et al., 2020), FOP (Zhang et al., 2021)) and value-correction mechanisms (QTRAN (Son et al., 2019), WQMIX (Rashid et al., 2020a)) to address representational limitations. However, their structural assumptions (e.g., additivity or monotonicity) are insufficient to capture complex interactions inherent in sophisticated multi-agent tasks.
We formalize this candidate-expansion step as a nonlinear bandit problem over local deviations and derive N ON UCT, an optimistic proposal rule for allocating deviation queries during exploration. Under discrete smoothness assumptions on the return surrogate, we obtain a sublinear local-regret guarantee for reaching approximate graph-local optima with complexity that does not scale with |A| = dn . Empirically, integrating N ON Z ERO into MuZero-style planning yields consistent gains in both sample efficiency and final performance on MatGame, SMAC (Samvelyan et al., 2019), and SMACv2 (Ellis et al., 2023) relative to strong model-based and model-free baselines under matched search budgets.
MCTS-based Planning. MCTS has been established as a powerful paradigm for sequential decision-making in complex planning horizons (Browne et al., 2012; Silver et al., 2017; Fang et al., 2026; Li et al., 2026b;a; Tang et al., 2026). Instead of relying on exhaustive search, MCTS approximates optimal values through iterative simulation, typically involving four stages: Selection, Expansion, Simulation, and Back-Propagation. To eliminate the dependency on groundtruth simulators, model-based variants like MuZero (Schrittwieser et al., 2020) introduce learnable components: a representation model hθ , a dynamics model gθ , and a prediction model fθ . Given an observation history, MuZero maps it to a latent state via hθ , and performs recursive predictions using gθ and fθ . Crucially, during the Selection phase, MuZero employs the Probabilistic Upper Confidence Tree (pUCT) rule to balance exploration and exploitation: # " pP b N (s, b) , at = arg max Φ(s, a) + c(s)P (s, a) a∈A 1 + N (s, a) (1) where Φ(s, a) is the estimated Q-value, P (s, a) is the prior policy probability, and c(s) is a scaling factor. This makes evaluating and maintaining selection statistics over Eq. 1 over the full joint-action space computationally intractable.
Our main contributions are: (i) N ON Z ERO, a candidate-set multi-agent MCTS framework that overcomes the combinatorial joint-action bottleneck through interaction-guided candidate expansion based on a compact nonlinear return surrogate. (ii) N ON UCT, a principled proposal mechanism derived from a nonlinear bandit formulation over local deviations, enabling coordinated exploration without enumerating the dn joint-action space. (iii) A sublinear local-regret analysis under graph-local optimality, together with consistent empirical gains on MatGame, SMAC, and SMACv2 under matched search budgets.
2. Related Works We formalize the cooperative multi-agent planning task as a Decentralized Partially Observable Markov Decision Process (Dec-POMDP) (Oliehoek et al., 2016; Zhang et al., 2025; Jiang et al., 2025; Mei et al., 2023), represented by the tuple M = ⟨I, S, A, P, R, Ω, O, γ⟩. Here, I = {1, . . . , n} denotes the set of n agents operating within a global state space S. At each discrete time step t, every agent i ∈ I receives a local observation oit ∈ Ωi and subsequently selects a local action ait from its individual action set Ai based on its action-observation history. These individual choices constitute a joint action vector at = (a1t ,Q . . . , ant ), n which resides in the joint action space A ≡ i=1 Ai . Upon the execution of at , the environment transitions to a new state st+1 ∼ P (·|st , at ) and yields a shared global reward rt = R(st , at ). The collective objective of the agents is to identify a joint policy π that maximizes the expected cumulative P∞ discounted return, formally defined as J(π) = Eπ [ t=0 γ t rt ], where γ ∈ [0, 1) serves as the discount factor.
To address large action spaces, Sampled MuZero (Hubert et al., 2021) modifies the algorithm to only search over a randomly sampled subset of actions T (s) ⊂ A, drawn from a proposal policy to at = β. The selection rule is adjusted √ β̂(a) arg maxa∈T (s) Φ(s, a) + c(s) β(a) P (s, a)
P
b∈T (s) N (s,b) 1+N (s,a)
with an importance sampling correction. Although this sampling strategy (and similar distributed approaches like MAZero (Liu et al., 2024)) makes execution feasible, it fundamentally relies on the quality of the proposal distribution β. In the vast combinatorial landscapes of multi-agent tasks, random or heuristic sampling is often inefficient, failing to cover sparse optimal joint actions. In contrast, N ON Z ERO constructs proposals using a learned nonlinear return surrogate and interaction-guided local
MARL with factorized representations. Factorizationbased methods are pivotal for mitigating the curse of dimensionality in the joint action space (Zhang et al., 2026; 2
NonZero: Nonlinear Search for Multi-Agent RL
∆2u,v η(θ, a) makes ∆2u,v a discrete interaction/curvature signal for coordinated deviations.
deviations, targeting coordinated joint actions without relying on uninformed sampling.
In this work, we define a score function z(θ, a) = ⟨w(θ), ψ(a)⟩ where w(θ) ∈ Rnd and ψ(a) ∈ Rnd . We adopt the asinh link g(z) = c asinh(αz) with fixed scale parameters c > 0 and α > 0, and define the estimated deterministic reward η(θ, a) = g(z(θ, a)). Thus, for each n-hot action vector a ∈ A, we model the low-dimensional reward η(θ, a) as a nonlinear combination of n corresponding peragent action rewards. This procedure can be viewed as projecting the actual reward rt into the low-dimensional space representable with η(θ∗ , a) = c asinh(α⟨w(θ∗ ), ψ(a)⟩). It reduces MCTS from considering dn joint reward values in each state to learning a structured parameter vector whose estimation complexity is independent of the exponential joint-action count |A| = dn , thereby allowing quick estimation of the global reward structure from limited samples and speeding up tree search convergence in multi-agent MCTS. Using the learned return proxy η(θ̂t , a), we select an action
3. N ON Z ERO for Multi-Agents MCTS N ON Z ERO leverages low-dimensional representations of the joint-action returns and solves the resulting nonlinear bandit problem to enable efficient and effective N ON UCTbased MCTS in complex multi-agent planning. N ON UCT is applied as a proposal and learning mechanism that guides candidate expansion and local surrogate refinement during MCTS. N ON Z ERO follows MuZero with (i) representation, (ii) dynamics, and (iii) prediction heads, and adds (iv) a mixing/hypernetwork that initializes the node-wise surrogate parameter θ used by N ON UCT. To achieve more accurate and efficient reward approximation, we propose N ON UCT to capture the non-linearity of low-dimensional rewards and analyze its regret. All proofs are collected in the Appendix A. Here, “low-dimensional” refers to the fact that exploration and estimation depend on local deviations in A rather than on enumerating the full joint-action set |A| = dn .
at = arg max η(θ̂t , a). a∈A
3.1. Leveraging Low-Dimensional Nonlinear Representations
(2)
Directly solving (2) over the full joint-action set A is intractable when |A| = dn . Instead, at each tree node s we maintain a small candidate set C(s) ⊂ A of expanded joint actions. MCTS selection compares only actions in C(s) using the learned surrogate score η(θ̂s , ·).
N ON Z ERO models the joint-action returns through a lowdimensional nonlinear combination of the latent per-agent action rewards, based on which an online learner optimizes to capture the representation. Precisely, we consider a deterministic nonlinear bandit problem with an unknown parameter θ∗ ∈ Θ and a discrete joint-action set A ⊂ {0, 1}nd consisting of n-hot vectors (one-hot per agent), where n denotes the number of agents and d is the size of action set for each agent. Thus, each joint action a ∈ A is represented by an n-hot vector selecting one local action for each agent. Given the action a, the environment reveals a deterministic reward rt = η(θ∗ , a).
N ON UCT is used only as a proposal mechanism that adds a small number of new candidates to C(s) by applying oneagent or two-agent deviations predicted to yield the largest discrete improvement under η(θ̂s , ·). This keeps the pernode branching factor |C(s)| fixed while still allowing coordinated exploration. However, the global convergence of the nonlinear bandit problem mentioned above is statistically intractable. Specifically, it requires exponential samples in the input dimension; for example, O(|A|) = O(dn ) globally optimizing a nonlinear reward model over A requires samples that scaling with the joint-action count |A| = dn .
We define first- and second-order finite-difference operators on the joint-action adjacency graph. Let a = (a1 , . . . , an ) ∈ A and define the one-agent neighbor a(i←j) as the joint action obtained by changing only agent i’s action to j ∈ Ai . Let the neighbor set be N (a) = {a(i←j) : i ∈ [n], j ∈ Ai , j ̸= ai }. We denote a discrete direction by u = (i ← j) and write a(u) := a(i←j) . The first-order directional difference is ∆u η(θ, a) := η(θ, a(u) ) − η(θ, a). For two directions u = (i ← j) and v = (k ← ℓ) with i ̸= k, define the mixed second-order difference ∆2u,v η(θ, a) := η(θ, a(u,v) )−η(θ, a(u) )−η(θ, a(v) )+η(θ, a),
Thus, we propose guiding the model to converge to a local maximum rather than directly seeking global optimization. Note that the loss function η̃(θ, a) is not concave, but its discrete local-optimality structure admits efficient convergence guarantees under our smoothness assumptions (Assumption 3.2), without requiring global maximization over A. We do not assume global concavity; our guarantees are graph-local and hold under one-agent and two-agent deviations. In general, globally optimizing a nonlinear reward model over the combinatorial set A is intractable (Dong et al., 2021). Accordingly, our analysis targets efficient conver-
where a(u,v) applies both one-agent changes. The identity η(θ, a(u,v) ) − η(θ, a) = ∆u η(θ, a) + ∆v η(θ, a) + 3
NonZero: Nonlinear Search for Multi-Agent RL
In MCTS, we treat the learned reward head rψ (s, ·) at a fixed node state s as the planning-time reward function. All counterfactual quantities (e.g., rψ (s, a(u) ) and rψ (s, a(u,v) )) are obtained by evaluating the learned model, without additional environment interaction. Accordingly, θ⋆ denotes the best-in-class parameter (within our asinh-GLM family) that locally fits rψ (s, ·) around the candidate actions explored at node s. Only the selected legal joint action is executed in the real environment for data collection.
gence to graph-local optima, measured by gains in oneagent and two-agent deviations (Definition 3.1). This is the relevant notion for scalable multi-agent planning, where coordinated improvements may require deviations across agents. To achieve this, we need to augment the loss function so that our model satisfies η(θ̂t , at ) ≈ η(θ∗ , at ), ∆u η(θ̂, at ) ≈ ∆u η(θ∗ , at ), and ∆2u,v η(θ̂, at ) ≈ ∆2u,v η(θ∗ , at ). It is implied that the virtual reward η(θ̂t , at ) will keep improving until at is a local maxima of η(θ∗ , at ) if we optimize the learning process via taking greedy actions.
The loss function that needs to be optimized is defined by h1 (η(θ, a) − η(θ⋆ , a))2 LN ON UCT := min Ea,u,v θ 4 + (η(θ, a(u) ) − η(θ⋆ , a(u) ))2 + (∆u η(θ, a) − ∆u η(θ⋆ , a))2 i + (∆2u,v η(θ, a) − ∆2u,v η(θ⋆ , a))2 .
Since the real environment provides only the realized reward for the executed joint action, we compute all counterfactual evaluations needed for discrete differences from the learned reward model at the node state (MuZero-style planning model): ∆u η(θ⋆ , a) := η(θ⋆ , a(u) ) − η(θ⋆ , a).
(7) 3.2. Analyzing Regret
(3)
In this section, we derive the theoretical guarantees of N ON UCT. Unlike standard UCT, which relies on global optimism (often intractable in high-dimensional spaces, i.e., requiring O(end ) samples), N ON UCT exploits the curvature information of the asinh-activated reward landscape. Our analysis targets convergence to graph-local maximizers under one-agent and two-agent deviations, which is the appropriate notion of optimality for scalable multi-agent planning.
For discrete curvature, we compute the mixed second-order difference: ∆2u,v η(θ⋆ , a) := η(θ⋆ , a(u,v) ) − η(θ⋆ , a(u) ) −η(θ⋆ , a(v) ) + η(θ⋆ , a).
(4)
where v is a random sampled direction independent of u. Note that the number of projections above does not scale with the exponential branching factor dn ; it depends only on the statistical complexity of the learned surrogate class and the number of sampled deviation directions per update, since only the norm of the projections needs to be estimated. This action-dimension-free property ensures that the proposed N ON UCT can achieve efficient exploration in the dn -large action space.
We quantify the performance via cumulative local regret, defined as the cumulative gap between the reward of the selected action at and the reward of the nearest approximate local maximizer. We prove that N ON Z ERO achieves a sub-linear regret R̂T = Õ(T 3/4 ), ensuring efficient convergence. The regret is measured with respect to the first time an (ε1 , ε2 )-local maximizer is reached, counting only steps taken outside this set.
∆u η(θ, a) measures the gain from a single-agent deviation, while ∆2u,v η(θ, a) measures the non-additive interaction (synergy/anti-synergy) of two coordinated deviations. In cooperative MARL, local one-agent improvements may be negative even when a coordinated two-agent deviation is beneficial; ∆2u,v provides a principled signal for proposing such coordinated joint actions without enumerating A.
Geometric and Smoothness Assumptions. We first define the convergence target and the regularity conditions of the reward landscape. Definition 3.1 (Approximate local maximizer on the joint-action graph). Let η̃(θ⋆ , a) be the objective over the discrete set A. Define the one-agent deviation gain G1 (a) := maxu ∆u η̃(θ⋆ , a) and the best two-agent coordinated devi ation gain G2 (a) := maxu̸=v η̃(θ⋆ , a(u,v) ) − η̃(θ⋆ , a) . We say a is an (ε1 , ε2 )-approximate local maximizer if G1 (a) ≤ ε1 and G2 (a) ≤ ε2 .
Given x = (a, u, v), define the prediction target ŷ(θ, x) = η(θ, a), η(θ, a(u) ), ∆u η(θ, a), ∆2u,v η(θ, a) (5) where a′ denotes the action perturbation used to produce the first and second order differences. The supervision is
The role of the first and second order differences in Eq. 7 is to refine the node-specific parameter θ̂s so that the optimistic score η(θ̂s , a) used in Eq. 2 is locally accurate around candidate actions, improving exploration efficiency without enumerating the full joint-action space.
y(x) = η(θ⋆ , a), η(θ⋆ , a(u) ), ∆u η(θ⋆ , a), ∆2u,v η(θ⋆ , a) (6) And we note that ŷ(θ, x), y(x) ∈ R4 . 4
NonZero: Nonlinear Search for Multi-Agent RL
While finding global optima is generally NP-hard in nonconvex settings, the invexity properties of the asinh-GLM landscape imply that approximate local maxima are effectively global or optimism-equivalent (Kalai & Sastry, 2009). Thus, convergence to the state defined above serves as a robust proxy for optimal planning. The choice of the asinh link function is pivotal to our theoretical framework. Unlike sigmoidal activations that suffer from vanishing gradients (saturation) or ReLU networks that lack higher-order smoothness, the asinh function, g(z) = c · asinh(αz), is strictly increasing, unbounded, and infinitely differentiable. Crucially, its derivatives decay at a controlled polynomial rate, ensuring that the reward landscape is sufficiently smooth to allow curvature-based optimization. This structural property justifies the following smoothness assumptions, which are satisfied by the asinh-GLM class by design.
ascent: f (at+1 ) − f (at ) ≥ ν(ϵ) − C1 · ξt+1 , (10) 3/2 2 where ν(ϵ) ≜ c1 min ζhϵ+1 , ϵ 1/2 is the strictly positive ζ3rd
improvement rate, C1 = 2 + ζg /ζh is a constant. Lemma 3.3 establishes a sufficient ascent property: the algorithm ensures a strict increase in the ground-truth reward at each step, modulo the online learner’s estimation error. We now provide bounds on the estimation error. Lemma 3.4 (Estimation Error Control). The cumulative prediction error is bounded by the generalization capacity of the learner: T X
Assumption 3.2 (Discrete smoothness on A). There exist constants ζ1 , ζ2 , ζ3 > 0 such that for all θ ∈ Θ, all a ∈ A, and all feasible directions u, v, w (with distinct agents when needed), |∆u η(θ, a)| ≤ ζ1 , |∆2u,v η(θ, a)| ≤ ζ2 , |∆2u,v η(θ, a(w) ) − ∆2u,v η(θ, a)| ≤ ζ3 .
(11)
Now we verify the convergence. Summing the one-step improvement over T iterations relates the total reward gain to the cumulative estimation error:
(8)
T −1 X η̃(θ∗ , aT ) − η̃(θ∗ , a0 ) = (η̃(θ∗ , at+1 ) − η̃(θ∗ , at )) | {z } t=0 Total Gain
≥
T −1 X t=0
ν(ϵ) · I(at ∈ / Aϵ ) − C1
T X
ξt .
t=1
(12) Since the reward is bounded, the total gain is finite. This inequality implies that the algorithm cannot stay outside the local maximizer set Aϵ for too long, unless the estimation error is large. Formalizing this intuition leads to the following regret bound. Theorem 3.5 (Regret Bound of N ON UCT). For any tolerance ϵ ≤ min(1, ζ3rd /16), the expected cumulative re√ gret of N ON UCT with respect to finding (ϵ, 6 ζ3rd ϵ)-local maxima is bounded by: p E[RegretT ] ≤ (1 + C1 4T RT ) · K(ϵ), (13) √ where K(ϵ) = max(4ζh ϵ−2 , ζ3rd ϵ−3/2 ) encapsulates the complexity regarding the landscape curvature and target precision.
2 ξt := η(θt , at ) − η(θ⋆ , at ) 2
T · RT .
√ In N ON Z ERO, we have RT = Õ( T ), which implies the cumulative error scales sub-linearly as Õ(T 3/4 ).
We establish the regret bound by decomposing the regret into two parts: a geometric improvement term, which quantifies the guaranteed increase in reward towards an approximate local maximizer, and a statistical estimation term, which captures the prediction discrepancy controlled by the sequential Rademacher complexity. We denote the composite prediction error at step t as a squared error over the four scalar supervision targets (value at a, value at a one-agent neighbor, one-agent directional difference, and two-agent mixed difference):
+ ∆ut η(θt , at ) − ∆ut η(θ⋆ , at )
p
t=1
Assumption 3.2 formalizes the boundedness of discrete gains and interaction effects under single- and two-agent deviations, which holds naturally for bounded reward models.
(u ) (u ) 2 + η(θt , at t ) − η(θ⋆ , at t )
ξt ≤
(9)
2 + ∆2ut ,vt η(θt , at ) − ∆2ut ,vt η(θ⋆ , at ) . which encompasses the discrepancies in reward values and in first-/second-order discrete differences used for local improvement.
Corollary 3.6 (The Order of Regret Bound for N ON UCT). Under the above conditions, the cumulative regret bound of N ON UCT satisfies: E[RegretT ] = Õ T 3/4 . (14)
Lemma 3.3 (One-step Geometric Improvement). Let f (a) = η̃(θ∗ , a). Provided that the current action is not yet an approximate local maximizer (i.e., at ∈ / Aϵ,6√ζ3rd ϵ ), the curvature-guided update yields a guaranteed reward 5
NonZero: Nonlinear Search for Multi-Agent RL
Algorithm 1 N ON Z ERO MCTS with Discrete CurvatureGuided Proposals
The regret bound of N ON UCT in Theorem 3.5 is actiondimension free while sublinear. We quantify the efficiency gap as follows to demonstrate N ON Z ERO’s exploration efficiency. Theorem 3.7 (Efficiency Separation). Let TNonUCT (d, ϵ) and TUCB (d, ϵ) denote the number of rounds required to output an approximate local maximizer. The separation ratio ζsep satisfies: ζsep ≜
TUCB (d, ϵ) exp(c · nd) ≥ , TNonUCT (d, ϵ) poly(nd, ϵ−1 )
1: Input: root state s0 2: Hyperparameters: simulations Nsim , candidate budget
K, learning rate γ 3: for sim = 1 to Nsim do 4: path ← S ELECT(s0 ) 5: leaf ← last(path) 6: if leaf not terminal then 7: E XPAND(leaf) 8: end if 9: BACKUP(path) 10: end for 11: return π(s0 ) from visit counts
(15)
where c > 0 is a universal constant. N ON UCT achieves action-dimension-free convergence in the sense that its sample complexity scales polynomially with the model’s statistical capacity, whereas standard UCB suffers from an unavoidable curse of dimensionality in the joint action space.
12: Procedure S ELECT(node) 13: while node has children do 14: a⋆ ← arg maxa∈C(node) 15: node ← node.child(a⋆ ) 16: append node to path 17: end while 18: return path
3.3. Algorithm Framework Integrated with curvature-aware learning, N ON Z ERO achieves efficient exploitation and exploration in complex MCTS. The N ON Z ERO model is unrolled with four key phases as standard MCTS and trained in an end-to-end manner like MuZero (Schrittwieser et al., 2020). The detailed pseudocode of NonZero is shown in Algorithm 1.
η(θnode , a)
19: Procedure E XPAND 20: Sample C(node) with policy-prior samples 21: for all a ∈ C(node) do 22: node′ ← node.child(a) 23: θ ← H YPER N ETWORK(node′ .state) 24: Sample u = (i ← j), v = (k ← ℓ), i ̸= k 25: Form a(u) , a(u,v) b u ← η(θ, a(u) ) − η(θ, a) 26: ∆ b 2 ← η(θ, a(u,v) ) − η(θ, a) 27: ∆ u,v 28: end for
N ON Z ERO augments the standard MCTS lifecycle by replacing the UCB heuristic in selection with a curvatureaware optimization routine. In the Selection and BackPropagation phase, rather than relying on scalar confidence bounds that scale poorly in combinatorial spaces, the algorithm selects among the currently expanded child actions using the learned surrogate optimized by N ON UCT. This step exploits the asinh-induced smoothness to efficiently navigate the joint-action space, guiding the search path toward the (ϵg , ϵh )-approximate local maximizers defined in Section 3.2. This mechanism allows the agent to synthesize complex multi-agent coordination strategies without exhaustively enumerating the exponential action space.
29: Procedure BACKUP(path) 30: for node in path (reversed) do 31: Update N (node, ·) and Q(node, ·) 32: Sample u = (i ← j), v = (k ← ℓ), i ̸= k 33: Pick a ∈ C(node) 34: Compute r(a), r(a(u) ), r(a(u,v) ) 35: ∆u r ← r(a(u) ) − r(a) 36: ∆2u,v r ← r(a(u,v) ) − r(a(u) ) − r(a(v) ) + r(a) 37: θnode ← θnode − γ∇θ LN ON UCT 38: end for
To ensure the reward landscape η(θ̂, ·) accurately reflects the ground truth, N ON Z ERO incorporates a two-stage estimation strategy. Subsequently, during Back-propagation, the algorithm performs online adaptation to refine this estimate. By collecting the reward evaluations and estimating the local geometry via the random projection operators (Eq. 3 and 4), we update the node-specific parameter θ̂ by minimizing the curvature loss LN ON UCT via gradient descent. This ensures that the local approximation progressively aligns with the true environmental dynamics as the simulation depth increases.
volves a hypernetwork (Ha et al., 2016) to predict the initialization of the state-wise θ when a new node is added to the search tree. Therefore, the gathered interaction information to estimate θ will be accumulated throughout the training process, which accelerates the convergence of N ON Z ERO. Specifically, the hypernetwork takes the state st+k as the input and generates the parameter θ. The generated θ will be further optimized in the following MCTS iterations.
Hypernetworks for parameter estimation warm-up. To achieve faster convergence of θ, the N ON Z ERO model in6
NonZero: Nonlinear Search for Multi-Agent RL
4. Experiments
forming both model-based (MAZero family) and model-free (MAPPO, QMIX) baselines. Beyond asymptotic performance, N ON Z ERO demonstrates superior sample efficiency; it converges to optimal policies requiring 50% to 70% fewer environmental steps than its closest competitor, MAZero. This corresponds to a 2-3× acceleration in training dynamics. We attribute this efficiency to the N ON UCT mechanism, which exploits the curvature of the latent reward landscape to guide the search. Unlike standard baselines that may stall in local optima due to the combinatorial explosion of the joint action space, N ON Z ERO effectively navigates the global geometry, rapidly identifying high-value coordination strategies.
To empirically validate the effectiveness of N ON Z ERO, we conduct extensive evaluations across three distinct multiagent reinforcement learning benchmarks: MatGame, the StarCraft Multi-Agent Challenge (SMAC) (Samvelyan et al., 2019), and SMACv2 (Ellis et al., 2023). Specifically, MatGame serves as a fundamental testbed that generalizes the normal-form setting to n agents, where a shared reward is derived by querying a predefined payoff tensor for simultaneous discrete actions. We compare N ON Z ERO against a comprehensive suite of state-of-the-art baselines, stratified into model-based and model-free categories. The modelbased baselines include MAZero (Liu et al., 2024), its priorfree variant MAZero-NP, and a multi-agent adaptation of MuZero (denoted as MA-AlphaZero). Furthermore, we benchmark against leading model-free algorithms, specifically MAPPO (Yu et al., 2022) and QMIX (Rashid et al., 2020b), to demonstrate the superiority of our approach.
The SMACv2 benchmark introduces significant stochasticity through randomized start positions and heterogeneous unit compositions, challenging the generalization capability of MARL algorithms. As depicted in Figure 2, the performance disparity between N ON Z ERO and the baselines is further amplified in this setting. N ON Z ERO exhibits remarkable robustness, nearly doubling the win rates on complex scenarios such as protoss 5 vs 5 and zerg 5 vs 5 compared to the best-performing baselines. While standard algorithms struggle to adapt to the highly non-stationary opponent formations, N ON Z ERO’s non-linear parameterization allows for adaptive modeling of diverse unit interactions. This confirms that capturing high-order dependencies via the learned parameter θ is crucial for effective generalization in multi-agent environments.
Experiment setting. All experiments are conducted on a cluster equipped with NVIDIA RTX A6000. We implement a training framework following EfficientZero (Ye et al., 2021) to decouple interaction, reanalysis, and learning stages. The hyperparameters for the MCTS are adjusted based on environment difficulty: for MatGame, we employ a budget of 50 simulations and sample 3 actions per node; for the SMAC and SMACv2 tasks, these parameters are scaled to 100 simulations and 7 sampled actions to accommodate the higher dimensional action space. The details of baselines and benchmarks could be found in Appendix C and Appendix D.
Ablation study. To rigorously assess the contribution of the core components within N ON Z ERO, we conduct an ablation analysis by selectively removing the mixing net and the curvature-aware optimization mechanism. We perform this evaluation on two MatGame maps to test performance under varying complexity. As illustrated in Figure 3, we compare the full N ON Z ERO model against three variants: (1) w/o Mixing Net, which removes the hypernetwork-based parameter initialization; (2) w/o Curvature, which falls back to first-order gradient updates without second-order estimation; and (3) w/o Both, which excludes both modules.
Performance evaluation. N ON Z ERO consistently outperforms all baselines across the 8 MatGame configurations reported in Table 1. While the gains are modest in lowerdimensional settings, the performance margin widens significantly as problem complexity scales, reaching an improvement of approximately 14% in the 8-agent scenarios with a 108 joint action space. This trend supports the conclusion that projecting high-dimensional returns into a low-dimensional space effectively mitigates the curse of dimensionality. Crucially, N ON Z ERO excels in nonlinear reward structures where standard methods struggle; by leveraging curvature information via second-order estimation, our approach avoids the local-optima stagnation common in global-optimism-based baselines. Furthermore, this exploration efficiency is achieved without prohibitive computational costs due to the action-dimension-free nature of the underlying bandit solver.
The results unequivocally demonstrate that both components are indispensable. The variant w/o Both exhibits the poorest performance, failing to achieve effective coordination. Notably, removing the curvature information results in a more severe performance degradation than removing the mixing net. This empirically validates our theoretical assertion: while the mixing net provides a valuable structural prior for initializing θ, the curvature-aware optimization is the primary driver for navigating the non-linear reward landscape. The full N ON Z ERO model effectively integrates both mechanisms to achieve superior nonlinear modeling capability and sample efficiency.
Figure 1 illustrates the comparative performance on three representative SMAC maps. N ON Z ERO establishes state-ofthe-art among the compared baselines, achieving a win rate exceeding 96% across all tasks while consistently outper7
NonZero: Nonlinear Search for Multi-Agent RL Table 1. Performance comparison on the MatGame benchmark across varying numbers of agents and action dimensions, encompassing both linear and non-linear reward landscapes. NonZero demonstrates superior sample efficiency and asymptotic performance compared to MCTS and MARL baselines, particularly in high-dimensional settings with limited simulation budgets. Notably, the performance gap is most pronounced in non-linear scenarios with to 14% improvement, as curvature-aware exploration effectively prevents the local stagnation observed in baseline methods. See Appendix D for detailed environmental specifications.
Agent Action Type Steps MAZero MAZero-NP MA-AlphaZero MAPPO QMIX NonZero(Ours) 2 3 Linear 500 51.9 ± 2.3 49.7 ± 3.9 50.8 ± 3.2 50.2 ± 2.9 50.4 ± 3.5 54.7 ± 0.8 55.2 ± 2.7 56.4 ± 3.1 54.3 ± 3.17 59.8 ± 0.3 2 3 Linear 1000 57.8 ± 2.4 53.1 ± 3.3 2 3 Non-Linear 500 49.1 ± 15.3 48.9 ± 17.2 49.0 ± 16.4 49.1 ± 19.1 48.7 ± 18.6 49.7 ± 7.8 2 3 Non-Linear 1000 47.6 ± 14.7 49.3 ± 14.3 49.2 ± 12.9 49.5 ± 18.1 49.1 ± 17.7 49.9 ± 16.3 4 5 Linear 1000 175.2 ± 4.4 171.7 ± 5.6 172.7 ± 4.1 173.1 ± 5.4 171.8 ± 4.9 186.2 ± 4.1 4 5 Linear 2000 191.7 ± 2.3 190.1 ± 1.2 190.4 ± 1.9 189.8 ± 2.1 190.2 ± 1.8 198.9 ± 2.3 4 5 Non-Linear 1000 179.4 ± 11.7 173.2 ± 10.0 174.5 ± 9.3 173.1 ± 8.0 174.7 ± 9.4 184.1 ± 12.2 4 5 Non-Linear 2000 195.4 ± 20.0 192.4 ± 12.8 192.7 ± 11.4 191.9 ± 12.5 190.3 ± 10.7 199.1 ± 20.7 6 8 Linear 1000 393.7 ± 9.9 387.2 ± 10.1 389.3 ± 8.4 390.6 ± 9.2 386.1 ± 10.4 398.2 ± 8.9 6 8 Linear 2000 434.2 ± 7.2 427.3 ± 9.3 432.6 ± 9.5 431.8 ± 8.4 430.1 ± 9.5 441.3 ± 6.5 6 8 Non-Linear 1000 399.8 ± 13.7 391.3 ± 10.3 393.1 ± 12.1 388.8 ± 13.1 390.5 ± 12.2 412.5 ± 9.2 6 8 Non-Linear 2000 443.9 ± 12.1 429.1 ± 9.3 427.1 ± 8.6 430.1 ± 8.5 431.7 ± 7.6 457.2 ± 13.7 8 10 Linear 1000 618.8 ± 16.9 608.8 ± 17.6 613.1 ± 13.1 617.1 ± 11.1 612.7 ± 15.4 641.3 ± 16.4 8 10 Linear 2000 692.7 ± 14.5 671.5 ± 13.9 654.3 ± 14.5 681.8 ± 12.5 679.4 ± 12.7 712.4 ± 16.2 8 10 Non-Linear 1000 615.2 ± 18.7 536.6 ± 24.1 573.2 ± 22.7 561.4 ± 20.9 558.7 ± 19.1 637.2 ± 17.1 8 10 Non-Linear 2000 672.3 ± 16.1 587.2 ± 18.4 633.2 ± 15.6 657.1 ± 17.3 648.2 ± 18.75 697.1 ± 16.4 3m NonZero MAZero MAZero-NP MA-AlphaZero QMIX MAPPO
1.0 0.8
0.4 0.2
0.8
0.6 0.4
10000
20000 30000 Training Steps
40000
50000
0.4
0.0
0.0 0
0.6
0.2
0.2
0.0
NonZero MAZero MAZero-NP MA-AlphaZero QMIX MAPPO
1.0
Win Rate
0.6
Win Rate
Win Rate
0.8
2m_vs_1z
so_many_baneling
NonZero MAZero MAZero-NP MA-AlphaZero QMIX MAPPO
1.0
0
10000
20000 30000 Training Steps
40000
50000
0
10000
20000 30000 Training Steps
40000
50000
Figure 1. Evaluations on 3 SMAC tasks/maps. Y-axis denotes the win rate and X-axis denotes training steps. Each algorithm is executed with 3 random seeds. NonZero achieves over 96% winning rate on all 3 maps, outperforming all baselines and also gets high winning rate much faster. Terran_5_vs_5
0.35
0.5 0.4
0.25
Win Rate
Win Rate
0.30
Zerg_5_vs_5
NonZero MAZero MAZero-NP MA-AlphaZero QMIX MAPPO
0.20 0.15 0.10
0.4
NonZero MAZero MAZero-NP MA-AlphaZero QMIX MAPPO
0.3
0.3 0.2 0.1
0.05 0.00 0.0
Protoss_5_vs_5
NonZero MAZero MAZero-NP MA-AlphaZero QMIX MAPPO Win Rate
0.40
0.2
0.1
0.0 0.2
0.4
Training Steps
0.6
0.8
1.0 1e6
0.0
0.2
0.4
Training Steps
0.6
0.8
1.0 1e6
0.0
0.2
0.4
Training Steps
0.6
0.8
1.0 1e6
Figure 2. Comparisons on 3 SMACv2 tasks/maps.Y-axis denotes the win rate and X-axis denotes the training steps. NonZero nearly doubles the winning rate on these challenging maps in SMACv2 and consistently outperforms all baselines. Each algorithm is executed with 3 random seeds.
5. Conclusion
candidate proposal as a nonlinear bandit subproblem, enabling curvature-aware exploration through mixed second differences rather than continuous action gradients. Under our modeling assumptions, we establish a sublinear regret guarantee whose sample complexity does not scale with |A|, and empirically demonstrate improved performance and sample efficiency on MatGame, SMAC, and SMACv2 compared to strong model-based and model-free baselines.
We proposed N ON Z ERO, a scalable multi-agent MCTS framework that avoids enumerating the exponential jointaction space |A| = dn by maintaining a small per-node candidate set and proposing new joint actions using discrete first-order and mixed second-order differences. We model joint-action returns with an asinh-GLM surrogate and cast
8
NonZero: Nonlinear Search for Multi-Agent RL Linear MatGame: 6 Agents, 8 Actions
500
NonZero w/o Mixing Net w/o Curvature w/o Both
700
400
600
350
500
Mean Score
Mean Score
Non-Linear MatGame: 8 Agents, 10 Actions
NonZero w/o Mixing Net w/o Curvature w/o Both
450
300
reinforcement learning. In MILCOM 2025-2025 IEEE Military Communications Conference (MILCOM), pp. 1518–1523. IEEE, 2025.
400
250 300
200 150
Kalai, A. T. and Sastry, R. The isotron algorithm: Highdimensional isotonic regression. In COLT, volume 1, pp. 9, 2009.
200 0
200
400
600
800 1000 Training Steps
1200
1400
1600
1800
0
200
400
600
800 1000 Training Steps
1200
1400
1600
1800
Figure 3. Ablation study of NonZero by removing various design components, including the mixing net for initializing the parameter θ and the Hessian for curvature-aware optimization. Full NonZero shows large performance gain compared with that without any of the key modules.
Kocsis, L. and Szepesvári, C. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282–293. Springer, 2006. Kwak, Y., Hwang, I., Kim, D., Lee, S., and Zhang, B.T. Efficient monte carlo tree search via on-the-fly state-conditioned action abstraction. arXiv preprint arXiv:2406.00614, 2024.
Impact Statement This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Leisiazar, S., Park, E. J., Lim, A., and Chen, M. An mcts-drl based obstacle and occlusion avoidance methodology in robotic follow-ahead applications. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 221–228. IEEE, 2023.
References Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43, 2012.
Li, Y., Tang, S., Chen, R., Yu, F. X., Jiang, G., Imani, M., Bastian, N. D., and Lan, T. Acdzero: Graph-embeddingbased tree search for mastering automated cyber defense. arXiv preprint arXiv:2601.02196, 2026a.
Dong, K., Yang, J., and Ma, T. Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature. Advances in neural information processing systems, 34:26168–26182, 2021.
Li, Y., Tang, S., and Lan, T. Reason in chains, learn in trees: Self-rectification and grafting for multi-turn agent policy optimization. arXiv preprint arXiv:2604.07165, 2026b. Liu, Q., Ye, J., Ma, X., Yang, J., Liang, B., and Zhang, C. Efficient multi-agent reinforcement learning by planning. arXiv preprint arXiv:2405.11778, 2024.
Ellis, B., Cook, J., Moalla, S., Samvelyan, M., Sun, M., Mahajan, A., Foerster, J., and Whiteson, S. Smacv2: An improved benchmark for cooperative multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 36:37567–37593, 2023.
Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Pieter Abbeel, O., and Mordatch, I. Multi-agent actor-critic for mixed cooperative-competitive environments. Advances in neural information processing systems, 30, 2017.
Fang, Z., Lan, T., and Imani, M. Mint: Minimal information neuro-symbolic tree for objective-driven knowledgegap reasoning and active elicitation. arXiv preprint arXiv:2602.05048, 2026.
Mei, Y., Zhou, H., Lan, T., Venkataramani, G., and Wei, P. Mac-po: Multi-agent experience replay via collective priority optimization. arXiv preprint arXiv:2302.10418, 2023.
Ha, D., Dai, A., and Le, Q. V. Hypernetworks. arXiv preprint arXiv:1609.09106, 2016.
Nesterov, Y. and Polyak, B. T. Cubic regularization of newton method and its global performance. Mathematical programming, 108(1):177–205, 2006.
Hernandez-Leal, P., Kartal, B., and Taylor, M. E. A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems, 33(6):750– 797, 2019.
Oliehoek, F. A., Amato, C., et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
Hubert, T., Schrittwieser, J., Antonoglou, I., Barekatain, M., Schmitt, S., and Silver, D. Learning and planning in complex action spaces. In International Conference on Machine Learning, pp. 4476–4486. PMLR, 2021.
Rashid, T., Farquhar, G., Peng, B., and Whiteson, S. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in neural information processing systems, 33: 10199–10210, 2020a.
Jiang, G., Imani, M., Bastian, N. D., and Lan, T. Agentic ai for cyber defense: Llm-guided hierarchical multi-agent 9
NonZero: Nonlinear Search for Multi-Agent RL
Rashid, T., Samvelyan, M., De Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S. Monotonic value function factorisation for deep multi-agent reinforcement learning. Journal of Machine Learning Research, 21(178):1–51, 2020b.
Ye, W., Liu, S., Kurutach, T., Abbeel, P., and Gao, Y. Mastering atari games with limited data. Advances in neural information processing systems, 34:25476–25488, 2021. Yu, C., Velu, A., Vinitsky, E., Gao, J., Wang, Y., Bayen, A., and Wu, Y. The surprising effectiveness of ppo in cooperative multi-agent games. Advances in neural information processing systems, 35:24611–24624, 2022.
Samvelyan, M., Rashid, T., de Witt, C. S., Farquhar, G., Nardelli, N., Rudner, T. G. J., Hung, C.-M., Torr, P. H. S., Foerster, J., and Whiteson, S. The StarCraft Multi-Agent Challenge. CoRR, abs/1902.04043, 2019.
Zhang, T., Li, Y., Wang, C., Xie, G., and Lu, Z. Fop: Factorizing optimal joint policy of maximum-entropy multiagent reinforcement learning. In International conference on machine learning, pp. 12491–12500. PMLR, 2021.
Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839): 604–609, 2020.
Zhang, Z., Zhou, H., Imani, M., Lee, T., and Lan, T. Learning to collaborate with unknown agents in the absence of reward. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 14502–14511, 2025.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. Mastering the game of go without human knowledge. nature, 550(7676):354–359, 2017.
Zhang, Z., Tang, S., and Lan, T. Cochain perspectives on temporal-difference signals for learning beyond markov dynamics. arXiv preprint arXiv:2602.06939, 2026.
Sironi, C. F., Liu, J., and Winands, M. H. Self-adaptive monte carlo tree search in general game playing. IEEE Transactions on Games, 12(2):132–144, 2018.
Zhou, H., Lan, T., and Aggarwal, V. Pac: Assisted value factorization with counterfactual predictions in multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 35:15757–15769, 2022.
Son, K., Kim, D., Kang, W. J., Hostallero, D. E., and Yi, Y. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International conference on machine learning, pp. 5887–5896. PMLR, 2019. Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv:1706.05296, 2017. Tang, S., Chen, J., and Lan, T. Malinzero: Efficient lowdimensional search for mastering complex multi-agent planning. arXiv preprint arXiv:2511.06142, 2025. Tang, S., Chen, R., and Lan, T. Agent alpha: Tree search unifying generation, exploration and evaluation for computeruse agents. arXiv preprint arXiv:2602.02995, 2026. Wang, T., Wang, J., Zheng, C., and Zhang, C. Learning nearly decomposable value functions via communication minimization. arXiv preprint arXiv:1910.05366, 2019. Wang, Y., Han, B., Wang, T., Dong, H., and Zhang, C. Dop: Off-policy multi-agent decomposed policy gradients. In International conference on learning representations, 2020. Xiao, Y., Liu, J., and Zhuo, H. H. Balmcts: Balancing objective function and search nodes in mcts for constraint optimization problems. arXiv preprint arXiv:2312.15864, 2023. 10
NonZero: Nonlinear Search for Multi-Agent RL
A. Proofs A.1. Justification of Assumption 3.2 In this section, we justify the existence of the smoothness constants ζ1 , ζ2 , ζ3 by modeling the discrete reward function η(θ, a) as a restriction of a smooth function operating on a continuous latent embedding space. This is a standard theoretical framework in discrete optimization and representation learning. Continuous Latent Representation. Let ϕ : A → Z ⊆ Rd be an embedding function mapping discrete joint actions to a continuous compact domain Z. We assume the reward function admits a decomposition: η(θ, a) = F (θ, ϕ(a)),
(16)
where F (θ, ·) : Rd → R is a C 3 -smooth function (e.g., a neural network with smooth activation functions like Softplus, SiLU, or Asinh). Relation between Discrete Difference and Continuous Gradients. For any agent index i and action change u (moving from a to a(u) ), let δu ≜ ϕ(a(u) ) − ϕ(a) be the displacement vector in the embedding space. The discrete difference operator ∆u is linked to the directional derivative via the Mean Value Theorem. I. Bound on First-Order Difference (ζ1 ).
By the first-order Taylor expansion with Lagrangian remainder:
∆u η(θ, a) = F (θ, ϕ(a) + δu ) − F (θ, ϕ(a)) = ∇z F (θ, ξ)T δu ,
(17)
where ξ ∈ [ϕ(a), ϕ(a(u) )]. Assuming F is L1 -Lipschitz continuous with respect to the embedding: |∆u η(θ, a)| ≤ sup ∥∇z F (θ, z)∥2 · max ∥δu ∥2 . a,u
z∈Z
(18)
Defining ζ1 ≜ L1 · Dmax where Dmax is the maximum embedding distance, the bound holds: |∆u η(θ, a)| ≤ ζ1 .
(19)
II. Bound on Second-Order Difference (ζ2 ). The second-order difference ∆2u,v captures the interaction between agent u and agent v. ∆2u,v η(θ, a) = ∆v (∆u η(θ, a)) = η(θ, a(u,v) ) − η(θ, a(u) ) − η(θ, a(v) ) + η(θ, a).
(20)
Using the second-order Taylor expansion for multivariate functions: F (z + δu + δv ) − F (z + δu ) − F (z + δv ) + F (z) = δuT ∇2z F (θ, ξ ′ )δv ,
(21)
where ∇2z F is the Hessian matrix and ξ ′ is an intermediate point. If the spectral norm of the Hessian is bounded by L2 (i.e., F is L2 -smooth): 2 |∆2u,v η(θ, a)| ≤ ∥δu ∥2 ∥∇2z F (θ, ξ ′ )∥2 ∥δv ∥2 ≤ L2 Dmax . (22) 2 Thus, we set ζ2 ≜ L2 Dmax . This directly reflects the bounded pairwise interaction strength in the system.
III. Bound on Third-Order Difference (ζ3 ). The term |∆2u,v η(θ, a(w) ) − ∆2u,v η(θ, a)| represents the variation of the Hessian (interaction strength) when the state changes by direction w. This corresponds to the third-order directional derivative (involving the tensor ∇3 F ). By the higher-order Mean Value Theorem: ∆w (∆2u,v η(θ, a)) = ∇3z F (θ, ξ ′′ )[δu , δv , δw ],
(23)
where [·, ·, ·] denotes the tensor-vector product. Assuming the Hessian is L3 -Lipschitz (bounded third derivatives): |∆3u,v,w η(θ, a)| ≤ sup ∥∇3z F (θ, z)∥op · ∥δu ∥∥δv ∥∥δw ∥. z
3 Setting ζ3 ≜ L3 Dmax , the assumption is satisfied.
The constants ζ1 , ζ2 , ζ3 are theoretically guaranteed to exist and are finite provided that: 11
(24)
NonZero: Nonlinear Search for Multi-Agent RL
1. The reward function η admits a smooth parameterization (e.g., asinh-GLM or Neural Networks). 2. The embedding space Z is compact. 3. The derivatives of the link function/activation function are bounded. This confirms that Assumption 3.2 is a direct consequence of standard smoothness properties in the continuous latent space. A.2. Proof of Lemma 3.3 Lemma 3.3 (Restated). Let f (a) = η̃(θ∗ , a). Provided at ∈ / Aϵ,6√ζ3rd ϵ , the update yields: f (at+1 ) − f (at ) ≥ ν(ϵ) − C1 · ξt+1 , where ν(ϵ) ≜ c1 min
ϵ2 ϵ3/2 ζh +1 , ζ 1/2
(25)
and C1 = 2 + ζg /ζh .
3rd
Proof. Let zt = ϕ(at ). Define the true gradient gt ≜ ∇z f (zt ) and the surrogate gradient ĝt ≜ ∇z fˆt (zt ). Define the estimation error vector et ≜ ĝt − gt . By the loss definition, ∥et ∥2 ≤ ξt+1 . We analyze the update zt+1 = zt + dt in the latent space. Case I: First-Order Dominance (∥gt ∥ > ϵ). The algorithm performs an approximate steepest ascent step using the surrogate gradient: dt = ζ1h ĝt = ζ1h (gt + et ). Applying the Descent Lemma to the ζh -smooth function f , we expand the reward increment: ζh ∥dt ∥2 2 2 1 ζh gt + et = ⟨gt , gt + et ⟩ − ζh 2 ζh 1 1 = ∥gt ∥2 + ⟨gt , et ⟩ − ∥gt ∥2 + 2⟨gt , et ⟩ + ∥et ∥2 ζ 2ζh h 1 1 1 1 1 = − ∥gt ∥2 − ∥et ∥2 ⟨gt , et ⟩ + ∥gt ∥2 − ζh ζh ζh 2ζh 2ζh 1 1 = ∥gt ∥2 − ∥et ∥2 . 2ζh 2ζh
f (at+1 ) − f (at ) ≥ ⟨gt , dt ⟩ −
(26)
Remark: The exact cancellation of the linear error term ⟨gt , et ⟩ is due to the optimality of the step size 1/ζh for the surrogate. Substituting ∥gt ∥ > ϵ and ∥et ∥2 ≤ ξt+1 : f (at+1 ) − f (at ) ≥
1 ϵ2 1 ϵ2 − ξt+1 ≥ − ξt+1 . 2ζh 2ζh 2(ζh + 1) 2ζh
(27)
√ Case II: Second-Order Dominance (Cubic Regime). Condition: ∥gt ∥ ≤ ϵ and λmin (∇2 f ) < −6 ζ3rd ϵ. The update follows the cubic regularization of the surrogate. Standard analysis (Nesterov & Polyak, 2006) on a manifold with ζ3rd -Lipschitz Hessian guarantees that the optimal step d∗fˆ for the surrogate satisfies: |λmin (∇2 fˆ)|3 fˆ(zt + d∗fˆ) − fˆ(zt ) ≥ ccubic ≈ O(ϵ3/2 ). 2 ζ3rd
(28)
Transferring this bound to the true function f involves the Hessian estimation error. Crucially, since d∗fˆ is a stationary point of the cubic model of fˆ, the first-order error terms vanish, leaving only second-order degradation: ϵ3/2 ϵ3/2 f (at+1 ) − f (at ) ≥ ccubic √ − Ccurv · ∥et ∥2 ≥ ccubic √ − Ccurv · ξt+1 . ζ3rd ζ3rd 12
(29)
NonZero: Nonlinear Search for Multi-Agent RL
Synthesis. We unify Eq. (27) and Eq. (29). Define the unified coefficient c1 ≜ min{1/2, ccubic } and the error coefficient Copt ≜ max{ 2ζ1h , Ccurv }. The lower bound becomes: f (at+1 ) − f (at ) ≥ c1 min
ϵ2 ϵ3/2 ,√ ζh + 1 ζ3rd
− Copt · ξt+1
= ν(ϵ) − Copt · ξt+1 .
(30)
Finally, we verify the constant C1 . The Lemma defines C1 = 2 + ζg /ζh . Assuming normalized smoothness ζh ≥ 0.5, we have C1 > 2 > 2ζ1h . Similarly, for standard cubic regularization constants, C1 is a loose upper bound for Ccurv . Subtracting a larger error term tightens the inequality (valid a fortiori): f (at+1 ) − f (at ) ≥ ν(ϵ) − C1 · ξt+1 .
(31)
This concludes the proof. A.3. Proof of Lemma 3.4 Notations and Problem Setting. Let Z = X × Y be the data space. We define the hypothesis class F = {fθ : θ ∈ Θ} with Θ ⊂ Rd . The algorithm generates a sequence of hypotheses f1 , . . . , fT adapted to the filtration Ft−1 = P4 σ((x1 , y1 ), . . . , (xt−1 , yt−1 )). The instantaneous loss is ℓt (f ) = k=1 (Dk f (xt ) − yt,k )2 , where Dk are linear difference operators. Let ξt = ℓt (ft ) be the realized prediction error. We assume bounded targets and predictions, implying ℓt (f ) ∈ [0, B 2 ] almost surely. Proof. The proof proceeds in three steps: (1) Martingale concentration to relate realized error to expected risk; (2) Symmetrization to introduce Sequential Rademacher Complexity; (3) Structural decomposition of the complexity for the NonZero architecture. Step PT 1: Martingale Concentration and Online-to-Batch Conversion. We aim to bound the cumulative error ST = t=1 ξt . Let Rt (f ) = Ezt ∼Dt [ℓ(f, zt ) | Ft−1 ] be the conditional expected risk. Define the martingale difference sequence Mt = ξt − Rt (ft ). Since |ξt | ≤ B 2 , by the Azuma-Hoeffding inequality, with probability 1 − δ/2: T X
(ξt − Rt (ft )) ≤ B 2
p
2T log(2/δ).
(32)
t=1
Rearranging, we bound the realized error by the sum of risks: T X
ξt ≤
t=1
T X
√ Rt (ft ) + Õ( T ).
(33)
t=1
Crucially, in the absence of strong convexity (the ”slow rate” regime), we cannot assume Rt (ft ) decays as 1/t. Instead, we PT bound the cumulative excess risk against the best comparator f ∗ ∈ F. Let LT (F) = supf ∈F t=1 (Rt (ft ) − ℓt (f )). This leads to the standard regret bound form: T X
Rt (ft ) ≤ inf
f ∈F
t=1
T X t=1
ℓt (f ) + sup
T X (E[ℓt (f ) | Ft−1 ] − ℓt (f )).
(34)
f ∈F t=1
The second term is bounded by the Sequential Rademacher Complexity Rseq T (ℓ ◦ F ) via the ghost sample symmetrization technique (Rakhlin et al., 2010): "
# T X E sup (Rt (f ) − ℓt (f )) ≤ 2Rseq T (ℓ ◦ F ). f ∈F t=1
13
(35)
NonZero: Nonlinear Search for Multi-Agent RL
Step 2: Deriving the T 3/4 Bound. In the realizable setting (inf √ Loss = 0), the cumulative error is dominated by the complexity. However, a direct application of Azuma yields an O( T ) bound only if the complexity itself is constant. Here, the complexity grows. We invoke the refined bound for squared loss functions from Srebro et al. (2010) and Foster et al. (2018). For non-negative smooth losses, the cumulative error is bounded by the root of the complexity times the horizon: T X
ξt ≤
p
T · K(F),
(36)
t=1
where K(F ) is the effective capacity. Identifying K(F ) ≈ Rseq T (ℓ ◦ F), we rigorously establish the form stated in the Lemma: T q X √ (37) ξt ≤ T · Rseq T (ℓ ◦ F ) + Õ( T ). If Rseq T ∝
√
√ T , this yields
t=1
T · T 1/2 = T 3/4 .
Step 3: Calculating the Complexity Rseq T (ℓ ◦ F). We now strictly derive the complexity bound using operator theory. The loss ℓ(f ) = ∥h(f ) − y∥22 is Lℓ -Lipschitz wrt h = (D1 f, . . . , D4 f ). By the vector-valued Talagrand’s Contraction Lemma: 4 X Rseq (ℓ ◦ F ) ≤ L Rseq (38) ℓ T T (Dk ◦ F ). k=1 seq (u) For any linear operator D (shift, difference), Rseq ) − f (a), we T (D ◦ F ) = RT ({Df | f ∈ F}). Since ∆u f (a) = f (a
have R(∆ ◦ F ) ≤ 2R(F ). Thus: 4 X
seq seq Rseq T (Dk ◦ F ) ≤ (1 + 1 + 2 + 4)RT (F) = 8RT (F).
(39)
k=1
Recall f (a) = σ(⟨w, ϕ(a)⟩) with σ = c · asinh. Since σ is cα-Lipschitz: seq Rseq T (F) ≤ cα · RT (Flin ),
where Flin = {a 7→ ⟨w, ϕ(a)⟩ : ∥w∥ ≤ W }. For the linear class with bounded norms W and X: √ Rseq T (Flin ) ≤ W X T . Substituting back up the chain: Rseq T (ℓ ◦ F ) ≤ (8Lℓ cαW X) | {z }
√
√ T = Õ( T ).
(40)
(41) (42)
Cconst
Substituting Eq. (42) into Eq. (37): T X
q ξt ≤
p √ √ √ T · Cconst T + Õ( T ) = Cconst T 3/4 + Õ( T ).
(43)
t=1
Since T 3/4 dominates
√
T for large T : T X
ξt ≤ Õ(T 3/4 ).
(44)
t=1
This completes the proof. A.4. Proof of Theorem 3.5 This proof unifies the geometric landscape analysis (Lemma 3.3) and the statistical generalization bound (Lemma 3.4) to derive the convergence rate of the NonUCT algorithm. 1. Definitions and Problem Setup 14
NonZero: Nonlinear Search for Multi-Agent RL
• Let A∗ϵ ≜ Aϵ,6√ζ3rd ϵ be the set of (ϵ, ϵH )-approximate local maximizers. • Define the instantaneous regret indicator It ≜ I{at ∈ / A∗ϵ }. • The cumulative regret (in termsP of sample complexity to find a local optimum) is defined as the number of visits to T non-optimal states: RegretT ≜ t=1 It . • Let f (a) ≜ η̃(θ∗ , a) denote the ground-truth reward function. We assume bounded rewards, i.e., f (a) ∈ [0, Df ] for all a ∈ A. Without loss of generality, we normalize Df = 1. • Let ξt+1 be the prediction error at step t + 1, bounded in expectation by Lemma 3.4. Proof. The derivation proceeds via a telescoping sum argument on the reward trajectory, analyzing the trade-off between guaranteed ascent and accumulated estimation error. Step 1: One-Step Conditional Improvement. Recall Lemma 3.3 (One-step Geometric Improvement). At any step t, if the current action at is not a local maximizer (i.e., It = 1), the curvature-guided update ensures a reward increase, modulo the estimation error: f (at+1 ) − f (at ) ≥ ν(ϵ) − C1 ξt+1 , if It = 1. (45) If at is already a local maximizer (It = 0), the algorithm may explore or oscillate. In the worst case, the reward could decrease, but since we are bounding the number of steps until convergence (or counting non-optimal steps), we focus on the contribution of It . Combining both cases, we write the conditional inequality: f (at+1 ) − f (at ) ≥ ν(ϵ)It − C1 ξt+1 − ∆drop (1 − It ),
(46)
where ∆drop accounts for potential value drops in optimal regions. However, for the purpose of bounding the ”hitting time” or the regret defined as visits to suboptimal states, we rearrange to isolate the positive indicator It : ν(ϵ)It ≤ (f (at+1 ) − f (at )) + C1 ξt+1 + ∆drop (1 − It ).
(47)
Remark: In standard non-convex analysis (e.g., finding stationary points), we bound the sum of indicators. The term (1 − It ) corresponds to steps where we are already in the target set A∗ϵ , contributing 0 to the specific definition of Regret used in ”finding” problems. Thus, we focus on summing the inequality over the trajectory. Step 2: Telescoping Sum over Trajectory. ν(ϵ)
T X
Summing Eq. (46) from t = 1 to T :
It ≤
t=1
T X
(f (at+1 ) − f (at )) + C1
t=1
T X
ξt+1 .
(48)
t=1
The first term on the RHS is a telescoping sum: T X
(f (at+1 ) − f (at )) = f (aT +1 ) − f (a1 ) ≤ max f (a) − min f (a) ≤ Df = 1. a
t=1
a
(49)
Substituting this back, we obtain a path-wise bound: ν(ϵ) · RegretT ≤ 1 + C1
T X
ξt+1 .
(50)
t=1
Step 3: Integrating Statistical Complexity. We take the expectation of both sides with respect to the algorithm’s randomness and data generation process. By the linearity of expectation: " T # X ν(ϵ) · E[RegretT ] ≤ 1 + C1 E ξt+1 . (51) t=1
15
NonZero: Nonlinear Search for Multi-Agent RL
We invoke Lemma 3.4 (Estimation Error Control), which states that the cumulative error is bounded by the sequential Rademacher complexity: " T # X p ξt+1 ≤ 4T RT . (52) E t=1
(Note: The factor 4 accounts for the four components of the supervision signal yt ∈ R4 in the vector-valued Talagrand contraction). Substituting this bound: p ν(ϵ) · E[RegretT ] ≤ 1 + C1 4T RT . (53) Step 4: Introducing the Landscape Complexity K(ϵ). We define the complexity term K(ϵ) as the inverse of the guaranteed improvement rate ν(ϵ). Recall from Lemma 3.3: ( ) ϵ2 ϵ3/2 ν(ϵ) = c1 min , . (54) ζh + 1 ζ 1/2 3rd
Inverting this expression implies that the required steps scale with the maximum of the inverses: √ 1 ζ3rd ζh + 1 1 = , 3/2 max . K(ϵ) ≜ ν(ϵ) c1 ϵ2 ϵ
(55)
Absorbing the constant 1/c1 into the notation (or setting c1 appropriately), we recover the definition in the Theorem statement: p K(ϵ) = max 4ζh ϵ−2 , ζ3rd ϵ−3/2 . (56) Step 5: Final Bound Derivation.
Dividing the inequality from Step 3 by ν(ϵ) (equivalently, multiplying by K(ϵ)): p 1 1 + C1 4T RT E[RegretT ] ≤ ν(ϵ) p = K(ϵ) 1 + C1 4T RT p = (1 + C1 4T RT ) · K(ϵ). (57)
This completes √ the proof. The regret scales linearly with the landscape difficulty K(ϵ) and sub-linearly with the time horizon T (via the T term in RT ), ensuring convergence to the set of approximate local maximizers. A.5. Proof of Corollary 3.6 Prerequisites. From Theorem 3.5, the expected cumulative regret is bounded by: p E[RegretT ] ≤ (1 + C1 4T RT ) · K(ϵ).
(58)
From Lemma 3.4 (Proof Step 3), the Sequential Rademacher Complexity scales as: √ RT ≜ Rseq T (ℓ ◦ F ) ≤ Cstat T ,
(59)
where Cstat = 8Lℓ cαW X is a problem-dependent constant independent of T . Proof. The proof follows by direct substitution and dominance analysis. Step 1: Substitution of Complexity Bound.
Substituting Eq. (59) into Eq. (58): q √ E[RegretT ] ≤ K(ϵ) + C1 K(ϵ) 4T · Cstat T p p = K(ϵ) + C1 K(ϵ) 4Cstat · T · T 1/2 p = K(ϵ) + 2C1 Cstat K(ϵ) · T 3/4 . 16
(60)
NonZero: Nonlinear Search for Multi-Agent RL
Step 2: Aggregation of Constants. Let Cgeo ≜ K(ϵ) denote the geometric complexity constant (dependent on ϵ−2 , ζh ). √ Let Ctotal ≜ 2C1 Cstat Cgeo denote the aggregate coefficient. The bound simplifies to: E[RegretT ] ≤ Cgeo + Ctotal · T 3/4 .
(61)
Step 3: Asymptotic Analysis. For sufficiently large T , the term T 3/4 dominates the constant term Cgeo . We utilize the Soft-O notation Õ(·) to suppress polylogarithmic factors and constants independent of the horizon T . Since ϵ, ζh , ζ3rd are fixed parameters of the problem instance and target precision: Cgeo E[RegretT ] lim ≤ lim + C total T →∞ T →∞ T 3/4 T 3/4 = Ctotal . (62) Thus, strictly bounding the order with respect to T : E[RegretT ] = Õ(T 3/4 ).
(63)
This confirms the sub-linear convergence rate characteristic of non-convex optimization under the ”slow rate” statistical regime. A.6. Proof of Theorem 3.7 Qn Definitions and Notations. Let A = i=1 Ai be the joint action space with cardinality K ≜ |A| = dn . We denote the class of unstructured reward functions by Eflat = {f : A → [0, 1]}. We denote the class of asinh-GLM reward functions (NonZero hypothesis) by Estruct ⊂ Eflat . The sample complexity TA (ϵ, δ) of an algorithm A is defined as the minimal stopping time τ satisfying: PA,f [f (a∗ ) − f (aout ) ≤ ϵ] ≥ 1 − δ, ∀f ∈ E. (64) Proof. The proof derives the minimax lower bound for Eflat and contrasts it with the problem-dependent upper bound for Estruct . Step 1: Minimax Lower Bound for Unstructured UCB. Any generic UCB algorithm treating actions as independent arms faces the minimax lower bound for Multi-Armed Bandits (MAB). We utilize the standard hypothesis testing construction. Construct a set of K hard instances {ν1 , . . . , νK } ⊂ Eflat such that in instance i, action ai is optimal with mean µ + ∆, while all aj̸=i have mean µ. By the Bretagnolle-Huber inequality applied to the canonical bandit model (Lattimore & Szepesvári, 2020), distinguishing these hypotheses requires sufficient information gain. The minimax sample complexity is lower-bounded by the sum of inverse squared gaps: inf sup E[TA (ϵ)] ≥ c1 A f ∈Eflat
K ∆−2 ≈ c1 2 . ϵ ∗
X
(65)
a̸=a
Substituting K = dn , we obtain the requisite lower bound for standard UCB: TUCB (d, ϵ) ≥ Ω dn ϵ−2 .
(66)
Step 2: Structural Upper Bound for NonUCT. We convert the cumulative regret bound derived in Theorem 3.5 into a sample complexity bound. From Theorem 3.5 and Lemma 3.4, the cumulative regret scales as: p E[RegretT ] ≤ (1 + C1 4T RT )K(ϵ). (67) √ √ √ Substituting √ the explicit Rademacher complexity RT ≤ Cmodel nd T (where nd arises from the linear class complexity W X ≈ nd): q √ √ E[RegretT ] ≤ Cconst · K(ϵ) · T · nd · T = Cconst · K(ϵ) · (nd)1/4 · T 3/4 . 17
(68)
NonZero: Nonlinear Search for Multi-Agent RL
Let the output policy be the uniform mixture over the trajectory. The expected sub-optimality is bounded by the average regret: E[RegretT ] E[Gap] ≤ ≤ Cconst K(ϵ)(nd)1/4 T −1/4 . (69) T Setting the RHS to ϵ and solving for T : T −1/4 ≤
ϵ =⇒ T ≥ Cconst K(ϵ)(nd)1/4
Cconst K(ϵ) ϵ
4 (nd).
(70)
Thus, the sample complexity for NonUCT scales linearly with the dimension nd: TNonUCT (d, ϵ) ≤ poly(ϵ−1 ) · O(nd). Step 3: Derivation of the Separation Ratio ζsep . ζsep ≜
(71)
We define the ratio using Eq. (66) and Eq. (71):
cL · dn · ϵ−2 TUCB . ≥ TNonUCT CU · nd · ϵ−4 · K(ϵ)4
(72)
We isolate the dimensionality terms from the precision terms: ζsep ≥ C(ϵ) ·
dn , nd
where C(ϵ) =
cL 2 ϵ K(ϵ)−4 . CU
(73)
We expand the term dn using the exponential identity x = eln x : ln d . dn = exp(n ln d) = exp nd · d
(74)
Let c(d) ≜ lndd . For discrete action spaces d ≥ 2, c(d) ≥ ln22 > 0. Thus: dn exp(c(d) · nd) = . nd nd
(75)
Since the exponential term dominates the linear denominator poly(nd), we conclude: ζsep ≥
exp(c · nd) . poly(nd, ϵ−1 )
(76)
This formally proves the exponential separation in sample complexity.
B. Implementation Details B.1. Model Architecture The proposed N ON Z ERO framework is constructed using six distinct neural network modules: the representation function h, the communication function e, the dynamic function g, the reward function r, the value function v, and the policy function p. We define the relevant variables for each agent i as follows: sit,k represents the latent state, ait+k denotes the action, eit,k indicates the cooperative feature, and pit,k is the policy prediction. The indices t and k refer to the real-world interaction step and the internal simulation rollout step, respectively. Additionally, rt,k and vt,k correspond to the predicted global reward and value. We also apply a hyper net-based mixing function m to predict the initialization of θ with the input of the node state. The workflow begins with the representation function sit,0 = h(oi≤t ), which encodes the individual observation history oi≤t into a latent embedding, thereby enabling planning without direct access to the underlying environmental rules. To facilitate coordination, the communication function {eit,k }i:1,...,n = e {eit,k }i:1,...,n , {ait+k }i:1,...,n leverages an attention mechanism to synthesize cooperative features for every agent, taking the set of individual states and actions as input. State transitions are predicted by the dynamic function sit,k+1 = g(sit,k , ait+k , eit,k ). For evaluation, the reward function 18
NonZero: Nonlinear Search for Multi-Agent RL Table 2. Detailed hyper-parameters for NonZero across MatGame, SMAC, and SMACv2 environments.
Hyper-Parameter
Value
Hyper-Parameter
Optimizer Learning rate Weight decay RMSprop epsilon Max gradient norm Evaluation episodes Target network update interval Unroll steps TD steps Min replay size for sampling
Adam 10−4 0 10−5 5 32 200 5 5 300
Minibatch size Discount factor Priority exponent Priority correction Dynamic generation ratio λ for initialization Quantile in MCTS value est. Decay λ in MCTS value est. Exp. factor in Weighted-Advantage Stacked observations
Value 256 0.99 0.6 0.4 → 1 0.6 10−4 0.75 0.8 3 4
rt,k = r {eit,k }i:1,...,n , {ait+k }i:1,...,n and the value function vt,k = v {eit,k }i:1,...,n estimate the reward for the global state-action pair and the value of the global state, respectively. The policy function pit,k = p(sit,k ) generates the policy distribution for on its current individual latent state. And the mixing function predicts the parameter θt,k each agent based
via θt,k = m {sit,k }i:1,...,n .
With the exception of the communication function e, all neural network components are instantiated as Multi-Layer Perceptron (MLP) architectures. Within these MLPs, each linear transformation is immediately followed by Layer Normalization (LN) and a Rectified Linear Unit (ReLU) activation function. Across the three benchmarks evaluated in the experiments, the input observations are processed as 1-dimensional vectors, mapped to a hidden state dimension of 128. To mitigate partial observability, the representation network h aggregates the four most recent local observations as input for each agent. Prior to this representation step, an LN layer is applied to normalize the raw observation features. To prevent gradient vanishing during the sequential unrolling of the latent dynamics, the dynamic function g incorporates a residual connection linking the current hidden state to the next. Furthermore, following the methodology of MuZero, we employ √ a categorical representation for value and reward targets, utilizing the invertible scaling transform f (x) = sign(x) 1 + x − 1 + 0.001x to stabilize predictions. The specific depth and configuration of the hidden layers for the MLP modules are detailed as follows: • Representation function h: [128, 128]. • Dynamic function g: [128, 128]. • Reward function r, Value function v, and Policy function p: [32]. • Mixing function m: [64, 64]. B.2. Training Details Our training infrastructure follows an asynchronous distributed paradigm inspired by EfficientZero (Ye et al., 2021), effectively decoupling the concurrent processes of trajectory generation, policy reanalysis, and network optimization. To maintain high throughput, distinct worker groups are allocated to manage these parallel tasks independently. Furthermore, we align our objective formulation—specifically the advantage estimation and loss calculation mechanism—strictly with the methodology established in MAZero (Liu et al., 2024). The computational experiments are executed on high-performance computing clusters equipped with NVIDIA RTX A6000 GPUs. Regarding the hyper-parameters for Monte Carlo Tree Search (MCTS), we tailor the search budget to the complexity of the environment. In the MatGame scenarios, we employ a simulation budget of 50, with a branching factor of 3 sampled actions per node. Conversely, for the more intricate SMAC and SMACv2 benchmarks, the simulation count is increased to 100, with 7 actions sampled during the expansion phase. A comprehensive list of additional hyper-parameters is provided in Table 2. 19
NonZero: Nonlinear Search for Multi-Agent RL Table 3. Hyper-parameters for MAZero, MAZero-NP, and MA-AlphaZero across MatGame, SMAC, and SMACv2 environments.
Hyper-Parameter
Value
Hyper-Parameter
Value
Optimizer Learning rate RMSprop epsilon Weight decay Max gradient norm Evaluation episodes Target network update interval Unroll steps TD steps
Adam 10−4 10−5 0 5 32 200 5 5
Minibatch size Discount factor Priority exponent Priority correction Quantile in MCTS value est. Decay λ in MCTS value est. Exp. factor in Weighted-Advantage Stacked observations Min replay size for sampling
256 0.99 0.6 0.4 → 1 0.75 0.8 3 4 300
C. Details of Baseline Algorithms MAZero Family. We derive our implementations of MAZero (Liu et al., 2024) and its variant, MAZero-NP, from the official repository1 . The MAZero-NP variant is distinct in that it excludes prior information from the UCT bound calculation, while retaining the remainder of the architecture. Regarding the MCTS configuration, we employ 3 sampled actions and 50 simulations for MatGame tasks, whereas SMAC and SMACv2 experiments utilize 7 sampled actions and 100 simulations. Additionally, we evaluate MA-AlphaZero, which adapts the MAZero codebase to incorporate the scoring mechanism of AlphaZero (Silver et al., 2017). Specifically, the UCT selection criterion is modified to utilize raw Q-values rather than advantage scores. Given the structural similarities to MAZero, it shares the hyperparameter settings enumerated in Table 3. Model-Free Baselines. The QMIX (Rashid et al., 2020b) baseline is established using the PyMARL framework2 , with configuration details provided in Table 4 (Left). Similarly, MAPPO (Yu et al., 2022) utilizes the official on-policy benchmark implementation3 , following the specifications detailed in Table 4 (Right). Table 4. Hyper-parameters for model-free baselines. (a) QMIX Configuration
Hyper-Parameter
(b) MAPPO Configuration
Value
Hyper-Parameter
Optimizer RMSProp Learning rate (Actor) 5 × 10−4 Learning rate (Critic) 5 × 10−4 Initial ϵ 1.0 Final ϵ 0.05 Batch size 32 Buffer size 5000 Discount factor 0.99 Exploration noise 0.1
Value
Optimizer Adam Learning rate 5 × 10−4 RMSprop epsilon 10−5 Recurrent chunk length 10 Gradient clipping 10 GAE parameter 0.95 Discount factor 0.99 Value loss Huber (δ = 10) Batch size Buffer × Agents
D. Settings of Benchmarks MatGame Environments. We evaluate the performance of NonZero and baseline algorithms on the MatGame benchmark under two distinct configurations. (1) Linear Setting: The joint reward is defined strictly as the summation of the indices of all agents within the system. (2) Non-linear Setting: We introduce stochastic perturbations to the linear reward structure. Specifically, the final joint reward represents the linear sum superimposed with a noise term composed of a Gaussian component u ∼ N (0, 22 ) and a uniform component v ∼ U (−3, 3). 1
https://github.com/liuqh16/MAZero https://github.com/oxwhirl/pymarl 3 https://github.com/marlbenchmark/on-policy 2
20
NonZero: Nonlinear Search for Multi-Agent RL Table 5. Summary of experimental configurations across MatGame, SMAC, and SMACv2 benchmarks.
Benchmark
Configuration / Map Type
Key Characteristics
Noise / Variation
MatGame
Linear Non-linear
Sum of agent indices Linear sum + Noise
None u ∼ N (0, 22 ) + v ∼ U(−3, 3)
SMAC
Small, Medium, Large
Homogeneous/Fixed
3 Random Seeds
SMACv2
General Maps
Heterogeneous Units
Randomized Start Positions Modified Sight/Attack Ranges
StarCraft Multi-Agent Challenge (SMAC). Our experiments on the standard SMAC benchmark utilize the official implementation hosted at https://github.com/oxwhirl/smac. To ensure a comprehensive evaluation, we select three representative maps covering small, medium, and large scales of agent counts. All experimental results are reported as averages over 3 independent random seeds to guarantee reproducibility and statistical significance. SMACv2. For the more complex SMACv2 environments, we adopt the codebase from https://github.com/ oxwhirl/smacv2. Unlike the original SMAC, this version emphasizes generalization. In our experiments, we enforce high stochasticity by randomizing both the start positions and the heterogeneous unit types for each episode, even within the same map. Furthermore, to enhance agent diversity and tactical complexity, the unit sight ranges and attack ranges are modified compared to the original SMAC settings.
21