Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: The paper proposes a hierarchical multi-agent reinforcement learning method for the restricted communication setting and verifies the algorithm performance in a number of useful applications. The hierarchical approach to the networked MARL problem proves novel, effective, and interesting.

+ Strengths:

+ The work targets an arguably less explored area by focusing on the restrictions on inter-agent communication that may be present in realistic scenarios.

+ Evaluation setup is varied, explained in detail and visualized in an intuitive manner.

+ Niche is well-identified, and the contribution is clear.


- Major Concerns:

- The reviewer had issues positioning the paper among the different lines of research. Although the research gap itself is clear (scalable MARL methods in a restricted communication setting), it isn't obvious why and how relevant the cited works are. For example, mentioning VDN, QMIX, and QTRAN (which together are some of the latest works in the factorization methods) does not seem to serve any further purpose, as they are no longer compared quantitatively or qualitatively to LToS. The authors' claim that they are not scalable leads the reviewer to anticipate that LToS naturally is scalable, but there appears to be no evidence whatsoever presented in the latter sections of the paper to show, let alone prove, the superior scalability of LToS, with, for example, growing numbers of agents and training times.

-  Furthermore, some of the cited works have been left out at the evaluation stage, which leaves the reviewer puzzled as to which baselines LToS really hopes to outshine. The work needs some justification over why the following studies have not been compared to in the evaluation:

If the main strength of LToS lies in its capability to function effectively and efficiently in restricted communications setting, comparison to one or more of the following works should be of great advantage in illustrating that edge:
DIAL/RIAL by  Foerster 2016 - Learning to Communicate with Deep Multi-Agent Reinforcement Learning
BiCNet by Peng 2017 arXiv - Multiagent Bidirectionally-Coordinated Nets
CommNet by Sukhbaatar 2016 NeurIPS - Learning Multiagent Communication with Backpropagation
IC3Net by Singh 2019 ICLR - Learning When to Communicate at Scale in Multiagent Cooperative and Competitive Tasks
SchedNet by Kim 2019 ICLR - Learning to Schedule Communication in Multi-agent Reinforcement Learning

If the main strength of LToS lies in its capability to resolve selfishness and assign credits appropriately to bring about a harmonious cooperation in social dilemmas, analysis with respect to the this work should be helpful:
Eccles 2019 CoRR - Learning Reciprocity in Complex Sequential Social Dilemmas

It would be interesting to draw some parallels between LToS and BAD, as both draw inspiration from a hierarchical decomposition:
BAD by Foerster 2019 ICML - Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning

This recent AAMAS paper is based on peer evaluation and exchanging evaluation messages computed from recently obtained rewards:
PED-DQN by Hostallero 2020 AAMAS - Inducing Cooperation through Reward Reshaping based on Peer Evaluations in Deep Multi-Agent Reinforcement Learning
Some of the potential issues to discuss are: bandwidth usage of message exchange, message overhead in sharing the neighbors' rewards.

Using neighbors' information to achieve scalability in MARL most likely requires discussion of mean-field methods, such as:
Yang 2018 ICML - Mean Field Multi-Agent Reinforcement Learning.

- Going through the Appendices spurred a great deal of curiosity, as the authors mention that all agents share the same, synchronized random number generator with the same seed across all the agents. This leads me to believe that the philosophy of decentralized learning is lost in LToS. Synchronization is definitely not cost-free; all the more so if the synchronized RNG is used to sample an experience from the agents' replay buffers. How do the agents synchronize their RNG in a decentralized manner?

- In the Routing evaluation. has overhead been taken into account? How does LToS fare with respect to varied communications channel? What if the network were sparser? Do you observe any trends as you vary the extent of network connectivity?
review_title: On Positioning and Evaluation

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper present a new method, called LToS which enables agents to share rewards in MARL. Two levels of policies, high-level and low-level, determines rewards and optimize global objectives. Three diverse scenarios were used to test the performance of LToS compared to other baseline methods. LToS consistently outperforms other methods. In the second scenario, authors also show the need for high-level policy by introduction fixed LToS. 

- At the end of Introduction, the sentence ‘LToS is easy to implement and currently realized by DDPG…’ can be misleading because of the word ‘realized’ and the fact that authors argue that LToS is a newly proposed method. Does this mean LToS simply combines DDPG and DGN?
- Do Figure 5 and 6 represent selfishness of agents when LToS is used?
- Minor editorial errors in Appendix
review_title: Learning to Share in Multi-Agent Reinforcement Learning

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary
The paper considers the cooperative MARL setting where agents get local rewards and they are interconnected as a graph where neighbors can communicate. The paper specifically considers the communication of reward sharing, that is, an agent shares (part of) its reward to its neighbors, such that each agent optimizes its local reward plus rewards from its neighbors. This motivates a bi-level optimization framework where the high-level policy decides how the rewards are shared and the low-level policy locally optimizes the shared rewards given the high-level’s decision. The paper’s flow motivates such a framework well. The experimental results demonstrate the method’s effectiveness. I think it is a strong paper (accept), but my confidence is low due to the following confusions I have.
 
Comments/Questions
 
1. I have a high-level comment on the reward sharing mechanism. It seems that the proposed method does not support multi-hop sharing because rewards can only be shared to neighbors. Why is this single-hop sharing effective in the experiments? Is it because of domain-specific reasons, or it’s because that single-hop sharing is in principle equally effective, why?

2. The derivation of (18) using taylor expansion is unclear to me. Could the authors explain it with more details?

3. I don’t fully understand the proof of Proposition 4.2. Specifically, does “phi can be learned in a decentralized manner” mean that the *optimal* phi can be based on only the local observation for each agent, instead of based on global state? Could the authors comment on the approximation error induced by the mean-field approximation? Why the proof begins with phi_i based on o_i and ends with phi_i based on global state s.

4. In Equation (17) and (20), should phi^* be just phi (i.e. no * here)?

5. The low-level policy is to optimize the shared rewards. My understanding is that any (single-agent) RL algorithm can be used for optimizing the shared rewards, e.g. DQN, DDPG, A2C, etc. Why would the authors choose DGN, a rather less popular RL algorithm? Have the authors tried more popular algorithms as the low-level policy?

6. For fixed LToS,  how do we determine the fixed sharing weights?

---
Thanks for the response. I've increased my confidence. 
review_title: An interesting paper on learning to share rewards

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper addresses multi-agent RL problems by presenting a decentralized approach where the agents learn to share their reward with their neighbors. In this method, a high-level policy determines a weight vector for weighting the reward of neighboring agents, and then each agent learns their own independent policy. The learning is thus conducted locally in a partially connected network toward a common goal and without the knowledge of global state and actions.

Overall, the approach is intuitive and interesting for decentralized learning in MARL tasks. However, I have some comments/questions for improving the paper that are summarized below.  Hence, I vote to reject at this stage.

Pros:
+ Intuitive design of communication among agents in decentralized setting
+ Clever adaption of algorithms
+ Well written paper and properly organized

Comments:
- The contribution of the paper is mainly in formulating the problem in the actor-critic setup of DDPG method which leads to a limited novelty.

- A key concern about the paper is how to decompose the reward in the first place. The paper aims at optimizing a global objective and assumes (also in the propositions) that this objective has additive connection with the decentralized rewards. Nevertheless, this is a strong assumption, particularly in real-world applications. A global reward can be decomposed into summation of smaller rewards, but not necessarily the other way around. As long as there is a global objective, we need a way to distribute the reward among the agents via learning or reward reshaping (or even manually). How can we properly define the reward of each agent in such scenarios?

- It is also unclear what is the benefit of sharing only with the neighbors. The method learns a weight vector of size |N_i| for every agent. Does it make a difference in the architecture/algorithm if we learn the weights of all the other agents (size |N|) instead?

- Formulating the weights as finite discrete values looks unnatural. If the method is designed for continuous action space, it is expected to have the notations to be continuous as well. Can we just simply convert the summations into integration in the propositions!?

- The authors claim that the problem with the related work is that they can not scale up with the number of agents. However, there is no (empirical) support that how the proposed approach deals with large-scale problems.

- In general, the experiments are small and based on simulation, and simulated scenarios are not considered real-world (which is claimed otherwise in the paper). I would recommend to incorporate more supportive empirical evaluation.


Minor:
What is \phi_{-i} in eq 17
review_title: Needs some improvement

final_score: rating: 4: Ok but not good enough - rejection
review_content: Update: I appreciate the detailed replies to my questions. Indeed, some of the points I raised were addressed well and the paper updated accordingly. 

However, some new concerns were also raised by the replies:
- Using 3 seeds for the experimental evaluation is an extremely questionable evaluation protocol. There is no way to know if any of the results are going to hold up. 
- It's also clear now that none of the experiments are comparing to benchmark numbers from other publications. It would have been more confidence inspiring if the method was tested on a set of tasks where external benchmarks have already been established. 
- This is particularly true for the new results that were added to the paper, e.g. the QMIX results. It's difficult to make sense of them and the instability points towards a potential hyperparameter issue.   
- All baselines for the 'prisoners' case should at least compare to the fully cooperative case of adding up the rewards. Comparing to a DQN baseline that maximizes individual rewards is a red herring. 
- It's odd that all experiments require less than 1000 episodes to train. This is very unusual for challenging multi-agent RL problems. It would be great to understand if the main selling point of LToS is sample-complexity/learning speed or if there is something else going on.

I also agree with the concern raised by other reviewers that the paper is currently not positioned clearly. 
All things considered, I believe my score is still appropriate for the paper. However, I also believe that a future version of the paper with clarified positioning and more thorough experimental evaluation could make for a compelling contribution.

Original review:
==========
-"Obviously, CTDE cannot address such problems due to the curse of dimensionality.". CTDE means that there is the *option* to use centralized information at training time. Clearly, some ways of using centralized information will scale better than others and claiming that none of them scale is simply unfounded. 

-"One is that the reward function.. tragedy of the commons.". I am struggling to make sense of this paragraph. Please work on the clarity of the writing. 

-"However, they are learned in a centralized way and hence not scalable." These methods have been scaled to large numbers of agents in complex environments. Please provide citations when making a claim that something doesn't scale. For example, the "The StarCraft Multi-Agent Challenge", Samvelyan et al 2020, includes results for numbers of agents comparable to the largest experiments in this paper.  

-"Moreover, the observation of each agent oi ∈ Oi can be enhanced to the Cartesian product of agent i and its neighbors (Jiang et al.,
2020) or the observation history (Chu et al., 2020)". I don't follow this. If the observation of each agent includes the observation of all neighbors (which includes the observation of their neighbors), then shouldn't everyone observe everything? 

-Equation (1) is wrong. The left-hand side conditions on 'oi_', but the right-hand side conditions on 's'. This also affects all following equations. 

-"The simple way to optimize the global objective is that each agent maximizes its own expected return, which is known as Markov game. ". This is wrong. When each agent optimizes their own expected return this is typically not a means of optimizing the global objective. 

-". In networked MARL, as the reward of an agent is assumed to depend on the actions of neighbors, we allow reward
sharing between neighboring agents": The reward function also depends on the global state, 's', which is a function of the joint action of all of the agents. So this local reward sharing seems clearly insufficient in general. 

- Eqn 6 to 15: This proof seems unnecessarily cumbersome. W only redistributes the rewards, so the sum of total rewards is unchanged, qed.

-"Unlike existing hierarchical RL methods, we can directly construct the value function and action value function of φ based on the value function of π at each agent.": Constructing the value function isn't really the problem, but approximating and learning it is challenging.

Theory:
-4.3: "Each vertex has its own local policy φij (wij |oi), and we can verify their independence by means of Markov Random Field." This is not clear to me. Furthermore, given that the transition function conditions on the joint action and that the reward function depends on the central state, this seems wrong. Unless I am mistaken, the dependency on the central state should break any locality assumptions. 

Experiments:
- The results on the prisoner's dilemma are misleading. Clearly, if there is an ability to change the reward functions of individual agents (which is assumed by LToS), there is no more social dilemma. As such, only baselines that maximize the total reward are credible comparisons (and seem to be missing completely). 
- The "traffic" and "ROUTING" experiments seem more interesting. A few caveats: None of the results include uncertainty estimates. It is furthermore unclear, how many seeds were used. Furthermore, the fixed LToS baseline ("For ablation, we keep the sharing weights fixed for each agent, named fixed LToS") seems odds. Did you try a baseline where all agents simply share their reward equally with their neighbors? Also, centralized baselines are missing. E.g: https://arxiv.org/pdf/1910.00091.pdf. 
- In "ROUTING" Fixed LToS (ie. not learning to share) and LToS seem indistinguishable. 


 
review_title: Some interesting ideas, but issues with formalizing the problem setting, theory and unconvincing results. 

Meta-review: Although there was some initial disagreement on this paper, the majority of reviewers agree that this work is not ready for publication and can be improved in various manners. After the discussion phase there is also serious concern that the experiments need more work (statistically), to verify if they hold up. More comparisons with baselines are required as well. The paper could also be better put in context with the SOTA and related work. The paper does contain interesting ideas and the authors are encouraged to deepen the work and resubmit to another major ML venue.
Decision: Reject