Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper addresses a class of MARL problems where a stochastic network of agents interacts cooperatively. The give a scalable actor-critic algorithm with finite-time convergence guarantees. The guarantees are obtained via a general stochastic approximation scheme that incorporates state aggregation.
main_review: The paper is well written and overall I think it is well organized, though one could argue that Section 4 should be presented a bit earlier, since it gives much of the setting for the paper. However, I don't feel strongly either way, and I am fine with starting from the abstract/general techniques in Section 2. If the paper gets accepted, I recommend fleshing out the description of the algorithm if the conference allows additional space for the final version. 

I think the authors do a good job at motivating the new setting. I very much appreciated the results in Section 4, I think they are articulated very clearly and at the right pace. The SA scheme given in Section 2 seems fairly general, though I should note that I am not an expert on this specific sub-area, so it's hard for me to evaluate whether all relevant literature has been appropriately cited and how much incremental the results are. 

All in all, I found the conceptual setup convincing, the paper well written and the results of interest, at least theoretically. To me, the biggest weakness of the paper is its lack of experimental evaluation, which seems standard and expected at this venue. In particular, I think that the paper would be significantly stronger if the authors could also show positive experimental results, possibly comparing to the related work by Qu et al [38]---the latter provides experimental data in their Section 4. However, I think the paper brings enough to the table that I am happy to suggest acceptance nonetheless. 
limitations_and_societal_impact: -
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a Scalable Actor-Critic algorithm for a stochastic network of agents. First of all, the authors introduce a new finite-time analysis of stochastic approximation. Then they show how stochastic approximation can be used for state aggregation. Finally they proposed the main algorithms and the theoretical results.
main_review: The paper takes into account the problem of learning the optimal policies for stochastic network agents. 
The problem is interesting, and the authors show by examples that real-world problems can be cast into this framework. I appreciated the effort of the authors to motivate the considered setting.

However, I have found the paper difficult to follow and hard to read. I think that the main problem is due to the space spent for the stochastic approximation part instead then the main objective of the paper, i.e., the algorithm for stochastic network agent. In fact, until page 6, the network setting is still not presented, and so the reader does not understand what the goal of the paper is. Moreover, the main algorithm is presented only on page 8 and this leads to having only one page to discuss it. I would like to strongly suggest removing the part on state aggregation to give more space to the main part of the paper.

Going into details, the main difference between the setting proposed in this paper and the one of Du et al. is that the transitions and the rewards do not depend on static links between the agent, but that the links are sampled by a distribution $D$. An interesting aspect that is not enough discussed in the paper is: what happens to the proposed algorithm if it is in the setting considered by Du et al? Does it achieve better theoretical performance?

I have found particularly nice the fact that the $\mu$ decay property enjoys small-world phenomena. 

I think that this paper needs an experimental evaluation to compare the proposed approach with the one of Du et al. when it is in the same setting of Du et al. (since the considered setting is a generalization of the one of Du et al.). I will suggest following the same line of experiments as in Du et al. and constructing similar scenarios also for the generalized setting considered in this paper.

I will also suggest adding a conclusive section to underline the main results of this paper and to highlight the differences with the state-of-the-art works.


Post author response:
I would like to thank the authors for their detailed answers. I accordingly increase my score (5 --> 6). I am confident that the authors will follow my suggestion to move the experimental evaluation to the main paper and to add a conclusive section.
limitations_and_societal_impact: In my opinion, this paper has not potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper first study the finite time analysis of linear SA with Markov noise, then apply the result to study TD with state aggregation. This paper further study the convegence of MARL based on exp-decay assumption.

The result is not strong and the author did not make sufficient comparison with the state-of-the-art. Specifically, the rate of linear SA/TD is not compared with the state-of-the-art in terms of conditional number dependence. The rate of AC algorithm seems to be very slow but the author did not make justification for that.
main_review: (1) The linear SA with “aggregated entries" is very similar to TD with linear function approximation setting, which has be extensitvely studied before. The author did not make it clear the technical novelity compare with previous proof.

(2) In (4), the author implicitly assume that $\Phi^\top D \Phi$ is invertable. This assumption is fine for linear TD with independent features, but seems to be strong in the setting considered in this paper. The author should at least provide some justifications here.

(3) It is not clear whether the author obtain a tighter bound for TD learning compare with the state-of-art [1].

(4) Although it is a theorecial paper, empirical verification is also needed becasue this paper proposes a new algorithm here.



[1] Kotsalis, G., Lan, G., & Li, T. (2020). Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning. arXiv preprint arXiv:2011.08434.
limitations_and_societal_impact: This paper does not have potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors propose a scalable actor-critic framework for a class of multi-agent reinforcement learning (MARL) problems with a stochastic and non-local network of agents. The authors provide a finite-time error bound for the algorithm and show the dependency of the convergence rate on the speed of information spread in the network.
main_review: Pros:

MARL with network structure is an important and challenging problem. Stochastic and nonlocal networks are even harder problems to tackle under the MARL framework. The theoretical contributions of this paper are solid and the techniques used are different from the work with deterministic networks [a].				

[a] G. Qu, Y. Lin, A. Wierman, and N. Li. Scalable multi-agent reinforcement learning for networked systems with average reward. Advances in Neural Information Processing Systems, 33, 2020. 

Comments:

(1) Is it possible to include a neural-network-type-of functional approximation (see [b] and [c])? This will make the framework more general and applicable to broader problems.
[b] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence.arXiv preprint arXiv:1909.01150, 2019.
[c] Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-difference learning converges to global optima.Advances in Neural Information Processing Systems, 32, 2019.


(2) I understand the importance of the preliminary analysis in Section 2 (for stochastic approximation) and Section 3 (for state aggregation). However, the main framework of networked MARL is not introduced until page 5. The authors may consider restructuring the materials a bit.


=============After authors' response=============
Thanks for the response. I read the comments from other reviewers and the authors' responses to all reviewers. RL with stochastic networked systems is a hard problem and I think this paper has a solid contribution to the theoretical front of MARL. My only concern was the organization of the original submission and the authors agreed to rearrange the materials, which I believe is quite achievable for the camera-ready version.

Therefore I will maintain my original score of 7.
limitations_and_societal_impact: N/A
review_title: null

Meta-review: While the initial reviews were contrasting, the rebuttals helped the reviewers to appreciate better the work. The major issue raised by the Reviewers concerns the organization of the work. All the Reviewers feel that the paper should be re-organized as the authors discuss in their rebuttals. I invite the authors to do that in the camera ready. A further, but secondary, issue concerns the lack of empirical results. My opinion is that this are not strictly necessary as the paper is mainly theoretical. However, having them in the paper would make it stronger. So, I invite the authors to add some empirical results in the final version of the paper.

Decision: Accept (Poster)