Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the cooperative average reward fully decentralized multi-agent reinforcement learning (MARL) problems, where the agents interact with their neighbors over a communication network. It proposes a consensus-based actor-critic algorithm and shows its convergence to the stationary point. The convergence rate and sample complexity of this algorithm are provided and comparison with existing algorithm is shown in the numerical experiments. 
main_review: This paper is well written and easy to follow in general. Its theoretical contribution on the first finite time convergence result (to the stationary point) for fully decentralized MARL in the average reward setting is important. However, I have some comments and questions for the authors, which are listed below.
1. Why is the work (Chen et al., 2021) independent of the number of agents? Is it because of the difference between discounted setting and the average reward setting?
2. Assumption 2 should be a lemma or a proposition under Assumption 1. Also, I think Assumption 7 should be able to be replaced with some more explicit conditions (see for example Lemma 10 in [1]). Also it would be better if the authors can comment on how essential this assumption is as it is not needed in (Zhang et al., 2018).
3. Please better highlight the differences from (Zhang et al., 2018) in Algorithm 2, and which parts are improvements that lead to better theoretical guarantees and numerical results and which parts are sacrifices to allow for private (instead of joint) actions observability. In particular, in Section 4, the explanation on the modification of the actor step to allow for private action observations is unclear. It's a bit hard to follow what's the relationship among the global, networked and local TD errors and what are changed compared to the TD error computation in (Zhang et al., 2018). It would also be helpful to comment more which changes are to allow for the more challenging private action observation assumption, and which changes (also) contribute to some theoretical and numerical improvements (as suggested in the subsequent sections). 
4. At the end of Section 5, it seems that the comment on the $O(\epsilon^{-1})$ sampling does not necessarily indicate that (Zhang et al., 2018)'s overall communication complexity is empirically worse (with appropriate hyper-parameter choices, such as step-sizes and mini-batches). In fact, synchronous actor and critic updates (instead of first updating the critic for many steps and then updating the actor) is more frequently adopted in practice. 
5. It looks a bit weird to me why observing the joint actions does not seem to have any benefits according to the numerical experiments. If I understand correctly, in addition to addressing the private action observation challenge, this paper also considers mini-batch updates and constant step-sizes modifications. These can also be easily applied to the classical MARL algorithm in (Zhang et al., 2018). For a fair empirical comparison, I think it's important to provide some comparisons with the mini-batch constant step-size version of the baseline classical MARL algorithm. 

References:
[1] X. Guo, A. Hu and J. Zhang. Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methods.
summary_of_the_review: This paper proposes a new actor-critic algorithm to deal with a cooperative average reward fully decentralized MARL and provides the first finite time convergence result. The theoretical results are important. However, the differences with existing literature are not well explained and numerical experiments need some improvements.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers cooperative multi-agent reinforcement learning (MARL) for average reward MDPs with fully decentralized actor-critic methods. In particular, the authors make some progress on top of existing works in this direction, and in particular (Zhang et al., 2018). More precisely, the authors remove the assumption in (Zhang et al., 2018) that the joint actions are observable to all agents, and propose to modify the actor updates with mini-batch TD sharing to accommodate the scenario where each agent only observes its own action. The authors then establish a finite-sample bound for the proposed algorithm in terms of convergence to stationary points under linear value function approximation. Numerical experiments are also provided to showcase the benefits of the modifications over the algorithm in (Zhang et al., 2018). 
main_review: [Reasons to accept]
This paper makes some relatively non-trivial progress on top of (Zhang et al., 2018). In particular, while (Zhang et al., 2018) requires that each agent observes the joint actions of all agents, this paper only requires each agent to observe their own private action. In addition, this paper also derives the first non-asymptotic bound for fully decentralized MARL on average reward MDPs. Thirdly, some numerical experiments are also provided to show that the modifications in this paper actually lead to improvement over the algorithm in (Zhang et al., 2018). 

[Questions and concerns]
However, there are also some issues in this paper regarding assumptions, literature comparisons and numerical experiments that the authors need to address. See below for the details.
1. The comparison of the results with (Zhang et al., 2018) may not be sufficiently fair. In particular, the assumptions made in that paper seems to be different from the current paper (e.g., Assumption 7 seems not to be needed in (Zhang et al., 2018). I would suggest the authors to make it clearer in Section 3.2 which assumptions are different from (Zhang et al., 2018), why they are essential, and how they help obtaining the improved results (like the non-asymptotic results) in the current paper. On a related point, the clarity of Section 3.2 also needs some improvement. For example, Assumption 2 is implied by Assumption 1, and so should not be stated as a separate assumption. Also, the notation of consensus weight matrix, $A_{\pi_{\theta}}$ and advantage functions all use $A$, which might cause some confusion. 
2. The authors should also compare the results with the recent global optimality literature of actor-critic methods, such as [A,B]. Are there any essential challenges in obtaining global optimality bounds using the techniques introduced in papers such as [A,B]? Also, in [A], it is mentioned that from both theoretical and practical perspectives, bi-level actor-critic methods which first update the critic to sufficient accuracies as in the current paper are typically seldom adopted in practice. However, the numerical results in this paper seem to suggest that the bi-level/mini-batch updates might indeed be beneficial. Some more discussion and numerical experiments are needed to validate this (see the next point for more comments). 
3. I have some questions for the numerical experiments. The authors mentioned that constant step-sizes are key to the improvement over (Zhang et al., 2018). Then what if using the same constant step-sizes for the classical MARL algorithm in (Zhang et al., 2018)? And what about updating classical MARL in a mini-batch critic/bi-level manner as in this paper? I think providing these comparisons are important to understand what are essential in the modifications on top of the classical MARL algorithm. Otherwise, it gives me an impression that allowing for observing global actions is impeding the performance, which is counterintuitive. 

There are also some minor suggestions, as detailed below:
1. In Assumption 5, why is $\Phi u \neq 1$ for any $u$ reasonable? I understand that this is a classical assumption, but still some explanations would be helpful. 
2. Some more comments on what the quantity $A_{\pi_{\theta}}$ in (1) is would be helpful. 
3. On page 6, 2) The Actor Step, “where in our model” might better be “whereas in our model”. 
4. On page 7, what is “the weight information of other agents”?
5. It would be helpful to refer to the x-axis in the plots as “number of samples” instead of “sample complexity”. And just to double check, does one sample mean tuple of $(s,a,r,s’)$?  

[A] Fu, Zuyue, Zhuoran Yang, and Zhaoran Wang. "Single-timescale actor-critic provably finds globally optimal policy." arXiv preprint arXiv:2008.00483 (2020).

[B] Yang, Zhuoran, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. "On the global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost." arXiv preprint arXiv:1907.06246 (2019).

summary_of_the_review: The theoretical contribution of this paper on top of (Zhang et al., 2018) is good. However, there also are some issues in terms of the assumptions, comparisons with the global convergence of actor-critic methods literature and numerical experiments that need to be addressed.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies a networked MARL problem based on the model in [Zhang et al 2018], where each agent can observe the global state, take local action and observe local rewards. The key difference in setting from [Zhang et al 2018] is that [Zhang et al 2018] assume the global action can be observed, but in this paper, only local action is known to each agent. To deal with this, an additional consensus loop is added to estimate the average TD error, which can be used to estimate the advantage function. Further, compared to [Zhang et al 2018], a finite time error bound is provided. 

main_review: Strength
Only local action is observed, which is an improvement from [Zheng et al 2018]. 
Finite-time convergence is provided which matches those bounds in single-agent AC. 
 
Weakness
1. The time index is a bit confusing. In Algorithm 1 (TD subroutine), there is a $s_{k,\tau}$ state sequence. In the outer loop, there is a $s_{t,\tau}$ sequence. This is quite confusing: do these states in the subroutine and the main Algorithm 2 form a single trajectory, or these are multiple trajectories?
2. In the TD subroutine, many TD errors are computed. Why can’t such TD errors be used to estimate the advantage function, as opposed to the approach in the paper (Line 1-10 in Algorithm 2) where many new TD errors are sampled? 
3. The benefit of Batch is not sufficiently discussed. For example, how does the batch algorithm compare with the “non-batch” algorithm, where one update is made after each sample?
4. While $t_{gossip}$ scales with $1/\epsilon$, each time a $B$-length vector is communicated, and $B$ also scales with $1/\epsilon$. So the overall communication is somehow more than just $t_{gossip}$, and this should be discussed. 
5. This simulation scope seems too limited (in the standard of ICLR). 

summary_of_the_review: Overall this is an interesting generalization from [Zhang et al 2018], but I feel many points are worth more elaboration and discussion. More simulation is needed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper establishes the first finite-time convergence result of the actor-critic algorithm for fully decentralized multi-agent reinforcement learning (MARL) problems with average reward. It focuses on the practical setting where the rewards and actions of each agent are only known to itself, and the knowledge of joint actions of the agents is not assumed. The established finite-sample complexity matches that of the state-of-the-art single-agent actor-critic algorithms.
main_review: In general, the paper is well-written, well-motivated, and the literature review is very complete. I enjoyed reading the paper. The detailed comments are as follows:

1. It would be better if the authors could explicitly summarize the difference, and mainly, the technical challenges of the analyses for the decentralized average reward setting, compared to the discounted setting and the centralized setting, in the introduction of the paper. 
2. I wonder what is the difference of the Algorithm 2 in the paper from the Algorithm 2 in Zhang et al., 2018? In the Algorithm 2 therin, the "global average reward" $\bar r$ needs to be estimated separately, in order to obtain the right TD error estimate. It seems a bit surprising to me that this paper can do it using only $r^i$. A detailed comparison and intuition would be necessary. 
3. In the statement of Theorem 3, how large is the eps^{critic}_{approx? Would the upper bound for stationarity be vacuous? Some discussions are necessary.
4. It would be better if the simulation section could include more complicated and realistic settings. The current empirical contribution is a bit limited. 
5. Some typos: On the top of page 2: "without join action" should be "without joint action"; Assumption 5. “bdd” should be “bounded”.
summary_of_the_review: The paper has made valid contribution to the area of multi-agent RL, and is well-written. As the empirical contribution is a bit limited, so I would view the main contribution to be theoretical. However, some detailed comparison with the most related works is needed, before justifying the novelty and significance of the theoretical contribution.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the finite-time convergence and sample complexity of MARL with average reward, focusing on actor-critic algorithm. It proposes a mini-batch Markovian sampled algorithm and obtain its sample complexity. 

main_review: - The paper is in general well written and well motivated. The ideas are clearly explained and presented in an organized way. 
- The log(N^5/\epsilon) term in the complexity appears odd. It seems that that log(N/\epsilon) is enough. 
- The assumption on observable global-state and unobservable global action should be better justified. It would be helpful to provide an example for it.. 
- Assumption 1 needs more explanation. It seems to assume that the optimal policy will always utilize all actions with non-zero probability? Usually it is more common that a deterministic policy exists for many problems. Please elaborate. 
- There is a typo in Assumption 5. “bdd” should be “bounded”. 
- The last sentence in Assumption 5 should be better explained. What does the condition imply?
 - Theorem 2 seems to indicate that a smaller beta gives a better result? Can the authors provide some intuition? 
- The paper claims that the current work is still an improvement of Zhang et al 2018. Can this be made more specified? 
- In the experimental section, the reviewer wonders whether schemes from the discounted case with gamma->1 can be compared here? Intuitively, they should also give reasonable performance. 
- Any intuition for the fact that the empirical sample complexity does not scale with N? Could this be because of the special topology used? 
- It might be helpful to strengthen the experimental section. The current setup is a bit limited.
summary_of_the_review: The paper is well written and the topic is timely and of interest. Some assumptions/statements require more elaboration and the experiments should be strengthened.
review_title: null

Meta-review: This paper provides actor-critic method for fully decentralized MARL. The results remove some of the restrictions from existing results and have also obtained a sample bound that matches with the bound in single agent RL. The authors also give detailed responses to the reviewers' concerns. The overall opinions from the reviewers are positive.
Decision: Accept (Spotlight)