Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies decentralized cooperative policy evaluation. The main idea is to reformulate it as some standard decentralized optimization problem and then apply the gradient tracking and variance reduction technique.

main_review: I feel the problem setting is kind of artificial and is not well motivated by real-world applications. In this setting, the network topology is static and the value function of each agent has the same parameterization (e.g., if the value function is a neural network, then each agent shall use the same NN architecture). I cannot think of a practical application where all these conditions are met while we still cannot do centralized PE. Also in this setting, why do we want to do PE? 

The technical contributions look marginal. Formulating decentralized PE as a decentralized optimization problem is straightforward, and the techniques for solving the reformulated problem have been widely studied in the decentralized optimization literature. 

limitations_and_societal_impact: This work is purely theoretical. I am not aware of any potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of policy evaluation in a decentralized multi-agent reinforcement learning setting with non-linear function approximation. The authors present a gradient tracking based descent-ascent optimization algorithm GT-GDA that aggregates global gradients by a network-weighted aggregation, and consequently updates local parameters by descent/ascent. The authors establish convergence of the proposed algorithm and additionally analyse a reduced-variant extension. Experimental results establish convergence in several numerical benchmarks.
main_review: Originality and quality: The paper makes a complete analysis of the presented algorithm for decentralized policy evaluation in the nonlinear setting, and additionally analyses a variant with reduced variance as well. Few points:
- Given that the authors have discussed a new problem setting, it would be helpful to pin-point the exact technical contributions (from both algorithmic and theoretical points of view), as it is unclear from the current manuscript what aspects of the paper are derived from existing research.
- The motivation for the problem is still lacking: I would imagine the non-linear setting to be more difficult than the linear function approximation setting, however, it is unclear to me what technical challenges one would face in extending linear algorithms to the non-linear setting.
- The experimental results are a bit lacking: only one problem is examined, and there are no baselines to compete with. While it is clear that the authors are tackling _decentralized nonlinear_ function approximation, it would be interesting nonetheless to compare their algorithm with linear baselines in a linear (or nearly-linear) environment. Additionally, the ablations in the supplementary material can be extended to larger systems to examine the effect of sparsity: the 6-node system considered does not seem challenging based on Figure 6.

Clarity: The paper is generally well-written but requires proof-reading to remove spelling and grammar issues.

Significance: The contributions are focused and tackle a somewhat niche problem (decentralized nonlinear policy evaluation).

Specific Questions:
- How do the potential functions described in Theorems 1 and 2 compare with existing single-agent and linear function approximation potentials?

limitations_and_societal_impact: The authors have not discussed the limitations of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers decentralized MARL policy evaluation with nonlinear function approximation. The authors first reformulate the policy evaluation problem as a decentralized nonconvex-strongly-concave minimax saddle point problem and then develop a decentralized gradient-based descent ascent algorithm called GT-GDA that enjoys a convergence rate of O(1/T ).

main_review: Pros:
This work is the first to investigate the decentralized PE (DPE) problem for MARL with nonlinear function approximation.		

Cons:
GT-GDA has the same sample complex and communication complexity as DHPD [1] in which linear function approximations are considered. It is not clear to me, from both practical and theoretical perspectives, the advantage of considering nonlinear functional approximations.

[1] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo R Jovanovic. Fast multi-agent temporal-difference learning via homotopy stochastic primal-dual method. In Optimization Foundations for Reinforcement Learning Workshop, 33rd Conference on Neural Information Processing Systems, 2019.

It will be nice to provide some numerical experiments to highlight and demonstrate the advantage of the proposed framework as there are several closely related works such as [2] and [3].

[2] Hoi-To Wai, Mingyi Hong, Zhuoran Yang, Zhaoran Wang, and Kexin Tang. Variance reduced policy evaluation with smooth function approximation. Advances in Neural Information Processing Systems, 32:5784–5795, 2019.

[3] Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. In Advances in Neural Information Processing Systems, pages 9649–9660, 2018. 
 


#############after authors' response#############

I am happy with the responses from the authors (especially on the further elaboration of the contributions and explanation on why the direct comparisons with existing algorithms are not applicable). I will raise my score to 7.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work analyzes decentralized policy evaluation problem for MARL under non-linear approximation for the first time, and the sample complexity is further reduced via variance reduction technique. The prevalent compact feasible set assumption is relaxed to mild assumptions on the objective function. 
main_review: Originality: This work is claimed as the first analysis on decentralized policy evaluation problem for MARL under non-linear approximation. However, advice (1) below probably invalidates this claim, so this work is not that original. 

Quality: The submission is technically sound for minimax optimization but not for RL. See advice (1) below for detail. 

Clarity: The submission is clear and well organized. 

Significance: The results are not significant. See advice (1) below for detail. 

Advice and questions: 
(1) Your evaluation metric $\frac{1}{T+1} \sum_{t=0}^{T} \mathbb{E}\left[\mathfrak{M}_{t}\right]$ is only about the empirical objective function $F$ and its related $J$, which depends on the fixed data. In contrast, all the policy evaluation works I read use the objective function $\mathcal{L}$ (eq. (1)) to ensure generalization ability. In addition, your Assumptions 1-3 are also data-dependent. In this case, I can envision that the proof simply repeats or slightly adjusts that of the finite-sum minimax optimization, without using the generating distribution of the Markovian samples, yes? If yes, this analysis is simply about finite-sum minimax optimization not RL. $\textbf{This is the main reason why I reject this paper. If you can solve this issue, I will accept this paper.}$ 

To ensure convergence on $\mathcal{L}$, each iteration needs to use a different sample mini-batch to avoid high correlation among stochastic gradients and high computation complexity, as done by almost all the works I have seen. The data should be treated as randomly generated from MDP, not as fixed. Then, bias and variance analysis of the stochastic gradient that estimates $\nabla \mathcal{L}$ are perhaps also needed. Finally, the evaluation metric should rely on $\mathcal{L}$ not dataset, and the complexity should not contain data size $n$. 

Also, it is more desirable to replace the data-dependent assumptions into some more basic assumptions on the MDP. For example, bounded reward mapping $R$ can imply and thus replace Assumption 1a. Assumptions on $V_{\theta}$ are perhaps also desirable such as Lipschitz or L-smooth properties, which might imply some of Assumptions 1-3.

(2) In the following sentence in the abstract, you could add “under nonlinear function approximation”, since [14], [37], [42] achieved lower complexity than yours under linear function approximation. 

“To our knowledge, this paper is the first work that achieves O(ε−2) in both sample  and communication complexities in decentralized policy evaluation for cooperative MARL. ”

(3) Typo: In the V function definition in the first paragraph of Section 2.1, change $s_{t+1}$ into $a_t$. 

(4) Typo: In eq. (2), change $\frac{1}{m}\sum_{t=1}^m$ into $\frac{1}{n}\sum_{t=1}^n$. 

(5) The author sequence of [14] should be
Gang Wang, Songtao Lu, Georgios B. Giannakis, Gerald Tesauro, Jian Sun3

(6) You might also cite the following papers on policy evaluation using linear function approximation. 

- Sun, J., Wang, G., Giannakis, G. B., Yang, Q., & Yang, Z. (2020, June). Finite-time analysis of decentralized temporal-difference learning with linear function approximation. In International Conference on Artificial Intelligence and Statistics (pp. 4485-4495). PMLR.

- Chen, Z., Zhou, Y., & Chen, R. (2021). Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity. ArXiv:2103.13147.

- Liu, R., & Olshevsky, A. (2021). Distributed TD (0) with Almost No Communication. ArXiv:2104.07855.
limitations_and_societal_impact: Limitations are not mentioned. 
Both the authors and I do not think this theoretical work could have any immediate societal impact.
review_title: null

Meta-review: This paper studies decentralized policy evaluation for cooperative multi-agent RL. The main approach of this paper is (1) reduce the problem to a minimax optimization problem, and (2) develop new algorithms for solving this minimax problem using gradient tracking and variance reduction technique. As pointed out by reviewers, the main concerns of this paper are that (a) the main technique contribution is mostly in optimization, while the paper currently mainly sells as a RL paper, without detailed comparison in terms of rate with existing optimization algorithms. (b) the strongly concave assumption lacks justification in the RL setting. Except these, most reviewers are convinced that the paper is well-written, the results are solid, and this paper makes interesting contributions. We hope authors can address above concerns in the final version.
Decision: Accept (Poster)