Paper deep dive
Decentralized Safe Multi-Agent Reinforcement Learning via Predictive Shielding
Yacine El Yamani, Hanna Krasowski, Elena Vanneaux
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 9/13/2026, 5:36:01 AM
Summary
This paper proposes a decentralized framework for safe multi-agent reinforcement learning (MARL) that integrates predictive shielding with model-based finite horizon Q-learning. The approach allows independently trained agents to adapt their policies during deployment in shared environments without communication, ensuring safety against both static and dynamic obstacles while mitigating livelocks through a stochastic conflict resolution protocol.
Entities (8)
Relation Signals (7)
Yacine El Yamani → affiliatedwith → ENSTA
confidence 98% · Yacine El Yamani ... Address: ENSTA, IP Paris
Hanna Krasowski → affiliatedwith → UC Berkeley
confidence 98% · Hanna Krasowski ... Address: UC Berkeley, USA
Conflict Resolution Protocol → mitigates → livelocks
confidence 95% · to mitigate livelocks in symmetric scenarios, we introduce a communication-free protocol for conflict resolution
Predictive Shielding → uses → MB-FH-IQL
confidence 95% · we propose a decentralized framework that integrates predictive shielding with model-based finite horizon Q-learning.
MB-FH-IQL → isbasedon → Independent Q-Learning
confidence 92% · Algorithm 1 implements our Model-Based Finite-Horizon Independent Q-Learning (MB-FH-IQL). Unlike standard IQL...
Predictive Shielding → handles → dynamic obstacles
confidence 90% · we propose to reformulate... as finite-horizon optimization problem... for dynamic obstacles
Predictive Shielding → handles → static safety constraints
confidence 90% · When the agent’s position leaves the region... the simulated process reaches the terminal state... solve the simulated game... for static safety constraints
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Environments are increasingly populated by multiple robots performing independent tasks with limited prior knowledge of each other. Deploying such multi-agent systems presents significant challenges. Specifically, shifts in deployment states compared to training data can lead to poor policy performance and compromised safety. While safety shields exist to mitigate these risks, they are typically reactive, which degrades performance near unseen obstacles,and centralized, limiting their scalability. To address this, we propose a decentralized framework that integrates predictive shielding with model-based finite horizon Q-learning. This approach allows agents to safely adapt their pre-trained policies during deployment. Furthermore, to mitigate livelocks in symmetric scenarios, we introduce a communication- free protocol for conflict resolution
Tags
Links
- Source: https://arxiv.org/abs/2609.07618v1
- Canonical: https://arxiv.org/abs/2609.07618v1
Trouble viewing inline? Open PDF directly →
Full Text
42,702 characters extracted from source content.
Expand or collapse full text
Decentralized Safe Multi-Agent Reinforcement Learning via Predictive Shielding Yacine El Yamani Hanna Krasowski Elena Vanneaux Address: ENSTA, IP Paris, Palaiseau, France (email: yacine.elyamani, elena.vanneaux@ensta.fr ) Address: UC Berkeley, USA (e-mail: krasowski@berkeley.edu) Abstract Environments are increasingly populated by multiple robots performing independent tasks with limited prior knowledge of each other. Deploying such multi-agent systems presents significant challenges. Specifically, shifts in deployment states compared to training data can lead to poor policy performance and compromised safety. While safety shields exist to mitigate these risks, they are typically reactive, which degrades performance near unseen obstacles,and centralized, limiting their scalability. To address this, we propose a decentralized framework that integrates predictive shielding with model-based finite horizon Q-learning. This approach allows agents to safely adapt their pre-trained policies during deployment. Furthermore, to mitigate livelocks in symmetric scenarios, we introduce a communication-free protocol for conflict resolution11endnote: 1 Source code: https://github.com/YacineEY/Decentralized-Safe-Multi-Agent-Reinforcement-Learning-via-Predictive-Shielding.git. keywords Multi-agent systems, Reinforcement learning, Autonomous navigation, Safety-critical systems. 1 Introduction In recent years, it has become increasingly common for multiple robots, often based on reinforcement learning (RL) agents, with distinct functionalities to operate simultaneously within a shared environment. For example, delivery robots transport packages and service robots perform continuous cleaning - all operating independently while sharing the same physical space (Oroojlooy and Hajinezhad, 2022; Guo and Dimarogonas, 2015). Unlike most multi-agent RL approaches, which assume joint training and shared objectives (Tang et al., 2025; Oroojlooy and Hajinezhad, 2022), this paper considers agents pretrained separately for individual tasks and later deployed together. Directly executing the pretrained policies may lead to collisions between agents. To ensure safety during deployment,safety shields are commonly used (Garg et al., 2024). In contrast to shields designed for joint multi-agent systems (ElSayed-Aly et al., 2021; Sheng et al., 2024), we assume that every robot is incorporated with an individual shield that replaces the unsafe actions proposed by the agent with a provably safe backup policy (Krasowski et al., 2023). The individual shields are then composed together using the assume–guarantee paradigm to ensure safety for the overall multi-agent system (Brorholt et al., 2025; Carr et al., 2025). Assume-guarantee shields design does not require explicit communication between agents (Xiao et al., 2023), but they are commonly based on simple safety rules (e.g., stop to avoid collision). The composition of reactive shields with trivial backup policies can significantly degrade the task-related performance of the agents (ElSayed-Aly et al., 2021). To address this limitation, we propose to equip each agent with a model-based predictive shield (Jin et al., 2025a; Banerjee et al., 2024). Unlike minimal interference shields (ElSayed-Aly et al., 2021) that modify the policy only when unsafe action is about to be taken on the next step, a model predictive shield uses the environment model learned during training and local sensing data to optimize the behavior of the agent for a few steps ahead. In contrast to existing work (Jin et al., 2025a; Banerjee et al., 2024), our shield differentiates between static and dynamic obstacles and adapts infinite-horizon RL from (Jin et al., 2025a) for static environments and finite-horizon RL for dynamic constraints (Banerjee et al., 2024). The proposed predictive shield aims to adapt to unseen constraints and minimize inter-agent interference through predictive optimization. However, agents may still enter a livelock, for example when symmetric actions are taken. Inspired by Grover et al. (2023); Chandra et al. (2025), we introduce a novel communication-free conflict resolution protocol to address this issue. The protocol randomly decides whether an agent should aggressively follow its desired path or yield to the other agent. The main contributions of this paper are the following: • We propose a decentralized model predictive shield for non-communicating heterogeneous agents operating in shared environments. Assuming that every agent equipped with a trivial backup policy it improves the total reward of the group, defined as a sum of the rewards of every agent, while preserving the hard safety guarantees. • We introduce a communication-free stochastic conflict resolution protocol for resolving deadlocks in symmetric multi-agent configurations. • We demonstrate through experiments that the proposed method achieves scalability, low online computational cost, and robust performance in dense multi-agent environments. 2 Preliminaries Multi-Agent Reinforcement Learning. A single RL agent is commonly modeled as a Markov Decision Process (MDP). Dec-POMDPs extend the traditional MDP framework to cooperative multi-agent settings, where multiple agents make decisions under uncertainty and partial observability (Tan, 1993). Definition 1 A Dec-POMDP is a tuple =(ℐ,,i,T,r,Ωi,γ),DP=(I,S,\A_i\,T,r,\ _i\,γ), where ℐ=1,2,…,NI=\1,2,…,N\ is the set of agents, S is the state space, iA_i is the action space of agent i with =×i∈ℐiA=×_i A_i the joint action space, T:×→T ×A is a deterministic transition function, r:×→ℝr ×A is the joint reward function, Ωi _i is the set of observations oi(s)o_i(s) available to agent i with Ω=×i∈ℐΩi =×_i _i the joint observation space, and γ∈[0,1)γ∈[0,1) is the discount factor. :×Ω→[0,1]O ×A× →[0,1] is the observation function with (s′,a,o)=ℙ(ot+1=o∣st+1=s′,at=a)O(s ,a,o)=P(o_t+1=o s_t+1=s ,a_t=a) that gives probability of receiving observation o when the system is actually in state s and the joint action is aa The objective is to find a joint policy π=(π1,…,πn)π=( _1,…, _n) that maximizes the expected discounted return [∑t=0∞γtr(st,at)]E [ _t=0^∞γ^tr(s_t,a_t) ]. Exactly solving a Dec-POMDP is NEXP-complete, even for finite horizons (Bernstein et al., 2000) problems. One of the approaches to find an approximate solution is IQL (Tan, 1993; Jin et al., 2025b), where each agent i maintains its own Qi(m)(oi(s),ai)Q^(m)_i(o_i(s),a_i)-table. All agents take actions simultaneously, using ε -greedy policy w.r.t. Qi(m)(oi(s),ai)Q^(m)_i(o_i(s),a_i), and then update Qi(m)(oi(s),ai)Q^(m)_i(o_i(s),a_i) according to the rule: Qi(m)(oi(st),ai,t)←Qi(m)(oi(st),ai,t)+α[ri,t(oi(st),ai,t)+γmaxai′∈iQi(m)(oi(st+1),ai′)−Qi(m)(oi(st),ai,t)].Q_i^(m)(o_i(s_t),a_i,t)← Q_i^(m)(o_i(s_t),a_i,t)\\ +α [r_i,t(o_i(s_t),a_i,t)+\\ γ _a_i _iQ_i^(m)(o_i(s_t+1),a_i )-Q_i^(m)(o_i(s_t),a_i,t) ]. (1) The individual rewards are chosen to be such that r(st,at)=∑i∈ℐri,t(oi(st),ai,t).r(s_t,a_t)= _i r_i,t(o_i(s_t),a_i,t). Independent Q-learning does not require coordination or communication between the agents, it scales well with respect to the number of agents, does not always converge. Provably Safe Multi-Agent Reinforcement Learning. A common way to make RL controllers suitable for safety-critical applications is to pair them with post-posed safety shields (ElSayed-Aly et al., 2021). These shields accept safe actions proposed by the agents and replace unsafe ones with a precomputed, provably safe, backup policy πbackup _backup. Definition 2 A safety specification is a sequence of state constraints that must not be violated during execution of Dec-POMDP, i.e. st∈safe⊆,∀t∈ℤ+s_t ^safe ,\,∀ t _+. Let us assume that every agent equipped with a monitoring system φi:Ωi×i→0,1 _i _i×A_i→\0,1\ verifying if the action aia_i is safe (φi(oi(s),ai)=1 _i(o_i(s),a_i)=1) or unsafe (φi(oi(s),ai)=0 _i(o_i(s),a_i)=0) in a state s and a shield ϕi:Ωi×i→i _i _i×A_i _i such that for all ai∈ia_i _i ϕi(oi(s),ai)=ai φi(oi(s),ai)=1 πbackup(oi(s))φi(oi(s),ai)=0 _i(o_i(s),a_i)= \ aligned &a_i& $ _i(o_i(s),a_i)=1$ \\ & _backup(o_i(s))& $ _i(o_i(s),a_i)=0$\\ aligned . (2) We assume that φi(oi(s),πbackup(oi(s)))=1 _i(o_i(s), _backup(o_i(s)))=1 for all s∈s . Definition 3 Let us define a sequence of sets t=⋃s∈t−1⋃a∈T(s,ϕ1(o1(s),a1),…ϕn(on(s),an))W_t= _s _t-1 _a T (s,\ _1(o_1(s),a_1),… _n(o_n(s),a_n)\ ) (3) A decentralized post-posed shield ϕ=ϕi,i∈ℐφ=\ _i\,i ensures safety for a winning region 0⊆safeW_0 ^safe if and only if t⊆safeW_t ^safe, ∀t∈ℤ+∀ t _+. Let us remark that in Definition 1 we assume the transition relation to be a deterministic function, in contrast to the more classical definition when the transition relation is the probability that action a in a state s at time t will lead to state s′s at time t+1t+1. We do it to ease the explanation and analysis of the proposed ideas. However, our approach could be extended to probabilistic settings, following the ideas from (Li and Bastani, 2020). 3 Problem Statement Let us consider a multi-robot system composed of N agents: ℐ=1,…,N.I=\1,…,N\. (4) Training Phase. Let us assume that every agent is trained independently to solve its task in the environment where no other agents are present. Every agent i∈ℐi is modeled as an MDP i=(Pos×~i,i,Ti,ri,γi)P_i=(Pos× S_i,A_i,T_i,r_i, _i), where PosPos is a set of all possible positions of a robot in the environment, and we suppose that this set is the same for all the agents. Hence, every state si∈Si=Pos×S~is_i∈ S_i=Pos× S_i can be decomposed into two components si=(spos,i,s~i)s_i=(s_pos,i, s_i), where spos,is_pos,i represents a position of a robot in the environment, and s~i s_i represents other task-related features. Note that since in this work the position space is where conflicts between agents arise, this subspace is relevant for checking safety. However, for the method of the paper it can be viewed as any space in which the conflict potentially arises. We also assume that iS_i and iA_i are finite and discrete. Every agent is trained to optimize its own cumulative reward πi∑t=0∞γtri,t(si,t,ai,t).E_ _i _t=0^∞γ^tr_i,t(s_i,t,a_i,t). During the training, each agent learns 1. an optimal value-action function QitrQ_i^tr and the corresponding optimal policy πitr(si)=argmaxai∈AiQitr(si,ai) _i^tr(s_i)= _a_i∈ A_iQ_i^tr(s_i,a_i). 2. a sample-based model ℳi=(si,ai,ri,si′)M_i=\(s_i,a_i,r_i,s_i )\ which stores the transitions of the agent during training. Deployment Phase. At deployment, all N agents operate simultaneously in a shared environment with joint state and action spaces =×i∈ℐi,=×i∈ℐiS=×_i S_i,\ A=×_i A_i (5) We assume no communication between agents, so each agent treats the others as part of the environment. Agent i observes its own state and partial observations of nearby agents within sensing range ρi _i. The observation function is oi(s)=si∪j:|spos,i−spos,j|≤ρio(i,j),o_i(s)=s_i _j:|s_pos,i-s_pos,j|≤ _io(i,j), (6) where o(i,j)o(i,j) always includes the position of agent j. Due to partial observability and the absence of communication, deployment is a Dec-POMDP with transition function T(s,a)=(T1(s1,a1),…,Tn(sn,an)).T(s,a)=(T_1(s_1,a_1),…,T_n(s_n,a_n)). (7) We assume the transition functions TiT_i are unchanged between training and deployment. Objectives. We aim to ensure safe and performant agent behavior during deployment. Safety. For any time t∈ℤ+t _+ a position spos,t∈Pos_pos,t∈ Pos is unsafe if there is an obstacle there or there exist i≠ji≠ j such that spos,i,t=spos,j,t=spos,ts_pos,i,t=s_pos,j,t=s_pos,t. A state si,ts_i,t of an agent i is unsafe if spos,i,ts_pos,i,t or s~i,t s_i,t are unsafe. The joint multi-agent state st=(s1,t,…sn,t)s_t=(s_1,t,… s_n,t) is safe if all agent states are safe. We therefore define a safe set safe⊆S^safe that agents must remain in during execution A state that is safe during training may become unsafe during deployment. We assume a decentralized communication-free safety shield ϕ=ϕi∈ℐφ= _i_i for the Dec-POMDP (4)-(7); its design is beyond the scope of this paper, though Section 7 presents a suitable shield for our benchmarks. Performance. Let us assume that the agents’ tasks remain unchanged, then reward functions ri(si,ai)r_i(s_i,a_i) one used for training are relevant at the deployment phase as well. While the shield ϕφ will guarantee safety during the deployment, the shielded policy π1tr,…,πNtr\ _1^tr,…, _N^tr\ not necessarily maximizes (8). In this paper, we search for joint policies π=π1,…,πnπ=\ _1,…, _n\, that improve the performance of the system in terms of the cumulative reward of all agents: π[∑t=0∞γt∑i=1Nri(si,t,ϕi(oi(st),ai,t))].E_π [ _t=0^∞γ^t _i=1^Nr_i(s_i,t, _i(o_i(s_t),a_i,t)) ]. (8) 4 Model Predictive Shield At any time t, agent i can use its local observation oi(st)o_i(s_t), and the sampling model Mi(si,t,ai,t,ri,t,si,t′)M_i(s_i,t,a_i,t,r_i,t,s_i,t ) to locally re-plan its trajectory. Since every agent has a limited observability range ρi _i, we limit the re-planning to this range. The objective is to improve the contribution of the agent i to the joint reward (8), by simulating the two-player game, where the agent i tries to maximize the reward πi[∑t=0∞γtri(si,t,ϕi(oi(st),ai,t))],E_ _i [ _t=0^∞γ^tr_i(s_i,t, _i(o_i(s_t),a_i,t)) ], (9) while the safety shield acts as an adversarial agent. When the shield is used in the simulation, the agent receives a negative reward rshr_sh, and the action is replaced with πbackup _backup. We assume that agents can distinguish between static and dynamic safety constraints. That enables us to solve the simulated game differently for stationary versus non-stationary environmental changes. When the agent’s position spos,i,ts_pos,i,t leaves the region Bρi(spos,i,0)=spos∈Pos∣‖spos−spos,i,0‖≤ρiB_ _i(s_pos,i,0)=\s_pos∈ Pos \|s_pos-s_pos,i,0\|≤ _i\ the simulated process reaches the terminal state. maxai∈iQitr(si,t+1,ai). _a_i _iQ_i^tr(s_i,t+1,a_i). Finally, the agent then takes the action that is optimal with respect to the simulated game. In the following, we detail how we solve the two-player game for static and dynamic constraints and explain the overall algorithm for safe deployment of independently learned Q-functions. 4.1 Predictive shield for static safety constraints To handle static safety constraints, we apply the methodology presented in (Jin et al., 2025a). Let us remark that agent i treats the others as dynamical obstacles, hence at this stage we can know that there are no other agents in our sensing range, consequently, in (9), oi(st)o_i(s_t) is equal to si,ts_i,t. For every agent i, let us define a sequence of reachable sets Ri(0∣t,si,t)=si,t,Ri(k∣t,si,t)=⋃ai∈i⋃si∈Ri(k−1∣t,si,t)Ti(si,ai). splitR_i(0 t,s_i,t)&=s_i,t,\\ R_i(k t,s_i,t)&= _a_i _i _s_i∈ R_i(k-1 t,s_i,t)T_i(s_i,a_i). split (10) We then introduce the planning horizon kstatk_stat and simulate the game that optimizes (9) in the local region Ri,kstat.R_i,k_stat. Every state si,ts_i,t beyond Ri,kstatR_i,k_stat is terminal for simulated process, and agent i gets the reward equal to maxai∈iQitr(si,t+1,ai) _a_i _iQ_i^tr(s_i,t+1,a_i). One should choose the static planning horizon kstatk_stat do not exceed the visibility region. To solve the simulated game, the RL agent solves model-based Q-learning by sampling transitions from the model MiM_i. When a sampled transition (si,t,ai,t,si,t′,ri,t)(s_i,t,a_i,t,s_i,t ,r_i,t) is safe, the corresponding Q-function Qi(m)(si,ai)Q_i^(m)(s_i,a_i) is updated according to (1), when the action aia_i is verified unsafe the shield ϕi _i replaces it with a backup policy πbackup(oi(s)) _backup(o_i(s)) and Q-function Q(si,ai)Q(s_i,a_i) is updated with a penalty ri,shieldr_i,shield. For a more detailed description of the algorithm, let us refer the interested reader to our previous work (Jin et al., 2025a). Note that, since the simulated process is stationary, Q-learning will converge to an optimal Q-table QistQ_i^st of the simulated process (Sutton and Barto, 2018). 4.2 Predictive shield for dynamic obstacles While Q-learning works well in stationary environments, in a non-stationary environment it may not converge. We hence propose to reformulate (9), as finite-horizon optimization problem, and use time-dependent Q-value functions in the Q-learning update rule. Let us now choose the dynamic planning horizon kdk_d, such that kd≤kstatk_d≤ k_stat. The cumulative reward (9) can be re-written as follows: πi[∑k=0kdγkri(si,t+k,ϕi(oi(st+k),ai,t+k))+γkd+1maxai∈iQπi(si,t+kd+1,ai)].E_ _i [ _k=0^k_dγ^kr_i(s_i,t+k, _i(o_i(s_t+k),a_i,t+k))+\\ γ^k_d+1 _a_i _iQ_ _i(s_i,t+k_d+1,a_i) ]. (11) The last term in the equation above can be approximated with Qst(si,t+kd+1,ai)Q^st(s_i,t+k_d+1,a_i): πi[∑k=0kdγkri(si,t+k,ϕi(oi(st+k),ai,t+k))+γkd+1maxai∈iQsti(si,t+kd+1,ai)].E_ _i [ _k=0^k_dγ^kr_i(s_i,t+k, _i(o_i(s_t+k),a_i,t+k))+\\ γ^k_d+1 _a_i _iQ^st_i(s_i,t+k_d+1,a_i) ]. (12) The agent i cannot predict the full state of the system st,s_t, since it cannot predict the trajectories of the other agents. It is then searching for the policy πi _i, maximizing the worst-case reward: πi[∑k=0kdγkminst+k∈R~i,kri(si,t+k,ϕi(oi(st+k),ai,t+k))+γkd+1maxai∈iQsti(si,t+kd+1,ai)].E_ _i [ _k=0^k_dγ^k _s_t+k∈ R_i,kr_i(s_i,t+k, _i(o_i(s_t+k),a_i,t+k))+\\ γ^k_d+1 _a_i _iQ^st_i(s_i,t+k_d+1,a_i) ]. (13) where R~i,k R_i,k is defined as follows: R~i,k=R1(k|t,s1,t)×⋯×Ri−1(k|t,si−1,t)×si,t+k×Ri+1(k|t,si+1,t)×⋯×RN(k|t,sN,t). split R_i,k=\ &R_1(k|t,s_1,t)×…× R_i-1(k|t,s_i-1,t)\\ &×\s_i,t+k\× R_i+1(k|t,s_i+1,t)×…× R_N(k|t,s_N,t). split (14) Here Rj(k|t,si,t),j∈ℐR_j(k|t,s_i,t),j are the reachable sets from si,t,s_i,t, defined at (10). Since we optimize over finite horizon kdk_d, in reality we only take into account the agents that are in 2kd2k_d observability range. We then use Algorithm 1 to find πi _i that maximizes (13). 4.3 Model-Based Finite-Horizon Independent Q-Learning Algorithm 1 MB-FH-IQL 1: Pretrained Q-table QistQ_i^st, predictive horizon kdk_d, learning rate α, discount γ, model ℳM, agent current state scs_c, threshold ε 2: Initialize Q-tables Qi0,…,Qikd+1Q_i^0,…,Q_i^k_d+1 with QistQ_i^st 3: repeat 4: Qi0prev←Qi0Q_i^0prev← Q_i^0 5: si,t←scs_i,t← s_c 6: for k∈0,…,kdk∈\0,...,k_d\ do 7: ai,t+k←εa_i,t+k← -greedy policy from Qik[si,t+k]Q_i^k[s_i,t+k] 8: ai,safe←ai,t+ka_i,safe← a_i,t+k 9: for s′∈R~i,ks ∈ R_i,k do 10: if ϕi(oi(s′),ai,t+k)≠ai,t+k _i(o_i(s ),a_i,t+k)≠ a_i,t+k then 11: ai,safe←πbackup(oi(s′))a_i,safe← _backup(o_i(s )) 12: break 13: if ℳ(si,t+k,ai,safe)M(s_i,t+k,a_i,safe) is not empty then 14: (si,t+k+1,r)←ℳ(si,t+k,ai,safe)(s_i,t+k+1,r) (s_i,t+k,a_i,safe) 15: else 16: break 17: if ai,safe=πbackup(oi(s′))a_i,safe= _backup(o_i(s )) then 18: r←ri,k,shield(ai,t+k,si,t+k)r← r_i,k,shield(a_i,t+k,s_i,t+k) 19: (si,t+k,ai,t+k,si,t+k+1,r,α,γ) UpdQ_k(s_i,t+k,a_i,t+k,s_i,t+k+1,r,α,γ) 20: until ‖Qi0−Qi0prev‖2<ε\|Q_i^0-Q_i^0prev\|^2< 21: return Qi0Q_i^0 Algorithm 1 implements our Model-Based Finite-Horizon Independent Q-Learning (MB-FH-IQL). Unlike standard IQL, the agent simulates its own evolution using an internal dynamics model ℳM and assumes a worst-case evolution of other agents (13). Iteratively, the agent generates a kdk_d-step trajectory. Actions are selected via an ε -greedy policy and verified by a safety shield. If the shield overrides an action, the reward is replaced by the minimum possible reward in the reachable set R~i,k R_i,k: ri,k,shield(ai,t+k,si,t+k)=minsk∈R~i,kri(si,t+k,ϕi(oi(st+k),ai,t+k)).r_i,k,shield(a_i,t+k,s_i,t+k)= _s_k∈ R_i,kr_i(s_i,t+k, _i(o_i(s_t+k),a_i,t+k)). The Q-values are then updated by propagating information forward along the horizon: Qk(m+1)(sk,ak)=Qk(m)+α[rk+γmaxa′Qk+1(m)(sk+1,a′)−Qk(m)].Q_k^(m+1)(s_k,a_k)=Q_k^(m)+α [r_k+γ _a Q_k+1^(m)(s_k+1,a )-Q_k^(m) ]. By augmenting the state space with the prediction step k, the value function incorporates non-stationary effects caused by dynamic obstacles. The MB-FH-IQL algorithm is integrated into a full predictive shield architecture. The process first checks if the agent’s current policy leads to static or dynamic safety violations within kstatk_stat or kdk_d steps, respectively. If a violation is detected, infinite-horizon Q-learning is first employed on a local frame to converge to the Q-table QistQ_i^st with respect to static safety constraints only. Subsequently, MB-FH-IQL is executed only if the policy leads to dynamic safety violations within kdk_d steps, using the Q-table that locally re-updated to avoid the static obstacles QistQ_i^st as the terminal cost. This architecture separates static and dynamic safety constraints for two main reasons. First, to accelerate convergence regarding static constraints infinite horizon RL converges faster in stationary environments than finite horizon Second, this separation optimizes computational costs by allowing distinct horizon lengths: while static constraints typically require longer horizons to anticipate structural deadlocks, dynamic collision avoidance is often effective with shorter horizons. Decoupling these processes avoids unnecessary computation. 5 Communication-free conflict resolution protocol The MB-FH-IQL framework presented in Algorithm 1 seeks to reduce inter-agent interference through predictive shielding. However, due to decentralization, densely occupied or symmetric configurations may still generate livelocks. To mitigate these situations, we introduce a communication-free coordination protocol that probabilistically alternates between a nominal single-agent policy and a conservative multi-agent policy. Algorithm 2 Conflict Resolution Protocol 1: Current state si,ts_i,t, dynamic Q-table Qi0Q_i^0, static Q-table QistQ_i^st, probability function ε(⋅) (·), coordination count cic_i 2: Action to execute over two steps 3: if argmaxa′Qist(si,t,a′) _a Q_i^st(s_i,t,a ) is verified unsafe then 4: ai,stat,1←ϕi(oi(st),argmaxa′Qist(si,t,a′))a_i,stat,1← _i(o_i(s_t), _a Q_i^st(s_i,t,a )) 5: With probability ε(ci) (c_i): 6: Environment step with ai=ai,stat,1a_i=a_i,stat,1 7: ai,stat,2←ϕi(oi(st+1),argmaxa′Qist(si,t+1,a′))a_i,stat,2← _i(o_i(s_t+1), _a Q_i^st(s_i,t+1,a )) 8: Environment step with ai=ai,stat,2a_i=a_i,stat,2 9: With probability 1−ε(ci)1- (c_i): 10: ai,1←abs(oi(st),Qi0,ai,stat,1)a_i,1←$a_bs$(o_i(s_t),Q_i^0,\a_i,stat,1\) 11: Environment step with ai=ai,1a_i=a_i,1 12: ai,2←abs(oi(st+1),Qi0,iex(si,t+1,si,t))a_i,2←$a_bs$(o_i(s_t+1),Q_i^0,A^ex_i(s_i,t+1,s_i,t)) 13: Environment step with ai=ai,2a_i=a_i,2 The protocol is activated when the nominal action anom=argmaxa′Qistat(st,a′)a_nom= _a Q_i^stat(s_t,a ), computed from the static single-agent Q-table, is predicted to be unsafe (Line 3). We define a switching probability ε(ci) (c_i) as a logarithmically decaying function of the coordination count cic_i, which measures how frequently an agent has been involved in coordination situations.This mechanism introduces differentiated behaviors among agents facing similar local configurations without requiring explicit communication or role assignment. With probability ε(ci) (c_i), the agent follows the nominal single-agent policy for two consecutive steps (Lines 4–8). Otherwise, with probability 1−ε(ci)1- (c_i), the agent executes a conservative two-step coordination sequence (Lines 10–13). This branch relies on the constrained action-selection operator abs(oi(s),Qi,iex)a_bs(o_i(s),Q_i,A^ex_i), abs(oi(s),Qi,iex)=argmaxai∈is∖exQi(si,ai)if is∖ex≠∅πbackup(oi(s))otherwise.,a_bs(o_i(s),Q_i,A^ex_i)= cases a_i _i^s ex \ Q_i(s_i,a_i)&if A_i^s ex≠ \\ _backup(o_i(s))&otherwise. cases, (15) where is∖ex=ai∈i∣φi(oi(s),ai)=1∧ai∉iexA_i^s ex=\a_i _i \, _i(o_i(s),a_i)=1\ a_i ^ex_i\, i.e. iexA^ex_i denotes the set of actions, we exclude from the safe actions. During the first step (Line 10), the protocol excludes the nominal action selected in the alternate branch by setting ex=ai,stat,1A_ex=\a_i,stat,1\. The agent is therefore encouraged to select an alternative safe action, which helps breaking the symmetry In the second step (Line 12), the protocol excludes actions that would immediately return the agent to its previous state: iex(si,si,prev)=ai∈i∣i(si,ai)=si,prevA^ex_i(s_i,s_i,prev)=\a_i _i _i(s_i,a_i)=s_i,prev\ (16) This constraint prevents immediate reversals and reduces short oscillatory behaviors. The resulting two-step sequence is inspired by the pseudo-goal coordination strategies introduced by (Jha et al., 2024). In particular, the conservative branch temporarily deviates from the goal, while the second-step exclusion constraint discourages an immediate return to the previous state. As a result, the agent is implicitly guided toward a temporary intermediate objective. 6 Dec-POMDP Algorithm Fig. 1 illustrates the proposed control architecture. The predictive shield operates as the primary control layer, filtering actions to mitigate dynamic interference while preserving goal-directed behavior. However, when the shield detects that the nominal policy is infeasible due to a crowded environment or a symmetric situation, the system transitions to the Conflict Resolution Protocol. To escape these local minima, the protocol employs a stochastic switching strategy where agents probabilistically alternate between a conservative multi-agent policy and the nominal trajectory. This induced stochasticity effectively breaks symmetry, minimizing livelocks. This architecture strictly guarantees that unsafe actions are never executed. Inputsi,t,Qi∗s_i,t,Q_i^*PredictiveShield (Alg. 1) argmaxQist(si,t) Q_i^st(s_i,t)unsafe? Executeai,safea_i,safe Conflict ResolutionProtocol (Alg. 2) ai,safea_i,safeQistQ_i^stFalsesi,t+1s_i,t+1Truesi,t+2s_i,t+2 Figure 1: Flowchart of algorithms and executions per time step for each agent i 7 Experiments Table 1: Performance Comparison: IQL vs MIS vs Dyna Shield vs DMPS vs Ours. (H: Horizon, TpreT_pre: Pretrain Time, TdepT_dep: Deployment Time) Exp. IQL MIS Dyna-Q Shield DMPS Ours Tpre(s)T_pre(s) Tdep(s)T_dep(s) Ret. Steps k Tpre(s)T_pre(s) Tdep(s)T_dep(s) Ret. Steps k Tpre(s)T_pre(s) Tdep(s)T_dep(s) Ret. Steps k Tpre(s)T_pre(s) Tdep(s)T_dep(s) Ret. Steps (kstat,kdyna)(k_stat,k_dyna) Tpre(s)T_pre(s) Tdep(s)T_dep(s) Ret. Steps Exp 1 531.1 1.91×10−51.91× 10^-5 180 11 11 5.5 4.9×10−44.9× 10^-4 −∞-∞ ∞ 77 5.5 0.27 151.2 26.8 77 5.5 0.1 180 11 (7,4) 5.5 0.05 180 11 Exp 2 1614.5 3.14×10−53.14× 10^-5 360 11 11 5.8 1.01×10−41.01× 10^-4 −∞-∞ ∞ 77 5.8 0.67 48.70 75.3 77 5.8 1.13 −∞-∞ ∞ (7,2) 5.8 0.41 328.5 31 Exp 3 3382.3 2.82×10−32.82× 10^-3 -94 ∞ 11 6.95 2.04×10−32.04× 10^-3 −∞-∞ ∞ 77 6.95 0.02 -379.8 ∞ 77 6.95 0.88 −∞-∞ ∞ (7,2) 6.95 2.6 268.4 105.2 In this section, we evaluate the proposed method using the gym-multigrid framework (Fickinger, 2020)11 1 https://github.com/ArnaudFickinger/gym-multigrid. Our evaluation focuses on two distinct environments: a standard multi-agent path findingscenario and a constrained coin collection task, where agents must collect assigned coins while strictly avoiding those belonging to others. Across all experiments, the discrete action space is defined as =,,,A=\ up, down, left, right\,and the backup policy is πbackup(s)= _backup(s)= stay, ensuring hard safety guarantees in non-adversarial environments where all agents are shielded, as agents can indefinitely hold their position without being collided with by other shielded agents. Finally, the reward function is defined as follows: +100+100 for reaching a goal or collecting a valid coin, −10-10 for inter-agent collisions, and −100-100 for hitting a static obstacle or collecting an invalid coin1. We conduct two types of evaluation, first benchmarking our approach against four baselines on three canonical scenarios (Fig. 2). We include IQL (Tan, 1993) as an independent learning technique where agents are trained within the shared environment with collision penalties but without an explicit shield. The other three baselines are shielding techniques that utilize a Q-table QitrQ_i^tr pre-trained in a single-agent, obstacle-free environment; for these methods, the agent initial positions and objectives remain identical between the pre-training and deployment phases. Within this group, the Minimal Interference Shield (MIS) (ElSayed-Aly et al., 2021) is a reactive method that follows the QitrQ_i^tr policy and only invokes πbackup _backup upon imminent violation. In contrast, the remaining two are predictive techniques: the local planner from Dynamic Model Predictive Shielding (DMPS) (Banerjee et al., 2024) is a finite-horizon planner that treats static and dynamic constraints identically, while the Predictive Safety Shield (Dyna-Q Shield) (Jin et al., 2025a) treats other agents as static obstacles during its updates. Finally, for all shielding-based methods, we enforce a decentralized safety guarantee that prohibits entry into any cell reachable by a neighbor in a single step to ensure hard safety against dynamic constraints. (a) Exp1: Narrow corridor (b) Exp2: Symmetric env. (c) Exp3: Crowded passage Figure 2: In the two figures on the right, the agents are solving a path-finding game. The agents are represented by triangles, and their goals are shown as squares. In the third figure, the agents (triangles) need to collect the balls (circles) of the corresponding color. Second a scalability analysis on the multi-agent path finding task within a 10×1010× 10 grid through two parametric tests where each configuration is evaluated over 45 random initialization: the first varies the number of agents in free, while the second fixes the number of agents to four and varies the static obstacle density with kstat=7k_stat=7. As shown in Figure 3, an increase in the density of either agents or static obstacles generally leads to a lower fraction of agents reaching their goals. To identify the most robust horizon across these varying conditions, we introduce a cumulative regret metric R(kdyna)R(k_dyna), defined as: R(kdyna)=∑c∈(maxkS(k,c)−S(kdyna,c))R(k_dyna)= _c ( _kS(k,c)-S(k_dyna,c) ) (17) where C represents the set of test configurations and S(k,c)S(k,c) denotes the success rate. In environments without static obstacles (Fig. 3), we observe that all values of kdynak_dyna perform quite similarly, with kdyna=1k_dyna=1 maintaining a slight edge while being preferable from a computational complexity perspective. However, the introduction of static obstacles (Fig. 3) shifts this trend, making a mid-length horizon of kdyna=3k_dyna=3 the most effective choice. Since kstatk_stat is already set to a long horizon to manage navigation around walls, the primary role of kdynak_dyna in these settings is to anticipate the presence of other agents before committing to narrow passages or bottlenecks. Without this look-ahead, agents may enter restricted spaces simultaneously, leading to situations that are difficult to resolve. These results illustrate a trade-off between look-ahead sufficiency and over-conservatism. While a mid-length horizon helps agents coordinate before entering constrained areas, excessively long horizons can lead to performance drops in dense settings. We attribute this to the accumulation of uncertainty over time, which causes the shielding mechanism to become overly sensitive, eventually inducing freezing behaviors or forcing agents to deviate excessively from their paths. Static Obstacles (kdynak_dyna): 1 2 3 4 5 6 Free Space (kdynak_dyna): 1 2 3 4 5 6 Figure 3: Average fraction of agents reaching their goal under static obstacles (4 agents, kstat=7k_stat=7) and in free space environments for different horizons 8 Conclusion This paper proposed a fully decentralized framework for the safe deployment of independently trained RL agents in shared environments. By integrating a predictive safety shield and a communication-free conflict resolution protocol, our approach enables agents to adapt their policies online while guaranteeing safety and minimize the number of livelocks. Experimental results show that the proposed method outperforms shielding baselines in terms of task completion and independent learning approaches in terms of computation time. Nevertheless, several challenges remain. First, the prediction horizon depends on the environment and must currently be chosen before deployment; future work should investigate adaptive horizon selection during execution. Second, the worst-case estimation makes the approach conservative, even with reward shaping, motivating the exploration of alternative methods such as trajectory estimation using conformal prediction (Lindemann et al., 2025). Finally, the impact of model mismatch between training and deployment environments remains unclear and requires further investigation. Acknowledgments This work was supported by the French National Research Agency (ANR) under grant ANR-22-EXES-0013. The authors also acknowledge Ferdinand Plesse-Costa for his assistance. References Banerjee et al. (2024) Banerjee, A., Rahmani, K., Biswas, J., and Dillig, I. (2024). Dynamic model predictive shielding for provably safe reinforcement learning. In Proceedings of the 38th International Conference on Neural Information Processing Systems, NIPS ’24. Bernstein et al. (2000) Bernstein, D.S., Zilberstein, S., and Immerman, N. (2000). The complexity of decentralized control of markov decision processes. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, UAI’00, 32–37. Brorholt et al. (2025) Brorholt, A.H., Larsen, K.G., and Schilling, C. (2025). Compositional shielding and reinforcement learning for multi-agent systems. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’25, 399–407. Carr et al. (2025) Carr, S., Bakirtzis, G., and Topcu, U. (2025). Compositional shield synthesis for safe reinforcement learning in partial observability. IEEE Open Journal of Control Systems, 4, 373–384. Chandra et al. (2025) Chandra, R., Zinage, V., Bakolas, E., and et al. (2025). Deadlock-free, safe, and decentralized multi-robot navigation in social mini-games via discrete-time control barrier functions. Autonomous Robots, 49(1), 12. ElSayed-Aly et al. (2021) ElSayed-Aly, I., Bharadwaj, S., Amato, C., Ehlers, R., Topcu, U., and Feng, L. (2021). Safe multi-agent reinforcement learning via shielding. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’21, 483–491. Fickinger (2020) Fickinger, A. (2020). Multi-agent gridworld environment for openai gym. Garg et al. (2024) Garg, K., Zhang, S., So, O., Dawson, C., and Fan, C. (2024). Learning safe control for multi-robot systems: Methods, verification, and open challenges. Annual Reviews in Control, 57, 100948. Grover et al. (2023) Grover, J., Liu, C., and Sycara, K. (2023). Deadlock analysis and resolution in multi-robot systems. The International Journal of Robotics Research, 42(1-2), 57–87. Guo and Dimarogonas (2015) Guo, M. and Dimarogonas, D.V. (2015). Multi-agent plan reconfiguration under local ltl specifications. Int. J. Rob. Res., 34(2), 218–235. Jha et al. (2024) Jha, A., Gupta, T., Rawat, S., and Kumar, G. (2024). Strategic pseudo-goal perturbation for deadlock-free multi-agent navigation in social mini-games. 264–269. Jin et al. (2025a) Jin, P., Krasowski, H., and Vanneaux, E. (2025a). Predictive safety shield for dyna-q reinforcement learning. In 2025 European Control Conference (ECC), 2173–2179. IEEE. Jin et al. (2025b) Jin, R., Chen, Z., Lin, Y., Song, J., and Wierman, A. (2025b). Approximate global convergence of independent learning in multi-agent systems. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2818–2826. Krasowski et al. (2023) Krasowski, H., Thumm, J., Müller, M., Schäfer, L., Wang, X., and Althoff, M. (2023). Provably safe reinforcement learning: Conceptual analysis, survey, and benchmarking. Transactions on Machine Learning Research. Li and Bastani (2020) Li, S. and Bastani, O. (2020). Robust model predictive shielding for safe reinforcement learning with stochastic dynamics. In 2020 IEEE International Conference on Robotics and Automation (ICRA), 7166–7172. Lindemann et al. (2025) Lindemann, L., Zhao, Y., Yu, X., Pappas, G.J., and Deshmukh, J.V. (2025). Formal verification and control with conformal prediction: Practical safety guarantees for autonomous systems. IEEE Control Systems, 45(6), 72–122. 10.1109/MCS.2025.3611545. Oroojlooy and Hajinezhad (2022) Oroojlooy, A. and Hajinezhad, D. (2022). A review of cooperative multi-agent deep reinforcement learning. Applied Intelligence, 53(11), 13677–13722. Sheng et al. (2024) Sheng, S., Parker, D., and Feng, L. (2024). Safe pomdp online planning via shielding. In 2024 IEEE International Conference on Robotics and Automation (ICRA), 126–132. Sutton and Barto (2018) Sutton, R.S. and Barto, A.G. (2018). Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA. Tan (1993) Tan, M. (1993). Multi-agent reinforcement learning: independent versus cooperative agents. In Proceedings of the Tenth International Conference on International Conference on Machine Learning, ICML’93, 330–337. Tang et al. (2025) Tang, C., Abbatematteo, B., Hu, J., Chandra, R., Martín-Martín, R., and Stone, P. (2025). Deep reinforcement learning for robotics: A survey of real-world successes. Annual Review of Control, Robotics, and Autonomous Systems, 8(1), 153–188. Xiao et al. (2023) Xiao, W., Lyu, Y., and Dolan, J. (2023). Model-based dynamic shielding for safe and efficient multi-agent reinforcement learning. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’23, 1587–1596. 1 1 1 endnote 1 Source code: https://github.com/YacineEY/Decentralized-Safe-Multi-Agent-Reinforcement-Learning-via-Predictive-Shielding.git