Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the multi-agent reinforcement learning policy evaluation (MARL-PE) problem, where $N$ agents collaborate to evaluate the value function of the global states for a target policy. It focuses on how to analyze the communication cost among agents when using the local temporal-difference (TD) learning method. 
First, this paper theoretically shows that executing multiple local TD steps can lower the communication complexity of MARL-PE compared to vanilla consensus-based decentralized TD learning algorithms.
Second, the paper theoretically shows that executing multiple local TD steps has higher communication complexity than the batch approach under same sample complexity condition.
Finally, executing multiple local TD steps is shown to perform similarly to the batch approach in practice under certain settings. 

strength_and_weaknesses: Strength:

1. Result novelty: this paper conducted a theoretical analysis of the approach of multiple local TD steps in terms of communication complexity, and showed that this approach indeed lowers communication complexity, which has not been shown before. This seems novel to me.

2. Technical novelty: the analysis of this paper has its technical novelty. Although the paper borrows technical tools from other works, it faces coupled challenges due to: underlying structure of TD, dynamic setting (i.e. MDP), and reward heterogeneity across agents.

3. Theoretical results are clearly stated without ambiguity.

4. Extensive empirical results are included which supports the theory. 

---
Weakness: 
There is no major technical weakness of this paper in my opinion. Still, I think the following is worth mentioning. 

1. It is not clear to me why Assumption 1 matters. Specifically, what would happen/why analysis fails if the stationary distribution is not unique? 
Is Assumption 1 very practical? 
Does it simplify the problem? What might be the extra challenges if the assumption does not hold?

---
Minor comments/Questions:

1. Assumption 4: each agent shares the same value function (i.e. same feature $\phi$ and parameter $w$)? The current statement is confusing. Why not say the global value function $V$ adopts a linear structure?

2. Typo: above section 3.2: definition of V-function: $\gamma^t$ instead of $\gamma$. 

clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is mostly clear in my opinion. The motivation and background are well introduced. The technical challenges are well covered. However, I do hope to learn more about the role of Assumption 1, such as why and how it matters.


Quality: The quality is fine. In terms of theory, the assumptions and theorems are stated without ambiguity. Although I did not check all the proof, the proof looks valid to me. The experiments are extensive enough, and details are included.  


Novelty: This paper is novel. It gives the analysis of multiple local TD steps’s communication complexity, which has been an open problem. Technically novelty is also discussed to handle the three coupled challenges. 


Reproducibility: The reproducibility seems fine. The experiments details are included. However there is no code uploaded so it is hard to be certain whether the experiments can be reproduced. 

summary_of_the_review: My current recommendation is to accept.

My reasons are the following:
Technical novelty: this paper gives a first answer to an open problem under certain settings
Good quality: the paper is well written: clear presentation, enough motivation. Detailed experiments, etc.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the multi-agent policy evaluation problem for a set of networked agents that can communicate through the network. In the linear function approximation regime, the authors apply the standard temporal difference (TD) learning method with no batch samples but multiple local TD updates per communication, and show near-optimal sample complexity and improved communication complexity compared to naive TD updates. Finally, the authors demonstrate the effectiveness of the proposed method in both synthetic and real multi-agent policy evaluation problems. 
strength_and_weaknesses: Strengths

- The communication compleixity is a bottleneck for distributed RL algorithms to efficiently work for large-scale networked systems. The studied multi-agent policy evaluation problem is a basic multi-agent RL task, which is real and meaningful. 

- The authors particularly focus on a class of temporal learning (TD) methods with local TD updates per communication. Compared with batch-based TD methods, the studied method works simpler and is more useful in practice, since a large amount of batch sampling is expensive in many real-world applications.

- It is useful to establish near-optimal sample complexity of the proposed method as the well-studied batch-based TD methods. The studied communication complexity is also important to understanding pros/cons of the proposed methods. 

 Weaknesses

- The proposed method is limited to an extension of naive TD methods for multi-agent MDPs. It is unknown about the generality of this method to other TD methods.

- This study is limited to the naive TD method which might not be very useful in some settings, for instance off-policy. Other limitations include the linear function approximation and the synchronous communication network.

- The study assumes a series of technical assumptions on the multi-agent MDPs and the function approximation. It is known that these assumptions provide convenience to analyze TD methods with Markovian data if the underlying MDP has a fast mixing. Hence, the first two claimed challenges are not the main difficulty of analyzing the proposed method. 

- For the communication complexity, it is unknown if the proposed method can match batch-based TD methods. It is useful if some lower bound can be established for the proposed methods. 

- It is expected to see that the information of network topology should be a big factor in the final error bound. This is missing. Experiments on other network topologies should be included for illustration.  

- The literature review misses many recent works on MARL policy evaluation problems, which is detrimental to the novelty. A more complete comparison is recommended, e.g., the paper:  Taming Communication and Sample Complexities in Decentralized Policy Evaluation for Cooperative Multi-Agent Reinforcement Learning. 

clarity,_quality,_novelty_and_reproducibility: Overall the paper is written well. However, there are some ambiguity in technical challenges and main results. Although several technical challenges are mentioned, some of them have been addressed for naive TD methods in the MARL policy evaluation setting. So, it is not  very clear what new techniques the authors have extended. Although the agent-drift seems to be unique challenge, the authors haven't highlight how this fails naive application of recent TD analysis. For the algorithm analysis, it is important to clarify what is the new development for analyzing the proposed algorithm compared with the mean-path result from Srikant & Ying, 2019. More discussions on generalizations to other settings, e.g., nonlinear function approximation and other TD methods, would increase the impact of the study. 

The paper has studied an extension of naive TD method for the MARL policy evaluation problem. Analyzing this extended method seems to be an adaption of existing TD analysis. Hence, novelty in method and analysis requires further justification. 

Here are some other questions for consideration:

- 'agent drift' phenomenon is interesting. Is there a way to quantify it? It is important to characterize conditions when the proposed method works and fails.

- What is the specific condition for the inverse in Eq. (4) to exist? 

- How does the mixing time in Eq. (5) relate to Assumption 1?



summary_of_the_review: The paper studies an extension of naive TD method for the multi-agent policy evaluation problem. This extension is limited to a basic TD learning setting, which leaves a question about usefulness in other settings. The analysis also extends existing mean-path analysis in a more direct way, which leaves a question about novelty of analysis. Further study on conditions when the proposed method works and fails due to 'agent drift' is also needed. Since the authors miss many recent works, the novelty hasn't been fully established without a fair comparison. Generalizations to other settings haven't been established in either theory and experiments.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Authors present a generalized TD learning for the MARL setting, with local updates occurring for K > 1 iterations for each instance of communication. Sample complexities at the inner loop (local TD updates) and the outer loop (consensus updates) are computed based on mild assumptions. Theoretical formulation predicts a worse complexity for the outer loop for the TD update method to match that of the batch learning method, but experiments produce more optimistic numbers, for reasons not provided/studied in the paper.
strength_and_weaknesses: The paper addresses a well-defined niche. By allowing for multiple local TD updates, a more general version of the MARL-PE problem is constructed and its complexities calculated.

The argument made can be even stronger with i) a more comprehensive literature review and a more strategic positioning, ii) some attempts to provide insight as to the conditions under which local TD updates would perform at its computed worst complexity, and iii) discussion on the fairness of the tested algorithms in Figures 1 and 3, perhaps by including Figures 4 and 6 in the main paper.

It would be interesting to cover an important line of MARL research related to the exchange of state information, and especially the succinct packetization of state information to exchange. Works investigating emergent communication may prove important (and arguably necessary) contenders to the local TD updates in the sense that the message-generating function can also be considered a learnable parametrization. Whereas in this paper, that function would be just the identity function accepting the parameters (after local TD updates), studies such as SchedNet (ICLR 2019) would subject the individual state information to undergo feature extraction via a trainable logic (i.e., neural networks). With the common goal of improving communication efficiency, how does the presented method compare against emergent communication methods?

Investigation on the following questions would make the paper more insightful: Under what circumstances does the computed (worst-case) communication complexity actually manifest in experiments? Do those circumstances also affect whether batch learning performs at its computed worst?

Figures 1 and 3 can be better explained, with particular emphasis on the fairness of the tested algorithms. Since the x-axis is the communication rounds, Figures 1 and 3 do not correctly reflect the K > 1 "advantage" given to the local TD update method. At every x-axis tick, the proposed method runs for K (50 or 100 or etc.) iterations, so the graphical display can be misleading, unless accompanied by graphs such as Figures 4 and 6, which picture a more honest view by taking into account both K and L and plotting the errors against sample numbers. Indeed, it is sometimes the case (Fig. 4(a)) that batch learning does better than local TD updates, depending on the choice of K and L. If that really is the case, a further empirical analysis on the effects of K and L on the competition between batch learning and local TD updates may be an interesting addition.
clarity,_quality,_novelty_and_reproducibility: Clarity
It is difficult to hold the math or the experiments as the pillaring reference of clarity as the conditions under which the computed complexities hold empirically are not studied. Also, the K-rounds advantage of the local TD updates needs some discussion as to its performance gain over vanilla TD learning.
As for the writing, there is but one minor fragment, found on the last of the three bullet points on page 3: "Although the communication," seems cut off.

Quality
Including more varied experiments (perhaps, with a few of them violating some of the four assumptions) can be a strong upgrade to the current version.

Novelty
To the best of my knowledge, the presented work is original.
summary_of_the_review: The paper's main strength lies more in the analyses on the feasibility and comparability of local TD updates in MARL-PE than in designing and implementing a novel algorithm itself. If the paper is indeed best viewed in this light, then it would be pleasant to see some updates on the literature review, complexity analyses in the experiments, and the fairness in comparison.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper aims to answer the following question: Does local TD-steps work for policy evaluation in the multi-agent setting and how does it compare with batched TD? This paper shows that in theory, local TD has a worse communication complexity than TD with batching, while in experiments they perform similarly. 

Strengths:

+ The MARL studied in this paper is an important problem

+ The paper is well written

Weaknesses:

- There is still a gap between the theory and the experiments. According to the experiments, it is very likely that the worse communication complexity for local TD-steps is an artifact of the analysis. 

- The dependence on the network topology in the complexity is missing, which again suggests that the analysis is loose.

- The discussion on the related work is not complete.

The main concern is that the results presented in this paper are not conclusive. Even after the author's response, it does not gather sufficient support from the reviewers. 

justification_for_why_not_higher_score: There is still a gap between the theory and the experiments. The results presented in this paper are not conclusive.
Decision: Reject