Finite-Time Error Bounds for Distributed Linear Stochastic Approximation
Authors: Yixuan Lin
Ji Liu
Vijay Gupta
Venue: NeurIPS 2021 Submitted (2021)

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.

Fime Error Bounds for Distributed Linear Stochastic Approximation
Abstract
This paper considers 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 tame-narying directed graph. While the convergence of consensus-base stochastic approximation algorithms when the interconnection among the agents is described by doubly stochastic matrices (at least in expectation) has been studied, less 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 the mean-square error, defined 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 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.
2
4
6
10
12
14
15
16
17
18
19
20
21
Introduction
22
23
The use of reinforcement learning (RL) to obtain policies that describe solutions to a Markov decision process (MDP) in which an autonomous agent interacting with an unknown environment aims to optimize its long term reward is now standard [1]. Multi-agent or distributed reinforcement learning is useful when a team of agents interacts with an unknown environment or system and aims to collaboratively accomplish tasks involving distributed decision-making. Distributed here implies that agents exchange information only with their neighbors according to a certain communication graph. Recently, many distributed algorithms for multi-agent RI. have been proposed and analyzed [2]. The basic result in such works is of the type that if the graph describing the communication among
24
25
26
27
29
31 the agents is bi-directional (and hence can be represented by a doubly stochastic matrix), then an algorithm that builds traditional consensus algorithms converges 33 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 be characterized [3.4].
solution in terms of policies
35 This paper aims relax the assumption of requiring bi-directional communication among agents 36 in distributed RL algorithm. This assumption is arguably restrictive and will be violated due to
37 reasons such as packet drops or delays, differing privacy constraints among the agents, heterogeneous capabilities among the agents in which some agents may be able to communicate more often or with 39 more power than others, adversarial attacks, or even sophisticated resilient consensus algorithms being used to construct the distributed RL algorithm. A uni-directional communication graph can 41 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 of
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

43
doubly stochastic matrix to simply a stochastic matrix in the multi-agent and distributed 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 mean square error for a multi-agent linear stochastic approximation algorithm which the agents interact over a time-varying directed graph characterized by a stochastic matrix. This paper, thus, extends the applicability of distributed and multi-agent RL algorithms presented in the literature to situations such as those mentioned above where bidirectional 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.
44
45
46
47
48
49
50
51
52
Related Work A key tool used for designing and analyzing RL algorithms is stochastic approxima- tion [5], e.g., for policy evaluation, including temporal difference (TD) learning as a special case [6]. Convergence study of stochastic approximation based on ordinary differential equation (ODE) meth- ods has a long history [7]. Notable examples are [8,9] which prove asymptotic convergence of (D))). Recently, finite- time performance of single-agent stochastic approximation and TD algorithms has been studied in [10-18]; many other works have now appeared that perform finite-time analysis for other RL algorithms, see, e.g.. [19-28], just to name a few.
53
54
55
56
57
58
59
Many distributed and multi-agent reinforcement learning algorithms have now been proposed in the literature. In this setting, each agent can receive information only from its neighbors, and no single agent can solve the problem alone or by 'tuking 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 [29]. Many works have analyzed asymptotic convergence of such RI. algorithms using ODE methods [4, 30-32. This can be viewed as an application of ideas from distributed stochastic approximation [33-38]. Finite-time performance guarantees for distributed RL have also been provided in works, most notably in [3,39-43]
60
61
62
63
64
65
66
87
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 [3, 39-43] at every time step, or at least in expectation, i..., W1 = 1 and
68
69
70
1 1 E(W)= = 1 [37]. Intuitively. doubly stochastic matrices imply symmetry in the communication graph, which almost always requires bidirectional communication graphs. More formally, the assumption of doubly stochastic matrices is restrictive since distributed construction of a doubly stochastic matrix needs to either invoke algorithms such as the Metropolis algorithm [44] which requires bi-directional communication of each agent's degree information; or to utilize an additional distributed algorithm [45] which significantly increases the complexity of the whole algorithm design. Doubly stochastic matrices in expectation can be guaranteed via so-called broadcast gossip algorithms which still requires bi-directional communication for convergence [37]. In realistic network, especially with mobile agents such as autonomous vehicles, drones, or robots, uni-directional communication is inevitable due to various reasons such as asymmetric communication and privacy constraints, non-zero communication failure probability between any two agents at any given time, 81 and application of resilient consensus in the presence of adversary attacks [46, 47], all leading to
71
72
73
74
76
78
79
80
82 an interaction among the agents characterized by a stochastic matrix, which may further be time-
83 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.
84
85 As step towards solving this problem, we propose 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- 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 the mean squared error. We consider both the cases with constant and time-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 on the push-sum idea [48] 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 (c.g., in TD learning) to converge to the policy maximizing the team objective of the sum of the individual
86
87
88
89
90
91
92
98
34
95
96
97
98
99

---

100
utility functions over time-vary varying, uni-directional, communication graphs, and characterizes the finite-time bounds on the mean squared error of the algorithm output from the equilibrium point under appropriate assumptions.
101
102
103
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 algorithms, finite-time performance analysis essentially boils down to two parts, namely bounding the consensus error and bounding the "single-agent" meean-quare error. For the case when consensus 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 double stochastic matrix W, namely that
104
105
106
107
108
109
110
111
112
113
(I) 1 W = 1 and (2) if Iz+1 = Wz,, then || (1 2z+1)1l|2 S 02 (W)ll - (1 xz 1 where 0º (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-varying (denoted by Wo), property (1) still
115
116
holds and property (2) can be generalized as in [49]. Thus, the square of the 2-norm || - (1 xz 1 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.
117
119
120
121
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 T(+1 = S,z;, with S, being stochastic, do not exist [50]. This breaks down all the existing analyses and provides the first technical challenge that we tackle in this paper. Specifically, we appeal to the idea of quadratic comparison functions for general consensus processes. This was first proposed in [51] and makes use of the concept of "absolute probability sequences". We provide a general analysis methodology and results that subsume the existing finite-time analyses for songle-timeseen distributed linear stochastic approximation and TD learning as special cases.
122
123
125
126
127
128
129
The second technical challenge arises from the fact that with stochastic matrices, the distributed RI. 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 a push-sum protocol for consensus. However, finite-time analysis for such push-based distributed algorithm is challenging.
130
131
132
133
Almost all, if not all, the existing push-based distributed optimization works build on the analysis in [52]; 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 direct umite-time error bound without this assumption, propose a new approach to analyze our push-based distributed algorithm by leveraging our consensus- based analyses to establish direct finite-time error bounds for stochastic approximation. Specifically, we tailor an "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.
135
137
138
139
140
141
142
We now list the main contributions of our work. We propose a 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 is a more practical assumption when only unidirectional communication is possible among agents. We establish both convergence guarantees and unite-time bounds on the mean-squar error, defined 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 time-varying step-sizes. Our results subsume the existing results on convergence and finite-time analysis of distributed RL algorithms that assume doubly stochastic matrices and bi-directional communication as special cases. In the case when the convex combination is required be a straight average and interaction between any pair of neighboring agents may be uni- direccicli,,l,, we propose a push-type distributed stochastic approximation algorithm and establish its tnite-time performance bound. It worth emphasizing that it is straightforward to extend our
143
144
145
147
148
149
150
151
152
153
154
155
156
3

---

157
algorithm from the straight average point to any pre-specified convex combination. Since it is well known that TD algorithms can be viewed as a special case of linear stochastic approximation [8], our distributed linear stochastic approximation algorithms and their finite-time bounds can be applied to TD algorithms in a straight-forwant manner.
158
159
160
161
We use X₁ to represent that a variable X is time-dependent and t E 1, is the discrete time index. The ith entry of a vector will be denoted by x² and, also, by (ar) when convenient. The ijth entry of a matrix A will be denoted by a and, also, by (A) when convenient. We use 1 denote the vectors in IR" whose entries all equal to 1 's and I to denote the identity matrix, whose dimension is to be understood from the context. Given a set S with finitely many elements, we use [S] to denote the cardinality of S. We use [-] to denote the ceiling function.
Notation
162
163
184
185
186
167 A vector is called a stochastic vector if its entries are nonnegative and sum to one. A square nonnegative matrix is called a row stochastic matrix, or simply stochastic matrix, if its row sums all equal one. Similarly, a square nonnegative matrix is called a 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 matrix is a direct graph with n vertices and a 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 a strongly connected graph G. the distance from vertex i another vertex j the length of the shortest directed path from i to j; the longest distance among all ordered pairs of distinct vertices and in G is called the diameter of G. The union of two directed graphs, Gp and G.. with the same vertex set, written Gp U GG. is meant the directed graph with the same vertex set and edge set being the union of the edge set of Gp and Gy. Since this union is a commutative and associative binary operation, the definition extends unambiguously to any finite sequence of directed graphs with the same vertex set.
168
169
170
171
172
directed edge from vertex
173
174
175
178
177
178
179
2
Distributed Linear Stochastic Approximation
180
181
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 time-dependent directed graph G; (V,E,) whose vertices correspond to agents and whose directed edges (or arcs) depict neighbor relations, where V (1..... , N} is the vertex set and & = V x V is the edge set at time t. Specifically, agent j is an in neighbb of agent i at time if i) E &g, and similarly, agent is an out-neighbor of agent at time / (i, k)) E &s. Each agent can send information to its neighboss 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- neighbe of itself, which implies that G, has self-ares at all vertices for all time t. We use use N2 and Ng to denote the in- and out-neighbor set of agent at time t, respectively, i.e.
182
183
184
185
186
187
189
NO = e (i. E E,), N;- = (k V : (i,k) E E.).
192 It is clear that N2 and M nonempty as they both contain index i.
We propose the following distributed linear stochastic approximation over a time-varying neighbor 194 graph sequence (Gr). Each agent has control over a random vector 0j which is updated by
193
0i Σ wiio! + az (A(X.) Σ JENS
of + (x(x)) i V, tE 1, (1)
JENS
195
where w are consensus weights, Oi is the step-size at time 1, A(X.) is random matrix and (*()) 196 a random vector, both generated based on the Markov chain (X,) with state spaces X. It is worth
noting that the update of each agent only uses its in ieiieihbs information and thus is distributed.
198 Remark
The work of [33] considers a different consensus- based networked linear stochastic approximation follows:
0
Σ
w of + an (A(X.)0) + (X.)), EEV, EE 1,,
JEN
whose state form is 0++1 = W,O,+o, +a, B(X.), and mainly focuses on asymptotically weakly convergence for the fixed step-size case (i.e., as for all t). Under the similar set of
200

---

202
conditions, with its condition (C3.4') being a stochastic analogy for Assumption 6, Theorem 3.1 in [33] shows that (2) has a limit which can verified be the same 8*, the limit of (1). How to
203
apply the fime analysis tools in this paper to (2) has far eluded us. The two updates (1) and
(2) are analogous to the "combine-then adapt" and "adapt-ther thecup--tee-commine diffusion strategies in
205
distributed optimization [53].
We impose the following assumption on the weights w/y which has been widely adopted in consensus literature [54-50 56].
207
208
Assumption There exists constant 3 such that for all i,j V and w whenever j E Ni. For all i and i, EjeN; w.
210
Let W2 be the x N matrix whose ijth entry equals w j E N2 and zero otherwise. From Assumption 1, each W, is stochastic matrix that is compliant with the neighbor graph G. Since 213 each agent is always assumed to be an in-neighbor itself, all diagonal entries of W, are positive. Thus, if G, is strongly connected, W, is irreducible and aperiodic. To proceed, define
211
(0))T
(b) (b)(
O
B(X,)
(ON)
(6 (X))
215 Then, the N linear stochastic recursions in (1) can be combined and written as
0++1 W,O, + az a,W;0, + B(X,). LE 10.
(3)
The goal of this section is to characterize the finite-time performance of (1), equivalently (3), with the following standard assumptions, which were adopted e.g. in 13].
217
Assumption There exists a matrix A and vectors b", e V, such that
218
lim E[A(X,)] A, lim ((b'(x,)) b', ie V. t+000
219
Define bmax- = maxiev zup [bb(() < cp and Amax suPxEx ||A(x)]12 < co. Then, ||A]|2 S Amax and | 1max, i iE) V.
220
221
Assumption Given a positive constant a, we use r(a) to denote the mixing time of the Markov chain {X,} for which
[[[A(X)) - A|Xo X]ll2 S a, AX, Vt 2 r(a), (X, - 6' = x]lla a VX, Vt 2 r(a), ViEV.
The Markov chain {Xi} mixes at geometric rate, i.e., there exists constant C such that r(a) S C log a.
224
225
Assumption All eigenvalues of A have strictly negative real parts, i.e., A a Hurwitz matrix.
226
Then, there exists symmetric positive definite matrix P, such that A P + PA = -I. Let Tmax and Tmin be the maximum and minimum eigenvalues of P, respectively.
227
228
Assumption' The step-size sequence {ar} is positive, inniincreas,n, and satisfies Ee at = 00
and E of <<00 co.
To state first main result, we need the following concepts.
Definition 1 A graph sequence {G,} ) is uniformly strongly connected there exists positive integer L such that for any t ' 0. the union graph U!=I=1 Gy is strongly connected. such integer exists,
233 we sometimes say that (G.) is uniformly strongly connected by sub-sequences of length L.
234 Remark Two popular joint connectivity definitions consensus literature are "B-connected" [57] and "repeatedly jointly strongly connected" [58]. A graph sequence (Gt) is B-connected if there
5

---

exists positive inleger B such that the union gruph - G, is strongly connected for each integer & 2 O. Although the uniformly strongly connectedness looks more restrictive compared with B-connectedness at first glance, they are in fact equivalent. To see this, first it is easy to see that if } is uniformly strongly connected, {[rt} must be B-connected; now supposing {Gt} is B- connected, for any fix t, the union graph k=! Utt2B-1Gs G2 must be strongly connected, and thus (Ge) ) is uniformly strongly connected by sub- sequenceueee 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 vertices, as "repeatedly jointly strongly connectedness" is defined upon "graph composition". D
237
239
240
242
243
244
245
Definition2 Let (W,) be a sequence of stochastic matrices. A sequence of stochastic vectors (me) an absolute probability sequence for (W.) if x -. for all t 2 0.
246
This definition first introduced by Kolmogorov [59]. It was shown by Blackwell [60] that every sequence of stochastic matrices has an absolute probability sequence. 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 [56]. It is easy to see that when W, is fixed irreducible stochastic matrix W, T. is simply the normalized left eigenvector of W for eigenvalue one. More can be said.
248
250
252
253
Lemma Suppose that Assumption 1 holds. If {Gt} is uniformly strongly connected, then there exists unique absolute probability sequence { for the matrix sequence {W1} and constant Tmin E (0, 1) such that xj 2 Tmin for all i and t.
255
Let (0), Ei= n: which is column vector and convex combination of all 0j. It is easy to
that (0); (IT, O.) = =0,-n ne. From Definition 2 and (3), we have
ক O++1 - W,O, + W. + B(II) = प. θ + a,,, + +
258
which implies that
1 (0), + (0)+1=
Axxi + a(,) T1+1.
(4)
Asymptotic performance of (1) with any uniformly strongly connected neighbor graph sequence is characterized by the following two theorems.
280
261
Theorem Suppose that Assumptions 1, and hold. Let {0]). i V, be generated by (1), If (G,) is uniformly strongly connected, then lim; 110; (0)el12 = 0 for all i E V.
282
263
Theorem 1 only shows that all the sequences {0]). E V. generated by (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.
285
266
Assumption The absolute probability sequence { } for the stochastic matrix sequence {Wi} has limit, i.e., there exists a stochastic vector no such that lim Rt. Weo.
Theorem 2 Suppose that Assumptions 1-6 hold. Let (0:). i E V, be generated by (1) and O be the unique equilibrium point of the ODE
268
269
N
0 = A0 +b, b, b= Σ R
(5)
where A and b' are defined in Assumption 2 and To is defined in Assumption 6. If (G,} is uniformly 271 strongly connected, then all 6% will converge to 8* both with probability 1 and in mean square.
272 Remark Though Assumption 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 emphasizing that
274 the existence of Tho does not imply the existence of lim,,-oc W., though the converse is true. Indeed, the assumption subsumes various cases including (a) all We are doubly stochastic matrices, and (b)

---

278
all We share the same left eigenvector for eigenvalue 1, which may arise from the scenario when the number of neighbors of each agent does not change over time [.1]. An important implication of Assumption 6 is when the consensus interaction among the agents, characterized by [Wa), is replaced by resilient consensus algorithms such as [46,47] in order to attenuate the effect of unknown malicious 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 values transmitted by the malicious agents, which can be arbitrary. and thus the resulting stochastic matrix sequence, in general, does not have a convergent absolute probability sequence; of course, in this case, the trajectories of all the non-malicious agents will still reach consensus as long as the step-size is diminishing, as implied by Theorem 1.
277
279
281
285
285
286
We now study the finite-time performance of the proposed distributed linear stochastic approximation (1) for both fixed and time-varying step-size cases, Its finite-time performance is characterized by the following theorem.
287
288
289
Let 1/: = || - l2 for all 2 0. From Assumption 6, 7/. converges to zero as t + Dc.
290
Theorem Let the sequences {0]}, i V, be generated by (1). Suppose that Assumptions 1-4, hold and {Gr} is uniformly strongly connected by sub-sequences of length L. Let qt and me be the unique integer quotient and remainder of t divided by L, respectively. Let òg be the diameter of
281
292
= U GGk δmax= = maXx20 &c, and
293
2b mbmax Amax
T mmin 32L
2bmax (1 + OcAmax))
c=
(1+
(1 + amxx
(6)
28max
Amax
294
where 0 < a < min(K1, Amaa
log
K27tmax"
0.13
295 1) Fixed step-size: Let a4 = a for all t 2 For all t 2 Tí.
Gorallt:
Σ
N
E [10: - 0111]] s 20
E
[10m. - (0) (0)mil12) [[]] + Ci (1
0.9c Vmax
1-11
+ C2. (7)
m.
1=1
298 2) Time-varying step-size: Let at
On 1+1
with ap 2 Imax For all LT2,
N
N
E 110 0- [|]] I 26 To
Σ i=1
n T
E [110ETtmm - (0) 1.7a ml1]]
+ Css Yaue 2 + a + 1
Ca (Calos" (1) +Cs Σ ms - mCC))
(8)
Am LT2
297
Here Ti, T2, K1, K2 - Ga are finite constants whose definitions are given in Appendix A.I.
Since के is uniformly bounded below by miin (0,1) from Lemma 1, it is easy to see that the above bound holds for each individual E[]lØ; - 8 [[2]. To better understand the theorem, we provide the following remark.
299
301
Remark& 4 In Appendix B.2.1, we show that both and (1 0.9c:
"Emase lie in the interval (0,1). It is easy
302
to show that is monotonically increasing for 8max and L, monotonically decreasing for 3 and Tmin- Therefore, the summands in the finite-time bound for the fixed step-size case are exponentially
303
decaying expect for the constant C2. which implies that lim lim sup, Σn=1 E[] - 00 S Oz. providing constant limiting bound. From Appendix A, C2 depends on L, Timia Tmax: Amax: 6max-
304
306
In Appendix B.2.2, we show that lime-+oc 1
O, which implies that the finite-time bound (8) for the time-varying step-size case converges to zero as + sc.
E
307
308
We next comment on 0.1 in the inequality defining a. Actually, we can replace 0.1 with any constant (0, 1), which will affect the value of e and the feasible set of o, with the latter becoming 0 < < min{K1, Amn) Katinns:
309
310
e }. Thus, the smaller the value of is, the smaller is the feasible set of ou, though the feasible set is always nonempty. For convenience, we simply pick c 0.1
log
311
in this paper; that is why we also have 0.9 in (7).
7

---

313
Lastly, we comment on on in the time-varying step-size case. We set ou 2 Jamx for the purpose of
0.9 "mas, our analysis approach still
314
getting a cleaner expression of the finite-time bound. For og 0.9 works, but will yield a more complicated expression. The same is true for Theorem 5.
m
316
Technical Challenge and Proof Sketch As described in the introduction, the key challenge of ana- lyzing the finite-time performance of the distributed stochastic approximation (1) lies in the condition that consensus interaction matrix is time-varying and stochastic (not necessarily doubly stochastic). To tackle this, we appeal to the absolute probability sequence म of the viry-ng interaction matrix sequence and introduce the quadratic Lyapunov comparison function Ei=1 T El 0" 113]- Then,
318
319
320
using the inequality Σ E - I 2 Ei (0), + 2E (0) (1)). the next
321
step to find the finite-time bounds of Σ T (0) and (l) 0 11]]. respectively.
322
323
The latter term is essentially the "single-agent mean-square error. Our main analysis contribution
324
here is to bound the former term for both fixed and time-varying step-size cases.
Push-SA
325
326
The preceding section shows that the limiting state of consensus- based distributed stochastic approxi- mation depends on Too, which leads to 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-wise accumulative rewards in applications such as distributed TD learning. In important case when the convex combination is desired to be the straight average, the existing literature c.g. [3,39] relics on doubly stochastic matrices whose corresponding xx (1/N)1N. As mentioned in the introduction, doubly stochastic matrices implicitly require oi-directional communication between any pair of neighboring agents; see e.g. gossiping [62] and the Metropolis algorithm [44]. A popular method to achieve the straight average target while allowing uni-directional communication between neighboring agents
327
329
331
333
335
336
is to appeal to the idea so-called "push-sum" [48], which was tailored for solving the distributed averaging problem over directed graphs and has been applied to distributed optimization [52]. In this section, we will propose a push-based distributed stochastic approximation algorithm tailored for uni-directional communication and establish its finite-time error bound.
337
338
339
Each agent has control over three variables, namely yi. 0 and 6), in which y is scalar-valued with initial value 1, 0f can be arbitrarily initialized, and fj = 6j- At each time & 2 O, each agent i sends its weighted current values wi y/ and úi + A(X,)) + aab' each of its current out-neighbors j E N₁- and updates its variables as follows:
342
343
Σ JENY
vi
36= =1
8
Σ w
0 + or (A(X.)0 + 5 +x.)))
JENS
0i+1
0
8 = 6%.
1+1
v
where u = 1/1N2 It is worth noting that the algorithm is distributed yet requires that each agent be aware of the number of its net-neigs
344
345
346
Asymptotic performance of (9) with any uniformly strongly connected neighbor graph sequence is characterized by the following theorem.
347
348
Theorem& 4 Suppose that Assumptions 2-5 hold. Let (0:), i E V, be generated by (9) and 0 be the unique equilibrium point of the ODE
349
1
8= A0 +
b
(10)
N
350 where and bf are defined in Assumption If (G.) uniformly strongly connected, then 0f will converge to 0r in mean square for all i e V.
8

---

352 In this section, we define (0), N + 0 and (0), Σ 8j. To help understand these definitions, let We be the N N matrix whose ij-th entry equals u jf E NV, otherwise equals zero. It is easy to see that each W₂ is a column stochastic matrix whose diagonal entries are all positive. Then, ग. = N yy for all 2 0 can be regarded as an absolute probability sequence of {W,). Thus, the above two definitions
353
354
355
intuitively consistent with (8), in the previous section.
357
Finite-time performance of (9) with any uniformly strongly connected neighbor graph sequence is characterized by the following theorem.
Let 14 = [x)))) - (0)))2. In Appendix B.3, we show that (0); - (0)ella converges to zero as + co, so does jtc-
359
380
Theorem 5 Suppose that Assumptions 2-4 hold and {G:} } is uniformly strongly connected by sub- aq and on 2 "muax Then, 0.9
362
sequences of length L. Let {6]]. E V, be generated by (9) with 0 1
t-1
there exists nonnegative S (1 NNL)) ) such that for all t 1222 T.
363
N
E 110
0/[2]] s C7t' + Cs (anet + ta(s)) + Cgar
| 1 (Coi log" (2))
+ +C Σ pe + C12)
(11)
k=T
384
where T and C7 C12 are finite constants whose definitions are given in Appendix A.2.
In Appendix B.3, we show that lim E Ek=1 14: O, which implies that the finite-time bound (II) converges to zero as - co. It is worth mentioning that the theorem does not consider the fixed step-size case, as our current analysis approach cannot be directly apply for this case.
365
386
387
Proof Sketch and Technical Challenge Using the inequality Σi= E[l 00
368
389
Ell +1 (0)+ + 2NE]I 11), our goal is to derive the finite-time bounds of E E1 11) and (I) - (1)). respectively. Although this looks similar to the proof of Theorem 3, the derivation is quite different. First, the iteration of (0)x is a single-agent SA plus a disturbance term (0), (0)., so we cannot directly apply the existing single-agent SA finite-time analyses to bound [[] 0 112]: instead, we have to show that (0), (0), will diminish and quantify the diminishing "speed". Second, both the proof of showing diminishing (0), (0), and derivation of bounding Σ Elll (0) involve a key challenge: to prove the sequence (0:) generated from the PUsh-SA (9) is bounded almost surely. To tackle this, we introduce a novel way to constructing an absolute probability sequence for the Push-SA as follows. From (9),
2
370
371
372
375
376
377
41 = Em= /نن (f) + ax,( + at ataaa
(x())),, where بنن = (w vl / wif v/)) We show v/
378
that each matrix W. = [xx5]] stochastic, and there exists a unique absolute probability sequence } for the matrix sequence (W.} such that #े 2 Amin for all i E and / 2 O, with the con- stant Amin E (0, 1). Most importantly, we show two critical properties of (W.) and { namely (1
379
380
381
1 and # 1/4 for all i, E V and 2 O, which have never been reported in the existing literature though push-sum based algorithms have been extensively studied.
382
383
384
4
Concluding Remarks
385
In this paper, we have established both asymptotic and non-asymptotic analyses for a consensus- based distributed linear stochastic approximation algorithm over uniformly strongly connected graphs, and proposed a 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
387
388
389
easy to compute. Future directions include leveraging the analyses for resilience in the presence of malicious agents and extending the tools to more complicated RL.
391

---

References
392
393
[1] R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. Cambridge: MIT press. 1998.
394
385
[2] K. Zhang, Z. Yang, and T. Basar. Multi-agent reinforcement learning: A selective overview of
396
theories and algorithms. arXiv preprint arXiv:1911.10635, 2019.
397 [3] 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, pages 1626-1635, 2019.
398
399
400
[4] K. Zhang, Z. Yang. H. Liu, Zhang, and T. Başar. Fully decentralized reuliii-g learning with networked agents. In 35th International Conference on Machine Learning, pages 5872-5881, 2018.
401
402
403
[5] H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
404
405
[6] R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
406
[7] V. S. Borkar and S. P. Meyn. The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-469 2000.
88] J.N. Tsitsiklis and B. Van Roy. An analysis of temporal-ddiffrrence learning with function
409
approximation. JEEE Transactions on Automatic Control, 4265)67746690 1997.
410
99] P. Dayan. The convergence of TD (A) for general x. Machine Learning, 8(3-4):34-362, 1992.
411
[10] G. Dalal, B. Szörényi, G. Thoppe, and S. Mannor. Finite sample analyses for TD(0) with function approximation. In 32nd AAAI Conference Artificial Intelligence, pages 6144-6160, 2018.
413
414
[1I] C. Lakshminarayanan and C. Szepesvari. Linear stochastic approximation: How far does con- stant step-size and iterate averaging go? In International Conference Artificial Intelligence and Statistics, pages 1347-1355, 2018.
416
417
[12] J. Bhandari, D. Russo, and R. Singal. A finite time analysis of temporal difference learning with linear function approximation. In 31st Conference on Learning Theory, pages 1691-1692, 2018.
419
420
[13] R. Srikant and L. Ying. Finite-time error bounds for linear stochastic approximation and TD learning. In 32nd Conference on Learning Theory, volume 99, pages of Machine Learning Research, 25-28 Jun 2019.
Proceedings
422
423
[14] H. Gupta, R. Srikant, and L. Ying. Finite- timee-timeeeeee performance bounds and adaptive learning rate selection for two time-scale reinforcement learning. In 33rd Conference on Neural Information Processing System, pages 4706-4715, 2019.
425
426
[15] Y. Wang, W. Chen, Y. Liu, Z. Ma, and T. Liu. Finite sample analysis of the GTD policy evaluation algorithms in markov setting. In 31st Conference Neural Information Processing Systems, pages 5504-5513, 2017.
428
429
[16] S. Ma, Y. Zhou, and S. Zou. Variance-reduced off-policy TDC learning: Non-asymptotic convergence analysis. In 34th Conference on Neural Information Processing Systems, 2020.
[17] T. Xu, S. Zou, and Y. Liang. Two time-scale off-policy TD learning: Non-asymptotic analysis over markovian samples. In 33rd Conference on Neural Information Processing Systems, pages 10634-10644, 2019.
432
[18] Z. Chen, S. T. Maguluri, S. Shakkottai, and K. Shanmugam. Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes. In 34th Conference on Neural Information Processing Systems, 2020.
435
[19] S. Zou, T. Xu, and Y. Liang. Finite-sample analysis for SARSA with linear function approx- imation. In 33rd Conference on Neural Information Processing Systems, pages 8668-8678, 2019.
438
[20] G. Qu and A. Wierman. Finite-time analysis of asynchronous stochastic approximation and Q- learning. In 33rd Conference on Learning Theory, volume 125, pages 3185-3205. Proceedings of Machine Learning Research, 09-12 Jul 2020.
441
10

---

443
[21] Y. Wu, W. Zhang, P. Xu, and Q. Gu. A finite time analysis of two time-scale actor critic methods. In 34th Conference on Neural Information Processing Systems, 2020.
444
445
[22] Xu and Q Gu. finite-time analysis of Q-learning with neural network function approxima- tion. In 37th International Conference on Machine Learning, 2020.
[23]
W. Weng, H. Gupta, N. He, L. Ying, and R. Srikant. The mean-squared error of double Q-learning. In 34th Conference on Neural Information Processing Systems, 2020.
448
449
[24] Y. Wang and S. Zou. Finite-sample analysis of Greedy-GQ with linear function approximation under markovian noise. In Jonas Peters and David Sontag, editors, Proceedings of the 36th Conference on Unceriainty in Artificial Intelligence (UAT), volume 124 of Proceedings of Machine Learning Research, pages 11 11-20. PMLR, 03-06 Aug 2020.
450
451
452
453
[25] S. Chen, A. M. Devraj, A. Bušić, and S. Meyn. Explicit mean -aaane error bounds for monte- carlo and linear stochastic approximation. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statisties, volume 108 of Proceedings of Machine Learning Research, pages 4173-4183. PMLR, 26-28 Aug 2020.
455
[26] G. Wang, B. Li, and G. B. Giannakis. A multistep іyарunov approach for finite-time analysis of biased stochastic approximation. arXiv preprint arXiv: 0999.44999 2019.
458
459
[27] G. Dalal, G. Thoppe, B. Szörényi, and S. Mannor. Finite sample analysis of two-timescale
460
stochastic approximation with applications reinforcement learning. In Conference On Learning Theory, pages 1 1199-1233. PMLR, 2018.
461
462
[28]
V.S. S. Borkar and S. Pattathil. Concentration bounds for two time scale stochastic approximation. In 56th Annual Allerton Conference on Communication, Control, and Computing, pages 504-
463
464
511, 2018.
[29] J. N. Tsitsiklis. Problems in Decentralized Decision Making and Computation. PhD thesis, Department of Electrical Engineering and Computer Science, MIT, 1984.
466
487
[30] Y. Zhang and M.M. Zavlanos. Distributed off-policy actor-critic reinforcement learning with policy consensus. In 58th IEEE Conference on Decision and Control, pages 4674-4679, 2019.
468
469
[31] W. Suttle, Z. Yang. K. Zhang. 7. Wang, T. Başar, and J. Liu. A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning. In 21st st IFAC World Congress, 2020.
470
471
[32] K. Zhang, Z. Yang. and T. Başar. Networked multi-agent reinforcement learning in continuous spaces. In 57th IEEE Conference on Decision and Control, pages 2771-2776, 2018
472
473
[33] H.J. Kushner and G. Yin. Asymptotic properties of distributed and communicating stochastic approximation algorithms. SIAM Journal on Control and Optimization, 25(5); 1987.
[34] S. S. Stanković, M. S. Stanković, and D. Stipanović. Decentralized parameter estimation by consensus based stochastic approximation. IEEE Transactions on Automatic Control, 56(3):531- 543, 2010.
476
478
[35] M. Huang. Stochastic approximation for consensus: a new approach via ergodic backward products. IEEE Transactions on Automatic Control, 57(12):2994-300 3008, 2012.
479
480
[36] M.S. Stanković and S.S. Stanković. Multi-agent temporal-differenc -iffeernceeee learning with linear func- tion approximation: Weak convergence under time-varying network topologies. American Control Conference, pages 167-172, 2016.
481
482
[37] P. Bianchi, G. Fort, and W. Hachem. Performance of a distributed stochastic approximation algorithm. IEEE Transactions on Information Theory, 59(11):445--4188 2013.
484
485
[38] M. S. Stanković, N. Ilié, and S. S. Stanković. Distributed stochastic approximation: weak
486
convergence and network design. IEEE Transactions on Automatic Control, (1(12):469940077 2016.
487
488
[39] 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-33)) 0229989-,,000 2021.
489
490
[40] 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.
432
11

---

494
[41] K. Zhang, Z. Yang. H. Liu, T. Zhang, and T. Başar. samtee analysis for decentralized batch multi-agent reinforcement learning with networked agents. IEEE Transactions on Automatic Control, 2021.
495
496
497
[42] J. Sun, G. Wang, G. B. Giannakis, Q. Yang, and Z. Yang. Finite-time analysis of decentralized cemporal-differencd learning with linear function approximation. In International Conference on Artificial Intelligence and Statistics, pages 4485-4495. PMLR, 2020.
498
499
500
[43] S. Zeng, T. T. Doan, and J. Romberg. Finite-time analysis of decentralized stochastic approxima- tion with applications in multi-agent and multi-task learning. arXiv preprint arXiv:2010. 5088, 2020.
501
502
503
[44] L.. Xiao, S. Boyd, and S. Lall. A scheme for robust distributed sensor fusion based on average consensus. In Proceedings of the 4th International Conference on Information Processing in Sensor Networks, pages 63-70, 2005.
504
505
506
[45] B. Gharesifard and J. Cortés. Distributed strategies for generating weight-balanced and doubly
507
stochastic digraphs. European Journal of Control, 18(6):539-555 557, 2012.
[46] N. H. Vaidya, L. Tseng, and G. Liang. Iterative approximate byzantine consensus in arbitrary directed graphs. In Proceedings of the 2012 ACM symposium on Principles of distributed computing, pages 365-374, 2012.
509
511
[47] H. J. LeBlanc, H. Zhang, X. Koutsoukos, and S. Sundaram. Resilient asymptotic consensus in robust networks. IEEE Journal on Selected Areas in Communications, 3164):766-71, 2013.
512
513
[48] D. Kempe, A. Dobra, and Gehrke. Gossip-based computation of aggregate information. In 44th IEEE Symposium on Foundations of Computer Science, pages 482-491, 2003.
514
515
[49] A. Nedić, A. Olshevsky, and M. G. Rabbat. Network topology and communication--omppaaiin
516
tradeoff's in decentralized optimization. Proceedings of the IEEE, 106(5)995--77,, 2018.
[50] A. Olshevsky and J. N. Tsitsiklis. On the nonexistence of quadratic іуаршпоv functions for
consensus algorithms. IEEE Transactions on Automatic Control, 53(1 1):2642-265,, 2008.
518
519
[51] B. Touri. Product of Random Stochastic Matrices and Distributed Averaging. Springer Science
& Business Media, 2012.
[52] A. Nedić and A. Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Trunsuctions on Automatic Control, 60(3):601-615, 2014.
522
523
[53] Chen and A. H. Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Transactions on Signal Processing, 60(8):4289-4305, 2012.
525
[54] A. Jadbabaie, J. Lin, and A. S. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6):988- 1001, 2003.
526
527
[55] R. Olfati-Saber, J. A. Fax, and R. M. Murray. Consensus and cooperation in networked multi-agent systems. Proc. IEEE, 95(1)2215-233, 2007.
528
529
[56] A. Nedić and J. Liu. On convergence rate of weighted-averaging dynamics for consensus problems. IEEE Transactions on Automatic Control, 62(():26622777 781, 2017.
[57] A. Nedić, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis. On distributed averaging algorithms and quantization effects. IEEE Transactions on automatic control, 54(1 (1(()1122562555 2009.
532
533
558 M. Cao, A. S. Morse, and B. D. O. Anderson. Reaching a consensus in a dynamically changing environment: a graphical approach. SIAM Journal on Control and Optimization, 47())5755-600, 2008
535
536
[59]
A. Kolmogoroff. Zur theorie der markoffishen ketten. Mathematische Annlen, 112(1):155-160. 1936.
537
538
[60]
D. Blackwell. Finite non non-homogeneous chains. Annals of Mathematics, 46(4):594-599 1945.
539
[61] A. Olshevsky and J. N. Tsitsiklis. Degree fluctuations and the convergence time of consensus
540
algorithms. IEEE Transactions on Automatic Control, (8110)2626-2663 2013.
[62] S. Boyd, A. Ghosh. B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE
542
Transactions on Information Theory. 52(6))2508-255 2006.
543
663] Adwaitvedant S Mathkar and Vivek Borkar. Nonlinear gossip. SIAM Journal on Control and Optimization, 54(3): 2016.
12

---

545
[64] J. Hajnal and M. S. Bartlett. Weak ergodicity in non-homogeneous Markov chains. Mathematical Proceedings of the Cambridge Philosophical Society, 54:233-246, 1958.
548
[65] A. Nedić and A. Olshevsky. Distributed optimization over time-varying directed graphs. IEEE
548
Transactions on Automatic Control, 60())601-6155, 2015.
13

---

Checklist
549
550
For each question, change the default [TODÖ] to [Yes], [No], or [N/A]] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper
551
552
or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
554
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
555
Did you include the license the code and datasets? [N/A]
557
Please do not modify the questions and only use the provided macros for your answers. Note that the
558
Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
559
560
1. For all authors...
561
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Abstract and Section 1.
563
(b) Did you describe the limitations of your work? [Yes] See Section 4 and the paragraph after Theorem 5.
564
585
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
567
588
2. If you are including theoretical results...
569
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2.
570
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B.
3. If you experiments..
572
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [N/A]
573
574
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
575
576
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
577
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
579
580
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
582
(b) Did you mention the license of the assets? [N/A]
583
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
585
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
586
587
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5e8
589
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
591
592
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
583
594
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
595
14


Reviews:
[{"review_id": "sOPAPDpWYtu", "reviewer": "Reviewer_kdHV", "summary": "This submission considers finite-time error analysis for distributed linear stochastic approximation (SA) algorithms under the assumption that the interconnection matrix is stochastic. In addition, leveraging the idea from “push-sum” based approaches, a novel Push-SA algorithm and the corresponding finite-time error bound are devised for directed interaction graphs.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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:\nThis paper relaxes the commonly adopted assumption that the interconnection matrix is doubly stochastic to a more general one. The assumptions and results obtained in the work are well explained relative to existing works. \n\nWeakness:\nThe motivating context concerns the application of SA approximation in reinforcement learning (RL).  It is suggested to briefly discuss how SA is applied in RL, for example, TD learning.\n\nSome typos to be fixed:\nLine 36, “arguably” —> “inarguably”;\nLine 37, “differing” —> “different”\n\n-------- after rebuttal --------- \nThanks for the reply! After reading other reviews and the committee discussion, I decide to change the score to weakly reject, which is in agreement with other reviewers, who raise detailed and constructive concerns.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Y8sw8rkhB8j", "reviewer": "Reviewer_BEZy", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "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 also new.\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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Numerical simulations may be provided comparing the proposed algorithm and existing ones as well as validating the proved finite-time error bounds for both constant/time-varying stepsizes.  ", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Wb2hRjBHclO", "reviewer": "Reviewer_AANE", "summary": "This paper studies a distributed linear stochastic approximation algorithm. The interconnection structure among the agents is described by a time varying directed graph. Under the setting of Markovian samples, the main contribution is to characterize the finite time error bound on the mean squared error. The analysis is applied to study a push-sum version of distributed linear stochastic approximation. ", "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": "As mentioned, the main contribution is a new analysis on the distributed linear stochastic approximation algorithm given in (1), encompassing constant stepsize and time varying step size, Markovian samples. To achieve this, the study introduces a technique known as the absolute probability sequence to track the evolution of error in light of the time varying directed graph which results in a row-stochastic interconnection matrix. This technique can be interesting as it leads to a simple recursion of the iterates in (4), simplifying the subsequent analysis.\n\nHowever, there are a number of drawbacks which outweigh the benefits of the current paper, as discussed below:\n\n- Though the paper title reads \"distributed linear stochastic approximation\", the algorithm in (1) only considers a restricted setting with an identical driving matrix $A(x)$ across agents (and different $b^i(x)$ across agents). This setting may be suitable for the distributed policy evaluation problem where a number of prior works have appeared, but it does not include many interesting cases for distributed linear stochastic approximation including classical ones such as linear regression. In this regard, the paper may better position itself as a paper for distributed policy evaluation insteado of the more general linear stochastic approximation. \n\n- The main theorems (Theorem 2 & 3) require Assumption 6 which is not well justified. Particularly, this assumption requires the absolute probability seqeunce to admit a limit vector. The Remark 3 which follows the assumption fails to provide a convincing case for this assumption to hold. Therein, two examples are given: the case $W_t$ is doubly stochastic is rather trivial as it defies one of the main relaxation considered in this paper; the case when the number of neighbors of agents are unchanged over time (also, is it the number of out-neighbors? or in-neighbors?) appears to be too artificial. The paper shall include a more concrete construction on how the assumption holds. \n\n- In addition, it is not clear what are the benefits of employing the absolute probability sequence technique in analyzing the convergence of distributed algorithms, e.g., when compared to the classical approach in [52] for the push-SA algorithm. As for the convergence to a weighted average of the equilibrium point when a row-stochastic mixing matrix is employed, some relevant work can be found in the static graph setting, e.g.,\n\n-- J. Chen, A. Sayed, \"Distributed Pareto Optimization via Diffusion Strategies\", IEEE Transactions on Signal Processing, 2013. \n\n- The presentation of the main theorems lacks useful information that a finite-time error analysis should encompass. For instance, it is mentioned that \"$C_2$ depends on $L, \\gamma_{min}, \\gamma_{max}, A_{max}, b_{max}$ ...\" which does not describe how small/large the bound is - in fact, without a more detailed description, the bound in (7) is not useful since $C_2$ can be large; the result for push-SA is summarized in Theorem 5 *only* for the case of time varying step size, and it is mentioned that \"our current analysis approach cannot be directly applied for this case\" which lacks further expatiation; in theorem 3, how does that the convergence rate of $\\eta_t$ affects the finite time error bound in the constant step size case? \n\n---\n**Post Rebuttal**\n\nThe reviewer appreciates the detailed response from the authors. Unfortunately, the response has not addressed my previous concerns and therefore my previous evaluation stands. In particular, the promised \"simulation based\" study will not be very convincing since cases which violate Assumption 6 may still include a lot of cases. Instead, it would be better to construct an **analytical** example to illustrate the necessity of Assumption 6. In summary, my main concern is that Assumption 6 and its corresponding analysis due to the \"absolute probability sequence\" is one of the main innovations claimed in the paper, yet its applications are so far only limited to the previously known cases. \n\nMoreover, while it is acceptable that $C_2$ can be a large constant, it is also important to point out **how** does $C_2$ depends on the system parameter $L, \\gamma_{min}, \\gamma_{max}, A_{max}, b_{max}$. The current presentation has so far eluded from discussing about that. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There isn't any potential negative societal impact. The limitation/suggestions for improvement have been discussed in the main review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "NmHrEkD4Oor", "reviewer": "Reviewer_KMZp", "summary": "This paper studies the convergence distributed linear SA under Markovian sampling. Both asymptotic and non-asymptotic convergence rate results are provided. This paper consider the setting in which the agents interact over a time-varying directed graph, which extend previous studies. Overall the results in this paper is solid and has some technical contributions.", "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": "Overall I think the results in this paper is solid and should be some interesting to the community. I have the following comments about the paper.\n\n(1) Only convergence rate is characterized in the main theorems. It would be better to see the sample complexity result (total number of samples that required to achieve $\\epsilon$-accuracy level) so that the readers can compare the contributions in this paper with the state-of-art.\n\n(2) Although it is a theoretical paper, empirical verification is also suggested even with toy example.\n\n(3) As claimed by the author, the dependence on some conditional numbers is not clear. However those conditional numbers could affects the convergence rate significantly. A detailed discussion about those numbers would makes the paper more convincing. \n\n-------- after rebuttal ---------\nIn the discussion, since the area chair and reviewer AANE raised some concerns about assumptions and the author did not address these concerns convincingly, I change my score to weakly reject.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper does not have potential negative societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper has received some discussion among the reviewers, with a weak consensus centering around rejection. A key concern is the presence of Assumption 6 in the paper. This issue has received substantial discussion with a lengthy reply from the authors. Nevertheless, I believe the authors have not successfully rebutted the concerns raised. 

To summarize the main contribution of the paper: existing analysis of distributed stochastic approximation are based on doubly stochastic matrices. The authors propose an analysis which can handle more cases, based on so-called absolute probability sequences, which is where Assumption 6 comes into play. However, the main concern is that the applicability of these new results is quite narrow. 

The authors list two cases where their results are applicable: (i) when all the matrices appearing in the algorithm share the same left-eigenvector (ii) when the matrices in question change until time T, at which point they remain constant. However, generalizing existing results from doubly stochastic matrices to cover case (i) is quite easy. The authors implicitly point out the key element of this in their response, which is that in this case we can write down a quadratic Lyapunov function using the quantities pi as coefficients -- there is no need for an absolute probability sequence. 

This leaves only case (ii). But if this is the main case where the results of this paper apply, the applicability already is quite narrow. Additionally, while in this case the authors remove scaling with the time T, they add a scaling with pi_{min} because the errors are scaled by pi_{min} in the bounds. There are bounds in the literature for this quantity which are exponentially small in the number of states; for example, see the proof of Theorem 4 in Touri and Nedic,  ''On the existence of a quadratic comparison function...", Proc. CDC 2011. So even in this case, it is not at all clear the results are better than the naive approach of simply applying existing bounds after time T; rather, there are tradeoffs.  Thus I believe this paper does not make the cut for NeurIPS. 

My suggestion to the authors for future submissions is to center the paper around their second main result, Theorem 5, provided it has good applications in distributed ML (this would need to be convincingly argued). 
Decision: Reject