Shield Decentralization for Safe Multi-Agent Reinforcement Learning
Authors: Daniel Melcer
Christopher Amato
Stavros Tripakis
Venue: NeurIPS 2022 Accept (2022)
Keywords: safety
shielding
reinforcement learning
synthesis
multi agent

Abstract: Learning safe solutions is an important but challenging problem in multi-agent reinforcement learning (MARL). Shielded reinforcement learning is one approach for preventing agents from choosing unsafe actions. Current shielded reinforcement learning methods for MARL make strong assumptions about communication and full observability. In this work, we extend the formalization of the shielded reinforcement learning problem to a decentralized multi-agent setting. We then present an algorithm for decomposition of a centralized shield, allowing shields to be used in such decentralized, communication-free environments. Our results show that agents equipped with decentralized shields perform comparably to agents with centralized shields in several tasks, allowing shielding to be used in environments with decentralized training and execution for the first time.

Shield Decentralization for Safe Multi-Agent Reinforcement Learning
Daniel Melcer
Christopher Amato
Northeastern University
Northeastern University Boston, MA 02115 amatoohorthhasttern.ce
Boston, MA 02115
melcer www.ordeeatteeenccoom
Stavros Tripakis* Northeastern University Boston, MA 02115
s stavros@hortheastemn. edu
Abstract
Learning safe solutions is an important but challenging problem multi-agent re- inforcement learning (MARL). Shielded reinforcement learning is approach for preventing agents from choosing unsafe actions. Current shielded reinforce- ment learning methods for MARL make strong assumptions about communica- tion and full observability. In this work, we extend the formalization of the shielded reinforcement learning problem to decentralized multi-agent setting. We then present an algorithm for decomposition of centralized shield, allowing shields to be used in such decentralized, communication-free environments. Our results show that agents equipped with decentralized shields perform comparably agents with centralized shields in several tasks, allowing shielding to be used environments with decentralized training and execution for the first time.
Introduction
Recently, the advent of deep reinforcement learning has produced solutions in highly complex do- mains such Atari [17), and the game of Go 20 However, the neural networks which power these methods are opaque, and there is significant risk of unintentional harm when a poorly understood safety-critical system
reinforcement learning method is applied
One common approach for safe RL is the idea of shield-a reactive system which monitors a reinforcement learning agent and environment [1]. During each step, the agent proposes action, the shield evaluates whether this action safe, and then the shield potentially replaces the proposed action with known-safe action. This method has been extended to multi-agent environments, but the shield remains centralized [TO) Such methods assume instantaneous communication with centralized coordination algorithm, which is not realistic in many environments.
In this work, we first diseuss the centralized shield synthesis problem, and outline its proposed so- lutions. We describe several implicit communication assumptions present in the existing centralized shield definition, and define a novel framework for decentralized shiclding. These decentralized shields enable each agent to act independently, without any coordination after shield synthesis.
'Equal Advising
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Our main technical contribution is algorithm which, using any centralized shield input, pro- duces a decentralized shield that guarantees safety. We also discuss various properties of input centralized shields, and the effect of these properties on the permissiveness of the output shield.
Lastly, we evaluate the performance of our shield decomposition algorithm on shields from several domains. We first analyze the structure of the shield itself, ensuring that the majority of actions allowed by the centralized shield are still allowed by the decentralized shield. We then train a shielded reinforcement learning agent to solve these tasks, and measure the performance of the learned policy. We find that all agents achieve a comparable value in the environment, and that, as be expected from the theoretical guarantees of our framework, decentralized shielding achieves 100% safety. These results show that our shield decentralization approach can, for the first time, allow reinforcement learning methods be provably safe in decentralized multi-agent settings.
Related Work
The concept of shielded reinforcement learning [ draws from the idea of Runtime Enforcement [6], from the Formal Methods community. In the single-agent case, shielding has been extended environments with continuous action spaces [8], stochastic adversarial environments [IS], and partially-observable environments 77. As with all shielding methods, these extensions require model of the environment, with a varying degree of abstraction. This differs slightly from contract- based decomposition [5; instead of defining contract first, and then constructing systems whose interfaces satisfy this contract, shielding involves constraining an agent to act safely within an envi- ronment whose dynamics are fixed.
Other proposed methods specify algorithms for enforcing safety in the presence of communication constraints or delays for pathfinding agents 23 or for general LTL specifications [2] but neither method eliminates communication entirely.
Several pieces of work focus on verifying a neural network or closed-loop reinforcement learning system after training is complete [4]. These methods could potentially succeed in a multi-agent reinforcement learning system if successfully scaled up, but such approaches typically make no guarantees of safety during training.
Preliminaries
We first describe several relevant structures, and formalization of the centralized shielding problem. Many elements of this framework have been described in prior formulations [1] 3 and extended to the multi-agent setting [TC..
Let A(X) be the set of all probability distributions over set X. Let denote the set of reals.
An environment with cooperative agents and full observability is often characterized MMDP:
Definition (MMDP) Multi-agent Markov Decision Process (MMDP) is tuple M (D,S, A., E,T,", R, be) where ID = (1.....,.) is a set of agents, S is a set of states, A = -Ie Aq is a finite joint action space, factorizaae into n individual action spaces, E S + P(A) represents the of actions available to the agents at given state, T S & A(S) is the transition probability distribution function, ? E [0, 1] represents the discount factor for future rewards, R. S x A R is the reward given after transition, and by ASS) is the distribution of initial states.
We call sequence of states and joint actions ((s0, $1..... $1,...,88411. $n+1), (ao, a1. a2 an environment trace of MMDP M if every pair (s,, 04, 8(41) is allowed by the transition function of the MMDP.
M is said to be in deadlock state E S if E(s) 0. M is deadlock-free if there are no environment traces of M that end in a deadlock state.
We will often have some prior knowledge of how to abstract the states in meaningful way for safety properties. For example, in a domain where we avoid collisions between agents, the relative positions of the agents may be useful, even if the absolute positions of all agents are not known.
We call a function f - which translates MMDP states into members of given label set an abstraction function. Note that some prior work refers to f the observer function
10

---

use different name to avoid potentially conflicting terminology. Every environment trace through
MMDP has a corresponding label trace (oo, ao)...., (bn, )), where Vi E (0....,n),, Several unique environment traces may correspond to the same label trace.
nn, 4 = /(
We note that an environment with partial observability or more complex reward structure is accept- able. As long each agent can independently calculate the current label, a shield can be constructed using this framework. However, for simplicity, we continue to use MMDPs in our description.
Definition 2 (DFA) A Deterministic Finite Automaton (DFA) is a tuple Φ (Q,E, so, F) where Q is a set of states, Sy E Q is the initial state, E is an alphabet, 6 6: Q x E - Q is the transition function, and F - Q is the set of accepting states.
Given a word (wy, Wi...., wn) E Σ", the corresponding DFA trace (qu. 9..... qn+1) E Q" is obtained by stepping through the transition function. A word is accepted by the DFA iff the last state of its corresponding DFA trace is member of F.
For given MMDP M = (D, A, E, T, R. bo) and label set I,, we define safety specification over M and L to be a DFA 6= = (Q", (L x A), F*) which accepts the empty word and does not contain any transitions from Q" F to Fs. .M satisfies d² (M F= o") iff all possible
label traces of MM are accepted by d², d² induces the accepting action function C Q" x L -
P(A)= - (g. 1) + {a E (q, (1, E }² given a DFA state and label, output the actions which transition the DFA to an accepting state.
We can compose DFA d² and a MMDP M to form new MMDP (M)) The state space of the resulting MMDP is the product of the state spaces of M and 6º, and the transition function steps through the DFA and MMDP's states in lockstep. At state (s, q). a given action is only enabled in the resulting MMDP if is a member of both E(s) and C* (q. (s)).
4 Centralized Shielding
We use a definition of a centralized shield based on the joint actions which are allowed at each shield state. Note that some prior formulations define the shield as Moore machine which outputs a specific safe action in response to an input action 3i; the following definition is equivalent.
Definition 3
(Centralized Shield) A DFA 6 is a centralized shield for MMDP M that enforces safety specification ø² iff M| = 6f and Mil0s is deadlock-free.
Problem 1 (Centralized Shield Synthesis) Given a MMDP M (I, (,,,,A,,,T, R, bo), a label set L. an abstraction function f over M and L, and safety specification 6² over M and L, synthesize a centralized shield for M that enforces 6²
This problem has previously been explored in M1 for the single-agent case, and 10 for the multi- agent case; we do not aim to advance the state of the art in this domain. Briefly, centralized shield synthesis works by constructing game with two players: the agents, and the environment. When constructing shield for a multiagent environment, all agents are collectively considered one "player" whose action set equals the space of joint actions for all of the agents. The environment proposes label, and the agents must respond with a joint action which does not violate the safety specification. The safety game is solved, typically by iterating to a fixpoint (9]
A complete model of the environment not necessary for this synthesis; an abstraction which cap- tures all possible label traces is sufficient. For example, our test environments all involve avoiding collisions. We therefore use the relative positions of the agents as the label set. The environment abstraction only captures information about how the relative positions of the agents change with each joint action, not any information about rewards or walls.
When using a centralized shield, the agents never explicitly construct the full composition of M Ml as M may have an infinite state space, and its exact dynamics may not be known. Instead, the agents maintain the current centralized shield state g. initialized to sg At every time step, they observe the label 1 from the environment. Using the shield's induced accepting action function, the agents compute the set of safe actions C*D (g.
We intentionally omit f(sn+1) ) allow label traces be word of (L A)"
3

---

At this point, there are common design choices in how the shield gets used M. In pre-posed shielding, the agent's action space is restricted to C (g. (); it is unable to choose an unsafe action. In post-posed shielding, the agent is free to choose any action. However, the action is not safe, the shield substitutes the action with an arbitrary action a' E C** (g. The agent observes, and is trained on the environment transition (s, a', s'). The agent is additionally trained on the synthetic transition (s, 0,, v + Tp; s') where Tp is a penalty reward. For both designs, the shield's transition function 59 is then used to obtain the next centralized shield state. We choose to use post-posed shielding for our experiments, as this method generalizable to a greater variety of agents.
5 Decentralized Shielding
The use of centralized shield requires agents to communicate with each other for two reasons:
First, the set of safe individual actions for a given agent may depend on the action choice of all other agents. For example, consider the safety specification where an even number of agents must pick a given action. Unless a single joint action decided upon in advance, the agents must all communicate before action selection in order to choose a safe action.
Furthermore, even if the set of safe individual actions independent, the centralized shield may transition to different states in response to different joint actions- if both joint actions produce the same result in the environment. Alshiekh al. M gives the example of industrial valve controller, where the flow of water through the valve is stochastic when the valve is open. Consider similar environment where multiple agents each control an independent valve, and unable to observe other agents' valve states, but they do observe the flow of water through each valve. An agent would not be able to tell the difference between other agents' valves being closed, versus their valves being open without water flowing during a given step due to chance. Depending on the shield structure, there may be no way to calculate what the next shield state is based on flow rates alone.
Therefore, in a no-communication environment, each agent must be equipped with a shield which has the following two properties: First, each agent must be able to independently choose actions. No matter what combination of actions are chosen by the various agents, the joint action must be safe. We call shield with this property Cartesian, as the safe joint action results from the Cartesian product of each agents' safe individual action sets. Second, each agent's local shield must be able to independently determine its next internal state, without direct knowledge of the actions that other agents have taken. We call a shield with this property unambiguous.
We call DFA an individual shield for agent D if the transition alphabet of this DFA is L L A, If P
the produc of a series of individual shields forms a centralized shield which enforces specification σ², we say that the individual shields collectively form decentralized shield which enforces s².
Problem 2 (Dec-A Shield Synthesis) Given MMDP M = (D, E,T. R, bu), a label set L, an abstraction function over M and L, and safety specification di,, synthesize decentralized shield which enforces 6h
Problem is generally hard to solve, and may even be undecidable in some cases, as it is related to decentralized controller synthesis problems |E 21 Therefore, instead of solving Problem 2 di- rectly, we opt for the following approach. First, we attempt to synthesize a centralized shield (i.c., to solve Problem P using the methods described in Section R If this fails, i.e., if centralized shield exists, than we can conclude that no decentralized shield exists either. If, on the other hand, we man- age to synthesize a centralized shield, than we can decentralize it, thereby turning our decentralized shield synthesis problem into the following shield decomposition problem:
Problem 3 (Dec-A Shield Decomposition) Given a MMDP M (D, R, by) and centralized shield de for M, synthesize a decentralized shield for M which enforces 6².
Problem 3 admits trivial solution, where for every shield state and label, we prescribe a single safe joint action in advance. Such a joint action guaranteed exist for all reachable states due to the deadlock-free property of the centralized shield. While the result is technically decentralized
Unlike standard automaton product, synchronize L. the resulting automaton's 's alphabet is L

---

shield that enforces d², this trivial solution does not allow the agents any freedom to explore actions and optimize for expected returns.
Instead, would ideally like to synthesize maximally permissive shield; i.c. shield for which there does not exist an alternate shield that admits a strict superset of label traces. However, this is fundamentally difficult problem in the general case. We therefore present a procedure which produces a maximally permissive decentralized shield when the input centralized shield is Cartesian and unambiguous, and in all other cases produces shield which is at least as permissive as the and described in what follows.
trivial solution. The steps of our algorithm are illustrated in Figure !I
Algorithm Step of Shield Decomposition: Determining Safe Actions
Input
2: Φ = (G, (L x A), 89, , F*)
// A centralized shield where A = I A;
3: Output
4:
D:
// A set of safe individual actions for agent i Uniquely determine the next state, given the observed label
5: -
6: procedure CALCUUATESS
7:
for E ((s) do // [(s) = set of all labels which may be observed in shield state s // All legal joint actions from ( Pick arbitrary a == (a), ................................ E C(s, // Guaranteed to exist, given that E (())
8:
C(s,1) + {a Al8 (I,a)) F3)
9:
10:
Vi D: :D:(s.)) R(s,1) 1) + [C(89 ().))))))) - ((s a).
{ai}
11:
12:
for i E D do
I1 Optimization: randomly permute D at each time step
13:
for de E A; do
14:
A (a.) JED. D)(s,1) // New joint actions if a' were added to D,
if A C(s, () and UNAIIGGUOSSACTTOOS//R..... A) then
16:
(s + D.(s.l)
Ya A, R(s,))
(s, al)
18:
end if
19:
end for end for
20:
end for
22:
return E
23:
end procedure
First, for every centralized shield state, and for every label which can be observed from that state, find subset of safe joint actions which is Cartesian and unambiguous. This step works by first choosing a single safe joint action, like in the trivial solution. The algorithm then attempts add individual actions for each agent in turn. When considering given individual action, the algorithm first calculates the set of all joint actions which would be enabled if this individual action were enabled. For example, if the algorithm has previously decided that agent may take either actions a or b. then enabling agent 2's action b would require checking that both joint action candidates (a, b) and (b, b) are suitable. In this manner, the set of enabled joint actions remains Cartesian. If any joint action candidate is unsafe, or if adding any of them would cause ambiguity in the next state, then the individual action is rejected. Since the starting joint action and the order of candidate individual actions are arbitrary, this algorithm's 's output is not unique. The details of this step are further illustrated in Figure 2 and described more specifically in Algorithm I
Algorithm ! performs most of the work in this sequence of algorithms: it takes a centralized shield as input, and outputs set of safe actions for every state-label combination, well as the information necessary to determine the next state of the environment.
Algorithm 2 (in appendix) projects the actions found by the previous step into an input-output state machine for each agent, which we call transient-ser state individual shield. This structure has two categories of states: label states, which receive an observation from the environment (shown as black dots in Figure I: and action states, which show allowed actions of the agent (shown as white circles). Lastly, Algorithm D (in appendix) performs some mild post-processing so that this structure conforms to the shield interface. Additional information about these structures and algorithms can be found in Section A
5

---

(a)
Lu (0, a)
(b)
(1, L)
881, L))
L. (-)
Agent
(.,,, 8)
La, m)
Agent
L, (t,, -t)
m))
11, L2)
R(1, L2)
(,,(,,)))
(..
(2, L ...
(2, Lt)
(c)
Agent 1 posttl, L))
posttz,
Agent 2
post2,
postll,
post(3,
postts,
Init
Init L.
post(3,
postts, Lg)
post(1,
posti4, L,>
postt4, Lg)
L
post(4, Lg)
posti4, L,)
(d)
Agent
Agent 2
Li
Lg
post(2,
postt2, L,)
Ls.
post(1,
La
post(1, L2)
past(3, L.)
post(3, L,)
init
Lax
m
past(3,
init
L1,
Lg on
post(3,
Lg
post(4,
post(4, L
L3.
post(l, L.)
post(1, Le)
post(4,
postt4, Lz)
Figure 1: An overview of algorithm sequence, in hypothetical environment where TD 18, t,, -) L2, La} E L. (a) The input centralized shield, showing =(1)= ((2) [L ((3) (L2, Lg), C(4) (L,, L3), well several transitions.
(1.2), A = A
(b) The output of Algorithm D DI... which denotes the allowed actions for each agent, and R, which maps labels seen in the next state the state number. Here, for shield state and label L,, is safe for agent 1 to take actions X or t,, while agent 2 may take X or >. (c) The output of Al- gorithm 2 transient-state individual shields for each agent, constructed using Dı... and R. (d) The output of Algorithm 3 individual shields, constructed by transforming the transient-ster state individual shields. These can be used by agents in communication-free environments to ensure safety.
If the centralized shield given as input to this sequence of algorithms enforces a given specifica- tion, the decentralized shield will also enforce that specification. This important safety property is formalized the following theorem, and proven in Section B.2 of the appendix:
Given MMDP M = (D, tralized shield d for M, the result of Algorithms ! 2 and 3 is decentralized shield for M which enforces da.
Theorem
R. by) where Vs (s) A. and a cen-
As mentioned previously, given an input centralized shield which is already both unambiguous and Cartesian, the resulting decentralized shield will be maximally permissive, shield is trivially unambiguous if each label only appears in single state; many safety specifications, especially in fully observable environments, are enforceable by such a shield. This includes all stateless shields- shields where F = { ). For input shields which are non non-Carterr Cartesian, our algorithm gives one agent "right of way": an agent with higher priority cannot put another agent a situation for which there are no safe actions, but the lower-priority agent must otherwise accommodate any potential actions that the higher-priority agent may take. centralized shield usually Cartesian in states where such "right of way" is not necessary, i.c. when agents not in contention with each other.

---

(b)
(c)
91,, L2)
31 L2
911,
S81 LD
9X1, L.)
S11 L)
Agent
Agent
Agent
O2
3
2 3
X
2 3 X
@
2
3
X
Agant
3
Agent 2
4 3 2
Agonn
4
3
2
4
3 3
3
3
4
(d)
(e)
(
(1,, L2)
@(1, 4
@11, L,)
@81, L
20, L.)
R1,, L)
Agent
Agent
Agent
@
2
X 2
2
X
2 3
X 2
Agunt
4
Agunt
4
3
Ageit
4
3
3 Next Staces
3
4
3
3
4
Nost States
Next States
Figure 2: detailed view Algorithm D which finds Cartesian set safe, unambiguous actions. The shield from Figure i used input. This figure focuses the process of finding safe actions for state 1, after L1 has been observed. The 3x3 grid squares represents the joint actions allowed by the centralized shield for given state-label pair. The 3xl rectangles the top and left represent the individual actions which the decentralized shield will allow. Green with a check mark represents that the individual action is allowed, red with an "X" represents that the action is not allowed, and yellow with "?" represents that the action is under consideration. The mapping from diamonds to circles represents knowledge of what the next joint action-(O). - chosen arbitrarily. R reflects that the agents see I next, state comes next. (b) The agent considers adding agent 1, action <-; it is safe this action is allowed. (c) The algorithm considers agent 1, action >. It may lead to an unsafe state, so this individual action is rejected. (d) The algorithm considers agent action f-, This would add two joint actions. Adding state 4 as a possible next state means that the states are ambiguous if L1 or La is observed, so is rejected. (e) The algorithm considers agent action -. Both joint actions which this would add
will be, given the shield. (a) single safe
safe, so it is allowed. We don't it consider the effects of action (++-,), as agent 1 is prevented from selecting >. (f) The finished result, used for the next step of the shield decentralization procedure.
No matter what, the decentralized shield which our algorithm generates will always allow at least one safe joint action, in manner similar the trivial solution described above. practice (c.f. Section C). we find that the resulting decentralized shield tends to allow large range of joint actions, even on input shields which are not fully unambiguous or Cartesian.
Experiments
We aim to show with our experiments that, as predicted by Theorem I decentralized shields cor- rectly prevent the agents from taking unsafe actions, while an equivalent unshielded agent may take unsafe actions in the same situation. Furthermore, we hypothesize that agents which use our decen- tralized shielding method perform comparably agents which use a centralized shield.
6.1 The Gridworld Collision Domain
We adapt the gridworld maps from Melo and Veloso 16 to test our method. These maps, shown in Figure 3 have previously been used to test multiagent shielding, with an assumption of instan- taneous local communication [TC] Each agent has five actions available: movement the four cardinal directions, or a no-op. If all agents reach their goal positions, they each receive a +100 reward. Any agents which hit wall receive -10 reward. The safety specification that collision between two agents should never occur (including agents crossing over each other). In an unshielded

---

MIT
ISR
SUNY
Pentagon
The four gridworld environments adapted from Melo and Veloso 16. starts in the red and green squares; the goal is to switch positions.
Figure 3:
One agent each
environment, if an agent violates this specification, all agents receive -30 reward. Agents receive -1 reward all other time steps. We use the four maps "MIT." "ISR," " "SUNY," and "Pentagon," both with and without randomized start positions. These maps range in size from 8x10 to 10x23.
We synthesized centralized shield which avoids collisions, using reactive synthesis tool 9 Note that this shield is shared across all four environments- is a coarse abstraction which operates solely relative agent positions, ensuring collision-fre behavior in any gridworld with similar dynamics. The synthesis tool outputs shield with many redundant states; we remove duplicate and unreachable states. In the resulting shield, each environment label only appears in single state, so the resulting shield is trivially unambiguous (though is not fully Cartesian).
We then utilized the procedure described in Section to to obtain decentralized shield which works for all our gridworld environments. The resulting individual shields are more conservative when the agents near each other, ensuring that more than one agent moves into potentially con- tested area. Centralized shield synthesis took approximately five minutes on a M1 Macbook Pro, and our decentralization algorithm ran in under 30 seconds.
We analyzed the structure of the shields to determine how much the decentralization procedure restricts the set of actions available. With the centralized shield, there are an average of 23.30 safe joint actions available to the agents for a given shield state. Using the trivial solution from Section 5 every shield state would only have joint action available. Our decentralization algorithm produces a shield where there are an average of 22.07 joint actions available- not much more restrictive than the centralized shield.
We trained independent tabular Q-learning agents using c-greedy exploration, with linear an- nealing schedule from 1 to 0.05. The discount factor is 0.9. Agents were trained with centralized shield, a decentralized shield, and with no shield. When an agent attempts to take an action which is not allowed by the shield, the penalty reward for the synthetic transition T = -10. These hyperparameters were chosen to closely match the parameters from 100, where possible.
Agents were trained for 2.5 million timesteps each, using 10 different random seeds for each config- uration. Each individual run took approximately minutes on a single core of Intel server CPU; we trained 240 agents in total. This was sufficient for convergence in all variations. Results are shown with both fixed and random starting positions Table I Extended tables and training curves are listed in the appendix.
As guaranteed by Theorem 1 this experiment shows that, because the centralized shield protects the agents from taking such unsafe actions, the agents which use a decentralized shield are also prevented from taking unsafe actions. The experiment also reveals that neither shielding method consistently performs better than the other method, as the highest-performin agent is generally within the margin of error. Therefore, our decentralized shielding approach allows safe, high-quality learning during training and execution in environments without communication. The training curves (Figure in the appendix) tell the same story- no method works significantly faster during training.
6.2 The Relative Particle Momentum Domain
One advantage of formally synthesizing a shield, rather than naively blocking actions which directly lead to an unsafe state, that a shielded agent can avoid states which do not immediately violate specification, but where all future paths end in unsafe state. This can occur in domains with momentum; if a car is driving towards a cliff, must slow down well before it reaches the edge. Therefore, would like to evaluate agents which use our shield in momentum-based environments.

---

Table I: Agent performance after 2.5 million environment steps, using the same shield for training and testing. Results show average evaluation return and standard error over 10 seeds, as well as average total violations over 100 testing episodes in parentheses. Note that centralized shielding is only for comparison; in a no-communication environment, this method would not be feasible.
Start Type
Map Name
Centralized
Decentralized
No Shield
ISR
90.4 + 0.6 (0)
8 (0)
90.0 + 0.6 (12.3)
MIT
72.0 0.8 (0)
7.5 7.36 (0)
Fixed
Pentagon SUNY
89.0 (0)
82.0
0.3 (4.8)
8.4 (0)
8. 0.66
(0)
ISR
7..6
76.1
1.46
MIT
0.2 (0)
8. 0.2
(0.4)
Random
Pentagon
88.4 0.5 (0)
0. 3.5
SUNY
78.1 2.1+0.4 0.4
73.1 1.7
77.3 + 0.4
Table 2: Individual DQN Agent Performance in the Particle- Momentum domain.
Observability
Start Type
Centralized
Decentralized
No Shield
Fixed
70,9 + 5.8 (0)
82.8 + 2.3 (0)
67.8 + 3.0 (34.3)
Partial
Random
70.8 + 1.7 (0)
80.5 + (.)
33.2 2.4 (115.7)
Fixed
91.6 + 0.0 (0)
91.6 + 0.0
90.7 + 0.2 (3.0)
Full
Random
94.6 + 0.1 (0)
94.6 0.1 (0)
93.7 0.2 (2.8)
We introduce an environment as follows. There are two agents, representing particles on a dis- cretized grid. Agent I begins 9 units above, and 9 units to the left of agent 2, with both agents at rest. Both agents obtain a reward of 100 when agent I gets to the position 9 units to the right of and below agent 2. If the agents get more than 10 units apart in any individual dimension, or cross with each other, it is considered a safety violation (and the agents get a reward of -30). Otherwise, all agents get reward of -1 at each time step. Each agent move in any of the four cardinal directions, or do nothing. Additionally, agents have momentunı; an agent's 's action is added its previous movement obtain its next movement in the environment. The relative velocity is capped at 2 units per time step in each direction. In the fully observable variant of this environment, both agents observe the relative positions and relative velocities. In the partially observable version, the agents only observe the relative positions.
collide
We synthesized shields which only use the relative positions of the agents the label set; such shields can be utilized in either variant of the environment. Using the same structure analysis as in Section 6.1 calculated that the centralized shield allows average of 21.67 actions, while the decentralized shield allows an average of 20.81 actions.
To show that our decentralized shielding algorithm is also effective regardless of the underlying reinforcement learning algorithm used by the agent, we trained reactive DQN agents to solve this task [17]. Full hyperparameters for this agent are located in the appendix. 10 random seeds were used the fully observable case, and 50 seeds were used in the partially observable version of the environment. Each run took approximately 8 hours using 3 threads on server CPU.
The results are shown in Table Under full observability, we reach similar conclusions as in the gridworid-collissonn domain: the agents protected by centralized and decentralized shields both achieve comparable performance. As guaranteed by Theorem [ the agent which uses the decen- tralized shield is safe as the agent which uses a centralized shield. This is further emphasized under the partially observable variant of the environment, where the unshielded reactive agents do not have sufficient information about the environment, and thus behave in a wildly unsafe manner. In contrast, the shields are able infer the current momentum based on the incremental changes in relative agent positions, Icading them to never take an unsafe action.

---

7 Broader Impact and Limitations
We believe that the algorithms presented this work represent progress towards the more general goal of safe reinforcement learning. Like most provably correct methods, shielding suffers from scalability issues such as the well-known state explosion problem B3. For example, prior to de- duplication and removal of unreachable states, the shield which we synthesized for the gridworld experiments contained 71 71130 states. The particle environment's 's shield, including momentum infor- mation, contained 170348 states. The size of centralized shield tends to scale exponentially with the number of agents. Our decentralization algorithm takes linear time with respect to the number of state-label pairs in the input shield, so we well positioned to take advantage of methods which synthesize a centralized shield without such state explosion.
Additionally, obtaining an environment abstraction is difficult-we wrote several iterations of our abstractions, each containing subtle but serious bugs, before finally obtaining precise and accurate models of the environments. If our algorithm is given inaccurate centralized shield, the decentral- ized shield which the algorithm outputs cannot be expected to perform well. We therefore caution abstraction which may not accurately represent the environment.
against overreliance
Furthermore, there exist some environments where it is difficult, or even impossible, to determine a shared label set. For example, an environment with highly asymmetric observations would not satisfy the assumptions of the shielding framework we use. However, there may still be sufficient information to ensure safety in these challenging environments; we are working on developing meth- ods to synthesize a decentralized shield without a shared label set.
As with any advance in machine learning, it may be possible to use our method to safely train an agent perform an unethical task. However, we hope that as whole, a process for safe reinforce- ment learning training and execution will reduce potential societal harms resulting from AL.
8 Conclusion & Future Work
Our experiments show that the shield decomposition method described in this paper results shields that are safe and do not require any communication between agents. Furthermore, agents which are trained and evaluated with a decentralized shield perform comparably to agents which are trained and evaluated with a centralized shield, or without any shield.
We are currently working to extend our results in several ways. First, we are implementing ad- ditional agents and training schemes, including individual Deep Q Networks with convolutional layers [17], and Centralized-Criite Critic Decentralized-Acte
methods M. Second, we are investigat- ing methods to scale our shield decomposition method to the more complicated shields and safety specifications necessary describe complex continuous or partially-obbeeraabee environments. Our algorithm makes a number of arbitrary choices which do not impact safety, but which could affect shield performance. It may be useful define additional metries for shield performance and per- missiveness that do not necessarily involve training and testing agents over thousands of episodes, and to use these metrics to improve the decisions that our algorithm makes. We would like to even- tually develop method which obtains maximally permissive decentralized shield, no matter what properties hold for the input shield. Finally, although similar problems in formal methods are unde- cidable [18 21I, we would like to explore heuristic methods for direct decentralized shield search and synthesis.
Acknowledgments and Disclosure of F Funding
We would like thank Ingy ElSayed-Aly for her assistance with shield synthesis. We would also like to thank the reviewers for their thoughtful comments and suggestions.
This work has been supported by NSF SaTC Award CNS-1801546, NSF CAREER Award IIS- 2044993, and Army Research Office Award INF2000025 This work was completed in part using the Discovery cluster, supported by Northeastem University's Research Computing team.
10

---

References
[1] ALSHIEKH, M., BLOEM, R., EHLERS, R., KÖNIGHOFER, B., NIEKUM, S., AND TOPCU,
U. Safe reinforcement learning via shielding, 2017.
[2] AMODEI, D., OLAII, C., STEINHARDD, J., CURISTIANO, P., SCHIULMAN, J., AND MANÉ,
D. Concrete problems
safery, 2016.
[3] BATER, C., KATOEN, J., AND LARSEN, K. Principles of Model Checking. The MIT Press. MIT Press, 2008.
[4] BASTANI, O., PU, Y., AND SOLAR-LEZAMA, A. Verifiable reinforcement learning via policy extraction, 2019.
[5] BENVENISTE, A., CAILLAUD, B., NICKOVIC, D., PASSERONE, R., RACLET, REINKE-
MEIER, P., SANGIOVANNI- CIVVANNIVIINNNTELLL, A. L., DAMM, W., HENZINGER, T. A., AND
LARSEN, K. G. Contracts for system design. Found. Trends Electron. Des. Autom. 12, 2-3 (2018), 124-400.
[6] BLOEM, R., KOENIGHOFER, B., KOENIGHOFER, R., AND WANG, C. Shield synthesis: Runtime enforcement for reactive systems, 2015.
[7] CARR, S., JANSEN, N., JUNGES, S., AND TOPCU, U. Safe reinforcement learning via shield- ing for POMDPs, 2022.
[8] DALAL, G., DVUOTHAM, K., VECERIK, M., HESTER, T., PADURARU, C., AND TASSA, Y. Safe exploration in continuous action spaces, 2018.
[9] EHLERS, R., AND RAMAN, V. Slugs: Extensible GR(I) synthesis. Computer Aided Verifi- cation (2016), S. Chaudhuri and A. Farzan, Eds., Lecture Notes in Computer Science, Springer International Publishing, p. 333-339.
[10] ELSAAYD--ALY, I., BHARADWAI, S., AMATO, C., EHLERS, R., TOPCU, U., AND FENG, L., Safe multi-agent reinforcement learning via shielding. In Proceedings the 20th International Conference on Autonomous Agents and MultiAgent Systems (Richland, SC, 2021), AAMAS '21, International Foundation for Autonomous Agents and Multiagent Systems, p. 483-491.
[11] FOERSTER, J., FARQUHAR, G., AFOURAS, T., NARDELLI, N., AND WHITESON, Coun- terfactual multi-agent policy gradients, 2017.
[12] GALLAY, F., AND FALCONE, Y. Decentralized LTL enforcement. Electronic Proceedings in Theoretical Computer Science 346 (sep 2021), 135-151.
[13] GLOROT, X., BORDES, A., AND BENGIO, Y. Deep sparse rectifier neural networks. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (Fort Lauderdale, FL, USA, 11-13 Apr 2011), G. Gordon, D. Dunson, and M. Dudik, Eds., vol. 15 of Proceedings of Machine Learning Research, PMLR, pp. 315-323.
[14] IVANOV, R., WEIMER J., ALUR, R., PAPPAS, G. J., AND LEE, I. Verisig: verifying safety properties of hybrid systems with neural network controllers, 2018.
[15] KÖNIGHOPER, B., RUDOLF, J., PALMISANO, A., TAPPLER, M., AND BLOEM, R. Online shielding for reinforcement learning. Innovations in Systems and Software Engineering (2022), 1-16.
[16] MELO, S., AND VELOSO, M. Learning of coordination: Exploiting sparse interactions in multiagent systems. In Proceedings of The 8th International Conference on Autonomons Agents and Multiagent Systems Volume (Richland, SC, 2009), AAMAS '09, International Foundation for Autonomous Agents and Multiagent Systems, p. 773-780.
[17) MNTH, V., KAVUKCUGGLIU, K., SILVER, D., GRAVES, A., ANTONOGLOU, I., WIERSTRA, D., AND RIEDMILLER, M. Playing Atari with deep reinforcement learning, 2013.

---

[18] PNUELI, A., AND ROSNER, R. Distributed reactive systems hard to synthesize. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science (1990), pp. 746-757 vol.2.
[19] SCHAUL, T., QUAN, J., ANTONOGLOU, I,, AND SILVER, D. Prioritized experience replay, 2015.
[20] SILVER, D., SCHRITTWESSE, J., SIMONYAN, K., ANTONOGLOU, I., HUANG, A., GUEZ, A., HUBERT, T., BAKER, L., LAI, M., BOLTON, A., CHEN, Y., LILLICRAP, T., HUI, F., SIFRE, L., VAN DEN DRIESSCHE, G., GRAEPEL, T., AND HASSABIS. D. Mastering the game of Go without human knowledge. Nature 550, 7676 (Oct. 2017), 354-359.
[21] TRIPAKIS, S. Undecidable problems of decentralized observation and control on regular lan- guages. Information Processing Letters 90, 1 (Apr. 2004), 21-28.
[22] VAN HASSELT, H., GUEZ, A., AND SILVER, D. Deep reinforcement learning with double Q-learning 2015.
[23] ZHANG, Y., KIM, K., AND FAINEKOS, G. DisCoF: Cooperative pathfinding in distributed systems with limited sensing and communication range. In Distributed Autonomous Robotic Systems (Tokyo, 2016), N.-Y. Chong and Y.-J. Cho, Eds., Springer Japan, pp. 325-340
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the pa- per's contributions and scope? [Yes] We present a method to decentralize a central- ized shield, and verify experimentally that this method does not significantly affect performance in the gridworld domain.
(b) Did you describe the limitations of your work? [Yes] See Section f
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We dis- cuss the topic in Section /
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Sections 5n discuss the relevant assumptions.
(b) Did you include complete proofs of all theoretical results? [Yes] See appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We attach our code as supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6 and the appendix.
(c) Did you report error bars (e.g., with respect the random seed after running experi-
ments multiple times)? [Yes] The tables and figures are all reflective of this.
(d) Did you include the total amount of compute and the type of resources used (c.g., type GPUs, internal cluster, or cloud provider)? [Yes] The total compute time mentioned in Section O the provider of the computation power is mentioned in the acknowledgements section.
4. If you using existing assets (c.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 6. where we discuss the origins of the environment maps.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
12

---

(d) Did you discuss whether and how consent obtained from people whose data you're re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "a4OINaTdHuj", "reviewer": "Reviewer_ZmUf", "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. ", "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. \n\n\n\nIs there a proof the resulting decentralized shield is indeed maximally permissive? ", "limitations": "Adequately addressed. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nThe 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. \n\nFurthermore, 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Zpkg0WblbZj", "reviewer": "Reviewer_iC7K", "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.\n\nExisting 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.\n\nThis 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.", "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?\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The work is certainly relevant. Distributed safe reinforcement learning is an important topic with a broad array of useful applications.\n\n- The case studies demonstrate feasibility of the approach.\n\n- The soundness theorem seems to be correct.\n\n- 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.\n\n- I have a few open questions, some of which may be straightforward for the authors to address in the camera-ready version.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3wlADu2UURC", "reviewer": "Reviewer_4UYh", "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. \nThe 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. \n\nThe 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. \n", "questions": "1. What is the example problem in figure 1 and 2? What are the red and green square, what are the circles? \n2. 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?\n3. Could you clarify whether or not each agent need to observe the joint state?\n4. What is the benefit of algorithm 2 and 3 over algorithm 1? This was not obvious from reading the paper.\n", "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. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The grade has been updated after clarification by the author on the figure illustrating how the proposed algorithm works. \n\nThe 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.\n\nOverall 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. \n\nThe 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. \n\n 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. \n \nAn 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. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept