MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planning
Authors: Sizhe Tang
Jiayu Chen
Tian Lan
Venue: NeurIPS 2025 poster ()
Keywords: Monte Carlo Tree Search
Reinforcement Learning
Multi-Agent System
Primary area: reinforcement_learning

Abstract: Monte Carlo Tree Search (MCTS), which leverages Upper Confidence Bound for Trees (UCTs) to balance exploration and exploitation through randomized sampling, is instrumental to solving complex planning problems. However, for multi-agent planning, MCTS is confronted with a large combinatorial action space that often grows exponentially with the number of agents. As a result, the branching factor of MCTS during tree expansion also increases exponentially, making it very difficult to efficiently explore and exploit during tree search. To this end, we propose MALinZero, a new approach to leverage low-dimensional representational structures on joint-action returns and enable efficient MCTS in complex multi-agent planning. Our solution can be viewed as projecting the joint-action returns into the low-dimensional space representable using a contextual linear bandit problem formulation. We solve the contextual linear bandit problem with convex and $\mu$-smooth loss functions -- in order to place more importance on better joint actions and mitigate potential representational limitations -- and derive a linear Upper Confidence Bound applied to trees (LinUCT) to enable novel multi-agent exploration and exploitation in the low-dimensional space. We analyze the regret of MALinZero for low-dimensional reward functions and propose an $(1-\tfrac1e)$-approximation algorithm for the joint action selection by maximizing a sub-modular objective. MALinZero demonstrates state-of-the-art performance on multi-agent benchmarks such as matrix games, SMAC, and SMACv2, outperforming both model-based and model-free multi-agent reinforcement learning baselines with faster learning speed and better performance.

MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planning
Sizhe Tang
Jiayu Chen
The George Washington University s. tang1@guu. edu
Carnegie Mellon University jiayuc20andrew. cmu. edu
Tian Lan
The George Washington University tlan8gwu. edu
edu
Abstract
Monte Carlo Tree Search (MCTS), which leverages Upper Confidence Bound for Trees (UCTs) to balance exploration and exploitation through randomized sampling, is instrumental solving complex planning problems. However, for multi-agent planning, MCTS is confronted with a large combinatorial action space that often grows exponentially with the number of agents. factor of MCTS during tree expansion also increases exponentially, making it very difficult to efficiently explore and exploit during tree search. To this end, we propose MALinZero, new approach to leverage low-dimensional representational structures on joint-action returns and enable efficient MCTS in complex multi- agent planning. Our solution can be viewed as projecting the joint-action returns into the low-dimensional space representable using a contextual linear bandit problem formulation. We solve the contextual linear bandit problem with convex and p-smoooh loss functions - in order to place more importance on better joint actions and mitigate potential representational limitations and derive linear Upper Confidence Bound applied to trees (LinUCT) to enable novel multi-agent exploration and exploitation in the low-dimensional space. We analyze the regret MALinZero for low dindenniiional reward functions and propose an (1 1)- approximation algorithm for the joint action selection by maximizing sub-modular objective. MALinZero demonstrates state-of-ther performance on multi-agent benchmarks such matrix games, SMAC, and SMACv2, outperforming both model-based and model-free multi-agent reinforcement learning baselines with faster learning speed and better performance.
result, the branching
Introduction
Monte Carlo Tree Search (MCTS) has demonstrated great performance in solving complex planning
problems such as game playing [1, robotic control [2]. and optimization [ It achieves much higher data efficiency than value- or policy-based reinforcement learning (RL) 4 by leveraging Upper Confidence Bound for Trees (UCT') to balance exploration and exploitation through randomized sampling and cumulative regret minimization (5). Integrated with deep learning (c.g., AlphaZero [6] and MuZero [4),, MCTS algorithms have achieved groundbreaking results in solving complex games, such Go, Chess and Shogi 4. relying on little knowledge of domain expertise or game rules.
However, for planning problems involving multiple agents, MCTS confronted with a large combi- natorial action space that often grows exponentially with the number of agents 87. As the number of candidate actions increases, the branching factor of MCTS (during tree expansion) also increases
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

exponentially, making it very difficult to efficiently explore and exploit during tree search [9] [0]. Existing works either focus on single-agent problems or limit tree search small set of state- conditioned action abstractions
p 111. As a result, MCTS can get stuck in local optima or become slow to explore optimal actions. Recent proposals like MAZero [0] facilitate distributed represen- tation of state transitions and reward prediction in multi-agent MCTS, but again do not address the challenges relating to the combinatorial action space in multi-agent planning.
In this work, we propose MALinZero, a new approach to leverage low-dimensional representational structures and enable efficient MCTS in complex cooperative aulti-agent planning. The main idea of MALinZero is to model the joint returns through low- -iwddmensiooal linear combination of the (latent) per-agent action rewards. Thus, by observing the joint returns resulted from multi-agent actions, we can formulate contextual linear bandit problem [12] with the per-agent action rewards as an unknown parameter vector 0 - and derive a linear Upper Confidence Bound applied to trees (LinUCT), to enable novel LinUCT-based exploration and exploitation in this oow-dimensional space of (latent) per-agent action rewards. The idea of enforcing representational structures on joint returns has been instrumental in multi-agent reinforcement learning (MARL), e.g., VDN I3
with linear
representations, and QMIX [14,, NDQ [5], and PAC [16] with monotonic representations, as well as policy factorizations like DOP 1 and FOP 18]. However, these MARL results do not apply to multi-agent MCTS, which requires not only factorized action-valuee but also the use of concentration [19] to bound their probability distributions given observed samples, like in our LinUCT
inequalities
For planning problem with agents and d actions per agent, MALinZero effectively reduces the tree search from considering d' independent joint-action returns to learning nd latent per-agent action rewards. Our solution can be viewed as projecting the returns into the low-dimensional space represented by MALinZero using a contextual linear bandit problem formulation [12 (0]. To mitigate the potential representational limitations, we further introduce a strongly-convex, je-smooth distance measure f into the projection (as a new contextual bandit loss), in order to place more importance on not underestimating the better joint actions, while not overestimating the less attractive joint actions 22I We solve the resulting contextual linear bandit problem with this convex loss and prove that our LinUCT achieves cumulative regret of Rr- O(nd VuTT In(T)) after T steps for low- dimensional rewards. We further show that the joint action selection problem in our MALinZero is a maximization of submodular objective and can be solved using an (1 >appproximation algorithm. MALinZero achieves state-of-the-ee performance in our evaluations on matrix games, SMAC [22]. and SMACv2 (23). by enabling multi-agents MSCT via low-dimensional representations.
The primary contributions of this paper are as follows:
We propose MALinZero to leverage low-dimensional representational structures on joint- action returns and enable efficient MCTS in complex multi-agent planning.
We solve the resulting contextual linear bandit problem with a convex loss function and derive novel LinUCT to facilitate exploration and exploitation in low-dimensional space.
We analyze the regret of MALinZero for low-dimensional rewards and proposes an (1 2)- approximation algorithm for joint action selection via submodular maximization.
MALinZero demonstrates state-of-the-ar performance on multi-agent planning benchmarks such as MatGame, SMAC, and SMACv2, outperforming both auett- RL and MCTS baselines in terms of faster learning speed and better performance.
2 Related Works and Background
Multi-agent planning with joint rewards can be modeled as Decentralized Partially Observable Markov Decision Process Dec-POMMP),, as tuple S, {A),Ez, P. R, (Q] {O) 7) (24]. where I = 1, 2..,. n is the set of n agents, S the global state space, A; the action space of agent the joint reward function, Ω2 the individual
i, P the state transition probability distribution, observation space of agent i, O the global observation function and y the discount factor to weigh future rewards. At times step t, agent i gets state 8 thus acquiring local observation of = O (st). then chooses action a₂ E A, based on the acquired local observation o'ge- Given joint action
ar (at,..., ,f"), ). the environment transits to the next state 5t-1 and returns reward R(s at). Agents aim to learn joint policy that maximizes the expectation of discounted return Ex D 7'r, laf m((-)gg),) I..
2

---

MARL with factorized representations. Factorization- based methods have been commonly used to cope with the exponentially growing joint state-action space MARL. Under the notion
of Centralized Training and Decentralized Execution (CTDE), algorithms like VIN 13 learn
centralized joint action-value function Quot through a linear combination of local per-agent value
functions. This is further extended to monotonic representations in QMIX [4., nearly decentralized representations NDQ [15], and counterfactual predictions in PAC [66]. Policy-based factorizations have also been considered in DOP [17] and FOP [18] To mitigate potential representation limitation, QTRAN 25 has considered adding state-value correction terms, while Weighted QMIX [4] introduces importance weights on dominant atate-actions. The idea of enforcing these representational structures has been instrumental in developing decentralized, scalable MARL algorithms. However, these factorized representations in MARL do not apply to multi-agent MCTS, which requires the use of concentration inequalities to bound the return distributions given observed samples, in order to balance exploration and exploitation.
MCTS-based planning. MCTS widely applied to solve planning problems through sequential decision-making [26]. Efficient search for optimal actions in a large decision space has been one of Existing works have leveraged Boltzmann policies [[]]
the central problems in MCTS [27 10
and condiiiond action abstractions
[ The problem becomes more pronounced in multi-agent
MCTS, as the joint action space increases exponentially as the number of agents grows [28] 29, 30), leading to significantly increased complexity in tree expansion and search. Recent approaches like MAZero [0] have considered multi-agent MCTS, but only considered distributed representation of state transitions and reward prediction, without addressing the combinatorial action space in multi-agent planning.
MCTS typically involves four stages, i.e., Selection to choose actions using UCB-like strategies 31 Expansion to add new child nodes, Simulation to sample payoffs, and Back- Suck-Propagation to propagate payoffs and update node returns. Model-based MCTS algorithms like MuZero 4 learn dynamic model to replace Simulation, thus improving the planning efficiency. MuZero involves three key learnable models: representation model he to map the real environment into latent space, dynamics model go that computes the next state and the reward of this transition, and a prediction model fo for value and policy approximation. Given the observation history Ocg at time step the model maps the observation into a latent space as $t,0 = ho(Oge), then unrolls K steps and predicts the corresponding St,k, ft. go (st, and Ut,k; Pt,k
(t.() ) for each hypothetical step & with k = 1, K. During Selection, MuZero traverses from the root node and applies the probabilistic Upper Confidence Tree (pUCT) rule select actions for node transitions until reaching the leaf node of the current tree:
a= == arg max (ss.a) + c(s) E, N(, ass
aeA
where s, and A are abbreviations for S1,--1, 0t,k and action set respectively. o(s, a) is the estimation for the real value nodes, NNs, a) denotes the visiting count, P(s, a) is the prior probability of selecting a in s, and c(s) is the coefficient balance exploitation and exploration. When the leaf node is reached, new nodes will be expanded to the tree, then ((s, a) and N a) of nodes in the search path will be updated. Specifically, ((s, a) is updated based reward Gi,A- = Dt-1-k 7T rK+147 + 1- k for l: = 0, 1...., where / the search depth and thus calculated as ((s, a) (s.a)
cumulative discounted
N(s.a)+1
Sampled MuZero 32 extends MuZero into sampling-basee framework to tackle larger action spaces for which MuZero can not construct all possible states as nodes. In Expansion, only a subset T(s) of the complete action space will be considered by Sampled MuZero according to the sampling policy 3 and prior policy æ. Then the sampled action will be selected by a = arg maX obs a) VE, N(a.6) c(s) 1 P(s.a) N(s,a)11 where 3 is the empirical action distribution.
3 MALinZero for Multi-Agent MCTS
MALinZero leverages low-dimensional representations of the joint-action returns and solves the resulting contextual linear bandit problem to enable efficient LinUCT-based MCTS in complex multi- agent planning. LinUCT is applied in Selection described in Section 2 choose the optimal action during MCTS. MALinZero consists of four main modules: the representation model for obtaining
3

---

the latent per-agent action rewards as an unknown parameter vector O from observed samples, the dynamics model for predicting the next latent state and reward, the prediction model for estimating the search policy and action-values, and the communication model for describing the coordination among multi-agentt[ Notably, the proposed LinUCT-based search and dynamic node generation in MALinZero would not incur any extra neural networks compared with MAZero, since they depend only on the inner process of each rollout. We analyze the regret of MALinZero for low-dimensional rewards. For action selections, we will show that the problem is maximization of a sub-modula objective, solvable by an (1 - aapproximmaionn algorithm. All proofs are collected in the Appendix.
3.1 Leveraging Low- Lon-Diinnsional Representations
MALinZero models the joint-action returns through low-dimensional linear combination of the
latent per-agent action rewards. More precisely, we consider a contextual linear bandit problem [20] with finite joint-action set C Rnd where we assume that each agent has d = |As,| actions without loss of generality. Thus, each joint action E A is represented by an n-hot vector selecting one local action for each agent. It is easy to see that the Euclidean norm of any action is bounded by
||a||2 < L Vn. Ya A.. At each round t, we chooses action A E A, and the environment reveals a reward X, = R(s;,A)) As).
In this work, we leverage a low -in-dninnsional representation of the reward, i.e., Xx, = (0", A,) + Et. Here ε, is conditionally -uubaaussiar observation noise, and 0* E Rnd is an unknown parameter vector representing the (latent) per-agent action return values. Thus, for each n-hot vector action A, E A, we model the low-dimensional reward X, as a linear sum of n corresponding per-agent action rewards. Our model can be viewed as projecting the reward R(s; Ag) into the low-dimensional space representable using X₁ = (0",Ae) t It reduces the MCTS from considering d' joint reward values in each state s; learning an unknown parameter vector of size nd only, thus allowing quick estimate of the global reward structure from limited samples and significantly speed-up the tree search in multi agget MCTS. Applying the regularized least-squares estimator, we can get the empirical estimation of 6* from observed samples X1, XI...., X₁
as
A 1011
0. arg min FO(O), S.I. (.(0) Σ 1(x, +
BERnd
where f is some distance measure, |00 regularization term ensuring the uniqueness of the solution, an appropriate constant for the regularization term.
Classic LinUCB for Euclidean distance f. When is the Euclidean distance measure, the solution to the estimation problem in can be obtained by differentiation, i.e., O, = V A, X, where V; are ndd x nd matrices given by Vo- = Al and V/2 = Vo - A.A. We can then apply the Upper Confidence Bound (UCB) algorithm (31 to seek the optimal action of stochastic linear bandits, which implements the "optimism in the face of uncertainty" principle. Let (C = maxsec, (0, a) be an upper bound on the mean payoff (0",a) a) for action a E Rndd where C2 S Rand is the confidence set based on the action-reward history that contains the unknown H* with high probability. At each time t, LinUCB 20 selects A, = arg max (a). The cumulative regret after steps is bounded by Rr = Σ ((A",0 0-) - (A,, 0))) )) < Cndv/T ToggTTooTTTTT (n)) where A = arg max (a, 0*), and C > 0 is constant.
Mitigating representational limitations with more general f. While classic bandit algorithms like UCB1 and LinUCB (20) solve the contextual linear bandit problem with Euclidean distance S. it does not necessarily yield the best model in terms of exploring the optimal actions in MCTS. Intuitively, the use of now-dimensional representation of the reward may introduce potential representational limitations, as previously observed in MARL algorithms like Weighted QMIX (2I) To explore the optimal actions in MCTS, it is important not to underestimate the better joint actions, while not to
Due to space limitation, the specific model architecture can he found in Appendix B. A random variable X is I-subgaussian if it satisfies the moment generating function bound E[c^x] A eA2// for all X E R. This implies rapid tail decay [[[[X] 2 t) < 2e -t2/2 analogous to a Gaussian with unit variance. The property is central deriving sharp concentration bounds in statistical learning theory.

---

overestimate the less attractive ones which otherwise may lead to substantial errors in recovering the correct maximal actions.
To this end, we consider a general family of strongly-convex, ju-smooth distance measure f in the contextual linear bandit problem in (2) For higher observed rewards X, that are likely optimal, the distance measure f will have a larger acceleration (i.e., second order derivative if differentiable) for underestimating (X, (0, As)) > O, while having a smaller acceleration for overestimating (X, (0, A.)) < 0. On the other hand, for higher observed rewards X₁ that are unlikely to be chosen, it is important not to overestimate by having a larger acceleration for (X, (0. A.)) An example of such f is to consider: f(X,- (0, A.)) = w_ (X, (0, A.)) 2 if X, 2 (0. Ag). and f(x; (8, A.)) w (X, (0. A.)) otherwise. We can choose W4 > w for better X, to prevent underestimation and W+ < w- for undesirable X,, This ensures that our low-dimensional representation in MALinZers can best support the exploration of the optimal actions in MCTS. We will drive a novel LinUCT with respect to such f and leverage it to balance exploration and exploitation in MCTS.
3.2 Deriving LinUCT and Analyzing Regret
We derive action selection using LinUCT in MALinZero and provide cumulative regret bound for the resulting contextual linear bandit problem, depending on the properties of strongly-convex, u-smooth f. We prove that LinUCT can achieve an regret of Ry = O(nd VuT - In(TT) after T steps, ensuring the exploration efficiency using LinUCT. Our analysis builds upon 33 and extends it to general convex loss f-
Let (Ae)T- C Rnd be a sequence of action vectors with ||A.||2 S vn, and suppose the observed reward at time is X; = Ar) + where 0 E Rdd satisfies ||0 12 S. S for some bound S, and each 7/r is conditionally I-subgaussian. Since f : R IR is strongly-convex and p-smooth, we have E S ff) (z) S μ. Vz E IR for some positive e. The solution to (2) is obtained by differentiation and yields 0, V, Ex= A, where use W, (Ee with
(0, X, (0,-1, A,)) and thus have E I W/ S for any and &t. Here X, is the immediate reward at step t. Further, Vn are nd x nd matrices given by initial Vi = Al for some constant À > 0 and 1/2 = Vo + E.= W,A,X,
Next, we consider an ellipsoid confidence set centered around the optimal estimator d.-1, i.e., Rnd, 110 0 llv S 3r, for an increasing sequence of 3e with B1 2
C. =
{0 (0 that as t grows, this ellipse C, is shrinking as V2 has increasing eigenvalues and if 3, does not grow too fast. We show that the problem of selecting optimal action A, E A by solving m....C (0, (0,a) in this contextual linear bandit problem is equivalent
33 Note
A arg max (ō--1. a) + 3--1 //11/=lll_71
which is referred to as our LinUCT rule for action selection. We consider the realized regret defined (n - 7t). The next theorem
by Ry = (x; - X2) = ((0" A4) (,,A)
gives the regret bound of LinUCT, with corresponding proofs in Appendix A.
Theorem 1. /Regret Bound of LinUCT) With probability 8, the regret of LinUCT satisfies
det((V)) det((II)
(ndx punt ndA
R < v /8ut8, In
Spndt In
Proof sketch Let S. = 1 and Vi = X N E W. W.A.A.. (i) A standard self-normalized concentration (mixture supermartingale) gives, for all t & T with probability 2188.
A,A.7.
S. VT S, s 2 1n
1/2 Ana/2s
110, 0'1|v S Br.
(4)
(ii) By optimism of LinUCT and the confidence event,
x;=;; X, B B + +
A == nr m/-
(5)
Since ne, ni are 1-sub- Gaubsaan Σ A < Tlm(10)) w.p. 2 1-6 8.
5

---

(iii) Summing and applying Cauchy-Schhee plus the (weighted) elliptical potential lemma,
T
Σ B- S VT Bry 2
dot(Vr)
(6)
And
which, together with (ii) and the definition of Br. yields
Rr S V 8p ST In dec(V And
(7)
(iv) Using wa S μ and ||A.|2 S vn, VT AI unT I, hence
Inf det((/))
S nd In +
(8)
ndd
giving the displayed bound in the theorem.
Choosing 3.
2/ In det(VV)1/2 det(Ar)1/28 )
VXS, we show that the regret has the following order:
Corollary 2 (The Order of Regret Bound for LinUCT). Under the above conditions, the cumulative regret bound of LinUCT with 1/T satisfies
Rr O (nd- (MT-I((T)
The regret bound of LinUCT in Theorem onnly depends on nd rather than the exponential size of the joint action space. The general convex loss f incurs an extra multiplicative factor / compared with the standard results of contextual bandit [33
3.3 Dynamic Node Generation
MALinZero allows modeling the joint action space using low-dimensional representation, thus significantly speeding up exploration and exploitation in multi-agent MCTS. Specifically, when the leaf node T in the search path is visited for the first time, = (x nodes will be sampled child nodes where Ç is the dynamic generation ratio and X is the maximum number of child nodes. In the subsequent Selection stage, node T will utilize the cumulative & and V (We omit the subscript in this section for abbreviated notations) to search for the potential optimal action from the entire joint action space and add it as the child node. If there no node with higher value, Selection will sample and compare the existing ones. The detailed process can be found in Algorithm []
For root or leaf node Y, K (x nodes are sampled for initialization similar to MAZero. The next time T is visited, MALinZero selects optimal action using LinUCT with search policy P(s, a):
arg max AcA (a) = arg max a 0 + c(s) a) trace (race(V)Va-V-la
(10)
where c(s) is a constant, (a) is the objective function for action selection, and P(s, a) is the search policy used as a prior information in LinUCT similar to MuZero [4] If the selected action for which the corresponding node does not exist, this node added after Selection. Once a node has x child nodes, it only selects next action from current children. After root-to-leaf search path is completed, and V are updated through the search path from the leaf node as procedure Back- Back-Propagation in Algorithm[1 [
Remark. MuZero 4 selects nodes/actions in MCTS via (I where the term VI, (s, b) represents the total sampling time. In MALinZero, we utilize trace( (V) achieve the same effect. We use trace(V) rather than its square root due to the existence Va V-ta in LinUCT. It ensures that the scale of exploration term can keep stable with the increasing times of selection. Using the definition of V and the fact that actions A are n-hot vectors, it is easy to show that traco(V) increases linearly with N and sampling time. For a single-agent problem, (IO) indeed reduces to (I. recovering existing result as a special single-agent case.
With Dynamic Node Generation (DNG), we can sample and add new child nodes according to LinUCT. In other words, the x sampled child nodes are used bootstrap low-dimensional representation of the joint reward over the entire joint action space, thus enabling fast exploration and exploitation

---

in MALinZero. Let ground set A be the set of all n-hot vectors in Rnd where each vector E A satisfies: each of the disjoint k-dimensional blocks, exactly one entry with others are 0. Let S be the set of selected actions and rewrite V(S) AT Laes aa using S. We show that the objective function ((( for action selection is sub-modular.
Theorem 3. [Submodularity of / V is a non-negative monotonic submodular function over the ground set A.
Hence, to solve the optimization for action selection in (TOp, we have maximize submodular function, which is shown to be N P-hard 34 35 by reduction from the classical Max-Coverage problem. Fortunately, there exists an (1 - approximation algorithm (36 solve this optimization.
Let V 2 + Rzo a monotone submodular function. Fix budget E N and let A = = Bg be partitioned into blocks (so that any feasible set contains most one element from each Bú; i.c. an n-hot constraint).
Theorem 4. [(1 Appproxximaaionn under Cardinality and n-Hot Constraints] There exists an /(1 appproxiinnno algorithm for the optimization of action selection.
(a) Uniform-matroite (cardinality) case |S| S T. The standard greedy algorithm
A arg max aEA:S
(S
(( S. = S U (At).
fort = -l.... T, returns ST satisfying (S,) (1 () (SS)), where S is optimal subset of size at most (36].
(b) n-Hot (partition-matriic case. One may apply the castinuous-greede algorithm to the mul- tilinear relaxation max,eP((M), 1 1 E[V (R(x)) where P(M) is the matroid polytope of the partition matroid and R(x) denotes the standard randomised rounding. It produces feasible set $ with V ($) 2 (1 (S*)) (37).
Thus, under the stronger n--ot (partition-mattts matroid) constraint, there exists an efficient algorithm to compute action selection in MALinZero with (1 apppproximation.
Algorithm 1 MALinZero
procedure BACK- PROPAGATION
1: procedure DYNAMIC NODE GENERATION arg max a
2:
for (s, (s,a) E path do
2:
+ 3:
Let k; the depth of the current node and the leaf node.
((s) (vaaa
3: return (s,a)
D. The weighting could replaced with strongly-convex y-smooth function for better performance.
4: end procedure
procedure EXPANSION
2:
.'' is the number of nodes generated by
4:
if Observed reward Xs
Q(s a)
sampling.
then
3: for i 1, M' do
5:
W1
4:
0g sample with 3 and as Sampled 6:
else
MuZero 32
7:
222
5:
T(s) U(s
8:
end
6: end for
9:
Calculate the cumulative discounted
7: end procedure
reward G(s) < Σ 11-1-
X
1: procedure SELECTION
10:
Q(s, a) ((s)))
N(s.a)11
2:
if number of child nodes M then
11:
N(s. + -N(ss)) ()s,a)+1 +1
3:
(s, + DYNAMIC NODE GENERATION
V(s) V(s) wa
4:
T(s) (s,
13:
((s) V(s) Xxa
5:
else
14: end for
6:
arg (ggax.eT(o)) To
+ 15: end procedure
7:
end
8:
return Index of (s,
9:
end procedure

---

Efficient Back-Propagation The update of f and V involves large matrix manipulation, of which the time complexity is (nn²d²) and the space complexity is On dP). To mitigate the computation complexity, we design an efficient back-propagation (as shown in Algorithm I to reduce both time and space complexity to ((nd) based on the Therman-Morrison formula [8) We consider the
update of A 0r and V VATV," A in LinUCT. Using the definition of 122 and d,, it is easy to show that these can be obtained by storing and recursively updating 6g and V.-!A:
-= V, AA"V, Ai and 0.+1 - V Me 1 ATV, A
V, AA"V Mr
1 AVV
where A, is the action corresponding to the i-th child node, A is the action of nodes in the back- propagation path, and where M,- Ee=1 W, is an auxiliary variable.
Theorem 5 (Complexity of the Back-Propage Propagation to update 0, and V.= The proposed method computes the same LinUCT, but reduces the computation complexity from O( (n)d)) to O(nd).
Experiments
We evaluate MALinZero on three reinforcement learning benchmarks: MatGame, StarCraft Multi- Agent Challenge (22 and SMACv2 [23]. MatGam is stateless-matrix game that generalizes the classic normal-form setting agents. At every step, all agents select an action from the same discrete set; the environment then looks up the joint action in predefined payoff (with or without noise) tensor and returns the corresponding shared reward, which used to evaluate algorithms' performance. MALinZero is compared with both model-based and model-free baseline models on these environments. The model-based algorithms are MAZero [TO. MAZero without prior information (MAZero-NP) and MuZero implemented for multi-agent tasks (MA-AlphaZerro) We
also choose two mainstream model-free MARI. algorithms: MAPPO 39 and QMIX 14
Model architecture MALinZero consists of 6 neural networks to be learned during the training and the parameter is to be estimated from initialization for a single MCTS process. Specifically, with network parameter c, there are 6 key functions: the representation function st (o's)) that maps the current individual observation history into the latent space, the communication function ci,....,,e C², , S . i......., x(,x)) that generates cooperative information for each agent via the attention mechanism, the dynamic function s1,41 = (s k: Litk: c(,)) that plays the role of transition function, the reward function re,* = ( Si,e- at "i..:... aa.....,0" o²,k) and the value function U = 1 (s) .... ) that predicts the reward and value respectively, and the policy function p (o(s that predicts the policy distribution for the given state. The subscript denotes the index of unrolling steps within one simulation from the root node in MCTS. The update of estimated 9 takes place in the Back- pack-propagation stage and the detailed process is analyzed above. For all these modules except for the communication function cs. the neural networks are implemented by Multi-Layee Perception (MLP) networks and a Rectified Linear Unit (ReLU) activation and Layer Normalization (LN) follows each linear layer in ML. networks. Agents process local dynamics and make predictions with the encoded information.
Experiment setting All experiments are conducted using NVIDIA RTX A6000 GPUs and NVIDIA A 100 GPUs For MatGame environments, the number of sampled actions for each node in MCTS is 3 and the number of MCTS simulations 50. For both SMAC and SMACv2 benchmarks, we set
them as 7 and 100, respectively. We build our training pipeline similar to EfficientZero [40] which synchronizes parallel stages of data collection, reanalysis, and training.
Performance Evaluation MALinZero outperforms all baselines in 8 MatGame environments. As shown in Table [ the performance improvements are achieved in even simple MatGames (a few percent for 2 agents with 3 actions each, thus a space of only 9 joint actions) and increases for more complex MatGames (such as up to 11% for agents each with 10 actions, thus space of 810 joint actions). This makes sense since the benefit of MALinZero comes from representing high-dimensional joint action space into lower-dimensional ones. Interestingly, the improvements are higher in MatGames with non-line lineir reward structures. This is because MALinZero is able to model
8

---

Agent Action
Type
Steps]
MAZero
MAZero-NP
MA-AlphaZero
MAPPO
QMIX
MALinZero(Ours)
Linear
500
51.9 1 2.3
1.9
50.8 1.2
50.2
50.4 1.41.335
0.9
Linear
1000
57.8 1 2.4
53.1
3.3
55.2 2.7
56.4
54.3
3.17
59.9 0.2
3
Non-Liness
500
49.1
+ 15.3
48.9
17.2
49.0
16.4
49.1
19.1+00 19.1
48.7
18.6
49.2 + 8.6
2
3
Non-Linear
1000
47.6
47.6 14.7
49.3
14.3
49.2
12.9
49.5
18.1
49.1
17.7
49.6 = 15.5
4
5
Linear
T000
175.2
171.7
1 5.6
172.7 4.1
173.1 1 5.4
171.8
4.9
184.3
3.2
4
5
Linear
2000
191.711..
100.1
1.2 1.2
190.4
180.8
1: 2.1
190.2
1. 1.8
197 4 2.1
Non-Lanean
1000
179.4+
173.2
10.0
974.5+9.33
173.1
8.0
174.7
182.4
11.7
Non-Linear
2000
195.4
20.0
192.4
11.4 192.7
191.9
12.5
190.3
197.8 21.1
Linear
1000
9.9
387.22
10.1
389.3
184
390.6
386.1
10.4
396.6 8.4
Linear
2000
4.2
427.3
432.61:99
431.8
84
430.1
1: 9.5
439 8 6.8
Non-Limear
1000
399.8
13.7
391.3
10.3
393.1
12.1
388.8 + 13.1
390.5
12.2
410.6 8.9
6
8
Non-Linear
2000
443.9
1 12.1
429.1
1. 9.3
427.
8.6
430.1 1 8.5
431.7 1: 7.6
451.1 12.8
8
10
Lincar
1000
618.8
16.9
608.8
17.6
613.1
= 13.1
617.1 11.1 612.7 = 15.4
637.1 = 15.8
8
10
Linear
2000
692.7 14.5
671.5
13.9
654. 14.5
681.8 + 12.5
679.4 12.7
705 2 = 15.7
8
10
Non-Linear 1000
615.2
+ 18.7
536.6
24.1
573.2 22.7
561.4
1 20.9
558.7
19.1
630.1
16.3
10
Non-Linear 2000 672.3 16.1
587.2
18.4
633.2
15.6
657.1
17.3 648.2
T 18.75
693.4 15.6
Table 1: Evaluation in MatGame with different numbers of agents and actions. We consider both linear and non-linear reward structures. MALinZero is shown to outperform both MCTS and MARL baselines, especially in more complex MatGames with larger action spaces and with less numbers of steps. Interestingly, the improvement is higher for non-linear reward structures (up to % %11). 11), as baselines may stuck in local optima. Detailed MatGame settings can be found in Appendix D.
the entire joint action space despite in lower dimensional space, while baselines may get stuck in local optima. MALinZero is also able to achieve the rewards much faster than baselines. Running the LinUCB algorithm will incur minor additional cost. However, the computation leverages a linear structure with sampling (dd)) actions rather than the standard (d")). Our evaluation shows that the computational cost is comparable to that of the MAZero 10 method.
Figure 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. MALinZero achieves over 95% % winning rate on all 3 maps, outperforming all baselines and also gets high winning rate much faster.
Figure I shows performance measured by win rate on three different SMAC maps. MALinZero beats all five MCTS and MARL baselines, in both higher winning rate (over 95% actoss maps) and faster convergence speed. Comparing with the closest baseline MAZero, our MALinZero reaches the same winning rate with 50% to 70% less steps/samples, implying 2-3x speedup. The results demonstrate LinUCT's ability to represent complex multi-agent decision-making problems in low-dimensional latent space. This efficient representation supports fast MCTS by exploring and exploiting the global reward structure of the joint action space (in an approximated fow-dimensional fashion), rather than getting trapped in local optima as in the baselines. This is validated by comparison with MCTS baselines with pUCT applied to MAZero, MAZero-NP and MA-AlphaZero.
Mhl
Figure 2: Comparisons on 3 SMACx2 tasks/maps. Y-axis denotes the win rate and X-aiis denotes the training steps. MALinZero nearly doubles the winning rate these challenging maps in SMACv2 and consistently outperforms all baselines. Fach algorithm is executed with 3 random seeds.

---

Different from SMAC, SMACv2 significantly increases difficulty by adding larger heterogeneous unit teams, more varied map layouts, and stochastic enemy formations, which all demand advanced coordination and generalization by the learning algorithms. Figure 2 shows the training curves of our proposed MALinZero and baseline algorithms on SMACv2, including widely-used maps. Compared with all baselines, MALinZero doubles the winning rate on protoss_5_v 5_vs_5 and rerg___v__$ and nearly doubles it on terran_ 5_vs_s. Our MALinZero shows very robust performance across different scenarios, which comes from the parameterization of LinUCT, allowing MALinZero to conduct more adaptive and efficient modeling of heterogeneous unit teams.
Ablation Study We intend to validate the necessity and effectiveness of DNG and the general function f applied in LinUCT. To accomplish this, we compare the proposed MALinZero under two MatGame environments: (1) Medium difficulty scenario containing agents and each with 5 actions; (2) Hard difficulty scenario containing 8 agents and each with 10 actions.
630
306
340
1240
2540
300
500
1200
Figure 3: Ablation study of MALinZero by removing various design components, such as DNG and the introduction of general convex loss f in the contextual bandit problem.
In Figure 3 we evaluate the impact of removing the DNG component, the use of the general convex loss I (to place more importance on better actions), and both simultaneously. It is shown that these components are critical for the superior performance of MALinZero. In particular, without DNG, is hard for MALinZero to model and explore the joint action space, thus the performance becomes limited. The observed performance degradation when using a Euclidean distance rather than general convex loss validates our design principle that by placing more importance on the better actions can boost maximal action selection in this low-dimension representation.
5 Conclusions
We propose MALinZero, which leverages low-dimensional representational structures to enable efficient MCTS in complex multi-agent planning. MALinZero can be viewed as projecting the joint- action returns into the oow-dimensional space representable using contextual linear bandit problem formulation, with a convex and μ--moooh loss to place more importance on better actions. We employ an (1 1 -approximation algorithm for the joint action selection by maximizing a submodular objective. MALinZero demonstrates state-of-the-art performance on multi-agent benchmarks such as MatGame, SMAC, and SMACv2, outperforming MARL and MCTS baselines.
Limitations: MALinZero leverages a contextual linear bandit formulation in the low-dimensional space. The use of non-linear formulations that may also allow efficient MCTS could further improve the performance. Developing fully decomposable representations also remains an open problem.
References
[1] Chiara F Sironi, Jialin Liu, and Mark HM Winands. Self-adaptive monte carlo tree search in general game playing. IEEE Transactions on Games, 12(2):132-144, 2018
[2] Sahar Leisiazar, Edward J Park, Angelica Lim, and Mo Chen. An mets-drl based obstacle and occlusion avoidance methodology in robotic follow-ahead applications. In 2023 IEFF/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 221 221-228. IEEE, 2023.
10

---

[3] Yingkai Xiao, Jingjin Liu, and Hankz Hankui Zhuo. Balmets: Balancing objective function and search nodes in mets for constraint optimization problems. arXiv preprint arXiv:2312.15864, 2023.
[4] Julian Schritwweserr, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(783))6044-60)) 2020.
[5] Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference machine learning, pages 282-293. Springer, 2006.
[6] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 359, 2017.
[7] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-oomptttin environments. Advances in neural information processing systems, 30, 2017.
[8] Pablo Hernandez-Leal. Bilal Kartal, and Matthew E Taylor. A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Mulli-Agent Systems, 33(6)7550-777, 2019.
[9] Yunhyeok Kwak, Inwoo Hwang, Dooyoung Kim, Sanghack Lee, and Byoung-Tak Zhang, Efficient monte carlo tree search via on-the-fly ffy state-conditioned action abstraction, 2024. URL httts::/aaxil: org/ abs /206 00614
[10] Qihan Liu, Jianing Ye, Xiaoteng Ma, Jun Yang, Bin Liang, and Chongjie Zhang. Efficient multi-agent reinforcement learning by planning. arXiv preprint arXiv:2405. 2024.
[11] Michael Painter, Mohamed Baioumy, Nick Hawes, and Bruno Lacerda. Monte carlo tree search with boltzmann exploration, 2024. URL httth:t////arrt arxiv www. httgg/bb//244... 24744.7773
[12] Chih-Chun Wang, Sanjeev R Kulkarni, and H Vincent Poor. Bandit problems with side observations. IEEE Transactions on Automatic Control, 50(3):338-355, 2005.
[13] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value-decoopoosition networks for cooperative multi-agent learning, 2017. URL https:// arxiv. wrxiv.org/abs/1100 05296
[14] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement learning. Journal of Machine Learning Research, 21(178):1-51, 2020.
[15] Tonghan Wang, Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decom- posable value functions via communication minimization, 2020. URL httpthtttp://asts. org/
abs/1910. hiss1990.05366)
[16] Hanhan Zhou, Tian Lan, and Vaneet Aggarwal. Pac: Assisted value factorisation with counter- factual predictions in multi-agent reinforcement learning, 2023. https:/::///art org/ aba/2206. 11420
[17] Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjic Zhang. Dop: Off- policy multi-agent decomposed policy gradients. In International conference on learning representations, 2020.
[18] Tianhao Zhang, Yueheng Li, Chen Wang, Guangming Xie, and Zongqing Lu. Fop: Factorizing optimal joint policy of maximum-entropy multi-agent reinforcement learning. In International conference on machine learning, pages 12491-12500. PMLR, 2021.
[19] Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school machine learning, pages 208-240 Springer, 2003. 2003.
11

---

[20] Lihong Li. Wei Chu, John Langford. and Robert E Schapire. A contextual -aaddi approach to personalized news article recommendation. Proceedings of the 19th international conference or World wide web, pages 661-670, 2010.
[21] Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning, 2020. URL
https://arxiv. org/ abs 10800
[22] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philiph H. S. Torr, Jakob Foerster, and Shimon Whiteson. The StarCraft Multi-Agent Challenge. CoRR, abs/ (bs//992.00444,, 2019.
[23] Benjamin Ellis, Jonathan Cook, Skander Moalla, Mikayel Samvelyan, Mingfei Sun, Anuj Mahajan, Jakob Nicolaus Foerster, and Shimon Whiteson. SMACv2: An improved benchmark for cooperative multi-agent reinforcement learning. In Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023. URL https:// openreview. htt.://ooooooomiiid--0001013333
[24] Frans A Oliehoek, Christopher Amato, et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
[25] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International conference on machine learning, pages 5887-5896. PMLR, 2019.
[26] Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012.
[27] Jiayu Chen, Wentse Chen, and Jeff Schneider. Bayes adaptive monte carlo tree search for offline model-based reinforcement learning, 2024.
[28] Shushman Choudhury, Jayesh K Gupta, Peter Morales, and Mykel J Kochenderfer. Scalable anytime planning for multi-agent mdps. arXiv preprint arXiv:2101.04788 2021.
[29] Marc Dalmasso, Anaís Garrell, José Enrique Domínguez, Pablo Jiménez, and Alberto Sanfeliu. Human-robot collaborative aulti--geett// path planning using monte carlo tree search and social reward sources. In 2021 IEEE international conference on robotics and automation (ICRA), pages 10133-10138, IEEE, 2021.
[30] Alexey Skrynnik, Anton Andreychuk, Konstantin Yakovlev, and Aleksandr Panov. Decentralized monte carlo tree search for partially observable multi-agent pathfinding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 17531-17540, 2024.
[31] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256 2002.
[32] Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Mohammadamin Barekatain, Simon Schmitt, and David Silver. Learning and planning in complex action spaces. In International Conference on Machine Learning, pages 1476-4486, PMLR, 2021.
[33] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[34] George I. Nemhauser, Laurence A Wolsey, and Marshall Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming. 14:265-20 2-245-294, 1978.
[35] Marshall Fisher, George I. Nemhauser, and Laurence A Wolsey. An analysis of approximations for maximizing submodular set functions-Il -II. Springer, 1978.
[36] George I. Nemhauser, Laurence A Wolsey, and Marshall Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming, 14:265-294, 1978.
12

---

[37] Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák. Maximizing monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6): 1740-1766, 2011.
[38] Jack Sherman and Winifred J Morrison. Adjustment of an inverse matrix corresponding to change in one element of given matrix. The Annals of Mathematical Statistics, 21(1):124-177, 1950.
[39] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. Advances in neural information processing systems, 35:2461 1-24624, 2022.
[40] Weirui Ye, Shaohuai Liu, Thanard Kurutach, Picter Abbeel, and Yang Gao. Mastering atari games with limited data. Advances in neural information processing systems, 34:25476-2548 2021.
13

---

A Proof of Theorems
A.1 Proof of Theorem
We will show the proof for the regret bound of our proposed LinUCT.
Setup. Let 0 E Rnd |0 I S. At each round we observe A E RTd | ll I vn v L. and receive.X; (t) + Th. where 77t is conditionally -sub-Gaussian Suppose f: strongly-convex and y--mmoth, we have (z) E [s, 14. V2 E R for some positive E. The solution to (2) is obtained by differentiation and yields 0. V, Σ WgA,X, where we use w, (5a) with & E X; 1, As)) and thus have E S we S for any t and Ex.
R is
We consider an ellipsoid confidence set centered around the optimal estimator 0.-1, i.c., C. {0 E Rnd |10 d1- I Bt. for any increasing sequence of 3, with 31 2 Note that as grows, this ellipse C₁ is shrinking as V, has increasing eigenvalues and if 3, does not grow too fast. We show that the problem of selecting optimal action A, E A by solving m. (0, a) in this contextual linear bandit problem is equivalent to A, arg max, (p-1, a) + 8 || ||lly; which is referred to LinUCT rule for action selection. We consider the realized regret defined by RT
Xt) ( (()) (0 A,)) + Σt m1). Lemma (Confidence Ellipsoid). With probability at least 5, for all T,
110, 0" 1l1 Bc.
(11)
Proof. Observe
0: ---0- 0" = -V,
Wy A, - v:00) = Vú ( 8=1
AsT - -100)
(12)
1=1
Set Y, Etm1 W/ A, and A0" Then we have
10: 8* 11:: (b - YT) V. (b Yi) Y,
25 Vv -V, VV 6 DV
(13)
Since V/ 2 AI, V 3 and ||0|| || < S, we can get
b vv b = X V. 00 S x2
A = AS².
(14)
According to Cauchy- inequality and V 1 H1,
16 V2 'Y. S [61|2 VIV, Yxll2 -
& AS tr, Yv Y2 VVs YY
Yn
(15)
Hence
-26 ', < 2VAS V
(16)
To bound Y,T V, -Y, note Y, self-normalizer tail bound yields
E' Wy A,A. is martingale sum. According to Lemma
the
VTV < 2n 2et(V))2/2
(17)
det( (2/)/2///2
Combining these three yields
10: 0 00 S VY + vās s 3
(18)
and union bound over t 1,..., gives the result.
14

---

Lemma 2 Norfl-eoral Martingale Tail), Let {m be sequence of conditionallyy Saub-Gaussian noises, and let A, I2' d and wt E [E. be Fi-r-measuabll. Define
Y2 W/ As Uas Vi
Σ us A,A +
(19)
Then for any E (0, 1), with probability at least 1 - simultaneously for all S T,
Y, V_V''' Yv s 24 In det((V)
(20)
det(\1))/2
Proof. First, we define
M1(x) exp (T, Y. デラ 1/
(21)
for each fixed x E R'd. Since Q is conditionally 1-sub-Gaussin and S μ. we have for any mees-uaaurablle
Ble"Ti [i-1]] s exp(tt²) = Ai A am Fr-1]
(22)
exp(# x) I exp( x (w;A,A )x)
Therefore
E [[M((x) Fi-1] = (x) Ble (weAm))) $ x (wrArAT) Fe.]] S Me-1(I).
(23)
Hence each Mx(x) a nonnegative supermartingale with Mo(x) =.
Then we lift the pointwise supermartingale bound to uniform one by integrating (x) against the Gaussian prior over æ. Let h be the density of N A-))). Define the mixture
/
M,
M((x) h(x) dr.
(24)
Rnd
By Fubini and the supermartingale property,
E[M, Fi-1= / ((M(())) Fi-1] h(x) dx S ()) do = M.
(25)
so M2 also a nonnegative supermartingale with M, A Gaussian integral gives
M, = (2T)nd/2 det(2-17)1/2
exp x Y, - 1/2 T (AT + +VV)) dr
(26)
det(Al) 1/2 (dolA(+av))
LYT,(AI+ (AI [Vii -Y.)
=
cxp
Since V2 1 AI, one checks (AI + (VV)) - V and det + vV)) S nM det(VV). Thus
M, 2 nd/2 (det(A)) 1/2 det(v:))
exp L V.
(27)
By Ville's maximal inequality for nonnegative supermartingales.
Pr Pr(at M, 2 2)) s 8MM 5.
(28)
On the complementary event, for all T T.
In det(Vi) det(A1) + In
M, < 1 V, YY < 2 Inp
(29)
Absorbing the constant nd In ş into in(1/) yields
2
V, V. ly, s 24 1n( 1///2
(XT)1175
(30)
claimed.
15

---

Lemma 3 (Elliptical Potential). Let Vo = Al fnr t = ........7 T define
V. Vi-1 wt A,A,,
(31)
where As 1nnd satisfies ||Ar|l2 & vn = L and we E [s with E 2 0. Then
T
2 In del(VT) 2nd In(1 det(Vo)
min 1, || { Σ
(32)
ax
Proof. First, for any 2 we have 2 1 2 + 2). Hence
T
min we A. } S 2 In 1 + 12 |A
(33)
Next, by the matrix determinant lemma,
det(V)) = dde((Vi-)) det( + wa A,A, = det det(Vi we [
(34)
Telescoping the product for t = 1...., T gives
II w/ [IAi)( det(VTT)
(35)
det(Vo)
and taking logarithms,
det (v)) det(Vo)
Σ In(1 we ||A: [|A+11))))))
(36)
Combining with the earlier bound yields the first inequality. Finally, since wi S l and ||A S L. have
T
VT = A Σ A.A 3 AI II
(37)
(VT) det(AI)
ndd 1a 112T = nd In 1 uT ndd
In
S nd In
(38)
2x
giving the second inequality.
Here we reclaim Theorem Theorem. (Regret Bound of LinUCT] With probability
8, the regret of LinUCT satisfies
det((V))
(ndd + prt nnd ndl
R, v /8pl.B In
(det(A))
8pndd In
(39)
Proof. Let
S. = Σ
W. AgHos
V -- - Σ W. A.A
(40)
s=l
and define
det (V.) 1/2
1/2)1/2
3 22 In
+ VĀ 10'
(41)
And/2 8
By Lemma 2
with probability least simultaneously for 1,
det (et(V)))
|| S V
2u In
And/2 3.- 1-V1110012
(42)
16

---

On this event, Lemma T shows
|0. 0 (1)
& |S + vx110112 S Br.
(43)
Next let A 1/E Te- Since each ne: .TE is
and independent, we can get
Bie [F-1]]
E -E(et1
Ele Am) I exp( 2
exp( 2
exp(1²).
(44)
Thus A is conditionally V2-sub-Gaussin
E Adi
Fi-1 S exp (v2a)²)
(45)
By Hoeffding's inequality,
Pr Σ A > uu
S exp
-x² u² 47
-27)
(46)
Choose u 2= Thn Then
Σ A > 2 Tln s expl
47 (n(188)
8.
(47)
47
Because A, is chosen by A, arg max max, (0--1, a) + B--1 1|llll= while A7 = arg max max (8", first compare the optimistic upper-confidence values:
(0) + Be-1lAArll (0-11, + BI- B1-1l1Aillv
(48)
Whenever the confidence event
holds for any a,
1(( - 1) a)l < ||0" 1 Ilalv, $ Be-1llallzzt
(49)
Applying this with A and then with At gives
(0", AA) & (0.11, A3) + B Aflll (0*, 2 (0-1, Ar) - Be-1llAellvz
(50)
Subtracting the second inequality from the first and using the choice of A.
(0*,A]) - 10", Az) S 3 ||Ae|l
(51)
Then we can get
X; X1 = A(0),A)) - + A. I 8- 1 + A..
(52)
The single-step regret is
ri = X; x,= = (8", - (0", A.)) A S S1-114 + +
(53)
Sum the single-step regret from = 1 to T:
T
RT
rt
Σ
B 1 + 2
(54)
t=1
1=1
Inequality 533 is the starting point for the final bounding of the main term
T
Σ
(55)
17

---

via together with the weighted elliptical potential lemma.
By Cauchy-Schward and Lemma 3
T Σ 3 11llllAlll, t=1
T
T
det det((V))
Σ
3
| Aull
S Br V 2
(56)
And
t=1
Combined with (4).
det(VT) And
RI S 2T By V In
+ 2 Tim 8-
(57)
According to the definition of Br, have
det(VT)
det(Vr)
Br S V 2 In
(58)
And
And
2/
Therefore the first term in 57 satisfies
det(VT)
37
T
2T BT V
In
2T 3T
B7.
(59)
And
211
Moreover,
Bz.
2 2 T
< 21 T
=
3r S
V
34.
(60)
2/1
Hence
RT s 2 v I 3 2
2p In dVt)
+ vx 10"112)
(61)
And/28
With wy I a and A S v L. according to Lemma
3 we have
T
Vr = x Σ
w. A.A
I nddI + II
(62)
and
(mid nd
ndd + μu?TT nd
det()r) And
(ndx 1u. nd ndd
dct(V>) <
$
(63)
Thus, with probability at least 5,
(ndx + ul21 nd
(ndd + prdl) ndl
R. < V 8pt.8
nndx ndl
V 8pmd Be In
(64)
A.2 Proof of Theorem
Theorem. 3 Submodularity of V V is a non-negative monotonic submodular function over the
ground set
Proof. Throughout, ||ж|| == Vxl Mx for M > 0.
(i) Non-negativity. Both summands in (SS) are non-negative, hence U(S) 2 0 for all S S A.
18

---

(ii) Monotonicity. Fix S S A and & S. Write
A S) ((S (SS) a | [(eelll -
radius
(65)
Apply Lemma with V = V(S) and u
(lullv(s)- - [|oll(( < |allv(s)~ & |
(66)
VES
Substituting inequality 66 in 65 gives (aa 5) 2 aTd 2 0; therefore V is monotone.
(iii) Submodularity (diminishing returns). any finite R S A define
Let S C S A and aet & T. Set U == T \.S. S. For
L(R)
- -ooelvag=--llllvvvaaa)))
(67)
PR
With this notation
(a S) = a [[allv(ssu)))) I(S), A(a (T) = 0 |allv(T((a)) L(T). (68)
Step Compare the new-radius terms. Because V(SU {a}) V(TU we have
|allv(Su[a))> 2 ||l|v((r(()))*
(69)
Step 2 Compare the loss sums. For every v E S Lemma applied with x == v, u= A =
V(T), V(S) yields
[s)] | & Ielllver -ellvaaaaa)
(70)
Summing (70) over all E S gives
L(S)= s
- -lull(ero))))))
(71)
WES
Adding the non-negative terms || - [(lller for v E U both sides of
we obtain
L(S) s L(T).
(72)
Step Combine. Subtracting (2) from (69) and using representation 68 yields
(a | S) - A(a 7) = [[||]] (ollvv( - [|allv(ru(a)==] - [[(S) - L(T)] 2 0,
(73)
that is, (aa 5) 2 (a T). Hence V satisfies the diminishing-retumm property and submodular.
D
Lemma 4 (Aggregate- loss bound). Let V E Rudxnd be positive definite, let u E Rnd and let S C Rad be a finite set. Then
Σ DES
(11lllv 11aa--11lllvee [|]](v+ <
||u]|v-
(74)
Proof. Write A. = | |
Using Woodbury's identity (V wuT) V-1
y- un V--
V compute
-0 un - (v v2))
(75)
1+ VV
For any a > one has Vo Va- 3 3/2322222 9) B/ /2a.. Applying the Triangle and Cauchy- Schwazz Inequalities, we have:
TV- ml
A, <
$ ||lll || 1.
(76)
V
19

---

Summing 776 over v E S and applying Cauchy-Schwarz, Schwarz,
Σ
|
|1 11lll
|
eES
PES
since ||llll Σ [s]
completing the proof.
Lemma (Monotone-ga) lemma). Fix Iz, Rnd and define, for every positive definite matrix A.
dz(A) = V= V V (A+ uni) 1xx
(77)
IA 2 B > then (A) 2 (B).
Proof. Let H : 1 B = 0 and define A, = + BH for /. E [0, 1]. Set g(!) = dx{A).. Using
d di A, A, HA, and dc (A + uu. ) (A, + uui ) -HH(A, + uu )-! we compute
g'(t) = J A, HA x. (As + un -1 [A + wu )
(78)
2/ x (A, + uu )
2 x. A,
Because A, + wu ł A., we have (A, + uu uu))+ 3 A, Consequently each numerator in 788 is
bounded by the same non-negative quantity and each denominator satisfies vz (A, wu -2 <
VaT //TA,, x. Hence g((t) 2 0 for all t e [0, 1]. Integrating g'(t) from to gives g(1) - g(0) 2
i.. (A) (B).
A.3 Proof of Theorem
Here we reclaim Theorem
Theorem. (1 Appprooximtiio under Cardinality and n- n-Hot Constraints] There exists an
[(1 apprrxximatin algorithm for the optimization of action selection.
(a) Uniform-matroiie (cardinality) case |S| < T. The standard greedy algorithm
A arg max AEA
(Vr(S {a}) (S: = (Ach
(79)
fort = -I.... T. returns ST satisfying (Sr) (1 !) ((S"), where S* is optimal subset of size at most (36].
(b) n-Hot Apartition-matroiae case. tilinear relaxation max 1T25T ([(((((())))))))))()((])(()(((() where P(M) is the matroid polytope of the partition matroid and R(x)) denotes the standard randomised rounding. produces feasible set S with V ($) Z (1 !) (S*) 377.
One may apply the continuous-gree algorithm to the mul-
Proof. We recall that V is a nonnegative, monotone, submodular set function on the ground set A. The classic results of [36] and 37 then yield the claimed (1 (11-----aa apprroximatio guarantees under the two matroid constraints.
(a) Uniform-matroid (cardinality) constraint |S| < T.
Let So 0, and for t 1,...,TT T let
A. arg max REASS
(V(S)- -V
S (A.).
(80)
By monotonicity and submodularity one shows inductively (cf. 36 that
V(S.) 2 (1 (1- (1-(1- (S*)) for all L
+)
(81)
20

---

where S is any optimal solution with |S*| - T. In particular at = T,
(ST) 2 -1 -1-113 +) v(S*) 2 (S5))
(82)
(b) Partition-matron ("n=-hot") constraint.
Let M be the partition matroid on A that enforces the n-hot constraint (i.e. each block can contribute most one element), together with the additional global cardinality bound 1Tx S T. Consider the
multilinear extension
F(x) ER-Z (R)],
(83)
where R S A includes each element a independently with probability Vi. The continuous-greedy algorithm (running for time 7' constructs a fractional solution x² E P(M) (x 1 = T} satisfying
F(x") 2 (1 (1-3)
max xEP(M). 1 1TST
F(r) 2 (1- - (S*).
(84)
where S* is the optimal integral solution (cf. (37). Finally, pipage (or swap) rounding converts
x²'
into a random integral set $ E EM of size at most T without decreasing the expectation:
E|((8) F(x*) 2 (1 - (1 ((S").
(85)
By Markov's inequality there exists a deterministic S with Vi$) 2 (1 1 VS*)). completing the proof.
B
Implementation Details
B.1 Model Structure
Our proposed MALinZero consists of 6 neural network modules, including the representation function h, communication function e, dynamic function g. reward function r, value function v and policy function p. For each agent i, let ai,8 be the latent state, of+4 + be the action, ef,e be the cooperative fea- ture and pl,, be the policy prediction where denotes the k-th rollout and t denotes the t-th real-world interaction step. Set k. Ft, the predicted reward and value under the corresponding global hidden state. Specifically, the representation function s h(ozs) maps the current individual observation history oz into the latent space, which enables the model could conduct planning without knowing
the real-world rule. The communication function (ci,,he,,..... = (fe) (fej,bhit,...p hist,..... fal+4he har.....
generates additional cooperative information for each agent in the multi-agent system via the attention mechanism, with the individual states and actions of agents as the input and the cooperative features the output. The dynamic function s a( of+ cf,,) plays the role of obtaining state
transition prediction. The reward function rt, = ((et, (a (c(+sha......)) and value function
vr. u (fef (e....) predicts the reward and value for the global state-action tuple and global state, respectively. The policy distribution of each agent will be the output of the policy function P = p(st,)) with the input of the current individual state. For the general strongly-convex and j--smoth function S, we set (" (0, A.)) = 0.75 X. (0, A.) < 0 and f"(X, (0, A.)) = X, (8, A.) 2 O.
For all these modules except the communication function the neural networks are implemented by Multi-Layer Perception (MLP) networks, and a Rectified Linear Unit (ReLU) activation and Layer Normalization (LN) follows each linear layer in MLP networks. The input observations of all three mentioned benchmarks in the experiment section are 1-dimensional vectors with a hidden state size of 128. For the representation network h. the last four local observations are treated as the input for each agent to deal with partial observability. And before representation, an LN is applied to normalize observation features. The dynamic function applies a residual connection between the next hidden state and the current one to tackle the problem that gradients tend to zero in the continuous unrolling of the model. Additionally, we use the categorical representation in MuZero and make the use of an
21

---

invertible transform f(x) - sign(z) (gg(z))/ 1 + 0.001 z to scale targets for value and reward
prediction.
Specifically, the number of hidden layers for all MLP modules is set as follows:
[128, 128] for Representation function h.
[128, 128] for Dynamic function
[32] for Reward function Value function and Policy function p.
B.2 Training Details
We build training pipeline similar to EfficientZero 40
which synchronizes parallel stages of data collection, reanalysis, and training. In programming, we assign different workers to deal with these tasks in the complete training pipeline. Additionally, choose the same advantage score computation and loss function as MAZero [TO] All experiments are conducted using NVIDIA RTX A6000 GPUs NVIDIA A100 GPUs.
For MatGame environments, we select the number of MCTS sampled actions as and the number of MCTS simulations as 50. For both SMAC and SMACv2 benchmarks, we set it as 7 and the number of MCTS simulations as 100, We list other important syper-parameters in Table 2
Parer-Parameter
Value
Optimizer
Adam
Learning
10-4
RMSprop epsilon
10-6
Weight decay
0
Max gradient norm
$
Evaluation episodes
32
Target network updating interval
200
Unroll steps
TD steps
5
Min replay size for sampling
300
Number of stacked observation
4
Discount factor
0.99
Minibatch
256
Priority exponent
0.6
Priority correction
0.4
Dynamic generation ratio
0.6
À for initialization
10-4
Quantile in MCTS value estimation
0.75
Decay lambda MCTS value estimation
0.8
Exponential factor in Weighted-Adwane
Table 2: Slyper-parameters for MALinZero in MatGame, SMAC and SMACv2 environments
C Details of Baseline Algorithms
MAZero 10 and MAZero-NP implemented based the code: https://github. com/ Slugh16/MAZere with hyper-parameters in Table MAZero-NP refers to MAZero without the prior information in the UCT bound while keeping other implementations the same. For MatGame environments, we select the number of MCTS sampled actions as 3 and the number of MCTS simulations as 50. For both SMAC and SMACv2 benchmarks, we set it as 7 and the number of MCTS simulations as 100. Hyper-parameters of MAZero and MAZero-NP is set as Table
MA-AlphaZero is implemented the codebase of MAZero but replaces the UCT score with that of AlphaZero 6 That is, MA-AlphaZero use the Q-value instead of the advantage score UCT. alpha- zero- general Since the implementation based on MAZero model structure, we use the same syper-parameten in Table 3
The AlphaZero code can be found in https:://// /::::://iii thub.
QMIX 14 is implemented based on the code: http:///ttttb..cooooosss//////// with
hyper-parameters in Table
22

---

JlyperPPrramete
Value
Optimizer
Adam
Learning
10-
RMSprop epsilon
10-s
Weight decay
0
Max gradient norm
5
Evaluation episodes
32
Target network updating interval
200
Unroll sleps
TD steps
5
Min replay size for sampling
300
Number of stacked observation
4
Discount factor
0.99
Minibatch size
256
Priority exponent
0.6
Priority currection
0,4
Quantile in MCTS value estimation
0.75
Decay lambda in MCTS value estimation
0.8
Exponential factor in Weighted-Ad Advatage
Table Syyer-parametent for MAZero, MAZero-NP and MA MA-AlpaaZero MatGame, SMAC and SMACv2 environments
Syyper-Pramettr
Value
Optimizer
RMSProp
Learning actors
10
Learning for crities x 10
Initial
1.0
Final e
0.05
Batch size
32
Buffer size
5000
Discount factor
0.99
Exploration noise
0.1
Table 4: Hyper-paramette parameters for QMIX in MatGame, SMAC and SMACv2 environments
MАPPO
39
implemented based on the code: https://github. httgg//hwwb.c//aaarbbaaaaaaaaaaa
on on-policy The specific hyper-parameters be found in Table
Param-Parretter
Value
Optimizer
Adam
RMSprop epsilon
10
Learning rale
5 10
Recurrent data chunk length
10
Gradient clipping
10
GAE parameter
0.95
Discount factor
0.99
Value loss
huber with delta 10 buffer length x number of agents
Batch size
Table 5:
for MAPPO in MatGame, SMAC and SMACv2 environments
D Settings of Benchmarks
MatGame We test our proposed MALinZero and other baseline algorithms on MatGame with two different modes: (1) Linear mode, where the joint reward is the sum of agents' indexes in the system; (2) Non-linear mode, where noise is added to the joint reward in the corresponding linear mode. For each joint reward, the noise is the sum of a Gaussian term u ~ (0,222 and a uniform term U( 3.
SMAC The implementation and settings of SMAC environments are based on
com/ htth//xwhirr/sse smac We chose three different maps containing a small, medium, and large number of agents, respectively. Experiments on each map conducted under 3 different random seeds for the reproducibility of results.
23

---

SMACv2 The implementation and settings of SMACv2 environments are based on https:// / github. com/ hwwhir1/smaccv For each SMACv2 map in the experiment part, we randomize heterogeneous unit types and start positions for each games even in the same map to make the environment more challenging. Additionally, the unit sight and attack ranges are changed from SMAC to increase the diversity of agents.
24

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction state the claims made, including the contributions made in the paper and important assumptions and limitations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have a limitation section discussing the limitations of this work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Justification:
We provide the full assumptions and proof of all theoretical contributions either in the main paper or in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all the information needed to reproduce the results presented in this paper together with the source code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
26

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide all the information needed to reproduce the results presented in this paper together with the source code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
Polmcy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle wwwppppgpuuiiieeeee http://guuudeee/eeuububbiaiia SooodeSubiissiee ssiiiiolcccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We explained all the details training settings in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We include the error bars in the experiment results section.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We explained all the details on training settings in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp////aaarrs..ccaaaaal//ccttt
Answer: [Yes]
Justification: We conducted the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discussed the potential positive societal impacts and negative societal impacts of the work performed at the end the paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We believe this paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
29

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
30

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpp/////euips..... wwwpariipssccooooeeeeeee cc/Conferencess///////eeeccc/eee for what should or should be described.
31


Reviews:
[{"review_id": "TtjeNcpUQ3", "reviewer": "Reviewer_hYgq", "summary": "This paper introduces MALinZero, a novel algorithm for multi-agent planning that incorporates low-dimensional representations of joint-action returns into Monte Carlo Tree Search (MCTS). The method models joint action values as a contextual linear bandit problem and derives a variant of Upper Confidence Bounds for trees, dubbed LinUCT, to guide efficient exploration. The paper presents regret analysis, derives an approximate algorithm to minimize it, an evaluates it over against existing baselines on MatGame, SMAC, and SMACv2.", "questions": "See above.", "limitations": "See above.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is very well written, ideas and results are presented clearly, and related work is well covered. \nI am not very familiar with the subject, though, so I may not be aware of missing references.\n\nWhile the idea of low-dimensional decomposition has been explored in previous MARL work (the authors cite QMIX and VD), the idea of transforming joint action return estimation in MCTS into a contextual linear bandit problem seems novel to me, and useful especially in MA problems where the joint action space grows exponentially. \n\n- How does MALinZero differs in terms of how it uses confidence bounds for exploration in contrast to value factorization? As someone not very familiar with the subject, I would appreciate a concise and clear conceptual comparison against baselines, and a recap of contributions at the end of the paper.\n\n- How does MALinZero scale to larger problems? The problem of scalability is briefly mentioned in the related work section, but not addressed later. Is MALinZero better than baselines in this regard? \n\n- How would MALinZero perform with different losses? E.g., Huber or exponential.\n\nThe authors also provide an extensive empirical evaluation, showing that MALinZero consistently outperforms all baselines across linear and nonlinear reward environments. \n\n- All algorithms are evaluated over 3 seeds only. I am not familiar with the environments, but in classic RL 3 seeds are usually unacceptable. I strongly encourage the authors to run more seeds. Also, please indicate what the shaded are and the +/- in the table are (standard deviation? confidence interval?).", "was_revised": true, "final_justification": "The authors have address my concerns, thus I have increased my score.", "rebuttal": "Thank you very much for your positive recommendation of our work and your insightful comments. Following are our responses to your concerns. \n\n**Q1: How does MALinZero differs in terms of how it uses confidence bounds for exploration in contrast to value factorization? As someone not very familiar with the subject, I would appreciate a concise and clear conceptual comparison against baselines, and a recap of contributions at the end of the paper.**\n\nValue-function factorization methods in multi-agent reinforcement learning (such as VDN, PAC, Qatten, DOP, FOP, PAC) do not explicitly model the uncertainty of the learned Q-value, which are resulted from limited samples during exploration-exploitation. They often choose optimal actions based on the expected Q-values -- which are obtained following a factorized structure -- and then rely on heuristics or introduce regularization terms to encourage exploration. Examples include $\\epsilon$-greedy (taking the optimal action \\\\(a_t=\\arg\\max_a Q_i(s_i,a)\\\\) with the probability of \\\\((1-\\varepsilon_t)\\\\) and a random action with probability \\\\(\\varepsilon_t\\\\)); soft-actor critic to an entropy term encouraging exploration; and introducing intrinsic reward terms to explore unseen states/actions. \n\nIn contrast, MALinZero models the Q-values from limited samples as distributions (which are estimated using limited samples) and derive mathematical guarantees on the potential return of each joint action through confidence bounds. It considers a multi-armed bandit formulation to provide a formal, rigorous framework of considering the uncertainty in exploration-exploitation. Compared with previously mentioned algorithms, the exploration using confidence bound can focus on the action with both high return and high potential automatically, instead of trying each action with the same probability \\\\(\\varepsilon\\\\).\nThese MCTS based solutions are known to be significantly more sample efficient than multi-agent reinforcement learning, as demonstrated by single-agent MCTS algorithms like MuZero and MAZero.  \n\nOur paper proposes a factorized confidence bound (rather than a factorized Q value) to guide exploration-exploitatio in MCTS, when multiple agents are involved. Intuitively, consider a linear factorization of $Q$ into $Q_1, Q_2, ... Q_n$. Estimating the mean of $Q$ only requires a sum over the mean of each $Q_i$. But a confidence bound on the joint $Q$ must evaluate the probability $P(Q-\\bar{Q})<\\epsilon$ with respect to the joint distribution of $Q_i$s using limited samples. Moreover, the adaptive and dynamic update of confidence bound is more suitable for long-horizon decision-making, especially with the help of the tree structure while \\\\(\\varepsilon\\\\)-greedy deals with single-step stochastic exploration. In conclusion, we apply the LinUCT to facilitate the exploration and exploitation in the low-dimensional space, which deals with uncertainties more efficiently and effectively with faster convergence compared with baselines. We will add the comparison and recap of contributions in a further version of our paper.\n\n**Q2: How does MALinZero scale to larger problems? The problem of scalability is briefly mentioned in the related work section, but not addressed later. Is MALinZero better than baselines in this regard?**\n\nThe goal of MALinZero is to improve scalability by introducing a linear structure for efficient evaluation of the confidence bound. Consider a decision-making problem involving $n$ agents, each with $d$ actions. A standard approach (such as SOTA method MAZero) would need to consider sampling \\\\(\\mathcal{O}(d^n)\\\\) possible joint actions (to estimate their confidence bounds). MALinZero considers a linearly factorized structure reducing this to sampling \\\\(\\mathcal{O}(dn)\\\\) actions. This is a significant reduction especially in systems with large number $n$ of agents.\n\nAs a result, MALinZero only samples fixed number of child nodes for each node in the Expansion stage instead of traversing the exponentially large action space to search candidate actions. Moreover, we leverage the Sherman-Morrison formula [1] to reduce the computing complexity of updating parameter \\\\(\\theta\\in\\mathbb{R}^{nd}\\\\) form \\\\(\\mathcal{O}(n^2d^2)\\\\) to \\\\(\\mathcal{O}(nd)\\\\). Therefore, the computational cost of each step of MALinZero is only linearly related to the product of the number of agents \\\\(n\\\\) and the number of actions \\\\(d\\\\) of each agent, rather than an exponential relationship; compared with MAZero, its scalability does not depend on the explosive growth of the number of joint actions, and it actually performs better in scenarios with large \\\\(n\\\\) and \\\\(d\\\\). We note that there are some additional cost involved in Dynamic Node Generation (DNG) using MALinZero, but it is insignificant compared with the substantial reduction of search space.\n\n**Q3: How would MALinZero perform with different losses? E.g., Huber or exponential.**\n\nWe choose our current loss to be consistent with existing search-based reinforcement learning algorithms both for single-agent problems [2] [3] and multi-agent problems [4]. Since the loss is proven useful and powerful in model-based reinforcement learning algorithms equipped with MCTS, we also adopt this loss. This will ensure a fair comparison with the baselines.  In this work, we want to emphasize the novelty in terms of low-dimensional representation, LinUCT, and submodular maximization-based joint action selection instead of designing a new loss.\n\n**Q4: All algorithms are evaluated over 3 seeds only. I am not familiar with the environments, but in classic RL 3 seeds are usually unacceptable. I strongly encourage the authors to run more seeds. Also, please indicate what the shaded are and the +/- in the table are (standard deviation? confidence interval?).**\n\nThanks for pointing this out. To address the concern, we further evaluate algorithms on two MatGame environments (6,8,Linear) and (6,8,Non Linear) over 5 random seeds and report the results here. \n| Agent | Action | Type       | Steps | MAZero       | MAZero-NP     | MA‑AlphaZero | MAPPO         | QMIX          | **MALinZero** |\n|:-----:|:------:|:----------:|:-----:|:------------:|:-------------:|:------------:|:-------------:|:-------------:|:-------------:|\n| 6     | 8      | Linear     | 1000  | 393.2±9.5    | 387.6±9.8     | 389.9±8.7    | 391.8±10.1    | 384.9±10.7    | **395.8±9.1** |\n| 6     | 8      | Linear     | 2000  | 432.3±6.9    | 426.1±9.2     | 433.1±9.4    | 430.2±8.9     | 431.2±7.3     | **438.2±6.3** |\n| 6     | 8      | Non‑Linear | 1000  | 399.1±12.9   | 390.4±10.1    | 392.3±11.9   | 389.1±13.7    | 391.3±12.8    | **407.2±7.3** |\n| 6     | 8      | Non‑Linear | 2000  | 442.3±11.8   | 427.3±8.4     | 425.9±7.8    | 428.7±8.9     | 433.2±8.1     | **449.8±12.1**|\n\nThe shaded area and the \\(+/-\\) in this paper refer to one stand deviation. At the beginning of conducting experiments, we also evaluated all algorithms over more seeds. We found relatively consistent results over different seeds. \n\n\n\n[1] Sherman, Jack, and Winifred J. Morrison. \"Adjustment of an inverse matrix corresponding to a change in one element of a given matrix.\" The Annals of Mathematical Statistics 21.1 (1950): 124-127.\n\n[2] Schrittwieser, Julian, et al. \"Mastering atari, go, chess and shogi by planning with a learned model.\" Nature 588.7839 (2020): 604-609.\n\n[3] Hubert, Thomas, et al. \"Learning and planning in complex action spaces.\" International Conference on Machine Learning. PMLR, 2021.\n\n[4] Liu, Qihan, et al. \"Efficient multi-agent reinforcement learning by planning.\" arXiv preprint arXiv:2405.11778 (2024)."}, {"review_id": "4Q7nSYoxBd", "reviewer": "Reviewer_oPgB", "summary": "The authors address the problem of the exponential action space blowup in multi-agent model based RL algorithms that rely on tree-search (like MAzero). The authors learn a low dimensional linear approximation of the reward function (for every hidden state).  The authors then propose using the UCB algorithm for a linear bandit, to select actions for expanding the tree search. This strikes a balance between exploration of new actions and exploitation of high rewarding actions, instead of expanding the tree for all possible actions. In benchmark tasks like MatGame and SMAC, the algorithm shows consistent improvement over baselines.", "questions": "1) Do you need to learn a reward function new approximation for different latent states? How computationally efficient is this? How is data generated to learn this function?\n\n2) At every-step during expansion, you need to run the linUCB algorithm to select an action, what additional computational and memory overheads does this cause?\n\n3) What happens when compute becomes orders of magnitude cheaper? Do you think the low rank approximation will still achieve better performance?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1) The strengths of the paper are a clear and detailed theoretical analysis of the MALinZero algorithm.\n2) The empirical performance on all benchmark tasks considered seem strong when compared to the baselines.\n\nWeaknesses:\n1) The paper seems to have a lot of technical details about UCB, linear bandits and regret analysis. This makes it a little difficult to read for practitioners / non-theory researchers. It also makes it less clear if the main contributions are theoretical /  empirical. I do not work in multi-agent RL /  multi-agent RL theory, so it is a bit difficult to gauge how strong the theoretical / empirical results are.\n\n2) How relevant do these algorithms remains when compute becomes orders of magnitude cheaper? Every agent can consider other agents as a part of the environment and use algorithms like sampled muzero to plan.", "was_revised": true, "final_justification": "My final recommended score is 4. The algorithm solves the problem of large action spaces in multi-agent planning. They do so by learning a low dimensional linear approximation of the reward function and rapidly solving a contextual bandit problem to select actions for node expansion during tree search. The paper also demonstrates stronger performance in common multi agent RL benchmarks.", "rebuttal": "Thank you for recognizing the novelty of our work. In what follows, we address the raised questions and weaknesses point-by-point.\n\n**W1: The paper seems to have a lot of technical details about UCB, linear bandits and regret analysis. This makes it a little difficult to read for practitioners / non-theory researchers. It also makes it less clear if the main contributions are theoretical / empirical. I do not work in multi-agent RL / multi-agent RL theory, so it is a bit difficult to gauge how strong the theoretical / empirical results are.**\n\nOur main contributions are two-fold: (i) The novel use of linear contextual bandit to enable factorization of multi-agent MCTS problems and the derivation of various guarantees; (ii) The design of MALinZero algorithm demonstrating significant reduction in joint action search. State-of-the-art MCTS algorithms such as MuZero and MAZero do not consider this type of factorization in terms of confidence bounds, making them not scalable as the number of agents increase. Empirical and the extensive experiments have shown consistent performance improvements over all baselines in benchmarks such as MatGame, SMAC and SMACv2. \n\nThe algorithm design of MALinZero is based on solid theories. Specifically, we apply the contextual bandit theory [1] to design LinUCT which enables the low-dimensional representation of joint action and provides theoretical guarantee for regret analysis. Moreover, we propose a \\\\((1-\\frac{1}{e})\\\\) approximation algorithm based on the submodular maximization theory [2] to select joint action. Additionally, to achieve efficient Backpropagation practically in MCTS we update the parameter according to the Sherman-Morrison formula [3], successfully reducing the computing complexity from \\\\(\\mathcal O(n^2d^2)\\\\) to the linear order \\\\(\\mathcal{O} (nd)\\\\) where \\\\(n\\\\) is the anget number and \\\\(d\\\\) is the space size of single action.\n\n**W2: How relevant do these algorithms remains when compute becomes orders of magnitude cheaper? Every agent can consider other agents as a part of the environment and use algorithms like sampled muzero to plan.**\n\n**Q3: What happens when compute becomes orders of magnitude cheaper? Do you think the low rank approximation will still achieve better performance?**\n\nFirst, we want to point out that MALinZero improves complexity from exponential to linear with respect to the number of agents. Consider a decision-making problem involving $n$ agents, each with $d$ actions. A standard approach (such as SOTA method MAZero) would need to consider sampling \\\\(\\mathcal{O}(d^n)\\\\) possible joint actions (to estimate their confidence bounds). MALinZero considers a linearly factorized structure reducing this to sampling \\\\(\\mathcal{O}(dn)\\\\) actions. Consider a problem with $n=10$ agents and $d=8$ actions. This is a reduction from $8^{10}$ to $8\\times 10$, which goes beyond computation cost factor.\n\nWe would also like to clarify that there are two different types of complexity involved here. One is sampling complexity (i.e., sampling the game environment with actions chosen) and the other is computational complexity. Sampling a physical environment (e.g., autonomous driving) has overhead/cost factors outside computation. By reducing the sampling overhead from exponential to linear, MALinZero achieves a huge saving that is not seperate from computation cost.\n\nThe mentioned distributed training and distributed execution (DTDE) must learn with respect to changing behavior of other agents (which are also updated during training), when they are considered as part of an environment (that now becomes stochastic). \n\n**Q1: Do you need to learn a reward function new approximation for different latent states? How computationally efficient is this? How is data generated to learn this function?**\n\nIn MALinZero, the reward function is trained with the representation function jointly so we do not need to learn a reward function for different latent states. This is the same method used in state-of-the-art MCTS solutions, such as MuZero and MAZero. It has been shown to be efficient even for very complex games such as go and chess.\n\nTo provide more details, the input of reward function are the states \\\\((s^1_t,\\dots,s^n_t)\\\\) and actions \\\\((a^1_t,\\dots,a^n_t)\\\\) of all agents at time step \\\\(t\\\\) and the output is the reward \\\\(r_t\\\\) for taking the input action at the input state. The training data comes from the interaction of model with the environment, which is also a conventional strategy to get training data for online reinforcement learning. For better understanding, we can wrap the complex architecture and networks of MALinZero into a simple model-based algorithm since the training procedure remains the same. At the beginning of training, the untrained model interacts with the environment and then some trajectories including \\\\(s,a,o,r\\\\) are generated, where \\\\(s,a,o\\\\) is the state-action-obervation tuple and \\\\(r\\\\) is the reward given by the environment. When there are sufficient trajectories in the buffer, the algorithm could apply them to train the reward function and other networks as conventional reinforcement learning algorithms do. The learned model will interact with the environment to generate new data and these new data are further used to train the model. \n\n\n**Q2: At every-step during expansion, you need to run the linUCB algorithm to select an action, what additional computational and memory overheads does this cause?**\n\nThis is a good questions. Yes, running the LinUCB algorithm will incur minor additional cost. However, the computation leverages a linear structure with sampling \\\\(\\mathcal{O}(dn)\\\\) actions rather than the standard \\\\(\\mathcal{O}(d^n)\\\\). Compared with this reduction from exponential to linear, the additional computation cost is negligible. Our evaluation shows that the computational cost is comparable to that of the MAZero [4] method. We will include additional explanations in the revised version. \n\n[1] Wang, Chih-Chun, Sanjeev R. Kulkarni, and H. Vincent Poor. \"Bandit problems with side observations.\" IEEE Transactions on Automatic Control 50.3 (2005): 338-355.\n\n[2] Nemhauser, George L., Laurence A. Wolsey, and Marshall L. Fisher. \"An analysis of approximations for maximizing submodular set functions—I.\" Mathematical programming 14.1 (1978): 265-294.\n\n[3]Sherman, Jack, and Winifred J. Morrison. \"Adjustment of an inverse matrix corresponding to a change in one element of a given matrix.\" The Annals of Mathematical Statistics 21.1 (1950): 124-127.\n\n[4] Liu, Qihan, et al. \"Efficient multi-agent reinforcement learning by planning.\" arXiv preprint arXiv:2405.11778 (2024)."}, {"review_id": "iinrSx7CLS", "reviewer": "Reviewer_PKqZ", "summary": "This paper proposes MALinZero for efficient low-dimensional search in multi-agent planning. The approach projects joint-action returns into a low-dimensional space via a contextual linear bandit formulation, and solves this contextual linear bandit problem with convex and $\\mu$-smooth loss functions. It reduces the tree search complexity from the exponential in the number of agents to linear in the number of agents. Results on SMAC demonstrate that MALinZero outperforms state-of-the-art methods in this multi-agent tasks.", "questions": "- Are all agents considered within a single MCTS process? If so, is MCTS applied during test time? If it is used, does the method still comply with the Centralized Training and Decentralized Execution (CTDE) paradigm?\n- The paper introduces a strongly convex and $\\mu$-smooth distance measure f, and discusses its benefits. However, it is unclear how f achieves the desired behavior. For example, line 186 states: “For higher observed rewards X_t that are likely optimal, the distance measure f will have a larger acceleration”. Does this behavior also apply to higher observed rewards that are not optimal? Further clarification and justification would strengthen the argument.\n- In high-dimensional multi-agent tasks, will the same state be encountered multiple times? I’m curious whether the MCTS is truly maintaining a tree structure, or just some independent trajectories, especially in this multi-agent setting.\n- see Weaknesses.", "limitations": "The authors acknowledge the limitations of their work and outline directions for future improvement.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper proposes a novel method for multi-agent planning that reduces the complexity of tree search from exponential to linear in the number of agents, which is theoretically sound.\n- The proposed method is evaluated on the SMAC benchmark and compared against both model-free and model-based baselines.\n\nWeaknesses\n- The writing can be improved. There are many repeated phrases across the abstract, introduction, and related work sections, which makes the paper feel redundant. \n- It would be helpful to clearly state at the beginning of the paper that the proposed method applies only to the cooperative multi-agent setting.\n- The provided code repository lacks a README file, making it difficult to install dependencies and reproduce the results.\n\nminors:\n- line 149, linear bandit problem []\n- line 178, UCB1 and LinUCB []", "was_revised": true, "final_justification": "The authors have done a good job in addressing my concerns. I raise my score accordingly.", "rebuttal": "Thank you for your detailed feedback. We have made corresponding revisions to the paper per the comments that reviewers kindly provided.\n\n**W1: The writing can be improved. There are many repeated phrases across the abstract, introduction, and related work sections, which makes the paper feel redundant.**\n\nWe will improve some of the expressions in the later version of our paper and try our best to make it more concise and clearer for readers.   \n\n**W2: It would be helpful to clearly state at the beginning of the paper that the proposed method applies only to the cooperative multi-agent setting.**\n\nThanks for your suggestion. We will clarify that MALinZero applies to cooperative multi-agent settings. \n\n**W3: The provided code repository lacks a README file, making it difficult to install dependencies and reproduce the results.**\n\nThanks for your understanding. Due to the latest rebuttal format, we can not include any links or PDF files during this process, so it is hard to provide a clear README file now. The README file will be updated to our supplementary file later. \n\n**Q1: Are all agents considered within a single MCTS process? If so, is MCTS applied during test time? If it is used, does the method still comply with the Centralized Training and Decentralized Execution (CTDE) paradigm?**\n\nWe consider a single MCTS process. \n\nDuring the test time, each agent will run its local instance of MCTS with the learned networks to simulate a fixed number of rollouts and then select the action according to the policy distribution of the root node. During training, action selections after factorizing and computing local confidence bounds are decentralized. Since each agent runs its local MCTS, MALinZero is completely CTDE. Specifically, all models are learned in the centralized manner with global states while the execution is fully decentralized: each agent carries its own copy of the learned model and exchanges only the observation to others without the central controller.  \n\n\n**Q2: The paper introduces a strongly convex and $\\mu$-smooth distance measure $f$, and discusses its benefits. However, it is unclear how $f$ achieves the desired behavior. For example, line 186 states: “For higher observed rewards $X_t$ that are likely optimal, the distance measure f will have a larger acceleration”. Does this behavior also apply to higher observed rewards that are not optimal? Further clarification and justification would strengthen the argument.**\n\nIntuitively, the introduction of a distance measure $f$ exploits the fact that estimation errors on different actions do not have the same impact on performance. Overestimating the return of an optimal action would still allow it to be selected (with no performance gap), while underestimating the return of a non-optimal action would not make it favorable (again with no performance gap). However, the opposite is not true (i.e., overestimating a non-optimal action or underestimating an optimal action). \n\nWQMIX [1] first leveraged this idea. Compared with QMIX [2], WQMIX does not treat each agent equivalently while it assigns higher weights for the joint actions with higher value to overcome the information loss of optimal actions due to the average operation in QMIX. \n\nLet's further analyze the example on line 191. Let \\\\(r=X_s-\\langle\\theta, A_s\\rangle\\\\) and then we can get \\\\(\\frac{\\partial f(r)}{\\partial \\theta}=2 w \\frac{\\partial r}{\\partial \\theta}\\\\). When \\\\(r\\ge 0\\\\), i.e., the model is under‑estimating, we assign\\\\(w=w_+\\\\) with a large \\\\(w_+\\\\) to amplify the update step \\\\(\\Delta\\theta\\propto-2w_+r\\partial r\\\\), thus accelerating the learning of \\\\(\\theta\\\\). Otherwise, if \\\\(r < 0\\\\), we will assign a small weight \\\\(w_-\\\\) to \\\\(w\\\\) to avoid the over-correction since the model is over-estimating. And this behavior also applies to the higher observed rewards that are not optimal since \\\\(w\\\\) depends on whether we over- or under-estimate the reward.\n\n\n**Q3: In high-dimensional multi-agent tasks, will the same state be encountered multiple times? I’m curious whether the MCTS is truly maintaining a tree structure, or just some independent trajectories, especially in this multi-agent setting.**\n\nIn MALinZero or many other search-based reinforcement learning algorithms [3] [4] [5], the node in a MCTS process is denoted by \\\\((s,a)\\\\) where \\\\(s\\\\) is the state and \\\\(a\\\\) is the action leading to this state. At a certain state \\\\(s\\\\), if the algorithm selects an action \\\\(a'\\\\), then the index will move from the node \\\\((s,a)\\\\) to node \\\\((s', a')\\\\) where \\\\(s'\\\\) comes from the dynamic model. During the entire MCTS process, every time \\\\(a'\\\\) is selected at \\\\((s,a)\\\\), the index will point to \\\\((s',a')\\\\). Meanwhile, the number of sampled actions is finite, so nodes are likely getting revisited within \\\\(K\\\\) simulation times -- which is the necessary to sample actions with not only a high observed return (due to limited samples), but also actions with high potential to yield a high return, through the computation of a confidence bound. Therefore, the MCTS is truly maintaining a tree structure.\n\n**Minors: line 149, linear bandit problem [], line 178, UCB1 and LinUCB []**\n\nWe will revise the lost reference you mentioned in the later version of our paper, which should be [6].\n\n[1] Rashid, Tabish, et al. \"Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning.\" Advances in neural information processing systems 33 (2020): 10199-10210.\n\n[2] Rashid, Tabish, et al. \"Monotonic value function factorisation for deep multi-agent reinforcement learning.\" Journal of Machine Learning Research 21.178 (2020): 1-51.\n\n[3] Schrittwieser, Julian, et al. \"Mastering atari, go, chess and shogi by planning with a learned model.\" Nature 588.7839 (2020): 604-609.\n\n[4] Hubert, Thomas, et al. \"Learning and planning in complex action spaces.\" International Conference on Machine Learning. PMLR, 2021.\n\n[5] Liu, Qihan, et al. \"Efficient multi-agent reinforcement learning by planning.\" arXiv preprint arXiv:2405.11778 (2024).\n\n[6] Li, Lihong, et al. \"A contextual-bandit approach to personalized news article recommendation.\" Proceedings of the 19th international conference on World wide web. 2010."}, {"review_id": "QH99NLDZsM", "reviewer": "Reviewer_EsMc", "summary": "This paper, MALinZero, proposes a new way to tackle a big problem in multi-agent planning with Monte Carlo Tree Search (MCTS): the action space gets huge very fast. Their idea is to represent joint-action returns in a low-dimensional space, treating it as a contextual linear bandit problem. They introduce a new LinUCT (Linear Upper Confidence Bound applied to trees) for MCTS that helps explore and exploit this lower-dimensional space. They also use a special \"loss function\" that's convex and smooth to make sure they don't miss out on good actions. The paper claims MALinZero has good theoretical guarantees, like regret bounds, and they show that picking actions is like maximizing a submodular function, which has a known approximation algorithm. Plus, they say they made the back-propagation part more efficient. They tested MALinZero on matrix games, SMAC, and SMACv2. They report it beats other model-based and model-free methods, learning faster and performing better.", "questions": "1. **How are \"latent per-agent action rewards\" learned?** Section 3.1 talks about these rewards, $\\theta^{\\ast}$, but the high-level representation model $h_{\\theta}$ (mentioned for MuZero) isn't clearly connected to how these specific latent rewards are actually derived from observations. Is there a neural network learning this projection? If so, what's its structure?\n2. **Details on the General Loss Function $f$:** You introduce the generalized loss function $f$ with $w_{+}$ and $w_{−}$. How are these values determined for different rewards ($X_s\\ge\\langle\\theta,A_s\\rangle$ vs. $X_s<\\langle\\theta,A_s\\rangle$)? Are they fixed, hand-tuned hyperparameters, or are they learned during training? This is important for practical application.\n3. **Clarify Back-Propagation Notation in Algorithm 1:** Please clarify the $\\theta(s)$ update: \"$\\theta(s)\\leftarrow V(s)^{-1}r_{k}a$\". How does this specific $r_{k}$ relate to $X_s$ in the sum for $\\hat{\\theta}_{t}$? A consistent and precise update rule would be much better.\n4. **More in Main Text, Less in Appendices, please!** The paper refers to Appendices A, B, and D constantly. Without them, it's impossible to properly evaluate the theoretical claims, understand the model's architecture, or verify the experimental setup. Could you explain them more clearly in the MAIN TEXT, or at least provide a sketch explanation?\n\nMy score could increase if you address my concerns and clarify the core mechanisms (representation learning, loss function parameters, back-propagation notation). It would decrease if these fundamental aspects remain unclear.", "limitations": "The authors mention two limitations: the current linear bandit formulation and the open problem of fully decomposable representations. These are fair.\n\nHowever, I think they should also explicitly acknowledge:\n\n- **Computational Overhead of Submodular Maximization:** While theoretically elegant, the practical speed implications of solving a submodular maximization problem (even approximately) during each MCTS selection step need to be considered and perhaps quantified, especially for time-sensitive applications.\n- **Hyperparameter Sensitivity of the Generalized Loss Function:** The novel loss function $f$ with its potentially tunable parameters ($w_{+}$, $w_{−}$) could introduce new challenges for hyperparameter tuning. It would be good to discuss the sensitivity of the method to these parameters as a potential limitation.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- **Tackles a Real Problem:** They're going after the exponential action space issue in multi-agent MCTS, which is a genuinely tough nut to crack. That's a solid motivation for the work.\n- **Novel Approach for MCTS:** Using a contextual linear bandit and LinUCT to project into a low-dimensional space for *multi-agent MCTS* is pretty neat. While these ideas exist elsewhere (like low-dimensional representations in MARL), their specific combination and theoretical backing for MCTS exploration is a notable contribution.\n- **Theoretical Backing:** They've got regret bounds and they've shown the action selection is a submodular optimization problem, which gives it a good theoretical foundation.\n- **Good Experimental Results:** The empirical results look strong across the benchmarks they chose. Outperforming existing methods, especially on SMACv2 where they claim to nearly double winning rates, is impressive. The speed-up claims are also interesting.\n\n### Weaknesses\n\n- **The \"General $f$\" Loss Function Needs More Detail:** They introduce this fancy convex and smooth loss function $f$ to avoid underestimating good actions. They give an example with $w_{+}$ and $w_{−}$. But how do you *choose* these weights in practice? Is it fixed? Is it tuned? Is it learned? This is crucial for understanding its real-world applicability and why it helps so much in the ablation study.\n- **Dynamic Node Generation (DNG) Sampling:** Algorithm 1 says DNG uses \"$\\beta$ and $P$ as Sampled MuZero\" for sampling new nodes. That's pretty vague. What exactly are $\\beta$ and $P$ in their context? How does this sampling work? Clarity here is needed.\n- **Computational Overhead of Submodular Maximization:** They proved action selection is submodular, which is cool, but they don't really talk about the practical speed impact of using an approximation algorithm for it during the MCTS rollout. MCTS relies on fast tree traversal. Does this add a noticeable overhead? How does it compare to the simpler UCB-like selections in other MCTS methods?\n- **Hard to Follow WITHOUT Appendix:** It's impossible to properly review this paper without the appendices. They refer to them *constantly* for proofs, architecture details, and experimental settings. Without these, I can't check their math, understand their \"low-dimensional representation\" fully, or see how their models are structured.", "was_revised": true, "final_justification": "The authors resolved most of my concerns and questions about the technical details of MALinZero in the rebuttal, and in light of this, I have raised my score towards acceptance. However, the clarity of its writing still needs improvement, and I can only believe that the authors will fulfill the promised revisions.", "rebuttal": "Thank you for your constructive and detailed suggestions. Our answers to your questions are provided below. \n\nDue to character limit, in order to use more space to answer your concerns in detail, we will not repeat the content of your question here, but will use numbers instead. We are deeply sorry for the inconvenience caused.\n\n**W1**\n\n**Q2**\n\nIn the current version of MALinZero, the values of \\\\(w_+\\\\) and \\\\(w_-\\\\) are fixed as \\\\(1\\\\) and \\\\(0.75\\\\) respectively. The design and setting of weights are inspired by the classic multi-agent reinforcement learning algorithm WQMIX [1]. In WQMIX, two fixed different weights are applied for cases where the joint reward is over-estimated and under-esitimated. We are interested in investigating whether a more sophisticated weighting function will bring extra performance improvement empirically and plan to do this in the future work. From the theoretical aspect, we have analyzed and derived the regret of LinUCT with the strongly-convex and \\\\(\\mu\\\\)-smooth function \\\\(f\\\\) so the difference of function designing will not damage our theoretical results. \n\n**W2**\n\n\\\\(\\beta\\\\) and \\\\(P\\\\) are applied in the Expansion stage. \\\\(P(s,a)\\\\) is the policy distribution output of policy network for state \\\\(s\\\\) and action \\\\(a\\\\). Both of them provide the prior information to guide the sampling in Expansion to pay more attention to actions with higher policy priors. Specifically, we compute a vector \\\\(\\beta_i(s)\\\\) for agent \\\\(i\\\\) and \\\\(\\beta_i(s)\\propto \\operatorname{pow}(P(s), 1/\\tau)\\\\) where \\\\(\\tau\\\\) is the temperature coefficient. In implementation, we sample the individual action with \\\\(\\beta_i\\\\) values for each action and then concatenate them to obtain the joint actions. By repeating this process for \\\\(K\\\\) times, we can get the \\\\(K\\\\) child nodes for the current node. \n\n**W3**\n\nThis is a great question. Putting our short answers first: Yes, Submodular Maximization will introduce minor computation overhead, but it is necessary to leverage the linear factorization in MALinZero to reduce the search complexity of joint actions from the standard \\\\(\\mathcal{O}(d^n)\\\\) to \\\\(\\mathcal{O}(dn)\\\\). The overhead of Submodular Maximization is negligible with respect to this reduction from exponential to linear. \n\nWith the linear structure in LinUCB, the problem of computing confidence bound and selecting optimal actions becomes a linear contextual bandit problem that cannot be computed using standard UCB. Thus the Submodular Maximization is proposed to solve this new problem. Running the LinUCB algorithm will incur minor additional cost. However, the computation leverages a linear structure with sampling \\\\(\\mathcal{O}(dn)\\\\) actions rather than the standard \\\\(\\mathcal{O}(d^n)\\\\). Compared with this reduction from exponential to linear, the additional computation cost is negligible. Our evaluation shows that the computational cost is comparable to that of the MAZero [4] method. We will include additional explanations in the revised version. \n\nWe also provide further details on this computation. First, we only select actions requiring submodular maximization for \\\\((1-\\zeta)\\chi\\\\) where \\\\(\\zeta\\\\) is the dynamic generation ratio and \\\\(\\chi\\\\) is the maximum number of child nodes for a node. For example, if we expand \\\\(5\\\\) child nodes at most for a node and set the dynamic generation ratio \\\\(\\zeta\\\\) as \\\\(0.6\\\\), then we only need to select \\\\(2\\\\) action by solving the submodualr maximization thus the overhead is not that huge but the benefit is noticeable. If we search the currently optimal action by the exhaustive method, the complexity will be \\\\(\\mathcal{O}(d^n)\\\\) where \\\\(d\\\\) is the size of individual action space and \\\\(n\\\\) is the agent number. However, the complexity of submodular maximization is \\\\(\\mathcal{O}(n^2d)\\\\), which is much smaller than that of exhaustive method.\n\n**W4**\n\n**Q4**\n\nUnfortunately we were not able to include all details in the main text due to page limit. We will make some room and provide sketch explanations in the main text, about the theoretical results, model's architecture and the experiment setting in the main text. Please see the following text. \n\n__Model architecture.__\nMALinZero consists of 6 neural networks to be learned during the training and the parameter \\\\(\\theta\\\\) is to be estimated from initialization for a single MCTS process. Specifically, with network parameter \\\\(\\phi\\\\), there are 6 key functions: the representation function \\\\(s^i_{t,0}=h_\\phi(o^i_{\\le t})\\\\) that maps the current individual observation history into the latent space, the communication function $e^1_{t,k},\\dots, e^n_{t,k} = e_\\phi(s^1_{t,k},\\dots,s^n_{t,k},a^1_{t,k},\\dots,a^n_{t,k})$ that generates cooperative information for each agent via the attention mechanism, the dynamic function \\\\(s^i_{t,k+1} = g_\\phi(s^i_{t,k}, a^i_{t+k}, e^i_{t,k})\\\\) that plays the role of transition function, the reward function \\\\(r_{t,k}=r_\\phi (s^1_{t,k},\\dots,s^n_{t,k},a^1_{t,k},\\dots,a^n_{t,k})\\\\) and the value function \\\\(v_{t,k}=v_\\phi(s^1_{t,k},\\dots,s^n_{t,k})\\\\) that predicts the reward and value respectively, and the policy function \\\\(p^i_{t,k} = p_\\phi(s^i_{t,k})\\\\) that predicts the policy distribution for the given state. The subscript \\\\(k\\\\) denotes the index of unrolling steps within one simulation from the root node in MCTS. The update of estimated \\\\(\\theta\\\\) takes place in the Back-propagation stage and the detailed process is analyzed in the main text, especially in the last part of Section 3.3. For all these modules except for the communication function \\\\(e_\\phi\\\\), the neural networks are implemented by Multi-Layer Perception (MLP) networks and a Rectified Linear Unit (ReLU) activation and Layer Normalization (LN) follows each linear layer in MLP networks. The Transformer architecture [2] with three stacked layers to encode the state-action pairs. And agents process local dynamics and make predictions with the encoded information. \n\n__Experiment setting.__\nAll experiments are conducted using NVIDIA RTX A6000 GPUs and NVIDIA A100 GPUs. For MatGame environments, the number of sampled actions for each node in MCTS is 3 and the number of MCTS simulations is 50. For both SMAC and SMACv2 benchmarks, we set them as 7 and 100, respectively. We build our training pipeline similar to EfficientZero [3] which synchronizes parallel stages of data collection, reanalysis, and training.\n\n__Proof outline.__ We have provided a brief outline in the appendix at the beginning of each proof. We will further simplify and move some of these to the main text. Thanks for this suggestion!\n \n**Q1**\n\nOur solution is not try to learn the \"per-agent action rewards\". It learns the joint reward, and more importantly, the corresponding confidence bound under a linear structure. For each node \\\\((s,a)\\\\) where \\\\(s\\\\) denotes the state and \\\\(a\\\\) denotes the action leading to \\\\(s\\\\), $\\theta^\\*\\in\\mathbb{R}^{nd}$ is maintained and learned during the MCTS process. The linear structure allows us to learn the confidence bounds (by estimating \\\\(\\theta^\\*\\\\) and its confidence set \\\\(\\mathcal{C}_t\\\\) on Page 4) and directly use the results for action selection (by solving the Submodular Maximization on Page 5). Our solutions combines these steps into a single process to sample actions using the confidence bounds. \n\nTo provide further details, when a new node is expanded and added to the search tree, $\\hat\\theta$ used to estimate \\\\(\\theta^\\*\\\\) is initialized as \\\\(\\mathbf{0}\\\\). The per-node initialization makes sense because it is helpful to achieve better per-state reward estimation and the next-node selection for each node can be viewed as an independent bandit problem. \\\\(\\hat\\theta\\\\) is update in the Back-propagation stage by the observed reward. After multiple round of update, the estimator will be more and more precise. \n\nThe representation model \\\\(h_\\theta\\\\) is only applied in the root node to project the real observation history \\\\(o^i_{\\le t}\\\\) until time step \\\\(t\\\\) of agent \\\\(i\\\\) into an individual latent state \\\\(s^i_t = h_\\theta(o^i_{\\le t})\\\\). Thus, all models (dynamic model, policy model, etc.) in MCTS are learned and executed in the latent space. The input of \\\\(h_\\theta\\\\) is the local observation history and the output is the state in the latent space. \\\\(h_\\theta\\\\) is implemented as Multi-Layer Perception (MLP) networks, where each linear layer in MLP is followed by a Rectified Linear Unit (ReLU) activation and a Layer Normalisation (LN) layer. Specifically, we use the hidden state size of 128 and the hidden layers for the MLP applied in \\\\(h_\\theta\\\\) is [128, 128].\n\n**Q3**\n\n\\\\(r_k\\\\) in the Algorithm 1 refers to the observed reward \\\\(X_s\\\\) after taking action \\\\(a\\\\) at the \\\\(k\\\\)-th node in the search path. We use the notation \\\\(r_k\\\\) here since \\\\(s\\\\) in Algorithm 1 \\\\(s\\\\) refers to the state while in Section 3.1 \\\\(s\\\\) of \\\\(X_s\\\\) means a time step. We will check the usage precision of notations through the paper to improve the readability. \n\n\n[1] Rashid, Tabish, et al. \"Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning.\" Advances in neural information processing systems 33 (2020): 10199-10210.\n\n[2] Vaswani, Ashish, et al. \"Attention is all you need.\" Advances in neural information processing systems 30 (2017).\n\n[3] Ye, Weirui, et al. \"Mastering atari games with limited data.\" Advances in neural information processing systems 34 (2021): 25476-25488.\n\n[4] Liu, Qihan, et al. \"Efficient multi-agent reinforcement learning by planning.\" arXiv preprint arXiv:2405.11778 (2024)."}]

Author rebuttal:

Meta-review: This paper is right at the threshold between acceptance and rejection. It adapts a known method from MARL for an extension of MCTS to MARL. Reviewers found it well written, but too many details have been moved into the appendix for full comprehension. However, the paper's highlight are the UCB regret bounds for the linearized representation of the joint action space that make MCTS planning efficient. Their approach comes at the price of all agent needing access to all others' observations, which is much more restrictive than model-free approaches to solve Dec-POMDP like QMIX. Nonetheless, the resulting AlphaZero style algorithm performs very well on the SMAC benchmark against other model-based baselines with the same assumptions. On the more conceptual MatGame evaluations other MARL planning algorithms (in particular MAZero) do not perform significantly worse, though, but only the proposed method is printed in bold, which misleads reader. This needs to be rectified.

Reviewers are mostly in favor of acceptance, as the paper presents a theoretically justified method that allows MARL planning with MCTS. On the other hand, the current version is hard to follow without reading the appendix, which should never be a requirement. The authors promise to fix this, but this is easy to promise and hard to do.

I do follow the reviewers and recommend acceptance as well, but this remains a threshold decision. I would therefore not mind if this paper gets bumped down due to limited conference resources.
Decision: Accept (poster)