SafeDiSTL: Decomposing Joint Constraints for Safe Multi-Agent Reinforcement Learning

SafeDiSTL: Decomposing Joint Constraints for Safe Multi-Agent Reinforcement Learning Hongrui Zheng

Aditya Singh

Rahul Mangharam

University of Pennsylvania, Philadelphia, USA

arXiv:2610.13737v1 [cs.LG] 9 Oct 2026

{hongruiz,singhadi,rahulm}@engineering.upenn.edu

Abstract Cooperative multi-agent tasks often impose constraints on a shared objective or collective safety. A team level violation cost function can measure this constraint outcome, but does not distinguish which agents’ actions most strongly influence that violation. We present SafeDiSTL, a constrained multi-agent reinforcement learning framework that allows for credit assignment even with joint constraint measurements. We use Signal Temporal Logic (STL) robustness to measure episode-level violation through running-maximum cost increments. Smooth full-episode robustness and differentiable dynamics provide action sensitivities, which allocate each cost increment across agents at the same decision time. These sensitivities account for delayed effects when weighting agents’ shares of each cost increment. We study the framework in cooperative payload transport, connected navigation, and networked traffic control tasks. SafeDiSTL achieves 1.6-5.1x the safe-success rate in transport, improves navigation safe-success by 11.1%, and delivers 50-68% more throughput in traffic when compared to constrained baselines. Results demonstrate a strong improvement of the learned policy in dealing with shared constraint while retaining the performance of unconstrained policies.

Uniform t1

t2 t3

t2

0.33

0.33

0.33

0.33

0.33

0.33

0.33

0.33

0.33

t1

t2

t3

t1 t3 t2

Attributed (a) Initial rollout

Payload

0.20

0.40

0.45

0.60

0.20

0.10

0.20

0.40

0.45

t1

t2

t3

(b) Uniform rollout t3

t1

(c) Attributed rollout

Agents

Obstacles

Goal

Figure 1: An illustration of the responsibility attribution mechanism. (a) A shared payload approaches an obstacle and incurs a constraint violation. (b) Uniform responsibility allocation produces conflicting corrections and agents stay deadlocked. (c) Agent-specific attribution enables coordinated obstacle avoidance.

1

1

Introduction

Recent developments in multi-agent autonomous systems and their applications in aerial swarms, intelligent transportation networks, and automated warehouses have made multi-agent coordination a central problem. In these environments, multiple agents must operate in shared spaces and achieve collective objectives, including collaborative manipulation, routing, and formation control, while satisfying system constraints such as connectivity and collision avoidance. Constraints in singleagent RL are commonly formulated with Constrained Markov Decision Processes (CMDPs) [2]. Policies are then optimized by reformulating the problem as a primal-dual optimization between reward and costs. Constrained Policy Optimization (CPO) [1] balances updates with more reward or cost consideration using a Lagrangian multiplier. Multi-agent Reinforcement Learning (MARL) is a popular paradigm for learning decentralized agent policies in multi-agent problems. Existing work extends CMDP formulations to MARL [11], although generally assuming well-defined, decoupled cost functions for individual agents. However, a shared constraint definition is important in multi-agent settings. For example, if multiple robots carry a shared rigid payload, a crash between the payload and obstacles is hard to attribute to individual agents. Consider the example shown in Figure 1: three warehouse robots collaboratively transport a large payload to a designated delivery location. At a given point t3 , one robot might be required to push in a direction such that the payload avoids the obstacle (green agent pushing up), while the other two maintain progress toward the goal (yellow and blue push right). When encountering a violation such as that in Figure 1.(a), assigning equal responsibility to all agents leads to a deadlock (Figure 1.(b)) without addressing the asymmetrical desired updates to individual agents. This shows that a shared constraint definition alone is not enough. It tells the team of agents how much they violated, but without explicit learning signals to individual agents on how to update their policies. Without careful decomposition, the introduction of a uniform penalty for all agents will hinder task learning progress. If an agent makes significant contribution towards the team’s task progress but not towards violating constraint at a timestep, that individual transition should not incur a penalty in the policy learning process. Credit assignment is an active area of research in MARL. Counterfactual Multi-Agent Policy Gradients (COMA) [9] established counterfactual reasoning for agents on task reward. Existing work [11, 14, 17] considers both individual and shared constraints in MARL problems, but leaves much to be desired in the effective decomposition of the constraint objective. This motivates the need for a principled mechanism to decompose the shared constraint among agents while accounting for the changing individual responsibilities to enable effective collaboration. Signal Temporal Logic (STL) [16] is a compact formal specification language that expresses logical and temporal requirements over trajectories. The quantitative measure called robustness [7, 8] assigns the margin of success to a trajectory instead of a binary signal. The biggest advantage of using STL is that differentiating its robustness through the full trajectory captures how individual actions influence subsequent constraint outcomes. We use these gradients to allocate cost increments across agents at its original timestep, while cost advantages propagate learning signals to earlier decisions. For the example in Figure 1, we express the shared responsibility as ”Always no collision between payload and obstacle”. Differentiable dynamics help achieve this by propagating individual agents’ influence to joint state space trajectories, and allowing back propagation from the margin of violation to decisions. As shown in Figure 1.(c), the green agent learns to subtly change its behavior by pushing upward rather than to the right, resulting in a successful avoidance of the obstacle. In summary, the contributions of this work are as follows: 1. We introduce an agent- and time-specific attribution mechanism that decomposes shared 2

team constraints using STL robustness gradients while preserving the total cost. 2. We develop SafeDiSTL, a constrained MARL framework that incorporates these attributed costs into policy optimization for decentralized execution. 3. We evaluate SafeDiSTL on three tasks, comparing task performance and constraint satisfaction with other baselines.

2

Related Work

Constrained MARL: Gu et al. [11] introduce MACPO and MAPPO-Lagrangian, using constrained trust region updates and Lagrangian policy optimization, respectively. Like MACPO, IsCPO [17] coordinates separate agent policies through sequential updates. IsCPO considers global costs and updates agents in random order, passing optimization information to subsequent agents. Thus, later agents account for the effects of earlier updates on the shared constraint. Both MACPO and IsCPO coordinate policy updates, rather than an explicit allocation of a trajectory’s violation cost according to each agent’s influence. Ling et al. [14] directly address constraint credit assignment through fictitious MARL in a collective setting. Its formulation exploits anonymous interactions represented by aggregate counts of agents in local states and actions, rather than individual identities. This structure supports scalable reward and constraint credit assignment, but is not assumed in our setting, where shared constraints can depend on coupled geometric configurations and actiondependent dynamics. SafeDiSTL instead obtains agent-specific cost allocations from the gradient sensitivity of a shared trajectory specification. Multi-agent Credit Assignment: Credit assignment methods for multi-agent systems extract individual learning signals from shared team outcomes. COMA [9] uses a centralized critic and a counterfactual baseline that marginalizes one agent’s action while holding the others fixed. QPD [21] applies integrated gradients along trajectory paths to decompose global action values into individual credits. STAS [5] first redistributes episodic return over time and then uses Shapley attribution between agents. These methods establish counterfactual, gradient-based, and temporal attribution for cooperative reward optimization. Our focus is the attribution of the shared constraint: we differentiate STL robustness through dynamics rather than attribute a learned return prediction. Responsibility Allocation: Wang et al. [20] use STL robustness to construct multi-agent rewards incorporating task and safety specifications. Zheng et al. [24] uses STL robustness as a learning signal for coordination of multiple agents. Lyu et al. [15] dynamically distribute collision avoidance responsibility using a control barrier function (CBF)-inspired risk measure. Cosner et al. [6] learn scene dependent allocations for responsibility aware control barrier functions. These approaches demonstrate the value of asymmetric safety responsibility in decentralized control. SafeDiSTL addresses the related problem of allocating learning signals for constraint violations during policy optimization, using STL robustness gradients to construct agent specific update signals rather than allocating online safety filter obligations.

3

Preliminaries

3.1

Signal Temporal Logic

Syntax: Signal Temporal Logic (STL) [16] allows us to create spatiotemporal requirements over trajectories τ , which encodes the global constraint in our learning problem. For example, we can express “Always avoid a collision between payload and obstacles” in a formal specification: 3

ϕ = □[0,5] ¬µcol (ppayload , pobs ), where µcol is a predicate function that measures whether the two objects described by positions p are in collision. The STL syntax is ϕ := ⊤ | µg | ¬ϕ | ϕ1 ∧ ϕ2 | ϕ1 U[t1 ,t2 ] ϕ2 .

(1)

⊤ is the truth value, µg := g(τ (t)) ≥ 0 is an atomic predicate, its truth value being determined by the value of the function g : Rn → R. ∧ and ¬ denote the “conjunction” and “negation” Boolean operators, respectively. U denotes the “until” temporal operator, which specifies that formula ϕ1 holds until ϕ2 holds in interval [t1 , t2 ]. Disjunction is defined as ϕ1 ∨ ϕ2 := ¬(¬ϕ1 ∧ ¬ϕ2 ); “Eventually” is defined as ♢[t1 ,t2 ] ϕ := ⊤ U[t1 ,t2 ] ϕ; “Always” is defined as □[t1 ,t2 ] ϕ := ¬ ♢[t1 ,t2 ] ¬ϕ; And “Implication” is defined as ϕ1 =⇒ ϕ2 := ¬ϕ1 ∨ ϕ2 . Quantitative Semantics: STL uses robustness ρϕ (τ ) ∈ R to measure how strongly a given trajectory satisfies or violates a specification ϕ. ρ > 0 implies satisfaction and ρ < 0 implies violation. We used the standard definition to calculate robustness [7, 8]. We also utilize smooth approximations [12, 13, 18] of max and min operators to enable auto-differentiation of the robustness value of a trajectory to the states in the trajectory. The end-to-end gradient computation from robustness to policy actions can then be enabled with differentiable dynamics.

4

Problem Formulation

4.1

Constrained Cooperative Markov Game

The cooperative multi-agent Markov Decision Process (MDP) is defined by the tuple: M = S, A = ΠN i=1 Ai , P, r, ρ0 , γ , where S is the state space, A is the joint action space, Ai is the action of agent i out of N , P is the transition kernel, r is the shared task reward, ρ0 is the initial state distribution, and γ is the discount factor. We extend this standard multi-agent MDP to a constrained Markov Game by extending the tuple to: MC = M, c, d , where c : S × A → R≥0 is a non-negative cost function representing the shared responsibility of all agents, and d is a scalar cost budget for each episode. In this setting, we consider decentralized agent policies, where the joint policy factorizes as follows: πθ (at |ot ) = ΠN i=1 πθ (ai,t |oi,t ), and the system evolves as: st+1 ∼ P (·|st , at ), where θ is the shared policy parameters, at is the joint action produced at time t, oi,t is the observation of agent i at time t, and st is the joint state at time t. The shared task reward objective can be expressed as: H−1  X t γ r(st , at ) , (2) JR (θ) = Eτ ∼πθ t=0

where τ ∼ πθ denotes the trajectories realized under policy πθ , and H denotes the episode horizon. In addition to the task reward, we also consider the shared cost objective: H−1  X γ t c(st , at ) . (3) JC (θ) = Eτ ∼πθ t=0

4

Hence, the combined constrained team objective of the agents becomes: maximizeθ JR (θ),

4.2

subject to JC (θ) ≤ d

(4)

Lagrangian SafeMARL

A standard Lagrangian formulation of the constrained objective in Equation (4) introduces a nonnegative multiplier that trades reward against excess cost [1]: max min L(θ, λ) = JR (θ) − λ(JC (θ) − d) θ

λ≥0

(5)

A canonical first-order projected primal–dual update performs ascent in the policy parameters and descent in the multiplier. At iteration k, it takes the form θk+1 = θk + ηθ ∇θ L(θk , λk ),
  λk+1 = λk + ηλ JC (θk ) − d + ,

(6)

where [·]+ = max(0, ·) and ηθ , ηλ > 0 are learning rates. The multiplier increases when the cost exceeds the budget. Equation (6) is an idealized gradient template: practical algorithms use sampled estimates and may change the surrogate objective, optimizer, or update schedule. Gu et. al. [11] proposes two constrained MARL algorithms MACPO and MAPPO-L: MACPO solves sequential constrained trust-region subproblems rather than using the multiplier recursion in Equation 6; MAPPO-L instead combines reward and cost advantages in a PPO-style surrogate with nonnegative multiplier updates. Our proposed method SafeDiSTL follows the Lagrangian approach but attributes the shared trajectory cost across agents and decision times for the actor update, while retaining the unallocated shared cost for multiplier updates.

5

SafeDiSTL

A shared constraint cost measures the team’s violation but does not distinguish the contributions of individual agents and decisions. SafeDiSTL uses full-episode STL sensitivities to allocate each running-maximum cost increment across agents at the same decision time. Section 5.1 develops this allocation while preserving both the per-step increment and the total episode cost. Section 5.2 incorporates the attributed costs into critic learning and constrained policy optimization, while retaining the original episode cost for the multiplier update.

5.1

Decomposing the Shared Constraint

SafeDiSTL uses an STL specification on the joint state of all agents for both calculating the shared constraint cost and credit assignment. Let τ = (s0 , a0 , . . . , aTτ −1 , sTτ ) be a complete episode. Let H denote the maximum episode length and Tτ ≤ H the number of transitions in episode τ , which may terminate before reaching H. Let ρϕ (τ ) denote the episode’s robustness with respect to the shared constraint specification ϕ. We define the episode violation cost and its expectation as C ϕ (τ ) = [−ρϕ (τ )]+ , JCϕ (θ) = Eτ ∼πθ [C ϕ (τ )].

5

(7)

In this paper, we consider the always-conjunction specifications type. This type of specification follows this form: K ^ ϕ= □ µgj , [0,Tτ −1] (8) j=1 ρϕ (τ ) = min

min gj (st+1 ),

0≤t<Tτ 1≤j≤K

where K counts shared predicates and gj (s) ≥ 0 indicates satisfaction of predicate j. Each predicate function g(j) here is essentially a distance function that describe a part of the shared constraint. For example, it could be the Euclidean distance between a shared payload and an obstacle. Inspired by State-wise Constrained Policy Optimization [23], we accumulate the episode cost through increments in the running maximum. Define the instantaneous post-transition violation of the shared constraint and running maximum by   cins (st+1 ) = − min gj (st+1 ) , 1≤j≤K (9) + cmax,t = max{cmax,t−1 , cins (st+1 )}, with cmax,−1 = 0. The incremental maximum cost is ∆ct = cmax,t − cmax,t−1 = [cins (st+1 ) − cmax,t−1 ]+ .

(10)

Only a violation exceeding the maximum of the previous episode incurs an additional cost. These increments telescope to the episode violation cost: TX τ −1

∆ct = cmax,Tτ −1 = C ϕ (τ ).

(11)

t=0

Unlike the generic discounted cost in Equation (3), our shared constraint objective sums without discounting. This preserves the peak violation irrespective of when it occurs, and the correctness of Equation (11). The increments identify when the measured violation increases, but not which decisions influence it. To construct agent- and time-specific learning signals, we differentiate trajectory robustness through the dynamics. Let ρeϕ denote the differentiable smooth approximation of the robustness and define the action sensitivity zi,t =

∂[−e ρϕ (τ )] . ∂ai,t 2

(12)

Note that we use the 2-norm here, thus our action sensitivity only measures the magnitude of the influence of an agent. The derivative propagates through the entire recorded episode, holding the other sampled actions fixed. Thus, the sensitivities capture delayed effects rather than only immediate effects. The smooth robustness approximation and attribution normalization are detailed in Appendix F. We normalize these sensitivities across agents separately at each decision time: wi,t =

zi,t N X

zj,t

j=1

6

,

(13)

assuming nonzero sensitivity at time t, with uniform weights when all sensitivities vanish. Thus, P i wi,t = 1 for every valid decision time. We allocate the corresponding cost increment using detached attribution weights: e ci,t = N ∆ct stopgrad(wi,t ). (14) The sensitivity that determines the relative agent weights is from the full episode, while the costs allocated remain local at each timestep. If ∆ct = 0, no attributed cost is assigned at that time. The factor N accounts for averaging across agents, preserving each increment and hence the episode cost: N 1 X e ci,t = ∆ct , N i=1 (15) TX N Tτ −1 τ −1 1 XX e ci,t = ∆ct = C ϕ (τ ). N i=1 t=0

5.2

t=0

Constrained Policy Optimization

We optimize decentralized policies using a MAPPO-style [22] proximal policy optimization (PPO) algorithm under centralized training. Following the Lagrangian formulation in Section 4.2, the policy update balances the shared task reward with the constraint cost. SafeDiSTL replaces the shared cost signal in this update with the agent-specific attributed costs defined in Section 5.1. A centralized reward critic VR (st ) estimates the expected discounted share task return. For constraint costs, we use an agent-specific critic VCi (oi,t , cmax,t−1 ) and a centralized critic VCg (st , cmax,t−1 ). They estimate the expected remaining cumulative cost assigned to agent i and its team mean, respectively, using the allocation from Section 5.1. The corresponding cost signals are e ci,t and 1 X e ci,t = ∆ct . N N

ct =

(16)

i=1

Attribution changes the distribution of cost across agents but not its timing or team mean. The centralized cost critic therefore learns from the original increments ∆ct , while the agent-specific critic learns from e ci,t . Both receive cmax,t−1 as training-only context for the constraint history. Then generalized advantage estimation (GAE) connects each signal and critic to its advantage: AR,t = GAEt (r, VR ),

AC ci , VCi ), i,t = GAEt (e

g AC g,t = GAEt (c, VC ).

(17)

Here, GAE takes the corresponding signal sequence and rollout-time critic predictions. The critic regression targets are: yR,t = AR,t + VR,t ,

C i yi,t = AC i,t + VC,t ,

g C yg,t = AC g,t + VC,t .

(18)

i , and V g denote predictions during rollout. The centralized cost critic supplies a Here VR,t , VC,t C,t joint-state reference for the local critics: a consistency penalty encourages their mean prediction to agree with it. Therefore, it influences the actor indirectly through agent-specific predictions, rather than through a separate AC g,t term in the actor objective. We combine the shared reward advantage with each agent’s attributed cost advantage:

Ai,t = AR,t − λk AC i,t , qi,t (θ) =

πθ (ai,t | oi,t ) . πθk (ai,t | oi,t ) 7

(19)

Algorithm 1 SafeDiSTL g

1: Initialize πθ , critics VR , VCi , VC , and λ0 . 2: for each training iteration k do

Collect complete episodes using πθk . 4: Compute C ϕ (τ ), increments ∆ct , and full-episode sensitivities zi,t . 5: Normalize zi,t across agents at each t to obtain wi,t . 6: Allocate e ci,t = N ∆ct stopgrad(wi,t ); set ct = ∆ct . C 7: Compute AR,t , AC i,t , Ag,t using Equation (17). g C , y C , with cost consistency regularization. 8: Fit VR , VCi , VC to yR,t , yi,t g,t 9: Form Ai,t = AR,t − λk AC . i,t 10: Update θk to θk+1 using Equation (20). 11: Update λk to λk+1 from the mean C ϕ (τ ) and budget d. 12: end for 3:

Here λk ≥ 0 is the shared constraint multiplier at training iteration k, and qi,t (θ) is the action likelihood ratio between the updated and rollout policies. The actor is updated using the PPO clipped objective  Lactor (θ) = Ei,t min{qi,t (θ)Ai,t ,  (20) clip(qi,t (θ), 1 − ϵ, 1 + ϵ)Ai,t } , where ϵ > 0 is the clipping threshold. The advantages and attribution weights are held fixed during this update. When individual constraints are also present, their cost advantages and multipliers contribute separate penalty terms and are not included in the shared attribution. For the dual update in Equation (6), we estimate JCϕ (θk ) using the mean exact episode cost C ϕ (τ ), not the attributed cost of any single agent. The shared multiplier λk increases when this mean exceeds d and decreases when it falls below d, subject to its nonnegative range. Thus, attribution changes the agents’ policy-learning signals while the dual update uses the original shared constraint. Algorithm 1 summarizes the training procedure. Cost-advantage estimation, critic losses, and implementation details are given in Appendix G.

6

Experiments

We evaluate SafeDiSTL on three cooperative multi-agent benchmarks with different shared constraints: package–obstacle clearance in transport, communication connectivity in navigation, and core occupancy in traffic control. Across tasks, we examine whether attribution of a shared constraint supports task completion while maintaining constraint satisfaction. We compare against reward-only MAPPO and the constrained baselines MACPO and MAPPO-L from Gu et. al. [11]. Baseline optimization details are provided in Appendix A.

6.1

Experimental Setup

All methods use six training seeds and common evaluation resets within each benchmark. We compare task success, shared constraint satisfaction, and their joint occurrence, as well as task returns. All methods are trained with the same compute budget in each scenario in terms of simulation steps. Transport policies train with 15M sim steps, and evaluates on 500 common resets per obstacle condition. Navigation policie train with 15M sim steps, and evaluates on 128 common resets. Traffic policies train with 20M sim steps and evaluates on 1,000 common resets. In

8

0 0.4

0.7

1.0

40 20 0 0.6

Completed trips (MAPPO = 1)

0.8

40 20 0

1.0

0.4

Return (MAPPO = 1)

0.7

Ours

Transport: 2 obs. Safe success (%)

50

MAPPO-L

Transport: 1 obs. Safe success (%)

Navigation

100

Safe success (%)

Overload-free episodes (%)

Traffic

MACPO

1.0

Transport: 3 obs. Safe success (%)

MAPPO

20 10 0 0.4

Return (MAPPO = 1)

0.7

6 4 2 0

1.0

0.4

Return (MAPPO = 1)

0.7

1.0

Return (MAPPO = 1)

Figure 2: Constraint–performance tradeoffs across benchmarks. Points and error bars show means and sample standard deviations across six training seeds. Traffic reports overload-free episode percentages versus completed trips. Others report safe-success rates where goal was reached without constraint violation versus task return. x-axes metrics are normalized by MAPPO values. Note that the sub-plots zooms into parts of the y-range for better visibility and comparison, and hence have different y-axes ranges. MAPPO Return

MACPO 100

35.6 55.4

42.2

50

50

23.8

2 3 Obstacles Higher is better

0 1

16.2

20 3.5

0 1

40 17.4

13.1

0

Safe success (%)

82.0

104.06

100

Ours

Constraint satisfaction (%)

100

125.83 104.52

MAPPO-L

Goal success (%)

2 3 Obstacles Higher is better

0 1

2 3 Obstacles Higher is better

1

2 3 Obstacles Higher is better

Figure 3: Transport results across obstacle counts (mean ± SD over six training seeds). Labels are SafeDiSTL mean values. all benchmarks, SafeDiSTL uses the running max increment cost defined in Secion 5.1. All other benchmarks utilizes cost functions equivalent to the per step cost of the same STL specification. For example, in transport, SafeDiSTL’s STL specification says ”Always no collision between the payload and the obstacles”, the equivalent per step cost function is the overlapping margin in Euclidean distance between the payload and obstacles’ geometric shapes. Each method then pre-processes the cost functions according to the reference implementation. All experiments are conducted in JAX [4] on GPUs. We primarily examine four key metrics. 1. Task return: episodic sum of task reward that the policies achieve in evaluation. 2. Goal success rate: the percentage of episodes that leads to successful goal reaching. 3. Constraint satisfaction rate: the percentage of evaluation episodes that did not incur any constraint violations. 4. Safe success rate: the percentage of episodes that has the joint occurrence of goal success and constraint satisfaction. Environment details and policy architectures are provided in Appendices H and I, respectively.

9

t = 92

t = 141

t = 377

t = 440

Ours

MAPPO-L

MACPO

MAPPO

t=0

Agent 1 Agent 2 Agent 3 Package Obstacle Goal Figure 4: Example rollout comparison with baselines in the 1-obstacle transport scenario with common initial conditions.

6.2

The Constraint-performance Tradeoff

We first show the key result of the experiments. In Figure 2, we show that SafeDiSTL balances the tradeoff between constraint satisfaction and retaining performance. In each subplot, the y-axes shows constraint satisfaction metrics in percentages, and the x-axes shows performance metrics in normalized returns to those obtained by MAPPO. Our algorithm modifies MAPPO by introducing the dual on constraint and asymmetric cost attribution to individual agents, thus we want to show that SafeDiSTL retains the performance of MAPPO, but does so considering satisfying the shared constraints. In all five scenarios shown in Figure 2, SafeDiSTL balances this trade off by being in the top right quadrant of the plots, while other methods sacrifice MAPPO’s task performance to increase constraint satisfaction. Appendix E examines attribution, cost formulation, and dualoptimizer variants.

6.3

Cooperative Transport

We use a transport task with dynamics and control similar to the one in [3], where three force input agents push a shared package around circular obstacles towards a goal. The shared constraint here is package–obstacle clearance, and safe success requires both the payload reaching the goal and no contact between the payload and the obstacle throughout the entire episode. In this benchmark, we consider three different settings with 1-3 obstacles between the starting position and the payload 10

goal. Figure 3 shows the comparison between the four methods. SafeDiSTL has the highest mean safe success rate in all three settings: 35.6 ± 9.6%, 16.2 ± 11.0%, and 3.5 ± 2.3% with one, two, and three obstacles, respectively. MAPPO-L trails closest behind with 7.0 ± 3.7%, 4.5 ± 0.9%, and 2.2 ± 1.0%. With three obstacles, safe success remains low for all methods in this harder condition, yet SafeDiSTL still achieves highest safe success rate there. Although MAPPO has higher mean goal success in all three conditions, SafeDiSTL more often achieves the goal while satisfying the shared clearance requirement. MACPO on the other hand completely fails in all three settings. Full numerical results appear in Table 1. Figure 4 shows an example rollout comparison between the methods. The same trend shows up here as well: MAPPO reaches the goal, the two constrained baselines has degraded goal reaching capability, while SafeDiSTL manages to go around the obstacle and reaches the goal.

6.4

Connected Navigation

In this benchmark, we control four point-mass agents navigating through two staggered obstacle passages to a shared destination. The shared constraint is buffered full episode communication connectivity: at every timestep, the longest edge of the agents’ Euclidean minimum-spanning tree must not exceed 3.325 m. Goal success requires all agents to remain in the destination region during the final 20 control steps. Figure 6 reports the comparison between all four methods. SafeDiSTL has the highest mean goal success rate (71.88 ± 6.13%) and safe-success rate (43.88 ± 4.40%) among the four main methods. MAPPO-L attains slightly higher full episode constraint satisfaction rate than SafeDiSTL (56.64 ± 10.61% versus 54.69 ± 8.33%). MACPO reaches only 4.43 ± 1.96% safe successes. MAPPO has the highest mean return but almost always violates the constraint. These results show that in the connected navigation benchmark, considering the constraint effectively also helps with task success rate since grouping together through the narrow passage reduces accidental collision with the obstacle that might slow down goal reaching. Full numerical results appear in Table 2. Figure 5 also shows the same conclusion in matched rollout trajectories. SafeDiSTL agents grouped closely together and navigated smoothly towards the goal without any disconnects in the graph. The agents in all other methods disconnected at least once throughout the episode.

6.5

Networked Traffic Control

We consider a seven region Networked Macroscopic Fundamental Diagram (NMFD) traffic task [10, 19]. Six peripheral regions exchange destination labeled traffic through a shared central core. Each region meters its outgoing traffic, while core exits are uncontrolled and randomized at every time step. The shared constraint is on the core region’s occupancy. The flow rate of the core region is dictated by the cubic polynomial shown in Figure 7. The flow rate first increases as the number of vehicles in the region increases. After the peak, it drops down to the congestion limit, where the flow rate drops below 1 vehicle per second. Thus the shared constraint is set as ncore ≤ nsafe ≃ 8786.415. Vehicle admissions to the core therefore trade off completed trips against core region congestion, while restrictive metering can increase the wait time in the system. The traffic in the system is randomly spawned as source-destination pairing of two peripheral zones into the queue. All vehicles must travel through the core on their way to their destinations. The agents control their own regions’ flow rate for vehicles with all other peripheral regions as destination. Then the system revolves following the controlled core region in-flow rate, and the uncontrolled, randomized out-flow rate. The agents observe the randomize exit rate, and should react to changes for decisions on their control. For this task, since there isn’t a clear measure for success, we use these key metrics instead:

11

t = 91

t = 110

t = 175

Ours

MAPPO-L MACPO

MAPPO

t=0

Agent 1 Agent 2 Agent 3 Agent 4 Obstacle Goal Disconnected gap Figure 5: Example rollout comparison with baselines in the connected navigation benchmark with common initial conditions. 1. Completed trips: this is the equivalent to task return, where the policy uses as training reward. 2. Overload-free episode rate: the percentage of full episodes without overloading the core region. 3. Core vehicle-hours: the time that vehicles spends on average at the core region, this measures the system delay. 4. Time above core limit: the time that core regions has occupancy higher than the limit. Figure 8 compares all four methods. The training reward for all methods here are completed trips. The goal of this benchmark is to test the trade off between throughput and core congestion. Since core region exit rates are randomized, a smart team of agents should learn to coordinate when to let each destination’s vehicles go without overloading the core. SafeDiSTL retains 71.4% of MAPPO throughput while reducing the core vehicle-hours to 8.8% of MAPPO and the time above core limits to 0.3% of MAPPO. Although MACPO and MAPPO-L also learn to reduce constraint violation to the same level, they only retain 47.6% and 42.5% of the MAPPO throughput, respectively. Full numerical results appear in Table 3.

7

Limitations and Conclusions

We propose SafeDiSTL, a constrained MARL framework that allows for credit assignment under shared team constraints. Using STL robustness gradients, we derive a cost attribution scheme that decomposes the shared team constraints while preserving the total cost. These attributed costs are then incorporated in policy optimization for centralized training and decentralized execution. Across three diverse case studies on cooperative payload transport, connected navigation, and traffic 12

MAPPO

MACPO Goal success (%)

Return 125.11

100 0

71.88

0

Ours

Constraint satisfaction (%) 54.69

Safe success (%) 50

43.88

50

50

Higher is better

MAPPO-L

0

Higher is better

Higher is better

0

Higher is better

Figure 6: Navigation results (mean ± SD over six training seeds). Labels are SafeDiSTL mean values.

Agent 2 Agent 3

Agent 1

Core Agent 4

Agent 6

Flow (veh/s)

Core limit 6

0

0

8,786

Vehicles

Agent 5

6-D control actor

Uncontrolled exits

Figure 7: Seven region traffic network with a shared core occupancy constraint. Controls for each agent is a 6-D vector that controls the flow rate for all 6 destinations (0 always for self). network control, SafeDiSTL shows a strong improvement in handling shared constraints over the other state-of-the art MARL baselines. First, while SafeDiSTL has shown an exceptional safety performance tradeoff in benchmarks, it relies on the gradients of the robustness signal through the system dynamics. The dynamics gradients might be hard to come by in contact-rich scenarios. Even with non-differentiable dynamics, we can still estimate via finite differences by using more calls to the simulation. Future extensions should aim to mitigate this issue by devising gradient-free signals for STL robustness decomposition. Second, our sensitivity metric used to allocate costs is the magnitude of influence. Future work could also consider how to incorporate the direction of influence. Third, we did not show benchmarks on higher fidelity robotic scenarios, and potential transfer of learned policies to real robots. Future works will include validation of the proposed method on real-world robotic platforms.

13

MAPPO Completed trips 1.0

0.714

0.5 0.0

Higher is better (MAPPO = 1)

MACPO

MAPPO-L

Overload-free episodes (%) 100

Ours

Core vehicle-hours

97.45

1.0

1.0

50

0.5

0

0.0

Higher is better

Time above core limit

0.5 0.088

Lower is better (MAPPO = 1)

0.0

0.003

Lower is better (MAPPO = 1)

Figure 8: Traffic results (mean ± SD over six training seeds). Labels are SafeDiSTL mean values.

References [1] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. 2017. Constrained Policy Optimization. In Proceedings of the 34th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 70). 22–31. [2] Eitan Altman. 1995. Constrained Markov Decision Processes. Technical Report RR-2574. INRIA. [3] Matteo Bettini, Ryan Kortvelesy, Jan Blumenkamp, and Amanda Prorok. 2022. VMAS: A Vectorized Multi-Agent Simulator for Collective Robot Learning. The 16th International Symposium on Distributed Autonomous Robotic Systems (2022). [4] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Yash Katariya, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye WandermanMilne, and Qiao Zhang. 2018. JAX: composable transformations of Python+NumPy programs. http://github.com/jax-ml/jax [5] Sirui Chen, Zhaowei Zhang, Yaodong Yang, and Yali Du. 2023. STAS: Spatial-Temporal Return Decomposition for Multi-agent Reinforcement Learning. arXiv preprint arXiv:2304.07520 (2023). https://arxiv.org/abs/2304.07520 [6] Ryan K. Cosner, Yuxiao Chen, Karen Leung, and Marco Pavone. 2023. Learning Responsibility Allocations for Safe Human-Robot Interaction with Applications to Autonomous Driving. In 2023 IEEE International Conference on Robotics and Automation. [7] Alexandre Donzé and Oded Maler. 2010. Robust Satisfaction of Temporal Logic over RealValued Signals. In Formal Modeling and Analysis of Timed Systems, Krishnendu Chatterjee and Thomas A. Henzinger (Eds.). Springer, Berlin, Heidelberg, 92–106. doi:10.1007/ 978-3-642-15297-9_9 [8] Goergios Fainekos. 2008. Robustness of Temporal Logic Specifications. PhD Thesis. University of Pennsylvania. http://www.public.asu.edu/~gfaineko/pub/fainekos_thesis.pdf

14

[9] Jakob N. Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. 2018. Counterfactual Multi-Agent Policy Gradients. In Proceedings of the ThirtySecond AAAI Conference on Artificial Intelligence. 2974–2982. [10] JW Godfrey. 1969. The mechanism of a road network. Traffic Engineering & Control 8, 8 (1969). [11] Shangding Gu, Jakub Grudzien Kuba, Yuanpei Chen, Yali Du, Long Yang, Alois Knoll, and Yaodong Yang. 2023. Safe multi-agent reinforcement learning for multi-robot control. Artificial Intelligence 319 (June 2023), 103905. doi:10.1016/j.artint.2023.103905 [12] Parv Kapoor, Kazuki Mizuta, Eunsuk Kang, and Karen Leung. 2025. STLCG++: A Masking Approach for Differentiable Signal Temporal Logic Specification. IEEE Robotics and Automation Letters 10, 9 (Sept. 2025), 9240–9247. doi:10.1109/LRA.2025.3588389 [13] Karen Leung, Nikos Aréchiga, and Marco Pavone. 2023. Backpropagation through Signal Temporal Logic Specifications: Infusing Logical Structure into Gradient-Based Methods. The International Journal of Robotics Research 42, 6 (2023), 356–370. doi:10.1177/02783649221082115 [14] Jiajing Ling, Arambam James Singh, Nguyen Duc Thien, and Akshat Kumar. 2023. Constrained Multiagent Reinforcement Learning for Large Agent Population. In Machine Learning and Knowledge Discovery in Databases, Massih-Reza Amini, Stéphane Canu, Asja Fischer, Tias Guns, Petra Kralj Novak, and Grigorios Tsoumakas (Eds.). Springer Nature Switzerland, Cham, 183–199. doi:10.1007/978-3-031-26412-2_12 [15] Yiwei Lyu, Wenhao Luo, and John M. Dolan. 2023. Risk-Aware Safe Control for Decentralized Multi-Agent Systems via Dynamic Responsibility Allocation. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems. 9737–9744. [16] Oded Maler and Dejan Nickovic. 2004. Monitoring Temporal Properties of Continuous Signals. In Proceedings of FORMATS-FTRTFT (LNCS, Vol. 3253). 152–166. [17] Yoshihiro Okawa, Hayato Dan, Natsuki Morita, and Masatoshi Ogawa. 2023. Multi-Agent Reinforcement Learning with Information-sharing Constrained Policy Optimization for Global Cost Environment. IFAC-PapersOnLine 56, 2 (Jan. 2023), 1558–1565. doi:10.1016/j. ifacol.2023.10.1854 [18] Yash Vardhan Pant, Houssam Abbas, and Rahul Mangharam. 2017. Smooth operator: Control using the smooth robustness of temporal logic. In 2017 IEEE Conference on Control Technology and Applications (CCTA). 1235–1240. doi:10.1109/CCTA.2017.8062628 [19] Renukanandan Tumu, Wenceslao Shaw Cortez, Ján Drgoňa, Draguna L. Vrabie, and Sonja Glavaski. 2024. Differentiable Predictive Control for Large-Scale Urban Road Networks. arXiv:2406.10433 [eess.SY]. doi:10.48550/arXiv.2406.10433 [20] Jiangwei Wang, Shuo Yang, Ziyan An, Songyang Han, Zhili Zhang, Rahul Mangharam, Meiyi Ma, and Fei Miao. 2025. Multi-Agent Reinforcement Learning Guided by Signal Temporal Logic Specifications. In 2025 IEEE/RSJ International Conference on Intelligent Robots and Systems. 6048–6054. doi:10.1109/IROS60139.2025.11246629 [21] Yaodong Yang, Jianye Hao, Guangyong Chen, Hongyao Tang, Yingfeng Chen, Yujing Hu, Changjie Fan, and Zhongyu Wei. 2020. Q-value Path Decomposition for Deep Multiagent 15

Reinforcement Learning. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 119). 10706–10715. https:// proceedings.mlr.press/v119/yang20d.html [22] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. 2022. The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games. In Advances in Neural Information Processing Systems. doi:10.52202/068431-1787 [23] Weiye Zhao, Rui Chen, Yifan Sun, Feihan Li, Tianhao Wei, and Changliu Liu. 2024. State-wise Constrained Policy Optimization. Transactions on Machine Learning Research (2024). [24] Hongrui Zheng, Zirui Zang, Ahmad Amine, Cristian Ioan Vasile, and Rahul Mangharam. 2026. STL-SVPIO: Signal Temporal Logic guided Stein Variational Path Integral Optimization. arXiv:2603.13333 [cs.RO]. doi:10.48550/arXiv.2603.13333

16

A

Baseline Optimization Details

This appendix gives the optimization details summarized in Section 4.2. Equation 6 is a firstorder Lagrangian template, not the update rule of every constrained policy optimizer. CPO [1] distinguishes this stateful multiplier update from its constrained trust-region subproblem, whose multipliers are solved anew at each iteration. SafeMARL extends constrained policy optimization to cooperative Markov games through MACPO and MAPPO-Lagrangian [11].

A.1

MACPO

Multi-Agent Constrained Policy Optimisation (MACPO) updates decentralized actors sequentially, accounting for the policies of agents already updated in the current iteration [11]. Each actor maximizes a reward surrogate subject to cost constraints and a Kullback–Leibler (KL) trust region. Thus, coordination enters the sequential surrogate rather than a simultaneous update of all actors using a fixed cost penalty. In the shared-cost notation of Equation 4, the local CPO-style approximation for agent i has the form [1] max gi⊤ ∆θi , ∆θi

subject to

c i + b⊤ i ∆θi ≤ 0,

(21)

⊤ 1 2 ∆θi Hi ∆θi ≤ δi .

Here gi and bi are gradients of the sequential reward and shared-cost surrogates, ci is the current surrogate cost minus d, Hi is the local Hessian of the mean KL divergence, and δi > 0 is the trust-region radius. These quantities are evaluated at the current actor parameters, with preceding actors’ updates accounted for in the surrogates. Linearizing reward and cost while quadratically approximating KL yields a constrained natural-gradient step. For invertible Hi and a positive trust-region multiplier ηi , its direction satisfies ∆θi⋆ = ηi−1 Hi−1 (gi − νi bi ), θinew = θiold + αi ∆θi⋆ ,

(22)

where νi ≥ 0 enforces the local cost constraint and αi ∈ (0, 1] is selected by backtracking. Unlike the stateful λk in Equation 6, these subproblem multipliers are solved anew for each actor update. MACPO uses a cost-reducing recovery step when the constrained update is infeasible [11]. Multiple budgets add linearized cost constraints to Equation 21. The theoretical sequential procedure provides reward-improvement and cost-feasibility bounds under its assumptions; sampling error, local approximations, and finite line searches mean that practical neural-policy updates do not guarantee constraint satisfaction on every trajectory.

A.2

MAPPO-Style Lagrangian Surrogates

A first-order Lagrangian implementation replaces the exact policy gradient in Equation 6 with a sample-based surrogate using reward and cost advantages. Let AR,t and AC,t be reward and shared-cost advantage estimates obtained from centralized critics. For the decentralized actor of agent i, define Aλi,t = AR,t − λk AC,t , (23) πθi (ai,t | oi,t ) qi,t (θi ) = . πθi,k (ai,t | oi,t ) 17

Table 1: Supplementary Transport results compared to baselines. Entries are mean ± sample SD across six seeds and 500 common resets per seed. Rates are percentages. Safe success denotes joint occurrence of goal reaching and shared-constraint satisfaction. Obstacles

Algorithm

Return

Goal success

Constraint satisfaction

Safe success

1 1 1 1

MAPPO MACPO MAPPO-L Ours

133.68 ± 7.96 49.25 ± 2.23 105.49 ± 5.40 125.83 ± 10.24

75.7 ± 13.7 0.0 ± 0.0 33.9 ± 4.8 42.2 ± 9.7

10.4 ± 3.8 9.1 ± 3.9 33.4 ± 2.5 82.0 ± 5.9

8.8 ± 4.4 0.0 ± 0.0 7.0 ± 3.7 35.6 ± 9.6

2 2 2 2

MAPPO MACPO MAPPO-L Ours

111.98 ± 4.19 49.65 ± 0.91 102.56 ± 4.15 104.52 ± 8.15

38.6 ± 8.6 0.0 ± 0.0 26.6 ± 3.6 23.8 ± 12.5

4.5 ± 1.9 8.0 ± 3.4 22.8 ± 4.0 55.4 ± 13.6

2.5 ± 1.3 0.0 ± 0.0 4.5 ± 0.9 16.2 ± 11.0

3 3 3 3

MAPPO MACPO MAPPO-L Ours

106.49 ± 3.50 48.69 ± 1.27 98.79 ± 4.35 104.06 ± 6.74

17.9 ± 8.3 0.0 ± 0.0 17.1 ± 4.3 13.1 ± 6.6

2.6 ± 2.2 7.5 ± 5.9 21.2 ± 5.1 17.4 ± 12.4

1.0 ± 0.8 0.0 ± 0.0 2.2 ± 1.0 3.5 ± 2.3

A MAPPO-style clipped surrogate for a fixed multiplier is  b i,t min{qi,t (θi )Aλ , Lbclip (θ) = E i,t

 clip(qi,t (θi ), 1 − ϵ, 1 + ϵ)Aλi,t } ,

(24)

where ϵ > 0 is the clipping threshold and the empirical expectation is over valid on-policy samples. Centralized critics may access st , while execution uses only oi,t . Homogeneous agents can share actor parameters without changing the factorized action sampling. Multiple constraints introduce one nonnegative multiplier per budget and a sum of cost-advantage terms. The surrogate above illustrates the reward–cost combination rather than specifying every detail of MAPPO-L. The Algorithm-3 MAPPO-L baseline used in our experiments updates independent actors sequentially and resets its nonnegative multipliers at each actor’s optimization phase; its cost objectives and budgets are specified with each benchmark. Reward-only MAPPO omits the cost term. SafeDiSTL uses attributed cost advantages instead of the broadcast shared-cost advantage, as described in Section 5. Clipping and a finite number of stochastic primal–dual updates do not enforce exact feasibility at each iteration. In particular, this first-order implementation does not inherit CPO’s trust-region bounds or the guarantees of SafeMARL’s theoretical sequential update. Moreover, broadcasting AC,t supplies no explicit differentiation of constraint responsibility across agents. Section 5 replaces this broadcast signal with trajectory-dependent attribution while retaining the exact shared constraint for dual accounting.

B

Supplementary Transport Results

Table 1 provides the numerical results plotted in Figure 3.

18

Table 2: Supplementary Navigation results compared to baselines. Entries are mean ± sample SD across six seeds and 128 common resets per seed. Goal success, constraint satisfaction, and safe success are percentages; safe success requires both goal achievement and whole-episode connectivity. Safe return assigns zero to unsafe episodes; final 20 step distance is in meters. Algorithm

Return

Goal success Constraint Safe success (%) satisfaction (%) (%)

MAPPO 130.43 ± 3.38 51.17 ± 3.31 MACPO 90.32 ± 9.70 11.85 ± 5.79 MAPPO-L 114.14 ± 8.71 52.99 ± 12.67 Ours 125.11 ± 8.80 71.88 ± 6.13

Safe return

Final 20 Step distance

0.91 ± 1.04 0.78 ± 0.99 1.49 ± 1.72 31.25 ± 4.39 4.43 ± 1.96 29.24 ± 3.29 56.64 ± 10.61 32.81 ± 8.62 69.80 ± 10.19 54.69 ± 8.33 43.88 ± 4.40 75.31 ± 10.50

2.14 ± 0.16 2.59 ± 0.23 1.84 ± 0.27 1.83 ± 0.30

Table 3: Supplementary Traffic results relative to MAPPO (column-wise MAPPO mean = 1). Mean ± SD across six training seeds; 1,000 common reset scenarios per policy. Higher completed trips and lower values in all other columns are preferable. Method

Completed trips

Network vehicle-hours

Core vehicle-hours

MAPPO MACPO MAPPO-L Ours

1.000 ± 0.012 0.476 ± 0.007 0.425 ± 0.016 0.714 ± 0.066

1.000 ± 0.001 1.053 ± 0.001 1.058 ± 0.002 1.029 ± 0.007

1.000 ± 0.041 1.000 ± 0.081 0.091 ± 0.002 0.000 ± 0.000 0.104 ± 0.007 0.00074 ± 0.00180 0.088 ± 0.018 0.000061 ± 0.000053

C

Episode-max core cost

Time above core limit 1.000 ± 0.010 0.000 ± 0.000 0.009 ± 0.023 0.003 ± 0.004

Supplementary Navigation Results

Table 2 provides the numerical results plotted in Figure 6, together with safe return and final-20 distance.

D

Supplementary Traffic Results

Table 3 retains the full traffic metrics, complementing Figure 8.

E

Ablation Studies

We ablate responsibility attribution, the cost formulation, and the dual optimizer. The four variants use uniform attribution with either max-incremental cost or step cost, with fixed-step or Adam multiplier updates. Max-incremental cost is the same incremental maximum cost ∆ct defined for SafeDiSTL in Equation 10; step cost uses positive per-transition violation. Labels without “+ Adam” use fixed-step multiplier updates. Ours retains sensitivity-based attribution with maxincremental cost. The Ours rows are repeated from the main tables, with the same evaluation protocols and seed-level aggregation. Results of ablations are presented in Tables 4, 5 and 6.

F

Robustness Differentiation

We write the differentiable dynamics as st+1 = F (st , at ), with sampled disturbances held fixed. The norm in Equation (12) is over the action coordinates of agent i. Differentiating negative robustness

19

Table 4: Two-dimensional transport ablations for one through three obstacles. Rates are percentages; entries are mean ± sample SD across six training seeds, with 500 common resets per seed. All three Ours rows are copied unchanged from Table 1. Obstacles 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3

Algorithm Uniform attribution Max-incremental cost Uniform attribution Max-incremental cost + Adam Uniform attribution Step cost Uniform attribution Step cost + Adam Ours Uniform attribution Max-incremental cost Uniform attribution Max-incremental cost + Adam Uniform attribution Step cost Uniform attribution Step cost + Adam Ours Uniform attribution Max-incremental cost Uniform attribution Max-incremental cost + Adam Uniform attribution Step cost Uniform attribution Step cost + Adam Ours

Return

Goal success

Shared constraint sat.

Safe success

58.91 ± 8.30

0.5 ± 0.8

74.4 ± 6.3

0.2 ± 0.4

70.00 ± 26.21

8.4 ± 8.7

75.3 ± 6.5

5.6 ± 7.7

46.81 ± 10.14

0.0 ± 0.0

57.7 ± 9.1

0.0 ± 0.0

44.26 ± 5.41

0.0 ± 0.0

58.6 ± 11.7

0.0 ± 0.0

125.83 ± 10.24

42.2 ± 9.7

82.0 ± 5.9

35.6 ± 9.6

59.40 ± 6.96

0.7 ± 1.4

61.8 ± 8.9

0.2 ± 0.3

80.63 ± 23.60

6.5 ± 5.8

73.3 ± 10.1

4.1 ± 4.0

38.41 ± 3.55

0.0 ± 0.0

60.1 ± 18.6

0.0 ± 0.0

44.65 ± 7.49

0.0 ± 0.0

52.1 ± 13.1

0.0 ± 0.0

104.52 ± 8.15

23.8 ± 12.5

55.4 ± 13.6

16.2 ± 11.0

52.54 ± 10.11

0.0 ± 0.0

62.2 ± 4.1

0.0 ± 0.0

81.79 ± 12.46

1.7 ± 1.1

70.8 ± 6.4

0.6 ± 0.7

42.93 ± 3.33

0.0 ± 0.0

50.1 ± 15.6

0.0 ± 0.0

44.66 ± 6.93

0.0 ± 0.0

54.6 ± 15.6

0.0 ± 0.0

104.06 ± 6.74

13.1 ± 6.6

17.4 ± 12.4

3.5 ± 2.3

rather than its rectified violation avoids an additional zero-gradient region when the smoothed trajectory is safe; the allocated cost is nevertheless zero whenever the exact C ϕ (τ ) is zero. Attribution normalizationPin implementation. Let It contain the active agents at valid decision time t, and let Zt = i∈It zi,t . The sum in Equation (13) excludes inactive entries. With numerical threshold εg > 0, the masked normalization is   zi,t /Zt , i ∈ It , Zt > εg , wi,t = 1/|It |, i ∈ It , Zt ≤ εg ,   0, i∈ / It .

(25)

P The uniform fallback handles finite, uninformative sensitivities and preserves i wi,t = 1 at each valid time with at least one active agent. Invalid padding receives zero weight; allocation assumes a nonempty active set at every cost-bearing transition. The factor N in Equation (14) corresponds to the fixed team-size mean, including zero contributions from inactive agents. Nonfinite active derivatives are flagged rather than assigned uniform credit. Complete episodes are required before 20

Table 5: Navigation ablations. Metrics and evaluation resets match Table 2; Ours is copied unchanged. Entries are mean ± sample SD across six training seeds. Goal, constraint-satisfaction, and safe-goal rates are percentages; final-20 distance is in meters. Algorithm

Return

Goal (%)

Safe (%) Safe goal (%)

Uniform attribution 126.77 ± 9.41 54.30 ± 15.19 2.60 ± 2.55 Max-incremental cost Uniform attribution 128.58 ± 5.08 50.52 ± 13.01 0.39 ± 0.65 Max-incremental cost + Adam Uniform attribution 39.60 ± 22.40 12.63 ± 9.34 90.36 ± 4.57 Step cost Uniform attribution 129.38 ± 15.43 61.33 ± 20.97 11.98 ± 8.81 Step cost + Adam Ours 125.11 ± 8.80 71.88 ± 6.13 54.69 ± 8.33

Safe return Final-20 distance

2.60 ± 2.55

4.21 ± 4.19

2.13 ± 0.34

0.39 ± 0.65

0.65 ± 1.10

2.17 ± 0.29

11.98 ± 9.11 36.42 ± 20.95

5.29 ± 1.66

10.16 ± 9.40 19.28 ± 14.75

1.94 ± 0.43

43.88 ± 4.40 75.31 ± 10.50

1.83 ± 0.30

Table 6: Traffic ablations. Values use the same fixed, column-wise MAPPO mean as Table 3; Ours is copied unchanged. Mean ± sample SD across six training seeds and 1,000 common resets per policy. Higher completed trips and lower values in all other columns are preferable. Method

Completed trips

Uniform attribution Max-incremental cost Uniform attribution Max-incremental cost + Adam Uniform attribution Step cost Uniform attribution Step cost + Adam Ours

Network vehicle-hours

Core vehicle-hours

Episode-max core cost

Time above core limit

0.786 ± 0.018 1.021 ± 0.002 0.079 ± 0.017

0.00031 ± 0.00058

0.005 ± 0.009

1.002 ± 0.010 1.000 ± 0.001 1.011 ± 0.076

1.002 ± 0.111

1.000 ± 0.010

0.388 ± 0.235 1.063 ± 0.025 0.065 ± 0.038 0.00000049 ± 0.00000076 0.000041 ± 0.000063 0.881 ± 0.033 1.011 ± 0.003 0.837 ± 0.050

0.788 ± 0.082

0.985 ± 0.012

0.714 ± 0.066 1.029 ± 0.007 0.088 ± 0.018

0.000061 ± 0.000053

0.003 ± 0.004

full-episode sensitivities and attribution targets can be finalized, even though the cost allocation is time-local. Sensitivity norms discard derivative direction, and attribution depends on the model, action parameterization, and smoothing scale. Conservation of scalar cost does not make the attributed policy gradient an unbiased estimator of the original shared-cost gradient. The exact minimum can concentrate its derivative on a single predicate and time. For the always-conjunction in Equation (8), we use the log-sum-exp approximation ρeϕβ (τ ) = −

TX K τ −1 X
1 log exp −βgj (st+1 ) , β

(26)

t=0 j=1

where β > 0 controls smoothing. Other supported Boolean and temporal compositions use their corresponding smooth minimum or maximum. The surrogate supplies derivatives only: its value and sign do not replace the exact cost or the exact satisfaction test.

G

SafeDiSTL Optimization and Implementation Details

G.1

Cost advantages and critic losses

The hybrid cost critic consists of a centralized predictor VCg (st , cmax,t−1 ) and a shared localobservation predictor VCi (oi,t , cmax,t−1 ), evaluated separately for each agent. The local heads predict expected remaining cumulative attributed costs from e ci,t and the global head predicts 21

their team mean from ct , defined in Equation (16), with the numerical scale below. Their learned outputs are not an exact decomposition by architecture. The regression targets in Equation (18) use unnormalized GAE estimates and rollout-time value predictions, and are held fixed during critic fitting. Cost prediction and GAE use the same fixed numerical scale κC > 0 on both e ci,t and ct . Let bt be one if the episode continues after transition t, and zero at either termination or the finite-horizon endpoint. With cost discount one, the agentspecific temporal-difference residual and generalized advantage estimate are C δi,t = κC e ci,t + bt VCi (oi,t+1 , cmax,t ) − VCi (oi,t , cmax,t−1 ),

AC i,t =

TτX −1−t

(27)

ℓ C ηC δi,t+ℓ ,

ℓ=0

where ηC ∈ [0, 1] is the cost trace-decay parameter. The global cost estimate uses the same recursion with ct and VCg . Cost targets do not bootstrap beyond the completed episode. The GAE-based C and y C are defined in Equation (18), using fixed rollout-time value predictions. cost targets yi,t g,t The cost critic is trained with clipped squared-error value losses and a consistency penalty: X  C b t ℓv (V g , y C ) + 1 LC = E ℓv (VCi , yi,t ) C g,t N +ζ

1 N

X

i g
2  i VC − VC .

(28)

i

Here ℓv clips changes relative to the rollout-time value prediction, and ζ ≥ 0 controls consistency. This regularizer encourages agreement of the predicted mean with the global prediction; Equation 15 holds for the allocated costs independently of critic accuracy, not necessarily for the learned values or generalized advantage targets.

G.2

Actor normalization and individual constraints

loc If agent i also has local constraints indexed by j, let Aloc C,i,j,t and λi,j denote their separately estimated, scaled cost advantages and multipliers. We form   X loc  Anorm = N AR,t − λk AC λloc (29) i,t i,t − i,j AC,i,j,t , j

where N denotes normalization of the combined advantage over valid actor samples. The implementation substitutes this normalized advantage into Equation (20) and adds an entropy bonus during optimization. Individual obstacle and workspace costs do not enter the shared robustness gradient or its normalization. They retain their own critics, budgets, and dual updates. Thus, attributing a payload violation cannot erase an individual robot’s constraint. For a local clearance ℓi,j,t and required buffer ∆j , the local signal is cloc i,j,t = [∆j − ℓi,j,t ]+ .

(30)

Each local dual uses the mean raw deficit of its own agent and channel over active transitions, not an average across teammates. These are stepwise budgets, distinct from the shared episode-maximum budget. The local critic uses its configured discounted cost return and bootstraps clean horizon truncations, whereas the completed-episode shared STL return does not. In the three-dimensional suites, both local buffers are 0.05 m, local cost discount and trace decay are 0.99 and 0.95, and local multipliers use projected budget-relative updates with stepsize 10−3 and cap two. 22

G.3

Shared multiplier update

The shared multiplier is updated from the mean exact, unallocated cost of completed episodes. In the budget-relative, fixed-step configuration, the update is k X bk = 1 C C ϕ (τb ), Bk

B

b=1

bk − d C λk+1 = clip λk + ηλ , 0, λmax d

!

(31) ,

with positive d and Bk completed episodes in the dual-update window. Neither κC nor the attribution weights change this physical-unit constraint statistic. The finite multiplier cap is a practical optimization choice, not an exact solution of the unrestricted saddle-point problem.

H

Supplementary Experimental Details

H.1

Collaborative Transport

The transport environment contains three force-controlled agents, an unactuated nonrotating square package, and circular obstacles in a planar workspace. The package has side length 0.15 m and mass 50; each agent has mass one and radius 0.03 m, and each obstacle has radius 0.10 m. Each agent selects a normalized two-dimensional action in [−1, 1]2 , scaled by 0.6 to produce the applied force. The differentiable VMAS-style simulator uses float64 smooth contact, and four 0.025 s physics substeps per control step. Episodes last 500 control steps. Resets sample one of eight layouts, apply a random quarter-turn and reflection, jitter each obstacle by at most 0.015 m per coordinate, and randomize the agents’ phase around the package. The layouts obstruct the direct route while providing detours. The shared constraint margin is the package-box signed distance to each obstacle, minus the obstacle radius and the required 0.02 m clearance. Goal achievement uses the task’s box-distance threshold of approximately 0.1567 m rather than a point-payload center-distance test. The shared reward combines distance-progress shaping scaled by 100 with the campaign’s approach and jointpush coordination terms, held fixed across algorithms. Package contact is logged separately; it neither adds a reward penalty nor terminates the episode.

H.2

Connected Navigation

Four homogeneous planar agents navigate from a compact start formation to a shared circular destination through two staggered obstacle passages. The canonical corridor is 18 m long and 10 m wide; ten static circular obstacles form two five-obstacle barriers. Agent and obstacle radii are 0.75 m and 0.8 m, respectively. Resets randomize barrier locations, opening centers, and opening widths (3.4–3.8 m), perturb the start formation and destination, and apply a global rotation, reflection, and translation. Agents use bounded two-dimensional acceleration commands, maximum speed 1.5 m/s, smooth contact forces, five physics substeps per 0.1 s control step, and a 250-step horizon. The shared reward combines reduction in mean agent-to-goal distance, scaled by 5/R, with the fraction of agents inside the destination. Goal success requires all four agents to remain within the 2.6 m goal radius throughout the final 20 control steps. The formal constraint is whole-episode buffered graph connectivity. Let bu be the longest edge in the Euclidean minimum-spanning tree of the agent positions at checked instant u. For transition 23

t, let Ut contain its source and five physics-substep endpoints. With communication radius R = 3.5 m and buffer fraction ξ = 0.05, bu =

max (i,k)∈MST(xu )

∥xi,u − xk,u ∥2 ,

R(1 − ξ) − bu . u∈Ut ξR

(32)

mt = min

The buffered check requires mt ≥ 0 for every transition, equivalently a checked bottleneck no larger than R(1 − ξ) = 3.325 m. The 0.175 m buffer exceeds the maximum relative displacement of 0.06 m between substep checks, satisfying the bounded-speed certificate condition. A safe episode passes every buffered check; a safe goal additionally satisfies the goal criterion. Smooth contacts do not count as connectivity violations, and separate obstacle and boundary cost channels are disabled. Disconnection does not terminate an episode.

H.3

Networked Traffic Control

The traffic task is a seven-region NMFD network with six peripheral regions and a shared core. Direct peripheral-to-peripheral transfers are disabled. Each region uses the cubic production function G(n) = 4.133 × 10−11 n3 − 8.282 × 10−7 n2 + 0.0042n, (33) where n is occupancy in vehicles and G is in vehicles/s. Episodes contain 240 control intervals of 30 s, each integrated with ten RK4 substeps. Demand is five times the reference setting: 0.625 vehicles/s per nonlocal peripheral origin–destination pair, with ±20% reset randomization. Three destinations receive low exit baselines of 0.1 and three receive high baselines of 0.9, randomly permuted at reset; temporal noise and incidents vary core exits within [0, 1]. Agent i controls a six-dimensional admission vector ui ∈ [0, 1]6 . Coordinate uid meters traffic in its region bound for destination d into the core; the self-destination coordinate is masked, leaving five effective controls. If xid is the commodity occupancy and ni the region total, its core-entry rate is uid (xid /ni )G(ni ), with zero flow for an empty region. The shared reward is completed trips per interval divided by 100. The core constraint is n0 ≤ nsafe , where nsafe ≃ 8786.415 is the descending-branch solution of G(n) = 1.

I

Observations and Policy Network Architectures

This section describes the actor inputs and policy networks used in the reported benchmarks.

I.1

Cooperative Transport

For agent i, the observation concatenates its absolute planar position and velocity (four coordinates), package position minus goal position (two), package position relative to the agent (two), absolute package velocity (two), and a binary package-on-goal indicator (one). It then includes the relative position of each of the K obstacles (2K coordinates) and the relative position and velocity of each of the other two agents (eight coordinates), ordered by agent index. Thus the observation dimension is 19 + 2K, giving 21, 23, and 25 inputs for the one-, two-, and three-obstacle conditions. The nonrotating package contributes no orientation features, and no assigned push-slot features are appended. Actor inputs are standardized using running means and variances estimated during training and clipped to [−10, 10]; evaluation uses the saved normalization statistics without updating them. 24

The actor is a feed-forward multilayer perceptron with two 64-unit hidden layers, tanh activations, and a linear two-dimensional Gaussian-mean head. A learned, observation-independent logstddev vector specifies the diagonal covariance. Training samples a latent Gaussian action and applies tanh to obtain the normalized force command in [−1, 1]2 ; deterministic evaluation applies tanh to the mean. The simulator multiplies this command by 0.6. MAPPO, SafeDiSTL, and the uniform-attribution variants share one actor across the three agents; MAPPO-L and MACPO use separate actor parameters for each agent with the same layer sizes and action parameterization.

I.2

Connected Navigation

Each agent receives a 72-dimensional observation. The first 34 coordinates comprise its own planar position and velocity (four), normalized episode time (one), four relative target positions (eight), and three teammate slots (21). The four target entries refer to the shared destination. Each teammate slot contains relative position and velocity from the stored communication packet, a direct-neighbor indicator, a connected-component reachability indicator, and packet age; slots follow the agents’ fixed identifiers within the episode. The remaining 38 coordinates describe the ten obstacles using relative position and radius (30), the four corridor-boundary clearances (four), and the flattened two-dimensional world-rotation matrix (four). Positions, relative distances, obstacle radii, and boundary clearances are divided by 10; velocities are divided by the maximum speed of 1.5; time and packet ages are divided by the 250-step horizon. These features are then standardized using running observation statistics and clipped to [−10, 10], with the saved statistics held fixed during evaluation. The actor maps these 72 inputs through two 64-unit tanh hidden layers to a linear twodimensional Gaussian-mean head. It uses a learned, observation-independent diagonal logstandard-deviation vector and tanh-bounded actions in [−1, 1]2 . Deterministic evaluation uses the transformed mean. The simulator additionally clips the command’s Euclidean norm to one before applying the acceleration scale. MAPPO, SafeDiSTL, and the uniform-attribution variants share actor parameters across the four agents, whereas MAPPO-L and MACPO use one independently parameterized actor per agent with the same network dimensions. The policies are feed-forward; communication packet contents and ages are explicit observation features, not a recurrent policy state.

I.3

Networked Traffic Control

Each peripheral agent receives 31 observation coordinates: its six destination-specific queues, six local origin–destination demand rates, six destination-specific queues in the shared core, six current effective core-exit factors, normalized episode time, and a six-dimensional one-hot agent identity. Queue occupancies are divided by 1,800; demand rates and exit factors are used directly, and time is divided by the 240-step horizon. The core queues and exit factors are broadcast to all six agents. The observation excludes the latent variables driving future exit disturbances. The identity is already part of the environment observation, so the learner does not append another identity vector. There is no additional running observation normalization, and actor inputs use float32 arithmetic. The actor has two 64-unit tanh hidden layers and a linear six-dimensional Gaussian-mean head, with a learned, observation-independent log-standard-deviation vector. A sigmoid transforms each latent Gaussian sample into an admission command in [0, 1]. The self-destination coordinate is masked to zero, leaving five effective controls per agent; deterministic evaluation applies the same sigmoid and mask to the mean. MAPPO, SafeDiSTL, and the uniform-attribution variants share

25

one actor across the six agents. MAPPO-L and MACPO instead maintain six independent actors with the same input features, hidden-layer sizes, and action transform.

26

Related documents

• SafeDiSTL: Decomposing Joint Constraints for Safe Multi-Agent Reinforcement Learning#1298233
• Learning to Report Unsafe Tasks in a Multi-Agent Game#1233041
• Evaluation Metrics for Safe Reinforcement Learning#1109345
• Task Decomposition with Multi-Agent Systems#642208
• Safe-Support Q-Learning: Learning without Unsafe Exploration#141500