Pricing Staleness in Multi-Agent Critics: Age-Conditioned Credit Assignment under Network Jitter

Teams of learning agents, such as robots, vehicles, or game units, are usually trained as if they share a single clock. At every tick, each agent sees its surroundings, hears its teammates, and acts, all at once. Real wireless networks do not behave this way. Messages arrive late, arrive out of order, and sometimes arrive several decisions after they were sent. So at any moment, each agent is acting on information of a different age. This note proposes to fix the part of training that most silently assumes a shared clock: the centralized critic, a value model used only during training that scores the whole team's joint behavior. We give the critic the vector of how old each agent's information is and which messages are still in transit. We then use it to compute, for each agent, how much team reward is lost because that agent's information is stale.

The claim is that under heterogeneous, heavy-tailed latency, a critic conditioned only on the true global state is not a valid (Markov) value function. Future team behavior depends on what each agent currently knows, and the global state does not record that. Adding the joint "age profile" restores a valid value function. It also yields a counterfactual quantity: the value of making agent $i$'s information fresh. That quantity is a task-grounded replacement for the content-blind freshness metrics of communication theory, and it can drive when agents wait for, request, or send updates.

Background and the gap

Centralized training with decentralized execution (CTDE) trains per-agent policies with a critic that sees everything, then discards the critic at deployment. MADDPG uses per-agent critics over joint actions and global information (Lowe et al.). COMA subtracts a counterfactual baseline to isolate each agent's contribution (Foerster et al.). QMIX mixes per-agent utilities through a state-conditioned monotonic network (Rashid et al.). All three score a joint action as if every agent chose it from the same instant. This is the machine-learning version of the synchronous network assumption, under which every message is guaranteed to arrive within a known bound, so computation proceeds in clean rounds.

Distributed-systems theory shows that dropping this assumption has an inherent cost. Dutta and Guerraoui prove that consensus tolerant of timing uncertainty needs at least one extra round even in runs that happen to be synchronous. The reason is that a slow peer cannot be told apart from a dead one. We use their result as a lens rather than a method. A learning agent facing a late teammate faces the same choice between waiting, which pays a time tax, and acting on stale data, which pays an accuracy tax. The right choice depends on the situation, which is exactly what a value function can price.

Three lines of multi-agent work motivate the proposal by leaving this gap open. DAMA-DDPG augments the state with pending-action buffers so that a delayed Markov game becomes Markov again (Chen et al.). It handles only fixed integer delays and names jitter as future work. DACOM learns an adaptive waiting timer per step (Yuan et al.). It fails once delays exceed one step, falling back to non-communicative behavior, and it keeps a synchronized environment step. VIL2C scores messages by the change they cause in the receiver's action distribution and allocates bandwidth and power accordingly (VIL2C). Its value score is instantaneous and myopic, and it assumes control over the physical layer. MARO imputes missing teammate observations with a centrally trained predictor (Santos et al.), but it treats communication as present or absent rather than as arriving with a continuous delay.

Two further results constrain the design. In single-agent control, Li et al. show that forward-prediction models collapse under jittered delay while simple action-history augmentation holds up. We therefore avoid predicting the present state from stale data. They also show that a critic trained offline can be given time-aligned "oracle" information. We reuse that asymmetry, extending it from one agent's sensor lag to many agents with different information ages. From the freshness literature we take the Age of Information (AoI), the time since the newest received update was generated, $\Delta(t)=t-U(t)$ (Huang et al.). We also take the Age of Incorrect Information, which grows only while the receiver's estimate is wrong (Abd-Elmagid et al.). Both are defined without reference to what the receiver does with the information. The learned quantity below is meant to close that gap.

Core Claim

Let $s$ be the true global state and $\mathbf{a}$ the joint action. Let $\boldsymbol{\Delta}=(\Delta_{ij})$ be the matrix of ages, where $\Delta_{ij}$ is the age of agent $j$'s newest information held by agent $i$. Let $m$ be the set of messages currently in flight, with their send times.

Because each agent's next actions depend on its information, the policy-conditioned value is $Q^\pi(s,\boldsymbol{\Delta},m,\mathbf{a})$, not $Q^\pi(s,\mathbf{a})$. A critic that drops $(\boldsymbol{\Delta},m)$ averages over information states it cannot see. Its value estimates and its credit assignment are then biased in a way that grows with the variance of the delay, not only with its mean. We define the value of freshness for agent $i$ as

$$ V^{\text{fresh}}_i = Q^\pi(s,\boldsymbol{\Delta}^{(i\leftarrow 0)},m,\mathbf{a}) - Q^\pi(s,\boldsymbol{\Delta},m,\mathbf{a}), $$

where $\boldsymbol{\Delta}^{(i\leftarrow 0)}$ sets agent $i$'s row of ages to the one-way minimum delay. Like COMA's baseline, this is a counterfactual computed from the critic alone. Unlike AoI, it is zero when staleness does not change what the team gets. Unlike VIL2C's score, it accounts for downstream consequences rather than the immediate shift in the action distribution.

Research Program

Event-driven wrapper. We first build a wrapper that removes the lockstep assumption from standard CTDE benchmarks. Each message receives a delay drawn from a configurable distribution: log-normal, a bursty two-state channel, or a shared-channel contention model. Delays range from a fraction of a step to several steps, so messages can reorder. Each agent's actions take effect when its decision completes, not at a shared tick. The wrapper logs the exact age matrix and in-flight queue at every step. This log is the privileged information given to the critic during training only.

Age-reconciled critic. The critic is a factored critic (a QMIX-style mixer and a MAPPO-style value head, to cover both families). Its mixing hypernetwork takes $(s,\boldsymbol{\Delta},m)$, where $m$ is summarized by a small set-encoder over (sender, receiver, age) tuples. Following Li et al., transitions are re-aligned offline so each agent's action is scored at the state in which it actually took effect.

Actors. Actors stay deliberately simple. Each is a recurrent policy over local observations, received messages tagged with their age, and its own recent action history. This is the augmentation that Li et al. found robust.

Freshness-driven communication. The value-of-freshness estimate $V^{\text{fresh}}_i$ is distilled into a small decentralized head that each agent runs locally from its own ages. That head drives three decisions under a fixed message budget: whether to wait one more sub-step for a late teammate, whether to request an update, and how the local buffer orders stale packets. For buffer ordering we test last-come-first-served against first-in-first-out, since Najm et al. show the ordering changes freshness non-trivially.

Analysis. Alongside the empirical work, we will make the non-Markov argument precise. We will show a two-agent example in which the state-only critic's credit assignment reverses sign under jitter but not under a fixed delay of the same mean.

Baselines

The naive reference is lockstep CTDE, meaning MAPPO or QMIX trained with zero latency and deployed in the jittered wrapper. It measures how much latency costs at all.

The first strong competitor is "age-tagged actors, standard critic." It uses the identical actors described above, but the critic sees only $s$ and $\mathbf{a}$, and training uses domain randomization over the same delay distributions. This is the baseline most likely to erase our gain. It is also the ablation that isolates our key ingredient, because it differs from our method only in the critic's inputs.

The second is DAMA-DDPG (Chen et al.), extended to random delays by padding its action buffer to the maximum delay. It is the principled prior method for restoring the Markov property.

The third is DACOM (Yuan et al.), the strongest existing method for delay-aware communication timing. The file reports on 2s3z under delay a win rate "nearly 20% higher than the next best communication-based baseline." No absolute win rate for DACOM is reported in the file.

The fourth is VIL2C (VIL2C), restricted to its progressive-reception and value-of-information scoring, because we do not assume control of transmit power. It is reported to approach full-communication win rates on SMACv2, but no numeric value was found on Lacuna.

The fifth is a MARO-style imputation model (Santos et al.).

The sixth is a hand-designed freshness scheduler. It requests or sends an update when AoI crosses a threshold, and separately when an AoII proxy (the estimate-error flag) crosses a threshold, with thresholds tuned on validation.

All methods share environments, delay distributions, seeds (at least eight), environment-step budgets, network sizes, and an equal hyperparameter-search budget. Communication methods are compared at matched messages per step. Beating the field means two things. At delays up to one step, we must match DACOM and VIL2C. Above one step, we must exceed the age-tagged baseline by a margin larger than seed variance, and we must reach equal return with fewer messages than the AoI and AoII schedulers.

Why not just…?

Why not just give the actors message ages and randomize delays during training? This is the real threat, and the experiment is designed around it. If the state-only critic's advantage estimates are already accurate enough, our method adds nothing. We test this directly in three ways. First, we compare each critic's value predictions against Monte Carlo returns, broken down by the variance of the age profile. Second, we measure disagreement in the sign of per-agent advantages between the two critics. Third, we compare final return. If the gap vanishes above one-step delays, we will report that the actor side suffices and the contribution shrinks to the value-of-freshness signal alone.

Why not just use a fixed timeout at the 99th percentile of latency, restoring synchrony? DACOM already found that rigid timers reduce arrival rates at the intersection (Yuan et al.). VIL2C found that fixed waiting windows inflate decision delay (VIL2C). Dutta and Guerraoui's lower bound says waiting always costs a round (Dutta and Guerraoui). We include the barrier baseline in heavy-tailed regimes, where the 99th percentile is many steps and the stall cost should dominate.

Why not just minimize AoI, or AoII, with a threshold policy? Threshold rules are optimal for their own metrics (Abd-Elmagid et al.). They also show that update rules matter: sending as fast as possible is often worse than waiting (Zhou et al.). But neither metric knows which teammate's staleness actually matters to the team's task. The matched-budget comparison settles this. If AoII thresholds reach equal return, the learned value of freshness is unnecessary.

Why not just predict the current state forward from stale messages? In single-agent control, forward prediction collapses under jitter (Li et al.). We still run MARO-style imputation, so the multi-agent case is tested rather than assumed.

Proposed Experiments

Environments. We use the Multi-Agent Particle Environment, where Lowe et al. report an 84% success rate for MADDPG in cooperative communication. We use SMAC and SMACv2 maps including 2s3z (Samvelyan et al.). We use the four-vehicle intersection, where delay-unaware agents fall "below 40%" success at a 0.8 s delay (Chen et al.). All three run through the event-driven wrapper with mean delays swept from 0.2 to 4 steps and delay variance swept independently at fixed mean.

Metrics. We measure success or win rate, collision rate at the intersection, and critic calibration error against Monte Carlo returns. We also measure messages per step, mean team AoI, and time spent stalled.

Decisive checks. The first decisive check is the variance sweep at fixed mean delay. The central prediction is that the state-only critic degrades with delay variance while the age-conditioned critic does not; if both degrade equally, the core claim is false. The second check tests whether $V^{\text{fresh}}_i$ is meaningful. On held-out states, the agents it flags should be those whose forced refresh most increases realized return. We measure this as rank correlation against refresh-intervention rollouts, compared with the ranking given by raw AoI. The third check is the matched-budget communication comparison.