Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes two decentralized AC algorithms, one for actor-critic and the other for natural actor-critic, which are sample and communication efficient. The paper also provides their finite time performance, which is comparable with their corresponding single-agent state-of-the-art results in sample complexity. 
main_review: Strengths:

1. The sample complexity of the proposed decentralized algorithms is comparable to their single-agent state-of-the-art results.

2. The decentralized NAC algorithm is probably the first one in the literature. 

3. Using a separate distributed averaging procedure to estimate team average policy gradient is an interesting idea to avoid sharing/broadcasting local actions. 

Weaknesses:

1. Although the idea of using a separate distributed averaging procedure to estimate team average policy gradient is interesting, it requires additional coordination among the networked agents. The value of T' needs to be carefully designed and shared among all the agents. 

2. The paper claims privacy-preserving. But it reads like a immediate, lower-level privacy concern. Does it involve any qualitative support?

3. The paper claims the technical challenges due to mini-batch updates. But the description at the end of Section 4 is still vague. What is the difference/novelty compared with the techniques used in "Finite-sample analysis for decentralized batch multi-agent reinforcement learning with networked agents" by Zhang et al. in TAC 2021?

4. The proposed idea involves additional T' iterations for distributed averaging in each time step. Is it still fair to compare with the single-agent case without such inner iterations? 

5. Why in Table 1 (63) is marked as both private and non-private? 


summary_of_the_review: The paper proposes a new decentralized AC framework which combines existing decentralized techniques including distributed averaging and TD learning. The idea is interesting but not sophisticated. The NAC part is probably the first decentralized NAC algorithm. Combining existing tools may lead to new analysis challenges, which needs to be further clarified. Thus I think the paper is on the board line.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces a decentralized multi-agent actor-critic algorithm. Different from existing algorithms, the new algorithm enjoys both the privacy and the communication efficiency. 
 
main_review: Strengths: 
1.	The proposed two decentralized multi-agent actor-critic algorithms achieve the state-of-the-art sample and communication complexities. The proposed algorithms also preserve privacy which seems important in practice.  
2.	Experiments have demonstrated that the proposed algorithms achieve lower sample and communication complexities than the existing decentralized AC algorithms. 

Weakness: 
1.	The paper does not put this work into context. In general, efforts over the past year/two have been made to develop different policy-based and value-based algorithms for MARL, some of which have also considered communication efficiency. Authors have missed many works in this field. Even for related works mentioned in this paper, the authors did not discuss their advantages and disadvantages, which makes hard to evaluate the real contributions of this work. 

2.	In the beginning of this paper, the authors mention privacy as the main motivation and the selling point of this paper. However, there is not explicitly definition of privacy nor the theoretical guarantee on privacy. In addition, there is a growing line of literature of differential privacy in RL, which has not been discussed in this work.

3.	The proposed algorithm seems impossible to be implemented in practice. There are two reasons behind this. One is that the number of samples N and N_c need to grow with accuracy epsilon^-1, which will eventually blow up as the number of iterations increase. More importantly, different from existing decentralized AC algorithm that uses one transition per update (e.g., [63]), the proposed algorithms require N or N_c transitions involving global states and actions per local update. Note that different from the centralized AC and PG, in the decentralized MARL setting, unless the agent has a accurate simulator to simulate the entire MARL systems, it is not possible to obtain more than one transition per update in MARL.

4.	The optimality gap in Theorem 2 can be very large. Specifically, there are three terms that depend on the unknown actor and critic approximation errors. Are they necessary to be in the bound? Any lower bound to justify this? Is it possible to quantify this?

5.	Numerical experiments seem very limited and not thorough enough considering the number of works published on a daily basis in this field. Specifically, only randomly generated MDPs have been tested and only one baseline [63] has been compared. Furthermore, in Theorem 2, the global convergence has been proved. It would be great to validate the optimality gap in this simulation.


summary_of_the_review: Two new decentralized AC algorithms have been developed with guaranteed  sample and communication complexities. However, some claims are not justified and the implementation is not realistic.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper developed two sample and communication efficient decentralized actor-critic algorithms for multi-agent reinforcement learning. Specifically, the authors proposed decentralized AC and natural AC algorithms that can be private and efficient for different agents to learn. They added noise the local rewards of agents, which were shared among different agents. Moreover, the authors adopted mini-batch updates for the actors and critics in these two algorithms. Theoretically, the authors showed that both algorithms were able to achieve the state-of-the-art sample complexities. To validate the proposed algorithms, they used a simple environment to show the superiority over the existing decentralized AC algorithm. Overall, the investigated topic in this paper is absolutely interesting. The sample and communication complexities of decentralized MARL algorithms remain active research areas. While the mathematical analysis in this work looks good, the numerical results to me don't look very convincing. Additionally, there are quite a few points I have in mind regarding the proposed algorithm and the relevant analysis.
main_review: 1.	In the abstract, the authors mentioned that the proposed algorithms were developed with linear function approximation. That way, how to apply the theory to scenarios where typically deep nets are utilized?
2.	In Table 1, though this paper is focused on AC type of algorithms, other decentralized algorithms, such as Q learning, value-prop, etc., should be discussed here for comparison as well. 
3.	When the authors mentioned Markovian sample, would it refer to a trajectory or just one transition? If it was a trajectory, then it might be enough in practice. As a mini-batch in practice could be time-consuming for updates, though it did really reduce the variance.
4.	In the proposed algorithm, each agent shares Gaussian-corrupted local reward. Then the differential privacy should be involved in this work? Also, why not sharing the parameters of actor or critic, which has been popular in decentralized optimization domain?
5.	The authors only put related works together without any discussion on their advantages and disadvantages, which renders the weak motivation. I would suggest the authors discuss these in detail to provide better comparison.
6.	In page 5, the authors mentioned that they could choose a large batch size to suppress the overall estimation error to the desired level. A large batch will definitely affect the accuracy and computational time in practice based on existing conclusions from the study in deep learning using large batch. Additionally, the authors cannot just always increase the size of mini-batch.
7.	In Algorithm 2, extra local model averaging steps are taken. Would this cause additional communication overhead in practice?
8.	In Theorem 1, $\epsilon$ is required to satisfy a condition. Similarly in Theorem 2. Why do you need such conditions? Can you not just define it as an arbitrarily small constant as in other works? If $\epsilon$ is too big, the optimality would be poor. For the finite-time analysis, can you not just make the step size and other constants satisfy some conditions w.r.t. time $T$ and derive the complexity? That way, typically $T$ needs to be sufficiently larger than one constant.
9.	In the discussion for Theorem 1, the author mentioned that “different from the existing decentralized TD (39) that uses a single sample to update the value function parameters per communication round, we use a mini-batch of $N_c$ samples instead to significantly reduce the communication complexity of decentralized TD learning while maintaining the same level of sample complexity.” Basically existing decentralized TD algorithm uses a single sample to update the value function parameters per communication round, the authors used a mini-batch of samples to reduce the communication complexity. Why is this true? Basically, when a mini-batch of samples is used, the variance can be used. But if the authors keep the same communication frequency, the number of communication rounds remains the same. Or after the authors use the mini-batch of samples, they do multiple updates before next communication round? When the authors mentioned the same level of sample complexity, I think they should give more detail on this. As in their case, I am not very clear about what sample complexity refers to. Is it the number of data samples required for update? Or the number of gradient oracles required? Or else?
10.	In the decentralized NAC, it requires to solve a quadratic programming. Would it increase the computational complexity when solving a quadratic programming problem? The approximation to the inverse Fisher information matrix looks complicated. In practice, what is computational time cost? Also, the Fisher information matrix has to be uniformly positive definite for the analysis. Such an assumption seems to be too strong.
11.	After Theorem 2, one statement is that “the result proves that the function value optimality gap asymptotically converges to the order…”. Finite-time typically corresponds to the non-asymptotic convergence, correct? If the authors require asymptotic behavior, why are those different parameters required to satisfy conditions w.r.t. $\epsilon$? Or did I misunderstand?
12.	At the bottom of Page 8, the authors mentioned that a sample budget was set in the analysis. Why is such a total sample budget constraint there? When $k$ is very large, $N_k$ will be huge. How would you implement this in practice?
13.	Though the experimental results make sense and sort of validate the algorithms, they are not convincing. First, the benchmark environment is too simple, only a few states with a couple actions. We have no idea how the proposed methods would perform under some popular benchmarks, such as gridworld, which has many more states. Second, more algorithms are required for comparison. It is understandable that this paper focuses significantly on the AC type of algorithms, while other existing algorithms have been proposed, and one or two of them should be used for the comparison. Third, for decentralized algorithms, different topologies are critical to be shown for demonstrate the effectiveness.
14.	In this paper, the authors used partial policy gradient. Why not directly using local policy gradient? The authors also mentioned that “…to obtain an accurate estimation, the network needs to have a sufficiently large number of agents, which can be unrealistic in practice.” But typically in practice, this can happen and remains a challenge. How to scale decentralized algorithms to large networks?
15.	What is $(\{s_t\})_t$ in page 5?

****************************************
I really appreciate the detailed responses from the authors and they did address some confusions regarding the theoretical analysis. More experimental results also provided better validation for the proposed algorithms. However, there are still some confusions in the revised draft. For example, in Table 1, why is the sample complexity for paper (54) much much larger than others? If $\epsilon = 0.001$, then the complexity is completely intractable. I checked the paper and don't think the complexity given in the Table 1 for paper (54) is correct. Additionally, after carefully reviewing comments from other reviewers, I decided to keep the score and believe with some more work, the paper will be technically solid and sound and a nice publication.
summary_of_the_review: Overall, I think the current form of the paper still requires substantial work to make it technically solid and sound. In particular, the numerical results are not very convincing, and there are numerous confusions in the analysis, which have weakened the theoretical contributions. I hope my comments can help out.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this work, the authors propose two decentralized policy gradient-type algorithms for multi-agent reinforcement learning, namely, a decentralized actor-critic algorithm and a decentralized natural actor-critic algorithm. The stochastic updates of both algorithms preserve the agents' privacy information, including their local actions and local rewards. The authors analyze the finite-time convergence rate of both algorithms under Markovian sampling and linear function approximation, and prove that both algorithms achieve the state-of-the-art sample complexities and improved communication complexities.
main_review: The paper is professionally written and well-organized. This is the first work that derives sample complexity bounds for decentralized AC-type algorithms, and the obtained sample complexities match the existing ones of centralized AC and NAC. Moreover, the corresponding communication complexities are orderwise lower.

Pros: 

The developed algorithms are fully decentralized. Especially for the decentralized NAC algorithm, the agents use decentralized SGD to compute the inverse of the fisher information matrix via solving a quadratic problem. This is proven to be computation-efficient.

The algorithm designs of AC and NAC use mini-batch sampling to substantially reduce the communication complexity (by an order of $\epsilon$). Also, the algorithm updates avoid sharing local actions. To accurately estimate the average reward while preserving privacy of the local rewards, the authors propose to add large Gaussian noises to each of the local rewards, and the total noise variance is shown to be substantially suppressed after averaging. This is because the mini-batch samples and local averaging help suppress the noise variance.

For the decentralized NAC, decentralized SGD is used to solve for the natural gradient update. This decentralized SGD uses Markovian samples and an adapted batch size scheme. Such a design helps optimize the error bound and achieve the desired complexity.

Questions:

The decentralized NAC algorithm involves multi-level loops, is there a more effective way to implement it in practice?

For the same algorithm, is it possible that we only update the inner mini-batch SGD for a single iteration and still achieve the desired complexity results?

In the critic update, the algorithm performs multiple steps of local model averaging after the main critic updates. What is the purpose of introduing these additional consensus steps? Is it necessary?
summary_of_the_review: The paper is professionally written and well-organized. This is the first work that derives sample complexity bounds for decentralized AC-type algorithms, and the obtained sample complexities match the existing ones of centralized AC and NAC. Moreover, the corresponding communication complexities are orderwise lower. I think the developed decentralized AC and NAC algorithms are good complements to the existing multi-agent RL literature, and hence I recommend accepting this work.
review_title: null

Meta-review: While authors have updated the draft to address reviewers' concerns, some parts are still not clear enough and the presentation needs further improvements. I encourage authors to revise the draft accordingly and resubmit in the future venues.
Decision: Reject