acceptodds
Under review as a conference paper at ICLR 2027

SpecMAGIC: Specification-Guided Multi-Task Generalization in Multi-Agent Reinforcement Learning

Abstract

Multi-task generalization is an important yet underexplored problem in multi-agent reinforcement learning (MARL). Many real-world applications require multi-agent systems to generalize across complex, temporally extended tasks with diverse inter-agent coordination requirements. We introduce a specification language that combines temporal-logic task specifications with operators for expressing such requirements. We propose SpecMAGIC, a hierarchical framework that leverages the automaton structure of task specifications for subtask decomposition. A centralized high-level planner identifies and allocates compatible subtask sequences across agents, while decentralized low-level policies execute individual subtasks. This enables zero-shot generalization to new tasks by composing reusable subtask policies according to new specifications, without retraining. We establish soundness and probabilistic completeness of the high-level planner. Experiments on multi-agent navigation tasks show that SpecMAGIC substantially outperforms existing approaches on unseen task specifications and maintains strong performance as the number of agents increases.

Primary area:
reinforcement learning
Keywords:
multi-agent reinforcement learning, multi-task geenralization, temporal logic specifications

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_TwhdOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces SpecMAGIC, a novel framework for multi-task, multi-agent RL with LTL specifications. Each agent has its own set of atomic propositions and must complete an individual LTL task, with additional dependency and count requirements for inter-agent coordination. While these coordination primitives do not increase the expressive power of the specification language (they can be translated into standard LTL), they are convenient for specifying common coordination requirements. Instead of constructing the product automaton of the individual specifications, which may be expensive, the method employs a sampling based task allocation procedure that operates on subtask sequences computed from the individual tasks. Agents are trained to individually complete subtasks, and a centralized planner allocates subtasks to agents at test time and continually updates them, such that the overall specification is satisfied upon successful completion.

Critical strengths
  • The paper tackles an interesting problem. There has been much recent progress on multi-task RL with LTL specifications in the single-agent setting. Most multi-agent works on the other hand do not tackle generalization to multiple tasks.
  • Augmenting the specification language with explicit coordination primitives makes sense and enables specifying interesting behaviour, such as simultaneous completion of Boolean conditions with the Sync operator.
  • The proposed hierarchical planning procedure seems sound. It successfully delegates coordination requirements away from individual agents, enabling the global planner to account for much of the coordination. The paper demonstrates successful scaling of the proposed subtask-based planning compared to the product automaton.
  • The experiments show strong performance of the proposed framework on complex specifications and demonstrate successful scaling w.r.t. the number of agents.
Critical weaknesses

The primary weakness of the proposed approach is that it seems to only be able to handle explicitly specified coordination requirements, rather than training agents how to successfully coordinate based on implicit task and environment constraints. Agents are trained and rewarded based only on successful completion of their own randomly sampled reach-avoid goals, rather than on achieving an overall objective as a multi-agent system. This is feasible in the environment considered in the paper, but does not enable learning truly cooperative behaviour, such as opening a door for another agent (see e.g. the environment considered in ACC-MARL) or learning to share resources based on a global coordination task.

The above point is exacerbated by the fact that agents do not have knowledge of the tasks the other agents are trying to complete. Indeed, the whole system at training time boils down to training individual agents to complete their own tasks while avoiding colliding with other agents. The proposed framework does not appear to learn task-level cooperative behaviour; coordination is delegated entirely to the centralized planner, which continually assigns subtasks during executing. In contrast to ACC-MARL, which only requires centralised planning once at the beginning of a new task, SpecMAGIC must continuously update each individual agent's tasks throughout the episode with its centralized planner.

The explicit coordination supported by the approach furthermore is limited. In particular, the Sync operator is handled by keeping the same reach-avoid subgoal for the agent, until the synchronizaiton requirement is met. The approach does not explicitly model (or train agents to) achieve a proposition and then actively maintain it, which may be required in more complex environments. Similarly, imagine an environment in which a zone disappears shortly after touching it. Successful synchronization would require agents to wait until others are nearby before entering the zone, rather than independently reaching it as quickly as possible. It is unclear how the proposed framework would handle such scenarios.

While the planning procedure successfully handles coordination in the abstract subtask sequence space, it fails to account for the feasibility of subtask sequences in the environment. For example, suppose that green propositions can only be found in a room that locks upon entry. The planner is not aware of this and may assign the sequence green -> blue to any policy, which it will fail to complete due to the dynamics of the environment.

The experiments are limited to a single environment, which is relatively simple: there are no environment-intrinsic coordination requirements and only a single proposition can be true (per agent) at any given point. The paper would be much stronger if the authors could present further evidence of their method working, especially in environments that require complex coordination (such as the different button tasks from ACC-MARL). Furthermore, the large performance gap to ACC-MARL is difficult to interpret, since the baseline already substantially underperforms on simple tasks (see Appendix D). Since the two methods differ in their training objectives, representations, and observation processing it is unclear to what extent the results demonstrate improved multi-agent coordination, rather than differences in low-level goal-reaching performance or task generalization. A more controlled comparison or additional analysis would strengthen the empirical conclusions.

Finally, the exposition of the paper could be improved. Lines 153-159 are difficult to follow, since symbols are explained only after being introduced. The description of the sampling algorithm is quite technical (describing e.g. individual indices and data structures) rather than explaining intuitively how the algorithm works - an example here could be helpful. The same is true for how the system handles coordination requirements, an example in the main text would be very helpful here.

Related to the above, there are some technical inaccuracies / inconsistencies. The paper explicitly uses nondeterministic Büchi automata, but does not describe how nondeterminism is resolved during execution. In particular, if a proposition assignment enables multiple outgoing transitions from the current automaton state, how is the successor selected? This seems important because replanning depends on tracking the current automaton state. The paper furthermore describes the setting explicitly as partially observable, but does not address how this is handled - the policies all seem to be stationary rather than account for observation histories, and the approach furthermore requires access to the true underlying labels. The paper should clarify what information is available to the planner and how this assumption relates to the partially observable setting. Finally, some implicit assumptions such as the agents' atomic propositions being disjoint are never explicitly mentioned and left for the reader to infer.

Overall, I think the paper has some interesting ideas, but the current method is significantly limited in its generality.

Questions for authors
  • Can you provide evidence of the method working in environments with more complex coordination requirements?
  • Can the method be adapted to true decentralized execution, without the centralized planner monitoring and updating the tasks of individual agents?
25 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/5)

We thank the reviewer for their comments and feedback. We address each weakness and question below and the revised content in the manuscript is highlighted in red.

Critical Weaknesses

  1. The primary weakness of the proposed approach is that it seems to only be able to handle explicitly specified coordination requirements, rather than training agents how to successfully coordinate based on implicit task and environment constraints. Agents are trained and rewarded based only on successful completion of their own randomly sampled reach-avoid goals, rather than on achieving an overall objective as a multi-agent system. This is feasible in the environment considered in the paper, but does not enable learning truly cooperative behaviour, such as opening a door for another agent (see e.g. the environment considered in ACC-MARL) or learning to share resources based on a global coordination task.

Our environment does involve implicit coordination. Although each agent is trained to satisfy its own reach-avoid subtask, collisions with other agents are treated as specification violations at all times. As described in Section 4.4, agents still interact during training and learn implicit coordination, e.g., avoiding collisions when multiple agents need to reach the same region. Regarding an overall objective as a multi-agent system, such objectives are directly expressed through our coordination requirements. For example, Sync[I, α, |I|] requires all agents to reach the same region simultaneously, and the planner coordinates all agents toward this joint objective. Moreover, ACC-MARL cannot handle some of our coordination requirements: since it represents tasks as DFAs, it cannot express requirements that must hold throughout infinite executions, such as EachReq, ¬Sync, and ¬Async. Regarding the door example, our framework can also learn such cooperative behavior implicitly: in the environments of ACC-MARL, it achieves comparable or higher success rates than ACC-MARL without specifying any coordination requirements (please see our response to Weakness 4).

  1. The above point is exacerbated by the fact that agents do not have knowledge of the tasks the other agents are trying to complete. Indeed, the whole system at training time boils down to training individual agents to complete their own tasks while avoiding colliding with other agents. The proposed framework does not appear to learn task-level cooperative behaviour; coordination is delegated entirely to the centralized planner, which continually assigns subtasks during executing. In contrast to ACC-MARL, which only requires centralised planning once at the beginning of a new task, SpecMAGIC must continuously update each individual agent's tasks throughout the episode with its centralized planner.

We respectfully disagree that ACC-MARL only requires centralized planning once at the beginning of a new task. As stated in Section 4 of ACC-MARL, “each agent deploys the same decentralized policy …, which takes the agent’s ID, local observation, and the RAD Embeddings of all agents’ current progressed DFAs as input and outputs an action.” The DFAs of all agents are therefore progressed and updated throughout the episode as well. Under a similar setting, where each agent knows the tasks of all other agents and has access to the global state information, our framework can also be executed in a decentralized manner; please refer to our response to Question 2. Moreover, our planner is only invoked when the automaton state of some component changes, rather than at every step as discussed in Appendix C.

AuthorsOpenReview ↗

Rebuttal (Part 2/5)

  1. The explicit coordination supported by the approach furthermore is limited. In particular, the Sync operator is handled by keeping the same reach-avoid subgoal for the agent, until the synchronizaiton requirement is met. The approach does not explicitly model (or train agents to) achieve a proposition and then actively maintain it, which may be required in more complex environments. Similarly, imagine an environment in which a zone disappears shortly after touching it. Successful synchronization would require agents to wait until others are nearby before entering the zone, rather than independently reaching it as quickly as possible. It is unclear how the proposed framework would handle such scenarios.

We would like to clarify that all reach-avoid subtasks are obtained from the current automaton state of each component specification, rather than “the Sync operator is handled by keeping the same reach-avoid subgoal for the agent, until the synchronization requirement is met.” Whenever any automaton state changes, the subtask sequences are recomputed and the planner generates a new plan based on the current progress of all components (Appendix C). Regarding the scenario in which agents must wait until others are nearby, this requires each agent to know the current subtasks or task progress of all other agents. Such an approach is limited to a small and fixed number of agents by conditioning each policy on this information. In contrast, our low-level policies condition only on each agent’s own subtask, while the planner coordinates the agents, which allows our framework to scale to more agents without retraining (Section 5.2). When such information is available, as in the setting of ACC-MARL, our framework can also condition on the subtasks of all agents and learn such implicit coordination (please see our response to Weakness 4).

AuthorsOpenReview ↗

Rebuttal (Part 3/5)

  1. While the planning procedure successfully handles coordination in the abstract subtask sequence space, it fails to account for the feasibility of subtask sequences in the environment. For example, suppose that green propositions can only be found in a room that locks upon entry. The planner is not aware of this and may assign the sequence green -> blue to any policy, which it will fail to complete due to the dynamics of the environment.

To evaluate our method in environments that require such coordination, we have conducted additional experiments in the TokenEnv environments used in ACC-MARL (Buttons-2, Rooms-2, Buttons-4, and Rooms-4). We use the same DFA tasks as ACC-MARL, from which the reach-avoid subtask sequences are obtained. Following ACC-MARL, the input to the low-level policy of agent ii is (si,σ)(s_i, \boldsymbol{\sigma}), where sis_i is the global state from agent ii’s own point of view, as in ACC-MARL, and σ\boldsymbol{\sigma} contains the current reach-avoid subtasks of all agents ordered by their IDs, in place of the DFA embeddings of all agents used by ACC-MARL. For a fair comparison, we use the same state processing model, policy, and value networks, except that no DFA embeddings are needed, and the same 10M environment interaction steps. We also follow the evaluation protocol of ACC-MARL (Table 1 in ACC-MARL), with success rates averaged over 5 seeds with 1,000 episodes each.

EnvMethodReachReachAvoidRADReach (OOD)ReachAvoid (OOD)RAD (OOD)
Buttons-2ACC-MARL0.860 ± 0.0420.790 ± 0.0570.821 ± 0.0440.677 ± 0.0850.456 ± 0.0740.522 ± 0.046
Ours0.859 ± 0.0290.805 ± 0.0410.854 ± 0.0220.617 ± 0.0500.477 ± 0.0570.598 ± 0.033
Rooms-2ACC-MARL0.890 ± 0.0340.871 ± 0.0400.866 ± 0.0320.723 ± 0.0820.577 ± 0.0650.559 ± 0.039
Ours0.948 ± 0.0560.886 ± 0.0590.929 ± 0.0420.959 ± 0.0470.747 ± 0.0760.875 ± 0.050
Buttons-4ACC-MARL0.751 ± 0.0440.676 ± 0.0320.736 ± 0.0310.482 ± 0.0290.282 ± 0.0210.355 ± 0.005
Ours0.915 ± 0.0940.810 ± 0.0790.867 ± 0.0870.813 ± 0.1910.547 ± 0.1100.686 ± 0.145
Rooms-4ACC-MARL0.832 ± 0.0170.764 ± 0.0180.795 ± 0.0100.539 ± 0.0580.363 ± 0.0200.392 ± 0.012
Ours0.987 ± 0.0150.888 ± 0.0110.947 ± 0.0110.992 ± 0.0140.697 ± 0.0260.840 ± 0.025

Our framework achieves comparable or higher success rates across all environments and task classes, without defining additional propositions or specifying the coordination with Req, EachReq, Sync, or Async. This shows that our framework can also learn the implicit coordination required by these environments: since the layouts are fixed, the required coordination, e.g., which button to press for which door, is determined by the combination of subtasks assigned to the agents and can be learned by the low-level policies. Moreover, the improvement is more substantial for OOD tasks and for four agents, consistent with the trend in Table 1 of our paper, highlighting that our framework generalizes better to unseen specifications.

Reviewer_gMSLOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces SpecMAGIC, which employs formal specifications to describe the collaborative requirements between individual tasks and agents. The approach decomposes these specifications into reusable subtasks, which are then coordinated and assigned by a centralized sampling-based planner, followed by execution via decentralized reinforcement learning policies. This framework enables zero-shot generalization to previously unseen task specifications.

Critical strengths
  • The research problem is valuable. By combining task specification generalization with inter-agent collaboration constraints, the approach aligns well with the practical requirements of complex multi-agent systems.

  • The methodology is sound. The use of hierarchical planning and reusable subtask strategies establishes a clear division of labor, while formal analysis and comparative experiments with planners provide robust support for the proposed scheme.

Critical weaknesses
  • The baseline coverage remains insufficient. The primary baselines considered are unable to handle full collaborative constraints, and the comparisons focus predominantly on explicit compositional search, offering limited validation of the proposed method’s advantages over other efficient planning approaches.

  • The link between planning guarantees and actual execution requires further clarification. While the theoretical analysis centers on high-level planning, the discussion on how low-level policy errors, execution asynchrony, or subtask failures affect the satisfaction of overall specifications remains too generalized.

  • The evaluation scenarios are limited in scope. Experiments focus primarily on navigation environments, lacking validation against other multi-task generalization benchmarks in MARL; consequently, the applicability of the method across diverse task structures and collaborative settings remains unclear.

Questions for authors
  1. Could you compare your approach, which avoids full-scale composition, against planning methods that also utilize the same low-level policies? Additionally, could you clarify whether the observation conditions for the learning baselines are consistent with those of your proposed method?

  2. How are synchronization constraints enforced through local sub-task policies? Furthermore, how does the high-level controller coordinate and adjust the plan when agents arrive at different times or when an execution failure occurs?

  3. Could you provide additional results on other relevant multi-task generalization benchmarks for MARL, such as StarCraft(SMAC), to demonstrate the method's generalization capabilities across diverse environments and varying collaborative requirements?

8 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/2)

We thank the reviewer for their comments and feedback. We address each weakness and question below.

Critical Weaknesses

  1. The baseline coverage remains insufficient. The primary baselines considered are unable to handle full collaborative constraints, and the comparisons focus predominantly on explicit compositional search, offering limited validation of the proposed method’s advantages over other efficient planning approaches.

To our knowledge, ACC-MARL is the only existing method for generalization across temporal-logic specifications in MARL, and no existing baseline supports the coordination requirements considered in our work. To validate the planner itself, in Section 5.3 we compare it with a product-automaton (PA)-based planner using the same GenZ-LTL low-level policies. Our planner achieves similar success and violation rates with substantially less planning time, and the PA-based planner fails to find a plan within 10 minutes once four or more agents are involved. Could the reviewer clarify which other efficient planning approaches they have in mind?

  1. The link between planning guarantees and actual execution requires further clarification. While the theoretical analysis centers on high-level planning, the discussion on how low-level policy errors, execution asynchrony, or subtask failures affect the satisfaction of overall specifications remains too generalized.

The theoretical guarantees concern the high-level planner, and execution is handled by replanning (Appendix C). During execution, we track the automaton state of each component specification using the actual labels L(s). Whenever any automaton state changes, the reach-avoid subtask sequences are recomputed from the current automaton states and the planner generates a new plan from the current progress. Asynchronous execution is therefore handled naturally: if an agent completes its subtask earlier or later than others, the plan is updated based on the actual progress of all components rather than on a fixed schedule (see Figures 7 and 8 in Appendix E for an example). Execution errors are captured in the same way: both satisfaction and violation are determined by running the actual labels L(s) through the automaton of each component specification (lines 830-835). If the labels lead any component automaton to a state from which its specification can no longer be satisfied, the trajectory is counted as a violation. The reported results therefore reflect the end-to-end effect of such execution errors.

  1. The evaluation scenarios are limited in scope. Experiments focus primarily on navigation environments, lacking validation against other multi-task generalization benchmarks in MARL; consequently, the applicability of the method across diverse task structures and collaborative settings remains unclear.

Please see our response to Question 3.

AuthorsOpenReview ↗

Rebuttal (Part 2/2)

Questions

  1. Could you compare your approach, which avoids full-scale composition, against planning methods that also utilize the same low-level policies? Additionally, could you clarify whether the observation conditions for the learning baselines are consistent with those of your proposed method?

For the comparison with planning methods using the same low-level policies, please see our response to Weakness 1 and the ablation study in Section 5.3. Regarding observation conditions, both methods use the same environment observations for a fair comparison, and for ACC-MARL we follow its original procedure to pretrain the DFA embeddings. Further details are provided in Appendix C.

  1. How are synchronization constraints enforced through local sub-task policies? Furthermore, how does the high-level controller coordinate and adjust the plan when agents arrive at different times or when an execution failure occurs?

The low-level policies only execute their current reach-avoid subtasks; synchronization is enforced by the high-level planner. For a synchronization constraint such as Sync[{0, 1}, blue, 2], the planner assigns reaching blue to both agents, and this component’s automaton only progresses once both agents satisfy blue at the same time. Until then, the planner keeps assigning blue to both agents, including after replanning triggered by other components. For example, in Figure 7, agent 1 reaches magenta at t = 289, and the planner retains magenta for both agent 1 and agent 2 until they reach it simultaneously at t = 349, satisfying the synchronous count requirement. Agents arriving at different times and execution failures are handled by replanning, as described in our response to Weakness 2.

  1. Could you provide additional results on other relevant multi-task generalization benchmarks for MARL, such as StarCraft(SMAC), to demonstrate the method's generalization capabilities across diverse environments and varying collaborative requirements?

We believe SMAC[1] is not suitable for evaluating our method. SMAC focuses on multi-agent challenges rather than multi-task generalization: each scenario has a fixed objective of defeating the enemy units, which in our specification language would simply be \mathsf{F}\ \text{eliminate_enemies} for every agent. Which agent attacks which enemy does not need to be specified, and there are no inter-agent dependency or count constraints that must be satisfied. In contrast, the Zone environment is a standard benchmark for generalization across temporal-logic specifications, and our multi-agent extension is similar to the commonly used Multi-Agent Particle Environment, while additionally requiring long-horizon tasks, diverse coordination constraints, and collision avoidance.

[1] https://arxiv.org/pdf/1902.04043

Thank you for the detailed reply. Regarding the event-triggered replanning and the Sync synchronization waiting mechanism, your explanations are very clear. However, several concerns I raised earlier, such as the comparison with other efficient planning methods, how high-level planning accounts for the physical feasibility in real environments, and the generalization validation in more complex multi-task scenarios, are not yet fully addressed by your current responses and experiments. Taken together with the limitations in theoretical proof and communication assumptions raised by other reviewers, I have decided to maintain my current score.

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

This paper proposes SpecMAGIC to address zero-shot generalization in multi-agent reinforcement learning when both individual LTL objectives and cross-agent coordination requirements change at test time. SpecMAGIC converts individual specification components into Büchi automata and employs a centralized randomized tree search to select, interleave, and assign candidate reach–avoid sequences, thereby avoiding the explicit construction of the full global product automaton. The resulting plan is executed by a shared subtask-conditioned low-level policy adapted from GenZ-LTL. The framework is evaluated in the Zone navigation environment with 3, 5, and 10 agents, covering in-distribution and out-of-distribution specifications, finite- and infinite-horizon tasks, and multiple coordination structures. The results suggest that this decomposition can reduce the practical search-space size relative to explicit product-automaton search on the evaluated instances.

Critical strengths

The paper studies an important generalization problem. Most prior work on specification-conditioned reinforcement learning focuses on either single-agent settings or fixed coordination structures. Jointly varying individual LTL objectives and cross-agent dependency and synchronization requirements constitutes a meaningful research problem with potential relevance to modular multi-robot systems. Reliably addressing this problem could broaden the practical applicability of specification-guided MARL.

The hierarchical decomposition has practical potential. Separating symbolic task composition from reusable low-level reach–avoid policies is a reasonable modular design. On suitable instances, avoiding the explicit construction of the full global product automaton can substantially reduce practical computational overhead. Table 2 also shows that the sampled trees are considerably smaller than the reported product-automaton references. This design offers a plausible path toward reusing learned policies across unseen specifications, although the current scalability claims require qualification.

Critical weaknesses

The core formal guarantees have not been established.

Theorem 1 (p. 6; proof on p. 13) uses the same notation for an environment trajectory and a symbolic subtask sequence, but does not define a mapping from the latter to a proposition word. Preserving the order of local sequences and checking instantaneous Boolean compatibility are insufficient, by themselves, to prove that the merged word is accepted by every component automaton, that components which are not advanced preserve their states, or that cyclic suffixes remain jointly realizable. This issue is particularly concrete for formulas containing X, since such formulas are not stutter-invariant and X appears in the translation of EachReq.

Theorem 2 (p. 6; proof on p. 13) treats successful expansions as i.i.d. Bernoulli trials and applies a binomial tail bound. However, tree expansion is history-dependent: a successor cannot be generated before its predecessor exists, the tree structure and parent-selection probabilities change over time, and successful expansions on unrelated branches cannot be combined into a single feasible path. Moreover, §4.2 and Appendix B.2 assign inequivalent semantics to EachReq. For example, when neither α nor β occurs, the stated event-triggered semantics is vacuously true, whereas ¬α U β is false. These issues require reformulation rather than a local clarification.

The experiments do not support the strongest claims about contribution attribution, infinite-horizon tasks, and scalability.

The only learning baseline, ACC-MARL, supports only Φ_ind, and therefore cannot be compared in the coordination settings central to this paper. The paper provides neither a matched-backbone comparison using alternative allocators with the same GenZ-LTL controller nor an oracle-controller experiment that isolates the planner's correctness. For infinite-horizon evaluation, the method repeats a finite cyclic suffix and measures violations and accepting-state visits over episodes of at most 2,000 steps (Table 5); finitely many accepting-state visits cannot establish Büchi satisfaction or long-run fairness.

Questions for authors

Formal semantics and EachReq: What exact semantics for EachReq are used in the implementation? Please reconcile the definition in §4.2 with the LTL formula in Appendix B.2, including traces in which neither event occurs and traces in which α and β occur simultaneously. Do the results in Table 5 change under the corrected semantics?

Scope of the soundness guarantee: Can the authors formally define the mapping from the returned subtask plan to an AP word and prove that the word's projection is accepted by every component automaton? Please specify the supported LTL fragment, explain how formulas containing X are handled under interleaving, and clarify that the guarantees apply to the abstract planner conditional on successful low-level execution rather than to the stochastic end-to-end system.

Scope of the completeness guarantee: Can Theorem 2 be restated and proved using a conditional full-support assumption and per-edge geometric waiting-time arguments? Is completeness guaranteed only relative to the finite set of precomputed candidates {G_i}? How are these candidate sets generated or truncated?

Infinite-horizon claims: What rigorous conclusion about Büchi satisfaction can be drawn from a finite 2,000-step rollout and finitely many accepting-state visits? What is n_cyc? What replanning and fairness assumptions are made, and what mechanism prevents components from starving during long-run execution?

Controlled attribution and statistical reporting: Can the authors provide either a matched-backbone comparison using the same low-level policy with alternative allocators or an experiment with oracle low-level execution? Can Tables 1 and 5 be recomputed so that uncertainty consistently reflects variation across random seeds? These results would materially affect whether the empirical evidence supports the proposed planner or instead reflects the inherited controller or the reporting methodology.

4 comments
AuthorsOpenReview ↗

Rebuttal (Part 1/3)

We thank the reviewer for their comments and feedback. We address each weakness and question below and the revised content in the manuscript is highlighted in red.

Critical Weaknesses

  1. The core formal guarantees have not been established. Theorem 1 (p. 6; proof on p. 13) uses the same notation for an environment trajectory and a symbolic subtask sequence, but does not define a mapping from the latter to a proposition word. Preserving the order of local sequences and checking instantaneous Boolean compatibility are insufficient, by themselves, to prove that the merged word is accepted by every component automaton, that components which are not advanced preserve their states, or that cyclic suffixes remain jointly realizable. This issue is particularly concrete for formulas containing X, since such formulas are not stutter-invariant and X appears in the translation of EachReq.

With a slight abuse of notation, τ\tau in Theorem 1 denotes the target trace specified by the returned subtask sequence, which is related to environment trajectories through the labeling functions defined in Section 3; we have clarified this in the revision. As mentioned in lines 276-281, Theorem 1 builds on the reach-avoid subtask sequences of each component, which are extracted from accepting runs of its automaton using established methods, such that following a sequence satisfies the corresponding component specification. Details on how these sequences are obtained are provided in GCRL-LTL, DeepLTL, and GenZ-LTL, which we cite in Sections 4.3 and 4.4. Our planner keeps track of the progress of every component and only interleaves these sequences without changing their order. At every step, it checks compatibility against the avoid conditions of all components, including those that are not advanced. Each component therefore still follows its own sequence, and Theorem 1 follows. Moreover, the empirical results do not rely on this argument. As described in Appendix C (lines 830-835), the traces of each rollout are evaluated directly against every component specification: “For finite-horizon tasks, a trajectory is considered successful only if all specification components are satisfied, whereas it is considered a violation if any component is violated.” The reported success rates therefore measure actual satisfaction of the specifications, rather than completion of the planned subtasks.

  1. Theorem 2 (p. 6; proof on p. 13) treats successful expansions as i.i.d. Bernoulli trials and applies a binomial tail bound. However, tree expansion is history-dependent: a successor cannot be generated before its predecessor exists, the tree structure and parent-selection probabilities change over time, and successful expansions on unrelated branches cannot be combined into a single feasible path.

Our proof does not treat expansions as independent. It fixes one feasible path and counts only extensions along that path, i.e., adding the next node of the path once its predecessor is in the tree. At every iteration, regardless of the current tree, this extension succeeds with probability at least p = 1/(MC): the tree never contains more than M nodes, so the path’s current node is selected with probability at least 1/M, and the required subtask combination is sampled with probability 1/C. Since each iteration extends the fixed path with probability at least p regardless of the current tree, the probability of fewer than m extensions after K iterations is at most that of a Binomial(K, p) random variable, and the binomial tail bound applies. Successes on unrelated branches are never counted, and a successor is never counted before its predecessor exists. We have made this explicit in the revised proof in Appendix A.

  1. Moreover, §4.2 and Appendix B.2 assign inequivalent semantics to EachReq. For example, when neither α nor β occurs, the stated event-triggered semantics is vacuously true, whereas ¬α U β is false. These issues require reformulation rather than a local clarification.

Thank you for pointing this out. We have updated the definition of EachReq in Section 4.2 as follows: τ⊨α EachReq β\tau \models \alpha \ \texttt{EachReq} \ \beta iff τ⊨α Req β\tau \models \alpha \ \texttt{Req} \ \beta and, for every t≥0t \geq 0 such that τ,t⊨α\tau, t \models \alpha and either t=0t = 0 or τ,t−1⊭α\tau, t-1 \not\models \alpha, there exists t′∈[0,t]t' \in [0, t] such that τ,t′⊨β\tau, t' \models \beta and τ,t′′⊭α\tau, t'' \not\models \alpha for all t′′∈[t′,t)t'' \in [t', t). Since our implementation uses the formula in Appendix B.2 for both planning and evaluation, and in all evaluated specifications the prerequisite β of each EachReq clause must be visited infinitely often under the corresponding individual-agent specification, the original results still hold.

AuthorsOpenReview ↗

Rebuttal (Part 2/3)

  1. The experiments do not support the strongest claims about contribution attribution, infinite-horizon tasks, and scalability. The only learning baseline, ACC-MARL, supports only Φind\Phi_{ind}, and therefore cannot be compared in the coordination settings central to this paper. The paper provides neither a matched-backbone comparison using alternative allocators with the same GenZ-LTL controller nor an oracle-controller experiment that isolates the planner's correctness. For infinite-horizon evaluation, the method repeats a finite cyclic suffix and measures violations and accepting-state visits over episodes of at most 2,000 steps (Table 5); finitely many accepting-state visits cannot establish Büchi satisfaction or long-run fairness.

ACC-MARL is, to our knowledge, the only existing method for generalization across temporal-logic specifications in MARL. It only supports independent individual tasks, so we compare against it on Φind\Phi_{ind}, and no existing baseline supports the coordination settings.

To isolate the contribution of our planner, in Section 5.3 we compare it with a reference allocator using the same GenZ-LTL low-level policies: a product-automaton (PA)-based planner, which applies the automaton search used in DeepLTL and GenZ-LTL to the product automaton of all specification components. Our planner achieves similar success and violation rates with substantially less planning time. The planner’s benefit becomes clearer as the number of agents grows. The PA-based planner fails to find a plan within 10 minutes once four or more agents are involved, and for 10 agents the product automaton cannot even be constructed within one hour. Our planner, in contrast, finds plans in 8.64 seconds on average for 10 agents while keeping the search tree small (Table 2). Regarding an oracle controller, our setting assumes unknown dynamics, so such a controller is not available; the planner’s correctness is addressed in our response to Weakness 1.

For infinite-horizon tasks, we do not claim that finite rollouts establish Büchi satisfaction. Following prior work (DeepLTL and GenZ-LTL), we report the violation rate, where a trajectory counts as violating if any component is violated, and the number of visits to accepting states among non-violating trajectories. For each such trajectory, as mentioned in lines 830-835, we count the accepting-state visits of every component and report the minimum across components. A high value therefore means that every component repeatedly reaches its accepting states, which shows empirically that no component is starved.

AuthorsOpenReview ↗

Rebuttal (Part 3/3)

Questions

  1. Formal semantics and EachReq: What exact semantics for EachReq are used in the implementation? Please reconcile the definition in §4.2 with the LTL formula in Appendix B.2, including traces in which neither event occurs and traces in which α and β occur simultaneously. Do the results in Table 5 change under the corrected semantics?

Our implementation uses exactly the LTL formula in Appendix B.2 for both planning and evaluation. Please see our response to Weakness 3 for the revised definition in Section 4.2, which now matches this formula: requiring α Req β handles traces in which neither event occurs, and allowing t′ ∈ [0, t] handles traces in which α and β occur simultaneously. Since all results were computed with this formula, Table 5 does not change.

  1. Scope of the soundness guarantee: Can the authors formally define the mapping from the returned subtask plan to an AP word and prove that the word's projection is accepted by every component automaton? Please specify the supported LTL fragment, explain how formulas containing X are handled under interleaving, and clarify that the guarantees apply to the abstract planner conditional on successful low-level execution rather than to the stochastic end-to-end system.

Please see our response to Weakness 1. In short, the soundness guarantee applies to the high-level planner, i.e., any trajectory that successfully executes the returned plan satisfies the global specification, while end-to-end performance under unknown dynamics is evaluated empirically in Section 5.

  1. Scope of the completeness guarantee: Can Theorem 2 be restated and proved using a conditional full-support assumption and per-edge geometric waiting-time arguments? Is completeness guaranteed only relative to the finite set of precomputed candidates {G_i}? How are these candidate sets generated or truncated?

Please see our response to Weakness 2: our proof only requires that, regardless of the current tree, each iteration extends a fixed feasible path with probability at least p > 0, and bounds the failure probability with the binomial tail. The candidate sets {G_i} are not truncated; they contain all reach-avoid subtask sequences obtained by the automaton search used in DeepLTL and GenZ-LTL.

  1. Infinite-horizon claims: What rigorous conclusion about Büchi satisfaction can be drawn from a finite 2,000-step rollout and finitely many accepting-state visits? What is n_cyc? What replanning and fairness assumptions are made, and what mechanism prevents components from starving during long-run execution?

As discussed in our response to Weakness 4, we do not claim that a finite rollout establishes Büchi satisfaction; following DeepLTL and GenZ-LTL, the infinite-horizon results report violation rates and accepting-state visits as empirical evidence. We use ncyc=2n_{cyc} = 2. Replanning is triggered whenever the automaton state of any component changes: the reach-avoid subtask sequences are first recomputed from the current automaton state of each component, and the planner then plans again over these updated sequences (Appendix C). Starvation is prevented by the planner: a plan is only returned once every component has reached the end of its selected sequence, and each sequence repeats the looping part of its accepting cycle ncycn_{cyc} times, where each repetition visits at least one accepting state. Every plan therefore requires every component to visit its accepting states repeatedly. This is also reflected empirically, since we report the minimum number of accepting-state visits across components (lines 830-835).

  1. Controlled attribution and statistical reporting: Can the authors provide either a matched-backbone comparison using the same low-level policy with alternative allocators or an experiment with oracle low-level execution? Can Tables 1 and 5 be recomputed so that uncertainty consistently reflects variation across random seeds? These results would materially affect whether the empirical evidence supports the proposed planner or instead reflects the inherited controller or the reporting methodology.

Please see our response to Weakness 4: Section 5.3 compares our planner with a product-automaton-based allocator using the same GenZ-LTL low-level policies, and an oracle controller is not available under unknown dynamics. As stated in the captions, each value in Tables 1 and 5 is reported as the mean and standard deviation over 5 random seeds, with 100 trajectories evaluated per seed.

Dear Reviewer,

As the rebuttal period is coming to an end, we kindly ask you to review our response. If you have any remaining concerns, we would be happy to provide further clarification. If our response has addressed your concerns, please consider raising your score.

Best,
The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.