Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors present a method to decompose a centralized shield in a multi-agent system to individual shields for each agents that can enforce a safety specification with no communication between agents. The authors' proposed approach takes a centralized shield and outputs a maximally permissive decentralized shield. The authors then show, using experiments on gridworlds, that their decentralized shields can perform comparably to a centralized shield and significantly outperforms no shield at all. 
strengths_and_weaknesses: This paper, while writen clearly, needs significantly more detail and preciseness. The paper also needs better structure as it is not easy to find out what exactly the problem statement is and what the inputs to the problem are and the outputs of the solution. Clearly stating the problem statement in the paper would be helpful. 

The focus of this paper is on the no-communication aspect of the multi-agent shielding problem. However, one of the main issues with multi-agent shielding is that centralized synthesis often scales very poorly. This aspect is not addressed much by the authors, which can be problematic as their solution requires the input of a centralized shield which is often not computationally feasible to procure. 

Furthermore, the paper would benefit greatly from complexity results. One of the key contributions is the decomposition of the centralized shields, but there is no intuition on the scaleability of the process. Additionally, it could also help to report synthesis times in the experiments. 
questions: Can the authors provide any theoretical complexity results on their decomposition process? It is stated simply in section 7 takes linear time in the number of state-label pairs of the centralized shield. A proof, or at least intuition for this statement will be helpful. 



Is there a proof the resulting decentralized shield is indeed maximally permissive? 
limitations: Adequately addressed.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the problem of reinforcement learning in the scenario in which some states are unsafe, and an agent cannot be allowed to visit them, not even as part of exploration. An example of such a scenario would be a robot behaving in a physical environment, in which it should not collide pedestrians, who might be hurt from such a collision. Due to this safety-critical nature of the problem, it is not sufficient to assign a negative reward to those states and expect the agent to learn to avoid those states from experience.

Existing work has considered the task of learning "shields", which are a state-dependent subset of actions that ensure that the agent(s) will never visit the unsafe states. It is possible to generalize the notion of shields to the multi-agent scenario by requiring that the joint actions taken by all of the agents satisfy the constraints of the (centralized) shield, but this has the drawback that it requires the agents to communicate and coordinate their actions, as well as for the shield to have enough information about all of the agent behaviors to know which state restrictions it should impose next.

This work considers the problem of automatically decomposing a centralized shield into a set of decentralized shields, one for each agent. The shields are iteratively constructed by adding actions for agent that do not result in a violation of the centralized shield. The authors demonstrate their approach on a collection of RL case studies.
strengths_and_weaknesses: - The work is certainly relevant. Distributed safe reinforcement learning is an important topic with a broad array of useful applications.

- The case studies demonstrate feasibility of the approach.

- The soundness theorem seems to be correct.

- The metric on permissiveness is given in terms of average actions per state, but this may be the wrong metric. In some cases, a few actions in a specific state may disallow a large portion of the behavior-space, resulting in excessively conservative behavior that is not accurately captured by the metric considered. For finite MMDPs, it should be possible to quantify the percentage of the behavior-space that is lost, and I think this would make for a better metric.

- I have a few open questions, some of which may be straightforward for the authors to address in the camera-ready version.
questions: - If the centralized shield is Cartesian and unambiguous, the authors claim in line 172 that their algorithm will produce maximally permissive shields. This statement is given casually, and does not even receive an informal argument to justify it. This statement further seems to be contradicted on line 325. Does this procedure produce maximally permissive decentralized shields, even in the restricted case of cartesian and unambiguous shields?

- For a given centralized shield, is the decomposition unique? This is not clear to me, it is not stated in the paper, and if a decomposition is not unique, it may be valuable to be able to be able to search among decompositions to balance application-specific trade-offs.

- Is it possible to derive a result on a bound for how conservative a distributed shield will be? It seems that for the case of finite MMDPs, it should be possible to quantify how many behaviors are allowed by the centralized shield and disallowed by the decomposition. It would be useful for practitioners to be able to quantify how much of a penalty they are paying in a specific application.

- The authors mention informally that the complexity of computing a shield decomposition is linear in the size of the centralized shield--but how does this relate back to the complexity of the original MMDP? I expect that the complexity of computing a centralized shield is known, and I think the paper would be improved by expressing the complexity of a distributed shield from the size of the MMDP.

- The authors seem to be familiar with the formal methods literature. Existing work in that literature considers the problem of decomposing safety properties into contracts for components in a large architecture--how does their work relate to the contract decomposition literature?
limitations: I think the limitations were suitably addressed.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors address the problem of safe multi-agent decision making in decentralized communication free environment. They build upon previous approaches generating centralized safety shield in multi-agent problems to propose an algorithm that generates a decentralized safety shield given the centralized one. 
The algorithm consists of a search procedure, it first identifies one safe actions for every agent at every states. Then it is progressively extending that set for each agent. To extend the set it checks that every new actions to be added still satisfies the safety constraints and is unambiguous. Some proofs are provided in appendix. 

The authors empirically analyze the decentralized shielded generated by their algorithm on two discrete environments. In both cases the shield is generated to prevent collisions between two agents in a discrete grid world domain. 

strengths_and_weaknesses: The grade has been updated after clarification by the author on the figure illustrating how the proposed algorithm works. 

The problem being addressed is relevant and important as multi-agent decision making and safe decision making can be applied to many societal applications. Such concept of decentralized shielding and the approach to generate the decentralized shield is to the best of my knowledge novel.

Overall the paper is really clear and well-written, the introduction, related work and problem setting are very nice to read. The related work section is quite clear and they clearly highlight how their method builds upon existing work in a non-trivial way by proposing an algorithm decentralizing an existing centralized shield. They do a very good job explaining a naïve approach to build such shield and how it can be improved. Some intuitive explanation is always provided to accompany the formalism and it is greatly appreciated. 

The experiments are satisfactory, however some discussion is missing on how it would handle more complex safety specification and scale to more than 1 agents. It would have been very nice to introduce another problem that is not related to collision avoidance. 

 The clarity of figure 1 and figure 2 is insufficient though. I read the caption multiple times and I still don’t get it. See questions. It almost seems like one paragraph is missing from the paper. Maybe the author could remove a figure and add theorem 1 which is referred to many times. Luckily algorithm 1 is quite ok to follow. 
 
An aspect that was unclear to me is how the joint state is handled, it seems the authors assume that the joint state is fully observable by all the agent and there is one mention that it could be extended to individual state. It seems like such task is highly non trivial. The fact that the agent observe the joint state makes me question the initial claim of communication free environment. 


questions: 1. What is the example problem in figure 1 and 2? What are the red and green square, what are the circles? 
2. For future work, would it be more efficient to directly search for decentralized shield rather than computing a centralized shield first and then decentralizing it?
3. Could you clarify whether or not each agent need to observe the joint state?
4. What is the benefit of algorithm 2 and 3 over algorithm 1? This was not obvious from reading the paper.

limitations: The authors are upfront and clearly explained the limitation of their method and impact in section 7. They mention possible extension for future work. The most important one is to address the scalability issue. The authors are also very clear about experimental challenges on the design of the environment.
review_title: null

Meta-review: metareview: It is agreed among reviewers that the paper should be accepted. Hope the authors can address the comments from the reviewers in the final version as promised.
confidence: Certain
Decision: Accept