Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a new learning algorithm for multi-agent reinforcement learning (MARL) when the stationarity of the policies are bounded. Non-stationarity measures how the agents' policies change with time and high non-stationarity implies slow learning in an MARL setting. The authors introduced a measure based on the KL-divergence between any pair of opponent's joint policies. The first result states that if the switching cost is bounded from above, then it is possible to derive a regret on the learning algorithm used by each agent.

The main problem is to maximize the sum of values of the agents subject to a bounded switching cost. The authors consider a mean-field approximation which assumes that the joint policy factorizes into individual policies conditioned on the observation. Based on this observations, they are able to show that it is enough to bound the switching cost of each agent rather than the overall switching cost. The authors propose a bilevel optimization problem where the outer optimization is over $\delta$ the measure of switching cost and the inner variable $\theta^\star(\delta)$ is the optimal parameter for a given choice of $\delta$. The proposed optimization procedure alternates between gradient descent at different scales. 


main_review: 
Strengths:
- I like the idea of controlling the non-stationarity of the policies to guide learning in the MARL setting.
- The proposed switching cost seems to be a useful metric to bound the non-stationarity of the agents' policies.
- Although it is quite natural that the mean-field approximation directly decomposes the overall switching cost into individual switching costs, I found the connection to be quite interesting.
- Finally, the experimental section demonstrates the effectiveness of the proposed approach compared to the other algorithms, and also it is an interesting results that the non-stationarity gradually reduces as the number of training rounds is increases.

Weaknesses:
- I found the paper hard to follow at times. Particularly, the introduction and the related work assumes significant background knowledge.
- The particular measure of non-stationarity $\mathcal{D}^t_{i,ns}$, as defined in equation (5), is not well-motivated. The authors should have provided some reasons behind choosing this function.

Some questions for the authors.
1. The bound on theorem 1 has a linear dependence on the number of time intervals $T = HK$. Therefore, the average regret doesn't vanish to zero as T becomes large, even when non-stationarity is small. What is the reason for this linear dependence? 
2. What is the justification behind replacing the $\delta_i$ in equation (3) by $\delta/n$ in equation (4)? Probably an alternative design choice is to keep the constraint $\sum_i \delta_i \le \delta$ and do a projection after each step of the gradient descent.

Some comments about the presentation.
1. I found the related work section hard to follow. However, this could be because I am not familiar with the latest work on MARL. But the authors should formally introduce MDP, POMDP, POSG through notations before discussing them in the related section. This could make the related section easy to follow.
2. Some notations should have been formally defined in the paper e.g. $\Pi_{ns}, POSG$ etc.

=============Update after reading the authors' response================
Many thanks for your response. I am happy with the way you addressed my two main concerns and I would vote for accepting the paper.
summary_of_the_review: Overall, I think the paper makes a useful contribution to the vast literature on MARL. In particular, I like the idea of using switching cost to derive better learning algorithms. The experimental evaluation also demonstrates the benefits of the proposes approach. That being said, I thought that the paper should do a better job in presenting the main ideas. Additionally, I believe bounds of some theorems (e.g. theorem 1) can be improved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes MAMT to address the important non-stationarity challenge in MARL, which is inherently resulted from the learning of other agents. Specifically, this paper makes two contributions: 1) introduces the $\delta$-stationarity metric to measure the non-stationarity, which bounds the dynamic regret of each agent; and 2) addresses the trust-region decomposition dilemma by combining message passing and mirror descent in MAMT. Experiments in four coordinated domains show that MAMT outperforms prior related works. 
main_review: **Strength:**
This paper makes a logical and theoretical connection to the proposed method based on the $\delta$-stationarity, its bound, and trust-region decomposition dilemma.

**Weaknesses and Concerns:**
1. I am unsure whether the statement "the insufficient theoretical understanding of non-stationarity" is true. In the game-theoretical MARL literature, the non-stationarity is represented by a distance of joint policy to an equilibrium. For instance, NashConv is a commonly used metric to measure the distance from a Nash equilibrium (Lanctot et al., 2017). 

*Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Perolat, David Silver, Thore Graepel. A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning. NeurIPS, 2017.*

2. I am unsure how novel the new metric $\delta$-stationarity is because it essentially measures the maximum KLD between two policies. 

3. Regarding the considered baseline methods in Section 4, is a fair comparison to MAMT conducted? For example, MAMT employs GNN layers, which could have a larger representation capacity than fully-connected layers. I wonder whether the baselines have a similar network architecture to MAMT for a fair comparison. As another related concern, MAMT's implementation uses other recent techniques, such as attention, mirror descent, and the counterfactual baseline, so it is difficult to identify whether the improvement over baselines is mainly due to which factor.

4. Regarding writing, the paper motivates and explains the idea for a general multiagent environment (e.g., "opponent" switching cost). However, the proposed method cannot be applied to competitive and/or general-sum settings because an agent cannot directly control the learning of other agents in these settings. In particular, limiting the divergence between an agent's consecutive policies in competitive settings would not be desirable because the opponent can learn faster, exploit the agent's (relatively) slow learning, and thus gain a bigger return than the agent. I also note that experiments are conducted on the four coordination environments. As a result, rewriting the paper assuming cooperative MARL settings can improve the paper's clarity. 

5. Regarding related works in A.1.2, other recent works exploit the opponent's learning process to achieve better performance. Adding the following works will make the related work section more complete:
*Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, Shimon Whiteson. Stable Opponent Shaping in Differentiable Games. ICLR, 2019.*

*Annie Xie, Dylan P. Losey, Ryan Tolsma, Chelsea Finn, Dorsa Sadigh. Learning Latent Representations to Influence Multi-Agent Interaction. CoRL, 2020.*

*Dong-Ki Kim, Miao Liu, Matthew Riemer, Chuangchuang Sun, Marwa Abdulhai, Golnaz Habibi, Sebastian Lopez-Cot, Gerald Tesauro, Jonathan P. How. A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning. ICML, 2021.*
summary_of_the_review: I initially vote for a score of 5. While the topic studied in this paper is an important problem in MARL and this paper makes a logical motivation to MAMT, I have main concerns regarding the experimental results (i.e., fair comparisons against baselines and identifying the main source of the improvements) and writing of the paper (i.e., needs to be rewritten for a cooperative multiagent setting). After reading the authors' responses to my questions, I am open to raising my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies non-stationarity in multi-agent RL. It introduces \delta-stationarity a notion that measures the non-stationarity of a policy sequence. It proposes an algorithm that satisfy \delta-stationarity by approximately constraining the consecutive joint policies’ divergence. A dynamic regret bound is proved for each agent. Experiments that verify the provided theoretical guarantees are provided.
main_review: The paper is well-written in general and the contributions and the model are well-motivated. Trust region constraints is first mentioned in the abstract, but there has not been enough context provided on how trust region constraints are related to the problem of interest in this paper. That would be great if the authors could briefly elaborate on this in the abstract. 

The main algorithm, MAMT, is not presented in the main body of the paper and I think it would be more instructive if the authors could move it from the appendix to the main body.

Is the algorithm a cooperative one? i.e., do agents communicate messages with each other? If so, how does the communication scheme work and what is the communication cost of the proposed algorithm, i.e., how many number of message bits are being communicated through the agents. Communication cost is an important aspect of every  cooperative multi-agent algorithm and a discussion on it and the ways to improve the tradeoff between the dynamic regret and communication cost is appreciated and would benefit the reader.

Could the authors provide a convincing argument about the non-incremental nature of the novelty?
summary_of_the_review: The problem studied in this paper is interesting and I think it would interest the ICLR community. While the theoretical derivations rely on previous works, e.g., Bai et al., 2019; Gao et al., 2021, they are interesting and elegant. I have not checked all the proofs, but they seem correct.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies non-stationarity in MARL. They introduce the notion of $\delta$-stationarity as a measurement of the non-stationarity of a policy sequence. They propose a trust region decomposition framework to impose trust region constraints. They estimate the joint policy divergence with a trust-region decomposition network (TRD-Net), which combined with the mirror descent policy algorithm gives the proposed MAMT algorithm. They show performance improvement in experiments than baselines. 
main_review: Strengths: Dealing with non-stationary in MARL is an important research topic in the community. The proposed method in this paper seems to achieve significant performance improvement than baselines.

Weakness: 
The novelty of $\delta$-stationarity is relatively less significant to me, especially when provided the mean-field approximation assumption.  It is suggested that the authors provide more discussion about this.  
The writing/structure of this paper needs to be improved. For example, the authors didn't summarise the proposed algorithm. The readers need to spend a hard time trying to combine all proposed ideas to imagine the final algorithm and hence it's difficult to follow. It is suggested that the authors clearly present their algorithm in a compact way. 
summary_of_the_review: Although the research topic of this paper is important, some parts of the paper should be further discussed and re-organized before it's ready to get accepted. 

Update after reading the authors' response: I appreciate the authors' response and revision (especially the algorithm section) that have addressed my concerns. I'm happy to increase my score accordingly.
review_title: null

Meta-review: Although the initial scores of the paper were not positive, the authors managed to properly address the questions/concerns of the reviewers and the changes they made to the paper convinced the reviewers' to update their scores. This clearly shows that there were flaws in the original presentation of the paper. So, I would recommend the authors to take the reviewers' comments into account when they prepare the camera-ready version of their work.
Decision: Accept (Poster)