# Communicating via Markov Decision Processes

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 17 Jul 2021.

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

- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Learning Multiagent Communication with Backpropagation](https://mlsanity.com/paper/1605.07736/) (2016)
- [TarMAC: Targeted Multi-Agent Communication](https://mlsanity.com/paper/1810.11187/) (2018)
- [Emergence of Linguistic Communication from Referential Games with Symbolic and Pixel Input](https://mlsanity.com/paper/1804.03984/) (2018)
- [Learning Efficient Multi-agent Communication: An Information Bottleneck Approach](https://mlsanity.com/paper/1911.06992/) (2019)
- [Learning Agent Communication under Limited Bandwidth by Message Pruning](https://mlsanity.com/paper/1912.05304/) (2019)
- [Learning to Share and Hide Intentions using Information Regularization](https://mlsanity.com/paper/1808.02093/) (2018)
- [Minimum--Entropy Couplings and their Applications](https://mlsanity.com/paper/1901.07530/) (2019)
- [Inference-Based Deterministic Messaging For Multi-Agent Communication](https://mlsanity.com/paper/2103.02150/) (2021)

## Built on by (most cited first, 10 of 10)

- [Secret Collusion among AI Agents: Multi-Agent Deception via Steganography](https://mlsanity.com/paper/2402.07510/) (2024)
- [Hidden in Plain Text: Emergence & Mitigation of Steganographic Collusion in LLMs](https://mlsanity.com/paper/2410.03768/) (2024)
- [Perfectly Secure Steganography Using Minimum Entropy Coupling](https://mlsanity.com/paper/2210.14889/) (2022)
- [Minimum Entropy Coupling with Bottleneck](https://mlsanity.com/paper/2410.21666/) (2024)
- [Cheap Talk Discovery and Utilization in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2303.10733/) (2023)
- [On the Role of Emergent Communication for Social Learning in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2302.14276/) (2023)
- [Learning to Match Unpaired Data with Minimum Entropy Coupling](https://mlsanity.com/paper/2503.08501/) (2025)
- [Despite Instructions: Frontier Agents Improvise Covert Channels at Test Time](https://mlsanity.com/paper/2609.32701/) (2026)
- [Learning from Totally Unpaired Data via Minimum Conditional Entropy Coupling](https://mlsanity.com/paper/2605.16229/) (2026)
- [Embedding Information in Policy Randomness: Distribution-Preserving Implicit Communication in MDPs](https://mlsanity.com/paper/2610.15976/) (2026)

## Abstract (arXiv)

We consider the problem of communicating exogenous information by means of Markov decision process trajectories. This setting, which we call a Markov coding game (MCG), generalizes both source coding and a large class of referential games. MCGs also isolate a problem that is important in decentralized control settings in which cheap-talk is not available -- namely, they require balancing communication with the associated cost of communicating. We contribute a theoretically grounded approach to MCGs based on maximum entropy reinforcement learning and minimum entropy coupling that we call MEME. Due to recent breakthroughs in approximation algorithms for minimum entropy coupling, MEME is not merely a theoretical algorithm, but can be applied to practical settings. Empirically, we show both that MEME is able to outperform a strong baseline on small MCGs and that MEME is able to achieve strong performance on extremely large MCGs. To the latter point, we demonstrate that MEME is able to losslessly communicate binary images via trajectories of Cartpole and Pong, while simultaneously achieving the maximal or near maximal expected returns, and that it is even capable of performing well in the presence of actuator noise.