Source-linked AI summary
Communicating via Markov Decision Processes
Samuel Sokota, Christian Schroeder de Witt, Maximilian Igl, Luisa Zintgraf, Philip Torr, Martin Strohmeier, J. Zico Kolter, Shimon Whiteson, Jakob Foerster
TL;DR
The paper studies communicating exogenous information through MDP trajectories, where actions must balance communication with their control costs. It introduces MEME, combining maximum-entropy reinforcement learning and minimum-entropy coupling. Experiments report strong performance on small MCGs and lossless image communication through Cartpole and Pong trajectories, including under actuator noise.
Problem
MCGs require agents to communicate through MDP actions while balancing communication against the associated cost, a challenge in decentralized control when cheap talk is unavailable.
Source: §1 · pp. 1–2Method
MEME combines maximum-entropy reinforcement learning with minimum-entropy coupling to select actions that preserve the policy’s expected return while reducing receiver uncertainty about the message.
Source: §1 · p. 2Results
Takeaways & Limitations
The experiments show that MEME scales to extremely large message spaces and complex control tasks, transmitting messages with high fidelity even with some actuator noise.
Source: §1 · p. 2, §7 · p. 9Proposition 1 holds only in expectation over messages; for particular messages, the action distribution generally differs from the MaxEnt policy.
Source: §5.2 · p. 6
Abstract
from arXiv · showhide
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.
1. Introduction
Markov coding games (MCGs) communicate private messages through trajectories of an MDP, balancing communication against the cost of actions. The paper introduces MEME and reports strong results on small and large MCGs.
1. Introduction
- An MCG gives a sender a private message to communicate through an MDP trajectory observed by a receiver, with shared payoff combining MDP reward and correct decoding.The sender and receiver are the two agents in a decentralized MDP.Source: §1 · p. 1
- MCGs generalize referential games by allowing communication actions to incur costs through their effects on transitions or rewards.Referential games use cheap-talk actions without those externalities.Source: §1 · p. 1
- MCGs generalize source coding by allowing encoding costs to involve complex considerations rather than only output sequence length.Standard source coding minimizes expected output length.Source: §1 · p. 1
- MCGs isolate a decentralized-control challenge: actions must both control the MDP and communicate implicitly, while communication protocols depend on counterfactuals that violate dynamic programming’s locality assumption.The introduction identifies this as a difficulty for approximate dynamic programming.Source: §1 · pp. 1–2
- MEME combines maximum-entropy reinforcement learning and minimum-entropy coupling to balance expected return with communication through action choices.The method first constructs a maximum-entropy policy, then couples messages with actions to reduce receiver uncertainty while preserving that policy’s action probabilities.Source: §1 · p. 2
- MEMEs achieves an optimal expected return in Cartpole and Pong while losslessly communicating binary images, and its performance decays gracefully as actuator noise increases.On CodeGrid, MEME also significantly outperforms a reinforcement-learning baseline with an optimal receiver for message spaces with cardinalities in the 10s or 100s.Source: §1 · p. 2
2. Related Work
MCGs connect communication through costly MDP actions to multi-agent learning, coding, and diverse-skill research. Their channel costs distinguish them from explicit costless communication channels and extend coding settings with established algorithms.
Multi-Agent Reinforcement Learning
- Unlike multi-agent reinforcement-learning approaches with explicit communication channels, MCG communication costs are dictated by an MDP.The CodeGrid baseline loosely resembles Strouse et al.’s auxiliary-reward approach to actions with high mutual information.Source: §2 · p. 2
Coding
- MCGs subsume length-limited coding and coding with unequal symbol costs, while established algorithms for those settings do not address the more general MCG setting.These coding extensions optimize expected sequence length under a maximum-length constraint or minimize cumulative symbol cost, respectively.Source: §2 · p. 2
- Unlike Markov-channel and intersymbol-interference settings, MCGs use the Markov system to control channel cost rather than transmission quality.MCGs are more like reliable channels whose costs vary naturally or with sender use.Source: §2 · pp. 2–3
Diverse Skill Learning
- MCGs resemble diverse-skill learning because skills can be interpreted as messages and discriminability as mutual information between skill and state.The CodeGrid baseline can also be viewed as an adaptation of an idealized DIAYN approach to MCGs.Source: §2 · p. 3
3. Background and Notation
The background defines episodic MDPs and introduces entropy, mutual information, the data-processing inequality, and minimum-entropy coupling. These concepts frame how policy uncertainty and information shared through actions can be described.
Markov Decision Processes
- An episodic MDP uses states, actions, rewards, transitions, and a policy; its objective is to maximize expected cumulative reward over terminal histories.A history records states and actions, and terminates after a finite number of transitions.Source: §3 · p. 3
Entropy
- Entropy measures uncertainty in a random variable, while conditional entropy describes action uncertainty given the state across decision points.The maximum-entropy RL objective trades off expected reward against cumulative conditional action entropy using temperature α.Source: §3 · p. 3
Mutual Information
- Mutual information measures dependence between variables and can be interpreted as the uncertainty about one variable eliminated by observing the other.The rain-and-umbrella example contrasts perfect, partial, and absent mutual information.Source: §3 · p. 3, Figure 2 · p. 3
- Mutual information can quantify communication when only an auxiliary variable’s realization is shared, by measuring its dependence with the variable of interest.Source: §3 · p. 4
The Data Processing Inequality
- When X and Z are conditionally independent given Y, the data-processing inequality states that I(X; Y) ≥ I(X; Z).The figure caption specifies the graphical-model condition and absence of confounding variables.Source: §3 · p. 4, Figure 3 · p. 4
Minimum Entropy Coupling
- Minimum-entropy coupling finds a joint distribution with fixed marginals and minimal joint entropy, equivalently maximizing mutual information between the variables.The passage notes that the problem is NP-hard and begins to describe approximation work.Source: §3 · p. 4, Figure 4 · p. 4
4. Markov Coding Games
This section defines MCGs as trajectory-based communication games with joint return-and-decoding objectives, then shows how the formalism recovers referential games and source-coding variants.
4. Markov Coding Games
- An MCG pairs an MDP with messages and a prior: the sender encodes a sampled message in a trajectory, and the receiver estimates it, optimizing return plus decoding accuracy.When a suitable distance function is available, the objective can instead minimize the distance between the message and the guess.Source: §4 · p. 4
4.1. An Example
- In the two-message, three-action example, babbling yields 4 + ζ/2 and can perform arbitrarily poorly as message priority ζ becomes large.Independent approximate dynamic-programming learning can settle on reward-maximizing action a, leaving the receiver to guess randomly and the sender without an incentive to communicate.Source: §4.1 · pp. 4–5
4.2. Special Cases
- The MCG formalism represents T-step referential games and standard, length-limited, and unequal-symbol-cost source coding as special cases.Source: §4.2 · p. 5
5. Maximum Entropy Reinforcement Learning and Minimum Entropy Coupling
MEME balances MDP reward and communication by first constructing a high-reward, high-entropy policy, then coupling its action distribution with message beliefs. Its analysis establishes expected-return preservation and greedy one-step information maximization subject to that preservation, while large message spaces require a factored approximation.
5.1. Method Description (MEME)
- MEME first computes a message-independent MaxEnt MDP policy, then uses minimum entropy coupling between the message posterior and action distribution to create a message-conditional policy online.The receiver reconstructs that policy along the trajectory, updates the posterior, and selects its maximum a posteriori message.Source: §5.1 · pp. 5–6
5.2. Method Analysis
- In expectation over messages, MEME preserves the MaxEnt policy’s action probabilities and expected MDP return, though individual messages can have different action distributions and returns.The preservation guarantees are aggregate, not message-by-message.Source: §5.2 · p. 6
- At each decision point, MEME greedily maximizes mutual information between the message and next history, subject to the action-probability preservation guarantee.The analysis links this objective to minimizing the joint entropy of messages and actions while their marginals are fixed.Source: §5.2 · pp. 6–7
5.3. Scalability
- For large message spaces, MEME factors messages into blocks and couples only the highest-entropy block at each step, reducing coupling size while retaining Proposition 2’s guarantees.The procedure uses approximate coupling and approximate posteriors for non-factorable priors, so Proposition 3 no longer holds, although mutual information remains high in practice.Source: §5.3 · p. 7
6. Experiments
The experiments compare MEME with an RL-plus-perfect-receiver baseline on CodeGrid and test MEME on large binary-image message spaces in Cartpole and Pong, including actuator noise. MEME retains near-optimal CodeGrid performance as the message space grows, and without actuator noise it transmits images perfectly while achieving maximum MDP return in both larger environments.
CodeGrid
- CodeGrid compares MEME with RL+PR across message-space sizes, plotting correct-guess proportion against MDP payoff.The grid task rewards reaching the opposite corner within eight steps; RL+PR pairs an RL sender with a receiver that computes the exact message posterior and guesses MAP.Source: §6 · p. 8
- MEME remains optimal or near optimal at 64 and 128 messages, while RL+PR transmission falls to only slightly above half at 128 messages.At 8 and 32 messages, both methods achieve optimal or nearly optimal MDP returns and transmission.Source: §6 · p. 8
CodeCart and CodePong
- The experiments use CodeGrid, CodeCart, and CodePong; the latter two encode uniformly distributed 16 × 16 and 22 × 22 binary images, respectively.Their message spaces are exceedingly large, and MEME uses a factorization scheme to scale to them.Source: §6 · p. 8
- With no actuator noise, MEME perfectly transmits images while achieving maximum MDP return in both CodeCart and CodePong.This occurs at log β ∈{−10, −1, 0.1} for CodeCart and log β ∈{4, 5} for CodePong.Source: §6 · p. 9
- Under actuator noise, CodeCart retains maximal MDP performance as transmission errors grow, whereas CodePong retains perfect transmission as MDP return declines.At p = 0.05, Cartpole's visual degradation at log β = −1 is difficult to perceive, while the CodePong sender wins roughly 80% of games at log β = 5.Source: §6 · p. 9
7. Conclusions and Future Work
The paper introduces Markov coding games and MEME, reporting theoretical guarantees and empirical performance across small and extremely large message spaces. It also outlines possible security applications and future work on more general minimum-entropy coupling.
Conclusion
- Markov coding games generalize referential games and source coding and relate to channel coding and decentralized control.The paper contributes MEME, with provable guarantees for MDP return and communicated information, and reports that it significantly outperforms an RL baseline with a perfect receiver.Source: §7 · p. 9
- MEME transmitted extremely large messages with high fidelity, including with some actuator noise, in experiments on Cartpole and Pong.The authors suggest this could make MEME robust in real-world settings.Source: §7 · p. 9
Security
- Trajectory-based communication could let an agent communicate privileged information to an ally while denying that communication occurred, due to Proposition 1.The paper presents this as an alternative to encrypted channels that may reveal sensitive communication to an adversary.Source: §7 · p. 9
Iterative Minimum Entropy Coupling
- The coupling procedure iteratively approximately couples a block-factorable distribution with an autoregressively specified one.Future work could extend it to two autoregressively specified distributions, potentially improving MEME when the belief prior is not factorable and supporting low-entropy couplings with large supports.Source: §7 · p. 9
A. Experimental Details
The experimental details specify the policy architectures, training budgets, initialization, and optimizer used across CodeGrid, CodeCart, and CodePong.
A. Experimental Details
- CodeGrid uses a two-layer fully connected policy with 64 hidden units per layer, while CodeCart and CodePong use a three-layer convolutional encoder followed by a fully connected layer.The convolution layers use (channels, kernel size, stride) settings (32,8,4), (64,4,2), and (64,3,1), with ReLU activations and no max-pooling.Source: A. Experimental Details · p. 12
- Training runs for 200k episodes on CodeGrid and 2M on CodePong; CodeCart starts from an optimally trained DQN policy and is fine-tuned for 15k steps per β.CodeGrid and CodePong weights are randomly initialized using PyTorch 1.7 defaults.Source: A. Experimental Details · p. 12
- All environments use Adam with learning rate 10^-4, β1 = 0.9, β2 = 0.999, and ϵ = 10^-8; Figures 7 and 8 average 10 rollouts.Figure 8 reports standard error.Source: A. Experimental Details · p. 12
CodeGrid
The supplied passages describe two possible CodeGrid trajectories and specify that CodeCart and CodePong use action spaces without redundant communication actions.
CodeGrid
- Figure 9 illustrates two possible CodeGrid trajectories, one of length 6 and one of length 8.Source: Figure 9 · p. 12
CodeCart
- CodeCart uses left and right actions, with no redundant actions available for communication.Source: CodeGrid · p. 12
CodePong
- CodePong uses a reduced two-action space—up and down—with no redundant actions available for communication.Source: CodeGrid · p. 12
B.1. Factored MEME
Factored MEME first computes a maximum-entropy policy, then uses minimum-entropy coupling to coordinate message beliefs with policy actions. The sender updates beliefs while generating a trajectory, and the receiver uses that trajectory to infer the message.
B.1. Factored MEME
- MEME computes a maximum-entropy reinforcement-learning policy for the MDP at temperature α.Source: §B.1 · p. 13
- The sender updates the active belief after each action and advances the MDP; the receiver processes the observed trajectory to update beliefs and decode a message.Source: §B.1 · p. 13
- At each sender step, MEME couples the highest-entropy message-belief block with the policy’s action distribution and samples an action conditional on the message.Source: §B.1 · p. 13
B.2. RL+PR baseline
The RL+PR baseline samples message-conditioned actions and updates beliefs during MDP interaction. The accompanying minimum-entropy joint-distribution algorithm constructs a coupling in sparse form using row and column priority queues.
B.2. RL+PR baseline
- The RL+PR baseline samples actions from a message-conditioned policy, updates beliefs, samples transitions, and adds experience to a buffer.Source: §B.2 · p. 14
B.3. Min Entropy Joint Distribution Algorithm outputting a sparse representation of M (Cicalese et al., 2019)
- The minimum-entropy joint-distribution algorithm takes distributions p and q as input and outputs their coupling as a sparse representation.Source: §B.3 · p. 15
- The coupling procedure initializes shared mass from p ∧ q and assigns extracted minima to row or column entries, using Lemma3-Sparse to distribute mass.Source: §B.3 · p. 15
- Lemma3-Sparse selects queue elements so the returned residual masses and selected entries satisfy the stated mass constraints.Source: §B.3 · p. 15