Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a family of distributed nonlinear stochastic approximation for MARL, and derives a law of iterated logarithm, which describes the convergence rate on the converging sample path. It also presents an application using TD(0) with linear function approximation, by establishing the convergence rate and showing that it does not depend on the interaction graph. 

main_review: - The problem in consideration is interesting. The paper is also well written and the ideas are carefully presented. 
- It would be useful if the authors could provide more intuitive explanation for Assume A2, e.g., what type of scenarios does it imply, or why is it necessary? 
- The application example appears to rely on the linear form of h(x). This is consistent with A2. Can this result be generalized to other cases? 
- Section 4.3 appears to be technical and not well positioned. 
- It would be helpful if the paper could provide an example for the distributed nonlinear SA case? Although Assumption A2 allows nonlinearity (assuming through the two f functions), the application seems to focus on the linear case. 

limitations_and_societal_impact: It would be useful if the authors could provide more intuitive explanation for Assume A2, as well as more concrete application examples.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces a new distributed stochastic approximations scheme that can be exploited in the Multi-Objective RL (MARL). They show that for TD(0) with linear function approximation, we can enjoy the convergence rate of $\mathcal{O}(\sqrt{n^{-\gamma}\log n})$.
main_review: 
**Originality and Quality**

Although the theoretical material and proof techniques are novel, the paper requires major improvement in writing to be accessible to the RL community. The paper motivates their stochastic approximation scheme by having application in MARL. However, the paper, as it is, is very inaccessible to the RL community. 

In many cases, it's better that authors first provide better intuition before jumping into the math and the assumptions. 
Many terminologies are assumed to be known by the readers in the RL community, which is not the case. The paper needs to be re-written and be more self-contained so that people don't need to look for the definition of the terminologies in the references. 

**Clarity**

The paper needs major improvement in writing.

**Significance**

The paper needs major improvement to be accessible and of interest to the RL community.
limitations_and_societal_impact: The limitations and societal impact have been adequately addressed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper presents a Law of Iterated Logarithm (LIL) for Distributed Stochastic Approximation (DSA) schemes, which characterizes the rate of convergence of the updates to their stable equilibrium. The conditions are more general than previous works (in particular the gossip matrix is not required to be doubly stochastic and step-sizes need not be square summable). An application to the case of TD(0) with linear function approximation is given. 
main_review: This is a well-written paper with a seemingly strong technical contribution to the DSA literature (although I am not an expert in that area), so I am recommending acceptance. 

The writing is very clear, in particular the related works are well-covered. The proof outline (Section 4) is well sketched-out. 

One question that I had was about the nature of the convergence guarantee. The theorem statement gives a convergence rate which holds “almost surely on E(x_\star)”, where E(x_\star) is the set of sequences which converges to x_star. It seems that this does not actually quantify the probability of convergence, but simply says that IF x_n converges to x_\star then the rate will be as given (and this rate holds with probability one). Am I interpreting this correctly? If so, are there other results in the literature guaranteeing convergence with high probability (or with probability one) for the same conditions considered here? Some discussion about this point in the text would be appreciated. 

I am also wondering about the applicability of this theorem to other RL algorithms? The discussion mentions that Q-learning would require extending the analysis but have the authors tried applying this theorem to other policy evaluation algorithms (which are more likely to be “linear” and could fall under the umbrella of Assumption 2). Some discussion on this point in the text would also be helpful. 
limitations_and_societal_impact: As mentioned above, some further discussion about the implications of the LIL would be appreciated.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies asymptotic convergence rates for a family of distributed Stochastic Approximation Schemes in a cooperative multi-agent learning setting (Nonlinear Gossip models). They provide convergence rates which applies almost surely on sample paths, improving over the existing analysis that analyse the expected behavior. In addition they have weaker assumptions on the Gossip matrix and the step sizes (removing square summability).

As a result, they analyze policy evaluation through TD(0) with linear function approximation for the infinite horizon reinforcement learning problem and the convergence rates follow for TD(0).


main_review: The model studied here is not widely studied in ML literature, but they show how their results apply to TD(0) with linear function approximation in the MARL setting. The main improvement is providing convergence rates over sample paths, eventhough it is asymptotic. This applies to a subclass of cooperative multi-agent RL where agents use TD(0).

1) Could this framework be used to analyze a competitive setting or where the agents maybe negatively correlated? For instance, the setting of Markov games (Daskalakis et al. 2021)?

2) Are there any conditions that guarantee the uniqueness of $x^*$?

3) I believe a reason for the asymptotic nature is moving from the discrete updates to the limiting behavior of the ODE and I feel it would be better to add more discussion on this part (even if some of it comes from a different reference).

4) What are the challenges of understanding other function approximation schemes, maybe quadratic (for example), could this be subsumed in the function h(x)? 

5) For the reduction to the RL setting the IID assumption seems to be key to ensure A and B dont depend on n, is there a work around for this? Would it be fruitful to look at the state-action visitation distribution? 

Additional Reference:
Daskalakis, Constantinos, Dylan J. Foster, and Noah Golowich. "Independent policy gradient methods for competitive reinforcement learning." arXiv preprint arXiv:2101.04233 (2021).
limitations_and_societal_impact: See above for limitations.
review_title: null

Meta-review: This paper studies a family of distributed nonlinear stochastic approximation for MARL, and derives a law of iterated logarithm, which describes the convergence rate on the converging sample path. It also presents an application using TD(0) with linear function approximation, by establishing the convergence rate and showing that it does not depend on the interaction graph. All reviewers are convinced on the novelty and contribution of this paper. Reviewers still recommend authors to take their advices in restructuring certain part of the paper to make it more accessible to the general RL community.
Decision: Accept (Poster)