REVIEW 4 major objections 6 minor 36 references
Remembering the Markov Property in Cooperative MARL
T0 review · 4 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read This paper argues that the empirical success of model-free cooperative MARL is driven by brittle conventions that ignore observations and memory, and that cooperative benchmarks must be redesigned to force grounded, memory-based behavior.
desk verdict Strong Prediction Game case study, but the Section 5 benchmark claims rest on correlational MI and FF/RNN parity without causal ablations — treat them as a hypothesis, not settled evidence. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central measurement device is paired mutual information statistics: I(O;A), between an agent's observation and its chosen action, and I(H;A), between its recurrent hidden state and its action, estimated with a k-NN estimator and averaged over agents. Low values are interpreted as evidence that the policy bypasses sensory input and memory. The complementary mechanism is the blind environment variant, which removes observations entirely, and the Prediction Game, which explicitly rewards predicting neighbors' next actions. This combination lets the paper attribute high returns to conventions rather than Markov-state recovery, and to show that when conventions are impossible, recurrent policies learn grounded, history-dependent behavior.
What would settle it
Mask the observation input and hidden state of trained agents in Hanabi, SMAX, and MaBrax and measure the return drop; if policies with low measured I(O;A) and I(H;A) still lose substantial performance when observations are masked, then low mutual information does not indicate that the policy bypasses sensory input. Conversely, on a task where the optimal policy provably requires history, the estimator should return high values; a failure there would undercut the diagnostic.
Extended reading notes
Core claim
The central claim is that model-free MARL policies succeed on cooperative benchmarks not by recovering a Markovian signal—a belief over the joint state and other agents' policies—but by learning simple conventions that bypass both observations and memory. In the Prediction Game, concurrently trained IPPO agents, including fully blind agents with no observations, all reach near-optimal returns, and mutual information I(O;A) and I(H;A) is low. Performance collapses when two agents are replaced by fixed heuristic partners, demonstrating that the learned policies are brittle conventions. When partners follow phase-randomized periodic cycles, learning agents must infer the hidden phase from observations; recurrent policies succeed and mutual information rises, while blind agents fail, showing the models can learn grounded policies when the task requires it. A mutual-information analysis of Hanabi, MaBrax, and SMAX then shows Hanabi demands observation grounding but not memory, MaBrax lets blind agents achieve non-trivial returns, and SMAX requires only moderate history reliance. The paper concludes that modern MARL environments do not adequately force the reasoning capacities that Dec-POMDPs assume, and that benchmarks should be redesigned around observation-grounded behavior and memory-based reasoning about other agents.
Load-bearing premise
The load-bearing premise is that the k-NN mutual-information estimates, averaged over agents, faithfully measure how much a policy relies on its observations and memory; if that estimator is biased for recurrent or high-dimensional policies, the benchmark conclusions weaken.
Editorial extensions
If this is right
- If co-trained successes are conventions, then existing benchmark rankings may partly measure how easily agents coordinate shortcuts, not how well they track hidden state or model teammates.
- Hanabi, despite requiring observation-grounded play, can be solved with no history, so it tests groundedness but not memory-based reasoning; feed-forward matching recurrent performance is the evidence.
- MaBrax locomotion instances do not require partner modeling or even observations, since blind agents achieve non-trivial returns; using them as cooperative MARL benchmarks can overstate progress.
- SMAC-v2/SMAX is an improvement over the original SMAC, yet its mutual-information values remain moderate, so it still leaves room for environments that force stronger history-based reasoning.
- Following the two design principles—observation-grounded behavior and memory-based reasoning about others—should make success require genuine Dec-POMDP skill rather than fragile co-adaptation.
Reading between the lines
- The same mutual-information diagnostic could be applied to zero-shot coordination and ad-hoc teamwork benchmarks as a pre-registered sanity check before trusting a ranking, an extension the paper does not perform.
- If the diagnostic logic is sound, a testable prediction follows: in redesigned benchmarks, the gap between recurrent and memoryless policies, and between sighted and blind agents, should widen substantially; current small gaps are the failure signature.
- The critique may carry over to single-agent POMDP benchmarks, where recurrent agents could also exploit task-specific conventions; the paper's blind-agent test could be adapted there.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper argues that the empirical success of model-free cooperative MARL methods on standard benchmarks is explained not by recovery of a Markov signal (i.e., state estimation and agent modelling) but by learning simple, brittle conventions that bypass observations and memory. The authors first build a custom Prediction Game in which four IPPO agents with feed-forward or recurrent policies, and even blind variants receiving no observations, all reach near-optimal returns while exhibiting low mutual information between observations/actions and hidden state/actions; when two agents are replaced by fixed heuristic partners, performance collapses, showing the learned behaviour is a non-generalising convention. In a heterogeneous variant where partners follow random-phase periodic policies, RNN policies succeed with markedly higher MI, FF policies do worse, and blind agents fail, indicating that grounded, memory-based policies are learnable when the task requires them. The paper then applies the same MI and feed-forward-versus-recurrent diagnostics to Hanabi, MaBrax, and SMAX, concluding that Hanabi does not require memory, MaBrax can be solved without observations, and SMAX, while improved, still does not strongly require history-based reasoning. The authors conclude that benchmarks should be redesigned to enforce observation-grounded and memory-based behaviour.
Significance. If the central claim holds, the paper makes a valuable diagnostic contribution: benchmark rankings in cooperative MARL may partly reflect co-adapted conventions rather than the temporal reasoning and belief maintenance that Dec-POMDP theory treats as essential. The Prediction Game is a well-designed controlled study with a genuinely informative negative result (blind agents succeed under concurrent training) and a positive control (random-phase heuristic partners force grounded memory use). The paper also usefully connects its findings to prior work on SMAC-v2 open-loop policies and extends the critique to newer benchmarks such as MaBrax and SMAX. The main weakness is that the benchmark conclusions in Section 5 rest on correlational evidence—MI estimates and architecture comparisons—rather than direct interventions on trained policies, so the strong interpretation of those results is not yet fully supported.
major comments (4)
- [Section 5, Fig. 5] The Section 5 benchmark claims that Hanabi, MaBrax, and SMAX policies do not rely on observations or memory are inferred only from I(O;A), I(H;A), and feed-forward-versus-recurrent performance parity; these are correlational proxies rather than direct evidence about the trained policies. Low MI can coexist with rare but decision-critical observation use, and FF≈RNN can arise from under-training or from an observation function that already exposes the belief state. The authors should add evaluation-time interventions, for example replacing observations with noise, resetting or zeroing the recurrent state, or freezing the partner policy, and then report the resulting returns. Without such ablations, the strong reading that modern benchmarks measure brittle conventions rather than Markov-signal recovery is established only in the Prediction Game, not in Section 5.
- [Section 3, Mutual Information] The k-NN mutual information estimator is applied to high-dimensional observations and recurrent hidden states, but the paper does not report the neighbor count k, does not validate the estimator on variables with known MI, and does not discuss bias for continuous or near-deterministic features. The I(O;A) and I(H;A) values in Figures 3–5 are therefore not yet interpretable as reliable measures of policy dependence. The authors should provide calibration experiments on synthetic data with known MI and report estimator settings for each environment.
- [Section 5, Hanabi paragraph and footnote 2] The Hanabi experiments use an observation that includes the entire discard pile, as acknowledged in footnote 2. This makes the feed-forward policy's observation nearly sufficient for the information that a memory-based policy would otherwise need to accumulate, so the FF≈RNN result may be an artifact of the chosen observation function rather than evidence that Hanabi does not test memory. The claim that the task 'can be solved with no notion of history' should be tested with a top-card-only observation, or the conclusion should be explicitly restricted to this specific observation encoding.
- [Section 5, MaBrax and Fig. 8] For MaBrax, the claim that blind agents achieve 'non-trivial' performance is not quantified against a random-policy baseline or a fully-observable upper bound, and the return scales differ widely across the five instances shown in Fig. 7. Please report normalized scores or explicit baselines so the reader can assess how much of each task is solvable without observations, and clarify what threshold would count as 'non-trivial'.
minor comments (6)
- [Section 4, first paragraph] The text contains a typo: 'Esch agent then selects' should read 'Each agent then selects'.
- [Section 4, introductory paragraph] The phrase 'We address push this idea further' is grammatically incomplete and should be revised.
- [Figure 3 caption] The caption labels panel (c) as 'histories' but the quantity plotted is the mutual information between the GRU hidden state and actions; please use consistent terminology.
- [Figure 5, panels d–g] The captions state approximate MI maxima but do not specify the action-space cardinality for Hanabi; adding H(A) explicitly would help readers interpret the percentages quoted in the SMAX paragraph.
- [Appendix A.1] The heuristic policy formula uses floor notation without defining it; adding a short definition would improve clarity.
- [Section 6, Next-steps] The limitation to Independent PPO without parameter sharing and without centralised critics is appropriately acknowledged only in the conclusions; it would be clearer to state this restriction in the experimental setup of Section 4 as well.
Circularity Check
No circular derivation: empirical evidence with independent causal controls; the one self-citation is not load-bearing.
full rationale
The paper is an empirical position paper rather than a derivational one. Its central claim—that model-free MARL success on benchmarks can reflect learned conventions rather than Markov-signal recovery—is supported by (i) blind-agent ablations in the Prediction Game, (ii) a heterogeneous variant with random-phase heuristic partners that forces grounded, memory-based policies, and (iii) benchmark comparisons against external environments (Hanabi, MaBrax, SMAX). No parameter is fitted to force the conclusion, and the 'same models can learn grounded policies when the task necessitates it' result provides an independent check that the learnt failures are due to task design rather than model capacity. The mutual-information estimates are treated as evidence, but low MI is not definitionally equivalent to the paper's conclusion; the claim also rests on behaviour (blind-agent returns, FF/RNN gaps, heuristic-partner failures). Possible weaknesses in the MI estimator or in the interpretation of FF≈RNN are correctness risks, not circularity. The only notable author-overlapping citation is Garcin et al. (2025) for the k-NN MI estimator; this is a standard estimator originally due to Kraskov et al. (2004) and Ross (2014), and the present conclusions do not hang on that specific citation. Thus no self-definitional, fitted-input, or self-citation-reduction pattern is present. The paper's Section 5 benchmark claims would be stronger with direct interventions on trained policies (e.g., noise-replaced observations or resetting recurrent state), but the absence of such ablations is an evidential limitation, not a circularity. Score 1 reflects only the incidental non-load-bearing self-citation.
Assumptions & free parameters
free parameters (2)
- k-NN MI estimator neighbor count k =
not reported
- Per-environment PPO hyperparameters (learning rate, clipping, value coefficient) =
see Appendix A.4 tables
assumptions (4)
- domain assumption Dec-POMDP is the appropriate formal model for cooperative MARL under partial observability
- domain assumption Low mutual information I(O;A) or I(H;A) implies the policy is not grounded in observations or memory
- domain assumption Random initial phase of heuristic partners in the Prediction Game forces memory-based inference
- domain assumption Action entropy H(A) is the right normalization for comparing MI across environments
Cite this review
Pith. "Pith review of Remembering the Markov Property in Cooperative MARL." pith.science (2026). https://pith.science/paper/7DDYGFSG
@misc{pith2026250718333,
author = {Pith},
title = {Pith review of: Remembering the Markov Property in Cooperative MARL},
year = {2026},
howpublished = {\url{https://pith.science/paper/7DDYGFSG}},
note = {Machine review of arXiv:2507.18333}
}
read the original abstract
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.
Figures
Figures from the paper (5 more)
Reference graph
Works this paper leans on
-
[1]
Autonomous agents modelling other agents: A comprehensive survey and open problems
Stefano V Albrecht and Peter Stone. Autonomous agents modelling other agents: A comprehensive survey and open problems. Artificial Intelligence, 258: 0 66--95, 2018
work page 2018
-
[2]
Albrecht, Filippos Christianos, and Lukas Sch\"afer
Stefano V. Albrecht, Filippos Christianos, and Lukas Sch\"afer. M ulti- A gent R einforcement L earning: Foundations and modern approaches . MIT Press, 2024
work page 2024
-
[3]
Optimal control of M arkov processes with incomplete state information
Karl Johan str \"o m. Optimal control of M arkov processes with incomplete state information. Journal of Mathematical Analysis and Applications, 10 0 (1): 0 174--205, 1965
work page 1965
-
[4]
The hanabi challenge: A new frontier for ai research
Nolan Bard, Jakob N Foerster, Sarath Chandar, Neil Burch, Marc Lanctot, H Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, et al. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 280: 0 103216, 2020
2020
-
[5]
The complexity of decentralized control of markov decision processes
Daniel S Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of markov decision processes. Mathematics of operations research, 27 0 (4): 0 819--840, 2002
work page 2002
-
[6]
Christian Schroeder De Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint arXiv:2011.09533, 2020
arXiv 2011
-
[7]
Smacv2: An improved benchmark for cooperative multi-agent reinforcement learning
Benjamin Ellis, Jonathan Cook, Skander Moalla, Mikayel Samvelyan, Mingfei Sun, Anuj Mahajan, Jakob Foerster, and Shimon Whiteson. Smacv2: An improved benchmark for cooperative multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 36: 0 37567--37593, 2023
work page 2023
-
[8]
Bayesian action decoder for deep multi-agent reinforcement learning
Jakob Foerster, Francis Song, Edward Hughes, Neil Burch, Iain Dunning, Shimon Whiteson, Matthew Botvinick, and Michael Bowling. Bayesian action decoder for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp.\ 1942--1951. PMLR, 2019
work page 1942
Show all 36 references
-
[9]
Studying the interplay between the actor and critic representations in reinforcement learning
Samuel Garcin, Trevor McInroe, Pablo Samuel Castro, Prakash Panangaden, Christopher G Lucas, David Abel, and Stefano V Albrecht. Studying the interplay between the actor and critic representations in reinforcement learning. arXiv preprint arXiv:2503.06343, 2025
2025 arXiv
-
[10]
Deep recurrent q-learning for partially observable mdps
Matthew J Hausknecht and Peter Stone. Deep recurrent q-learning for partially observable mdps. In AAAI fall symposia, volume 45, pp.\ 141, 2015
2015
-
[11]
other-play
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. “other-play” for zero-shot coordination. In International Conference on Machine Learning, pp.\ 4399--4410. PMLR, 2020
2020
-
[12]
Off-belief learning
Hengyuan Hu, Adam Lerer, Brandon Cui, Luis Pineda, Noam Brown, and Jakob Foerster. Off-belief learning. In International Conference on Machine Learning, pp.\ 4369--4379. PMLR, 2021
2021
-
[13]
Planning and acting in partially observable stochastic domains
Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101 0 (1-2): 0 99--134, 1998
1998
-
[14]
Multi-agent reinforcement learning as a rehearsal for decentralized planning
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190: 0 82--94, 2016
2016
-
[15]
Estimating mutual information
Alexander Kraskov, Harald St \"o gbauer, and Peter Grassberger. Estimating mutual information. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 69 0 (6): 0 066138, 2004
2004
-
[16]
Nonapproximability results for partially observable M arkov D ecision P rocesses
Christopher Lusena, Judy Goldsmith, and Martin Mundhenk. Nonapproximability results for partially observable M arkov D ecision P rocesses. Journal of artificial intelligence research, 14: 0 83--103, 2001
2001
-
[17]
Partner modelling emerges in recurrent agents (but only when it matters)
Ruaridh Mon-Williams, Max Taylor-Davies, Elizabeth Mieczkowski, Natalia Velez, Neil R Bramley, Yanwei Wang, Thomas L Griffiths, and Christopher G Lucas. Partner modelling emerges in recurrent agents (but only when it matters). arXiv preprint arXiv:2505.17323, 2025
2025 arXiv
-
[18]
Towards few-shot coordination: Revisiting ad-hoc teamplay challenge in the game of hanabi
Hadi Nekoei, Xutong Zhao, Janarthanan Rajendran, Miao Liu, and Sarath Chandar. Towards few-shot coordination: Revisiting ad-hoc teamplay challenge in the game of hanabi. In Conference on Lifelong Learning Agents, pp.\ 861--877. PMLR, 2023
2023
-
[19]
Optimal and approximate q-value functions for decentralized pomdps
Frans A Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32: 0 289--353, 2008
2008
-
[20]
A concise introduction to decentralized POMDPs, volume 1
Frans A Oliehoek, Christopher Amato, et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016
2016
-
[21]
The complexity of M arkov D ecision P rocesses
Christos H Papadimitriou and John N Tsitsiklis. The complexity of M arkov D ecision P rocesses. Mathematics of Operations Research, 12 0 (3): 0 441--450, 1987
1987
-
[22]
Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks
Georgios Papoudakis, Filippos Christianos, Lukas Sch \"a fer, and Stefano V Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks. arXiv preprint arXiv:2006.07869, 2020
2006 arXiv
-
[23]
Agent modelling under partial observability for deep reinforcement learning
Georgios Papoudakis, Filippos Christianos, and Stefano Albrecht. Agent modelling under partial observability for deep reinforcement learning. Advances in Neural Information Processing Systems, 34: 0 19210--19222, 2021
2021
-
[24]
Facmac: Factored multi-agent centralised policy gradients
Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Pierre-Alexandre Kamienny, Philip Torr, Wendelin B \"o hmer, and Shimon Whiteson. Facmac: Factored multi-agent centralised policy gradients. Advances in Neural Information Processing Systems, 34: 0 12208--12221, 2021
2021
-
[25]
Machine theory of mind
Neil Rabinowitz, Frank Perbet, Francis Song, Chiyuan Zhang, SM Ali Eslami, and Matthew Botvinick. Machine theory of mind. In International conference on machine learning, pp.\ 4218--4227. PMLR, 2018
2018
-
[26]
Mutual information between discrete and continuous data sets
Brian C Ross. Mutual information between discrete and continuous data sets. PloS one, 9 0 (2): 0 e87357, 2014
2014
-
[27]
Jaxmarl: Multi-agent rl environments in jax
Alexander Rutherford, Benjamin Ellis, Matteo Gallici, Jonathan Cook, Andrei Lupu, Gardar Ingvarsson, Timon Willi, Akbir Khan, Christian Schroeder de Witt, Alexandra Souly, et al. Jaxmarl: Multi-agent rl environments in jax. arXiv preprint arXiv:2311.10090, 2023
2023 arXiv
-
[28]
The starcraft multi-agent challenge
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv:1902.04043, 2019
1902 arXiv
-
[29]
Sutton and Andrew G
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: A n Introduction . The MIT Press, Cambridge, MA, 1998
1998
-
[30]
Order matters: Agent-by-agent policy optimization
Xihuai Wang, Zheng Tian, Ziyu Wan, Ying Wen, Jun Wang, and Weinan Zhang. Order matters: Agent-by-agent policy optimization. In The Eleventh International Conference on Learning Representations, 2023
2023
-
[31]
Emergence of maps in the memories of blind navigation agents
Erik Wijmans, Manolis Savva, Irfan Essa, Stefan Lee, Ari S Morcos, and Dhruv Batra. Emergence of maps in the memories of blind navigation agents. In The Eleventh International Conference on Learning Representations, 2023
2023
-
[32]
Learning latent representations to influence multi-agent interaction
Annie Xie, Dylan Losey, Ryan Tolsma, Chelsea Finn, and Dorsa Sadigh. Learning latent representations to influence multi-agent interaction. In Conference on robot learning, pp.\ 575--588. PMLR, 2021
2021
-
[33]
The surprising effectiveness of ppo in cooperative multi-agent games
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. Advances in Neural Information Processing Systems, 35: 0 24611--24624, 2022
2022
-
[34]
Heterogeneous-agent reinforcement learning
Yifan Zhong, Jakub Grudzien Kuba, Xidong Feng, Siyi Hu, Jiaming Ji, and Yaodong Yang. Heterogeneous-agent reinforcement learning. Journal of Machine Learning Research, 25 0 (32): 0 1--67, 2024
2024
-
[35]
Deep interactive bayesian reinforcement learning via meta-learning
Luisa Zintgraf, Sam Devlin, Kamil Ciosek, Shimon Whiteson, and Katja Hofmann. Deep interactive bayesian reinforcement learning via meta-learning. In International Conference on Autonomous Agents and Multi-Agent Systems, 2021
2021
-
[36]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.