Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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. 

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.

In 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.". 

Unfortunately, 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. 

In 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).

summary_of_the_review: Good core idea and intend, but the paper is incomplete.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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. 
main_review: The problem is nice - to keep the same policy and being able to send a 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. 

1. 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. 
2. 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. 
3. In general systems, the model of MDP may not be known between sender and receiver. How can these issues be handled?
4. Channel coding and source coding are separate problems, and the authors seem to write the two as same in the text. 
5. 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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

main_review: Strength:

1. The paper identifies some interesting connections of MCG with several existing problems.
2. 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,

Weakness:

1. 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.
2. 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.
3. 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).

Questions:

1. 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.
2. 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:
    - Mordatch, Igor, and Pieter Abbeel. "Emergence of grounded compositional language in multi-agent populations." Thirty-second AAAI conference on artificial intelligence. 2018.
    - S. Sukhbaatar, R. Fergus, et al. Learning multiagent communication with backpropagation. In
Advances in Neural Information Processing Systems, pages 2244–2252, 2016.
    - 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.
3. 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.


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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: 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.


main_review: Pro:
- Using MDP policies to code messages is a fun and interesting idea.
- The Decentralized POMDP framework seems a natural formalism for this problem
- 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

Cons:
- 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. 

Questions:
- 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 ?
- If we are facing a two-players game, is it a special case of Markov game as in (Littman 94) ?
- 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 ?


Minor remarks:
p4 "An Markov" -> "A Markov"
p4 "the receiver uses a trajectory conditional policy to guess the message \hat{M} \sim \pi_{|Z}(Z)"  is not a proper formalization.



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.
review_title: null

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