Trust-Ordered Intention Chains for Heterogeneous Teams with Byzantine Members

The strongest current methods for coordinating robots with different bodies and sensors have one thing in common: they are chains. One robot plans, tells the next robot what it intends to do, that robot plans around it and passes its own intention on, and so on down the line. This structure works because it lets very different agents take turns instead of colliding with each other's plans. It also has an obvious weakness. If the first robot in the chain lies, or is simply broken in an arbitrary way, every robot after it plans around a fiction. And in a team of different kinds of robots, the robots downstream often cannot catch the lie, because the liar is reporting things only it can see.

We propose a defense with two parts. The first part changes who goes first: the chain order is set by how much each agent is currently trusted, so a suspected agent is moved to where its messages can mislead as few teammates as possible. The second part changes how trust is earned when a claim cannot be checked directly. Each agent commits to its claims, and teammates check those claims later, once their predicted consequences come into view. The combined result is a coordination scheme in which the harm a Byzantine agent can do is bounded by its position in the chain, and its position depends on evidence that heterogeneous teammates can actually gather.

Core Claim

Two lines of work, both studied in partially observable settings, coordinate agents through an ordering. In Heterogeneous-Agent Reinforcement Learning, agents with different action spaces are updated one at a time, each conditioning on the agents updated before it; this gives monotonic improvement and convergence guarantees. In Empowering Multi-Robot Cooperation via Sequential World Models (SeqWM), robots plan in sequence, and each passes its predicted future trajectory to the next robot in the chain. Both methods assume every agent is honest.

Here "Byzantine" means arbitrary or malicious behavior, including lying and sending different messages to different peers. In a chain, the damage a Byzantine agent can do depends on where it sits. An agent at position $k$ of an $n$-agent chain can corrupt at most the $n-k$ agents that condition on it. Suppose $p_k$ is the probability that the agent at position $k$ is Byzantine. Then the expected number of honest agents planning on corrupted inputs is at most

$$ E = \sum_{k=1}^{n} p_k\,(n-k). $$

By the rearrangement inequality, this bound is smallest when agents are sorted by increasing suspicion. HAPPO-style random ordering does not do this; it averages the exposure over positions.

The ordering rule is easy. The real difficulty is estimating $p_k$ when observations are asymmetric. A ground rover cannot score a drone's report about terrain it cannot see. That is exactly where receiver-side scoring, as in Robust Multi-Agent LLMs under Byzantine Faults, runs out. Our second contribution addresses this. Each receiver learns a consequence model that maps a sender's claim, which may be stated in a different observation or action space, to predictions about the receiver's own future observations. Trust is then updated as those predictions are confirmed or contradicted by what the receiver later sees.

The new element is not Byzantine robustness in multi-agent learning as such. It is the combination of position-dependent damage bounds in sequential heterogeneous coordination with delayed verification of claims that receivers cannot check at the moment they arrive.

Relation to Prior Work

The closest work is Byzantine Robust Cooperative Multi-Agent Reinforcement Learning as a Bayesian Game. It treats whether each teammate is adversarial as a hidden type and trains agents (EIR-MAPPO) to keep posterior beliefs over those types from their observation histories. This paper motivates our use of adaptive beliefs rather than static worst-case play; it proves that the adaptive equilibrium weakly dominates the static one. It differs from our proposal in three ways. Its updates are simultaneous rather than sequential. Its agents are homogeneous. Its beliefs come from observed actions, not from verifying messages.

Classical robust aggregation constrains the design and is largely ruled out for this setting. Collaborative Learning in the Jungle names the "minority filtering" problem, in which trimmed means and minimum-diameter averaging discard honest agents whose inputs are legitimately unusual. On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks proves that exact consensus is impossible when local rewards are heterogeneous. In a team where the drone is the only drone, there is no peer group to filter against.

Secure Multi-agent Reinforcement Learning for Service Systems with Affinity and Byzantine Nodes supplies one idea we reuse: falling back to a known safe behavior when inputs are distrusted. Our analogue is that a demoted agent's intention is still received but is discounted, rather than replacing the whole policy.

TrInc: Small Trusted Hardware for Large Distributed Systems supplies the reason commitments are useful. Binding each message to a monotonic counter turns equivocation into something that can be detected. We use a software analogue, a signed and hashed broadcast of each claim, which costs far less than the reliable broadcast that gives RB-TM its reported >10x overhead.

Research Program

We will build the method on SeqWM's planning chain and on HAPPO's sequential updates. Each agent's outgoing message, an intention trajectory or a reported local observation, is signed and committed together with a step counter. A receiver that sees two different commitments for the same counter has detected equivocation, and it marks the sender as maximally suspect.

For claims about states the receiver cannot see, each receiver trains a consequence model during centralized training. The model takes a sender's claim and the receiver's own history, and predicts a distribution over the receiver's observations over the next $H$ steps. When those observations arrive, the receiver computes a likelihood ratio between "the claim was true" and the receiver's prior predictive. It accumulates these ratios into a per-sender posterior, and peers can pool their posteriors robustly.

At each decision step, the chain is reordered by increasing suspicion. In addition, each message is mixed with a prior intention in proportion to that suspicion, so information from a demoted agent is down-weighted rather than dropped. This matters because some heterogeneous agents, such as scouts, are informative exactly because they go first. The tension between "informative agents should lead" and "suspected agents should trail" is a central object of study. We will measure it as the loss in nominal return from trust-ordering when every agent is honest.

Training uses a learned adversary that controls a randomly chosen agent, updated on a faster timescale than the defenders, following the EIR-MAPPO recipe. We will also run three fixed attack types. A liar falsifies off-horizon terrain. An equivocator sends different intentions to different peers. A sleeper behaves honestly until it reaches the first chain position and then lies.

On the theory side, we will extend HAPPO's monotonic-improvement argument to a bound on the drop in joint return that a single Byzantine agent can cause. We expect the bound to scale with its position-weighted exposure $E$ and with how quickly the consequence model gathers evidence, which depends on $H$ and on how much the sender's and receiver's observations overlap.

Baselines

The naive reference point is SeqWM and HAPPO run unchanged, with random or fixed ordering, under every attack. This measures how fragile honest sequential coordination is, and it sets the floor any defense must clear.

The strongest existing competitor is EIR-MAPPO from Byzantine Robust Cooperative Multi-Agent Reinforcement Learning as a Bayesian Game. It is the only method in the file that learns adaptive beliefs about which teammates are Byzantine under partial observability. It reports a 25.45% higher average reward than M3DDPG and RMAAC on SMAC 4m vs 3m under attack, and roughly a 5.8% improvement over baselines on Level-Based Foraging. We will run it on our tasks with the same environment steps, the same adversary training budget, and the same hyperparameter search budget. Because it was designed for homogeneous agents, we will give it separate per-agent networks so that heterogeneity alone does not handicap it. Beating it means a higher return under the learned adversary on the asymmetric-observation tasks, with honest-team return within a few percent of it.

The second strong competitor is MARTA from Learning Robust Multi-Agent Policies via Selective Adversarial Fault Induction. It trains against faults injected at coordination-critical states and reports a 44.6% gain on LBF and a 116.7% gain for MARTA-VDN on SMACv2 over baseline training. It tests whether robust training alone, without any verification, is enough. We give it the same budget and the same attack suite.

The third competitor is a classical-filter baseline: SeqWM with incoming intentions filtered by coordinate-wise trimmed mean across senders, in the style of On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attacks.

Three ablations isolate the ingredients. The first keeps random ordering but uses our trust-weighted mixing. The second uses trust ordering but derives trust only from observed actions, EIR-style, with no consequence model. The third removes commitments.

Why not just…?

Why not just use EIR-MAPPO's beliefs to pick the order? This is the most serious threat, and it is precisely our second ablation. If an agent's actions reveal its type as fast as delayed message verification does, the consequence model adds nothing, and the honest conclusion would be that trust ordering plus action-based beliefs is sufficient. We expect action-based beliefs to fall short against the liar and sleeper attacks. In those attacks the Byzantine agent's own movements look normal while its reports about unseen terrain are false. The asymmetric-observation tasks are built so that this distinction is measurable.

Why not just turn off communication at execution time? Silence removes the attack surface, but it also removes the coordination that heterogeneous teams need. The StarCraft Multi-Agent Challenge reports most methods at a 0% win rate on super-hard maps such as corridor, and SeqWM reports that sharing intentions is what produces the push-and-steer role split in PushBox. We include a no-communication SeqWM variant. Our method should match it under the worst attack and clearly exceed it under honest or mild conditions.

Why not just filter messages with a trimmed mean or Krum? In a team where each role has one member, a robust aggregate either has nothing to compare against or discards the unique specialist. That is the minority filtering problem from Collaborative Learning in the Jungle. The filter baseline will show this directly as lost honest-team return on tasks where one agent is the only one with the relevant view.

Why not just keep HAPPO's random ordering, since it already spreads the risk? Random ordering places a Byzantine agent at the head of the chain with probability $1/n$ at every step. A sleeper attacker can wait for that slot. Our first ablation and the sleeper attack together test whether choosing the order matters beyond trust-weighted mixing.

Proposed Experiments

Benchmarks. We will use benchmarks from the file and modify them to make observation asymmetric.

In MPE Speaker-Listener, only the speaker sees the goal. We turn it into an attack setting by letting a Byzantine speaker lie and by extending it to several listeners, each of which sees landmark regions only once nearby. Consequence verification is possible here but delayed.

In Level-Based Foraging we use one wide-view scout and several narrow-view collectors of different levels, so the scout's food reports can only be confirmed when collectors arrive.

In Multi-Quadruped Gate and Shepherd, from the SeqWM suite, we add a corrupted intention chain.

On SMACv2 with mixed unit types, we include one unit type with an extended sight range.

Metrics. We measure return or win rate under each attack, return with an honest team, the number of steps until a Byzantine agent is demoted, the false-demotion rate for honest specialists, and communication overhead relative to plain SeqWM.

Comparison numbers. For SeqWM and HARL, the file gives no reported absolute numbers on these tasks ("no reported result found on Lacuna" for SeqWM's Gate/Shepherd returns and HARL's tabular scores), so all comparisons will be re-run under matched budgets.

Decisive checks. Three results matter most.

  1. The measured number of corrupted downstream agents should track $E$. If trust ordering does not reduce corruption in proportion to the predicted exposure, the position argument fails.
  2. On the asymmetric tasks, the full method should beat the action-belief-only ablation against the liar and sleeper attacks. If it does not, the consequence model is unjustified and we drop it.
  3. Honest-team return should stay within a small margin of unmodified SeqWM and HAPPO. This shows the defense avoids the pessimism that MARTA documents for always-on adversarial training.