Communicating via Markov Decision Processes
Authors: Samuel Sokota
Christian Schroeder de Witt
Maximilian Igl
Luisa M Zintgraf
Philip Torr
J Zico Kolter
Shimon Whiteson
Jakob Nicolaus Foerster
Venue: ICLR 2022 Submitted (2022)
Keywords: coding
communication
maximum entropy reinforcement learning
minimum entropy coupling

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.

Under review as a conference paper at ICLR 2022
COMMUNICATING VIA MARKOV DECISION PROCESSES
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the problem of communicating exogenous information by means of Markov decision process trajectories. This setting, which we call Markov cod- ing game (MCG), generalizes both source coding and large class of referen- tial games. MCGs also isolate problem that is important in decentralized con- trol settings in which cheap-talk not available- -namely, they require balancing communication with the associated cost of communicating, We contribute a theo- retically 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 able to outperform a relevant base- line 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 commu- nicate binary images via trajectories of Cartpole and Pong, while simultaneously achieving the maximal or near maximal expected returns, and that is even capa- ble of performing well in the presence of actuator noise.
INTRODUCTION
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.
the fourth, the receiver estimates the message from the received trajectory. The shared payoff to the sender and receiver is 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 referential game, a sender attempts to communicate message to a receiver using cheap talk actions-i.e., communicatory actions that do not have exter- nalities the transition interest dating back at least as far as Lewis's ' seminal work Convention (Lewis) 1969). Since then,
reward functions. Referential games have been subject of academic
various flavors of referential games have been studied in game theory (Skyrms 2010), artificial life (Steels 2013), cvolutionary linguistics (Smith 2002). cognitive science (Spike et al. 2017). and machine learning (Lazaridou et al. 2018). MCGs can be viewed 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 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.
be viewed generalization
Yet another reason to be interested in MCGs is that they isolate an important subproblem of decen- tralized control. In particular, achieving good performance in MCG requires the sender's actions

---

Under review as a conference paper at ICLR 2022
to simultaneously perform control in 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 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 union of maximum entropy reinforcement learning (MaxEnt RL) (Ziebart al. 2008) and minimum entropy coupling (MEC) (Kovačević 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 max- imizing 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 the MaxEnt RL policy (thereby guaranteeing the same expected return from the MDP) and the receiver's 's uncertainty about the message is greedily reduced as much as possible.
To demonstrate the efficacy of GME, we present experiments for MCGs based a gridworld, Cartpole, and Pong (Bellemare et al. 2013), which we call CodeGrid, CodeCart, and CodePong, re- spectively. For CodeGrid, we show that with message space in the 10s 100s, GME significantly is able to outperform a relevant baseline. For CodeCart and CodePong, we use a message space of binary images and uniform distribution over messages, meaning that 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.
2 RELATED WORK
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 '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 not directly applicable to MCGs, 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 [wata 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 mapped. The cost of symbol may differ from the cost of other symbols arbitrarily, making it 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 receiver is controlled by a Markov process, which, in contrast to our work, transitions independently of the sender's '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
2

---

Under review as a conference paper at ICLR 2022
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 '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 coop- erative settings with asymmetric information. The baseline for our CodeGrid experiments loosely resembles Strouse et al.Js algorithm. More recently, Bhatt& Buro (202I) 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 not directly applicable to settings in which 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) jtt 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.
3 BACKGROUND AND NOTATION
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 pro- cesses (MDPs). We notate MDPs using tuples (S, R, T) where S is the set of states, A is the set of actions, R: S x A + R is the reward function, and T: S x A + ASS) is the transition function. An agent's ' interactions with MDP are dictated by a policy 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 = (s"; .......&*) 5²). We use the notation R(h) = Σj R(s", (a)) to denote the amount of reward accumulated over the course of a history. When a history is terminal, we use 2 to notate it, rather than h. The objective of MDP is to determine policy arg max E, R(Z) yielding large cumulative reward in expectation.
S + A(A) mapping
Entropy To help us quantify the idea of uncertainty, we introduce entropy. Symbolically, the entropy of a random variable X is H((X) -E log P(X). Because the logarithm function is concave, the entropy of X is maximized when the mass of Px is spread 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 describe the uncertainty regarding which action will be taken by an agent. When a policy spans multiple decision--oints the uncertainty regarding the agent's actions given that the state 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) Y) H(Y) where the joint entropy H(X,Y) -E log P(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,, E., R(S* A') + aH(A'' | [s']], which trades off between maximizing expected return and pursuing trajectories along which its actions have large cumulative conditional entropy, using the temperature hyperparameter a.
3

---

Under review as a conference paper at ICLR 2022
02
.33
J22
J/1
22
3/3
y/1 Py
y/2
y/
y/2 Px.Y
Px
Figure 1: An approximate minimum entropy coupling. Given marginal distributions Px and Py, minimum entropy coupling constructs the a joint distribution Px,y having minimal joint entropy. In other words, it finds joint distribution which allows to encode as much information as possible about X into given marginal distribution Py.
Mutual Information A closely related concept to entropy is mutual information. Mutual informa- tion 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 H(Y))H((Y distribution of the other. Symbolically, mutual information is defined by I(X;Y) information of X) - Y). From this definition, two random variables can be interpreted as the amount of uncertainty about one that is eliminated by observing the realization of the other.
explicitly that the mutual
Mutual information important for communication because we may only be able to share the real- ization 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 con- ditionally independent given Y (that is. X 1 Z Y), the data processing inequality states that I(X; Y) 2 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 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 determin- ing 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 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 equivalent to that minimizing the joint entropy of X and Y. As result, this problem often referred to the minimum entropy coupling problem. A visual example is shown in Figure D While minimum entropy coupling is NP-hard Kovačević et al. (2015), Cicalese al. (209)) recently showed that there exists polynomial time algorithm that is suboptimal by no more than one bit.
4 MARKOV CODING GAMES
We ready to introduce Markov coding games (MCGs). An MCG is tuple ((S, T, M, μ. Ç)2 where (S, A, R) is a Markov decision process, M is a set of messages, is distribution over M, and is non-negative real number. An Markov coding game proceeds in the following steps:
1. First, message M a sampled from the prior over messages and revealed the sender.
2. Second, the sender uses a message conditional policy to generate a trajectory Z ~ (T, MMM) Third, the sender's terminal trajectory Z is given to the receiver as an observation.
Fourth, the receiver uses trajectory conditional policy to estimate the message M ~ म (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 = MM] Optionally, cases in which a reasonable distance function is available, allow for the objective be modified to minimizing the distance
4

---

Under review as a conference paper at ICLR 2022
between the message and the guess ((M,MM, rather than maximizing the probability that the guess correct.
A
M
Z
M
Sender
MDP
Receiver
R, S
A depiction the structure of MCGs. First, the sender given a message. Second, the sender is tasked with MDP, unrelated to the message. Third, the receiver observes the sender's trajectory. Fourth, the receiver estimates the message.
Figure 2:
4.1 AN EXAMPLE
payoff matrix for a simple MCG shown in Figure In this game, the sender is given of two messages m or m', with equal probabil- ity. It then chooses among three actions d1, of and o", 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 i and m corre- sponding to guessing to and m', respectively. The receiver accrues reward of 4 for guess- ing correctly. The payoff entries table denote (R(2), <I[M = M]) for each outcome.
Figure 3: A payoff matrix for simple MCG.
Receiver
Message
Sender
m
m
a1
(4, (
(4, 0)
(3,
(3, 0)
"
(0, O
(0, 0)
a
(4, 0)
(4,
m'
a]
(3, 0)
(3, (39
a²
(0, 0)
(0.
As is generally true of MCGs, this MCG is difficult for independent approximate dynamic programming- based approaches because their learning dynamics are subject local optima. Con- sider in which the sender first learns 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 not communicating any information about the message. As result, thereafter, the sender has no incentive to communicate any information in its message, because the receiver would ignore anyways. This outcome, sometimes called babbling equilibrium, leads to a total expected return of 4 + 2/2 (sender always selects 01, receiver guesses randomly). In cases in which Ç is small (communication unimportant), the babbling equilibrium performs well. However, it can perform arbitrarily poorly as becomes large.
4.2 SPECIAL CASES
We can express both (a large class of) referential games and various source coding settings special cases 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 = {so s!......"))
The transition function deterministically maps of + ++1 and terminates at input sf.
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 À (0).
The transition function deterministically maps to to s for a E Á and terminates the game on
The reward function maps to 1 for a E and maps to
Length Limited Source Coding Length limited source coding can be captured in the same way as standard source coding with the modifications that S = {sa, s' .!...., s s"', }. the transition function terminates S and the reward function yields from s where 7' is the length limit.
5

---

Under review as a conference paper at ICLR 2022
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 E A.
GREEDY MINIMUM ENTROPY COUPLING
To address MCGs, we propose a novel algorithm call greedy minimum entropy coupling (GME). GME (and more broadly, any algorithm geared toward MCGs) is faced with two competing incen- tives. On one hand, needs maximize expected reward R(Z) generated by the MDP. On the other hand, it needs to maximize the amount of information I(M; 2) communicated to the receiver about the message, so to maximize the probability of correct guess. GME handles this trade-off using a two step process for constructing the sender's i policy. In the first step, it computes an MDP policy that balances between high cumulative reward and large cumulative entropy. the second step, couples the probability mass of this policy with the posterior over messages in such 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.
5.1 METHOD DESCRIPTION
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 the choice of temperature used for the MaxEnt RL. algorithm.
Step Two the second step, at execution time, GME constructs a cessage-conditiona policy on- line. Say that, up time the sender is in state s², history h' and has played according to the message conditional policy "[M. Let
8' = P(M W m(())
be the posterior over the message, conditioned on the history and the historical policy. GME per- forms a MEC between the posterior over the message D' and distribution over actions T(*') ())) as determined the MDP policy. Let MEC(b 7 (s()) denote joint distribution messages and actions resulting from the coupling. Then GME sets the sender to act according to the message conditional distribution
(sA((", = v(A' M= m))
of the coupling distribution MEC MEC(b",=(s')),
Given the sender's MDP trajectory, GME's receiver uses the the sender's MDP policy and MEC procedure to reconstruct the sender's 's message conditional policy along the trajectory, thereafter, the receiver computes the posterior and guesses the maximum a posteriori message.
Pscuodocode for GME is included in the appendix.
5.2 METHOD ANALYSIS
GME possesses guarantees both concerning the return R(Z) generated by the MDP and concerning the amount of information communicated [(M; Z). Proposition 1. At each state of the MDP, the message conditional policy T/M selects actions with the same probabilities as the MDP policy x.
Proof. Fix arbitrary state Let b be 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(),.(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. is equal to that of the MaxEnt policy т. That is,
The expected return generated from the MDP by the message conditional policy M|M
EM Ex R(Z) E RZ))

---

Under review as a conference paper at ICLR 2022
69
MDP payoff
RL+PR
128
Prediction accuracy
Figure 4: Results for GME and RL+PR on CodeGrid with varying message space sizes.
Proof. It follows from Proposition I that all trajectories 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; H bt, h²) between the message M the history the next time step H given the contemporaneous posterior and history, subject to Proposition
Proof. For conciseness, we leave the conditional dependence on D and ht implicit in the argu- ment. First, we claim that [MM; ( = I(M;A')
see this, first consider that H I(M; (A', s(+ since are conditioning
(h', A', St, This means we have I(M; (LM:H++1 on h². Now, consider that because the message influences the next state only by means of the action, have the causal graph M + A + (A*, St++,,, which implies that M 1 (*+,1 A Also, we trivially have M 1 A' (A', 5t+1). These conditional independence properties allow us to apply the data processing inequality: X 1 Y I(X;Y) I(X; Applying it in both directions yields I(M; (A', S(+1)) = I(M; A').
Now consider that rewrite mutual information using the equality
I(M; A+) 7((M) + H(A') H(M, At).
The first term H(M) exogenous by virtue of being determined by 6*, The second term is exoge- nous by virtue of being subject to Proposition The third term is the joint entropy between M and A which is exactly what a minimum entropy coupling minimizes.
5.3 МETHOP DISCUSSION
One aspect of GME that went uncommented upon in the analysis section the choice of MaxEnt RL for step one. The reason that GME uses MaxEnt RL here is to control the H(A') term in equation [T.. the temperature a large, GME places more emphasis on maximizing H(AA) (and thereby [M: Z)); if the temperature is small, GME places appropriate choice of a will depend on the value of Ç. Code for GME that illustrates the functionality of applied the example from Figure can be found at https: / /tttt 1y/36Ta 3..m
emphasis
maximizing R (Z). The
second aspect of GME that we have yet to discuss its scalability. Performing an approxi- mate MEC takes (N log N) time, making it expensive to scale very large message spaces. To accommodate this fact, for large message spaces we recommend using factored representation Mr and corresponding factored belief (bi,..., bx), where each by tracks the
MI C M, posterior over M,. At each time step, we suggest performing a MEC between ((s") and the block b, arg max, H(bb) having the largest entropy. By doing so, we can substantially reduce the size the of the space over which we need to perform minimum entropy coupling at any one time, allowing us to scale to extremely large message spaces.
EXPERIMENTS
We investigate the efficacy of GME MCGs based gridworld, Cartpole and Pong. For all three we use MaxEnt Q-learnig for our MDP policy. Details regarding our implementation can be found in the supplementary material and in the appendix.

---

Under review as a conference paper at ICLR 2022
log A -10.0
log f +1,0
log 0 A1
log m 1.0
acoustor natse 2 0.00
pleel entrr
01:93
1:1:2
5004 Go
5200 2.3
0000011
cd
Scquater noise
pocel -CoE occustor noise (p- 0.1
2000
200
pool entor
25
(p
peel score
aсCEEBI noise
poeli etrer Score
201 22
1224 25
22
Y552 46.2
2AM4 1MM4
Figure 5: Results for GME on CodeCart with varying amounts of actuator noise and temperatures. CodeGrid In our gridworld MCG, which we call CodeGrid, the sender is placed on 4 4 grid in which it can move left, right, up and down. The sender starts at position (1. 1) and must to move to (4, 4) within 8 time steps to achieve the maximal MDP return of 1. Otherwise, the game terminates after 8 time steps and the sender receives a payoff of O.
For our baseline, we trained an RL agent 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 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 r-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 a, while RL+PR can adjust the value of ( used during training. Figure the Pareto curve for each. For GME, the size of the circle corresponds to the inverse temperature / = 1/a.
For the settings with 8 messages and 32 messages, we observe that both GME and RL+PR achieve strong performance- aaciieinchiiiigggeee optimal or nearly optimal MDP returns and optimal or nearly opti- mal 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 correctly transmit the message slightly more than half the time. RL+PR's 's inability to achieve strong performance in these cases may be a result of the fact that communication protocols violate the locality assumption of ap- proximate 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 x 16 and 22 22 binary images, respectively, each with a uniform prior. The cardinality of these spaces (> 10TT and > 10245) is astronomical. In fact, it is not clear how an RL+PR-lik- 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 random action, rather than the one it intended. Actuator noise models the probability of error during transmission and arises naturally in many settings involving communica- tion, such as noisy channel coding. In this setting, the receiver may only observe the action executed
8

---

Under review as a conference paper at ICLR 2022
log 1.0
log -
log F
log - 5.0
log p
log f 7.0
achuasor nosse Ip - 0.0)
pixel entor scone
00002
02:250
00
1177 FB
+10
21:000
21000:
actuator noise 0.05)
picel enrer
60 x.
50:400
00 20
x 10
15:87
2.3
[23 211
120
67 115
achuaor nosen
Ip - 0.1)
score
122:14
actuator
picel eneor
score
1 17
R2. 22
160
adtastor noise (p - 0.5)
picel error
18235
1000 ABA
267
2:54 22
23
Figure 6: Results for GME on CodePong with varying amounts of actuator noise and temperatures.
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 3 = 1/ax (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 ε pixel error (blue) and the MDP expected return (green), along with corresponding standard errors over 10 runs; a brighter color corresponds 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 8 E [-10,- -,, 0.1}; for CodePong, it occurs at log e 54,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 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 3 = -1) is difficult to even perceive, while the CodePong sender still manages to win games roughly 80% of the time (log B = 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.
CONCLUSIONS
This work introduces a new problem setting called Markov coding games, which generalize referen- tial 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 con- tent communicated, subject to some constraints. On the experimental side, we show that GME significantly outperforms an RL baseline with a perfect receiver. Finally, 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.

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY
Our codebase is included in the supplemental material.
REFERENCES
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, Jun 2013. ISSN 1076-9757. doi: 10.1613/jair.912.. URL http: dtt. 10. jair. 3912
Varun Bhatt and Michael Buro. Inference-based deterministic messaging for multi-agent communi- cation. Proceedings of the AAAI Conference on Artificial Intelligence, 1282 May 2021. htttps///o/1s
Cicalese, L. Gargano, and U. Vaccaro. Minimum-enttropy couplings and their applications. IEEE Transactions on Information Theory, 65(6):3436-3455) 2019. doi: 10.1109/1IT.2019228444
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity all you need: Learning skills without a reward function. International Conference on Learning Representa- tions, 2019. URL
net Sox
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, pp. 2137 Curran Associates, Inc., 2016. URL https::/ppocceddinn neurips.
Mordecai J. Golin, Claire Kenyon, and Neal E. Young. Huffmann coding with unequal letter costs. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC '02, pp. 785-791, New York, NY, USA, 2002. Association for Computing Machinery. ISBN 1581 13995,, doi: 10. 0111444999775100000 510020
Kenichi Iwata, Masakatu Morii, and Tomohiko Uyematsu. An efficient universal coding algorithm for noiseless channel with symbols of unequal cost. JEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 80:2232-2237. 1997.
Mladen Kovačević, Ivan Stanojevié, and Vojin Šenk. On the entropy of couplings. Informa- tion and Computation, 242:369-382, 2015. ISSN 0890-5401. doi: https///doiorrg/10.000 ic.2005.04.003. URL https: htttpp::/wwww.oo www.eeecieeeirereeccoomm http://ceeeecccccooccccceeeeeaaa
S08 008905401110 15000450
Lawrence L. Larmore and Daniel S. Hirschberg. Length-limited coding. In Proceedings of the First Annual ACM-SIAM Symposium Discrete Algorithms, SODA '90, pp. 310-318, USA, 1990. Society for Industrial and Applied Mathematics. ISBN 0898712513. 12513.
B. P. Lathi, Modern Digital and Analog Communication Systems 3e Osece. Oxford University Press, Inc., USA, 3rd edition, 1998. ISBN 01951
Angeliki Lazaridou, Karl Moritz Hermann, Karl Tuyls, and Stephen Clark. Emergence of linguistic communication from referential games with symbolic and pixel input. In International Confer- ence on Learning Representations, 2018. URL
net forum?id ?
HJGv
David K. Lewis. Convention: A Philosophical Study. Wiley-Blackwell, 1969.
David J. C. MacKay. Information Theory, Inference Learning Algorithms. Cambridge University Press, USA, 2002. ISBN 0521642981.
10

---

Under review as a conference paper at ICLR 2022
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioamnis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518((540))522 533, February 2015. ISSN 1476-4687. doi: 10.1038/nature 4236.. URL https: http::/wwwwnette natuuatureee.... http:///oo/o.rr.oeeeeettttteeeee
Number: 7540 Publisher: Na-
ture Publishing Group.
Vinod Nair and Geoffrey F. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th International Conference on International Conference on Machine Learning. ICML' 10, pp. 807-814, Madison, WI, USA, June 2010. Omnipress. ISBN 978-1- 60558-907-7.
Frans A Oliehoek, Christopher Amato, al. A concise introduction decentralized POMDPs, volume 1. Springer, 2016.
Adam Paszke, S. Gross, Soumith Chintala, G. Chanan, E. Yang, Zachary Devito, Zeming Lin, Alban Desmaison, L. Antiga, and Lerer, Automatic differentiation in PyTorch, 2017.
Brian Skyrms. Signals: Evolution, Learning, and Information. Oxford University Press, 2010.
Kenny Smith. The cultural evolution of communication population neural networks. Con- nection Science, 14:65 84, 2002.
Matthew Spike, Kevin Stadler, Simon Kirby, and Kenny Smith. Minimal requirements for the gence of learned signaling. Cogmitive Science, 41(3))623-658, 2017. doi: https://oi..org/10 (L1l/cogs.12351 URL http::://cmineeiirrree htwpiiibrrrr.wlleyy.......eeeeee wwwww. com/ http///i/abbbb/eee cogs 12351
Luc Steels. Self-organization and selection in cultural language evolution. 03 2013. doi: 10.10751 3is.3.02ste.
DJ Strouse, Max Kleiman- Weiner, Josh Tenenbaum, Matt Botvinick, and David Schwab. Learning to share and hide intentions using information regularization. In Proceedings of the 32nd Interna- tional Conference on Neural Information Processing Systems, NIPS'18, 18, pp. 10270-10281, Red Hook, NY, USA, 2018. Curran Associates Inc.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. Bradford Book, Cambridge, MA, USA, 2018. ISBN 978-0-262-03922-6
Hong Shen Wang and N. Moayeri. Finite-state markov channel-a useful model for radio com- munication channels. IEEE Transactions on Vehicular Technology, 1111) 1995. doi:
10.1109/25.30022..
Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd national conference on Artificial intelligence Volume 3, AAAI'08, pp. 1433-144 1438, Chicago, Illinois, July 2008. AAAI Press. ISBN 978-1- 57735-368-3.

---

Under review as a conference paper at ICLR 2022
A EXPERIMENTAL DETAILS
For CodeGrid, we use policy parameterized by neural network with two fully-connected layers of hidden dimension 64, each followed by ReLu activation (Nair & Hinton 2010). For CodePong and CodeCart, we use convolutional encoder with three layers of convolutions (number of channels, kernel size, stride) follows: (32,8.4), (64,4,2), (64,3,1). This is followed by 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 randomly initialized using PyTorch 1.7 (Paszke et al. 2017) defaults. For CodeCart, we initialise weights according to an optimally- trained DQN policy included rl-baselines3- zod and individually finetune for each for 15k steps. For all environments, we use the Adam optimizer with learning rate 10 10-4, 31 0.9, B2 0.999, = 10-8 and no weight decay.
CodeGrid
GOAL
GOAL
START
START
Figure 7: An illustration two possible CodeGrid trajectories, one length 6 (left) and one of length 8 (right).
CodeCart For CodeCart we use the standard action space (move left and move right). There no redundant actions that the agent can use to communicate.
reduced action space of size (move up and move down). There are no redundant actions that the agent can use to communicate.
CodePong For CodePong
inea3 zoo
12

---

Under review as a conference paper at ICLR 2022
B ALGORITHMIC DETAILS
B. GME
Algorithm GME
Compute MDP policy Input: MDP GMDP. temperature & MaxEnt MDP policy <- MaxEndRL(GMiDe..d a)
// Step 1:
Step 2:
Play Sender's Part of MCG episode
Input: MDP policy æ. MCG GMOG
message m reset(GMcG)) // observe message from environment
belief + GMCG-44
state G
while sender's turn do
joint distribution v minimum entropy coupling(b, π (s))
decision rule TM < v(A M)
sender action ~ au (m)
new belief b < sureriooruudate((( M)a,a) a)
next state s f- GMco.step(a) end while
// Step 3: Play Receiver's Part of MCG episode Input: MDP policy म. MCG GMOG MDP trajectory belief &- GMCG-44
for s, a E 2 do
joint distribution e minimum entropy coupling(b, π (s)) decision rule TIM + v(A M)
new belief b < posterior end for
up, (osterior.update(0 a)
estimated message in +- arg max bmm") (MC
13

---

Under review as a conference paper at ICLR 2022
B.2
FACTORED GME
Algorithm 2 Factored GME
Step 1: Compute MDP policy
Input: MDP MMP., temperature
MaxEnt MDP policy <- MaxEmtRL.(GMDe- a))
Step 2:
Play Sender's Part of MCG episode
Input: MDP policy MCG GMGG
message m t- reset(GMcud // observe message from environment
belief b f GMCG-H4
state s + GMic.s"
while sender's turn do active block index i +- arg max, (H(b,)1b, b
joint distribution y
htwp:uuueeettoocooupuue (s))
decision rule MM < v(A M)
sender action ~ मI aur (mz))
new belief b, - posterior.updateee sudaatebddaaat.aaaaaaee TIM, a)
next state f- GMco.step(a) end while
// Step 3: Play Receiver's Part of MCG episode Input: MDP policy æ. MCG GOO MDP trajectory belief f- GMCG-/4
receveee observation()
for 8, E do
active block index i + arg max, (H(b,)]6, E 6} joint distribution decision rule as + v(A M)
minimum wattmmmettttyyyooee couplinggl,, क (s))
new belief b < cesteriorr_pdateff a)
end for for i do
estimated ith message block m, arg max,; (m(,)
end for
Gmco-step(rn)
B.3 RL+PR BASELINE
Algorithm 3 RL+PR baseline
Play Episode
Input: MCG GMCG
state 8 S
message m <- sample(μ)
belief + μ
while True do
action f sample(r(s, m))
belief b + posterior.updatee (b ı, a)
new state s' + sample a))
if s' non-terminal then add_to add_to_butt wtw.ttoobffferr_e__er (8,
state 5
else
break
end if
end while
add to buffer(ss, a, R(s,, a) + maxm'eM b(m'), 0)
14

---

Under review as a conference paper at ICLR 2022
B.4 MIN ENTROPY JOINT DISTRIBUTION ALGORITHM OUTPUTTING SPARSE REPRESENTATION OF M CICALESE ET AL. (2019)
Algorithm Min Entropy Joint Distribution
Require: prob. distributions p (. Pn)) and q (4), (2),-....h qn)
Ensure: A Coupling M [may] of p and q in sparse representation L = {(maj, (1,j)) Imgs # 0)
if / q. let i max Lipp + g p, < then swap +>
(B...... 2n - P q. L
CreatePriorityuueuc ((raw)
growsum 0
CreatePriorityyueeee ((col))
qcolsum t 0
for downto do
(r)
f Zi, 22 + 0
if qcolsum + > qi then
(r) I, qcolsum)
+ Lemma3-Spars. (zi, Q(cal), geolsum)
else
while ((cal) + 0 do (m, I) + ExtractMin(QQcca)) gcolsum gcolsum
+ LU { (1, ())
end while end if
if growsum + 24 P: then
(c) z growssu)) + Leemmm-mmaapp Seemma3-Spars(2z.222 Ps: Q(row), growsum)
for each (m, 1) I -
LU {m, (i,
if (r) 0 then Insert (((ow)), (e
growsum < growsum
else
while (rrww) + 0 do
(m, + ExtractMin( @(row))
growsum < growsum m L [L (i,
end while end if
L + LU LU ((.%%.11)))) end for
Algorithm LLemma--Spprs
Require: real 0, x 2 and priority queue s.t. Σ (m. m
qsum and gsum
Ensure: 2(4), ()) 2 0, and C Q s.t. (d)) + 2(r) = 2, and 2(d) + Σ E(m.)er m = x ++00 0. sum + 0
while Q + and sum + Min Q) < x do
(m, 1) +- ExtractMin Q), qsum +- qsumn
I + TTTTTmmmm ((m,1))) ((r) + (d)
end while
(d) +- -- suum, 2(1) -- (d))
return (z14), z(r), I, q.quu))
15


Reviews:
[{"review_id": "y5vY0XoetKU", "reviewer": "Reviewer_FcQX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n1. The paper identifies some interesting connections of MCG with several existing problems.\n2. The paper conducted extensive empirical evaluation of its model. The results look good and are presented with carefully-designed figures and videos. The performance comparison with RL+PR baseline is also interesting,\n\nWeakness:\n\n1. I am sorry to say the paper does not have sufficient novelty in both its proposed problem setting and the learning algorithm. First, I think the described problem setting, at least something very similar, already exists (see the reference below). The only difference might be that they do not explicitly evaluate on how accurate the message is decoded. But I am not sure why it is necessary to explicitly evaluate this objective, if we could design a game where good communication is necessary to achieve optimality. I hope the author can provide more motivation on the design of this problem setting. Second, technical contribution is limited, as the proposed GME algorithm seems to be a straightforward combination of existing methods, MaxEnt RL and MEC.\n2. I am not sure why the authors describe their proposed method as \"theoretically grounded\", as I see no theoretical guarantee about its proposed method in this paper from the three Propositions in practice. I think it might be possible to combine proof techniques in information signaling scheme design (e.g., persuasiveness constraint) to improve the theoretical results.\n3. In the empirical evaluation, the results look good, but I wish to see more baselines for comparisons. However, some more thorough tests are possible to help us understand the strength of the proposed method (e.g., See question 3 below).\n\nQuestions:\n\n1. I wonder why the authors describe their problem setting as \"the receiver observes the sender’s MDP trajectory\", but from the examples, it actually just observes the sender's taken action. Is it just a fancy word, or the author is actually considering something more general about the receiver's observation.\n2. I wonder how the proposed problem is the related to a series of literature in learning multiagent communication, and can their method serves as the additional baseline of this paper:\n    - Mordatch, Igor, and Pieter Abbeel. \"Emergence of grounded compositional language in multi-agent populations.\" Thirty-second AAAI conference on artificial intelligence. 2018.\n    - S. Sukhbaatar, R. Fergus, et al. Learning multiagent communication with backpropagation. In\nAdvances in Neural Information Processing Systems, pages 2244–2252, 2016.\n    - Lowe, Ryan, et al. \"Multi-agent actor-critic for mixed cooperative-competitive environments.\" Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017.\n3. I notice that the games in the experiment do not include the additional dummy action available for communication, so the agent has to take the action that not only serves as to achieve value but also to achieve good communication with the receiver. I wonder what happens if the game includes the redundant action that the agent can use to communicate.\n\n", "summary_of_the_paper": "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.\n", "summary_of_the_review": "While the paper demonstrates some nice empirical results, my major concern is its lack of novelty in the proposed problem setting and the learning algorithm. Therefore, I think additional studies are needed in order to  improve the technical and empirical contribution of the work.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "qQ_e-DJe4E", "reviewer": "Reviewer_8Cj5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pro:\n- Using MDP policies to code messages is a fun and interesting idea.\n- The Decentralized POMDP framework seems a natural formalism for this problem\n- Introducing a stylized theoretical game to formalize a difficult point in a more complex problem (like for instance multi-armed bandits for exploration/exploitation in RL) can provide valuable insights\n\nCons:\n- The key point when introducing new theoretical games is to give a clear, abstract view of a problem. But I found the formalization of this MCG problem too muddled. To start with, it is not clear to me if we are really facing a two-players game or a single-player (the sender) game because the way the receiver \"guesses\" the message is not clearly formalized in the paper. \n\nQuestions:\n- Assuming the game is a single-player game, is it reducible to an equivalent \"transformed\" MDP/POMDP where original MDP reward is shaped to reflect the additional \"easy-to-guess\" reward ?\n- If we are facing a two-players game, is it a special case of Markov game as in (Littman 94) ?\n- Is the proposed GME algorithm able to solve a special case of MCG, as for instance a channel coding problem as efficiently as an ad-hoc algorithm would ?\n\n\nMinor remarks:\np4 \"An Markov\" -> \"A Markov\"\np4 \"the receiver uses a trajectory conditional policy to guess the message \\hat{M} \\sim \\pi_{|Z}(Z)\"  is not a proper formalization.\n\n\n", "summary_of_the_paper": "The article introduce a new theoretical game called Markov Coding Game (MCG).\nA 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.\nA dedicated algorithm called GME for greedy minimum entropy coupling is proposed to solve this problem.\nAccording to the authors, this game is supposed to generalize several referential games and channel coding games.\nSome experiments are provided where bitmap images are transmitted through actions on gridword and pong environments.\n\n", "summary_of_the_review": "A new theoretical game called Markov Coding Game and an algorithm to solve it. But I found the formalization the problem too muddled.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "er9o7CteU0i", "reviewer": "Reviewer_o2vx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very clearly written right until the actual method is described. At that point key details vanish and the approach remains half-presented with some ostensible gaps on the receiver side.\n\nIn particular, authors take a relatively good care of preparing and presenting the sender's behaviour generation side. From ensuring that the natural policy contains sufficient stochasticity to piggyback a message to some (though fairly naive) theoretical guarantees for the correctness on the sender's side. This reviewer has little argument against that portion. However, the paper completely misses the explanation of \\pi_{Z} -- the receiver's decoding policy. The only line about it reads \"... the receiver guesses the maximum a posteriori message.\". \n\nUnfortunately, posterior calculation, as presented previously in Step 2 belief formulation, depends on the knowledge of the Sender's policy throughout execution. As it is greedily constructed, it seems strange that the receiver would be aware of it to any reasonable extent. This makes the posterior calculation impossible on the receiver's side. One could argue that these are calculated in some form of an equilibrium pattern, but that is not the authors intent or explanation either. So, either there is a secondary communication channel that allows the policy information to be accessible to the receiver -- which contradicts the assumption of communicating by behaviour only -- or there's one half of the approach that authors neglected to present -- which is even more unfortunate. \n\nIn addition, authors tend to miss quite a bit of related work. From technological issues (e.g., combinations of RL with information bottlenecks) to ideological \"brothers\" (e.g., boosting goal recognition in RL solutions and its countermeasures, such as deceptive RL).\n", "summary_of_the_paper": "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. \n", "summary_of_the_review": "Good core idea and intend, but the paper is incomplete.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "a1Rt6wZDcEb", "reviewer": "Reviewer_Er8e", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem is nice - to keep the same policy and being able to send a message. ", "summary_of_the_paper": "This paper aims to send a message through an MDP. The key is that the policy should still be optimal in the sense of the distribution of actions in each state, while communicating the message. ", "summary_of_the_review": "There are multiple issues in the paper, due to which the reviewer feels that the paper is not ready in its current form. \n\n1. How much message entropy can be communicated? In source coding, we have the entropy of message that is communicated through a certain message length. Similarly, when communicating through a MDP, it is important to know message length communicated for a given finite T length MDP. \n2. Since the optimal policy is deterministic, for a given state, there is a unique optimal action, it is unclear how the policy can be the same and still contain the message. This is because deterministic action has no entropy. It seems that the authors are assuming that even if message is sent o(T) of the time, policy will be the same - and thus o(T) times, actions can be chosen - so \\tilde{O}(T\\log |A| ) length message can be communicated without any change in average policy. Not sure, if the authors are able to get better - and how to quantitatively say that. \n3. In general systems, the model of MDP may not be known between sender and receiver. How can these issues be handled?\n4. Channel coding and source coding are separate problems, and the authors seem to write the two as same in the text. \n5. Two of the special cases are given. How does the results here give same/improved communication results in the two domains. The result of message communications need to be at least the same as in those areas, with results in the general setup. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes Markov coding game (MCG), which generalizes both source coding and a large class of referential games. All the reviews are negative. The reviewers think the work is not ready for publication in its current form.
Decision: Reject