# Remembering the Markov Property in Cooperative MARL

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 36 references that are in the map.
- First posted on arXiv 24 Jul 2025.

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

- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?](https://mlsanity.com/paper/2011.09533/) (2020)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Machine Theory of Mind](https://mlsanity.com/paper/1802.07740/) (2018)
- [Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks](https://mlsanity.com/paper/2006.07869/) (2020)
- ["Other-Play" for Zero-Shot Coordination](https://mlsanity.com/paper/2003.02979/) (2020)
- [The Hanabi Challenge: A New Frontier for AI Research](https://mlsanity.com/paper/1902.00506/) (2019)
- [FACMAC: Factored Multi-Agent Centralised Policy Gradients](https://mlsanity.com/paper/2003.06709/) (2020)
- [Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems](https://mlsanity.com/paper/1709.08071/) (2017)
- [SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2212.07489/) (2022)
- [Learning Latent Representations to Influence Multi-Agent Interaction](https://mlsanity.com/paper/2011.06619/) (2020)
- [Off-Belief Learning](https://mlsanity.com/paper/2103.04000/) (2021)
- [Heterogeneous-Agent Reinforcement Learning](https://mlsanity.com/paper/2304.09870/) (2023)
- [Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1811.01458/) (2018)
- [Agent Modelling under Partial Observability for Deep Reinforcement Learning](https://mlsanity.com/paper/2006.09447/) (2020)
- [Emergence of Maps in the Memories of Blind Navigation Agents](https://mlsanity.com/paper/2301.13261/) (2023)
- [Deep Interactive Bayesian Reinforcement Learning via Meta-Learning](https://mlsanity.com/paper/2101.03864/) (2021)
- [Order Matters: Agent-by-agent Policy Optimization](https://mlsanity.com/paper/2302.06205/) (2023)
- [Towards Few-shot Coordination: Revisiting Ad-hoc Teamplay Challenge In the Game of Hanabi](https://mlsanity.com/paper/2308.10284/) (2023)
- [Studying the Interplay Between the Actor and Critic Representations in Reinforcement Learning](https://mlsanity.com/paper/2503.06343/) (2025)
- [Partner Modelling Emerges in Recurrent Agents (But Only When It Matters)](https://mlsanity.com/paper/2505.17323/) (2025)

## Abstract (arXiv)

Cooperative multi-agent reinforcement learning (MARL) is typically formalised as a Decentralised Partially Observable Markov Decision Process (Dec-POMDP), where agents must reason about the environment and other agents' behaviour. In practice, current model-free MARL algorithms use simple recurrent function approximators to address the challenge of reasoning about others using partial information. In this position paper, we argue that the empirical success of these methods is not due to effective Markov signal recovery, but rather to learning simple conventions that bypass environment observations and memory. Through a targeted case study, we show that co-adapting agents can learn brittle conventions, which then fail when partnered with non-adaptive agents. Crucially, the same models can learn grounded policies when the task design necessitates it, revealing that the issue is not a fundamental limitation of the learning models but a failure of the benchmark design. Our analysis also suggests that modern MARL environments may not adequately test the core assumptions of Dec-POMDPs. We therefore advocate for new cooperative environments built upon two core principles: (1) behaviours grounded in observations and (2) memory-based reasoning about other agents, ensuring success requires genuine skill rather than fragile, co-adapted agreements.