Interpretable Failure Analysis in Multi-Agent Reinforcement Learning Systems

1. Problem Statement

Multi-Agent Reinforcement Learning (MARL) is increasingly used in safety-critical domains (e.g., robotics, power grids). However, when failures occur, diagnosing the root cause is exceptionally difficult due to the "domino effect" inherent in tightly coupled systems.

• The Core Challenge: The first agent to exhibit detectable instability is often not the true source of the failure (Patient-0). Instead, a downstream agent may fail first because it is more sensitive to perturbations or because the system amplifies small upstream deviations.
• Limitations of Existing Methods:
  • Global Metrics: Tracking team rewards or aggregate statistics obscures individual agent instability and propagation pathways.
  • Credit Assignment: Methods like Shapley values explain contribution to rewards but do not reveal failure dynamics or cascading propagation.
  • Single-Agent XRL: Existing Explainable RL tools cannot handle the non-stationarity and complex interdependencies of multi-agent systems.
• Goal: The paper aims to answer three questions:
  1. Q1: Who is the true Patient-0 (the first agent to enter a non-robust state)?
  2. Q2: Why are non-attacked agents sometimes flagged first, and how can we distinguish true sources from amplified downstream effects?
  3. Q3: How do failures propagate through learned coordination pathways over time?

2. Methodology: A Two-Stage Gradient-Based Framework

The authors propose a forensic framework that moves beyond black-box detection to interpretable gradient-level analysis. The method operates in two stages:

Stage 1: Local Policy Instability Detection (Patient-0 Candidate)

• Mechanism: This stage monitors each agent's policy stability by analyzing the Taylor remainder of a policy-gradient cost function.
• Mathematical Formulation:
  • For an agent $i$ with policy $\pi_i$, a deterministic action-commitment cost $J_i$ is defined based on local observations $o_i$.
  • Using Taylor's theorem, the method calculates the Taylor remainder statistic ($L^t_i$), which approximates the second-order curvature (Hessian) of the cost function with respect to observations.
  • $L^t_i(\eta_i) \approx \frac{1}{2}\eta_i^\top \nabla^2_{o_i} J_i(o_i, \tau_i) \eta_i$.
• Logic: Large deviations in this remainder indicate the policy is in a "non-robust," high-curvature region where small observation changes cause disproportionate policy shifts.
• Output: The agent whose Taylor error first exceeds a baseline threshold is declared the initial Patient-0 candidate ($\hat{p}_{S1}$).

Stage 2: Cascade Source Identification & Validation

• Mechanism: This stage validates or corrects the Stage 1 candidate by tracing accelerating upstream influence using the Critic (the value function $Q$).
• Key Insight: It distinguishes between damping and accelerating influence. A downstream agent might fail first if an upstream agent's action creates a state with high sensitivity and positive curvature (amplification).
• Mathematical Formulation:
  • The method computes first-order sensitivity ($G^t_{ij} = \|\partial Q_i / \partial a_j\|$) and directional second-order curvature ($D^t_{ij} = g^\top H g$) for the pair $(j \to i)$.
  • If $D^t_{ij} > 0$, the influence is accelerating (amplifying deviations). If $D^t_{ij} < 0$, it is damping.
• Traceback Algorithm:
  • Starting from the Stage 1 candidate, the algorithm iteratively traces back to the strongest accelerating upstream source ($D > 0$) within a causal time window.
  • It aggregates the Influence Score ($I_{j \to i}$), which weights the magnitude of deviation by the recency and the presence of accelerating curvature.
• Output: A corrected Patient-0 and a Directed Contagion Graph.

Output: Interpretable Contagion Graphs

The framework generates a directed graph summarizing:

• Nodes: Agents, colored by Instability Occupancy (IO) (duration of instability).
• Edges: Directed influence pathways ($j \to i$) annotated with:
  • Influence Score (IS): Cumulative first-order sensitivity.
  • Critical Rate (CR): Frequency of accelerating states ($D > 0$).
  • Timing: The propagation window.

3. Key Contributions

1. Two-Stage Patient-0 Detection: A novel method combining local Taylor-error detection with upstream traceback validation to identify true failure sources.
2. Geometric Explanation of Anomalies: Uses directional second-order analysis to explain why downstream agents are flagged first (amplification via positive curvature).
3. Interpretable Contagion Graphs: Visual and quantitative maps of failure propagation, quantifying influence strength, amplification frequency, and timing.
4. Comprehensive Evaluation: Validated across 500+ episodes in Simple Spread (3 and 5 agents) and 100 episodes in StarCraft II (SMAC) using MADDPG and HATRPO algorithms.

4. Experimental Results

The method was evaluated on its ability to identify the true Patient-0 and explain failure dynamics.

• Patient-0 Detection Accuracy:
  • The combined two-stage approach achieved 88.2% – 99.4% accuracy.
  • HATRPO (a trust-region algorithm with smoother gradients) consistently outperformed MADDPG (which has higher gradient noise), confirming that smoother landscapes yield cleaner Taylor signals.
  • Correction Rate: Stage 2 successfully corrected "downstream-first" misidentifications in 40.1% – 76.9% of cases, depending on the environment's coupling strength.
• Influence Validation (Intervention Studies):
  • The authors performed "paired causal tests" by intervening at Critical states (high sensitivity + accelerating curvature) vs. Robust states.
  • Result: Interventions at Critical states caused significantly longer instability (measured by Instability Occupancy) than Robust states.
  • Metric Superiority: The proposed Instability Occupancy (IO) metric outperformed traditional performance metrics (AUC of Reward/Q) by 20+ percentage points, proving that gradient geometry captures vulnerabilities invisible to reward-based analysis.
• Case Studies:
  • High-Influence: Showed that perturbing a source at an accelerating state caused persistent downstream instability, correctly traced by Stage 2.
  • Downstream-First (False Positive): Demonstrated a scenario where Agent 1 failed first (Stage 1 flag), but Stage 2 correctly traced the amplification back to the true source, Agent 3, via a high-curvature pathway.

5. Significance and Conclusion

This paper represents a significant step forward in Explainable MARL (xMARL) by shifting from post-hoc reward analysis to gradient-level forensics.

• Practical Impact: It provides safety engineers with actionable tools to diagnose cascading failures, identifying not just who failed, but why and how the failure spread.
• Theoretical Contribution: It formalizes the relationship between policy curvature, critic derivatives, and failure propagation, offering a geometric explanation for "downstream-first" detection anomalies.
• Future Work: The authors note limitations regarding the single-source failure assumption and computational overhead (Hessian-vector products), suggesting future work on online detection and handling multiple simultaneous failure sources.

In summary, the framework transforms opaque multi-agent failures into transparent, geometric evidence, enabling more reliable deployment of MARL in safety-critical systems.