{'fraction_non_alphanumeric': 0.042129699288523954, 'fraction_numerical': 0.011757625260623777, 'mean_word_length': 4.1866220735785955, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
D3PI: Data-Driven Distributed Policy Iteration for Homogeneous Interconnected Systems

Control of large-scale networked systems often necessitates the availability of complex models for the interactions amongst the agents. While building accurate models of these interactions could become prohibitive in many applications, data-driven control methods can circumvent model complexities by directly synthesizing a controller from the observed data. In this paper, we propose the Data-Driven Distributed Policy Iteration (D3PI) algorithm to design a feedback mechanism for a potentially large system that enjoys an underlying graph structure characterizing communications among the agents. Rather than having access to system parameters, our algorithm requires temporary"auxiliary"links to boost information exchange of a small portion of the graph during the learning phase. Therein, the costs are partitioned for learning and non-learning agents in order to ensure consistent control of the entire network. After the termination of the learning process, a distributed policy is proposed for the entire networked system by leveraging estimated components obtained in the learning phase. We provide extensive stability and convergence guarantees of the proposed distributed controller throughout the learning phase by exploiting the structure of the system parameters that occur due to the graph topology and existence of the temporary links. The practicality of our method is then illustrated with a simulation.


Introduction
There has been a renewal of interest in distributed control during the past few years mainly due to the complexity in modeling and analysis of large-scale systems. The unprecedented size of the produced data and required computations have enforced policy-makers to parallelize the computational power into sub-tasks to effectively exploit the problem's potential underlying structure. In such scenarios, high-dimensional collective tasks are formed from local decisions of each member that lead towards a global system-level decision where the synthesis problem can possibly be intertwined or divided among agents. From a modelling viewpoint, the distributed characteristic of the problem can be originated from the underlying interconnections among dynamics, the objective of subsystems, or simply the sparsity in the information exchange. Either way, the standard control methods are not directly applicable due to the shortcomings of scalability 1 and there has been a persistent attempt in the literature to exploit the structure of problem, and thus, make control algorithms more computationally plausible.
In general, structured control synthesis is an NP-hard constrained optimization problem in nature [3,4]. Therefore, the main focus in distributed control is not necessarily to find the optimal policy, but an efficient (possibly suboptimal) control mechanism that benefits from the inherent structure of the system. Meanwhile, recent advances in measurement and sensing technologies have led to the availability of an unprecedented amount of data generated by a variety of physical, social, biological, and transportation systems [5]. This so-called big data revolution has resulted in the development of effective computational tools that utilize the data generated by a dynamic system to reason about reduced order representations of this data, subsequently utilized for classification or prediction on the underlying model. Such techniques have been particularly useful when the derivation of models from first principles is restrictively complex or infeasible, and hence, it seems natural to leverage such data-driven methods for high-dimensional complex systems [6].
In this work, we propose the LQR-based Data-Driven Distributed Policy Iteration (D3PI) algorithm to iteratively learn a set of stabilizing controllers for unknown but identical linear dynamical systems that are connected with a network topology induced by couplings in their performance indices that can also be cast as a particular form of a cooperative game-theoretic setup. Furthermore, data-driven control of (unknown) identical systems is motivated by applications such as formation flight [7] or monitoring networked cameras [8] where the agents possess corresponding dynamics whose exact models are inaccessible due to model perturbations and uncertainties. Notably, to avoid annihilation of the consensus-based nature of the distributed control setup, the option of single-agent learning is ruled out in this framework. We assume that the feedback signal for stabilization is available to each system locally through the same network topology. Then, we find a compound data-driven feedback mechanism for the entire networked system which is trained based on data collected from only a small portion of the network. In particular, considering a subgraph including the agent corresponding to the node with maximum degree, we require temporary feedback links within this subgraph in order to iteratively learn a stabilizing structured controller for the entire network that is optimal for the subgraph-thus, generally suboptimal for the entire network ( Figure 1). Finally, the compound feedback for the entire network is constructed based on this locally optimal policy. We provide extensive analysis on the convergence and stability of our proposed distributed policy followed by comments on its suboptimality with respect to the optimal (unstructured) LQR controller with the same design parameters. We also give a simulation on distributed control of turbocharged diesel engines that showcase the usefulness of D3PI in a practical setting.
The remainder of the paper is organized as follows. We provide an overview on the related literature in Section 2. In Section 3, we introduce the problem setup and the motivation behind our work. In Section 4, we present and scrutinize the D3PI algorithm. We provide theoretical analysis of our method in Section 5. Illustrative simulations are provided in Section 6, followed by concluding remarks in Section 7.

Related Work
Distributed control of large-scale systems is a well-established area of research. The roots of the field trace back to the socioeconomics literature of 1970's [9] and early works in the control literature began to emerge later in the same decade [10]. The inspiration of these types of works were that the presupposition of centrality fails to hold due to the lack of either a central intelligence or , Figure 1: Addition of auxiliary links (dashed red) to the subgraph G d in D3PI during the policy learning phase. The size of the subgraph depends on the maximum degree of the original graph G.
computational capability [11,12]. Subsequently, stability conditions were derived for multi-channel linear systems [13], solidifying the research one further step. Fast forward a few decades, sufficient graph-theoretic conditions were provided for stability of formations comprised of identical vehicles [14] and, along the same lines, graph-based distributed controller synthesis was further examined independently in works such as [3,4,[15][16][17][18]. The topic was also studied from a spatially distributed control viewpoint [19,20] and a compositional layered design approach [21,22]. Moreover, from an agent-level perspective, the problem has been tackled for both homogeneous systems [3,15,17] and more recently heterogeneous ones [23].
The complete knowledge of the underlying system model is a common assumption in the literature on distributed control, where the goal is to find a distributed feedback mechanism that follows an underlying network topology. However, derivation of models from first principles could be restrictive when the system is highly complex and uncertain. Such restrictions also hold for parametric perturbations that occur due to inefficient modeling or other unknown design factors. 2 Robust synthesis approaches could alleviate this issue if the perturbations follow specific models, in both centralized [25] and distributed [26] cases. However, if the original estimates of system parameters are faulty or the perturbations violate the presumed model, then both stability and optimality of the proposed feedback mechanisms will be shattered. Data-driven control, on the other hand, circumvents such drawback by performing the modeling, optimization, and synthesis only by using the data when the physical model is unavailable. From an asymptotic analysis point of view, such machinery are studied under adaptive control and system identification [27,28]. Later, more research was conducted in a discrete non-asymptotic fashion where control and analysis are performed on batches of collected data [29][30][31] or through an online iterative procedure [32,33]. Besides, in regards to the adaptive nature of such algorithms, there is a close connection between online datadriven control and reinforcement learning [34][35][36]. The latter works extend policy iteration [37] to approximate LQR by avoiding the direct solution of Algebraic Riccati Equation (ARE); yet most of them fail to scale towards high dimensions.
Control and estimation of large-scale systems in essence, is a more complicated problem than single-agent (centralized) control because of higher levels of uncertainty, dimensions, and modeling errors. Nevertheless, model-free large-scale analysis-as one tool to address such setbacks-is still an immature research area. Similar ideas have been investigated in Multiagent Reinforcement Learning (MARL) community, mainly presented on a more general Markov Decision Processes (MDP) framework [38,39], but still application of most of the MARL-based algorithms remains challenging as the state-action space grows exponentially large with the number of agents [40]. From a control theoretic perspective, [41] addresses this using ideas from mean-field multiagent systems and with the key assumption of partial exchangeability. Besides, [42] provides a decentralized LQR algorithm based on network consensus that demonstrates low complexity, but potentially very high cost. Also, an SDP projection-based analysis is studied in [43] where each agent is shown to obtain sublinear regret compared to the best fixed controller in hindsight. The problem is also considered from a game-theoretic standpoint [44][45][46] where the set of agents possess conflicting objectives.
In contrast, we propose and analyze the D3PI algorithm in which we iteratively learn necessary control components that would be used to design a distributed controller for the entire network. We also show that depending on the structure of the problem, not only our scheme would be computationally efficient, but also more applicable when model-based control in high dimensions is practically infeasible. The structure of our distributed control design is inspired by classic ideas previously studied in [3] (which is also extended to discrete-time in [17]).
Notations. We denote by R and N the set of real and natural numbers respectively, N 0 = N ∪ {0}, and S refers to the set of symmetric matrices. A column vector with n elements is referred to as v ∈ R n , where v i represents the ith element in v. The matrix M ∈ R p×q contains p rows and q columns with M ij denoting the element in the ith row and jth column of M . The square matrix N ∈ S n×n is symmetric if N = N , where N denotes the transpose of the matrix N . The operator diag(.) makes a square diagonal matrix out of the elements of its argument and the operator vech(.) takes a square matrix and stacks the upper right triangular half (including the diagonal) into a single vector. The zero and identity matrices are denoted by 0 and I n . We let N 0 ( 0) when N is a positive-(semi)definite matrix, i.e., x N x > 0 (≥ 0) for all x = 0. A matrix is positive-definite if and only if all of its leading principle minors are positive. The ith eigenvalue and spectral radius of M are denoted by λ i (M ) and ρ(M ) and M is Schur stable if ρ(M ) < 1. To simplify the vector notation, we use semicolon (;) to concatenate column vectors, e.g., [v w ] = [v; w]. We call the pair (A, B) controllable, if and only if the controllability matrix C = [B AB . . . A n−1 B] has full-rank, where n is the size of the system. A ⊗ B ∈ R p 1 q 1 ×p 2 q 2 refers to the Kronecker product of A ∈ R p 1 ×q 1 and B ∈ R p 2 ×q 2 and the mixed-product property states that for matrices A, B, C, and D with compatible dimensions (A ⊗ B)(C ⊗ D) = AC ⊗ BD. For a block matrix F, by [F] rk we imply the rth row and kth column "block" component with appropriate dimensions. We denote by I E the indicator function of event E defined as I E = 1 if E holds and I E = 0 otherwise. A graph is characterized by G = (V G , E G ) where V G is the set of nodes and E G ⊆ V G × V G denotes the set of edges. An edge exists from node i to j if (i, j) ∈ E G ; this is also specified by writing j ∈ N i , where N i is the set of neighbors of node i. We show the maximum degree of G by d max (G). The complete graph created from the nodes in V G is denoted by K(V G ). Finally, the graph can be represented by various matrices such as graph Laplacian L G or the adjacency A G .

Problem Setup
Consider a network of identical agents with interdependecies briefed in a common network-level objective function. In particular, we assume that the system contains N agents forming a graph G = (V G , E G ) where each node of the graph in V G represents a linear discrete-time decoupled dynamical system as, with x i,t ∈ R n and u i,t ∈ R m denoting the states and inputs of agent i at time-step t, respectively. Also, A ∈ R n×n and B ∈ R n×m are unknown system parameters that we assume to be controllable as a pair (A, B) on the hindsight. The formulation can be compactly presented as, wherex t ∈ R N n andû t ∈ R N m contain the states and inputs of entire networked systems, withÂ ∈ R N n×N n andB ∈ R N n×N m defined in block diagonal formsÂ = I N ⊗ A andB = I N ⊗ B.
The interconnections of these agents are captured by the set of edges E G ⊆ V G × V G that provide the communication possibilities for distributed feedback controller design. We do not assume that G is necessarily connected and its reason becomes apparent in the next section. Let N i denote the set of neighbors of node i in G (excluding itself). Then, based on this communication graph structure and for any choice of positive integers a and b, we define a linear subspace of R aN ×bN as follows Without having access to the system parameters A and B, we are interested in designing linear feedback gains with a desired sparsity pattern using measurements from the system in (2). Of particular interest in this work are the structured feedback gains based on the underlying communication network. Given an initial conditionx 0 , the distributed (structured) optimal control problem is posed in the form of, whereK stabilizes the pair (Â,B) (i.e. ρ(Â+BK) < 1),R = I N ⊗R andQ = I N ⊗Q 1 +L G ⊗Q 2 for some given cost matrices Q 1 0, Q 2 0, R 0. Note thatQ ∈ U N n,n (G) and it is a simple exercise to show thatQ is positive definite. Such interdependent structure of the cost have been considered in a graph-based distributed control framework in the literature (See for instance [3,15,17,47]). Intuitively, the first term inQ indicates the absolute cost pertinent to regulating each agent, while the second term denotes the cost that arises from consensus error with respect to the neighbors' states.
The goal is to find a data-guided suboptimal solution to problem in (3) without the knowledge of system parametersÂ andB. Indeed, not knowing the true underlying system parameters, adds one additional layer of difficulty to this framework. Instead, input-state data of the system can be collected for distributed feedback control synthesis over the given underlying communication graph G. In what follows, we summarize the challenges involving the analysis of this problem: I) In general, the constrained optimization problem in (3) is an NP-hard problem [48]. Based on the complete knowledge of the system parameters, it has been investigated under variety of assumptions [3,19,49,50], or tackled directly with the aid of projected gradient-based policy updates [4,51]. II) On the other hand, the main issue with data-driven approaches is the fact that, the policy obtained in this way, will not necessarily respect the hard constraint ofK ∈ U N m,n (G) as was posed in the optimization (3). Also, a "projection" onto the intersection of this constraint and stabilizing controllers is not straightforward due to the complicated geometry of the set of stabilizing controllers [52]. III) Another significant challenge of adopting data-driven methods for the entire network takes root in the "curse of dimensionality" inherent to large-scale networked systems. In fact, collecting data from the entire large-scale network itself is prohibitive. IV) Finally, it is often impossible in real-world applications to stop the entire network from functioning for data collection or decision-making purposes. Therefore, a proposed algorithm must enjoy an online nature that allows the entire network to evolve through out the process.
As a designer is left with no choice rather than leveraging the input-state observations to find a "reasonable" distributed policy for the networked system, we summarize our approach in the followings: I) As the constraintK ∈ U N m,n (G) is strict in distributed control synthesis and the underlying problem is NP-hard in general, we shift our attention from the optimal solution of (3) towards a suboptimal stabilizing distributed controller with reduced computational burden. II) Inspired by a Q-learning-based policy iteration algorithm, we propose a model-free distributed policy iteration scheme to obtain a reasonable solution to the problem in (3). In particular, We learn two control components that resembles the "individual" and "cooperative" parts. We also simultaneously learn a stability margin related to these components which eventually is utilized to prescribe a distributed control synthesis consisting for the entire network. III) Inherent to our algorithm is a subproblem whose dimension is related to only the maximum degree of the underlying graph rather than the dimension of the original network. In particular, we will reason that for the learning phase, our method requires data collection only from a specific smaller portion of the underlying network G d ⊆ G with size d = d max (G) + 1. This subgraph is substantially smaller than the original graph whenever d max (G) N which is the case in many real-world applications. IV) We allow temporary feedback links on G d during the learning phase of our algorithm that would be removed subsequently. So, our approach allows an online execution of our algorithm.
As described in the subsequent sections, the distributed control design part of our method follows a model-based framework previously studied in [3,17]. Here, we provide a model-free distributed policy iteration algorithm provided which is not only computationally efficient, but also, more practical when model-based control in high dimensions is not feasible.

The Objective of D3PI Algorithm
We base our method on a policy iteration scheme where a linear feedback gain is updated at each iteration followed by a policy evaluation step that finds the solution to the corresponding Lyapunov function. With no knowledge of the system parametersÂ andB, we may follow a Qlearning-based methodology with a trial-and-error nature in which a control agent optimizes some value function from observing the results of its own actions (see [35,36] for instance). To implement such machinery, an online iterative scheme-say, Recursive Least-Squares (RLS)-is often utilized where at each iteration, data is collected using the current estimate of the policy and the same data is recursively employed to perform an inherent policy evaluation step. Then the policy is updated in a similar manner to the discrete-time LQR update as, where F and G are matrix blocks estimated from data in the policy evaluation step. Nonetheless, the main issue with this approach is the fact that the policy obtained in this way, will not respect the hard constraint ofK ∈ U N m,n (G) as was posed in the optimization (3). On the other hand, an arbitrary "projection" of the obtained policy on the set U N m,n (G) may fail to be stabilizing. Furthermore, such projection onto the intersection of this constraint and stabilizing controllers is not straightforward due to the complicated geometry of the set of stabilizing controllers [52].
As the constraintK ∈ U N m,n (G) is strict in distributed control synthesis, we shift our attention from the optimal solution of (3) towards a suboptimal stabilizing distributed controller with reduced computational burden. Hence, we need to exploit the structure that is incurred to this formulation from the underlying graph. Finally, we note that it is often prohibitive in real-world applications to stop the entire network from functioning for data collection or decision-making purposes. Therefore, we allow temporary feedback links on a specific smaller portion of the underlying network G d ⊆ G with size d during the learning stage of our algorithm that would be removed subsequently. 3 We will reason that for the learning phase, our method requires observations only from this portion of the graph where few temporary links are appended to make G d complete. We show that such interdependency leads to finding control components separately that later on, prescribe a distinction between "self" versus "cooperative" controls in a network. In the next section, we provide the D3PI algorithm and sketch the analysis that connects the ideas presented above along with the convergence study.

Main Algorithm
In this section, we propose and discuss the main algorithm of the paper. Given the underlying communication graph G, the system is considered as a black-box, whereas the designer is capable of inserting input signals to the system and observe states. The goal of D3PI is then to find a data-guided suboptimal solution to problem in (3) without the knowledge of system parametersÂ andB. To this end, we take a roundabout and consider the synthesis problem of only a subgraph G d ⊆ G and collect data only from that portion of the system. Before we proceed to the main algorithm, we formalize two notions in order to facilitate the presentation. Definition 1. Given any subgraph G ⊆ G and a fixed labeling of the nodes, we let "Policy (V G )" denote the concatenation of all the policies of the agents in V G , i.e., where u i is the feedback control policy of agent i in the subgraph G as a mapping from {x j |j ∈ N i ∪ {i}} to R m . Furthermore, we use Policy(V G ) t to denote the realization of these policies (i.e. the control signals) at time t. Similarly, we define, 3 Of our particular interest are those systems that can be modeled with graphs in which d N . Examples of such occurrences are prevalent in grid-based applications such as social media, power grids, etc.
The D3PI algorithm is introduced in Algorithm 1. During the learning phase, we include temporary "auxiliary" links to G d and make the communication graph complete. We show such distinction by G d,learn where |V G d | = V G d,learn and G d,learn = K(G d ). Inherent to D3PI is a policy iteration on G d,learn that finds components K k and L k which intuitively represent "self" and "cooperative" controls at iteration k, respectively. Even during the learning phase, we utilize these components in order to design and update an effective stabilizing controller for the remainder of the agents in G \ G d,learn . We do so by ensuring that during the learning phase, information is exchanged unidirectional from G d,learn to the rest of the network, therefore, the policy of the agents in G \G d,learn is dependent on those in G d,learn , but not vice versa. Finally, with the convergence of the algorithm, we remove the temporary links so as to get back to the original communication topology, and propose a final suboptimal stabilizing scheme for the entire network that follows the original network topology. In the learning stage of D3PI, we use an RLS-based recursion to estimate the unknown parameters in the cost matrix at iteration k, referred to as H k . This entire process is performed in the Subgraph Policy Evaluation (SPE) (Algorithm 2) given G, G d,learn , the mapping policy(V G d ), and the previous estimate of H k−1 . 4 As will be discussed in Appendix A.1, H k contains the required information to find K k and L k from data. We extract this square matrix through a recursive update on the vector θ k−1 , derived from half-vectorization of H k−1 , solving the RLS for the linear equation R(x t ,ũ t ) = ζ t θ k−1 , where R(x t ,ũ t ) denotes the local cost and ζ t ∈ R p contains the data measurements. 5 The adaptive nature of the algorithm entails the exploration signal e t to be augmented to the policy vector in order to satisfy persistence of excitation. In our setup, e t is sampled from a normal distribution e ∼ N (0, Σ) where the choice of the variance Σ is problemspecific. 6 We denote by P k the projection factor that is reset to P • 0 at the beginning of each iteration. Convergence of the SPE-guaranteed based on the persistence of excitation condition-is followed by the update of H k that encodes the necessary information to get K k and L k . This is done by recovering the block matrices X 1 , X 2 , Y 1 , Y 2 , Z 1 , and Z 2 from H k that are further used to form the intermediate variables F and G. 7 Such recovery of meaningful blocks from H k is due to the specific matrix structure that is resulted from adding extra links to G d and will be discussed further in the following section. Each iteration loop is then ended by updating the parameters γ k and τ k which are effective in the stability analysis of the proposed controller throughout the process. With the convergence of D3PI, G d is retrieved by removing the temporary links and the distributed policy is extrapolated to the entire graph G. Lastly, note that the inverse operations on line 14 of the algorithm occur on matrices of size m × m and are computationally negligible. Furthermore, the complexity of finding extreme singular values-as on line 17 in Algorithm 1-is shown to be as low as O(n 2 ) [55]. Hence, the computational complexity of D3PI is mainly originated from the SPE recursion that is equivalent to the complexity of RLS for the number of unknown system parameters in G d and is equal to O d 2 (n + m) 2 [56]. This implies that the complexity of the algorithm will be fixed for any number of agents N , as long as the maximum degree of the graph remains unchanged. Remark 1. Adding temporary links within the subgraph G d is a way to learn optimal K k and L k for the subgraph G d,learn by fully examining the dynamical interference among the agents. Moreover, initializing K k such that (1) is Schur stable-as assumed in our algorithm-has become a standard in the data-driven control literature. However, we acknowledge that this is not a trivial assumption Algorithm 1 Data-Driven Distributed Policy Iteration (D3PI) 1: Initialization (t ← 1, k ← 1)

2:
Obtain graph G and choose G d ⊆ G with d = d max (G) + 1

7:
Switch ON temporary links in G d to set G d,learn ← K(G d ) 8: While K k and L k not converged, do 9: Set P k ← P • 10:

18:
Set τ k+1 ← γ 2 k+1 /(1 + γ k+1 ) 19: k ← k + 1 20: Switch OFF the temporary links and retrieve G d and often impractical, in particular, when the system is unknown. While we stick to this assumption for the brevity of analysis, the interested reader is referred to the recent works [32,57] to learn how the issue can be circumvented for specific classes of systems.

5:
Choose e t ∼ N (0, Σ) and update Policy(V G ) t for all i ∈ V G asũ t ←ũ t + e t

Convergence and Stability
In this section, we provide the convergence and stability analyses of the D3PI algorithm. For clarity of the discussions, we defer the framework subtleties and extensive detailed proofs to Appendices A and B. First, we study the structure and gain margins of each local controller and then establish the stability property of the proposed controller for the entire network throughout the learning process of D3PI algorithm. Lastly, we show the convergence of D3PI to a stabilizing suboptimal distributed controller followed by the derivation of a suboptimality bound characterized by the problem parameters.
We begin by introducing a linear group and show its useful properties in our setup. For any integer r ≥ 2, let us define the patterned linear group as follows PL(r × n, R) := N r ∈ GL(rn, R) N r = I r ⊗ A − B + 1 r 1 r ⊗ B, for some A ∈ GL(n, R) ∩ S n×n and B ∈ S n×n . Proposition 1. The PL(r × n, R) is indeed a linear group. Furthermore, for any stable matrix A ∈ PL(r × n, R), let P denote the unique solution to the discrete-time Lyapunov equation for any 0 ≺ Q ∈ S rn×rn , i.e., it satisfies P = A P A + Q. Then, P ∈ PL(r × n, R) if and only if Q ∈ PL(r × n, R).
The fact that the patterned linear group is preserved under Lyapunov equation is a key to our analysis that facilitates efficient propagation of information in our algorithm. Next, we demonstrate how a specific structure and stability of the controller for the subgraph G d,learn , if initialized properly, can be preserved throughout D3PI algorithm.
Proposition 2. Let K k := I d ⊗ K k − L k + 11 ⊗ L k for all k ≥ 0 where K k and L k are obtained as in Algorithm 1. If K 1 is a stabilizing controller for the system in G d,learn = K(V G d ), then the following statements are true for all k ≥ 0, • Policy k (V G d,learn ) t = K kxt , ∀t.
• K k is stabilizing for all k ≥ 0 for the system in G d,learn .
• ∆K k := K k − L k stabilizes the dynamics of one single agent, i.e., A + B∆K k is Schur stable.
The results in Proposition 2 form the cornerstone of the remainder of the analysis in this section. It also gives insights on the existence of a stabilizing controller ∆K k and its corresponding costto-go matrix ∆P k . In the sequel, our goal is to design a distributed suboptimal controller based on the components that shape ∆K k . To this end, we find stabilizability gain margins that induce more flexibility in designing the distributed controller. In the following proposition, we provide the backbone of the distributed controller design for the networked system of G.
Proposition 3. At each iteration k ≥ 0, let K k , L k and τ k be as obtained in Algorithm 1 and choose α such that |α − 1| < τ k . Then A + B(K k − αL k ) is Schur stable.
The result in Proposition 3 provides model-free stability gain margins, τ k , at each iteration of the algorithm for the dynamics of one single agent in G. We take advantage of these margins as a tool to find stability guarantee for the controller proposed in our algorithm. For the learning phase of D3PI, this is formally established in the following theorem.
Theorem 1. Suppose K k , L k and τ k are defined as in Algorithm 1. Then the control policy Policy k (V G ) designed as, stabilizes the entire network G at each iteration of the learning phase in Algorithm 1 for any choice of V G d .
The latter theorem establishes the fact that the proposed feedback mechanism stabilizes the entire network throughout the learning phase. This facilitates the control of the agents outside of G d , while the learning process is activated in the subgraph. Nonetheless, the practicality and suboptimality characteristics of the algorithm heavily depend on its convergence. This will be addressed in the following theorem.
Theorem 2. Assume that the initial controller K 1 is stabilizing for (1) and Policy k (V G d ) t in Algorithm 2 is persistently excited. Then K k → K * , L k → L * , γ k → γ * , and τ k → τ * as k → ∞ where K * = I d ⊗ K * − L * + 11 ⊗ L * is the optimal solution to the infinite-horizon statefeedback LQR problem with system parameters A, B, Q, R defined as As we remove the temporary links that were provided for the learning phase, the structure of the interconnections in G are returned to it original topology. Therefore, it is vital to provide stability guarantees after the recursion in Algorithm 1 is completed. This statement is a direct consequence of Theorem 1 when the control components are converged and is outlined in the following corollary.
Corollary 1. Suppose K * , L * , γ * , and τ * are given as in Theorem 2 where Algorithm 1 is converged. Then Policy(V G ) defined as,

Simulation
In this section, we apply our method to a series of identical turbocharged diesel engines with exhaust gas recirculation in a chain formation that work collectively for industrial power generation ( Figure 2). The dynamics of the engines are assumed to be unknown and we apply D3PI to find a model-free distributed policy based on the observed data from the system. The values of the continuous-time system parameters are given as [58], We normalize and discretized the dynamics with a sampling rate of ∆T = 0.1s. We set Q 1 = Q 2 = I n and R = I m with n = 6 and m = 2 and sample a random exploration signal from a zero-mean normal distribution. Given the number of engines N ≥ 5, the maximum degree of a path graph is d max = 2, and hence, d = d max + 1 = 3. W.l.o.g., we take the first three engines (i = 1, 2, 3) as the elements of G d . Figure 3 demonstrates the trajectories of the states of node i = 4 for the case when D3PI synthesis is ON (solid curves) and contrasts it to the naive application of model-free policy iteration to G d without considering the control of the rest of the network. The latter is referred to as D3PI-OFF in the plots (dashed curves). As the plot suggests, when D3PI is activated, the states of each engine remain near the origin throughout learning. Note that when D3PI is ON, the noisy behavior of the trajectories is due to the (unidirectional) interconnections of G d -being persistently excited-with the rest of the network. Furthermore, the first few iterates of the learning and post-learning are magnified for better comparison of the trajectories. Figures 4 and 5 outline the performance of our algorithm on the nodes inside G \ G d over 5000 runs of the simulation. Figure 4 depicts the cumulative logarithmic costĴ G\G d,learn for all nodes i ∈ V G d over the entire horizon of the algorithm's implementation for N = 10. As the figure shows, the algorithm is converged by the end of the first iteration at time-step t = 400 where the cost indices get fixed, implying the convergence of the states to the origin (because the state cost matrix is positive definite). The result of our algorithm (blue)   is compared with the case when D3PI is OFF (red) and also the optimal unstructured solution of LQR (for the same system parameters) as the baseline. The plot also verifies the stability of the proposed policy as the cost remains bounded bounded (andQ 0). Similar implementation is performed for N = 5, 6, · · · , 30 and the final costs are reported in Figure 5. The increase in costs is due to the added value by the newly included agents in G \ G d,learn . As the plot suggests, the gap between our method and the case with inactive D3PI shows the superiority of our algorithm for any problem setting with different number of agents in the system.

Conclusion and Remarks
In this paper, we propose the D3PI algorithm as an efficient model-free distributed control of potentially high-dimensional homogeneous linear systems that are interconnected with an underlying communication graph. We exploit the graph-based structure to propose a policy that reflects the sparsity pattern in the system. To achieve a structured controller for the entire network that is persistently stabilizing throughout the learning process, D3PI requires temporary additional communication links during the policy learning phase to a small portion of the graph. The results of the synthesis of this subsystem is leveraged in order to achieve a distributed feedback mechanism for the entire system. Other than controllability of the unknown system, our algorithm makes no assumption on the dynamics' parameters. Furthermore, our method does not require rest-ofthe-network shutdown during the learning process and introduces stabilizing controllers at each iteration. Extension of the current results to a heterogeneous system of agents is considered as an immediate future direction of our work. Moreover, D3PI builds upon parameter estimation techniques that represent an end-to-end policy prediction directly from observed data. In a black-box linear setup, model-based methods-i.e., extracting an approximate model from data and use it for control-can be integrated in this multiagent setup to further reduce sample and time complexities of the algorithm. We address these ideas for potential future investigation.

A Analysis Prerequisites
In this section, we initiate the building blocks and tools that we need for the proofs and the analysis of our algorithm. We first provide some insight on how our setup is connected to the classic modelbased LQR machinery and some previously established results that we leverage from the literature. Next, we present some lemmas that will be used later on in the proof of the main results in Section 5.

A.1 Underlying Model of the Subsystem G d
The configuration of the synthesis problem in D3PI intertwines an online recursion on the subsystem corresponding to G d and the original system G. To distinguish between these two frameworks, we use the tilded notation to present system parameters of G d in contrast to the hatted notion introduced in Section 3 for G. In particular, from (1) the dynamics of the subgraph G d can be cast as, wherex t andũ t are formed from concatenation of state and control signals in G d -recall that u t is also denoted by Policy(V G d ) in the algorithm to emphasize the functional independence of Algorithms 1 and 2-and A = I d ⊗ A and B = I d ⊗ B form the dynamics parameterization of G d .
Also define Q = I d ⊗ Q − 11 ⊗ Q 2 and R = I d ⊗ R. From the Bellman equation [59] for the LQR problem with parameters ( A, B, Q, R), the cost-to-go matrix of G d is correlated with the LQR cost, where R(x t ,ũ t ) =x t Qx t +ũ t Rũ t is the one-step cost, P k is the solution to the Lyapunov equation, and K k is the controller estimate at iteration k. The dynamic programming solution to the LQR problem suggests a linear feedback formũ t = K kxt for the subsystem G d at each iteration. As in [36], combining (6) and (7) with some rearrangements result iñ wherez t = [x t ;ũ t ]. Note that the discrete-time LQR policy update can be obtained from, and the Lyapunov equation in (8) can be rewritten as, Hence, H k provides the required information to perform both policy update and policy evaluation steps in a policy iteration algorithm. We will show that because of the particular structure of our setup, H k enjoys a special block pattern, justifying the recovery of the block matrices X 1 , X 2 , Y 1 , Y 2 , Z 1 , and Z 2 from H k in D3PI. Such constraint on the subspace of this particular class of matrices H k can also be employed in order to potentially reduce the computational complexity of the algorithm. D3PI leverages this idea to implicitly learn H k from data and exploit these matrix blocks in order to find a suboptimal solution to problem (3).

A.2 Linear Algebraic Lemmas
In the remainder of this section, we first state a well-known result to make the paper self-contained, and then propose two new linear algebraic facts as vital complements to our analysis. where M, N ∈ R n×m with n ≥ m and a > 0.

([60])
The following equation holds for matrices A, B, C, and D with compatible dimensions, where D and H = A − BD −1 C are invertible. [62]) The following holds,

(Matrix Inversion Lemma
for matrices A, U , C, and V with compatible dimensions where A, C, and A + U CV are invertible. Lemma 2. Suppose A and B are symmetric matrices such that A, A − B, and A + (n − 1)B are all invertible for some n ∈ N 0 . Then the following algebraic relations hold: 3. N −1 r ∈ PL(r × n, R), i.e., with F and G defined as, Let the claim hold for r = p − 1. Then for r = p we again use the Schur complement to get, 3) Since N r is invertible, N r−1 − L r−1 A −1 L r−1 is invertible by Schur complement where L r−1 = 1 r−1 ⊗ B. We follow the proof by induction. For r = 2, from item item 3 in Lemma 1, establishing the recurrence of diagonal blocks. Furthermore, Also, from item 1 in Lemma 2 with n = 1, we get that where we also used Hence, Assume that the claim holds for r = p. To extend the result to r = p + 1, again from Lemma 1 items 3 and 4, where the inversions are valid from item 2 of the current Lemma. By simplification we get P = A − nB F p + (n − 1)G p B and from Lemma 2 items 1 and 2, which, in turn, gives P = A − nB A + (p − 1)B −1 B. Also with similar reasoning, each block of P −1 L p N −1 p has the following form, and for the off-diagonal terms, Hence, the inverse can be cast as, with F p+1 and G p+1 defined as,

4)
With direct multiplication and using the mixed-product property of Kronecker products,

Proof of Proposition 1
The fact that PL(r × n, R) is a linear group follows directly by item 3 and item 4 in Lemma 3. Now for any Schur stable matrix A, and any symmetric positive definite matrix Q there exists a unique positive definite solution P to the discrete Lyapunov equation described by P = ∞ j=0 (A ) j QA j (item 2 in Lemma 2). Note, that PL(r × n, R) ⊂ S rn×rn by construction. Therefore, since PL(r × n, R) is a linear group, each summand also falls in PL(r×n, R) whenever Q ∈ PL(r×n, R). Thus, as the infinite sum preserves the structure, P ∈ PL(r × n, R) whenever Q ∈ PL(r × n, R). Conversely, if P ∈ PL(r × n, R), then Q = P − A P A also must lie in PL(r × n, R). This completes the proof.

Proof of Proposition 2
The first claim is a direct consequence of the structure of G d,learn during the learning phase, where G d,learn = K (G d ) and hence u i = ∆K k x i + L k j∈V G d,learn \{i} x j for all i ∈ V G d,learn which, in turn, results inũ t = K kxt . Since the underlying system A, B is assumed to be controllable andũ t is persistently excited, the stabilizability of the policy K k follows directly form Theorem 1 in [36]. Now, assume K is stabilizing for = 1, · · · , k. From Lemma 1, the solution to (8) is given by, From item 4 in Lemma 3, the term inside the latter sum preserves the structure of K k . Therefore, P k can be reformulated as, where P 1,k and P 2,k are obtained from (8) as, with A K k = A + BK k and, Setting Z 1 = B P 1,k A, Z 2 = B P 2,k A, Y 1 = R + B P 1,k B, and Y 2 = B P 2,k B, the matrix blocks H 21,k and H 22,k (as defined in (9)) become, Recall from (10) where Subtracting the two equations in (13) and some simplification results in, where ∆P k = P 1,k − P 2,k , A ∆K k = A + B∆K k , ∆K k = K k − L k , and Q = Q 1 + dQ 2 . Since Q + ∆K k R∆K k 0, by Lyapunov Stability Criterion it suffices to show that ∆P k 0. Note that K k being stabilizing implies P k 0 from (8). Therefore, the final claim follows by item 2 in Lemma 3 and the structure of P k from (12).

Proof of Proposition 3
Define the Lyapunov candidate function V k (x t ) = x t ∆P k x t where ∆P k is defined as in Proposition 2 and x t contains the states of the closed-loop system x t+1 = A + B(K k − αL k ) x t . We show that for the given choice of α, V k is nonincreasing. From definition, where Γ k = (A + B(K k − αL k )) ∆P k (A + B(K k − αL k )) − ∆P k . Suppose α < 1. from (15), where the inequality holds for some a > 0 due to Lemma 1. Let β = (1 − α)/2 and choose a = β + β 2 + 1. Then, Γ k = (1 − α)a A ∆K k ∆P k A ∆K k + L k B ∆P k BL k − Q + ∆K k R∆K k ≤ (1 − α)aσ max A ∆K k ∆P k A ∆K k + L k B ∆P k BL k I − σ min Q + ∆K k R∆K k I Note that using the parameterization of control blocks in Algorithm 1 and also from (9), the latter bound can be obtained completely from data as, Γ k ≤ (1 − α)aσ max Ξ k + L k (∆Y − R)L k I − σ min Q + ∆K k R∆K k I = ((1 − α)a − γ k ) σ max Ξ k + L k (∆Y − R)L k I with Ξ k defined as, where we used the structure in (9) and the way the matrix blocks were defined on line 13 of Algorithm 1. From the hypothesis 1 − τ k < α, we obtain γ 2 k − 4β 2 γ k − 4β 2 > 0. Since γ k > 0, this second-order term in γ k only gets positive when, γ k > 2β 2 + 2β β 2 + 1 = 2β(β + β 2 + 1) = (1 − α)a.
where the upper block forms an upper triangular matrix with block diagonals A+B(K k −λ i (S)L k ). We already know from Proposition 2 that A K k is Schur stable. Hence, we only need to show ρ (A + B(K − λ i (S)L)) < 1 for i = 1, · · · , N − d. We know |λ i (A(G))| ≤ d max [63]. Then from this inequality, definition of S, and the fact that d max = d − 1, The rest of the proof follows directly from Proposition 3.

Proof of Theorem 2
We first show θ k → θ * k as k → ∞ where θ * k includes similar parameterization to that of θ k at iteration k but for the true system parameters. Correspondingly, let H * be the counterpart to H k . First, by induction we show that the parameter estimation error is uniformly bounded. Then, as the established bound will be inversely proportional to the number of iterations of SPE, we conclude the convergence of the parameter estimator. For that, assume the parameter estimation error in Algorithm 1 is bounded, i ≤ c i ≤ c 0 , for i = 1, · · · , p − 1 and c 0 > 0. From Lemma 2 in [36], where = 1/ C 0 σ min (P 0 ) for some 0 > 0 and C is the number of iterations of SPE for each k. From Theorem 1 in [37] we know θ * p−1 − θ * p ≤ s 0 at every consecutive step of policy iteration under controllability assumptions. Therefore, where κ = (c 0 + s 0 ) / ( 0 σ min (P 0 )) > 0. Hence by choosing C > κ/δ for any δ > 0, we get θ p − θ * p < δ. We know from [37] that at convergence, the approximated policy for true system parameters can be derived from, where A, B, R, and Q are defined as in Appendix A.1 and P * satisfies, Recall from (12) that the solution to this Lyapunov equation satisfies P * = I d ⊗(P * 1 −P * 2 )+11 ⊗P * 2 with corresponding blocks P * 1 and P * 2 . From Lemmas 2 and 3, where, Then direct multiplication results in K * = I d ⊗ (K * 1 − K * 2 ) + 11 ⊗ K * 2 where, which coincides with the updates of K k and L k in the algorithm. Therefore, our policy update at optimality corresponds to (16) which completes the proof.