Belief-Tracked Team Automata for Safe Decentralized Multi-Agent Missions

Suppose a robot team is told: "Agent 1 inspects room A, and only then may Agent 2 enter corridor C; nobody ever enters the hazard zone." The standard way to make such an instruction learnable is to compile it into an automaton. An automaton here is a small finite-state machine whose state records how much of the mission is done. The learner then treats the pair (physical state, automaton state) as its state, which is called a product state space. That pair is Markov: the right action depends only on the current pair, not on the full history. The trouble with teams is that at execution time each robot sees only its own sensors. Agent 2 often cannot know whether Agent 1 has finished inspecting room A. The team automaton state becomes a hidden variable, and some safety rules depend on it. "Don't enter C yet" is safe or unsafe depending on progress that Agent 2 cannot observe.

We propose that each decentralized agent carry an explicit probability distribution over the team automaton state. This distribution is updated by pushing the agent's own observations, plus learned predictions of what its teammates have observed, through the automaton's known transition rules. During centralized training the true automaton state is available and supervises that belief. The agent's actions are then gated for safety against the worst case among the automaton states it still considers plausible. In two sentences: training uses the true team progress to teach each robot to estimate that progress, and at deployment a robot only takes an action that would be safe no matter which plausible stage the mission is actually in. The bet is that this explicit, automaton-structured belief beats both implicit memory (a recurrent network) and the existing decentralized shields, which assume every agent can reconstruct the shared state from public labels.

Core Claim

In multi-agent tasks written in temporal logic with partly private labels, the gap between centralized training and decentralized execution comes down mainly to one thing: each agent's error in estimating the team automaton state. Closing that gap with a structured belief does two things. It recovers most of the task success of an oracle that broadcasts the automaton state. It also makes progress-dependent safety constraints enforceable without communication, because the safety check uses the whole support of the belief rather than its best guess. The claim is falsifiable. If a centrally trained recurrent actor, given the same supervision signal, matches the structured belief as label privacy increases, the structural part of the idea is unnecessary.

Where This Sits

The closest multi-agent temporal-logic work is Almanac (Multi-Agent Reinforcement Learning with Temporal Logic Specifications). It builds a product Markov game from a limit-deterministic automaton and trains lexicographic actor-critics. It tracks a single global automaton state, needs parameter sharing for optimality, and does nothing about safety during exploration. We keep its product construction for the centralized critic, but remove the assumption that actors see the global automaton state.

HyPOLE (HyPOLE) is the nearest thing to "inferring teammates" under CTDE. It uses an encoder-decoder to predict teammate traces and shapes rewards with robustness scores from a hyperproperty logic. It builds no explicit product state, provides no hard safety, and is limited to QMIX with discrete actions. Our belief is over automaton states rather than raw traces, and it feeds a safety gate, not only a reward.

Two shield papers supply the safety motivation and also constrain our design. Shield Decentralization for Safe Multi-Agent Reinforcement Learning splits a centralized automaton shield into local shields. This works only when the allowed joint actions factor as a product and every agent can track the shield state unambiguously from public labels. It reports zero violations against more than 115 per 100 episodes unshielded. Shield Decomposition for Safe RL in General Partially Observable Multi-Agent Environments drops the public-label assumption by solving a SAT problem over bounded histories. It works on discrete abstractions, its encoding grows quickly with history length, and it is decoupled from policy learning. Our belief-support gate can be read as a learned, approximate, continuous-state analogue of that SAT construction. It gives up its formal guarantee in exchange for scale, and we measure how much that trade costs. Safe Multi-Agent Reinforcement Learning via Shielding needs a centralized or zone-coordinated monitor at execution time, which is exactly what we avoid.

Two papers supply the method. Automaton Constrained Q-Learning (ACQL) contributes a minimum-safety critic, which predicts the smallest future safety margin rather than a cumulative cost, and automaton-aware hindsight relabeling. Both are single-agent and assume full observability. A Necessary and Sufficient Condition for the Unique Solution of the Bellman Equation for LTL Surrogate Rewards shows that with discount 1 the value estimate is unique only if states in unrecoverable "dead-end" components are pinned to zero. In the tabular case, error fell from 16.75 to 0.0079 when this was enforced. We apply this pinning to the centralized critic.

Constrained multi-agent optimizers (MACPO / MAPPO-Lagrangian, Scal-MAPPO-L) handle only Markovian scalar costs with cumulative budgets. That gap motivates the work, and these methods are our strongest optimization baselines.

Research Program

Centralized side. Training uses a centralized reward critic and ACQL-style minimum-safety critic over the true product state, meaning the physical state, the team automaton state, and the joint action. Automaton states from which the specification can no longer be satisfied are known from the automaton's graph. The critic's output is hard-masked to zero there, which enforces the uniqueness condition of the Bellman-uniqueness paper structurally rather than hoping the network learns it. Automaton-aware hindsight relabeling is extended to joint trajectories.

Decentralized side. Each agent $i$ keeps a belief $b_i$ over the team automaton states $Q$, updated as

$$ b_i^{t+1}(q') = \sum_{q \in Q} \sum_{\sigma} b_i^t(q)\, p_\phi(\sigma \mid h_i^t)\, \mathbf{1}[\delta(q,\sigma) = q']. $$

The symbols are as follows. $\sigma$ ranges over joint labels. $\delta$ is the automaton's transition function. $h_i^t$ is agent $i$'s own observation history. $p_\phi$ is a learned predictor of the joint label. That predictor is exact on the agent's own labels, predicts teammates' labels, and is trained centrally against true labels and the true automaton state. The automaton's transition function is hard-coded into the update rather than learned. This is the structural prior that separates the method from a plain recurrent network.

Safety gate. Actor $\pi_i(a_i \mid o_i, b_i)$ proposes an action. The action is admitted only if

$$ \min_{q \,:\, b_i(q) \ge \tau} \; G_i(o_i, q, a_i) \ge 0, $$

where $G_i$ is a per-agent distillation of the centralized minimum-safety critic and $\tau$ is a plausibility threshold. If no action passes, the agent falls back to a designated safe action such as braking or holding position. Purely Markovian collision constraints can still go to an existing decentralized shield where one is synthesizable. The belief gate targets the progress-dependent constraints those shields cannot express under private labels.

Analysis. We will characterize when the gate is sound. It is sound when the true automaton state lies inside the $\tau$-support and the distilled critic is conservative. We will measure empirically how often the true state falls outside the support as a function of $\tau$, and how that frequency predicts violations.

Baselines

The naive reference is independent PPO with a Lagrangian cost. Each agent is trained on local observations with the automaton reduced to a scalar violation cost. It shows what happens with no centralized scaffolding and no automaton memory, and it is run with the same environment steps and hyperparameter search budget as every other method.

The strongest existing optimizer is MAPPO-Lagrangian from MACPO, using the released code (chauncygu/Multi-Agent-Constrained-Policy-Optimisation). Its centralized critic is given the true team automaton state, and its actors are recurrent, so it has full access to the history. That paper reports near-zero costs on Safe Multi-Agent MuJoCo but gives no numeric values. We also found no reported result on Lacuna for any method on multi-agent temporal-logic tasks with private labels, so we will produce these numbers ourselves. Beating it means lower total training violations and at least equal specification-satisfaction rate at matched environment steps.

The strongest existing safety method is SAT-based shield decomposition (general partially observable shield decomposition). It is run on discretized versions of our tasks, where it applies, and paired with the same learner. It reports zero violations. On small discrete tasks we expect to match its safety, not beat it. We will report how far each method can scale in history length and agent count before synthesis becomes infeasible.

The communication upper bound is an oracle that gives every actor the true automaton state, equivalent to broadcasting a few bits per step. This bounds what any belief can achieve.

Three ablations isolate the key ingredients. The first swaps the structured belief for a recurrent actor trained with the same auxiliary cross-entropy loss on the automaton state. The second keeps the belief but gates on its most likely state instead of its support. The third removes the zero-masking of dead-end automaton states in the critic. The claimed contribution holds only if the structured belief beats the recurrent actor on satisfaction under high label privacy, and support gating beats most-likely-state gating on violations.

Why not just…?

Why not just give the actors recurrent memory and let them learn progress implicitly? This is the most serious threat, which is why its strongest version, with the same auxiliary supervision on the automaton state, is an ablation rather than a strawman. Our reason to expect a gap is that the recurrent network must rediscover the transition function $\delta$ and must stay calibrated on rare mission stages. Miscalibration matters specifically for the support-based safety gate. If the recurrent actor matches us, we will report that the structural prior is unnecessary and retain only the support-gating finding.

Why not just broadcast the automaton state? When a few reliable bits per step are available, this is the right answer. The oracle baseline measures exactly how much it is worth. The proposal targets communication blackouts, intermittent links, and settings where even agreeing on the global state is ambiguous. We will stress-test by dropping broadcasts at increasing rates and comparing oracle-with-dropout against our method.

Why not just use a Lagrangian cost on the specification with standard CTDE? Cumulative budgets tolerate repeated violations during training. The shield literature quantifies the difference: more than 115 violations per 100 episodes unshielded versus zero shielded, in Shield Decentralization. MAPPO-Lagrangian with a product-state critic is our main baseline, so the training-violation curve settles this directly.

Proposed Experiments

Environments. We build two-to-four-agent variants of ACQL's Brax PointMass Field and Quadcopter Room tasks, specified in temporal logic. Rooms, gates, and hazard zones emit labels that are private to whichever agent is present. A knob sets the fraction of labels that are public, from all public (where the unambiguity assumption of Shield Decentralization holds) to all private. Single-agent reference: ACQL reports 60–80% success on its Loop task, where other baselines reach 0%. That number anchors our single-agent sanity check. For discrete comparisons against SAT shields we add automaton-task overlays to Grid-Col and Flashlight-6/10. As a check that our machinery does not hurt on purely Markovian costs, we also run Safe ManyAgent Ant.

Metrics. We report specification-satisfaction rate at test time and cumulative safety violations over all of training. We also report task reward, the rate at which the true automaton state falls outside the belief support, and wall-clock overhead. All results use ten seeds with matched environment steps.

Decisive checks. The first check is a privacy sweep. The gap between our method and the recurrent ablation should widen as the fraction of private labels grows, and our method should stay within a small margin of the oracle. If the gap never opens, the structural claim fails. The second check sweeps $\tau$. Training violations should track the rate at which the true state falls outside the belief support, showing that safety failures come from belief errors rather than critic errors. The third check removes dead-end masking. The centralized critic should overestimate value on unrecoverable automaton states, echoing the leakage result of the Bellman-uniqueness paper in the multi-agent setting. We expect this overestimation to show up as degraded satisfaction.