Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies multi-agent distributed optimization under general consensus-type interactions between agents. The main contribution of the paper is to study linear stochastic approximation in a multi-agent setup without using bi-directional communication among agents. Non-asymptotic upper bounds on the associated error function, in a mean squared sense, are derived. 
main_review: The paper studies a concrete problem in distributed optimization in a multi-agent setting, where consensus-type dynamics prevail to allow various agents reach a global equilibrium point, which is often the globally optimal solution of some convex problem. Maintaining a consensus algorithm using bi-directional communication is rather straightforward and, by now, well-understood, but as the authors argue, relaxing this assumption poses some challenge. 

The paper is well-written and well-organized. Problem formulation and results are presented clearly and precisely. Though generally well-organized, the paper uses 3.5 (out of 9) pages of the main text for introductory, non-technical part, which suggests that the organization is more suitable for a journal submission than a conference. In this limited review time, I was unable to check the proofs. Nonetheless, the derived error bounds make perfect sense, and they look correct. 

My main concern about the paper is that it is marginally relevant for a learning conference like ICLR. To establish connection to ML and RL, the authors provide pointers to some literature studying distributed multi-agent RL problems using distributed optimization frameworks. First, I personally believe that this literature does not represent well distributed, multi-agent RL. Second, the paper addresses a challenge existing in generic distributed optimization, but not in RL. In other words, this challenge does not arise because of the RL nature of the problem, but rather comes from the networked nature of the generic distributed optimization. The problem studied here is a good fit for networked/distributed optimization venues. As such, it might get a reasonable attention if published in NeurIPS and ICML, but I think it will receive much less attention from the ICLR community. This is the main reason behind my low score. 


Minor points: 

- terms such as “mean-square” and “mean squared” are used to denote the same notion. 

- p. 3: double stochastic matrix => doubly stochastic matrix 

summary_of_the_review: This is a well-written paper studying a multi-agent distributed optimization under general consensus-type interactions between agents. I personally think that it is not of relevance for ICLR, while it might be on interest to some larger learning conferences such as NeurIPS.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper addresses a consensus problem in stochastic approximation, which has application to policy iteration in reinforcement learning. Specifically, the authors address the case where the interaction graph between agents is stochastic, but not doubly stochastic. Under certain assumptions, the authors prove convergence of their proposed algorithm in a certain sense. 
main_review: The topic of the proposed paper is certainly significant, and the extension to the general non-doubly stochastic case is important. The proofs appear to be solid at first glance, although I have certainly not verified all 47 pages of the supplementary material. Despite the significance of the topic, however, the paper is not well-conceived or well-written. 

For example, the introduction is 3 pages long and is mostly talking about how doubly stochastic matrices are not good enough to represent certain systems and discussing related literature. While it is appropriate to place the results in the context of existing literature, much of this exposition is repetitive and is undercut by the fact that the authors fail to provide a numerical example/simulation illustrating a non-doubly stochastic model. Furthermore, this extensive introduction means the authors have less space to define the problem and present the results.

This brings up the second problem with the paper, which is the lack of exposition and rigour in the definition of the problem and presentation of results. Specifically, the problem being solved is not defined. The exposition begins on page 4 with the proposed approximation/consensus rules. Yet it is unclear what the purpose of these dynamics is and what problem they are solving. I had to do significant literature survey to even understand what problem the authors were trying to solve. This lack of exposition continues to the main results in Thms 3/5. These results are presented as inequalities proving convergence of the proposed dynamics in a certain sense. Yet it is unclear to me exactly in what sense these inequalities prove convergence or what that convergence would imply about whether the proposed dynamics solve a particular problem. For example, the approximation state $\theta$ appears on both the left and the right. Does the inequality imply that the approximation state is converging to the true state or not.

This brings up my third concern which is that a certain lack of rigour impedes understanding, verification and interpretation of the results. For example, the theorem statements are not self-contained and rely on implicit assumptions and definitions of variables mentioned earlier in the exposition. This is particularly problematic since several variables are defined differently at different times. For example, $A$ is initially part of the definition of the dynamics, but then is later taken to be some property of the sequence $\pi_t$. As a result, there are numerous terms in the Thm statements for which must guess at the meaning. This is further impeded by a length series of assumptions included in the Thm statement which depend on terms which do not actually appear in the theorem statement. See the notes for specific concerns.

My final concern is that there is no validation or illustration of the proposed approach on a numerical example. This is rather unusual and makes it particularly difficult for the reader to verify or interpret the results.

- Is assumption 1 required to hold for any $X_t$?
- What are all these assumptions on? The use of assumptions is generally not rigorous, but the particular usage here does not even make it clear what these properties of which variables are being assumed. 
- the $\forall X$ in Assumption 3 is unclear.
- Which $A$ is used in assumption 3.
- Which $A$ is used in assumption 4. Also assumption 4 has some discussion which is not part of the assumption.
- The statement of Thm1 is not complete
- The use of both fixed and time-varying step sizes are unclear. I was initially under the impression that the time-varying step could be unknown or stochastic, but it seems to be prescribed. What is the motivation here?
- What is the diameter of a graph in Thm 3.
- why does $i$ not appear in the definition of $\hat w_{t}^{ij}$
- Typos: "decaying expect for" "decreasing" "that consensus interaction" "cannot be directly apply"


summary_of_the_review: In summary, the paper may contain publishable results, but is not sufficiently clear to understand what those results are, let alone verify them. In addition, the lack of a numerical illustration seriously undercuts the claims of significance. To be publishable, the authors should focus on clearly defining the problem, presenting the solution and its significance, and illustrating on a numerical example.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper:  The paper presents a finite time analysis of distributed linear stochastic approximation (non-doubly stochastic interconnection matrix) in the presence of Markovian Noise.
main_review: Strength:
               Attacking a hard setting.

Weakness:
1. A major weakness of the paper is the lack of numerical examples in the distributed TD setting. Furthermore, even a simpler toy example demonstrating the interplay between the various quantities in the Theorems is missing.

2. As the paper mentions, the value of many constants cannot be computed, however, it is sort of the inherent difficulty of the setting itself. While it is not a weakness that should limit the evaluation of the paper per se, it is nevertheless important to be highlighted and I thank the authors for the same.



Possible Technical Issues: It will be great if the authors can clarify the following.

* (Question 1) Why is that $b^i$ keeps changing with agents and yet $A$ is the same across agents? To elaborate, let us consider TD with linear function approximation, wherein $\phi(s)$ is the feature for state $s$, then $A=\phi(s_t)\left(\beta\phi(s_{t+1})-\phi(s_t)\right)^\top$, which is based on the transition from state $s_t$ to state $s_{t+1}$. In a distributed RL like setting, different agents could possibly be transitioning from different states, i.e., we would have $s^i_t$ to state $s^i_{t+1}$ and hence $A^i=\phi(s^i_t)\left(\beta\phi(s^i_{t+1})-\phi(s^i_t)\right)^\top$. This is where it would have helped to have a motivating example. 



*  (Question 2)  Consider the stochastic approximation in $2$-dimensions for just a single agent. Let $A=\left[\begin{matrix}-\gamma_{\max} ,0 ; 0 ,-\gamma_{\min}\end{matrix}\right]$ and $b=\left[\begin{matrix}0 ;0  \end{matrix}\right]$. In this case $\theta_*=\left[\begin{matrix}0 \\ 0 \end{matrix}\right]$, and assume $\theta_0=\left[\begin{matrix}1 \\ 1  \end{matrix}\right]$. In below, step sizes $\alpha_t=\frac{\alpha_0}{t+1}$, and $\theta_t=\left[\begin{matrix}\theta_t(1) \\ \theta_t(2)  \end{matrix}\right]\in \mathbb{R}^2$. 

$\theta_{t+1}(1)=\theta_t(1)-\alpha_t\gamma_{\max}\theta_t(1),$

$\theta_{t+1}(2)=\theta_t(2)-\alpha_t\gamma_{\min}\theta_t(2),$

Let us just look at $\theta_{t+1}(2)$, 

$\theta_{t+1}(2)=\Pi_{k=0}^{t}\left(1-\frac{\gamma_{\min}\alpha_0}{k+1}\right) \theta_{0}(2)$

$|\theta_{t+1}(2)|=\Pi_{k=0}^{t}\left(1-\frac{\gamma_{\min}\alpha_0}{k+1}\right)|\theta_{0}(2)|=\Pi_{k=0}^{t}(1-\frac{\gamma_{\min}\alpha_0}{k+1})$

Now using the fact that for for small $x$, we have $e^{-2x}\leq(1-x)$ we have (for sufficiently small $\gamma_{\min}\rightarrow 0$ and for $t\geq 1$):

$|\theta_{t+1}(2)|\geq e^{-2\gamma_{\min}\alpha_0\sum_{k=0}^{t}\frac{1}{k+1} }$

$=e^{-2\gamma_{\min}\alpha_0}e^{-2\gamma_{\min}\alpha_0\sum_{k=1}^{t}\frac{1}{k+1} }$

$\geq e^{-2\gamma_{\min}\alpha_0}e^{-2\gamma_{\min}\alpha_0\ln(t) }$

$= \frac{e^{-2\gamma_{\min}\alpha_0}}{t^{2\gamma_{\min}\alpha_0} }$

Picking $\alpha_0= \frac{\gamma_{\max}}{0.9}$, we have 


$|\theta_{t+1}(2)| \geq \frac{e^{-2\gamma_{\min}\alpha_0}}{t^{\frac{2\gamma_{\min}\gamma_{\max}}{0.9}} }$

We can always let $\gamma_{\max}=1$, to get $\frac{1}{t^{\frac{2\gamma_{\min}}{0.9}}}$, which is arbitrarily small rate for arbitrarily small $\gamma_{\min}$. However, Theorem 3-(2) seems to suggest that we are indeed achieving a $\frac1t$ rate. Please clarify the same.


*  (Question 3) We can think of the constant step size case to be $\alpha_t=\alpha_0=\alpha$. Now, it is intriguing that for the constant step size case we have $\alpha_0<\min\\{K_1,\frac{\log 2}{A_{\max}\tau(\alpha)}, \frac{0.1}{K_2\gamma_{\max}}\\}$, where $\gamma_{\max}$ appears in the denominator and for the time varying case we have $\alpha_0\geq \frac{\gamma_{\max}}{0.9}$, where $\gamma_{\max}$ appears in the numerator. Why is this difference on the dependence of step size on $\gamma_{\max}$? 


summary_of_the_review: While the possible technical issues can be discusses further, the score is mainly due to lack of empirical section which is a major weakness of the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of distributed linear stochastic approximation for a group of agents over time-varying directed communication networks (to be more specific, the setup is decentralized). The authors propose two decentralized algorithms, (1) consensus-based linear stochastic approximation using row-stochastic mixing matrices (Eq. (1)), and (2) a push-sum type algorithm using column-stochastic mixing matrices (Eq. (9)). They further provide results on the asymptotic and finite-time mean-square errors to the equilibrium point of the (proper) ODE for each proposed algorithm.
main_review: The manuscript considers the linear stochastic approximation problem (Srikant & Ying (2019)) for a multi-agent system. The authors revisit similar setups and results as Doan et al. (2019) for the cases where the agents interact over time-varying directed communication networks. Below, the strong and weak points of the paper are pointed out.

Strengths:
- The authors propose a push-sum counterpart for the distributed linear stochastic approximation under time-varying directed networks.
- The manuscript made a nontrivial contribution to generalize the convergence result in Doan et al. (2019) for a more complicated communication setup, time-varying directed networks.
- The authors provide a detailed analysis in the appendix for both proposed algorithms.

Weaknesses:
- The lack of any theoretical comparisons to the literature prevents the readers from understanding the technical differences between the results of this work and the existing theoretical results (e.g., Doan et al. (2019)). The reviewer suggests providing a detailed table, comparing the results in this work in terms of the constants shown in the convergence rate. This is a crucial part of such a theoretical paper.
- The authors introduced RL and specifically TD as examples of the theory developed in this paper. This reviewer suggests adding an illustrative synthetic example over a sequence of directed graphs besides additional discussions on the two proposed algorithms for that example.
- Another serious issue with this work is Assumption 6. Even after reading Appendix C, this reviewer is not convinced that Assumption 6 is a proper assumption. Indeed, the limit in Assumption 6 does not exist for multiple real-world problems. For example, consider a periodic change of $\pi_t$, given periodic communication networks. Given that all agents reach consensus on the same $\theta_t^i$, this reviewer suggests dropping Assumption 6 and modifying the statement in Theorem 2 to some time-varying ODE with $\pi_t^i$ in the definition.
- This reviewer finds the introduction lengthy, yet not sufficiently informative. Most of the discussions address the issues for time-varying directed networks, while the discussions on the linear stochastic approximation are limited. This reviewer strongly encourages the authors to add examples and/or motivations on the importance of this problem for TD (or generally RL) problems.
- As a minor issue, before using an acronym, please first mention the full form, for example, TD learning which is mentioned several times, is the acronym for temporal difference learning.
- One of the main issues of this manuscript is that it takes the reader a long time to find the main objective, which is reaching consensus on the equilibrium point of some ODE, and why this is important. The authors elaborate on the setup details, and after proposing the first algorithm (Eq. (1)), they mention that local $\theta_t^i$ converges to $\theta^\star$ which is the solution to some ODE problem (Eq. (5)). The authors do not explain why reaching consensus on the solution of the ODE is the main objective, i.e., it is not quite clear where the ODE appears in this problem. To understand the role of the ODE, the reader is required to read the Appendix. 
- For a non-expert reader, finding the differences between the two proposed algorithms (Eq.(1) and Eq, (9) is not easy. This reviewer suggests the authors take some time to improve the presentation of the two algorithms and highlight the advantages of one to the other (e.g., in a table). The manuscript in its current format is confusing, in the sense that the importance of the second algorithm compared to the first algorithm is vague. This reviewer believes that the authors should specifically address the cases wherein a column stochastic matrix is not guaranteed. This requires clear explanations.
- On a more technical note, it is not clear to this reviewer why in Eq. (1) the update rule is established based on $b^i$, while in Eq.(9) considers a convex combination of neighbors’ $b^j$.
summary_of_the_review: In summary, this work extends the existing results on the finite-time error bounds for the problem of distributed (decentralized) linear stochastic approximation to a more challenging communication setup. The paper is marginally novel and the contributions are fair. However, the manuscript has two main issues, (1) the comparisons to the previous works are missing, and (ii) the structure of the paper, as well as the presentation of its results, require some work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: An interesting submission dealing with distributed stochastic approximation driven by Markovian noise, in which the communication topologies considered among agents are captured by a stochastic matrix (in contrast to the doubly stochastic matrix studied in the related literature). Both asymptotic and finite-time error bounds are established and it was shown that the algorithm converges to some unspecified convex combination of the equilibrium points of local tasks. This paper finally proposes a push-type distributed stochastic approximation algorithm and provides its finite-time bounds for the performance by leveraging the analysis for the consensus-type algorithm with stochastic matrices. All analysis and error bounds are directly applicable to distributed TD algorithms.


main_review: Originality: This paper studies distributed Markovian stochastic approximation algorithms with stochastic interconnection matrices, which has not yet been covered in the related literature. The results are a bit different than what is known for related algorithms having doubly stochastic interconnection matrices. Further, a push-type algorithm is proposed for decentralized implementation.

Quality. The results are technically sound and theoretically supported. The algorithm proposed is fresh and new as well as interesting.

Clarity. The paper is well written and easy to follow. The results are nicely organized and the contributions relative to existing works are clear too.

Significance. The results are important and complement the existing distributed Markovian stochastic approximation results which have only focused on doubly stochastic interconnections among agents. The tools developed for analysis may also be useful for further use.
summary_of_the_review: Numerical simulations are suggested to compare the proposed algorithm and existing ones as well as validate the proved finite-time error bounds for both constant/time-varying stepsizes.

--------------
After rebuttal: After reading the other reviews and authors response, I have updated my score.
review_title: null

Meta-review: This paper studies a stochastic approximation framework for multi-agent consensus algorithms driven by Markovian noise in the spirit of the classical paper of Kushner & Yin. The authors' main result is that - modulo a series of assumptions, some conceptual, some technical - the generated sequence of play reaches a consensus, and they also estimate the rate of this convergence. 

Even though the paper's premise is interesting, the reviewers identified several weaknesses in the paper, and the reviewers that raised them where not convinced by the authors' replies (especially regarding the relative lack of numerical evidence to demonstrate the claims that are not supported by the theory, such as the role of Assumption 6). After my own reading of the paper and the discussion with the reviewers during the rebuttal phase, I concur that this version of the paper does not clear the bar for acceptance - but, at the same time, I would encourage the authors to submit a suitably revised version at the next opportunity.
Decision: Reject