Centralized and Factored MARL Shielding

Context

ElSayed-Aly2021 - Safe Multi-Agent Reinforcement Learning via Shielding extends LTL-based Shielding from single-agent RL to MARL. The key technical move is to treat the agents’ proposed joint action as the controllable move in a safety game, then synthesize either one centralized Mealy-machine shield or several factored shields with boundary coordination.

Formal Statement

Let the MARL problem be a Markov game

$$M=(N,S,\{A_i{\}}_{i\in N},P,\{R_i{\}}_{i\in N},\gamma )$$

with joint action space A=A_1 x ... x A_n. Let f:S -> L map concrete joint states to the observation alphabet used for safety reasoning.

Centralized shielding assumes:

• a coarse environment abstraction A_e=(Q_e,q_e0,L x A,delta_e,F_e);
• a safety automaton A_s=(Q_s,q_s0,L x A,delta_s,F_s) obtained from an LTL safety specification;
• a two-player safety game with states G=Q_e x Q_s, safe states F=Q_e x F_s, Player 1 alphabet L, and Player 2 alphabet A.

The game transition is:

$$delt{a}_g((q_e,q_s),l,a)=(delt{a}_e(q_e,(l,a)),delt{a}_s(q_s,(l,a))).$$

If W subseteq F is the winning region, the centralized shield is a Mealy machine whose output rule is:

$$lambda(g,(l,a))=\{\begin{array}{ll}a,& delt{a}_g(g,l,a)\in W,\\ \bar{a},& delt{a}_g(g,l,a)\notin W,\end{array}$$

where \bar a is a safe joint action with delta_g(g,l,\bar a) in W that differs from a in the minimum number of agents’ components.

Factored shielding replaces one global game with multiple shields over state factors. Each shield monitors a subset of agents at a step, handles boundary-crossing actions as leave/join requests, and a coordination phase permits a crossing only when both sides accept; otherwise the agent receives a default safe action.

Derivation / Construction

• Translate the LTL safety specification into a deterministic safety automaton.
• Build or supply a coarse environment abstraction over observations and joint actions.
• Form the product safety game between observations and joint actions.
• Compute the winning region.
• Construct the centralized Mealy-machine shield so safe proposed actions are forwarded and unsafe ones are replaced with minimal per-agent changes.
• For the factored variant, choose state-space factors, synthesize one shield per factor, map agents to relevant shields at each step, and rename boundary moves as leave/join.
• Run each factored shield on its local tuple of related agents, then coordinate cross-factor actions. If leave and join both succeed, keep the original action; otherwise substitute the default safe action.

Implications

• The guarantee is runtime safety during learning: unsafe actions are corrected before the environment executes them.
• The construction is MARL-algorithm agnostic because it wraps the action interface rather than changing the learner internals.
• The centralized variant has the cleanest minimal-interference rule but inherits the exponential cost of the joint state/action space.
• The factored variant is more scalable, but its safety and usefulness depend on a sound factorization and can become conservative near factor boundaries.
• This differs from Distributed Shield Synthesis, where local shields are composed with assume-guarantee obligations and no online join/leave coordination is needed.

Links

• Source: ElSayed-Aly2021 - Safe Multi-Agent Reinforcement Learning via Shielding
• Concepts: Shielding, Safe Reinforcement Learning, Safe Multi-Agent Reinforcement Learning, Linear Temporal Logic