# Non-Stationarity Breaks Permutation Surrogates in Multi-Agent Reinforcement Learning: Diagnosis and Remedies

arXiv: https://arxiv.org/abs/2604.23716 · HTML: https://mlsanity.com/paper/2604.23716/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 26 Apr 2026.

## Builds on (most cited first, 16 of 16)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [MINE: Mutual Information Neural Estimation](https://mlsanity.com/paper/1801.04062/) (2018)
- [On Mutual Information Maximization for Representation Learning](https://mlsanity.com/paper/1907.13625/) (2019)
- [Gradients should stay on Path: Better Estimators of the Reverse- and Forward KL Divergence for Normalizing Flows](https://mlsanity.com/paper/2207.08219/) (2022)
- [JIDT: An information-theoretic toolkit for studying the dynamics of complex systems](https://mlsanity.com/paper/1408.3270/) (2014)
- [Optimization Issues in KL-Constrained Approximate Policy Iteration](https://mlsanity.com/paper/2102.06234/) (2021)
- [A robust estimator of mutual information for deep learning interpretability](https://mlsanity.com/paper/2211.00024/) (2022)
- [Efficient transfer entropy analysis of non-stationary neural time series](https://mlsanity.com/paper/1401.4068/) (2014)
- [Random Forests for Adaptive Nearest Neighbor Estimation of Information-Theoretic Quantities](https://mlsanity.com/paper/1907.00325/) (2019)
- [Estimation of Shannon differential entropy: An extensive comparative review](https://mlsanity.com/paper/2406.19432/) (2024)

## Abstract (arXiv)

Reporting guidance for information-theoretic measures is rarely tested against ground truth. We test one guardrail in two multi-agent reinforcement learning games, a social dilemma and a coordination race, where directed influence between selected agent pairs is zero by construction, over 100 seeds. Omitting one precondition, exclusion of the non-stationary training transient, gives false-positive rates of 100.00% and 99.95%: agents annealing exploration independently, in runs that never met, are flagged as influencing one another. Excluding the transient reaches 3.0% in the social dilemma but 11.8% in the coordination game, which stationarity tests explain: 95.7% of social-dilemma series are stationary afterwards against 56.8% of coordination series. So the non-stationarity must be treated, and exclusion is neither the only way nor sufficient. What we recommend instead changes the null model rather than the data: permuting the source within blocks of training time reaches 5.25% and 5.50%, the only one of four constructions at the size of the test in both games, leaving series, statistic and estimand untouched. Titrating injected links of known strength in both games shows it is also the most sensitive of the three, detecting 89.0% in the coordination game where conditioning detects 61.0% on identical pairs, while the ablated test reports 100% with or without a link, so its apparent sensitivity is uninformative. The block count is not critical: every setting from 16 to 256 lands in the nominal region, and a partition derived from the stationarity test removes the parameter, though less sensitively. Code and data are released.