Online Change-point Detection for Cooperative Multi-Agent Reinforcement Learning

In cooperative Multi-Agent Reinforcement Learning (MARL), agents are often trained under concurrent participation, while in many tasks some agents act earlier and leave task-relevant information that becomes useful to agents participating later. We study this setting as staggered participation (SP), which introduces a cross-time, cross-agent learning dependency because an early action may affect the return through the information it provides and the later policy that uses it. Learning under SP therefore requires both identifying what information is useful for future decisions and learning how later agents should use it. We propose Staggered Participation Learning (SPL), a training-time augmentation that addresses these two parts with prospective acquisition supervision for earlier agents and outcome-supervised receiver learning for later agents. We evaluate SPL across multiple policy-based MARL backbones, environments, and staggered-participation patterns. Across 60 MPE/RWARE backbone setting comparisons, SPL achieves higher observed mean task completion in every case, with an average difference of 14.1%. The gains also extend to eight-agent teams and a physics-based UAV-UGV environment in Isaac Lab, providing evidence across algorithmic, temporal, and embodied settings.

We argue that cooperative multi-agent reinforcement learning (MARL) should treat test-time coordination as part of the problem definition rather than a deployment artifact. Our focus is on long-horizon, centrally monitored cooperative systems such as warehouse robotics, automated storage-and-retrieval systems, and cloud-resource scheduling, where teams share a reward, operate under shifting objectives, and already run with global telemetry at deployment. The dominant paradigm in this regime, centralized training with decentralized execution (CTDE), uses global information only during training and provides no coordination channel at execution. This is sufficient when agents are weakly coupled or the environment is stationary, but it fails when the team must realign after conditions change. The limitation is structural rather than algorithmic, and more training cannot add a channel that does not exist at execution time. We call this the recoverability gap. To address it, we name the underexplored design space of intermittent test-time coordination as centralized training with mixed execution (CTME), in which a coordinator observes global state and emits high-level signals while agents act locally. CTME is not a particular learning algorithm, but a cooperative MARL problem setting that makes test-time information structure explicit. It specifies team-level information, high-level signals, and update frequency after training, with CTDE recovered as a limit case. We do not argue that CTDE is obsolete. We argue that removing the test-time channel is a modeling choice, not a necessity, and the wrong default when global telemetry is available and teams must recover from drift.

Cooperative multi-agent reinforcement learning (MARL) is typically framed as a decentralised partially observable Markov decision process (Dec-POMDP), a setting whose hardness stems from two key challenges: partial observability and decentralised coordination. Genuinely solving such tasks requires Dec-POMDP reasoning, where agents use history to infer hidden states and coordinate based on local information. Yet it remains unclear whether popular benchmarks actually demand this reasoning or permit success via simpler strategies. We introduce a diagnostic suite combining statistically grounded performance comparisons and information-theoretic probes to audit the behavioural complexity of baseline policies (IPPO and MAPPO) across 37 scenarios spanning MPE, SMAX, Overcooked, Hanabi, and MaBrax. Our diagnostics reveal that success on these benchmarks rarely requires genuine Dec-POMDP reasoning. Reactive policies match the performance of memory-based agents in over half the scenarios, and emergent coordination frequently relies on brittle, synchronous action coupling rather than robust temporal influence. These findings suggest that some widely used benchmarks may not adequately test core Dec-POMDP assumptions under current training paradigms, potentially leading to over-optimistic assessments of progress. We release our diagnostic tooling to support more rigorous environment design and evaluation in cooperative MARL.