- 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
Syncoperator. - 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
Rebuttal (Part 2/5)
- 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).
Rebuttal (Part 3/5)
- 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 is , where is the global state from agent ’s own point of view, as in ACC-MARL, and 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.
| Env | Method | Reach | ReachAvoid | RAD | Reach (OOD) | ReachAvoid (OOD) | RAD (OOD) |
|---|---|---|---|---|---|---|---|
| Buttons-2 | ACC-MARL | 0.860 ± 0.042 | 0.790 ± 0.057 | 0.821 ± 0.044 | 0.677 ± 0.085 | 0.456 ± 0.074 | 0.522 ± 0.046 |
| Ours | 0.859 ± 0.029 | 0.805 ± 0.041 | 0.854 ± 0.022 | 0.617 ± 0.050 | 0.477 ± 0.057 | 0.598 ± 0.033 | |
| Rooms-2 | ACC-MARL | 0.890 ± 0.034 | 0.871 ± 0.040 | 0.866 ± 0.032 | 0.723 ± 0.082 | 0.577 ± 0.065 | 0.559 ± 0.039 |
| Ours | 0.948 ± 0.056 | 0.886 ± 0.059 | 0.929 ± 0.042 | 0.959 ± 0.047 | 0.747 ± 0.076 | 0.875 ± 0.050 | |
| Buttons-4 | ACC-MARL | 0.751 ± 0.044 | 0.676 ± 0.032 | 0.736 ± 0.031 | 0.482 ± 0.029 | 0.282 ± 0.021 | 0.355 ± 0.005 |
| Ours | 0.915 ± 0.094 | 0.810 ± 0.079 | 0.867 ± 0.087 | 0.813 ± 0.191 | 0.547 ± 0.110 | 0.686 ± 0.145 | |
| Rooms-4 | ACC-MARL | 0.832 ± 0.017 | 0.764 ± 0.018 | 0.795 ± 0.010 | 0.539 ± 0.058 | 0.363 ± 0.020 | 0.392 ± 0.012 |
| Ours | 0.987 ± 0.015 | 0.888 ± 0.011 | 0.947 ± 0.011 | 0.992 ± 0.014 | 0.697 ± 0.026 | 0.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.
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
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).
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.