Source-linked AI summary
Online Change-point Detection for Cooperative Multi-Agent Reinforcement Learning
Fatemeh Saberi Khomami, Julita Vassileva
TL;DR
Cooperative MARL may rely on stale experience when environment or reward conditions change, creating a need to detect shifts before adaptation. The paper proposes PPR, an algorithm-agnostic detector for episodic returns, and finds that it balances detection responsiveness against alarm stability better than raw-return and smoothed-return alternatives. Reward-based detection remains sensitive to training seeds, especially under reward-function changes.
Problem
Cooperative MARL needs online detection of environmental or reward shifts because such changes can make prior experience unreliable before agents decide how to adapt.
Method
PPR is a lightweight, algorithm-agnostic detector that transforms episodic returns with smoothing and variance processing before applying KSWIN drift detection.
Results
Across two controlled shift scenarios, PPR provides a more balanced outcome than earlier but unstable SMA + KSWIN and conservative raw return + KSWIN, reducing repeated alarms while remaining responsive.
Takeaways & Limitations
Reward-derived signals can provide useful diagnostic information for monitoring non-stationarity in cooperative MARL.
Takeaways & Limitations
Reward-based detection remains challenging because results show seed sensitivity, especially under reward-function changes.
Abstract
from arXiv · showhide
Cooperative multi-agent reinforcement learning (MARL) systems rely on past experience for learning coordinated behaviour, but this experience may become unreliable if the environment or task objective changes during training. In such cases, agents first need a way to recognize that the situation has changed before deciding how to adapt. This paper studies online change-point detection for cooperative MARL using reward-derived signals. We propose \emph{Patterns of Past Rewards} (PPR), a lightweight algorithm-agnostic detector that smooths agents' return streams, highlights recent changes, and applies a statistical drift detector to flag significant shifts. We evaluate PPR in a custom Speaker-Listener environment based on the Multi-Agent Particle Environment under two controlled non-stationarity scenarios. Our results show a trade-off between detection speed and alarm stability. A smoothed-return baseline detects earlier but produces many repeated alarms. In contrast, applying the detector directly to raw returns often misses the shift. PPR offers a more balanced approach by limiting redundant detections while still identifying the controlled shifts. These findings highlight PPR as a lightweight, reward-based monitoring tool that enables cooperative MARL systems to reliably identify major changes during training.
1 Introduction
Cooperative MARL depends on past experience, but changing environments, objectives, observations, or agent roles can make that experience unreliable. The paper therefore treats online change-point detection as a prerequisite for deciding when prior knowledge should no longer be trusted.
- Cooperative MARL agents learn coordinated behaviour from accumulated interaction experience, which remains useful only when training conditions stay compatible.
- Changes in observation channels, reward functions, environment behaviour, or agent composition can invalidate previously learned experience.
- Detection is needed before adaptation because agents lack a clear signal for adjusting trust in prior knowledge without an online indication of change.
- Patterns of Past Rewards (PPR) monitors episodic returns with a lightweight, algorithm-agnostic detector without modifying the underlying MARL algorithm.
- The study evaluates PPR in a custom Speaker-Listener environment derived from MPE using controlled shifts during training.
2 Background
Cooperative MARL is commonly formulated as a partially observable multi-agent decision problem with shared rewards, while non-stationarity can arise from changing environments and simultaneously learning agents. Online change-point detection addresses this challenge by identifying distribution shifts in streaming signals such as rewards, although noisy reward sequences can reduce stability and delay detection.
- Cooperative MARL under Partial Observability: Cooperative MARL can be modelled as a Dec-POMDP in which multiple agents receive local observations and share a reward.
- Cooperative MARL under Partial Observability: A Dec-POMDP specifies agents, states, joint actions, transitions, rewards, observations, observation functions, and a discount factor.
- Cooperative MARL under Partial Observability: Because agents act from local observation histories, cooperative performance depends on coordination over time as well as individual decisions.
- Non-stationarity in Reinforcement Learning: Stationarity assumes transition dynamics and rewards remain unchanged, but environmental behaviour, reward structure, or observation processes may alter trajectory distributions.
- Non-stationarity in Reinforcement Learning: Multi-agent non-stationarity also arises when teammates or opponents learn, changing an individual agent’s effective transition dynamics.
- Online Change-point Detection: Change-point detection identifies when the distribution generating observations changes, which matters because shifts can make earlier experience less reliable.
- Online Change-point Detection: KSWIN compares reference and recent sliding windows with a Kolmogorov–Smirnov test for online concept-drift detection in noisy reward streams.
- Reward-based Monitoring: Reward-based monitoring is useful for detecting drift, but noisy reward-derived sequences can reduce detector stability and delay meaningful-shift identification.
3 Our Approach
PPR monitors episodic returns through smoothing, variability transformation, and sliding-window statistical drift testing. This pipeline is designed to reduce transient alarm noise while highlighting meaningful changes in return dynamics.
- PPR transforms episodic returns with SMA, EMV, and KSWIN to detect when recent return patterns differ from previous patterns.SMA produces a smoothed return, EMV emphasizes changes in that trajectory, and KSWIN outputs a binary drift indicator.
- SMA reduces short-term fluctuations caused by exploration noise, stochastic transitions, and ordinary learning dynamics.The smoothed stream provides a local trend estimate before drift detection.
- PPR begins after at least w episode returns are available because SMA requires an initial warm-up period.
- EMV converts changes in the smoothed return sequence into a positive variability signal before KSWIN testing.Gradual changes yield smaller values, whereas abrupt changes or variability bursts yield larger values.
- KSWIN compares recent and reference windows using empirical cumulative distributions to test whether transformed return distributions differ.The recent window has size m, while the reference sample is drawn from the preceding portion of a larger window W.
- A drift is flagged when the detector statistic D exceeds the critical threshold τα determined using significance level α.
4 Experiment Setup
The experiments evaluate PPR during cooperative Speaker–Listener training under controlled task and reward changes. Agents are trained online with MADDPG, while matched detector variants are compared using timeliness and alarm-stability metrics.
- 4.1 Environment: The Speaker–Listener task uses a speaker that communicates a goal colour and a listener that moves toward the corresponding landmark using shared team reward.The agents learn the communication convention from reward feedback rather than an explicit symbolic mapping.
- 4.2 Controlled Non-stationarity Scenarios: The landmark-colour-change scenario reassigns colour-to-landmark associations, requiring the agents to re-establish a compatible communication mapping.
- 4.2 Controlled Non-stationarity Scenarios: The reward-function-change scenario makes the landmark farthest from the original goal the new rewarded target while preserving the cooperative setting.The prior communication convention may therefore no longer match the changed reward structure.
- 4.3 Training Procedure: PPR runs alongside MADDPG training and monitors episode-level returns without modifying the learning algorithm or its update rules.
- 4.3 Training Procedure: Training lasts 1,000,000 steps, with the controlled shift introduced at step 500,000, corresponding to episode 20,000.
- 4.3 Training Procedure: The full SMA → EMV → KSWIN pipeline is compared with SMA + KSWIN and raw return + KSWIN using matched detector settings.
- 4.4 Evaluation Metrics: Detection delay, pre-shift detections, and excess detections jointly measure response timeliness, false early alarms, and repeated post-detection alarms.These metrics distinguish quick over-triggering from conservative later responses.
- 4.4 Evaluation Metrics: A run is counted as missed when no drift is flagged after the true shift within the training horizon.Delay is computed only over runs in which detection occurred.
5 Results
Across two controlled shifts, detector performance exposes a sensitivity–stability trade-off: faster methods alarm repeatedly, while conservative raw-return monitoring often misses changes. PPR provides a more balanced response, trading some detection speed for fewer redundant alarms.
- Learning dynamics: The reward-function-change shift separated shifted learning curves from matched no-shift runs shortly after episode 20,000.The dashed vertical line marks the true shift point.
- Detector comparison: SMA + KSWIN detects reward-function changes earlier than PPR but produces hundreds of pre- and post-shift detections.This alarm burden makes the faster detector difficult to use in practice.
- Detector comparison: Raw return + KSWIN is conservative and often misses shifts, whereas PPR responds better with substantially fewer repeated alarms.Only one of three runs detected the reward-function change, and that detection occurred long after the true change point.
- Overall trade-off: Across both scenarios, PPR offers a more usable balance between detection timeliness and alarm stability, especially for mild return changes.PPR does not minimize detection delay, but it reduces the repeated-alarm burden relative to faster detection.
- Parameter sensitivity: Reducing β produces earlier detection but more pre-shift and repeated alarms, while increasing w reduces alarm burden but increases delay.The final configuration was selected as a balance between timely detection and alarm stability.
6 Conclusion
This paper proposes PPR, an algorithm-agnostic detector for online change-point detection in cooperative MARL. Experiments across reward-function and landmark-colour shifts show a more balanced alarm pattern than faster or more conservative baselines, while seed sensitivity remains a challenge.
- Contribution: PPR monitors episodic returns with sequential SMA and EMV transformations followed by a KSWIN drift test.The detector operates alongside existing MARL training without modifying the underlying learner.
- Results: Across reward-function and landmark-colour shifts, SMA + KSWIN detects earlier but produces many alarms, while raw return + KSWIN often misses shifts.PPR reduces repeated alarms while remaining more responsive than raw-return monitoring.
- Conclusion: The results support reward-derived signals as diagnostic information about non-stationarity in cooperative MARL.This conclusion concerns monitoring value within the evaluated cooperative MARL setting.
- Limitations and future work: Seed sensitivity, especially under reward-function changes, indicates that reward-based detection remains challenging.The paper identifies adaptive parameter selection, broader monitoring signals, and downstream adaptation as future directions.