acceptodds
Under review as a conference paper at ICLR 2027

A Semi-Decentralized Approach to Scalable Multiagent Control

Abstract

Scalable multiagent control under stochastic communication remains an open challenge. Existing planning methods such as RS-SDA scale poorly, sampling-based approaches such as Dec-MCTS assume fixed-period communication, and MARL methods typically impose either strict execution-time decentralization (QMIX, MAPPO) or full centralization (MAZero), respectively limiting coordination opportunities or ignoring the stochastic communication constraints that arise at decision time. We consider the Semi-Decentralized POMDP (SDecPOMDP), which unifies the Dec-POMDP and MPOMDP through a distribution over communication-sojourn times. We introduce SDecMCTS, a multiagent MCTS algorithm that achieves solution quality comparable to RS-SDA while requiring less computation across benchmarks. Building on the SDecPOMDP's semi-Markov communication dynamics, SDecMCTS uses an options framework in which decentralized solvers execute between communication events, enabling planning and execution that faithfully reflects semi-decentralization. We extend SDecMCTS to Semi-Decentralized Zero (SDecZero), a scalable AlphaZero-style algorithm that learns semi-decentralized value estimates used by decentralized solvers. SDecZero additionally learns the stochastic communication dynamics through a dedicated network communication head. SDecZero substantially outperforms model-based and model-free methods across large multi-drone search scenarios constructed from real cave systems associated with the DARPA Subterranean Challenge.

Primary area:
reinforcement learning
Keywords:
multiagent planning, communication, semi-decentralization, model-based, learning, search

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_XPLGOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies multiagent planning in which communication capability changes as agents move; the problem is modeled using the existing SDec-POMDP framework. The authors first propose SDecMCTS, an online MCTS over the shared belief: while agents remain in contact, it searches over joint actions; each time contact is lost, the decentralized window is treated as an option and handed to a Dec-POMDP solver, and search then continues from the belief at which communication resumes. Building on this, the authors propose the AlphaZero-style SDecZero, which guides search with a policy head and a value head and additionally trains a communication head. The experiments show that SDecMCTS roughly matches the quality of the offline planner approximate RS-SDA* on 17 planning benchmarks and takes less time on the 15-node DARPA caves. On three 25-node real-world caves, SDecZero is far more sample-efficient than MAPPO, QMIX, MAZero, and other methods.

Critical strengths

The problem is real and understudied, and the idea of folding out-of-contact windows into the same search process as options is simple and highly reusable.

Critical weaknesses
  1. SDecZero itself uses the true model and performs 1,000 simulations per decision, and its return already reaches about 40–50 before training begins, yet the evaluation-time head ablation lacks the configuration that uses no learned head at all. Therefore, how much improvement the networks actually bring, and the significant scaling the authors claim, are not verified.

  2. SDecMCTS is only run on problems with at most 15 nodes, and SDecZero is only run on the 25-node caves; the two are never compared on the same problem.

Questions for authors
  1. Can results with more than two agents be reported?

  2. Can pseudocode be provided, and why is assigning zero value at window truncation conservative?

  3. Can the learned communication head be evaluated in an environment where communication is actually stochastic?

5 comments
AuthorsOpenReview ↗

Response to reviewer XPLG: matched SDecMCTS on 25-node labyrinths, three agent experiments, stochastic communication learning

We appreciate reviewer XPLG for their review of our paper and for highlighting the underlying problem’s importance and utility of the options-like approach. We address the identified weaknesses and questions:

Weaknesses

1. Evaluation-time head ablation. Agreed. We run the suggested ablation without learned heads, on the 25-node benchmarks, below in response to point two. These results have been added to Figure 6.

2. SDecMCTS and SDecZero direct comparison. We now do so; we run SDecMCTS on all 25-node benchmarks with the same hyperparameter configuration as SDecZero for matched comparison across components and include online computation times.

PriorContinuation valuesTunnels-25[s/ep]Chamber-25[s/ep]Grapevine-25[s/ep]
LearnedLearned76.13 ± 0.04 (21, 21, 21)13.0 ± 0.566.31 ± 1.43 (19, 18, 18)10.0 ± 1.260.11 ± 1.49 (17, 17, 16)31.6 ± 5.7
HeuristicLearned73.19 ± 1.49 (20, 20, 21)20.1 ± 1.855.99 ± 4.92 (18, 14, 16)20.9 ± 3.645.85 ± 7.05 (15, 10, 15)37.0 ± 17.5
LearnedOptimistic57.01 ± 1.59 (17, 16, 17)58.9 ± 2.956.15 ± 2.76 (15, 17, 16)38.3 ± 4.431.56 ± 6.54 (9, 8, 13)68.1 ± 0.7
HeuristicOptimistic58.64 ± 0.01 (17, 17, 17)76.4 ± 10.842.61 ± 2.16 (14, 13, 12)57.6 ± 19.048.35 ± 2.47 (14, 13, 15)59.4 ± 17.6

** updated to include learned component breakdown (learned priors vs values)

We further discussed why SDecMCTS struggles with these larger benchmarks, in our response to reviewer rf7p.

Questions

  1. We now report n = 3 performance and computation time for ExtCross9 h7, tunnel_3d_010 h6/8/10, and tunnel_3d_015 h8. We assume communication is transitive along the communication graph and a τany\tau_{any} termination scheme from the MSMDP literature. We also add the o-SARSA$^{seq}$ baseline in response to reviewer 2AHM.
n = 3 benchmarks (horizon)PF-MAA* (dec.) [s]o-SARSA$^{seq}$ (dec.) [s]App. RS-SDA* (semi-dec.) [s]SDecMCTS (semi-dec.) [s/ep]Centralized upper bound
ExtCross9 (7)84.50 [68]84.50 ± 0.00 [111]98.00 [371]97.83 ± 0.08 [24.5]98.00
DARPA 3D Tunnels-10 (6)74.33 [21]74.33 ± 0.00 [74]86.22 [91]85.51 ± 0.06 [23.6]86.33
DARPA 3D Tunnels-10 (8)85.11 [30]85.11 ± 0.00 [61]97.22 [95]97.00 ± 0.00 [27.8]97.33
DARPA 3D Tunnels-10 (10)96.11 [36]96.11 ± 0.00 [146]97.22 [103]96.93 ± 0.03 [53.9]97.33
DARPA 3D Tunnels-15 (8)73.86 [215]73.83 ± 0.02 [307]81.36 [560]88.26 ± 0.17 [135.7]88.93

SDecMCTS remains tractable - and faster than any other considered baseline - for n = 3 in problems with large state and observation spaces, while also returning a near optimal semi-decentralized result.

Other assumptions about communication dynamics and agent replanning naturally lead to different results, but we leave extensive discussion of these assumptions to future work.

  1. Agreed. We now include algorithm pseudocode for SDeMCTS and SDecZero in the technical appendix. The original intent of zero value decentralized window truncation was to advantage policies that result in returned connectivity when beyond the depth cap. However, we later deemed it more principled and performant to assign it the centralized upper bound value in SDecMCTS and the learned semi-decentralized value in SDecZero. The paper text has been modified accordingly.

  2. It is a good suggestion, and doing so captures the representative power of the underlying SDec-POMDP. We evaluate and now depict in the updated Figure 7 a modified version of S&R ExtCross9 in which connectivity degrades probabilistically as range between agents increases. No changes are required to the existing learned communication head, which is a Bernoulli model trained by observed contact outcomes. The learned communication head easily captures probabilistic communication in this environment, and the solver quickly converges on the optimal policy.

Thank you for the detailed response and the additional experiments. The most useful part for me is the table that runs SDecMCTS and SDecZero on the same three 25-node maps with online times; the n = 3 results also help. The PDF I can download from the forum is still identical to the submitted version, so I go by the text of the response. Four points remain open for me.

  1. W1 and W2 (what the networks add). Your table gives the number I asked for: search without learned heads returns 58.45 / 44.12 / 48.35, against 73.7 / 62.0 / 61.8 with them. Two things should be stated with the table. To me you write "the same hyperparameter configuration as SDecZero", while to rf7P the same table is "across hyperparameter configurations". Is it one configuration or several? And is ± over the 3 seeds a standard error or a standard deviation? On Chamber-25 (44.12 ± 2.85 against 62.0 ± 7.5), how firm the gap is depends on which. Your table also shows SDecMCTS completing 25-node episodes in 56.6 to 97.3 s, so I would narrow "enable significant scaling" in the contributions list to the gain in return and the lower online time.

  2. Q1 (more than two agents). The n = 3 table answers this for SDecMCTS on graphs of up to 15 nodes. The claim "faster than any other considered baseline" holds on three of the five rows. PF-MAA* is faster on Tunnels-10 at horizon 6 (21 against 23.6) and horizon 10 (36 against 53.9). The response reports no n = 3 result for SDecZero. Unless the revision adds one, the paper should say that SDecZero is evaluated for two agents only.

  3. Q2 (value at truncation). Please state which rule produced the SDecMCTS numbers in Table 1 of the submission and in the two tables in your reply to me, and reconcile two descriptions: to me you write that the probability mass reaching the depth cap receives the centralized upper bound, and to 2AHM that a capped window "chains into another optimistically priced by" V_dec.

  4. Q3 (stochastic communication). The modified environment is the right test, but the response states no numbers. Table 4 of the submission lists the head as used in planning as "communication predicted where the head exceeds 0.5". A thresholded prediction is deterministic, so if the same threshold is used here, I do not see how the head can be used unchanged when contact is random. Please state whether search samples contact from the predicted probability, and give the error of the predicted contact probability against the true one and the return gap to planning with the true F.

Thank you again. I hope these points are useful for the revision.

AuthorsOpenReview ↗

Response to XPLG's remaining questions (hyperparameter clarification, scoping contributions, clarifying estimator, updated manuscript)

We appreciate the follow-up questions. The feedback has substantially helped improve the paper!

You will find that the manuscript is now updated on Open Review. This remains an interim product, as we continue to facilitate additional experiments and ablations in support of reviewer 2AHM. But this should at least enable review of the updated Figure 6, Figure 7, and pseudocode in the technical appendix.

1. One configuration. The SDecMCTS hyperparameter configuration in Figure 6 matches that of SDecZero (simulation count, window depth, visits before decentralized solve, and decentralized solver recursion) for a fair comparison, inasmuch as these two can be compared directly. Tables 5, 6, and 7 outline these hyperparameters clearly. The "across hyperparameter configurations" in response to reviewer rf7P is confusing and has been dropped. The match is clean. Standard error. All tables and figures report SE other than the in-simulation drone experiments in Table 3. We agree and modify the contribution claim accordingly.

2. Concur. We clarify, however, that the contribution is to be scoped against the semi-decentralized baseline. SDecMCTS is faster than RS-SDA* on all semi-decentralized rows and substantially outperforms it on one. For additional context: PF-MAA* and o-SARSA$^{seq}$ are solving the fully decentralized version of the problem to provide a sort of lower bound (note the dec. in the column header). RS-SDA* and SDecMCTS are solving the semi-decentralized version of the problem (note the semi-dec. in the column header). That is correct; we have thus far run the n = 3 experiments for only SDecMCTS. although there is no technical or structural blocker to doing so for SDecZero as well.

3. The two descriptions are the same rule; there is no discrepancy. VdecV^{dec} names the estimator for a belief that is still out of contact. It does not mean a fully decentralized (pessimistic) value. In the window solve (Algorithm 1, line 41), probability mass that reaches the depth cap is priced by VdecV^{dec} at its belief, and search then continues in a further window (line 39). SDecMCTS fills VdecV^{dec} there with the centralized upper bound, which is optimistic, and SDecZero with a learned semi-decentralized value.

Which rule produced which numbers: Table 1 of the original submission priced that mass at zero, as Section 4 of that version stated. Table 1 of the revised manuscript and both tables in our reply, use the centralized bound: exact on the tabular, Search & Return and 15-node rows, VMDPV_{MDP} on Search & Rescue, and a 3-step lookahead on the 25-node maps (reference Table 5).

4. Please reference the updated Figure 7 now in the uploaded manuscript. Yes, search samples contact from predicted probability in the stochastic communication experiment. The head remains a Bernoulli model and outputs a probability. Its architecture and inputs are unchanged, and it is fit by the plain likelihood to the contact outcomes observed in execution. The 0.5 threshold in the settings table is how planning reads the head on the benchmarks where contact is deterministic, so that FF is 0 or 1. Where contact is random, the planning model takes FF to be the predicted probability. Each simulation samples the contact outcome from it, beliefs are conditioned on that outcome, and the window solver weights communication by it. The reviewer's reasoning about thresholding is correct, and we measure it below.

Setting: ExtCross9 Search & Return (h=7h = 7), with contact probability 0.7hops0.7^{\text{hops}} on the 29 line-of-sight node pairs and 0 on the other 16; 12 rounds of 40 episodes, 1,000 simulations per decision.

Error of the predicted contact probability. Mean squared error against the true probability over all 45 node pairs: 0.317 before training, 0.016 after 160 episodes, 0.010 at the end (mean absolute error 0.05). By hop distance, predicted against true: 1.00 / 1.00, 0.61 / 0.70, 0.46 / 0.49, 0.34 / 0.34, 0.39 / 0.24, and below 0.001 against 0 on pairs out of line of sight.

Return, mean ± SE over 480 episodes.

Planning modelReturn
True FF80.6 ± 2.0
Learned FF, predicted probability83.0 ± 1.8
Learned FF, thresholded at 0.568.1 ± 2.3

The learned row includes the episodes played while the head was still being fit. Unsurprisingly, thresholding the same head loses 12.5 against the true FF.

Reviewer_2AHMOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper aims to approximately solve a two-agent semi-decentralised partially observable Markov decision process (SDec-POMDP) over short-to-medium finite horizons. The motivation is the control of two robots navigating a labyrinth where communication is occasionally interrupted and subsequently restored. The authors suggest breaking down the problem into subproblems, solving each subproblem and storing its solution as an option, and combining the options into a complete policy for each agent. The decomposition exploits the structure of the SDec-POMDP instances considered. The authors introduce two methods (SDecMCTS and SDecZero) to calculate these composite policies.

Critical strengths
  1. The paper addresses a genuinely important problem in machine learning, i.e., the synthesis of controllers for a group of agents controlling a dynamical system under asymmetric information.
  2. The paper leverages the underlying structure of a subclass of decentralised partially observable Markov decision processes.
  3. Two algorithms show improvements over the baselines used in the experiments.
Critical weaknesses
  1. The related work is incomplete. Several closely related papers are missing, including:

    [1] Goldman, C. V., and Zilberstein, S. (2008). “Communication-Based Decomposition Mechanisms for Decentralized MDPs.” Journal of Artificial Intelligence Research, 32, 169–202.

    [2] Zhang, K., Miehling, E., and Başar, T. (2019). “Online Planning for Decentralized Stochastic Control with Partial History Sharing.” Proceedings of the American Control Conference (ACC), 3544–3550.

    [3] Peralez, J., Delage, A., Castellini, J., Cunha, R. F., and Dibangoye, J. S. (2025). “Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach.” Proceedings of the AAAI Conference on Artificial Intelligence, 39(22), 23276–23285.

  2. The necessity of the SDec-POMDP model over the standard Dec-POMDP model is unclear. The fact that communication is occasionally interrupted and subsequently restored does not justify the shift from Dec-POMDPs to SDec-POMDPs. One can always reformulate an SDec-POMDP as a Dec-POMDP. Although the resulting Dec-POMDP may become very large, [3] demonstrates the ability to handle large Dec-POMDPs.

  3. The occupancy state in [3] provides a means of representing public and private information, together with truncated histories if needed. The same paper demonstrates scalability to larger numbers of agents, up to seven, without exploiting any specific structure. The decomposition of policies according to communication availability could be performed using [3].

  4. The authors do not precisely identify the operators used in their proposed algorithms, nor their properties and underlying assumptions. Summarising information at communication times could be naturally captured by occupancy states [3].

  5. The paper lacks theoretical guarantees regarding the gains from option generation, limited search depth, or approximate continuations. For example, what is the regret associated with composing a policy from precomputed options? There are also several heuristics, e.g., setting continuation values to zero when communication is unavailable, whose impact on regret is not quantified.

  6. The advantage of the proposed algorithms is not demonstrated against state-of-the-art solvers, e.g., oSARSA-Seq [3]. The scalability of the algorithms with respect to the number of agents is also not demonstrated.

Questions for authors
  • How does the paper compare with [1, 2, 3]?
  • What regret bounds can be established for the operators used in the proposed algorithms?
8 comments
AuthorsOpenReview ↗

Response to reviewer 2AHM: added references, evaluated o-SARSA, three agent experiments, algorithm specification, augmented Dec-POMDP experiments

We thank reviewer 2AHM for their review. We address each item below:

1. References. We add [2] and [3] to the subsection on planning approaches and [1] to a new appendix subsection, and evaluate [3] below.

Zhang et al. [2], for which we found no code, use online tree search over prescriptions under partial history sharing. Their prescription space grows exponentially with the number of retained histories. Our methods instead exploit communication events to organize planning into short decentralized windows, solved online and composed through joint-belief continuations.

We evaluate and show that [3] is competitive with our decentralized baseline (PF-MAA*), and add o-SARSA$^{seq}$ [3] to Table 1. o-SARSA$^{seq}$ [3] however struggles with the large state and observation spaces caused by augmenting the Dec-POMDP with communication. We respectfully disagree with the reviewer's claim: “although the resulting Dec-POMDP may become very large, [3] demonstrates the ability to handle large Dec-POMDPs”. The benchmarks evaluated in [3] have at most 256 states and nine observations per agent. Augmented ExtCross9 has 49,753 reachable states with 5,549 observations per agent. Consider:

n = 2 benchmarks (h)o-SARSA$^{seq}$ [3] on the augmented Dec-POMDP (s)App. RS-SDA* (s)SDecMCTS (s/ep)
LopsidedY10 (6)85.67 (6)85.67 (<1)85.53 (1)
ExtCross9 (6)84.38 (185)84.38 (1)84.38 (<1)
Ladder10 (6)85.52 (547)95.89 (<1)96.33 (1)

Peralez et al. themselves note that growing state and observation spaces limit scalability.

Goldman and Zilberstein [1] develop option-based decomposition algorithms for Dec-MDPs with costly communication that reveals the global state. The SDec-POMDP and relationship to earlier communication-based decompositions were introduced in (Al-Husseini et al. 2026). Our methods plan online over shared beliefs under stochastic communication availability, where communication need not reveal the full state. We add a subsection on decentralized decision processes to the appendix.

2. Decision process mapping. We recognize that any SDec-POMDP can be reformulated as a Dec-POMDP. This is established in the AAMAS paper that introduces the SDec-POMDP (Al-Husseini et al. 2026), and is similarly true of the Dec-POMDP-Com (Goldman & Zilberstein 2004), Dec-SMDP-Com (Goldman & Zilberstein 2008) [1], Dec-POMDPs with k-step delayed communication (Oliehoek et al. 2008), and the partial-history-sharing model underlying Zhang et al. [2]. These models are nonetheless introduced because making communication structure explicit yields sufficient statistics and solution methods that are challenging or unavailable in a communication augmented Dec-POMDP. We suggest the reviewer's cited Dec-SMDP-COM paper (authors map to a MMDP) and SDec-POMDP (authors map to a Dec-POMDP) for additional context. We reiterate that the SDec-POMDP is borrowed, not introduced.

3. Occupancy states. We address this in response to point one. The many-agent scalability argument made for [3] is also narrower than stated. Results are at h = 10, on small planning problems, and compared against A2C and IQL. We evaluate o-SARSA$^{seq}$ [3] on five n = 3 decentralized labyrinth benchmarks:

n = 3 benchmarks (horizon)PF-MAA* (dec.) [s]o-SARSA$^{seq}$ [3] (dec.) [s]App. RS-SDA* (semi-dec.) [s]SDecMCTS (semi-dec.) [s/ep]Centralized upper bound
ExtCross9 (7)84.50 [68]84.50 ± 0.00 [111]98.00 [371]97.83 ± 0.08 [24.5]98.00
DARPA 3D Tunnels-10 (6)74.33 [21]74.33 ± 0.00 [74]86.22 [91]85.51 ± 0.06 [23.6]86.33
DARPA 3D Tunnels-10 (8)85.11 [30]85.11 ± 0.00 [61]97.22 [95]97.00 ± 0.00 [27.8]97.33
DARPA 3D Tunnels-10 (10)96.11 [36]96.11 ± 0.00 [146]97.22 [103]96.93 ± 0.03 [53.9]97.33
DARPA 3D Tunnels-15 (8)73.86 [215]73.83 ± 0.02 [307]81.36 [560]88.26 ± 0.17 [135.7]88.93

4. Algorithm Specification. We agree the algorithms could be better specified, which we do by adding pseudocode for both SDecMCTS and SDecZero, in the technical appendix.

5. Regret. Options are solved online, then fixed. We add Prop. 1 to the appendix: given solver error δ\delta and continuation error ϵ\epsilon, a window policy loses at most δ\delta + 2 ϵ\epsilon (δ\delta + ϵ\epsilon if continuation values are optimistic), so error is not amplified. We do not bound the outer MCTS or compounding across windows. As in our response to reviewer XPLG, decentralized continuations are no longer zeroed: a capped window chains into another optimistically priced by VdecV^{dec}. Empirically, SDecMCTS is within 1 point of the exact centralized optimum on 34 of 35 rows (Tables 1-2).

6. SOTA Baselines. We disagree that we have not demonstrated performance against SOTA solvers, now further supported by our experiments against o-SARSA$^{seq}$ [3].

Thank you for the additional experiments. My main concern is whether the algorithms solve the same problem. The two-agent table uses a communication-augmented Dec-POMDP, whereas the three-agent table labels oSARSA-Seq as “decentralized” and your methods as “semi-decentralized”. Does the three-agent comparison preserve the same communication opportunities and information available to each agent? If not, it cannot isolate differences between the solvers.

Please describe the equivalent Dec-POMDP construction and report the hyperparameters used for each algorithm, particularly the history-memory length, any truncation, and whether lossless probabilistic equivalence (LPE) was used.

The state and observation counts alone do not explain the difficulty. A central bottleneck in Dec-POMDP planning is the exponential growth of histories with the horizon. LPE can reduce this growth in structured problems, and communication can create opportunities to merge equivalent histories. It therefore matters whether the reduction and solver exploit these equivalences.

The question is whether solving the equivalent Dec-POMDP remains less efficient after accounting for this structure. The current results do not establish this, because the three-agent comparison appears to use different information structures and the configuration of the augmented Dec-POMDP experiments is insufficiently specified.

AuthorsOpenReview ↗

Ablation of o-SARSA across LPE and memory across benchmarks

Immediate answers:

(1) No: the three-agent table does not give o-SARSA$^{seq}$ communication. It was added for the reviewer request on n > 2 experiments and reports the no-communication Dec-POMDP as a lower bound. The same-information comparison is the two-agent table below. Within the three-agent table, the like-for-like pairs are o-SARSA$^{seq}$ against PF-MAA* (decentralized) and RS-SDA* against SDecMCTS (semi-decentralized). The communication-augmented Dec-POMDP at n = 3 is beyond the released implementation of [3] even with our leanest construction: on three-agent ExtCross9 (h = 7) it has 5,074 observations per agent, about 1.3×10111.3 \times 10^{11} joint observations.

(2) Yes: on the equivalent Dec-POMDP with memory 1 and LPE on, o-SARSA$^{seq}$ matches SDecMCTS on all six labyrinth instances (within 0.5) and equals or slightly exceeds approximate RS-SDA* (by at most 1.0), but takes 102-473 s on the four larger ones, against 2 s or less for approximate RS-SDA* (the like-for-like offline solver) and 1 s or less per episode for SDecMCTS. We therefore maintain that SDecMCTS and RS-SDA* are more efficient than o-SARSA$^{seq}$ on the Dec-POMDP equivalent to the SDec-POMDP.

The table below ablates o-SARSA$^{seq}$ across LPE and memory (history truncation) on six small labyrinth instances. Its best configuration is memory 1 with LPE on.

MethodModelLopsidedY10 (h = 6)ExtCross9 (h = 6)Ladder10 (h = 6)Mesh10 (h = 6)Maze12 (h = 7)Ladder10 (h = 7)
Exact RS-SDA* (upper bound)Centralized85.67 [<1]84.38 [1]96.33 [<1]96.78 [7]96.00 [1]96.78 [<1]
App. RS-SDA*SDec-POMDP85.67 [<1]84.38 [1]95.89 [<1]96.67 [2]94.82 [<1]96.44 [<1]
SDecMCTS (online)SDec-POMDP85.53 ± 0.13 [<1]84.38 ± 0.00 [<1]96.33 ± 0.00 [<1]96.22 ± 0.00 [1]95.82 ± 0.00 [1]96.56 ± 0.00 [<1]
o-SARSA$^{seq}$, memory 1, LPE offAugmented Dec-POMDP85.67 ± 0.00 [<1]84.38 ± 0.00 [8]92.74 ± 3.59 [114]89.22 ± 3.72 [417]95.82 ± 0.00 [557]96.56 ± 0.00 [114]
o-SARSA$^{seq}$, memory 1, LPE onAugmented Dec-POMDP85.67 ± 0.00 [<1]84.38 ± 0.00 [9]96.33 ± 0.00 [215]96.67 ± 0.00 [473]95.79 ± 0.03 [463]96.56 ± 0.00 [102]
o-SARSA$^{seq}$, memory 2, LPE offAugmented Dec-POMDP85.67 ± 0.00 [6]84.38 ± 0.00 [393]85.48 ± 0.04 [108]74.30 ± 0.04 [475]77.45 ± 0.00 [283]96.48 ± 0.07 [148]
o-SARSA$^{seq}$, memory 2, LPE onAugmented Dec-POMDP85.67 ± 0.00 [3]84.38 ± 0.00 [137]89.04 ± 3.65 [497]77.93 ± 3.59 [436]86.52 ± 9.12 [717]92.78 ± 3.78 [124]
o-SARSA$^{seq}$, memory 3, LPE offAugmented Dec-POMDP85.67 ± 0.00 [7]75.83 ± 4.27 [378]77.96 ± 3.63 [557]–––
o-SARSA$^{seq}$, memory 3, LPE onAugmented Dec-POMDP85.67 ± 0.00 [4]75.83 ± 4.27 [204]81.70 ± 3.69 [315]–––
o-SARSA$^{seq}$, memory 4, LPE offAugmented Dec-POMDP85.67 ± 0.00 [85]75.83 ± 4.27 [627]77.74 ± 3.52 [204]–––
o-SARSA$^{seq}$, memory 4, LPE onAugmented Dec-POMDP85.67 ± 0.00 [203]71.62 ± 7.33 [426]77.81 ± 3.48 [209]–––
o-SARSA$^{seq}$, memory 5, LPE offAugmented Dec-POMDP85.67 ± 0.00 [68]67.25 ± 4.12 [138]not representable–––
o-SARSA$^{seq}$, memory 5, LPE onAugmented Dec-POMDP85.67 ± 0.00 [109]67.25 ± 4.12 [141]not representable–––

Cells are values [solve time s]. RS-SDA* rows are offline solves. SDecMCTS is the mean ± SE of online planning with its per-episode time. o-SARSA$^{seq}$ is the best value found by 1,200 s, mean ± SE over three seeds, with the mean time at which that value was first reached. Because o-SARSA$^{seq}$ is an anytime algorithm, the appendix now plots its value over the 1,200 s for each labyrinth and configuration. These results supersede our earlier augmented runs, which used a larger construction: there o-SARSA$^{seq}$ reached 85.52 on Ladder10 (h = 6), and it now reaches 96.33. The leaner, equivalent construction is described in our next comment.

Search & Return labyrinth benchmarks have deterministic observations, indicating that memory = 1 is indeed sufficient. LPE matters at memory 1 on the two largest h = 6 models (Ladder10 92.74 to 96.33, Mesh10 89.22 to 96.67) and is neutral on the other four; at longer memories its effect is mixed. We do increase o-SARSA$^{seq}$ memory in problems with stochastic observations, such as SDec-Tiger, when evaluated in Table 1. The released code for [3] exposes history-memory length and truncation as a single parameter, reported here as memory. The hyperparameter configuration for each method across benchmarks is in the appendix of our updated manuscript.

Reviewer_rf7POpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes SDecMCTS, a Monte Carlo tree search method for multiagent planning under stochastic communication. It combines centralized planning when agents can communicate with decentralized planning during communication gaps, treating these periods as options within the search tree. The authors further extend this approach to SDecZero, an AlphaZero-style method that uses learned policy and value networks to guide planning, along with a separate model for learning communication dynamics.

Critical strengths
  1. A principled approach to planning under stochastic communication. SDecMCTS handles communication loss by solving depth-capped Dec-POMDP windows as options within MCTS. This allows the planner to account for how joint actions may affect future communication opportunities, rather than assuming fixed communication intervals or continuous coordination. I see this as a meaningful contribution, particularly for multi-robot settings where communication depends on the agents' locations and actions.

  2. Strong planning results with reduced computation. SDecMCTS achieves returns close to approximate RS-SDA* while requiring substantially less planning time on the larger deterministic cave-search benchmarks. For the 15-node DARPA environments, planning takes 8–88 seconds compared with 25–275 seconds for RS-SDA*, and it also consistently outperforms periodic Dec-MCTS in solution quality. These results provide convincing evidence that the proposed search approach can scale to larger environments without sacrificing much solution quality.

Critical weaknesses
  1. Limited evaluation of scalability with more agents. Scalability is a key motivation of the paper, but the reported experiments appear to involve only two agents. While the results show improvements on larger environments, it is difficult to judge how the method would perform with larger teams. Both the RS-MAA* solver used during communication gaps and the joint-action search could become expensive as the number of agents increases. Experiments with more agents would provide stronger support for the scalability claim.

  2. The benefit of learning in SDecZero is not fully established. SDecZero shows promising results, but it uses 1,000 search simulations per decision, compared with 200 for SDec-MAZero and 10 for MAZero. The paper also lacks a direct comparison with SDecMCTS without learning on the 25-node environments, making it difficult to separate the gains from learning and search. The ablations are limited as well, with the policy-only variant tested on one map and only one seed used for two maps. These issues make it harder to assess how much the learned components contribute to the reported improvements.

Questions for authors
  1. In Table 1, SDecMCTS exceeds the exact centralized upper bound on SDec-Tiger at every horizon (e.g., 130.66 ± 3.14 vs. 125.19 at h = 20). Could the authors clarify what ± represents, whether both methods use the same evaluation protocol, and why this difference persists across all four horizons if it is due to finite-sample variability?

  2. What explains the lower performance of SDecMCTS compared with approximate RS-SDA* on the noisy Search & Rescue benchmarks, particularly ExtCross9 (69.0 vs. 80.1) and Mesh10 (79.1 vs. 88.1)?

  3. How does SDecZero compare with SDecMCTS without learned components on the 25-node environments? Would the improvements over the learning-based baselines remain under comparable search budgets?

  4. Can the authors provide evidence of how SDecMCTS scales with the number of agents, even with three agents on a single benchmark? Planning time and solution quality would both be useful to see.

3 comments
AuthorsOpenReview ↗

Response to reviewer r7fp: three agent experiments, matched learned search, additional tiger episodes

We are grateful to reviewer rf7p for their consideration of our paper and for highlighting the principled approach and performance of our algorithms. We address the points raised:

Weaknesses

1. Limited evaluation of scalability with more agents. Agreed. We now demonstrate SDecMCTS performance in three agent settings for five different labyrinth instances in the main paper. Results with assumptions below.

n> 2 assumptions: we assume communication is transitive along the communication graph; if agent 1 is connected to agent 2 which is connected to agent 3 – then agents 1 and 3 are in communication. We take inspiration from the multiagent semi-Markov decision process (MSMDP) literature and adopt the "any" termination scheme (Rohanimanesh & Mahadevan, 2003), in which agents who regain contact (as opposed to control) share their histories and replan jointly from their updated initial belief. We find that n = 3 SDecMCTS remains easily tractable across labyrinth problems with near optimal performance. We also add o-SARSA$^{seq}$ on request of reviewer 2AHM. We bold our algorithm's results.

n = 3 benchmarks (horizon)PF-MAA* (dec.) [s]o-SARSA$^{seq}$ (dec.) [s]App. RS-SDA* (semi-dec.) [s]SDecMCTS (semi-dec.) [s/episode]Centralized upper bound
ExtCross9 (7)84.50 [68]84.50 ± 0.00 [111]98.00 [371]97.83 ± 0.08 [24.5]98.00
DARPA 3D Tunnels-10 (6)74.33 [21]74.33 ± 0.00 [74]86.22 [91]85.51 ± 0.06 [23.6]86.33
DARPA 3D Tunnels-10 (8)85.11 [30]85.11 ± 0.00 [61]97.22 [95]97.00 ± 0.00 [27.8]97.33
DARPA 3D Tunnels-10 (10)96.11 [36]96.11 ± 0.00 [146]97.22 [103]96.93 ± 0.03 [53.9]97.33
DARPA 3D Tunnels-15 (8)73.86 [215]73.83 ± 0.02 [307]81.36 [560]88.26 ± 0.17 [135.7]88.93

2. The benefit of learning in SDecZero is not fully established. Agreed and addressed. We now match both training and online search simulations per decision for SDecZero and SDec-MAZero, and online search per decision for MAZero. We now report three independent training seeds for all learned experiments across the 25-node maps, reflected in the updated Figure 6. Appendix ablations are expanded to three seeds and all maps. We also include and report SDecMCTS performance on 25-node maps:

n = 2 benchmarks (horizon)SDecMCTS return (3 seeds)SDecMCTS s/epSDecZero return (3 seeds)SDecZero s/ep
DARPA 3D Tunnels-25 (17)58.45 ± 0.1088.073.7 ± 2.611.2
DARPA 3D Chamber-25 (15)44.12 ± 2.8597.362.0 ± 7.510.3
DARPA 3D Grapevine-25 (13)48.35 ± 2.4756.661.8 ± 1.422.9

Questions

  1. Correct – finite sample variability. ±\pm is SE over k episodes. We increase seeds/episodes from 100 to 10,000 on SDecTiger for both App. RS-SDA* and SDec-MCTS and the updated results resolve noted concerns. | h | App. RS-SDA* (k = 10,000) | SDecMCTS (k = 100) | SDecMCTS (k = 10,000) | Exact optimum | |:---:|:---:|:---:|:---:|:---:| | 10 | 60.64 ±\pm 0.27 | 62.28 ±\pm 2.34 | 60.75 ±\pm 0.26 | 60.51 | | 12 | 73.79 ±\pm 0.29 | 76.46 ±\pm 2.64 | 73.46 ±\pm 0.29 | 73.39 | | 15 | 92.00 ±\pm 0.34 | 95.94 ±\pm 2.72 | 92.52 ±\pm 0.33 | 92.67 | | 20 | 125.27 ±\pm 0.38 | 130.66 ±\pm 3.14 | 125.83 ±\pm 0.38 | 125.19 |

  2. Traditionally, MCTS samples its way through a stochastic observation model, which results in noisy value estimates and poor policies. This shortfall inspires MCTS implementations with explicitly defined chance nodes, like POMCP/OW and StochasticMuZero. RS-SDA* is an offline solver that evaluates candidate policies by exact expectation over the stochastic observation model through the full remaining horizon. We intentionally introduce the Search & Assist environment to demonstrate our sampling-based method nonetheless results in good, if not quite comparable, performance against exact solvers. We add the integration of chance nodes branching over observations to our new appendix subsection on limitations and future work.

  3. SDecMCTS struggles with the scale of 25-node environments, especially in problems with large joint action spaces. The labyrinth benchmarks are deceptively challenging; they involve the sort of sparse, long-horizon rewards associated with problems like Montezuma’s Revenge (Ecoffet et al., 2021). The learned value and policy heads assist with propagating long-horizon knowledge in a way that is difficult for classical planning rollouts. As demonstrated, there was no change in the improvements over learning-based baselines under matched search.

  4. We now do so across five benchmarks, to include computation time, as reported in our response to weaknesses point one.

Thank you for the detailed responses and additional experiments. I have two follow-up questions:

  1. The three-agent results are encouraging. As the number of agents increases further, which part of SDecMCTS do youexpect to become the main computational bottleneck: joint-action search, solving decentralized windows, or handling communication-dependent replanning?
  2. I appreciate the clarification regarding the matched hyperparameter configuration and the reported standard errors. I also noticed that the revised SDecMCTS uses optimistic continuation estimates, while SDecZero uses learned continuation values. Do the expanded ablations help distinguish the benefit of the learned value head from the effect of using different continuation estimates? I think this would help clarify how much of the performance improvement comes from learning itself.
AuthorsOpenReview ↗

Response to reviewer rf7P's remaining questions

1. Good question. Taking a step back, SDecMCTS/SDecZero permits the use of any decentralized algorithm to solve its decentralized windows. The algorithm therefore inherently takes on the characteristics of its choice of decentralized solver. For example, o-SARSA$^{seq}$ excels at larger numbers of multiagent problems on smaller scale problems, while we find PF-MAA* to be better suited to two agent problems with larger observation and state spaces and longer horizons. We choose to coopt PF-MAA* for this paper, but it is just another hyperparameter choice on the part of the problem optimizer. With that lens in mind, for PF-MAA*, profiling traces at n = 3 indicate about a 50/50% split on time spent conducting joint-action search versus solving decentralized windows. Increasing the number of agents, using PF-MAA*, increases the relative percentage of time spent solving decentralized windows compared to joint-action search. We’d like to note that MAZero, which itself takes inspiration from Stochastic MuZero, provides a principled and performant approach to sampling joint actions from extremely large actions spaces to enable MCTS-style joint-actions search for upwards of tens of agents. That same approach will be coopted in our future work on SDecMuZero.

2. They do, and we think the results are telling. We run SDecMCTS on a 2x2 ablation (learned vs heuristic/optimistic priors and values) across the three 25-node graphs. You’ll recall that “classical” SDecMCTS performance is quite poor on these benchmarks, as reflected in the revised Figure 6. The semi-decentralized learned continuation values substantially improve SDecMCTS performance, as does the combination of learned priors and values.

PriorContinuation valuesTunnels-25[s/ep]Chamber-25[s/ep]Grapevine-25[s/ep]
LearnedLearned76.13 ± 0.04 (21, 21, 21)13.0 ± 0.566.31 ± 1.43 (19, 18, 18)10.0 ± 1.260.11 ± 1.49 (17, 17, 16)31.6 ± 5.7
HeuristicLearned73.19 ± 1.49 (20, 20, 21)20.1 ± 1.855.99 ± 4.92 (18, 14, 16)20.9 ± 3.645.85 ± 7.05 (15, 10, 15)37.0 ± 17.5
LearnedOptimistic57.01 ± 1.59 (17, 16, 17)58.9 ± 2.956.15 ± 2.76 (15, 17, 16)38.3 ± 4.431.56 ± 6.54 (9, 8, 13)68.1 ± 0.7
HeuristicOptimistic58.64 ± 0.01 (17, 17, 17)76.4 ± 10.842.61 ± 2.16 (14, 13, 12)57.6 ± 19.048.35 ± 2.47 (14, 13, 15)59.4 ± 17.6

** updated to include online computation times

SDecMCTS's search at 200 simulations per decision, with its policy priors and values either learned or its own. Mean return ± SE at 200 simulations per decision, on the 24-target slate. In parentheses, targets returned out of 24 for each of the three runs. Rows with a learned element use the three final SDecZero checkpoints. The last row uses three planner seeds. All four rows run the same search loop. The prior is either the SDecZero policy head or the softmax of the QMDP heuristic, and the continuation values are either the SDecZero value heads or SDecMCTS's rollout at a new node with the depth-3 centralized bound at a window's exits.

We update our ablation section in the technical appendix with these results.

Comments on the paper

1 comment

We thank all three reviewers for their time, for their constructive feedback, and for meaningfully engaging in sustained discussion throughout the rebuttal. The improved paper reflects substantial effort on the part of all reviewers. We also thank the AC for their time and consideration.

In summary, we introduce two scalable algorithms designed to provide approximate solutions for SDec-POMDPs. The SDec-POMDP is a general model that models stochastic communication conditioned on the state, joint actions, and joint observations. The SOTA for solving SDec-POMDPs is Approximate RS-SDA*, our primary baseline, which extends a long lineage of decentralized MAA* algorithms to the semi-decentralized case. We introduce SDecMCTS, an online planner that generates optimal trajectories in less time than RS-SDA*, especially with larger problems (across the number of agents, observations, and states). We then extend SDecMCTS to an AlphaZero-style approach, where we learn semi-decentralized values, policy priors, and the communication dynamic itself. SDecZero demonstrates excellent performance in the 25-node benchmarks, where SDecMCTS struggles, and does so with rapid online solution times.

The reviewers generally highlighted the underlying problem as understudied and important, the strength of the algorithm designs, and the demonstrated empirical performance. Primary shared concerns include scalability to n > 2 agents, robustness of the experimental design (additional seeds, ablations, etc.), and additional clarity on the algorithm design specification. We were also asked to compare, extensively, against a decentralized solver in o-SARSA$^{seq}$. We have sought to address concerns and requests as comprehensively as feasible within the rebuttal period.

All modifications and additions to the manuscript since rebuttal:

  • Three-agent experiments with SDecMCTS.
  • SDecMCTS and SDecZero pseudocode added to the appendix.
  • Decentralized window bound error proposition and proof added to the appendix.
  • Adding a paragraph on decentralized and partially decentralized decision processes to the literature review extension in the appendix.
  • Adding two new baselines to the planning paragraph in the literature review in the main manuscript.
  • Extensive experiments on eight benchmarks against the o-SARSA$^{seq}$ baseline, including developing and evaluating (1) a flattened version of the Dec-POMDP (what we refer to as the communication-augmented Dec-POMDP), (2) a recursive implementation specified by the reviewer, and (3) a flattened implementation specified by the reviewer. These experiments include several ablations of o-SARSA$^{seq}$ hyperparameters and reporting on performance, computation time, model construction times, and peak RAM. We make all code available in the supplementary files.
  • SDecMCTS evaluation at matched simulation count and other parameters, on the 25-node benchmarks.
  • Reducing finite sample variability on the SDecTiger problem by running and reporting 10,000 episodes for SDecMCTS.
  • Demonstrating that the learned communication head is performant and learns in benchmarks with stochastic communication, now depicted in Figure 7.
  • Aligning notation throughout, updated figures and tables.

Full results are in the individual responses, and all changes have been made in the updated manuscript. That manuscript, along with the revised supplementary files, have been uploaded. Thank you again.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.