Finite-Time Error Bounds for Distributed Linear Stochastic Approximation
Authors: Yixuan Lin
Ji Liu
Vijay Gupta
Venue: ICLR 2022 Submitted (2022)
Keywords: Stochastic Approximation
Distributed Stochastic Approximation
Finite-time Analysis

Abstract: This paper considers a novel multi-agent linear stochastic approximation algorithm driven by Markovian noise and general consensus-type interaction, in which each agent evolves according to its local stochastic approximation process which depends on the information from its neighbors. The interconnection structure among the agents is described by a time-varying directed graph. While the convergence of consensus-based stochastic approximation algorithms when the interconnection among the agents is described by doubly stochastic matrices (at least in expectation) has been studied, less is known about the case when the interconnection matrix is simply stochastic. For any uniformly strongly connected graph sequences whose associated interaction matrices are stochastic, the paper derives finite-time bounds on the mean-square error, defined as the deviation of the output of the algorithm from the unique equilibrium point of the associated ordinary differential equation. For the case of interconnection matrices being stochastic, the equilibrium point can be any unspecified convex combination of the local equilibria of all the agents in the absence of communication. Both the cases with constant and time-varying step-sizes are considered. In the case when the convex combination is required to be a straight average and interaction between any pair of neighboring agents may be uni-directional, so that doubly stochastic matrices cannot be implemented in a distributed manner, the paper 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.

Under review as a conference paper at ICLR 2022
FINITE-TIME ERROR BOUNDS FOR DISTRIBUTED LIN- EAR STOCHASTIC APPROXIMATION
ABSTRACT
This paper considers novel multi-agent linear stochastic approximation algo- rithm driven by Markovian noise and general consensus-type interaction, in which each agent evolves according to its local stochastic approximation process which depends the information from its neighbors. The interconnection structure among the agents is described by a time-varying directed graph. While the con- vergence of consensus-based stochastic approximation algorithms when the inter- connection among the agents is described by doubly stochastic matrices (at least in expectation) has been studied, less is known about the case when the intercon- nection matrix is simply stochastic. For any uniformly strongly connected graph sequences whose associated interaction matrices are stochastic, the paper derives finite-time bounds on the mean-square error, defined as the deviation of the output of the algorithm from the unique equilibrium point of the associated ordinary dif- ferential equation. For the case of interconnection matrices being stochastic, the equilibrium point can be any unspecified convex combination the local equi- libria of all the agents in the absence of communication. Both the cases with constant and time-varying step-sizes are considered. In the case when the convex combination is required to be straight average and interaction between any pair of neighboring agents may be uni-directional, so that doubly stochastic matrices cannot be implemented in distributed manner, the paper proposes 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.
INTRODUCTION
The of reinforcement learning (RL) obtain policies that describe solutions Markov deci- sion process (MDP) in which an autonomous agent interacting with an unknown environment aims to optimize its long term reward is now standard Sutton & Barto (1998). Multi-agent distributed reinforcement learning is useful when team of agents interacts with an unknown environment or system and aims to collaboratively accomplish tasks involving distributed decision-making. Dis- tributed here implies that agents exchange information only with their neighbors according to certain communication graph. Recently, many distributed algorithms for multi-agent RL have been proposed and analyzed (Zhang et al., 2019). The basic result in such works is of the type that the graph describing the communication among the agents bi-directional (and hence can be represented by doubly stochastic matrix), then an algorithm that builds traditional consensus algorithms converges to a solution in terms of policies to be followed by the agents that optimize the sum of the utility functions of all the agents; further, both finite and infinite time performance of such algorithms can be characterized (Doan et al., 2019; Zhang et al., 2018b).
This paper aims to relax the assumption of requiring bi-directional communication among agents in a distributed RL algorithm. This assumption is arguably restrictive and will be violated due to reasons such packet drops or delays, differing privacy constraints among the agents, heteroge- neous capabilities among the agents in which some agents may be able to communicate more often or with more power than others, adversarial attacks, or even sophisticated resilient consensus al- gorithms being used to construct the distributed RL algorithm. A uni uni-directional communication graph can be represented through (possibly time-varying) stochastic which may not be doubly stochastic matrix being used in the algorithm. As we discuss in more detail below, relaxing the assumption doubly stochastic matrix to simply a stochastic matrix in the multi-agent and dis- tributed RL algorithms that have been proposed in the literature, however, complicates the proofs of their convergence and finite time performance characterizations. The main result in this paper is to provide finite time bound on the square error for a multi-agent linear stochastic approx- imation algorithm in which the agents interact over a time- varying directed graph characterized by stochastic matrix. This paper, thus, extends the applicability of distributed and multi-agent RI.

---

Under review as a conference paper at ICLR 2022
algorithms presented in the literature to situations such those mentioned above where bidirec- tional communication at every time step cannot be guaranteed. As we shall see, this extension is technically challenging and requires new proof techniques that may be of independent interest.
Related Work (See Appendix B for more related work) Many distributed reinforcement learning algorithms have now been proposed in the literature. In this setting, each agent can receive informa- tion only from its neighbors, and no single agent can solve the problem alone or by 'taking the lead'. A backbone of almost all distributed RL algorithms proposed in the literature is the consensus-type interaction among the agents, dating back at least to Tsitsiklis (1984). Many works have analyzed asymptotic convergence of such RL algorithms using ODE methods (Zhang & Zavlanos. 2019; Zhang et al., 2018b; Suttle et al., 2020: Zhang et al., 2018a). This can be viewed as an application of ideas from distributed stochastic approximation (Kushner & Yin, 1987; Stanković et al., 2010; Huang, 2012; Stanković & Stanković, 2016; Bianchi et al., 2013; Stanković et al., 2016). Finite-time performance guarantees for distributed RL. have also been provided in works, most notably in Doan et al. (2019; 2021); Wang et al. (2020); Zhang et al. (2021); Sun et al. (2020); Zeng et al. (2020).
The assumption that is the central concern of this paper and is made in all the existing finite-time analyses for distributed RL algorithms is that the consensus interaction is characterized by doubly stochastic matrices (Doan et al., 2019; 2021; Wang et al., 2020; Zhang et al., 2021; Sun et al.. 2020; Zeng et al., 2020) at every time step, at least in expectation, i.c.. W1 1 and 1 E(W) = 1 (Bianchi et al., 2013). Intuitively, doubly stochastic matrices imply symmetry in the communica- tion graph, which almost always requires bidirectional communication graphs. More formally, the assumption of doubly stochastic matrices is restrictive since distributed construction of doubly stochastic matrix needs to either invoke algorithms such as the Metropolis algorithm (Xiao et al., 2005) which requires bi-directional communication of each agent's 's degree information; or to utilize an additional distributed algorithm (Gharesifard & Cortés, 2012) which significantly increases the complexity of the whole algorithm design. Doubly stochastic matrices in expectation can be guar- anteed via so-called broadcast gossip algorithms which still requires bi-directional communication for convergence (Bianchi et al., 2013). In realistic network, especially with mobile agents such as autonomous vehicles, drones, or robots, miidiircctioall communication is inevitable due to var- ious reasons such asymmetric communication and privacy constraints, non-zero communication failure probability between any two agents at any given time, and application of resilient consen- sus in the presence of adversary attacks (Vaidya et al., 2012; LeBlanc et al., 2013), all leading to an interaction among the agents characterized by a stochastic matrix, which may further be time- varying. The problem of design of distributed RL algorithms with time-varying stochastic matrices and characterizing either their asymptotic convergence or finite time analysis remains open.
As a step towards solving this problem, we propose a novel distributed stochastic approximation algorithm and provide its convergence analyses when a time-dependent stochastic matrix is being used due to uni-directional communication in a dynamic network. One of the first guarantees to be lost as the assumption of doubly stochastic matrices is removed is that the algorithm converges to a "policy" that maximizes the sum of reward functions of all the agents. Instead, the convergence is to set of policies that optimize a convex combination of the network-wise accumulative reward, with the exact combination depending on the limit product of the infinite sequence of stochastic matrices. Nonetheless, by defining the error as the deviation of the output of the algorithm from the eventual equilibrium point, we derive finite-time bounds on the mean-square error. We consider both the cases with constant and varying step sizes. In the important special case where the goal is to optimize the average of the individual accumulative rewards of all the agents, we provide distributed stochastic approximation algorithm, which builds the push-sum idea (Kempe al., 2003) that has been used to solve distributed averaging problem over strongly connected graphs, and characterize its finite-time performance. Thus, this paper provides the first distributed algorithm that can be applied (e.g., in Temporal difference (TD) learning, see Appendix D) to converge to the policy maximizing the team objective of the sum of the individual utility functions over marying uni- directional, communication graphs, and characterizes the finite-time bounds on the mean mean-square error of the algorithm output from the equilibrium point under appropriate assumptions.
Technical Innovation and Contributions There are two main technical challenges in removing the assumption of doubly stochastic matrices being used in the analysis of distributed stochastic approximation algorithms. The first is in the direction of finite-time analysis. For distributed RL al- gorithms, finite-time performance analysis essentially boils down to two parts, namely bounding the consensus error and bounding the "single-agent" meaa-square error. For the case when consensus
2

---

Under review as a conference paper at ICLR 2022
interaction matrices are all doubly stochastic, the consensus error bound can be derived by analyzing the square of the 2-norm of the deviation of the current state of each agent from the average of the states of the agents. With consensus in the presence of doubly stochastic matrices, the average of the states of the agents remains invariant. Thus, it is possible to treat the average value as the state of a fictitious agent to derive the mean-square consensus error bound with respect to the limiting point. More formally, this process relies on two properties of a doubly stochastic matrix W, namely that (I) 1 1 W where 02 (W) denotes the second largest singular value of W (which is strictly less than one if W is irreducible). Even if the doubly stochastic matrix is time-vare varying (denoted by Wt), property (1) still holds and property (2) can be generalized as in Nedić et al. (2018). 8). Thus, the square of the 2-norm ||,; - (1 Ø/) 11 is a quadratic Lyapunov function for the average consensus processes. Doubly stochastic matrices in expectation can be treated in the same way by looking at the expectation. This is the core on which all the existing finite-time analyses of distributed RL algorithms are based.
1", and (2) if 1 = Wz,, then || (1 1 S 02 [2(WW]]= - (1 xz 1
However, if each consensus interaction matrix is stochastic, and not necessarily doubly stochastic, the above two properties may not hold. In fact, it is well known that quadratic Lyapunov functions for general consensus processes Iz-1 SyTa, with St being stochastic, do not exist (Olshevsky & Tsitsiklis, 2008). This breaks down all the existing analyses and provides the first technical challenge that tackle in this paper. Specifically, we appeal to the idea of quadratic comparison functions for general consensus processes. This was first proposed in Touri (2012) and makes use of the concept of "absolute probability sequences". We provide a general analysis methodology and re- sults that subsume the existing finite-time analyses for single- single-timescale distributed linear stochastic approximation and TD learning as special cases (see Appendix D).
The second technical challenge arises from the fact that with stochastic matrices, the distributed RL algorithms may not converge to the policies that maximize the average of the utility functions of the agents. To regain this property, we propose a new algorithm that utilizes push-sum protocol for consensus. However, finite-time analysis for such a push-based distributed algorithm is chal- lenging. Almost all, if not all, the existing push-based distributed optimization works build on the analysis in Nedić & Olshevsky (2014); however, that analysis assumes that a convex combination of the entire history of the states of each agent (and not merely the current state of the agent) is being calculated. This assumption no longer holds in our case. To obtain a direct finite-time error bound without this assumption, we propose a new approach to analyze our push-based distributed algorithm by leveraging our consensus-bad based analyses to establish direct finite-time error bounds for stochastic approximation. Specifically, we tailor "absolute probability sequence" for the push- based stochastic approximation algorithm and exploit its properties. Such properties have never been found in the existing literature and may be of independent interest for analyzing any push-sum based distributed algorithm.
We now list the main contributions of our work. We propose novel consensus-based distributed linear stochastic approximation algorithm driven by Markovian noise in which each agent evolves according to its local stochastic approximation process and the information from its neighbors. We assume only a (possibly time-varying) stochastic matrix being used during the consensus phase, which a more practical assumption when only unidirectional communication is possible among agents. We establish both convergence guarantees and finite-time bounds on the mean-square error, defined as the deviation of the output of the algorithm from the unique equilibrium point of the associated ordinary differential equation. The equilibrium point can be an "uncontrollable" convex combination of the local equilibria of all the agents in the absence of communication. We consider both the cases of constant and fime-iarying step-sizes. Our results subsume the existing results on convergence and finite-time analysis of distributed RL algorithms that assume doubly stochastic ma- trices and bi-directional communication as special cases. In the case when the convex combination is required to be straight average and interaction between any pair of neighboring agents may be uni uni-directional, we propose a push-type distributed stochastic approximation algorithm and estab- lish its unite-time performance bound. It is worth emphasizing that it is straightforward to extend our algorithm from the straight average point to any pre-specified convex combination. Since is well known that TD algorithms can be viewed as a special case of linear stochastic approximation (Tsitsiklis & Roy, 1997). our distributed linear stochastic approximation algorithms and their finite- time bounds can be applied to TD algorithms in straight-forward manner; (see distributed TD(A) in Appendix D).
3

---

Under review as a conference paper at ICLR 2022
Notation We use X, to represent that variable X is time-dependent and t 1..1.2.... is the discrete time index. The ith entry of a vector I will be denoted by x' and, also, by (x))* when convenient. The ijth entry of a matrix A will be denoted by a and, also, by (A)'5 when convenient. We use In to denote the vectors in Rn whose entries all equal to 1's, and / to denote the identity matrix, whose dimension is to be understood from the context. Given set S with finitely many elements, we use |S] to denote the cardinality of S. We use [-] to denote the ceiling function.
A vector is called a stochastic vector if its entries are nonnegative and sum one. A square non- negative matrix is called row stochastic matrix, or simply stochastic matrix, if its row sums all equal one. Similarly, a square nonnegative matrix is called column stochastic matrix if its column sums all equal one. A square nonnegative matrix is called a doubly stochastic matrix if its row sums and column sums all equal one. The graph of an n X n matrix is a direct graph with n vertices and directed edge from vertex to vertex j whenever the ji-th entry of the matrix is nonzero. A directed graph is strongly connected if it has a directed path from any vertex to any other vertex. For strongly connected graph G, the distance from vertex i to another vertex j is the length of the shortest directed path from to j: the longest distance among all ordered pairs of distinct vertices i and in G is called the diameter of G. The union of two directed graphs, Gp and Gg. with the same vertex set, written Gp U G.. is meant the directed graph with the same vertex set and edge set being the union of the edge set of G, and Gg. Since this union is commutative and associative binary operation, the definition extends unambiguously to any finite sequence of directed graphs.
DISTRIBUTED LINEAR STOCHASTIC APPROXIMATION
Consider a network consisting of N agents. For the purpose of presentation, we label the agents from 1 through N. The agents are not aware of such a global labeling, but can differentiate between their neighbors. The neighbor relations among the N agents are characterized by a time-dependent directed graph G. (V, &,) whose vertices correspond to agents and whose directed edges (or ares) depict neighbor relations, where V = (I,...,' N is the vertex set and & = V x V is the edge set at time Specifically, agent j is an ne-nneihbor of agent agent & is an out- out-neighbor of agent i at time t if (i. k) E & Each agent can send information to its out-neighbors and receive information from its in-neighbors. Thus, the directions of edges represent the directions of information flow. For convenience, we assume that each agent is always an in- and out-neighbor of itself, which implics that G, has self-ares at all vertices for all time t. We use Ng and N to denote the in- and out neighbor set of agent i at time t, respectively, i.e.
time t if (j. E,, and similarly,
Nº = {1 E EV: (i E &,), Ni- = (k E V : kt, E E,).
It is clear that N² and M7- are nonempty as they both contain index i.
We propose the following distributed linear stochastic approximation over a time-varying neighbor graph sequence (G+}. Each agent has control over a random vector 0j which is updated by
0
Σ JENT
oe + az (A(x)) JENT
Σ
0 +
i EV EE 1,,, J.. (1)
where w/ are consensus weights, Oi the step-size at time 1, A(X,) a random matrix and b (X₂) is a random vector, both generated based on the Markov chain {X,} with state spaces X. It worth noting that the update of each agent only uses its in neighbors' information and thus is distributed.
Remark 1 The work of Kushner & Yin (1987) considers different consensus-based networked linear stochastic approximation as follows:
0 0
Σ w of as b(())) iEV, tE 10.
+
JENT
whose state form is O+41= (( weakly convergence for the fixed step-size case (i.e., 04 a for all t). Under the similar set of conditions, with its condition (C3.4") ) being a stochastic analogy for Assumption 6, Theorem 1 in Kushner & Yin (1987) shows that equation 2 has a limit which can be verified to be the same as 0*, the limit of equation I. How to apply the finite-time analysis tools in this paper to equation 2 has so far eluded us. The two updates equation I and equation 2 analogous to the "combine-tte adapt" and "adapt-ther then combenee diffusion strategies in distributed optimization (Chen & Sayed, 2012).
and mainly focuses on asymptotically
4

---

Under review as a conference paper at ICLR 2022
We impose the following assumption the weights w which has been widely adopted in consen- sus literature (Jadbabaie et al., 2003; Olfati-Satee Saati-Sabrree et al., 2007; Nedić & Liu, 2017).
Assumption There exists constant 3 > such that for all i,j V and w B whenever j E NY. For all i and I, EjENt w
Let W, be the N x N matrix whose ijth entry equals wi j E Ni and zero otherwise. From Assumption 1, each W, is a stochastic matrix that compliant with the neighbor graph Gr. Since each agent is always assumed to be an in in-ncighbor of itself, all diagonal entries of W are positive. Thus, G2 is strongly connected, W; is irreducible and aperiodic. To proceed, define
(0!)T
(b'(X.))
O.
B(X))
(
(b (X)))
Then, the N linear stochastic recursions in equation can be combined and written as
2+1 W,O, + a,,,,,AAX)) a(X,)),, E 10,112....
The goal of this section is to characterize the finite-time performance of equation 1, equíva- lently equation 3, with the following standard assumptions, which were adopted e.g. in Srikant & Ying (2019); Doan et al. (2019).
Assumption 2 There exists matrix A and vectors b', e V, such that
lim E[A(X.)) = A, lim (X.) = b4, i V. t+
Define Umax maxiev supzex [bb(z))l2 < oo and Amax = supzex ||(x))l2 oo. Then, ||All2 S Amax and [|6'| 2 S m V.
Assumption Given a positive constant a, we use r(a) to denote the mixing time of the Markov chain {X,} for which
[E[A(X)) A|X, x]1l2 a, AX, Vt 1+21 =2T(),,
( = x]]l2 aa VX, 22 T(a),,, ViEV.
The Markov chain {Xi} mixes at geometric rate, i.e., there exists a constant C' such that Taa) S -C log a.
Assumption All eigenvalues of A have strictly negative real parts, i.e. A is a Hurwitz matrix. Then, there exists symmetric positive definite matrix P, such that A + PA -I. Let Nmax and Tinin be the maximum and minimum eigenvalues of P, respectively.
Assumption 5 The step-size sequence {ar} is positive, non-increasing, and satisfies Er ar = and Dre a < co.
To state our first main result, we need the following concepts.
Definition 1 A graph sequence {G,} is uniformly strongly connected if there exists positive integer L such that for any 2 O, the union graph U U Gy. is strongly connected. sfch an integer exists, we sometimes say that {G.) is uniformly strongly connected by sub-sequences of length L.
Remark Two popular joint connectivity definitions in consensus literature are "B-connected" (Nedić al., 2009) and "repeatedly jointly strongly connected" (Cao et al., 2008). A graph sequence {G,} is B-connected if there exists positive integer B such that the union graph U (k+1)B-1 G, is strongly connected for each integer 2 O. Although the uniformly strongly nectedness looks more restrictive compared with B-connectedness at first glance, they are in fact equivalent. To this, first it is easy see that (Gt) is uniformly strongly connected, (G+) must
5

---

Under review as a conference paper at ICLR 2022
be B-connected; now supposing {Gr) is B-connected, for any fix the union graph Uk=t Gk must be strongly connected, and thus {Gr} is uniformly strongly connected by sub-sequences of length 2B. Thus, the two definitions are equivalent. It is also not hard to show that the uniformly strongly connectedness is equivalent to "repeatedly jointly strongly connectedness" provided the graphs under consideration all have self-ares at all verfices, as "repeatedly jointly strongly con- nectedness" is defined upon "graph composition".
Definition 2 Let {W, be a sequence of stochastic matrices. A sequence of stochastic vectors { an absolute probability sequence for [W, if ni W, for all t 0.
This definition was first introduced by Kolmogorov (Kolmogoroff, 1936). It was shown by Black- well (Blackwell, 1945) that every sequence of stochastic matrices has an absolute probability se- quence. In general, a sequence of stochastic matrices may have more than one absolute probability sequence; when the sequence of stochastic matrices is "ergodic", it has a unique absolute probability sequence (Nedić & Liu, 2017). It is easy to see that when W, a fixed irreducible stochastic matrix W, ne is simply the normalized left eigenvector of W for eigenvalue one. More can be said.
Lemma 1 Suppose that Assumption I holds. If {Gr} } is uniformly strongly connected, then there exists a unique absolute probability sequence {me} for the matrix sequence [Wa} and constant Tmin (0, 1) such that xं Tmin for all i and
Let (0), = Dim zi0i. which is a column vector and convex combination of all 0j. It is easy to see that (0), = (T, 01)T T.TT. ne. From Definition 2 and equation 3, we have 44 9441 -H_ W,O; + 0+ W.O,A(X,)) I(X,) B(X.) = म.. O2 + + O,A(X.) + +0,T,1 B B(X.), which implies that
(0)+1 = (0), + A(x) + (X.) 4++1- Tt+1
Asympiotic performance of equation with any uniformly strongly connected neighbor graph quence characterized by the following two theorems.
Theorem Suppose that Assumptions 1, 2 and 5 hold. Lei {0:), i E V, generated by equation 1. If (Gi) is uniformly strongly connected, then lim;-+oc 110 (0) ll 0 for all i V.
Theorem I only shows that all the sequences {0)), V, generated by equation 1 will finally reach a consensus, but not necessarily convergent or bounded. To guarantee the convergence of the sequences, we further need the following assumption, whose validity is discussed in Remark 3.
Assumption 6
The absolute probability sequence { for the stochastic matrix sequence {W.)
has a limit, i.e., there exists a stochastic vector π such that lim, N. Tec-
Theorem Suppose that Assumptions 1-6 hold. Let {0:}, E V, be generated by equation I and O be the unique equilibrium point of the ODE
Ô = A0 b. b
Σ b
(5)
where A and b' are defined in Assumption and Too defined in Assumption If (Gr) is uniformly strongly connected, then all 0ं will converge to 6* both with probability 1 and in mean square.
Remark 3 Though Assumption 6 may look restrictive at first glance, simple simulations show that the sequences {0:]. i E V. do not converge if the assumption does not hold. It is worth empha- sizing that the existence of woo does not imply the existence of lim W., though the converse true. Indeed, the assumption subsumes various cases including (a) all W, are doubly stochastic matrices, and (b) all W, share the same left eigenvector for eigenvalue 1, which may arise from the scenario when the number of in-neighbors of each agent does not change over time (Olshevsky & Tsitsiklis. 2013). An important implication of Assumption 6 is when the consensus interaction among the agents, characterized by {We). is replaced by resilient consensus algorithms such as Vaidya al. (2012); LeBlanc et al. (2013) in order to attenuate the effect of unknown malicious

---

Under review as a conference paper at ICLR 2022
agents, the resulting dynamics of non-malicious agents, in general, will not converge, because the resulting interaction stochastic matrices among the non-malicious agents depend on the state val- ues transmitted by the malicious agents, which can be arbitrary, and thus the resulting stochastic matrix sequence, in general, does not have a convergeni absolute probability sequence; of course, in this case, the trajectories of all the non-malicious agents will still reach consensus long as the step-size is diminishing, as implied by Theorem 1. Further discussion on Assumption 6 can be found in Appendix C.
U
We now study the finite-time performance of the proposed distributed linear stochastic approxi- mation equation for both fixed and time-varying step-size cases. Its finite-time performance is characterized by the following theorem.
Let 1/+ || 222 for all t 2 O. From Assumption 6, t) converges to zero as t -> Do.
Theorem 3 Let the sequences {0)}, i E V, be generated by equation I. Suppose that Assump- tions 1-4, 6 hold and {Gr] uniformly strongly connected by sub-sequences of length L. Let qe and my be the unique integer quotient and remainder of t divided by L, respectively, Let 8g be the diameter of U u Gk. 6max= maX120 8r, and
c= -1+ 2bmax
m2ing32
2bmax (1 + am
+ Amax)
(6)
Amax
26max
Amax
where O < a < min(Kn, Amax)(a)
1og2
0.1
K27mmax
1) Fixed step-size: Let for all t 2 O. For all t 2 Ti.
N
E
0
1-
0r
<
2t
N
Time
E
||00 - (00mme + C1
0.9cx
t-T
+ C2
7max
i=1
Ymax
20rC
t-
Σ
1/++ (1
0.9a
Ymin
Vmmx
2) Time-varying step-size: Let 04
an b+1
with ag
Tmaas 0.9
For all t > LT2.
N
N
E 110 0r [12] S 26 26 T2
TTo+ +m
E
[10 - (0) (0)) 112]
+ C3 (ave " + amma +
1 7 Ca log"
(L (00)
Σ 1/ + C6).
+ C3
(8)
I I.T
Here T2, K1, K2, C1 - C6 are finite constants whose definitions are given in Appendix A.I.
Since oi is uniformly bounded below by Tinn E 1) from Lemma it is easy to that the above bound holds for each individual Bi[l0; - 0* To better understand the theorem, we provide the following remark.
Temax lie the interval (0, 1). It is easy to show that e monotonically increasing for 6max and L, monotonically decreasing for 3 and
Remark In Appendix E.2.1, we show that both e and (1 0.9a.
Twin- Also, lim Σt-T Mh+1=x(1-
0.9c y* < liim Junns [M - + m: 0.9g 1-77
"maax
0.90
Yanax
Therefore, the summands in the finite-time bound equation for the fixed step-size case are exponentially decaying except for the constant Cz, which implies that lim supt DN11 n. E
0" [2] S Cz. providing a constant limiting bound. From Appendix A, C2 is monotonically increasing for Tmnax Smax, bmax and L, and monotonically decreasing, for Tiiiny Emin and B3. In Appendix F.2.2, we show that lim i Ei πi O, which implies that the finite-time time bound equation 8 for the time- varying step-size case converges to zero as t - cc. We next comment on 0.1 the inequality defining a. Actually, we can replace 0.1 with any constant E (0, which will affect the value of log
and the feasible set of a. with the latter becoming 0 < minn (1, (a))
Kr }. Thus,
7

---

Under review as a conference paper at ICLR 2022
the smaller the value of is, the smaller is the feasible set of a, though the feasible set is always nonempty. For convenience, we simply pick c 0.1 in this paper; that is why we also have 0.9 in equation 7. Lastly, we comment on ag in the time-varying step-size case. We set an 2mas for the
purpose of getting a cleaner expression of the finite-time bound. For Og < Tumas, our approach still
0.9 works, but will yield a more complicated expression. The same is true for Theorem 5.
M
Technical Challenge and Proof Sketch As described in the introduction, the key challenge of analyzing the finite-time performance of the distributed stochastic approximation equation I lies in the condition that the consensus-based interaction matrix is time-varying and stochastic (not necessarily doubly stochastic). To tackle this, we appeal to the absolute probability sequence T, of the time-varying varying interaction matrix sequence and introduce the quadratic Lyapunov com- parison function Σ Ell0 0 (1]. Then, using the inequality Σ क5. E 0; 0- I
2 ii El]0; - ( + 20(1 0'] the next step is to find the finite-time bounds of TH E - (0), [1 and Elll (0) 0" [|2], respectively. The latter term is essentially the "single- agent" mean-square error. Our main analysis contribution here is to bound the former term for both fixed and time-varying step-size cases.
EE
3 PUSH-SA
The preceding section shows that the limiting state of consensus-based distributed stochastic approx- imation depends on Too. which leads to a convex combination of the local equilibria of all the agents in the absence of communication, but the convex combination is in general "uncontrollable" Note that this convex combination will correspond to a convex combination of the network- accumu- lative rewards in applications such as distributed TD learning. an important case when the convex combination is desired to be the straight average, the existing literature e.g. Doan et al. (2019; 2021) relies on doubly stochastic matrices whose corresponding Tep = (1/N)1N. As mentioned in the introduction, doubly stochastic matrices implicitly require bi-directional communication between any pair of neighboring agents; see e.g. gossiping (Boyd et al., 2006) and the Metropolis algo- rithm (Xiao et al., 2005). A popular method to achieve the straight average target while allowing uni-directional communication between neighhoring agents is to appeal to the idea so-called "push- sum" (Kempe al., 2003), which was tailored for solving the distributed averaging problem over directed graphs and has been applied to distributed optimization (Nedić & Olshevsky, 2014). In this section, we will propose push-based distributed stochastic approximation algorithm tailored for uni-directional communication and establish its finite-time error bound.
Each agent has control over three variables, namely vi- 9: and 0i, in which z/ is scalar-valued with initial value 1, of can be arbitrarily initialized, and Oj = 0z- At each time t 2 0, each agent i sends its weighted current values a²f yt and w/ (0) + A(X,)) + axb'(X,)) to each of its current out- neighbors j e N₁ and updates its variables as follows:
Vi+ = Σ
vó 1,
SEAT
0 = E w
0 + ai ( +x(x))
+
(9)
JEN
0if1
0
8 = 0%.
vi41
where vi agent be aware of the number of its nut-neigh
1- It is worth noting that the algorithm is distributed yet requires that each
Asymptotic performance of equation 9 with any uniformly strongly connected neighbor graph se- quence is characterized by the following theorem.
Theorem 4 Suppose that Assumptions 2-5 hold. Let (0)), E V, be generated by equation 9 and O be the unique equilibrium point of the ODE
1
0 A0 +
bi
(10)
N
i=1
8

---

Under review as a conference paper at ICLR 2022
where A and b' are defined in Assumption 2. If {Gt} } is uniformly strongly connected, then 8j will converge to 8" in mean square for all i E V.
In this section, we define (0), = Σ and (0), = Ei 0j To help understand these definitions, let W, be the N x N matrix whose ij-th entry equals wi if j E .Ni otherwise equals zero. It is easy to that each W. is a column stochastic matrix whose diagonal entries are all positive. Then, Te = N ly for all t 2 can be regarded as an absolute probability sequence of (W.). Thus, the above two definitions are intuitively consistent with (0), in the previous section.
Finite-time performance of equation 9 with any uniformly strongly connected neighbor graph se- quence characterized by the following theorem.
Let μ4 [IA(X)) as + 0o, 80 does 14-
(0) In Appendix E.3, we show that (0), x0) converges to zero
Theorem 5 Suppose that Assumptions 2-4 hold and {G,} is uniformly strongly connected by sub-
sequences of length L. Let {0;}. E V, be generated by equation with a₁ = I and ag 2 Imas Then, there exists nonnegative I (1 w &. such that for all t T.
0.9
||0e
0/11]] s Crt + Cs (avet + tars)) + Coat
E
+ 1 (Cio log? (
+C (w))
(II)
k=T
where T and C7 - C12 are finite constants whose definitions are given in Appendix A.2.
In Appendix E.3, we show that lim Ek_ Me O which implies that the finite-time bound equation 11 converges to zero as t + It is worth mentioning that the theorem does not consider the fixed step-size case, as our current analysis approach cannot be directly applied for this case.
Proof Sketch and Technical Challenge Using the inequality E
2 N of Theorem 3, the derivation is quite different. First, the iteration of (0), is single-agent SA plus disturbance term (0), (0),. so we cannot directly apply the existing single-agent SA finite- time analyses to bound [I) - [12): instead, we have to show that (0), (0); will diminish and quantify the diminishing "speed". Second, both the proof showing diminishing (0), (0), and derivation of bounding Σ Elll0++ - e0) involve key challenge: to prove the sequence {0)) generated from the Push-SA SA equation 9 is bounded almost surely. To tackle this, we introduce novel way to constructing an absolute probability sequence for the Push-SA as follows. From equa- tion 9, 0++1 Σラ=
El 10) ()), 01)))). our goal is derive the finite-time bounds of E 01 11) and E[I(()), - respectivvy Although this looks similar to the proof
N
i wh [o] + A(x,) o1 + az vi
('(x)), where w. _i (w)) (/ V with vtt)) )-
We show that each matrix W. = [ is stochastic, and there exists a unique absolute probability sequence } for the matrix sequence (W:) such that #े 2 *min for all i E V and 2 O, with the constant 7min E (0, 1). Most importantly, we show two critical properties of (W,) and (#x). namely lim been reported in the literature though push-sum based algorithms have been extensively studied.
) = N IN and # Mi n for all i, E V and t 2 0, which have never
4 CONCLUDING REMARKS
In this paper, we have established both asymptotic and non-asymptotic analyses for consensus- based distributed linear stochastic approximation algorithm over uniformly strongly connected graphs, and proposed push-based variant for coping with uni-directional communication. Both algorithms and their analyses can be directly applied to TD learning. One limitation of our finite- time bounds is that they involve quite few constants which are well defined and characterized but whose values are not easy to compute. Future directions include leveraging the analyses for resilience in the presence of malicious agents and extending the tools more complicated RI..

---

Under review as a conference paper at ICLR 2022
REFERENCES
Bianchi, G. Fort, and W. Hachem. Performance of a distributed stochastic approximation algo- rithm. IEEE Transactions on Information Theory, 59(11::705--7118 2013.
D. Blackwell. Finite non-homogeneous chains. Annals of Mathematics, 46(4):594-599, 1945.
S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6))2508-255) 25300, 2006.
M. Cao, A. S. Morse, and B. D. O. Anderson. Reaching a consensus in a dynamically changing environment: graphical approach. SIAM Journal on Control and Opfimization, 47(2):575-600 2008.
J. Chen and A. H. Sayed. Diffusion adaptation strategies for distributed optimization and learning networks. IEEE Transactions Signal Processing, 60(8):4289-4305, 2012.
T.T. Doan, S.T. Maguluri, and J. Romberg. Finite-time analysis of distributed TD(0) with linear function approximation on multi-agent reinforcement learning. In 36th International Conference on Machine Learning, pp. 1626-1635, 2019.
T.T. Doan, S. T. Maguluri, and J. Romberg. Finite-time performance of distributed temporal- difference learning with linear function approximation. SIAM Journal on Mathematics of Data Science, 3(1):298-320, 2021.
B. Gharesifard and J. Cortés. Distributed strategies for generating weight-balanced and doubly stochastic digraphs. European Journal of Control, 18(6)553--557, 2012.
M. Huang. Stochastic approximation for consensus: new approach via ergodic backward products. IEEE Transactions Aulomatic Control, 57(12):2994-3008 2012.
A. Jadbabaie, J. Lin, and A. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6);988-101, 2003.
D. Kempe, A. Dobra, and J. Gehrke. Gossip-hased computation of aggregate information. 44th IEEE Symposium on Foundations of Computer Science, pp. 482-491, 2003.
A. Kolmogoroff. Zur theorie der markoffschen ketten. Mathematische Annalen, 12(1):155-160. 1936.
H.J. Kushner and G. Yin. Asymptotic properties of distributed and communicating stochastic ap- proximation algorithms. SIAM Journal Control and Optimization, 25(5): 1987.
H.J. LeBlane, H. Zhang, X. Koutsoukos, and S. Sundaram. Resilient asymptotic consensus networks. IEEE Journal on Selected Areas in Communications, 31(4)766-781,
consenuus in robust
A. Nedić and J. Liu. On convergence rate of weighteddaaveragnng dynamics for consensus problems. IEEE Transactions Automatic Control, 62(2):766-781, 2017.
A. Nedić and A. Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60(3):601-615, 2014.
A. Nedić, A. Olshevsky, A. Ozdaglar, and N. Tsitsiklis. On distributed averaging algorithms and quantization effects. IEEE Transactions automatic control, 54(11):2506-2517 2009.
A. Nedié, A. Olshevsky, and M. G. Rabbat. Network topology and communication-compuaaaa tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-97,. 2018.
R. Olfati-Saber, A. Fax, and R. M. Murray. Consensus and cooperation in networked multi-agent systems. Proc. IEEE, 9551):2 2007.
A. Olshevsky and J. N. Tsitsiklis. On the nonexistence of quadratic Iyapunov functions for consensus algorithms. JEEE Transactions on Automatic Control, 53(11):2622-2655 2008.
A. Olshevsky and J. N. Tsitsiklis. Degree fluctuations and the convergence time of consensus algo- rithms. IEEE Transactions Automatic Control, 58(10)2266-2631, 2013.
10

---

Under review as a conference paper at ICLR 2022
R. Srikant and L. Ying. Finite-time enror bounds for linear stochastic approximation and TD learn- ing. In 32nd Conference on Learning Theory, volume 99, pp. 2803 2803-2830. 2830. Proceedings of Machine Learning Research, 25-28 Jun 2019.
M. S. Stanković, N. Ilié, and S. S. Stanković. Distributed stochastic approximation: weak conver- gence and network design. IEEE Transactions on Automatic Control, 61(12):40694400 2016.
M.S. Stanković and S.S. Stanković. Multi-agent temporal-differee learning with linear function approximation: Weak convergence under time-varying network topologies. In American Control Conference, pp. 167-172, 2016.
S. Stanković, M. S. Stanković, and D. Stipanović. Decentralized parameter estimation by consen- based stochastic approximation. IEEE Transactions Automatic Control, 56(3):531-543, 2010.
Sun, G. Wang. G. B. Giannakis, Q. Yang, and Z. Yang. Finite-time analysis of decentralized remporal-difference learning with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 4485-4492 PMLR, 2020.
W. Suttle, Z. Yang, K. Zhang, Z. Wang. T. Başar, and Liu. A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning. In 21 IFAC World Congress, 2020.
R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. 1998.
Cambridge: MIT press,
B. Touri. Product of Random Stochastic Matrices and Distributed Averaging. Springer Science & Business Media, 2012.
J. N. Tsitsiklis. Problems in Decentralized Decision Making and Computation. PhD thesis, Depart- ment of Electrical Engineering and Computer Science, MIT, 1984.
J.N. Tsitsiklis and B. Van Roy. An analysis of cemporal-differeme learning with function approxi- mation. IEEE Transactions Automatic Control, 42(5):674-69) 1997.
N. H. Vaidya, L. Tseng, and G. Liang. Iterative approximate byzantine consensus in arbitrary di- rected graphs. In Proceedings of the 2012 ACM symposium on Principles of distributed comput- ing, pp. 365-374, 2012.
G. Wang. S. Lu, G. Giannakis, G. Tesauro, and J. Sun. Decentralized TD tracking with linear function approximation and its finite-time analysis. In 34th Conference on Neural Information Processing Systems, 2020.
L. Xiao, S. Boyd, and S. Lall. A scheme for robust distributed sensor fusion based average consensus. In Proceedings of the 4th International Conference on Information Processing in Sensor Networks, pp. 63-70, 2005.
S. Zeng. T.T. Doan, and J. Romberg. Finite-time analysis of decentralized stochastic approximation with applications in multi-agent and multi-tast learning. arXiv preprint arXiv:2010. /5088, 2020.
K. Zhang, Z. Yang, and T. Başar. Networked multi-agent reinforcement learning in continuous spaces. In 57th IEEE Conference on Decision and Control, pp. 2771-2776, 2018a.
K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Başar. Fully decentralized multi-agent reinforcement learning with networked agents. In 35th International Conference on Machine Learning, pp- 5872-5881, 2018b.
K. Zhang, Z. Yang, and T. Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint arXiv:1911.10635, 2019.
K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Başar. Finite-sample analysis for decentralized batch multi-agent reinforcement learning with networked agents. IEEE Transactions Automatic Con- trol, 2021.
Y. Zhang and M.M. Zavlanos. Distributed off-policy actor-critic reinforcement learning with policy consensus. In 58th IEEE Conference Decision and Control, pp. 4674-4679, 2019.


Reviews:
[{"review_id": "rAewWd8SN2c", "reviewer": "Reviewer_5MZ3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nStrengths:\n- The authors propose a push-sum counterpart for the distributed linear stochastic approximation under time-varying directed networks.\n- 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.\n- The authors provide a detailed analysis in the appendix for both proposed algorithms.\n\nWeaknesses:\n- 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.\n- 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.\n- 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.\n- 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.\n- 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.\n- 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. \n- 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.\n- 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Xghi-gfqGZP", "reviewer": "Reviewer_HPzY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nQuality. The results are technically sound and theoretically supported. The algorithm proposed is fresh and new as well as interesting.\n\nClarity. The paper is well written and easy to follow. The results are nicely organized and the contributions relative to existing works are clear too.\n\nSignificance. 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_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.\n\n", "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.\n\n--------------\nAfter rebuttal: After reading the other reviews and authors response, I have updated my score. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "OLhEcHw5S-c", "reviewer": "Reviewer_RnJ8", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nFor 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.\n\nThis 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.\n\nThis 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.\n\nMy 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.\n\n- Is assumption 1 required to hold for any $X_t$?\n- 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. \n- the $\\forall X$ in Assumption 3 is unclear.\n- Which $A$ is used in assumption 3.\n- Which $A$ is used in assumption 4. Also assumption 4 has some discussion which is not part of the assumption.\n- The statement of Thm1 is not complete\n- 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?\n- What is the diameter of a graph in Thm 3.\n- why does $i$ not appear in the definition of $\\hat w_{t}^{ij}$\n- Typos: \"decaying expect for\" \"decreasing\" \"that consensus interaction\" \"cannot be directly apply\"\n\n", "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. ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "6OcJyhUJA0Y", "reviewer": "Reviewer_fcYJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n               Attacking a hard setting.\n\nWeakness:\n1. 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.\n\n2. 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.\n\n\n\nPossible Technical Issues: It will be great if the authors can clarify the following.\n\n* (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. \n\n\n\n*  (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$. \n\n$\\theta_{t+1}(1)=\\theta_t(1)-\\alpha_t\\gamma_{\\max}\\theta_t(1),$\n\n$\\theta_{t+1}(2)=\\theta_t(2)-\\alpha_t\\gamma_{\\min}\\theta_t(2),$\n\nLet us just look at $\\theta_{t+1}(2)$, \n\n$\\theta_{t+1}(2)=\\Pi_{k=0}^{t}\\left(1-\\frac{\\gamma_{\\min}\\alpha_0}{k+1}\\right) \\theta_{0}(2)$\n\n$|\\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})$\n\nNow 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$):\n\n$|\\theta_{t+1}(2)|\\geq e^{-2\\gamma_{\\min}\\alpha_0\\sum_{k=0}^{t}\\frac{1}{k+1} }$\n\n$=e^{-2\\gamma_{\\min}\\alpha_0}e^{-2\\gamma_{\\min}\\alpha_0\\sum_{k=1}^{t}\\frac{1}{k+1} }$\n\n$\\geq e^{-2\\gamma_{\\min}\\alpha_0}e^{-2\\gamma_{\\min}\\alpha_0\\ln(t) }$\n\n$= \\frac{e^{-2\\gamma_{\\min}\\alpha_0}}{t^{2\\gamma_{\\min}\\alpha_0} }$\n\nPicking $\\alpha_0= \\frac{\\gamma_{\\max}}{0.9}$, we have \n\n\n$|\\theta_{t+1}(2)| \\geq \\frac{e^{-2\\gamma_{\\min}\\alpha_0}}{t^{\\frac{2\\gamma_{\\min}\\gamma_{\\max}}{0.9}} }$\n\nWe 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.\n\n\n*  (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}$? \n\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "-WBCYDnB3ZE", "reviewer": "Reviewer_dShT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe 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. \n\nMy 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. \n\n\nMinor points: \n\n- terms such as “mean-square” and “mean squared” are used to denote the same notion. \n\n- p. 3: double stochastic matrix => doubly stochastic matrix \n", "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. ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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