When several robots or controllers share a physical space, each one's safe actions depend on what the others do and on parts of the world it cannot see. Two agents must not collide, and a leg must not push a shared body into a wall. The usual fixes are poor fits for this setting. Penalty methods add a learned cost weight to the reward, and those weights oscillate between recklessness and timidity. Exact projection onto the safe set is expensive and needs a global view of the state that no single agent has. This proposal borrows a tool from constrained optimization: describe the safe set as the set of points left unchanged by a cheap "nudge" operator, then enforce safety by applying that nudge a few times. Concretely, each agent takes its proposed action and repeatedly applies a one-line correction step toward satisfying the constraints it believes are active, swapping corrected actions with its neighbors in between. After a small, fixed number of rounds, it executes the result.
The question is how safe such a truncated, decentralized correction can be when every agent evaluates the constraints on its own noisy belief about the hidden state. We will prove and measure a two-term answer. The residual constraint violation is the sum of a part that shrinks geometrically with the number of correction rounds and a floor set by how wrong the agents' beliefs are. This recasts the familiar trade between convergence speed and accuracy. Once the agents run a handful of rounds, extra rounds or smaller step sizes stop helping. Only better information helps, meaning belief sharing or constraint margins scaled to uncertainty. If this holds, it tells practitioners where to spend their communication and compute budget.
Core Claim
A constraint set $C$ can be written as the fixed-point set $\mathrm{Fix}(T)=\{a: T(a)=a\}$ of an operator $T$ that moves infeasible points toward $C$ without pushing any point farther from $C$. Operators with this property are called quasi-nonexpansive. For a convex constraint $g(a)\le 0$ on an action $a$, the standard choice is the subgradient projection
$$T_g(a) = a - \frac{\max(0, g(a))}{\|\nabla g(a)\|^2}\,\nabla g(a),$$
a single closed-form step that needs one function value and one gradient and no inner optimization. Iiduka showed that such steps satisfy a quasi-firm nonexpansivity property and can replace projections onto sublevel sets of nonsmooth functions (Acceleration method for convex optimization over the fixed point set of a nonexpansive mapping). Intersections of many such sets can be handled by parallel or incremental iterations (Parallel computing subgradient method for nonsmooth convex optimization over the intersection of fixed point sets of nonexpansive mappings). That entire line of work assumes a known, shared decision vector, a central averaging step, and convergence as the iteration count goes to infinity.
In our setting, agent $i$ evaluates $\hat g_i$, the constraint computed on its own belief about the hidden state, and the iteration is cut off after $K$ rounds per environment step. Our claim is that, under a regularity condition on the intersection of the true constraint sets (for example, a strictly feasible interior point), the worst-case violation of the executed joint action satisfies
$$\max_j g_j(a^{(K)}) \;\le\; c\,\rho^{K} + L\,\varepsilon_b .$$
In this bound, $\rho<1$ depends on the relaxation parameter and on the spectral gap of the communication graph. $\varepsilon_b$ bounds the error between believed and true constraint values, $L$ is a Lipschitz-type constant of the constraints, and $c$ depends on how far the policy's proposed action starts from the safe set.
The geometric first term follows the linear convergence of relaxed projection-type iterations onto regular intersections. The second term follows the inexact-oracle analysis of accelerated fixed-point methods (A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications). That work shows that errors in evaluating the operator enter additively. It is centralized and says nothing about hidden state; we import its error-accounting technique.
The practical consequence is that $K$ only needs to be large enough that $c\rho^K$ falls below $L\varepsilon_b$. Beyond that point, the right lever is reducing $\varepsilon_b$ or tightening the constraints by an amount proportional to it.
Research Program
We will build a decentralized safety layer that sits between each agent's policy and the environment. Each agent begins with its proposed action. For $K$ rounds, it applies relaxed subgradient-projection steps for the constraints it owns, including the pairwise coupling constraints with neighbors, and then averages its copy of the shared action coordinates with its neighbors' copies over the current communication graph. This is the neighbor-mixing structure of D-KM (Distributed algorithms for computing a fixed point of multi-agent nonexpansive operators). That paper computes a common fixed point over time-varying graphs without a coordinator but assumes fully observed state and proves only weak convergence in the limit. We need a finite-$K$ guarantee with inexact, belief-dependent operators.
Constraint functions come from one of two sources. In analytic tasks such as collision radii and wall half-spaces, they are known functions of state and action. Otherwise, a learned one-step cost predictor is linearized in the action. Beliefs come from each agent's recurrent history encoder, optionally fused with neighbors. For the belief-sharing variant we reuse the geometric-averaging diffusion of Policy Evaluation in Decentralized POMDPs with Belief Sharing, which showed that belief disagreement stays bounded by network connectivity but addressed only policy evaluation, with no constraints.
We treat the layer as part of the environment during learning. This choice is grounded in Safe Reinforcement Learning using Action Projection: Safeguard the Policy or the Environment?. That paper proves that for stochastic policies trained with generalized advantage estimation, safeguarding the environment and safeguarding the policy are equivalent. It also shows that differentiating through a projection costs 3 to 12 times more compute and suffers zero gradients from action aliasing. Because we use stochastic MAPPO-style policies, we never differentiate through the correction.
The theory work has three parts. First, prove the two-term bound for quasi-nonexpansive subgradient projections with belief-perturbed constraints over time-varying connected graphs. Second, identify when the regularity condition fails, for example tangent constraint sets, which break the linear rate. Third, derive an uncertainty-scaled tightening $\hat g_i + L\hat\sigma_i \le 0$, where $\hat\sigma_i$ is the agent's estimated belief error. This tightening turns the floor into a guarantee at the price of some conservatism. The empirical work tests each term of the bound separately.
Baselines
The naive reference point is unconstrained MAPPO with the same recurrent encoders. It fixes the reward ceiling and the violation level that any safe method must improve on.
The strongest existing competitor is Scal-MAPPO-L from Scalable Constrained Policy Optimization for Safe Multi-agent Reinforcement Learning. It truncates advantage estimation to $\kappa$-hop neighborhoods and enforces safety with adaptive Lagrange multipliers. It is the right opponent because it is decentralized, it scales, and it matches centralized MAPPO-L on Safe MAMuJoCo; the paper reports that "once $\kappa \ge 3$" agents match a centralized controller. The file contains no scalar cost or reward table for it; no reported result found on Lacuna for Scal-MAPPO-L as numerical values on Safe MAMuJoCo. We will therefore rerun it from the released configurations.
For context on Lagrangian behavior, the only reported figure in the file is single-agent. PPO-Lag achieved "a 98% reduction in safety violations compared to standard PPO, with only a 45% drop in total reward" on Safety-Gymnasium velocity tasks (Safety Gymnasium: A Unified Safe Reinforcement Learning Benchmark). That benchmark also documents how sensitive Lagrangian training is to the multiplier's learning rate.
Fairness rules apply across all methods. Each method gets the same environment steps, the same policy architecture, and the same hyperparameter search budget, measured in trials over the multiplier learning rate or over $K$ and the relaxation parameter. We report wall-clock time and messages per environment step. We allow Scal-MAPPO-L a $\kappa$-hop neighborhood equal in size to our layer's communication radius. Beating it means one of two outcomes: equal or lower cost with reward within noise, or equal reward with lower cost. In either case we also require lower variance across seeds and multiplier settings. Fewer episodes over the cost budget early in training would count strongly, because that is exactly where Lagrangian methods fail.
Two upper bounds and two ablations complete the comparison. The first upper bound is an oracle centralized safety filter that solves the exact quadratic program projection with the true global state. It shows how much the inexact decentralized iteration gives up. The second upper bound is our layer with true-state constraints, which sets $\varepsilon_b=0$ and isolates the information floor. The ablation central to the proposal is $K=1$ with no neighbor exchange: each agent takes one independent subgradient step on its own believed constraints. A second ablation removes the uncertainty-scaled tightening.
Why not just…?
Why not just use Lagrangian penalties, which already work at scale? Scal-MAPPO-L does keep cost below threshold on Safe MAMuJoCo, so this alternative is a serious threat to our reward numbers. Penalties, however, enforce constraints only on average over trajectories, and they do so after a multiplier has learned to be large. Safety-Gymnasium documents the resulting limit cycles. The distributed-optimization analyses in A Fast Distributed Asynchronous Newton-Based Optimization Algorithm and Superlinearly Convergent Asynchronous Distributed Network Newton Method show that a fixed penalty leaves a persistent residual, while raising the penalty damages conditioning. Our layer acts on every step, from the first episode. The early-training violation curves and the sensitivity-to-tuning sweep will settle the question. If Scal-MAPPO-L matches us on both, our contribution reduces to the bound and the diagnosis of the error floor, and we will say so.
Why not just project exactly onto the safe set? With a global state, exact projection is the gold standard, which is why it serves as our oracle. Under partial observability, no agent has the inputs to compute it. A centralized projection also reintroduces the single point of failure that D-KM removes. The action-projection study measured 3 to 12 times extra compute when the projection is differentiated through. The oracle comparison will show how close truncated decentralized iteration comes, in violation per unit of compute.
Why not just let each agent take one local correction step, with a safety margin? This is the most plausible threat, because it needs no communication. When constraints are mostly decoupled, it may match our method. The theory predicts it fails exactly when coupled constraints, such as shared bodies or close pairs of agents, need several rounds for neighbors' corrections to agree. A margin large enough to cover that disagreement costs reward. The $K=1$ ablation and a sweep over coupling density decide the matter. If one step with a margin is on the same reward–cost frontier as our method in dense-coupling tasks, the fixed-point iteration is unnecessary, and we would pivot to studying uncertainty-scaled margins alone.
Why not just run more rounds or shrink the step size? Diminishing relaxation removes step-size error in the limit (PARALLEL OPTIMIZATION ALGORITHM FOR SMOOTH CONVEX OPTIMIZATION OVER FIXED POINT SETS OF QUASI-NONEXPANSIVE MAPPINGS). Our bound predicts it cannot remove the belief-error floor. The $K$ sweep tests exactly this prediction.
Proposed Experiments
The first testbed is a controlled continuous-navigation Dec-POMDP with $N$ agents from 4 to 64. Agents observe noisy neighbor positions within a radius, and pairwise collision and wall constraints are analytic, so exact projections and true violation are computable. We also run the synthetic sublevel-set problems of Iiduka's testbed with up to 256 users, as a pure optimization check with injected constraint noise of known size. The decisive check here has two parts. For each noise level, measured violation should decay geometrically in $K$ and then flatten at a level that scales linearly with injected $\varepsilon_b$. The flattening should not move when the relaxation parameter or schedule changes, but it should move when geometric belief sharing reduces $\varepsilon_b$. If the plateau instead depends on step size, the central claim is wrong.
The second testbed is Safe MAMuJoCo: ManyAgent Ant in the $2\times3$, $3\times2$ and $6\times1$ splits, and Coupled HalfCheetah $12\times1$. Here each agent controls part of one body and sees only local joints, so constraints are strongly coupled and partially observed. Metrics are episode reward, episode cost relative to the budget, the fraction of training episodes over the budget, variance across seeds and tuning settings, wall-clock time, and messages per step. We compare against unconstrained MAPPO, Scal-MAPPO-L at matched $\kappa$, the $K=1$ local-margin ablation, and the oracle filter. The decisive check is whether our layer keeps early-training violations near zero while its final reward stays within noise of Scal-MAPPO-L, with overhead well below the 3 to 12 times reported for differentiated projection.
A final stress test uses time-varying graphs with random link drops. Among the file's candidates, this is where the coordinator-free structure of D-KM should matter, and where the incremental ring scheme of Iiduka stalls, since it needs every user to participate each cycle.
References
- Acceleration method for convex optimization over the fixed point set of a nonexpansive mapping
- Parallel computing subgradient method for nonsmooth convex optimization over the intersection of fixed point sets of nonexpansive mappings
- A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications
- Distributed algorithms for computing a fixed point of multi-agent nonexpansive operators
- Policy Evaluation in Decentralized POMDPs With Belief Sharing
- Safe Reinforcement Learning using Action Projection: Safeguard the Policy or the Environment?
- Scalable Constrained Policy Optimization for Safe Multi-agent Reinforcement Learning
- Safety Gymnasium: A Unified Safe Reinforcement Learning Benchmark
- A Fast Distributed Asynchronous Newton-Based Optimization Algorithm
- Superlinearly convergent asynchronous distributed network newton method
- PARALLEL OPTIMIZATION ALGORITHM FOR SMOOTH CONVEX OPTIMIZATION OVER FIXED POINT SETS OF QUASI-NONEXPANSIVE MAPPINGS