Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper aims to address the delayed action problem in multi-agent reinforcement learning. The authors propose LeGEM, a episodic memory structure that improves the temporal credit assignment by searching for the pivot timestep and reward redistribution. The method is evaluated on four game domains.
strengths_and_weaknesses: **Strengths:**
This paper looks at an interesting and practical perspective of MARL, namely the delayed action. While it has been explored in the single-agent domain, there are fewer studies in the multi-agent domain. 

**Weaknesses:**
I found it is overall hard to follow the paper:
1. The search scheme I part (Section 4.2) lacks explanation and intuition. There is little to no explanation of the notations in the algorithms., for example, $\Upsilon, \mathbf r^{l, i}, e^i_t[j]$, the meaning of -1 in Algorithms 2 etc. (and there are more examples like these in the paper). The missing information greatly impedes understanding. 
2. Many new concepts come up without further mentioning or explanation, such as “subserve the inter-agent credit assignment”. What exactly is inter-agent credit assignment? How does it help?
3. Line 195: “the accuracy of Scheme I is over 90% in grid world scenarios.” What does “grid world” refer to? How is the accuracy defined?
4. I do not quite understand why Scheme II, a simplified version of Scheme I is able to deal with “more complex scenarios, whose trajectories are multiple-off-beat-reward trajectories”. 
5. What is the role of $\beta$ in Equation (2)? How to interpret it?
6. Why does the off-beat bellman operator enjoy contraction property?

The experiment part is not convincing either:
* If the key is to identify the pivot timestep, shouldn’t there be some experiments to investigate the accuracy of that? 
* The experiment environments are simple, with a maximum of three agents, short horizons, and small actions space. Could this be related to the scalability of the graph search method?
questions: Please see the weakness 2-6 and comments on the experiments.
limitations: The authors address some of the limitations and I do not see the potential negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper addresses the issue in off-beat multi-agent reinforcement learning, where the actions have pre-set execution durations. During execution, the environment changes are influenced by, but not synchronized with, action execution. This off-beat issues exit in scenarios, such as traffic lights and video games. To mitigate this issue, the authors propose an episode memory module, i.e., Levelled Graph Episodic Memory (LeGEM) method. The authors propose a search method to search the pivot timestep and utilize a proximal ranking method to estimate the pivot timestep, which invokes the future reward. The authors evaluate the proposed method in different scenarios, including Stag-Hunter Game, Quarry Game, Afforestation Game, and StarCraft II micromanagement tasks. The empirical experimental results show that LeGEM can boost the performance of existing RL such as IQL, VDN, QTRAN, and QMIX. 
strengths_and_weaknesses: The strengths of the paper:

* The paper is well motivated and the problem is well defined. 
* The proposed memory module shares connections with the human learning process and shows performance improvement in the experiments. 
* The paper is well structured and well written. The figures in the paper help the reader to understand the idea. 

The weaknesses of the paper:

* The baselines used in the experiments are relatively “weak”, including IQL, VDN, QTRAN, and QMIX, in the sense that they are not specially designed to solve the off-beat problem. Stronger baselines should be used. For example, the methods, which tackle the credit assignment problem should be compared, such as RUDDER [Arjona-Medina et al, 2019].  
* The LeGEM module includes the search process. I have concerns about the training time. 
* The off-beats problem exits but not very general.

questions: * How does LeGEM compare to other credit assignment methods, such as RUDDER?
* How does the training time of IQL, VDN, QTRAN, and QMIX compare to the training time of IQL-LeGEM, VDN-LeGEM, QTRAN-LeGEM, and QMIX-LeGEM?
* Does LeGEM also improves the performance in the general environments without the off-beat issue?
limitations: * The proposed method seems limited to the off-beats scenarios. It would be better if the proposed method improves the performance in the general environments.
* LeGEM introduces additional computational overhead. It might be difficult to utilize LeGEM in large scale settings.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work introduces a novel generalization of Dec-POMDPs that also takes different execution durations for actions into account. Furthermore, the authors propose a novel approach that uses graph algorithms to search for critical points in agent trajectories. These points are used to assign rewards to the corresponding action. In a series of multi-agent tasks, which are modified such that they exhibit off-beat actions, LeGEM enhanced algorithms are compared to baselines. The baseline algorithms span simple MARL algorithms to memory enhanced, more sophisticated approaches.
strengths_and_weaknesses: ## Originality

The paper introduces off-beat Dec-POMDPs, a novel generalization of delayed MDPs and Dec-POMDPs. The approach uses levelled-graphs to represent the episodic memory. This apprears to be a novel combination of levelled-graphs and deep MARL methods.

*Minor Remark:* While you include [74] in the experiments section, it should also be cited in section 4.1 as another approach that uses graphs to structure EM.

**Strengths:**

- Novel application of established data structures/algorithms to deep RL

**Weaknesses:
-**

## Quality

The approach seems to be valid in general. The experimental evaluation is a major strength of this paper. First, the authors identify relevant questions to address. The experiment design is adequate as it demonstrates the efficacy of their approach along several dimensions, such as performance improvements of existing approaches and comparisons to alternative episodic memory approaches. Thus, the experiments undermine the claimed contributions.
It would have been interesting to see how much computational overhead (e.g. training time) is induced by the graph updates and the search. You may consider to include some comparisons in this direction to other EM approaches. Furthermore, investigating the performance of LeGEM in many-agent tasks would be important.

**Strengths:**

- Algorithms appear to be sound
- Well formulated questions to answer
- Strong experimental evaluation: well chosen baselines and experiments

**Weaknesses:**

- No experiment addressing computational overhead
- Experiments only involve a few ($\leq$ 3) agents.

## Clarity

In general, the paper is well written. However, the notation that is introduced is rather heavy (many indices, sub-indices, etc...) and uses many symbols. This is especially true for section 4 and the algorithm pseudo code. Also, $\Upsilon$ is not defined in the main paper, only in the appendix. Also, the training procedure (Fig. 3) could be addressed more clearly.
Browsing through the code helped when trying to understand the algorithms. However, it would have been nice to also include a file that runs an experiment or trains a policy. Why did you not include the training script?

**Strengths:**

- Generally well written paper.
- Code was provided.

**Weaknesses**:

- The amount of symbols and indexed symbols makes it somewhat hard to read.
- No training script/executable included.

## Significance

The problem addressed in the paper, off-beat actions, is novel and most probably important for real world applications of RL. Furthermore, the proposed approach could be a stepping stone for other works exploring this new problem setting. Also the evaluation of other algorithms on this kind of problem is valuable. 
The performance was demonstrated on simple tasks. The results could be more convincing if you would include an experiment with more agents (e.g. 20).

**Strengths:**

- Significant problem with plausible real-world connection

**Weaknesses:**
- The tasks that were solved are rather simplistic.
questions: - The experiments only involve a few agents. How is the performance influenced by adding more agents, e.g. up to 100's? It would be valuable to have one experiment that explores this.
- From the experiments you run, how much overhead is approximately introduced by the graph updates/search?
limitations: The authors admit that their approach introduces a large computational overhead and that scalability was not addressed in this paper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper looks at the problem of coordination games where actions may have a delayed impact on the environment, which are referred to as "off-beat actions". To appropriately credit these off-beat actions they proposed a graph-based memory structure (LeGEM). It works by building a count-based graph of possible histories and searches for differences in graphs to assign future rewards to off-beat actions. They demonstrate their algorithm's ability to encourage coordination on three analytic games and the StarCraft II micromanagement task suite. Their results suggest LeGEM leads to a higher probability of successful coordination. 
strengths_and_weaknesses: **Strengths**
- Addresses, indirectly, a challenging problem of ascribing delayed-credit to actions. 

**Weaknesses**
- As a non-expert on "off beat" systems I found the introductory exposition challenging to read. An "off beat" action is not fully defined until page 3. I would suggest the authors provide motivating examples and describe the particular problem of "off beat" actions that they will study much earlier in the paper. 
- There are many claims that are not appropriately supported. Non-exhaustive list of examples: L38-44 contains many "challenges' of OBMAS that is neither cited nor proven why this is a quality and problem unique to OBMAS; L52-53, it's not super clear at this point what is meant by "delayed timestep of the actions" or why this might be privileged information and why this is meaningful; L236 Proposition 1 is not proved, you could imagine an adversarial reward redistribution that prevents a contraction.
- The experiments are focused around "outperforming" various MARL methods, but not on understanding the method and problem proposed. 
questions: 1. Could the authors explain how modelling the actions as having a delayed effect on the transition dynamics is usefully different here than just considering that the reward might be delayed?

2. It seems like the multi-agent aspect of this problem is simply that there are decentralized unit-actions. Why did the authors not consider comparing this work to single-agent off-beat algorithms? It seems that they might be applied directly or with small modifications and provide reasonable baselines. 

3. I am hoping the authors might better justify their choice of model for off-beat actions. Initially the exposition introduces them like a sub-system within the environment dynamics, but they're modelled as a process that occurs prior to transition. Moreover, the off-beat calculation is ego-tistically considering only a single agent. However, this paper focus is on games, should off-beat actions not consider other-agents and their influence on delays? 

4. Could the authors please clarify how their model "find[s] an off-beat reward in a trajectory" (L171). All formalisms seem to suggest that an agent receives a single scalar reward at each timestep, but it's not clear how this could be decomposed into rewards from multiple co-occurring off-beat action rewards? 

5. Nit: the line spacing on page 6 is off.

6. L124-5: "there is no MARL method that can explicitly recall the past and identify key states that lead to future reward" This seems like a pretty large claim that I don't think is genuine. Tabular methods have explicitly built state-return mappings in the past. 

7. Could the authors please comment on how this method compares to reward shaping. It seems like reward shaping methods might be comparable baselines as it could amount to modifying the credit assignment pattern for an agent. 

8. Do the authors have any analysis or ablation studies on the different components of their algorithm? It would be interesting to see which search patterns / heuristic are useful and under what settings a practioneer may want to use them (or not).
limitations: The authors should include their limitation discussion to note that (a) this method only works for strictly cooperative games, and (b) methods where all information can be perfectly shared across all agents.
review_title: null

Meta-review: metareview: The review scores for this paper were borderline, and while close to the bar for acceptance, I am unable to recommend acceptance at this time, due to the very competitive nature of NeurIPS submissions. Reviewers had mixed opinions on the applicability of the off-beat scenario presented, and concerns about missing baselines (especially using methods from single-agent RL that are better able to handle delayed effects, e.g. alternative memory architectures), clarity of presentation, and scalability. Personally, I find the problem setting interesting, but am most concerned about the aforementioned baselines. All of that said, I think this work is promising and encourage the authors to integrate reviewer feedback and resubmit.
confidence: Less certain
Decision: Reject