Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Good theoretical analysis and compliant experiment performance

1. The Limitation of Theorem 1: the authors have said that ``the optimal gap of r_i heavily depends on the size of s_i^{local}. But in experiments (including experiments in appendix), the authors only discussed the claimed optimal setting (“using the observation o_i of agent i covers $s_i^{local}$”). More experiments on other size of s_i^{local} could be added to better prove the conclusion. (Whether the best choice can not or hard to be proven mathematically.)
2. Some expression problems which may cause confusions: 1) Too many kinds of rewards including perceived reward, local reward, external reward and etc. The definitions of them are not very clear.  For example,  the perceived reward is really confused; 2) A brief algorithm flow chat and pseudo codes are needed for better understanding of how the algorithm works.
3. As this work is eventually an MARL work in solving ad hoc team setting games by decomposing reward. Some explicit comparisons (May be in form or experiments or brief analysis) should be added with some MARL methods(SSD: Social Influnce as Intrinsic Motivation for Multi-Agent Deep Reinforcement Learning; PBRS: Reward shaping for knowledge-based multi-objective multi-agent reinforcement learning). Only the credit assignment problem in RL is discussed, the authors need to discuss more on some other related works like social dilemma in MARL or reward shaping?
review_title: Good theoretical analysis and compliant experiment performance

final_score: rating: 7: Good paper, accept
review_content: The paper focuses on reward attribution in multiagent reinforcement learning, proposing a new algorithm, essentially by splitting value functions to what agents can achieve individually and learning separately how different individual rewards interact. This is an old idea, but the paper essentially applies it to the state-of-the-art deep learning machinery, producing impressive results on the hardest games state-of-the-art algorithms can manage. 

As is the case with many similar areas, the work emphasises translation of an idea to the deelp learning setting, with the usual caveats, i.e. that there is not a major new methodological or conceptual insight, and the main advance is in terms of scaling up to real-world scenarios rather than having a better explicit algorithm to manage reward decomposition at runtime in an online learning setting. In other words, we learn more about how to solve challenging games rather than about the key underlying AI problem. 

The paper does not offer a huge amount of novelty, but rather presents a solid deep RL engineering approach to solving the wider problem in a specific setting. Nonetheless, the technical material is well-developed, the presentation is overall of a high quality, and the experimental results extensive (and impressive). 
review_title: Novel method for reward attribution achieves impressive results in state-of-the-art benchmark domains

final_score: rating: 6: Marginally above acceptance threshold
review_content: To address the ad hoc team play, the authors propose a residual term of Q function, which additionally considers the states of nearby agents. A novel MARA loss is introduced to the residual term as a regularization to achieve the reward assignment implicitly. The proposed CollaQ could be easily built on QMIX and trained end-to-end. CollaQ outperforms other baselines on various tasks with the ad hoc team play setting. 

The paper is very clear and well-structured. To the best of my knowledge, the MARA regularization is novel enough. The Ad-hoc MARL is an important problem in real-world applications but has not been fully studied. The interactive term with regularization is a practical and promising method to solve this problem and could be followed by other researchers.

However, I still have some concerns:

First, the theoretical analysis of reward assignment is not close to the implementation of CollaQ. There is no real assignment mechanism. A MARA loss is derived from the theoretical analysis to achieve the reward assignment implicitly, but the MARA loss could be more straightforwardly interpreted as that the Q value should be equal to the individual value when the agent cannot observe other agents. From this perspective, the complex reward assignment is not necessary. Moreover, CollaQ is built on QMIX. However, the individual value function in QMIX does not estimate a real expected return, and the value has no meaning. Is the theoretical analysis of reward assignment still valid in QMIX?

I do not find any experiments to support the claim that "agents using CollaQ would first learn to solve the problem pretending no other agents are around using Qalone then try to learn interaction with local agents through Qcollab." I think it is over-claimed and should be removed. Splitting the end-to-end learning process into two learning stages might harm the learning. 

The visualizations in Fig 3 are helpful to understand how CollaQ works, but they are special cases. Statistical results are more convincing to verify how CollaQ influences the decision.

At the test time of StarCraft, are the IDs shuffled at each timestep or only at the first timestep of an episode?

----------Update after author response----------

I thank the authors for the detailed response. Most of my concerns have been addressed, and I decide to keep my score.

review_title: Reviews

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper studies a team of agents that collaborate to maximize a global objective, where all agents receive the same reward value as a function of their state and actions. The approach suggested here is to assign each agent a virtual ("perceived") reward function such that all the virtual rewards sum up to the actual reward. Then the problem from the point of view of agent i can be solved with local value functions that depend on the local state of agent i and its perceived reward.  It is shown that such a decoupled policy exists that approximates the optimal policy if the state structure decomposes "well enough" into local states. Experiments demonstrate the advantages of this approach on a resource collection game on the StarCraft Multi-Agent Challange, with dramatic improvements over existing methods for the scenarios that were tested. 

The paper is mostly easy to follow, and is well-written and well motivated. The idea of this paper is nice and intuitive. Being less familiar with the literature, It's hard for me to judge how novel this idea is. It seems like there must exist multi-agent works that exploit the local structure of the interaction to reduce the dimensionality. Hence, as a start, the contribution of this paper can be enhanced by extending the literature review to include works of that kind, even if under different contexts. If indeed this idea is unique enough (and had a major impact on the design of the algorithm), then this is a significant contribution. Then, the other main issue is with improving the rigor of the presentation and the math. While it's clear what the results are showing, some guessing is needed to fill in some gaps. 

The reward and state structure: I guess that the "external rewards" referred to above (1) and the "same reward" that all agents share are the same thing. Please clarify and unify the definitions. Then it's not clear what's going on with the dimensions of the local states. The local states appear in the second paragraph of Section 2 and are never properly defined, and also the local state spaces S_i are not well defined. Are the cardinalities of S_i and A_i the same for all i? otherwise, the constraint in (1) isn't clear. Additionally, it's not clear how can one measure distances of states that live in different state spaces (of different agents) as is often being done in the proofs (e.g., the proof of Theorem 1, the definition of D, and so on). On that note, the idea of "nearby agents" should be more rigorously defined. Ignoring these gaps, it looks like Theorem 1 basically shows that the better the problem decomposes into local environments, the easier it becomes to solve it distributedly. It's not clear if the math provides any added value on top of this important yet simple observation. 

The connection between theory and practice: Assigning perceived rewards to simplify the MARL problem is an elegant and appealing idea. For this reason, it's important to carefully discuss to what extent this idea actually influenced the algorithm that was tested in practice. Subsection 2.3 raises some concerns in this regard since the algorithm resorts to "end-to-end learning of Q_i", in what seems like a total bypass of the idea of the perceived rewards. Looking at equation (3) or (4), one can get the impression that the perceived rewards are just an interpretation of what happens "inside" when training the Q-values after splitting them as in (4). By itself, (4) makes a lot of sense and is very natural, so it's not clear if it isn't' easier to come up directly with (4) without knowing anything about perceived rewards. This raises the question: why isn't it possible to bypass the idea of the perceived rewards and motivate the paper based on (4), which is closer to the practical algorithm? answering this question is crucial to claim a significant contribution since otherwise the are two loosely related parts in this paper. 

Precise statements: The statements of the mathematical results often lack some definitions. The statement of theorem 1 doesn't define R_{max} (but Lemma 3 does). The statement of Lemma 3 doesn't define the distance between states (but Lemma 2 does). Please make the statements more standalone and well defined. On the same note, make sure that important definitions don't randomly appear in the paper, sometimes too late (e.g., local states). 

Experiments: The experimental results are overall nice and promising.  My only question here is why the resource collection scenario only compares to IQL and not to QTRAN/VDN/QMIX like the StarCraft scenario? 

Vague sentences and typos:

"each agent i is acted independently on its own state" - acting? based on its own state? 

(s_1,...,s_N) (bottom of page 2) - needs to be s_K

"so that" in Theorem 1 - such that 

"We found that using the observation o_i of agent i covers s_i^{local} works sufficiently well" - not clear. 

"since 1990s" - since the 1990s. 

"We sometimes also replace... in Eq.7 by its target to further stabilize training" (Page 12)- what does sometimes mean? how can one reproduce this?

"doesn't" - does not 

"Applying Lemma 1 and notice that all other rewards does not change" - do not change 

"Define the remote agents s_i^{remote}..." isn't that a set of states and not of agents? please rephrase. 

"the more distant between relevant rewards istes from remote agents" - the larger the distance?  




review_title: Nice idea, but needs some serious clarification and polishing 

Meta-review: This paper proposes a method for collaborative multi-agent learning and ad-hoc teamwork. The paper includes extensive empirical results across multiple environments (including one of known outstanding high difficulty) and repeatedly performs favourably in comparison to a suitable set of state of the art methods. The proposed method is motivated by theoretical analysis, which was considered interesting but its connection to the method in the initial paper was weak. 

Overall, there are remaining concerns which have not been fully addressed in the discussion phase. The authors' responses and discussion with the reviewers should be utilised to improve the material's presentation and to clarify the theory-empirical connection in future revisions of the paper.
Decision: Reject