Teams of learning agents, such as drones, vehicles in a platoon, or traffic signals, usually coordinate by keeping a private recurrent memory and swapping short messages computed from that memory with whoever is currently in radio range. This design has a weakness that current benchmarks do not measure. Suppose one agent's memory is corrupted by a bit flip, a reboot into garbage, or a newcomer joining mid-mission with an uninitialized state. The bad state does not only mislead that agent. It is broadcast to neighbors, folded into their memories, and sent back around every cycle in the communication graph. Nothing in a standard recurrent message-passing policy guarantees that the corruption ever dies out. The neighbor sets also change at every step, so classical self-stabilization does not help. Self-stabilization is the distributed-computing property of returning to a correct state from any starting state, and its recovery proofs assume the graph holds still while recovery happens.
We propose to build the self-stabilization guarantee into the learned network itself. Each agent's memory update is constrained to shrink differences in its own memory and in the averaged messages it receives. Neighbor messages are combined by averaging rather than summing. Under these two conditions, the gap between a corrupted run and a clean run of the whole team shrinks by a fixed factor at every step, for every sequence of graphs, including graphs where agents appear, vanish, or are isolated. The result is a recovery-time bound that holds no matter how fast the topology changes. The guarantee follows from the choice of architecture and costs nothing at run time. The empirical question is how much task performance the constraint costs, and whether simpler tricks such as finite history windows, memory resets, or training with injected corruption already deliver the same robustness.
Core Claim
Write $h_i^t$ for agent $i$'s memory vector at step $t$, $o_i^t$ for its local observation, and $\mathcal{N}_i(t)$ for its current neighbor set. Neighbors are those in range, so membership changes arbitrarily over time. The agent updates its memory as
$$h_i^{t+1} = F_\theta\big(h_i^t,\, o_i^t,\, \bar m_i^t\big), \qquad \bar m_i^t = \frac{1}{|\mathcal{N}_i(t)|}\sum_{j \in \mathcal{N}_i(t)} M_\theta(h_j^t),$$
with $\bar m_i^t = 0$ when the agent has no neighbors. Here $F_\theta$ is the memory update and $M_\theta$ is the message encoder. Suppose $F_\theta$ changes by at most a factor $a$ when its memory input changes and by at most $b$ when its message input changes, and $M_\theta$ changes by at most $c$ (these are Lipschitz constants). An average never exceeds the largest of the values it averages. So the worst-case memory gap $e^t$ between any two runs that see the same observations and the same graphs, measured in the maximum over agents, satisfies $e^{t+1} \le \rho\, e^t$ with $\rho = a + bc$. When $\rho < 1$ and memories are bounded (for example by tanh), the initial gap is at most the size of the memory space $R$. Every corrupted team is then within $\varepsilon$ of its clean counterpart after
$$T(\varepsilon) \le \frac{\log(R/\varepsilon)}{\log(1/\rho)}$$
steps, for every topology sequence.
This is self-stabilization in the sense of convergence plus closure. The legitimate states are memories that are within $\varepsilon$ of what an uncorrupted history would have produced, and the bound shows the team enters and stays in that set. The guarantee fails with sum aggregation, because the gain then grows with node degree. It also fails if only the agent's own memory path is constrained, because corruption can loop through neighbors.
Two scope limits keep the claim honest. First, the guarantee covers the agents' internal memories given a shared stream of observations and graphs. Corrupted memories can change actions, which can change the physical state and therefore future topologies, so whether the closed-loop behavior also recovers is an empirical question, and we test it directly. Second, the bound does not require the graph to be connected. This contrasts with Exponential Consensus of Multiple Agents Over Dynamic Network Topology, which shows that joint $(\delta,T)$-connectivity is necessary for linear agents to reach agreement. We ask for something weaker than agreement, namely forgetting corruption, and that is why the topology drops out of the bound. Connectivity still matters for whether useful information spreads, which is a separate question about task performance.
Relation to Prior Work
Self-stabilizing systems that tolerate topology change show what the gap looks like. Renaissance rebuilds a corrupted network control plane through tagged neighbor discovery, with bounds in terms of a fixed diameter $D$. In its experiments it takes about 55 seconds on a 200-node topology, far longer than link lifetimes in fast-moving networks like the satellite constellations described by Xiang et al.. Self-Stabilizing Repeated Balls-into-Bins proves stabilization only on a complete graph. Both are hand-designed protocols over discrete states. We instead constrain a learned continuous update so that the bound does not depend on the graph.
The closest relative is E(n)-equivariant Graph Neural Cellular Automata. It trains local 1-hop update rules whose target shapes regrow after damage, which supplies the idea that learned local rules can act as attractors. That paper has a fixed graph, no decision-making, and empirical rather than certified healing. We add switching graphs and reward-driven agents, and we make the healing a provable property of the architecture.
On the multi-agent learning side, three lines of work motivate the gap. DCT-MARL learns which wireless neighbors to listen to in vehicle platoons. BayesG infers sparse communication masks inside a fixed physical neighborhood and names truly dynamic topologies as future work. Dynamic Belief tracks drifting teammate policies. All three keep recurrent or variational beliefs with no bound on how long a corrupted belief persists. Our constraint can be added on top of any of them, and we use DCT-MARL-style gating as the base architecture.
DISKF constrains our design in a useful way. It fuses estimates over range-limited dynamic graphs in a single communication round. Its 1-hop error of 15.76 beats iterative consensus filters, which exceed 37.0, so multi-round consensus is a poor template for us. But DISKF is linear, which is why it serves as a reference point here rather than a competitor in the learning setting.
Research Program
The first component is an architecture. Each agent's memory update is a leaky contractive cell, $h' = (1-\alpha)h + \alpha \tanh(Wh + Uo + V\bar m)$, in which the hidden-to-hidden matrix $W$, the message matrix $V$, and the message encoder are spectrally normalized. The constants are certified layer by layer, and $\rho$ is computed exactly from the normalized norms, so the bound comes from the parameterization and not from a post-hoc estimate. The contraction budget $\rho$ is a single hyperparameter that sets the trade-off between memory length and recovery speed, and we sweep it. Training uses independent or parameter-shared actor-critic learning without a global-state critic. This choice follows the finding in COMRAD that decentralized IPPO beat centralized critics on Ammo Carrier. It also follows from the fact that a centralized critic is unavailable in the deployed networks that motivate the work.
The second component is a corruption protocol that current benchmarks lack. During evaluation we inject four kinds of fault. The first is random memory overwrites on a fraction of agents. The second is adversarial overwrites, chosen by gradient ascent on the team's loss. The third is agents that join mid-episode with arbitrary memory. The fourth is replayed stale messages from departed neighbors. We vary how often the topology changes independently of fault timing.
The third component is analysis. We measure empirical recovery curves, defined as the per-step memory gap and the return gap against a clean replay with the same seed. We compare them with the bound $T(\varepsilon)$. We also measure how the clean-condition task performance degrades as $\rho$ approaches 1 from below.
We use three testbeds that span the directions. The first is a learned version of the DISKF tracking task, with mobile sensors and links that form only within 120 units. Its known linear reference makes the cost of the contraction constraint easy to read. The second is SMAC from The StarCraft Multi-Agent Challenge with communication restricted to allies within sight range. This yields a genuinely dynamic graph on maps where memory matters, such as 27m_vs_30m and MMM2. The third is a platoon setting built on the NGSIM I-80 trajectories with Rayleigh fading, following DCT-MARL, where corrupted memory has a physical cost in string stability.
Baselines
The naive reference point is an unconstrained recurrent message-passing policy: GRU memories, summed or attention-weighted messages, and the same gating, data, and training budget. This is what DCT-MARL and BayesG-style systems effectively deploy. Beating it means two things. On clean returns, our method should stay within a pre-registered margin, such as 5 percent relative. Under corruption, its recovery time should be bounded, whereas we expect the naive policy's memory gap to plateau or never fall below $\varepsilon$ on graphs with cycles.
The strongest competitor on clean task performance depends on the testbed. For tracking, it is DISKF, whose reported 1-hop MAE is 15.76 in Decentralized Input and State Estimation. For SMAC, we compare against the reported SIDE median win ratio of 71% on 27m_vs_30m from SIDE. That figure uses unrestricted observation, not our range-limited communication, so we rerun SIDE under our communication restriction rather than quote it as a like-for-like number. For platoons, the reference is DCT-MARL's string stability index of 0.103 on a 6-car platoon. We reimplement DCT-MARL in our simulator and treat its reported number as a sanity check. For DCT-MARL under memory corruption, no reported result was found on Lacuna, and that is the measurement this proposal supplies.
All learned baselines get the same environment steps, the same hyperparameter search budget, and the same network width. Beating a strong baseline means matching its clean performance within the stated margin while cutting the worst-case recovery time under adversarial corruption by a large factor. We also require that, unlike the baseline, this recovery time does not grow as topology switching speeds up.
Three ablations isolate the key ingredient. The first constrains only the self-memory path and leaves messages unconstrained. The second keeps the full constraint but uses sum aggregation. The third uses the full constraint with mean aggregation, which is the proposal. If the first two recover nearly as well as the third on cyclic graphs, then the network-level small-gain argument is not doing real work.
Why not just…?
Why not just use a finite history window instead of recurrent memory? A policy that reads only its last $k$ observations is trivially self-stabilizing for a single agent. This is the most serious alternative. It breaks once agents exchange messages computed from their windows, because my window then contains messages that encode your window, which contains my earlier messages. The effective memory runs through the network without limit. A window that is truly bounded must ban recursion in messages, so that messages are computed from raw observations only. That loses multi-hop information. We run exactly this message-recursion-free windowed transformer as a baseline. If it matches our clean returns, especially on 27m_vs_30m where long memory matters, then the contraction approach adds nothing, and we will report that.
Why not just reset memories periodically, or when an anomaly detector fires? Periodic resets throw away good memory on schedule and still let corruption live until the next reset. Detectors miss small or adversarial corruptions by construction. A centralized reset authority runs into the in-band deadlock that Renaissance identifies, and it suffers the stale-coordinator penalties seen with centralized routing in SkyLink, where Dijkstra-based routing dropped 99% more packets. We include periodic and detector-triggered resets at several intervals. The test is the trade-off curve between clean return and recovery time, swept over the reset interval and over $\rho$.
Why not just train with injected memory corruption? This is a real threat. Training with corruption may teach an unconstrained network to forget corruption in practice, with no architectural constraint. Its weakness is that the robustness is only as broad as the training distribution. We train this baseline on random overwrites and then evaluate on adversarial overwrites, newcomers, stale-message replay, and topology change rates two to four times faster than in training. If it holds up out of distribution as well as the constrained model, the guarantee is of theoretical interest only, and we would recommend corruption-augmented training instead.
Proposed Experiments and Decisive Checks
The first decisive check is the gap between bound and measurement. On the tracking and SMAC testbeds, the measured worst-case recovery time under adversarial corruption must lie below $T(\varepsilon)$ for every topology change rate, while the naive baseline's recovery time grows with switching speed or diverges. If the bound is loose by orders of magnitude, we report the empirical rate as the main result and treat the bound as a safety floor.
The second check measures the cost of the constraint. We plot clean task performance against $\rho$ and locate the point where the constrained model matches the unconstrained baseline. If no value of $\rho$ below 1 comes within the margin on memory-heavy SMAC maps, the method only applies to tasks with short memory, and we will say so.
The third check is closed-loop recovery in the platoon. After corrupting the memory of a middle vehicle, we track string stability and the comfort score over time. We test whether physical recovery follows memory recovery, or whether feedback through vehicle motion and fading links keeps the platoon in a degraded state that the memory-level guarantee does not cover.
The fourth check is the aggregation ablation on graphs with many cycles, such as dense SMAC engagements. Sum aggregation should fail to recover, and mean aggregation should succeed. That result would show that topology-independent stabilization comes from the network-level gain condition and not from per-agent forgetting alone.
References
- Exponential Consensus of Multiple Agents Over Dynamic Network Topology: Controllability, Connectivity, and Compactness
- Renaissance: A Self-Stabilizing Distributed SDN Control Plane
- Wireless Access in Vehicular Environments
- Self-Stabilizing Repeated Balls-into-Bins
- E(n)-equivariant Graph Neural Cellular Automata
- DCT-MARL: A Dynamic Communication Topology-Based MARL Algorithm for Connected Vehicle Platoon Control
- Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning
- Dynamic Belief for Decentralized Multi-Agent Cooperative Learning
- Decentralized Input and State Estimation for Multi-agent System with Dynamic Topology and Heterogeneous Sensor Network
- COMRAD: A Benchmark for Embodied Cooperative Multi-Agent Reinforcement Learning
- The StarCraft Multi-Agent Challenge
- SIDE: State Inference for Partially Observable Cooperative Multi-Agent Reinforcement Learning
- SkyLink: Scalable and Resilient Link Management in LEO Satellite Networks