When several agents must learn a task under a safety budget, and each sees only part of the world, gradient-based training often settles on policies that are safe but timid. This proposal argues that much of this timidity is an optimization failure, not an information limit. Hidden state makes the training objective bumpier. It creates extra points where the gradient is zero, called stationary points, that are not the best achievable policy. A safety constraint then makes these points attractive: an agent that cannot tell a dangerous situation from a harmless one it cannot distinguish learns to back off in both.
We propose to separate the two causes and fix the one that can be fixed. First, on small problems where the best safe policy can be computed exactly, we certify how far standard safe multi-agent training falls short. Second, we train with a gradually shrinking amount of privileged information. Early on, agents sometimes see the true state. The probability of seeing it is annealed to zero, and the pace is set by how much safety budget remains. Training starts where the objective is benign and follows the good solution as observations degrade, with a per-step bound on how much the annealing itself can raise cost.
Core Claim
Consider cooperative agents trained with a Lagrangian (a scalar price on safety cost, raised whenever the budget is exceeded). Under partial observability, they converge to stationary points whose reward gap grows with two things: how ambiguous the observations are, and how tight the safety budget is. A large share of that gap can be closed by training through a sequence of intermediate problems. Each problem mixes true-state and local observations. The mixing is annealed at a rate chosen so that the expected cost never leaves the budget.
What would be new is threefold. Prior work has not certified this constrained, partially observed gap against exact optima. It has not shown that tighter budgets make the gap from hidden state worse. And it has not combined observation annealing with a feasibility-preserving schedule.
Why This Gap and Not the Obvious One
The obvious move at this intersection is to take a safe multi-agent primal-dual actor-critic and prove a stationary-point rate when observations are partial. That is the natural next step after Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities, which proves an $\mathcal{O}(T^{-2/3})$ stationary-point rate for networked safe multi-agent reinforcement learning but assumes full visibility within each agent's neighborhood. We think that result would be incremental. A rate to a stationary point says nothing about which stationary point is reached, and partial observability is exactly the regime where that matters.
The strongest evidence comes from The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs. It shows that returns are rational functions of the policy parameters and that the number of critical points grows with observational ambiguity. On a 13-state grid, policy gradient stalls at a reward of 0.747 while a polynomial program solved by an interior-point solver finds the global optimum of 0.833. That paper is unconstrained and single-agent. It motivates our proposal, and it also supplies a method: its polynomial formulation lets us compute certified optima. Because safety costs are linear in state-action frequencies, adding a cost budget keeps the problem a polynomial program. Exact constrained optima therefore remain computable on small instances.
By contrast, the fully observable theory says stationary points can be global. Gradient dominance holds for the linear quadratic regulator (Maryam Fazel et al.), and natural policy gradient converges globally (Alekh Agarwal et al.), including under constraints with dimension-free rates (Natural Policy Gradient Primal-Dual Method for Constrained Markov Decision Processes). Those results constrain our design in a useful way. They say the endpoint where agents see the true state is a benign place to start. Our method exploits that.
Research Program
The first strand is diagnosis. We build small cooperative problems, each with a cost function: constrained single-agent versions of the 13-state aliased grid, and two-agent variants small enough for exact solution. For each problem we solve the constrained polynomial program to obtain the best achievable memoryless decentralized safe policy. That number captures the information limit: what any policy restricted to local observations can do. We then run Lagrangian policy gradient from many initializations. The measured shortfall below the certified optimum captures the optimization failure. We sweep two quantities: aliasing degree (how many hidden states share one observation) and budget tightness $\epsilon$. The hypothesis is that the fraction of runs trapped at safe-but-poor stationary points rises with both, and rises faster when both are large.
The second strand is the method. Agent $i$ receives, at each step, the true state $s$ with probability $1-\alpha$ and its local observation $o_i$ otherwise, through a masked input channel on one shared actor network. Here $\alpha \in [0,1]$ is the annealing parameter. At $\alpha=0$ the problem is fully observed and benign. At $\alpha=1$ it is the real decentralized problem. The centralized critics see the true state throughout, as in standard centralized training with decentralized execution (training with access to global information, deploying with local information only).
The safety mechanism is a sensitivity bound. For a fixed actor, the per-step action distribution is linear in $\alpha$. The standard performance-difference argument then gives
$$ \big| J_c(\pi, \alpha') - J_c(\pi, \alpha) \big| \le \frac{\gamma\, c_{\max}}{(1-\gamma)^2}\, \delta_\pi \, |\alpha' - \alpha|. $$
In this bound, $J_c$ is the expected discounted cost, $c_{\max}$ bounds the per-step cost, $\gamma$ is the discount, and $\delta_\pi$ is the largest total-variation distance between the actor's privileged and local action distributions. The $(1-\gamma)^{-2}$ factor comes from the performance-difference lemma. We therefore choose each increment $\Delta\alpha$ so the right-hand side stays below the measured slack $\epsilon - \hat J_c$, with a confidence margin. After each increment, several primal-dual actor-critic updates re-converge before $\alpha$ moves again, and the dual variable is carried over from the previous stage.
This construction borrows its logic from Constrained Markov Decision Processes via Backward Value Functions. There, training-time feasibility follows from starting with a safe policy. Here, the safe starting point is the $\alpha=0$ solution, which is found where the objective is benign.
The third strand is theory, kept modest. Within each stage, the analysis of Finite-Time Analysis of Actor-Critic Methods with Deep Neural Network Approximation supplies a $\widetilde{\mathcal{O}}(T^{-1/2})$ stationary-point rate. Across stages, we aim to prove that the constraint violation caused by annealing is bounded by the schedule above. We also aim to characterize, on the small polynomial instances, when the annealed path stays on the branch of the global constrained optimum and when it bifurcates away. We will not claim global optimality in general.
Baselines
The naive reference is independent Lagrangian PPO with recurrent actors trained directly at $\alpha=1$. It shows what happens when the problem is ignored.
The strongest existing competitors are centralized-critic safe multi-agent methods run with local-observation actors. The first is MAPPO-Lagrangian. The second is Multi-Agent First Order Constrained Optimization in Policy Space, which projects a closed-form constrained target policy onto the network and reports stable constraint satisfaction on Safe MAMuJoCo and Safe Multi-Agent Isaac Gym. The third is Scalable Constrained Policy Optimization for Safe Multi-agent Reinforcement Learning, whose neighborhood-truncated advantages match centralized MAPPO-L once the communication radius $\kappa \ge 3$. All three already give critics privileged state, so beating them isolates the effect of privileged actor input and its annealing, not privileged information in general.
For quantitative reference, the file gives no numerical returns or costs for MAPPO-L, MAFOCOPS, or Scal-MAPPO-L on Safe MAMuJoCo. Results there are shown only graphically, so we found no reported result on Lacuna for those methods' returns. The only exact numbers in the file are single-agent: FOCOPS scores 1106.1 on Humanoid-Circle within a cost limit of 50 (First Order Constrained Optimization in Policy Space), and policy gradient scores 0.747 against an optimum of 0.833 on the aliased grid. We will therefore rerun every baseline ourselves.
Every method gets the same environments, observation definitions, network sizes, environment-step budget, and hyperparameter search of 20 configurations. We report mean and spread over 10 seeds. Beating a baseline means higher final return at an equal or lower rate of budget violation, and equal or fewer cumulative training violations.
Four ablations isolate the key ingredient. The first uses the privileged channel with random dropout at a fixed rate, without annealing. The second anneals on a fixed linear schedule that ignores slack. The third anneals but resets the dual variable at each stage. The fourth is a compute-matched random-restart ensemble at $\alpha=1$.
Why not just…?
Why not just use more memory, such as recurrent actors, and let them infer the hidden state? Memory reduces aliasing but does not remove the extra stationary points that remaining ambiguity creates. With finite training it may also fail to learn the inference before the safety price has already pushed the policy into timidity. We test this directly. Recurrent MAPPO-Lagrangian is a baseline, and on the small instances we measure its gap to the certified optimum. If recurrent actors close the gap as well as annealing does, the method claim fails and the diagnostic result stands on its own.
Why not just distill a privileged safe teacher into a decentralized student? This is the most serious alternative. It shares our intuition that the fully observed problem is easy. Its weakness under constraints is that the teacher's safe behavior relies on information the student lacks. The student imitates an average of teacher actions over hidden states it cannot tell apart, and that average can be unsafe. In our method, by contrast, the student is always optimizing its own constrained objective. We run teacher-student distillation followed by constrained fine-tuning as a full baseline under the same budget. We expect distillation to reach good returns but with violation spikes during the transition, much like the cost spikes documented in Breaking Safety Paradox with Feasible Dual Policy Iteration. If it does not show those spikes, it is a genuine competitor, and we will say so.
Why not just restart from many random initializations? On small problems with few critical points, restarts may match annealing. The geometry paper's bound of at most $n$ critical points for blind two-action controllers suggests restarts are cheap there. The compute-matched restart ensemble is therefore an ablation, and we report the aliasing level at which restarts stop sufficing. Restarts also incur training-time violations on every run, which annealing is designed to avoid, so we compare cumulative violations as well as final return.
Why not just shield the agents? Safe Reinforcement Learning via Shielding under Partial Observability and Shield Decentralization for Safe Multi-Agent Reinforcement Learning achieve zero violations. However, they need an accurate transition graph, and the multi-agent version requires building a centralized shield whose size grows exponentially with the number of agents. Shields also remove unsafe actions without addressing which stationary point the learner reaches. Where a shield can be built, on the Carr et al. domains, we report it as an upper reference for safety, and we test whether annealing composes with it.
Proposed Experiments
The decisive first experiment is the certified-gap study on small constrained problems. Its outcome is a surface showing the fraction of the certified gap closed by each method as aliasing degree and budget tightness vary. Two results would support the proposal. First, Lagrangian policy gradient's gap should widen with budget tightness beyond what is seen unconstrained. Second, observation annealing should close most of that gap while keeping cost within budget at every stage.
The second experiment uses the six Carr et al. POMDP domains with cost annotations, extended to two agents where tractable. We track cumulative training violations against the published reference of about 3,153 violations for unshielded REINFORCE on the Avoid domain.
The third experiment uses Safe MAMuJoCo: ManyAgent Ant in 2×3, 3×2, and 6×1 configurations and Coupled HalfCheetah 12×1. We also use the multi-agent tasks in Safety Gymnasium: A Unified Safe Reinforcement Learning Benchmark. In all of these we control partial observability by limiting how many neighboring joints each agent perceives. Metrics are normalized reward, normalized cost, cumulative training violations, and the largest violation during the annealing phase. We also check whether the actor's privileged-to-local gap $\delta_\pi$ actually predicts the violation bound.
The claim is falsified if either of two things happens. One is that, at matched compute, annealing does not beat both distillation and restarts on the certified gap at high aliasing and tight budgets. The other is that slack-adaptive scheduling does not reduce the peak violation below the fixed linear schedule.
References
- Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities
- The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs
- Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
- Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
- Natural Policy Gradient Primal-Dual Method for Constrained Markov Decision Processes
- Constrained Markov Decision Processes via Backward Value Functions
- Finite-Time Analysis of Actor-Critic Methods with Deep Neural Network Approximation
- Multi-Agent First Order Constrained Optimization in Policy Space
- Scalable Constrained Policy Optimization for Safe Multi-agent Reinforcement Learning
- First Order Constrained Optimization in Policy Space
- Breaking Safety Paradox with Feasible Dual Policy Iteration
- Safe Reinforcement Learning via Shielding under Partial Observability
- Shield Decentralization for Safe Multi-Agent Reinforcement Learning
- Safety Gymnasium: A Unified Safe Reinforcement Learning Benchmark