Year: 2021

Abstract:
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 greedy minimum entropy coupling (GME). We show both that GME is able to outperform a relevant baseline on small MCGs and that GME is able to scale efficiently to extremely large MCGs. To the latter point, we demonstrate that GME 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.

heading: 1 INTRODUCTION
text: This work introduces a novel problem setting called Markov coding games (MCGs). MCGs are two-player decentralized Markov decision processes (Oliehoek et al., 2016) that proceed in four steps. In the first step, one agent (called the sender) receives a special private observation (called the message), which it is tasked with communicating. In the second step, the sender plays out an episode of a Markov decision process (MDP). In the third, the other agent (called the receiver) receives the sender’s MDP trajectory as its observation. In the fourth, the receiver estimates the message from the received trajectory. The shared payoff to the sender and receiver is a weighted sum of the cumulative reward yielded by the MDP and an indicator specifying whether or not the receiver correctly decoded the message.
Among the reasons that MCGs are of interest is the fact that they generalize other important settings. The first of these is referential games. In a referential game, a sender attempts to communicate a message to a receiver using cheap talk actions—i.e., communicatory actions that do not have externalities on the transition or reward functions. Referential games have been a subject of academic interest dating back at least as far as Lewis’s seminal work Convention (Lewis, 1969). Since then, various flavors of referential games have been studied in game theory (Skyrms, 2010), artificial life (Steels, 2013), evolutionary linguistics (Smith, 2002), cognitive science (Spike et al., 2017), and machine learning (Lazaridou et al., 2018). MCGs can be viewed as a generalization of referential games to a setting where we drop the often unrealistic assumption that the sender’s actions do not incur costs.
A second problem setting generalized by MCGs is source coding (MacKay, 2002). In source coding (also known as data compression) the objective is to construct an injective mapping from a space of messages to the set of sequences of symbols (for some finite set of symbols) such that the expected output length is minimized. Source coding has a myriad of real world applications involving the compression of images, video, audio, and genetic data. MCGs can be viewed as a generalization of the source coding problem to a setting where the cost of an encoding may involve complex considerations, rather than simply being equal to the sequence length.
Yet another reason to be interested in MCGs is that they isolate an important subproblem of decentralized control. In particular, achieving good performance in an MCG requires the sender’s actions
to simultaneously perform control in an MDP and communicate information (i.e., to communicate implicitly). This presents a challenge due to the fact that approximate dynamic programming, the foundation for preeminent approaches to constructing control policies (Sutton & Barto, 2018), is ill suited to constructing communication protocols because their values depend on counterfactuals. In other words, the information conveyed by an action depends on the policy at other contemporaneous states, violating the locality assumption of approximate dynamic programming approaches.
To address MCGs, we propose a theoretically grounded algorithm called greedy minimum entropy coupling (GME). GME leverages a union of maximum entropy reinforcement learning (MaxEnt RL) (Ziebart et al., 2008) and minimum entropy coupling (MEC) (Kovačević et al., 2015). The key insight is that maximizing the returns of the MDP can be disentangled from learning a good communication protocol by realizing that the entropy of a policy corresponds (in an informal sense) to its capacity to communicate. GME leverages this insight in two steps. In the first step, GME constructs a MaxEnt policy for the MDP, balancing between maximizing expected return and maximizing cumulative conditional entropy. In the second step, which occurs at each decision point, GME uses MEC to pair messages with actions in such a way that the sender selects actions with the same probabilities as the MaxEnt RL policy (thereby guaranteeing the same expected return from the MDP) and the receiver’s uncertainty about the message is greedily reduced as much as possible.
To demonstrate the efficacy of GME, we present experiments for MCGs based on a gridworld, Cartpole, and Pong (Bellemare et al., 2013), which we call CodeGrid, CodeCart, and CodePong, respectively. For CodeGrid, we show that with a message space in the 10s or 100s, GME significantly is able to outperform a relevant baseline. For CodeCart and CodePong, we use a message space of binary images and a uniform distribution over messages, meaning that a randomly guessing receiver has an astronomically small probability of guessing correctly. Remarkably, we show that GME is able to achieve an optimal expected return in Cartpole and Pong while simultaneously losslessly communicating images to the receiver, demonstrating that GME has the capacity to be scaled to extremely large message spaces and complex control tasks. Moreover, we find that the performance of GME decays gracefully as the amount of actuator noise in the environment increases.

heading: 2 RELATED WORK
text: The works that are most closely related to this one can be taxonomized as coming from literature on referential games, source coding, multi-agent reinforcement learning, and diverse skill learning.
Referential Games Among work on referential games, Foerster et al. (2016)’s work is perhaps most similar in that it is concerned with directly optimizing the performance of a communication protocol. They propose DIAL, an algorithm that optimizes the sender’s protocol by performing gradient ascent through the parameters of the receiver. Foerster et al. show that DIAL outperforms methods based on independent Q-learning on a variety of communication tasks. However, DIAL-based approaches are not directly applicable to MCGs, as they would require differentiating through trajectories.
Coding Another body of related work concerns extensions of the source coding problem. Length limited coding (Larmore & Hirschberg, 1990) considers a problem setting in which the objective is to minimize the expected sequence length (as before), subject to a maximum length constraint. Coding with unequal symbol costs (Golin et al., 2002; Iwata et al., 1997) considers the problem in which the goal is to minimize the expected cumulative symbol cost of the sequence to which the message is mapped. The cost of a symbol may differ from the cost of other symbols arbitrarily, making it a strictly more general problem setting than standard source coding (which can also be thought of as minimizing cumulative symbol cost with equally costly symbols). Both length limited coding and coding with unequal costs are subsumed by Markov coding games. And while existing algorithms for both standard source coding and the extensions above are well-established and widely commercialized, they are unable to address the more general MCG setting.
MCGs are also related to finite state Markov channel settings (Wang & Moayeri, 1995). In such settings, the fidelity of the channel by which the sender communicates to a receiver is controlled by a Markov process, which, in contrast to our work, transitions independently of the sender’s decisions. Another related setting is intersymbol interference, where the sender’s previously selected symbols (i.e., actions) may cause interference with subsequently selected symbols, making them less likely to be faithfully transmitted to the receiver (Lathi, 1998). MCGs differ from both Markov channel
and intersymbol interference settings in that the Markov system controls the cost paid by the sender, rather than interfering with the quality of the channel. MCGs are more resemblant of a setting in which the channel is reliable, but subject to natural variation in costs, such as based on weather or third party usage, as well as variation based on the sender’s own usage.
Multi-Agent Reinforcement Learning A third related area comes from MARL literature. Strouse et al. (2018) investigate directly embedding a reward for taking actions with high mutual information into policy gradient objectives. They find that this approach can improve expected return in cooperative settings with asymmetric information. The baseline for our CodeGrid experiments loosely resembles Strouse et al.’s algorithm. More recently, Bhatt & Buro (2021) investigate an alternative approach whereby the sender’s behavioral policy deterministically selects the action that maximizes the receiver’s posterior probability of the correct message, when computed using the target policy. They show that this modification empirically yields significantly improved convergence properties as compared to other variations of independent reinforcement learning. However, this approach is not directly applicable to settings in which a single action must be used for both communication and control.
Diverse Skill Learning A fourth area of related research is that of diverse skill learning (Eysenbach et al., 2019). Eysenbach et al. (2019) propose an unsupervised learning method for discovering diverse, identifiable skills. Their objective, called DIAYN, seeks to learn diverse, discriminable skills. This paradigm resembles our work in the sense that skills can be interpreted as messages and discriminability can be interpreted as maximizing the mutual information between the skill and the state. The baseline used in our CodeGrid experiments can also be viewed as an adaptation of an idealized version of DIAYN to the MCG setting.

heading: 3 BACKGROUND AND NOTATION
text: We will require the following background and notation material to introduce Markov coding games and greedy minimum entropy coupling.
Markov Decision Processes To represent our task formalism, we use finite Markov decision processes (MDPs). We notate MDPs using tuples 〈S,A,R, T 〉 where S is the set of states, A is the set of actions, R : S × A → R is the reward function, and T : S × A → ∆(S) is the transition function. An agent’s interactions with an MDP are dictated by a policy π : S → ∆(A) mapping states to distributions over actions. We focus on episodic MDPs, meaning that after a finite number of transitions have occurred, the MDP will terminate. The history of states and actions is notated using h = (s0, a0, . . . , st). We use the notation R(h) = ∑j R(sj , aj) to denote the amount of reward accumulated over the course of a history. When a history is terminal, we use z to notate it, rather than h. The objective of an MDP is to determine a policy arg maxπEπR(Z) yielding a large cumulative reward in expectation.
Entropy To help us quantify the idea of uncertainty, we introduce entropy. Symbolically, the entropy of a random variable X is H(X) = −E logP(X). Because the logarithm function is concave, the entropy of X is maximized when the mass of PX is spread as evenly as possible and minimized when the mass of PX is concentrated at a single point. In the context of decision-making, entropy can be used to describe the uncertainty regarding which action will be taken by an agent. When a policy spans multiple decision-points, the uncertainty regarding the agent’s actions given that the state is known is naturally described by conditional entropy. Conditional entropy is the entropy of a random variable, conditioned upon the fact that the realization of another random variable is known. More formally, conditional entropy is defined by H(X | Y ) = H(X,Y )−H(Y ) where the joint entropyH(X,Y ) = −E logP(X,Y ) is defined as the entropy of (X,Y ) considered as a random vector.
In some contexts, it is desirable for a decision-maker’s policy to be highly stochastic. In such cases, an attractive alternative to the expected cumulative reward objective is the maximum entropy RL objective Ziebart et al. (2008) maxπ Eπ [ ∑ tR(St, At) + αH(At | St)], which trades off between maximizing expected return and pursuing trajectories along which its actions have large cumulative conditional entropy, using the temperature hyperparameter α.
Mutual Information A closely related concept to entropy is mutual information. Mutual information describes the strength of the dependence between two random variables. The greater the mutual information between two random variables, the more the outcome of one affects the conditional distribution of the other. Symbolically, mutual information is defined by I(X;Y ) = H(Y )−H(Y | X) = H(X)−H(X | Y ). From this definition, we see explicitly that the mutual information of two random variables can be interpreted as the amount of uncertainty about one that is eliminated by observing the realization of the other.
Mutual information is important for communication because we may only be able to share the realization of an auxiliary random variable, rather than that of the random variable of interest. In such cases, maximizing the amount of communicated information amounts to maximizing the mutual information between the auxiliary random variable and the random variable of interest.
The Data Processing Inequality The independence relationships among random variables play an important role in determining their mutual information. If random variables X and Z are conditionally independent given Y (that is, X ⊥ Z | Y ), the data processing inequality states that I(X;Y ) ≥ I(X;Z). Less formally, the data processing inequality states that if Z does not provide additional information about X given Y , then the dependence between X and Z cannot be stronger than the dependence between X and Y .
Minimum Entropy Coupling In some cases, we may wish to maximize the mutual information between two random variables subject to fixed marginals. That is, we are tasked with determining a joint distribution PX,Y that maximizes the mutual information I(X;Y ) between X and Y subject to the constraints that PX,Y marginalizes to PX and PY , where PX and PY are given as input. Invoking the relationship between mutual information and joint entropy I(X;Y ) = H(X) + H(Y ) − H(X,Y ), we see that this problem is equivalent to that of minimizing the joint entropy of X and Y . As a result, this problem is often referred to as the minimum entropy coupling problem. A visual example is shown in Figure 1. While minimum entropy coupling is NP-hard Kovačević et al. (2015), Cicalese et al. (2019) recently showed that there exists a polynomial time algorithm that is suboptimal by no more than one bit.

heading: 4 MARKOV CODING GAMES
text: We are now ready to introduce Markov coding games (MCGs). An MCG is a tuple 〈(S,A, T ,R),M, µ, ζ〉, where (S,A, T ,R) is a Markov decision process,M is a set of messages, µ is a distribution overM, and ζ is a non-negative real number. An Markov coding game proceeds in the following steps:
1. First, a message M ∼ µ is sampled from the prior over messages and revealed to the sender. 2. Second, the sender uses a message conditional policy to generate a trajectory Z ∼ (T , π|M ). 3. Third, the sender’s terminal trajectory Z is given to the receiver as an observation. 4. Fourth, the receiver uses a trajectory conditional policy to estimate the message M̂ ∼ π|Z(Z). The objective of the agents is to maximize the expected weighted sum of the return and the accuracy of the receiver’s estimate E [ R(Z) + ζI[M = M̂ ] ] . Optionally, in cases in which a reasonable
distance function is available, we allow for the objective to be modified to minimizing the distance
between the message and the guess d(M, M̂), rather than maximizing the probability that the guess is correct.
4.1 AN EXAMPLE
A payoff matrix for a simple MCG is shown in Figure 3. In this game, the sender is given one of two messages m or m′, with equal probability. It then chooses among three actions a1, a′1 and a′′1 , for which the rewards are 4, 3, and 0, respectively. The receiver observes the sender’s trajectory (which is equivalent to the sender’s action in MDPs with one state) and estimates the message using actions m̂ and m̂′, corresponding to guessing tom andm′, respectively. The receiver accrues a reward of 4 for guessing correctly. The payoff entries in table denote (R(Z), ζI[M = M̂ ]) for each outcome.
As is generally true of MCGs, this MCG is difficult for independent approximate dynamic programming-based approaches because their learning dynamics are subject to local optima. Consider a run in which the sender first learns to maximize its immediate reward by always selecting a1. Now, the receiver has no reason to condition its guess on the sender’s action because the sender is not communicating any information about the message. As a result, thereafter, the sender has no incentive to communicate any information in its message, because the receiver would ignore it anyways. This outcome, sometimes called a babbling equilibrium, leads to a total expected return of 4 + ζ/2 (sender always selects a1, receiver guesses randomly). In cases in which ζ is small (communication is unimportant), the babbling equilibrium performs well. However, it can perform arbitrarily poorly as ζ becomes large.

heading: 4.2 SPECIAL CASES
text: We can express both (a large class of) referential games and various source coding settings as special cases of the MCG formalism by describing the MDPs to which they correspond.
(A Large Class of) Referential Games We can express a T step referential game as follows.
• The state space S = {s0, s1, . . . , sT }. • The transition function deterministically maps st 7→ st+1 and terminates at input sT . • The reward function maps to zero for every state action pair.
Standard Source Coding We can express the standard source coding problem as follows.
• The state space S = {s}. • The action space A = Ã ∪ {∅}. • The transition function deterministically maps to s to s for a ∈ Ã and terminates the game on ∅. • The reward function maps to −1 for a ∈ Ã and maps ∅ to 0. Length Limited Source Coding Length limited source coding can be captured in the same way as standard source coding with the modifications that S = {s0, s1, . . . , sT }, the transition function terminates on sT , and the reward function yields 0 from sT , where T is the length limit.
Source Coding with Unequal Symbol Costs Source coding with unequal symbol costs can be captured in the same way as standard source coding with the modification that R(·, a) returns the negative symbol cost of a, rather than returning −1, for a ∈ Ã.

heading: 5 GREEDY MINIMUM ENTROPY COUPLING
text: To address MCGs, we propose a novel algorithm we call greedy minimum entropy coupling (GME). GME (and more broadly, any algorithm geared toward MCGs) is faced with two competing incentives. On one hand, it needs to maximize expected rewardR(Z) generated by the MDP. On the other hand, it needs to maximize the amount of information I(M ;Z) communicated to the receiver about the message, so as to maximize the probability of a correct guess. GME handles this trade-off using a two step process for constructing the sender’s policy. In the first step, it computes an MDP policy that balances between high cumulative reward and large cumulative entropy. In the second step, it couples the probability mass of this policy with the posterior over messages in such a way that the expected return does not decrease and the amount of mutual information between the message and trajectory is greedily maximized. We describe these steps below. Thereafter, we show this procedure possesses desirable guarantees and discuss intuition for the method.

heading: 5.1 METHOD DESCRIPTION
text: Step One In the first step, GME uses MaxEnt RL to construct an MDP policy π. This policy is an MDP policy, not an MCG policy, and therefore does not depend on the message. Note that this policy depends on the choice of temperature α used for the MaxEnt RL algorithm.
Step Two In the second step, at execution time, GME constructs a message-conditional policy online. Say that, up to time t, the sender is in state st, history ht and has played according to the message conditional policy π:t|M . Let
bt = P(M | ht, π:t|M ) be the posterior over the message, conditioned on the history and the historical policy. GME performs a MEC between the posterior over the message bt and distribution over actions π(st), as determined by the MDP policy. Let ν = MEC(bt, π(st)) denote joint distribution over messages and actions resulting from the coupling. Then GME sets the sender to act according to the message conditional distribution
πt|M (s t,m) = ν(At |M = m)
of the coupling distribution MEC(bt, π(st)).
Given the sender’s MDP trajectory, GME’s receiver uses the the sender’s MDP policy and MEC procedure to reconstruct the sender’s message conditional policy along the trajectory; thereafter, the receiver computes the posterior and guesses the maximum a posteriori message.
Pseuodocode for GME is included in the appendix.

heading: 5.2 METHOD ANALYSIS
text: GME possesses guarantees both concerning the returnR(Z) generated by the MDP and concerning the amount of information communicated I(M ;Z). Proposition 1. At each state of the MDP, the message conditional policy π|M selects actions with the same probabilities as the MDP policy π.
Proof. Fix an arbitrary state s. Let b be a posterior over the message induced by the sender’s message conditional policy on the way to s. Then recall that GME uses the distribution PMEC(b,π(s)) induced by a MEC between b and π(s) to select its action. Because MECs guarantee that the resultant joint distribution marginalizes correctly, it follows directly that GME must select its actions with the same probabilities as π(s).
Proposition 2. The expected return generated from the MDP by the message conditional policy π|M is equal to that of the MaxEnt policy π. That is,
EM∼µEπ|MR(Z) = EπR(Z).
Proof. It follows from Proposition 1 that all trajectories are generated with the same probabilities and therefore that the expected returns are the same.
Proposition 3. At each decision point, GME greedily maximizes the mutual information I(M ;Ht+1 | bt, ht) between the message M the history at the next time step Ht+1, given the contemporaneous posterior and history, subject to Proposition 1.
Proof. For conciseness, we leave the conditional dependence on bt and ht implicit in the argument. First, we claim that I(M ;Ht+1) = I(M ;At). To see this, first consider that Ht+1 ≡ (ht, At, St+1). This means we have I(M ;Ht+1) = I(M ; (At, St+1)) since we are conditioning on ht. Now, consider that because the message influences the next state only by means of the action, we have the causal graph M → At → (At, St+1), which implies that M ⊥ (At, St+1) | At. Also, we trivially have M ⊥ At | (At, St+1). These conditional independence properties allow us to apply the data processing inequality: X ⊥ Z | Y ⇒ I(X;Y ) ≥ I(X;Z). Applying it in both directions yields I(M ; (At, St+1)) = I(M ;At). Now consider that we can rewrite mutual information using the equality
I(M ;At) = H(M) +H(At)−H(M,At). (1)
The first term H(M) is exogenous by virtue of being determined by bt. The second term is exogenous by virtue of being subject to Proposition 1. The third term is the joint entropy between M and At, which is exactly what a minimum entropy coupling minimizes.

heading: 5.3 METHOD DISCUSSION
text: One aspect of GME that went uncommented upon in the analysis section is the choice of MaxEnt RL for step one. The reason that GME uses MaxEnt RL here is to control the H(At) term in equation (1). If the temperature α is large, GME places more emphasis on maximizing H(At) (and thereby I(M ;Z)); if the temperature α is small, GME places more emphasis on maximizing R(Z). The appropriate choice of αwill depend on the value of ζ. Code for GME that illustrates the functionality of α applied to the example from Figure 3 can be found at https://bit.ly/36I3LDm.
A second aspect of GME that we have yet to discuss is its scalability. Performing an approximate MEC takes O(N logN) time, making it expensive to scale to very large message spaces. To accommodate this fact, for large message spaces we recommend using a factored representation M ⊂ M1 × · · · ×Mk and a corresponding factored belief (b1, . . . , bk), where each bj tracks the posterior over Mj . At each time step, we suggest performing a MEC between π(st) and the block bj = arg maxbjH(bj) having the largest entropy. By doing so, we can substantially reduce the size the of the space over which we need to perform a minimum entropy coupling at any one time, allowing us to scale to extremely large message spaces.

heading: 6 EXPERIMENTS
text: We investigate the efficacy of GME on MCGs based on a gridworld, Cartpole and Pong. For all three we use MaxEnt Q-learning for our MDP policy. Details regarding our implementation can be found in the supplementary material and in the appendix.
For our baseline, we trained an RL agent to play as the MCG sender. We paired this RL agent with an perfect receiver, meaning that, for each episode, the receiver computed the exact posterior over the message based on the sender’s current policy and guessed the MAP, both during training and testing. We abbreviate this baseline as RL+PR (where PR stands for perfect receiver). RL+PR is one way to adapt related work such as (Strouse et al., 2018; Eysenbach et al., 2019) to the MCG setting. Pseudocode for the RL+PR baseline can be found in the appendix.
We show results for GME and RL+PR across a variety of settings in Figure 7. The column of the figure corresponds to the cardinality of the message space; the exact size is listed in the green bubble. We use a uniform marginal over messages in each case. The x-axis corresponds to the proportion of the time that the receiver correctly guesses the message. The y-axis corresponds to the MDP payoff (in this case whether the sender reached the opposing corner of the grid within the time limit). Both GME and RL+PR possess mechanisms to trade-off between these two goals. GME can adjust its temperature α, while RL+PR can adjust the value of ζ used during training. Figure 7 show the Pareto curve for each. For GME, the size of the circle corresponds to the inverse temperature β = 1/α.
For the settings with 8 messages and 32 messages, we observe that both GME and RL+PR achieve strong performance—achieving optimal or nearly optimal MDP returns and optimal or nearly optimal transmission. However, as the size of the message space increases, the performance of RL+PR falls off sharply. Indeed, for the 128 message setting, RL+PR is only able to correctly transmit the message slightly more than half the time. RL+PR’s inability to achieve strong performance in these cases may be a result of the fact that communication protocols violate the locality assumption of approximate dynamic programming approaches. In contrast, we observe that GME, which constructs its protocol using MEC, remains optimal or near optimal both the 64 and the 128 message settings.
CodeCart and CodePong While the CodeGrid experiments that GME can outperform an obvious approach to MCGs, it remains to be determined whether GME can perform well at scale. Toward the end of making this determination, we consider MCGs based on Cartpole and Pong. In these MCGs, the message spaces are the sets of 16 × 16 and 22 × 22 binary images, respectively, each with a uniform prior. The cardinality of these spaces (> 1077 and > 10145) is astronomical. In fact, it is not clear how an RL+PR-like approach could even be scaled to this setting. On the other hand, GME is easily adaptable to this setting, using the factorization scheme suggested in the method section.
We also include results with variable amounts of actuator noise, i.e., with some probability p, the environment executes a random action, rather than the one it intended. Actuator noise models the probability of error during transmission and arises naturally in many settings involving communication, such as noisy channel coding. In this setting, the receiver may only observe the action executed
by the environment, rather than the one intended by the sender. While this setting is not technically an MCG, GME can still be directly applied. And while the derivation of Proposition 3 no longer holds, we suggest that GME nevertheless offers a strong heuristic in such settings.
We show the results in Figure 5 and Figure 6 for CodeCart and CodePong, respectively. For both plots, the y-axis corresponds to the amount of actuator noise (lower is more noise). The x-axis corresponds the inverse temperature value β = 1/α (further right is colder temperature, meaning there is more emphasis on MDP expected return). Each entry contains a decoded yin-yang symbol with the corresponding temperature and actuator noise. Each entry also lists the `1 pixel error (blue) and the MDP expected return (green), along with corresponding standard errors over 10 runs; a brighter color corresponds to better performance.
Remarkably, for both CodeCart and CodePong, we observe that, when there is no actuator noise, GME is able to perfectly transmit images while achieving the maximum expected return in the MDP. For CodeCart, this occurs at log β ∈ {−10,−1, 0.1}; for CodePong, it occurs at log β ∈ {4, 5}. Interestingly, as the amount of actuator noise increases to a non-zero value, the effect on performance differs between CodeCart and CodePong. In CodeCart, GME continues to achieve maximal performance in the MDP, but begins to accumulate errors in the transmission. In contrast, in CodePong, GME continues to transmit the message with perfect fidelity, but begins to lose expected return from the MDP. This suggests that accidentally taking a random action is costlier in Pong than it is in Cartpole, but that, in an informal sense, Pong has more bandwidth to transmit information. However, in both cases, the decay in performance is graceful—for example, with p = 0.05, the decrease in the visual quality of the transmission for Cartpole (log β = −1) is difficult to even perceive, while the CodePong sender still manages to win games roughly 80% of the time (log β = 5). The performance in both settings continues to deteriorate up to p = 1/2, at which point GME is neither able to perform adequately on the MDP nor to transmit a clear symbol.
Videos of the agent playing are included in the supplemental material.

heading: 7 CONCLUSIONS
text: This work introduces a new problem setting called Markov coding games, which generalize referential games and source coding and are related to channel coding problems and decentralized control. We contribute an algorithm for this setting called GME and show that GME possesses provable guarantees regarding both the return generated from the MDP and the amount of information content communicated, subject to some constraints. On the experimental side, we show that GME significantly outperforms an RL baseline with a perfect receiver. Finally, we show that GME is able to scale to extremely large message spaces and transmit these messages with high fidelity, even with some actuator noise, suggesting that it could be robust in real world settings.

heading: 8 REPRODUCIBILITY
text: Our codebase is included in the supplemental material.

heading: A EXPERIMENTAL DETAILS
text: For CodeGrid, we use a policy parameterized by neural network with two fully-connected layers of hidden dimension 64, each followed by a ReLu activation (Nair & Hinton, 2010). For CodePong and CodeCart, we use a convolutional encoder with three layers of convolutions (number of channels, kernel size, stride) as follows: (32,8,4), (64,4,2), (64,3,1). This is followed by a fully connected layer (Mnih et al., 2015). We use ReLu activations after each layer, note that we do not use any max-pooling. For CodeGrid and CodePong, layer weights are randomly initialized using PyTorch 1.7 (Paszke et al., 2017) defaults. For CodeCart, we initialise weights according to an optimallytrained DQN policy included in rl-baselines3-zoo1 and individually finetune for each β for 15k steps. For all environments, we use the Adam optimizer with learning rate 10−4, β1 = 0.9, β2 = 0.999, = 10−8 and no weight decay.
CodeGrid
CodeCart For CodeCart we use the standard action space (move left and move right). There are no redundant actions that the agent can use to communicate.
CodePong For CodePong we use a reduced action space of size two (move up and move down). There are no redundant actions that the agent can use to communicate.
1https://github.com/DLR-RM/rl-baselines3-zoo

heading: B ALGORITHMIC DETAILS
text: B.1 GME
Algorithm 1 GME // Step 1: Compute MDP policy Input: MDP GMDP, temperature α MaxEnt MDP policy π ← MaxEntRL(GMDP, α)
// Step 2: Play Sender’s Part of MCG episode Input: MDP policy π, MCG GMCG message m← reset(GMCG) // observe message from environment belief b← GMCG.µ state s← GMCG.s0 while sender’s turn do
joint distribution ν ← minimum entropy coupling(b, π(s)) decision rule π|M ← ν(A |M) sender action a ∼ π|M (m) new belief b← posterior update(b, π|M , a) next state s← GMCG.step(a)
end while
// Step 3: Play Receiver’s Part of MCG episode Input: MDP policy π, MCG GMCG MDP trajectory z ← GMCG.receiver observation() belief b← GMCG.µ for s, a ∈ z do
joint distribution ν ← minimum entropy coupling(b, π(s)) decision rule π|M ← ν(A |M) new belief b← posterior update(b, π|M , a)
end for estimated message m̂← arg maxm′b(m′) GMCG.step(m̂)
B.2 FACTORED GME
Algorithm 2 Factored GME // Step 1: Compute MDP policy Input: MDP GMDP, temperature α MaxEnt MDP policy π ← MaxEntRL(GMDP, α)
// Step 2: Play Sender’s Part of MCG episode Input: MDP policy π, MCG GMCG message m← reset(GMCG) // observe message from environment belief b← GMCG.µ state s← GMCG.s0 while sender’s turn do
active block index i← arg maxj {H(bj)|bj ∈ b} joint distribution ν ← minimum entropy coupling(bi, π(s)) decision rule π|M ← ν(A |M) sender action a ∼ π|M (mi) new belief bi ← posterior update(bi, π|M , a) next state s← GMCG.step(a)
end while
// Step 3: Play Receiver’s Part of MCG episode Input: MDP policy π, MCG GMCG MDP trajectory z ← GMCG.receiver observation() belief b← GMCG.µ for s, a ∈ z do
active block index i← arg maxj {H(bj)|bj ∈ b} joint distribution ν ← minimum entropy coupling(bi, π(s)) decision rule π|M ← ν(A |M) new belief b← posterior update(b, π|M , a)
end for for i do
estimated ith message block m̂i ← arg maxm′ibi(m ′ i)
end for GMCG.step(m̂)
B.3 RL+PR BASELINE
Algorithm 3 RL+PR baseline // Play Episode Input: MCG GMCG state s← s0 message m← sample(µ) belief b← µ while True do
action a← sample(π(s,m)) belief b← posterior update(b, π, a) new state s′ ← sample(T (s, a)) if s′ non-terminal then
add to buffer(s, a,R(s, a), s′) state s← s′
else break
end if end while add to buffer(s, a,R(s, a) + ζ maxm′∈M b(m′), ∅)
B.4 MIN ENTROPY JOINT DISTRIBUTION ALGORITHM OUTPUTTING A SPARSE REPRESENTATION OF M CICALESE ET AL. (2019)
Algorithm 4 Min Entropy Joint Distribution Require: prob. distributions p = (p1, . . . , pn) and q = (q1, . . . , qn) Ensure: A Coupling M = [mij ] of p and q in sparse representation L = {(mij , (i, j)) |mij 6= 0}
if p 6= q, let i = max {j|pj 6= qj}; if pi < qi then swap p↔ q. z = (z1, . . . , zn)← p ∧ q, L← ∅ CreatePriorityQueue ( Q(row) ) , qrowsum← 0
CreatePriorityQueue ( Q(col) ) , qcolsum← 0 for i = n downto 1 do z (d) i ← zi, z (r) i ← 0
if qcolsum+ zi > qi then( z (d) i , z (r) i , I, qcolsum ) ← Lemma3-Sparse ( zi, qi,Q(col), qcolsum ) else
while Q(col) 6= ∅ do (m, l)← ExtractMin(Q(col)), qcolsum← qcolsum−m, L← L ∪ {(m, (l, i))}
end while end if if qrowsum+ zi > pi then
(z (d) i , z (r) i , I, qrowsum)← Lemma3-Sparse(zi, pi,Q(row), qrowsum) for each (m, l) ∈ I do L→ L ∪ {(m, (i, l))} if z(r)i > 0 then Insert ( Q(row), (z(r)i , i) ) qrowsum← qrowsum+ z(r)i
else while Q(row) 6= ∅ do
(m, l)← ExtractMin(Q(row)) qrowsum← qrowsum−m L← L ∪ {(m, (i, l))}
end while end if L← L ∪ { (z
(d) i , (i, i)) } end for
Algorithm 5 Lemma3-Sparse Require: real z > 0, x ≥ 0, and priority queueQ s.t. (∑ (m,l)∈Qm )
= qsum and qsum = x ≥ z Ensure: z(d), z(r) ≥ 0, and I ⊆ Q s.t. z(d) + z(r) = z, and z(d) +∑(m,l)∈I m = x I ← ∅, sum← 0 while Q 6= ∅ and sum+Min(Q) < x do
(m, l)← ExtractMin(Q), qsum← qsum−m I ← I ∪ {(m, l)} , z(r) ← z − z(d)
end while z(d) ← x− sum, z(r) ← z − z(d) return ( z(d), z(r), I, qsum )

Review summaries:
The paper suggests a combination of MaxEnt RL with Minimum Entropy Coupling to construct a communication method via (on the fly) modulation of a stochastic policy execution. The core idea being that communication does not require a separate channel beyond the capability of the receiver to observe the sender's (otherwise goal-driven) behaviour. The paper is supported by several experiments, including a study of external interferences with the established behaviour-based communication channel in the form of action execution uncertainty.  

The paper introduces a problem setting, namely Markov Coding Game (MCG): sender receives a state (message) and takes an action to communicate the state to the receiver, receiver observes the taken action, then takes an action to decode the observed state of sender. This game is related to the referential games, source coding as well as decentralized control. To solve the MCG problem, the author designs the greedy minimum entropy coupling algorithm (GME), that aims to maximize the returns of the MDP and learn a good communication protocol simultaneously by combining existing techniques, MaxEnt RL and MEC. The algorithm is test empricially on Gridworld, Cartpole, and Pong. 

The article introduce a new theoretical game called Markov Coding Game (MCG). A Markov Coding game is a special case of Decentralized POMDP (Oliehoek et al. 2016). It seems to be a two-players cooperative game with a sender agent and a receiver agent. Given a message unknown to the receiver, the sender agent must play on a fixed MDP in a way that facilitates the decoding of this message by the receiver. A dedicated algorithm called GME for greedy minimum entropy coupling is proposed to solve this problem. According to the authors, this game is supposed to generalize several referential games and channel coding games. Some experiments are provided where bitmap images are transmitted through actions on gridword and pong environments.