arXiv CS open access

A Spectral Filtering Approach to Regret Analysis of Distributed Online Control for Linear Dynamical Systems

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

A Spectral Filtering Approach to Regret Analysis of Distributed Online Control for Linear Dynamical Systems

arXiv:2608.02375v1 [math.OC] 3 Aug 2026

Ting-Jui Chang the Online Spectral Control method [4] proposes a convex relaxation of linear feedback policies by constructing spectral filters from the eigenvectors of a Hankel matrix. This method achieves the same order of regret guarantees as previous disturbance-feedback approaches [2], while improving the runtime dependence on the inverse stability margin from polynomial to polylogarithmic scaling. On the other hand, the computational and informational constraints of large-scale control systems motivate the development of distributed control algorithms. In many practical systems, the overall control task is carried out by a network of agents or subsystems, such as unmanned aerial vehicles [5], [6], mobile robots [7]–[9] and microsatellite clusters [10], [11]. In these applications, it is often unrealistic to assume that a centralized controller has direct access to the complete cost information of all agents at every time step. Instead, each agent observes only its local cost and communicates with its neighbors through a given network topology. The objective is therefore to design local controllers such that each agent, despite having only partial information, can achieve performance comparable to that of a centralized policy that has access to the global network cost. Motivated by these considerations, this paper studies the distributed online control problem for a network of linear time-invariant systems under adversarial disturbances and time-varying convex costs. Each agent is modeled as an LTI system, and the global network cost is given by the summation of local cost functions. At each round, every agent observes its own state, applies a local control input, receives its local cost function, and exchanges information only with its neighbors. The goal is to minimize the individual regret of each agent with respect to the best centralized policy in hindsight, where the benchmark is chosen from the class of diagonalizably stable linear controllers. The main difficulty is that the centralized spectral controller cannot be directly applied in the distributed setting. In the centralized case, the controller parameters are updated using the gradient of the global loss. In the distributed case, however, each agent has access only to its local cost function and must rely on communication to approximate the global objective. Moreover, the spectral controller is timevarying because the parameters are updated online, and the actual state depends on the entire history of past controller parameters. This prevents a direct reduction to standard distributed online convex optimization. To address this issue, we introduce a distributed online spectral control framework in which agents update their local spectral parameters through a consensus-based online gradient step over memory-less surrogate costs. The surrogate construction allows the control problem to be reformulated as a distributed online learning

Abstract— This paper studies the distributed online control problem over a network of linear time-invariant (LTI) systems in the presence of adversarial disturbances and time-varying convex costs. The network cost is characterized by the summation of local cost functions, where each local function is sequentially revealed only to the corresponding agent. The goal of each agent is to generate a control sequence, using only local observations and neighbor communication, that competes with the best centralized linear policy in hindsight. We extend the recently proposed Online Spectral Control framework from the centralized setting to the distributed setting. In particular, each agent applies a spectral controller obtained by convolving past disturbances with the leading eigenvectors of a Hankel matrix, while the controller parameters are updated through a distributed online gradient descent step over the local surrogate costs. We formulate this problem this problem as a regret minimization problem based on the spectral parameterization, and under standard √ assumptions, we establish a sublinear T) ), where T is the time horizon regret bound of O( T poly(log γ3 and γ denotes the stability margin. The resulting bound also captures the dependence on the network size and connectivity.

I. I NTRODUCTION In recent years, there has been a growing interest in studying problems at the intersection of control theory, machine learning, and online optimization. Classical optimal control provides a rich collection of tools for designing controllers when the system dynamics and the performance criterion are known in advance. For example, in the linear quadratic regulator (LQR) problem, when the dynamics are given and the cost function is quadratic and known in advance, the optimal controller can be computed through Riccati equations. However, many modern control applications operate in nonstationary environments where the cost metric may vary over time, the disturbance sequence may not follow any statistical model, and future information is unavailable at the time when the controller is applied. These challenges motivate the study of online control, where the controller must make sequential decisions while adapting to the revealed cost information. The performance of an online controller is typically measured by regret, defined as the difference between the cumulative cost incurred by the online controller and that of the best policy in hindsight. A sublinear regret bound implies that the timeaveraged performance of the online controller approaches that of the best benchmark policy asymptotically. In the centralized online control setting, recent works [1]–[3] have shown that online learning techniques can be used to design controllers for linear dynamical systems with time-varying convex costs which are unknown in advance. In particular, T.J. Chang is with the Department of Aeronautics and Astronautics, National Cheng Kung University, Taiwan. email:tjc@gs.ncku.edu.tw.

divide the online control literature into two categories, based on the types of the considered cost functions. 1) Online LQR Control: The linear quadratic regulator serves as a canonical optimal control problem, where the stage costs are quadratic functions of the state and control input. When the system dynamics are unknown, the controller must be designed adaptively based on the learned model, and a number of recent works have established sublinear regret guarantees for this setting [17]–[21]. A related line of research considers systems driven by potentially adversarial disturbances. In this direction, [22] studied an MPC-type approach for LQR with time-invariant costs under accurate disturbance predictions, while [23] generalized the framework to time-varying quadratic costs with imperfect predictions. Both works analyzed the performance of the proposed methods through dynamic regret bounds. In [1], the setup of time-varying costs and stochastic √ noises was considered, and a regret bound of O( T ) was proved by formulating the problem as a timevarying semi-definite programming (SDP) problem. 2) Online Convex Control: As opposed to quadratic costs, there is another line of research extending the setup to the case where the time-varying costs are generally convex and the noises are adversarial. Toward this direction, [2] proposed DFC and parameterized the online control problem as an online convex problem √ with memory for which a regret bound of O( T ) was achieved. The bound was further improved to O(poly(logT )) for strongly convex costs [3]. This O(poly(logT )) bound was also proved for the setup where the system is partially observable and the noises are semi-adversarial [24]. Recently, [4] proposed the idea of applying spectral filters to approximate linear control policies, which further improved the dependence on the stability margin compared to DFC. Besides the setup where the function information is available, online control with bandit feedback was studied in [25], [26]. Distributed Control: Distributed LQR has received considerable attention in the control literature. Many existing works consider multi-agent systems with known, identical, and dynamically decoupled agents. For instance, [27] developed a distributed control synthesis method by solving an LQR problem whose dimension depends on the maximum degree of the underlying communication graph. In [28], the authors characterized necessary conditions for optimal distributed controller design, which leads to a non-convex optimization problem. The work [29] studied a multi-agent network in which each agent follows single-integrator dynamics, and showed that computing the optimal controller requires global knowledge of both the network topology and the initial states of all agents. Due to the inherent difficulty of exactly solving the optimal distributed control problem, [30] instead derived sufficient conditions for constructing suboptimal distributed controllers. For the unknown dynamics case, [31] developed a distributed Q-learning algorithm for dynamically decoupled systems. Beyond the setting of identical and decoupled subsystems, several works have also

problem over a fixed-dimensional convex parameter set, while the spectral filters preserve the approximation power of the centralized spectral controller. With this reparameterization, we are able to analyze the performance of the distributed controller by borrowing the existing techniques from online learning. Our main contributions are summarized as follows. 1) Based on the online spectral controller (OSC) proposed in [4], we develop the distributed variant called distributed OSC (D-OSC). At each round, every agent applies spectral filters to the past disturbances and computes its action with its local control parameters based on the filtered information. Then, all agents jointly apply a distributed online gradient step (DOGD) over local surrogate costs (parameterized with the spectral filters) to update the local controllers. 2) We show that the original distributed online control problem can be transformed into a distributed online learning problem through the parameterization of spectral controllers. By appropriately choosing the hyperparameters (the learning rate, the window size of past noises and the number of the spectral√ filters), we T) derive a sublinear regret bound of O( T poly(log ) γ3 where, as the centralized OSC, the dependence on the stability margin γ is improved compared to disturbance feedback controller (DFC) previously proposed in [2]. 3) With respect to the distributed setup, the dependence of the regret bound on the network connectivity and size √ n n is also characterized: O( (1−β) ), where n denotes the total number of agents and β is a parameter inversely proportional to the network connectivity. II. R ELATED L ITERATURE Online Optimization: Online control is closely related to online convex optimization, where a learner sequentially selects actions before observing the corresponding cost functions. A classical result in this area is online √ gradient descent, which achieves sublinear regret of O( T ) for convex functions [12] (see e.g., [13], [14] for more details). In this work, based on the reparameterization using spectral controllers, we transform the original online control problem into a distributed online learning problem which allows us to gauge the control performance through the lens of online learning. Regret vs. Stability: The regret of an online controller is not merely an optimization measure; it is also closely related to stability properties of the corresponding closedloop system. Existing results have shown that, for linear systems driven by adversarial disturbances, regret bounds and stability notions are connected in both time-invariant and time-varying settings regarding the system dynamics [15]. This connection provides a control-theoretic justification for using regret as the performance metric. Similar discussion for non-linear systems can also be found in [16]. Online Control: In contrast to online convex optimization which studies pure optimization problems, online control must additionally account for the effect of current decisions on future states through the system dynamics. This distinction makes online control more challenging. We roughly 2

agent i follows

considered more general distributed control problems. For example, [32] studied the design of distributed controllers for unknown sparse LTI systems. [33] investigated modelfree approaches for distributed LQR and established samplecomplexity guarantees for problem classes satisfying a local gradient dominance property, such as quadratically invariant problems. For control problems in non-stationary environments, [34] extended the SDP method proposed in [1] to the setup of distributed LQR with known dynamics and achieved the regret bound of the same order as [1]. The idea was further generalized to the case with unknown dynamics in [35], and a regret bound of O(T 2/3 log T ) was derived. Spectral Filtering: Spectral filtering was initially introduced as an improper-learning approach for online prediction in linear dynamical systems (LDS). For LDS prediction with symmetric transition matrices, [36] proposed an efficient algorithm which evades the non-convexity of the original system identification problem by overparameterizing the system through spectral filters. This framework was later extended by [37] to general latent-state LDSs, where a new convex relaxation was developed to handle non-symmetric dynamics and phase information without explicitly identifying the underlying system. However, this extension incurred dependence on the hidden dimension. More recently, [38] further advanced this direction by addressing asymmetric and marginally stable LDSs with dimension-free regret guarantees, using spectral filters together with Chebyshevpolynomial-based constructions in the complex plane. In parallel, spectral filtering has also been connected to modern sequence modeling: [39] proposed spectral state space models, which use fixed convolutional filters derived from spectral filtering to capture long-range dependencies while retaining robustness to the spectrum and hidden dimension of the underlying dynamics. Besides sequence prediction, the idea of spectral filtering was incorporated into the design of controllers. For offline LQR with unknown dynamics, [40] showed that the control problem can be formulated as a convex program without first solving the non-convex systemidentification problem. The idea was further extended to the online setup with general convex costs in [4].

xi,t+1 = Axi,t + Bui,t + wt , d1

where xi,t ∈ R and ui,t ∈ R denote the state and control input at time t, respectively. The disturbance sequence {wt } is bounded (wt ≤ W, ∀t), unknown ahead of time, and may be chosen adversarially. In this work, we consider the case where the agent has access to the system dynamics, in other words, (A, B) are known. The distributed online control process unfolds sequentially. At each time step t, agent i observes its current state xi,t , selects an action ui,t , and subsequently receives a local cost function fi,t (·, ·), incurring the cost fi,t (xi,t , ui,t ). Although costs are revealed locally, the objective is global: agents aim to minimize the aggregate network cost ft (·, ·) = P n i=1 fi,t (·, ·). Thus, the design of the control policy is cooperative, requiring each agent to perform well with respect to the overall system objective rather than just its local cost. To evaluate performance, we introduce a centralized benchmark. For any policy π, its cumulative cost over a horizon of length T is JT (π) =

T X

ct (xπt , uπt ).

(1)

t=1

An online distributed algorithm is assessed by comparing its performance against the best policy in hindsight from a predefined benchmark class Π. This comparison is formalized through the notion of individual regret, defined for agent j as RegretjT (A) := JTj (A) − min JT (π), π∈Π

(2)

where JTj (A) denotes the cumulative network cost evaluated along the trajectory generated by agent j under algorithm A. A desirable algorithm ensures that this regret grows sublinearly in T , implying that its average performance converges to that of the optimal centralized policy over time. Since the objective depends on the global cost, agents must exchange information. This interaction is modeled by an undirected communication graph G = (V, E), where V = [n] denotes the set of nodes (i.e., agents) and E represents the set of edges. The interaction weights are encoded in a matrix P with elements ≥ 0, which is assumed to be symmetric, doubly stochastic, and connected. By further assuming P has a positive diagonal, the network exhibits a mixing property that governs how quickly information propagates across agents, which plays a key role in the analysis of distributed algorithms:

III. P RELIMINARIES AND P ROBLEM S ETUP A. Notation [m] ∥·∥ ∥·∥F ΠX [·] [A]ij [A]i,: [A]:,j 1 ei 1

i ∈ [n],

The set {1, 2, . . . , m} for any integer m Euclidean (spectral) norm of a vector (matrix) Frobenius norm of a matrix The operator for the projection to set X The entry in the i-th row and j-th column of A The i-th row of A The j-th column of A The vector of all ones The i-th basis vector Indicator function

n X

[Pk ]ji − 1/n ≤

√

nβ k , i ∈ [n],

(3)

j=1

where β is the second largest singular value of P. Practical Examples: Our framework can be used to model distributed control problems where the main system is composed of a network of sub-systems with identical and decoupled dynamics [5], [9], [10], and the general goal is to minimize the network cost using only local information exchange while reaching consensus. Control problems of this

B. Dynamical System and Cost Model We study a network composed of m identical agents, each governed by a LTI system. The evolution of the state for 3

Online learning is an efficient framework for capturing the evolving pattern of a time-varying function sequence. However, this framework does not directly apply to linear policies of type u = Kx due to the non-convex parameterization (xt is non-convex in terms of K). To address this problem, [2] proposed a disturbance-feedback controller (DFC), where the control is parameterized as a linear function of past noises from a specified time window, and both the state and control become linear functions of those coefficient matrices applied to the noises. In the work of [4], it was shown that the dependency of the regret bound of DFC on the stability margin γ (see Definition 1) can be further improved by convolving past noises with the eigenvectors of a specific Hankel matrix H defined as:

kind have been well-studied through the lens of LQR [27]– [29] while in this work, we further extend to the case where the cost is assumed to be general convex. 1) The considered framework can be applied for analyzing the online temperature control of a heating, ventilation and air conditioning (HVAC) system [41], [42] in a large building with multiple rooms modeled as a network of sub-systems. Supposing the dynamics of each sub-system can be well approximated by an identical dynamical system, the goal, under the condition that all rooms can only exchange the cost information locally, is to minimize the total energy cost over time (the summation of local energy costs of all rooms) while making the temperature of all rooms reach consensus. By applying our proposed algorithm which guarantees an sub-linear bound on (2) ∀i, this goal can be achieved. 2) Another example is the consensus control problem of mobility cost in mobile sensor networks (MSNs) [4] in the time-varying setup. Considering a MSN where the time-varying network mobility cost of sensors is modeled as ct at time t. Each agent has a local budget of ci,t and the team goal, under the condition that the information can only be exchanged locally, is to design actions that minimize the global network cost over time while reaching consensus. As our regret guarantee applies to the individual regret defined by any agent and the learning process complies with the network topology, the goal of a MSN can be achieved with our proposed method.

[H]ij =

(1 − γ)i+j−1 . i+j−1

(4)

The definition of the corresponding spectral controller (SC) is given as follows: Definition 2: A spectral controller (M1:h , H) is defined by parameters M1:h = {M1 , . . . , Mh } for h ≥ 1 and a Hankel matrix H ∈ Rm×m following Equation (4). At round t, the control ut is determined as follows ut =

h X

1/4

σi

Mi Wt−1:t−m ϕi ,

i=1

where {(σj , ϕj )}hj=1 are the top h eigenpairs of H and Wt−1,t−m = [wt−1 , . . . , wt−m ]. To capture the pattern of a time-varying cost sequence, M1:h has to be updated over time, which leads to a time-varying Ph 1/4 t SC: ut = i=1 σi Mi Wt−1:t−m ϕi . By expanding the dynamics recursively, we can see for a time-varying SC, ′ xt+1 is a function of {Mt1:h }tt′ =1 , which circumvents this parameterization from fitting into the framework of online learning since the number of parameters is growing over time. To tackle this problem, we resort to the the memoryless cost function [4] defined as follows:

C. Strong Stability and Strong Controllability In this work, as [4], the centralized benchmark we consider is a set of (κ, γ)-diagonalizebaly stable policies defined as follows: Definition 1: A linear policy K is (κ, γ)-diagonalizably stable (κ > 0 and 0 < γ ≤ 1) for the LTI system (A, B) if there exists matrices L and H such that A+BK = HLH−1 and the following conditions hold: 1) L is diagonal with nonnegative entries* . 2) ∥L∥ ≤ 1 − γ † . 3) ∥K∥ , ∥H∥ , H −1 ≤ κ. The notion of (κ, γ)-diagonalizable stability is similar to the idea of strong stability proposed in [1], which provides a quantification for a stable linear controller K with respect to the system (A, B) in the sense that any stable linear policy is strongly stable with some κ and γ. Despite the requirement of the diagonal structure imposed on L, based on Ackermann’s formula [43], there always exists a K ∈ S (S = {K : K is (κ, γ)-diagonalizably stable}) that controls the noiseless system.

fi,t (M1:h |A, B, {w}) = fi,t (xt (M1:h ), ut (M1:h )) , (5) where xt (M1:h ) and ut (M1:h ) denote the resulting state and control at time t when a fixed M1:h is applied to the dynamical system. IV. M AIN THEORETICAL RESULTS In this section, we introduce D-OSC, a distributed variant of online spectral controller which determines local controllers with information collected through local communication. At each round t, all agents jointly perform a distributed online gradient step over the memory-less cost functions {fi,t (Mi,t 1:h |A, B, {w})}. The update step consists two parts: 1) Each agent i fist shares its current iterate Mi,t 1:h with its neighbors; 2) The weighted average iterate (based on the network topology) is then updated using the local gradient ∇M1:h fi,t (Mi,t 1:h |A, B, {w}). The updated policy parameters Mi,t+1 will be used to decide the next local 1:h action ui,t+1 for agent i. The learning process is summarized in Algorithm 1. Later we show that for user-defined hyperparameters such as η, m and h, by properly selecting them as

D. Spectral Controller * The requirement of nonnegative entries can be further relaxed, and is imposed here for the ease of the analysis. † For the ease of analysis, γ is assumed to be less than 2/3 without loss of generality.

η = mhγ2 √T , we have the individual regret of any agent j ∈ [n] being bounded as √ n nT j ), JT (A1 ) − min JT (π) = Õ( K∈S (1 − β)γ 3

Algorithm 1 Distributed Online Spectral Control

•

1: Require: number of agents n, doubly stochastic matrix

P ∈ Rn×n , parameters γ, η, m, h, time horizon T and the convex constraint set K. 2: Define 1 ×h K = {M1:h ∈ Rd2 ×d q | ∥xt (M1:h )∥ , ∥ut (M1:h )∥ ≤ 3κ3 W 2h 3 γ , ∥M1:h ∥ ≤ κ γ }.

where S denotes the set of (κ, γ) diagonalizably stable linear controllers. The analysis of Theorem 11 mainly consists of three parts: 1) The approximation part, where a diagonalizably stable linear controller is well-approximated by a a spectral controller; 2) The online optimization part, where part of the overall regret is parameterized as an online learning problem using memory-less cost functions ; 3) The gap between the cost induced by actual iterates (xi,t , ui,t ) and that of the memoryless cost function. For the second part, through standard analysis of online convex optimization, the resulting bound is sublinear in T and can be handled optimally when η = Θ( √1T ). There exists a trade-off between the first and third terms: the approximation gap shrinks geometrically in terms of the memory length m, but the the third term increases when m is larger. By properly selecting m and η as functions of the stability margin γ, we show that the dependency on γ, like the centralized case [4], is improved in contrast to that derived based on the DFC parameterization. Also, the impact of the network topology is characterized in terms of the network size n and β, the second largest singular value of P, which is inversely proportional to the connectivity. We can see in the regret bound, when the network is more connected or comes with a smaller size, the resulting regret bound is tighter.

i,1

3: Initialize: ∀i ∈ [n], randomly generate the same M1:h ∈

K for all i. {(σj , ϕj )}hj=1 , the top h eigenpairs of the Hankel matrix H. 5: for t = 1, 2, . . . , T do 6: for i = 1, 2, . . . , n do 7: Determine the control ui,t : 4: Compute

ui,t =

h X

1/4

σj Mi,t j Wt−1:t−m ϕj .

j=1

8: 9:

Observe xi,t+1 and compute wt = xi,t+1 −Axi,t − Bui,t . Pn c i,t+1 Compute M = [P]ji Mj,t − 1:h

j=1

η∇M fi,t (Mi,t 1:h |A, B, {w}). c i,t+1 ). 10: Compute Mi,t+1 = ΠK (M 1:h 1:h 11: end for 12: end for

1:h

functions of γ and T , the resulting individual regret bound is sub-linear in T and enjoy better dependency on γ than DFC. For the technical analysis, we adhere to the standard assumptions used in [2] and [4]. Assumption 1: The system matrix B and the noise wt are bounded, i.e., ∥B∥ ≤ κB and ∥wt ∥ ≤ W, ∀t‡ . Assumption 2: The cost functions fi,t (x, u), ∀i, t are convex, and if ∥x∥ , ∥u∥ ≤ D, the gradients are bounded as follows:

C ONCLUSION In this work, we studied the distributed online control problem for LTI systems with adversarial disturbances and time-varying convex costs. Based on the spectral parameterization proposed in [4], we reformulated this online control problem as a distributed online learning problem and proposed a learning approach called √ D-OSC, which achieves an poly(log T ) individual regret bound of O( n nT ). The resulting (1−β)γ 3 bound preserves the improved dependence on the stability margin inherited from the centralized spectral controller, while also characterizing the effect of the network size and connectivity. Possible future directions include the extensions to unknown dynamics, partially observable systems and timevarying dynamics.

∥∇x fi,t (x, u)∥ , ∥∇u fi,t (x, u)∥ ≤ GD. Assumption 3: The zero policy K = 0 is (κ, γ)diagonalizably stable. The assumption that a zero policy is diagonalizably stable is mainly for the simplicity of the analysis. As shown in Section 8 of [4], this assumption can be relaxed by using a precomputed (κ, γ)-strongly stable linear controller, which can be done by applying SDP relaxation described in [1]. The effect of the relaxed assumption on the main theoretical results boils down to an additional factor in terms of κ. We now present our main theorem as follows: Theorem 1: Suppose Assumptions 1, 2 and 3 hold. Then by running Algorithm 1 with the hyper-parameters determined as follows: 1 • ϵ= √ , T √ 8GκB κ8 W 2 T 1 • m = ⌈ γ log ⌉, 3 γ √ 600GκB κ8 W 2 mdT • h = 2 log T log log T log1/4 γ2 , κ5/2

R EFERENCES [1] A. Cohen, A. Hasidim, T. Koren, N. Lazic, Y. Mansour, and K. Talwar, “Online linear quadratic control,” in International Conference on Machine Learning (ICML), 2018, pp. 1029–1038. [2] N. Agarwal, B. Bullins, E. Hazan, S. M. Kakade, and K. Singh, “Online control with adversarial disturbances,” in International Conference on Machine Learning (ICML), 2019, pp. 154–165. [3] N. Agarwal, E. Hazan, and K. Singh, “Logarithmic regret for online control,” in Advances in Neural Information Processing Systems (NeurIPS), 2019, pp. 10 175–10 184. [4] A. Brahmbhatt, G. Buzaglo, S. Druchyna, and E. Hazan, “A new approach to controlling linear dynamical systems,” arXiv preprint arXiv:2504.03952, 2025. [5] L. Buzogany, M. Pachter, and J. D’azzo, “Automated control of aircraft in formation flight,” in Guidance, Navigation and Control Conference, 1993, p. 3852.

‡ For ease of analysis, κ, κ B and W are assumed to be greater than one without loss of generality.

approach to distributed linear quadratic optimal control,” IEEE Transactions on Automatic Control, vol. 65, no. 3, pp. 1218–1225, 2020. [31] S. Alemzadeh and M. Mesbahi, “Distributed q-learning for dynamically decoupled systems,” in American Control Conference (ACC), 2019, pp. 772–777. [32] S. Fattahi, N. Matni, and S. Sojoudi, “Efficient learning of distributed linear-quadratic control policies,” SIAM Journal on Control and Optimization, vol. 58, no. 5, pp. 2927–2951, 2020. [33] L. Furieri, Y. Zheng, and M. Kamgarpour, “Learning the globally optimal distributed lq regulator,” in Learning for Dynamics and Control (L4DC), 2020, pp. 287–297. [34] T.-J. Chang and S. Shahrampour, “Distributed online linear quadratic control for linear time-invariant systems,” in American Control Conference (ACC), 2021, pp. 923–928. [35] ——, “Regret analysis of distributed online lqr control for unknown lti systems,” IEEE Transactions on Automatic Control, 2023. [36] E. Hazan, K. Singh, and C. Zhang, “Learning linear dynamical systems via spectral filtering,” in Advances in Neural Information Processing Systems (NeurIPS), 2017, pp. 6702–6712. [37] E. Hazan, H. Lee, K. Singh, C. Zhang, and Y. Zhang, “Spectral filtering for general linear dynamical systems,” Advances in Neural Information Processing Systems, vol. 31, 2018. [38] A. Marsden and E. Hazan, “Dimension-free regret for learning asymmetric linear dynamical systems,” arXiv e-prints, pp. arXiv–2502, 2025. [39] N. Agarwal, D. Suo, X. Chen, and E. Hazan, “Spectral state space models,” arXiv preprint arXiv:2312.06837, 2023. [40] S. Arora, E. Hazan, H. Lee, K. Singh, C. Zhang, and Y. Zhang, “Towards provable control for unknown linear dynamical systems,” 2018. [41] S. Shin, Y. Lin, G. Qu, A. Wierman, and M. Anitescu, “Near-optimal distributed linear-quadratic regulator for networked systems,” SIAM Journal on Control and Optimization, vol. 61, no. 3, pp. 1113–1135, 2023. [42] N. R. Patel, J. B. Rawlings, M. J. Ellis, M. J. Wenzel, and R. D. Turney, “Economic optimization of distributed embedded battery units for large-scale heating, ventilation, and air conditioning applications,” AIChE Journal, vol. 65, no. 7, p. e16576, 2019. [43] J. Ackermann, “Der entwurf linearer regelungssysteme im zustandsraum,” at-Automatisierungstechnik, no. 7, pp. 297–300, 1972.

[6] J. Wolfe, D. Chichka, and J. Speyer, “Decentralized controllers for unmanned aerial vehicle formation flight,” in Guidance, Navigation, and Control Conference, 1996, p. 3833. [7] H. Yamaguchi, “A cooperative hunting behavior by mobile robot troops,” in Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat. No. 98CH36146), vol. 4. IEEE, 1998, pp. 3204–3209. [8] H. Yamaguchi, T. Arai, and G. Beni, “A distributed control scheme for multiple robotic vehicles to make group formations,” Robotics and Autonomous systems, vol. 36, no. 4, pp. 125–147, 2001. [9] C. Yang, G. N. Sue, Z. Li, L. Yang, H. Shen, Y. Chi, A. Rai, J. Zeng, and K. Sreenath, “Collaborative navigation and manipulation of a cable-towed load by multiple quadrupedal robots,” IEEE Robotics and Automation Letters, vol. 7, no. 4, pp. 10 041–10 048, 2022. [10] R. Burns, C. A. McLaughlin, J. Leitner, and M. Martin, “Techsat 21: formation design, control, and simulation,” in 2000 IEEE Aerospace Conference. Proceedings (Cat. No. 00TH8484), vol. 7. IEEE, 2000, pp. 19–25. [11] H. Schaub, S. R. Vadali, J. L. Junkins, and K. T. Alfriend, “Spacecraft formation flying control using mean orbit elements,” The Journal of the Astronautical Sciences, vol. 48, pp. 69–87, 2000. [12] M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in Proceedings of the 20th international conference on machine learning (icml-03), 2003, pp. 928–936. [13] N. Cesa-Bianchi and G. Lugosi, Prediction, learning, and games. Cambridge university press, 2006. [14] E. Hazan, “Introduction to online convex optimization,” Foundations and Trends in Optimization, vol. 2, no. 3-4, pp. 157–325, 2016. [15] A. Karapetyan, A. Tsiamis, E. C. Balta, A. Iannelli, and J. Lygeros, “Implications of regret on stability of linear dynamical systems,” arXiv preprint arXiv:2211.07411, 2022. [16] M. Nonhoff and M. A. Müller, “On the relation between dynamic regret and closed-loop stability,” Systems & Control Letters, vol. 177, p. 105532, 2023. [17] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu, “Regret bounds for robust adaptive control of the linear quadratic regulator,” in International Conference on Neural Information Processing Systems (NeurIPS), 2018, pp. 4192–4201. [18] A. Cohen, T. Koren, and Y. Mansour, “Learning linear-quadratic reg√ ulators efficiently with only T regret,” in International Conference on Machine Learning (ICML). PMLR, 2019, pp. 1300–1309. [19] A. Cassel, A. Cohen, and T. Koren, “Logarithmic regret for learning linear quadratic regulators efficiently,” in International Conference on Machine Learning (ICML). PMLR, 2020, pp. 1328–1337. [20] M. Simchowitz and D. Foster, “Naive exploration is optimal for online lqr,” in International Conference on Machine Learning (ICML). PMLR, 2020, pp. 8937–8948. [21] S. Lale, K. Azizzadenesheli, B. Hassibi, and A. Anandkumar, “Reinforcement learning with fast stabilization in linear dynamical systems,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2022, pp. 5354–5390. [22] C. Yu, G. Shi, S.-J. Chung, Y. Yue, and A. Wierman, “The power of predictions in online control,” Advances in Neural Information Processing Systems (NeurIPS), vol. 33, 2020. [23] R. Zhang, Y. Li, and N. Li, “On the regret analysis of online lqr control with predictions,” in American Control Conference (ACC), 2021, pp. 697–703. [24] M. Simchowitz, K. Singh, and E. Hazan, “Improper learning for non-stochastic control,” in Conference on Learning Theory (COLT). PMLR, 2020, pp. 3320–3436. [25] Y. J. Sun, S. Newman, and E. Hazan, “Optimal rates for bandit nonstochastic control,” Advances in Neural Information Processing Systems, vol. 36, pp. 21 908–21 919, 2023. [26] A. Suggala, Y. J. Sun, P. Netrapalli, and E. Hazan, “Second order methods for bandit optimization and control,” in The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024, pp. 4691– 4763. [27] F. Borrelli and T. Keviczky, “Distributed lqr design for identical dynamically decoupled systems,” IEEE Transactions on Automatic Control, vol. 53, no. 8, pp. 1901–1912, 2008. [28] A. Mosebach and J. Lunze, “Synchronization of autonomous agents by an optimal networked controller,” in European Control Conference (ECC), 2014, pp. 208–213. [29] Y. Cao and W. Ren, “Optimal linear-consensus algorithms: An lqr perspective,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 40, no. 3, pp. 819–830, 2010. [30] J. Jiao, H. L. Trentelman, and M. K. Camlibel, “A suboptimality

V. S UPPLEMENTARY A. Complementary materials 2

Lemma 2: Suppose Assumptions 1, 2 and 3 hold. Then by running Algorithm with η = mhγ2 √T , we have ∀i, j, t: √ 144G2 κ2B κ10 W 4 n 2 i,A1 i,A1 i,t 1/2 √ |fj,t (xt , ut ) − fj,t (M1:h |A, B, {w})| ≤ log , 3 γ γ T (1 − β) 2 √ 36Gκ2B κ4 W 2 n . for T ≥ log1/2 γ2 γ(1−β) Proof: Based on how each agent’s iterate is updated, for each k ∈ [t − 1] and h′ ∈ [h], we have i,t−k Mi,t h′ − Mh′

≤

i,t−k Mi,t 1:h − M1:h

t X

≤

i,s−1 Mi,s 1:h − M1:h

s=t−k+1

≤

t X

i,s−1 c i,s c i,s Mi,s 1:h − M1:h + M1:h − M1:h

s=t−k+1

≤

t X

 ∥ri,t ∥ +

n h X

 Pij

i,t−1 t−1 Mj,t−1 − Mt−1 1:h 1:h + M1:h − M1:h

− η∇fi,t−1 (Mi,t−1 1:h )|A, B, {w}

(6)



j=1

s=t−k+1

√ √ √ 12GκB κ5 W 2 mh 2 24ηGκB κ5 W 2 mh n 2 1/4 1/4 ≤ η log + log γ2 γ γ 2 (1 − β) γ s=t−k+1 √ √ 36ηGκB κ5 W 2 mh n 2 1/4 ≤k log . γ 2 (1 − β) γ t X

i,A1 1 = ut (Mi,t solely depends on Mi,t From the algorithm, we can see ui,A t 1:h ). 1:h , which imples that ut 1 As for the deviation between xi,A and xt (Mi,t t 1:h ), first we observe these two terms can be written as follows

xt (Mi,t 1:h ) = 1 xi,A = t

t X

j−1

wt−j +

t X

j=1

t X

j−1

wt−j +

j=1

j−1

h X

1/4

′ σh′ Mi,t h′ Wt−j−1:t−j−m ϕh ,

h′ =1

j−1

h X

(7) 1/4 σh′ Mi,t−j Wt−j−1:t−j−m ϕh′ , h′

h′ =1

j=1

upon which we have 1 xi,A − xt (Mi,t t 1:h )

≤

t X j=1

j−1

∥B∥

h X

1/4

|σh′ | Mi,t−j − Mi,t h′ h′ ∥Wt−j−1:t−j−m ∥

h′ =1

√ √ h X √ 2 36ηGκB κ5 W 2 mh n 2 1/4 log1/4 j log W m (8) γ γ 2 (1 − β) γ j=1 h′ =1 X √ √ t 36ηGκ2B κ7 W 3 mh2 n 2 36ηGκ2B κ7 W 3 mh2 n 2 1/2 1/2 j−1 ≤ log j(1 − γ) ≤ log . 2 4 γ (1 − β) γ j=1 γ (1 − β) γ

≤

t X

κ2 (1 − γ)j−1 κB

Based on the definition of K and the selection of T , we have both Assumption 2, we have ∀j ∈ [n]

1 xi,A , t

xt (Mi,t 1:h )

≤ 4κγW . Then based on

1 1 |fj,t (xi,A , ui,A ) − fj,t (Mi,t t t 1:h |A, B, {w})|

i,t 1 1 =|fj,t (xi,A , ui,A ) − fj,t (xt (Mi,t t t 1:h ), ut (M1:h ))| 4Gκ3 W 1 ≤ xi,A − xt (Mi,t t 1:h ) γ √ 144ηG2 κ2B κ10 W 4 mh2 n 2 1/2 ≤ log 5 γ (1 − β) γ √ 144G2 κ2B κ10 W 4 n 2 √ ≤ log1/2 γ γ 3 T (1 − β)

(9)

Lemma 3: Let a linear policy K ∈ S. Then, for m ≥ γ1 log T X

K |fi,t (xK,m , uK,m ) − fi,t (xK t t t , ut )| ≤

t=1

8GκB κ8 W 2 ϵγ 3

ϵ T, 2

and ϵ ∈ (0, 1),

≤ , uK,m xK,m t t

2κ3 W , γ

∀i ∈ [n]. 3

OLOC ≤ 2κγW , there exists , uK,m Lemma 4: For every open loop optimal controller πK,m such that K ∈ S and xK,m t t SC a spectral controller πh,m,γ,M with M ∈ K such that: T X

K,m M |fi,t (xM , uK,m )| ≤ t t , ut ) − fi,t (xt

t=1

for any ϵ ∈ (0, 1) and h ≥ 2 log T log

600GκB κ8 W 2 ϵγ 5/2

√

log T log1/4

2 γ

ϵ T 2

K Lemma 5: For any K ∈ S, the corresponding states xK t and control inputs ut are bounded as follows,

κ2 W κ3 W , uK . ≤ t γ γ ′ Lemma 6: For any M1:h , M1:h ∈ K, it holds that ∀t, i, xK ≤ t

6GκB κ5 W 2 |fi,t (M1:h |A, B, {w}) − fi,t (M′1:h |A, B, {w})| ≤ 2

√

2 log ∥M1:h − M′1:h ∥ . γ γ Lemma 7: Let σj be the j th top singular value of Hm . Then, for all T ≥ 10, we have mh

1/4

2 2 π2 j 1 · exp − ≤ log . γ 4 log T 2 γ Lemma 8: Let {ϕj } be the eigenvectors of Hm . Then for all j ∈ [m], α ∈ [0, 1 − γ] and γ ≤ 2/3, σj ≤ 156800 log

2 1/4 30 2 π2 j 1/4 σ ≤ √ log exp − . γ γ γ 16 log T P n i,t 1 Lemma 9: Let Algorithm ?? run with step size η > 0 and define Mt1:h = m i=1 M1:h . Under Assumptions ??, ?? and ??, we have that ∀i ∈ [n] √ √ 12ηGκB κ5 W 2 mh n 2 i,t 1/4 t M1:h − M1:h ≤ log 2 γ (1 − β) γ F |µ⊤ α ϕj | ≤

and

√ √ 2 12ηGκB κ5 W 2 mh n 1/4 log . γ 2 (1 − β) γ F i,t t Proof: In this proof, we consider the vectorized versions of Mi,t 1:h , M1:h and ∇fi,t (M1:h |A, B, {w}). For the ease of the analysis, we define the following matrices c i,t+1 Mt1:h − M 1:h

≤

n,t Mt = [M1,t 1:h , . . . , M1:h ] c 1,t , . . . , M c n,t ] b t = [M M 1:h

1:h

n,t Gt = [∇f1,t (M1,t 1:h |A, B, {w}), . . . , ∇fn,t (M1:h |A, B, {w})] Rt = [r1,t , . . . , rn,t ],

c i,t − Mi,t . Based on these notations, the update can be expressed as Mt = Mt−1 P − ηGt−1 − Rt . where ri,t = M 1:h 1:h Expanding the update recursively, we get Mt = M1 Pt−1 −

t−1 X

ηGt−l Pl−1 −

l=1

t−2 X l=0

Rt−l Pl .

(10)

As P is doubly stochastic, we have Pk 1 = 1 for all k ≥ 1. Based on the geometric mixing bound of P, we have ∥Mt − Mi,t ∥ 1 = Mt ( 1 − e i ) n t−1 t−2 X X 1 1 1 ≤ M1 1 − M1 [P(t−1) ]:,i + η Gt−l ( 1 − [Pl−1 ]:,i ) + Rt−l ( 1 − [Pl ]:,i ) n n n l=1 l=0 X √ √ t−1 t−2 √ l 6GκB κ5 W 2 mh 2 X √ l−1 2 6GκB κ5 W 2 mh 1/4 1/4 ≤η log log nβ + η nβ 2 2 γ γ γ γ l=1 l=0 √ √ 12ηGκB κ5 W 2 mh n 2 1/4 ≤ log , 2 γ (1 − β) γ

where the second inequality is due to Lemma 6 and the fact that M1 − M1 [P(t−1) ]:,i = 0 by the identical initialization. Also based on Lemma 6 we have c i,t − Mi,t ∥ri,t ∥ = M 1:h 1:h X X [P]ji Mj,t−1 [P]ji Mj,t−1 − η∇fi,t−1 (Mi,t−1 1:h 1:h 1:h ) −

≤

j 5

≤η

6GκB κ W γ2

√

mh 2 log1/4 , γ

where the first inequality is due to projection on convex sets. By the same token, c i,t+1 = Mt1:h − M 1:h

1 Mt 1 − (Mt P − ηGt )ei m

1 1 − Pei ) + ηGt ei m t−1 X 1 ≤ M1 − M1 [Pt ]:,i + η Gt−l ( 1 − [Pl ]:,i ) m

= Mt (

l=1

t−2 X

1 1 − [Pl+1 ]:,i ) + ∥η∇fi,t (Mi,t )∥ m l=0 √ 6GκB κ5 W 2 mh 2 1/4 ≤η log 2 γ γ # "X √ t−1 t−2 5 2 X √ √ 6GκB κ W mh 2 +η log1/4 mβ l + mβ l+1 γ2 γ l=0 l=1 √ √ 12ηGκB κ5 W 2 mh n 2 1/4 ≤ log . γ 2 (1 − β) γ +

Rt−l (

Theorem 10: Suppose Assumptions 1, 2 and 3 hold. Then by running Algorithm, we have for any M1:h ∈ K, T X n h X

fi,t (Mj,t 1:h |A, B, {w}) − fi,t (M1:h |A, B, {w})

t=1 i=1

2 √ √ n 8ηn n 6GκB κ5 W 2 mh 2 2 1/4 1 M1:h − M1:h + T + 2η log . ≤ 2η (1 − β) γ2 γ Proof: Following the notation defined in Equation (10), we have the following equations for the iterate Mt1:h : 1 1 Mt+1 1 = (Mt P − ηGt − Rt+1 )1 n n n n 1 η 1 ηX 1X i = Mt 1 − Gt 1 − Rt+1 1 = Mt1:h − ∇fi,t (Mi,t |A, B, {w}) − r . 1:h n n n n i=1 n i=1 t+1

Mt+1 1:h =

(11)

Then for any M1:h ∈ K, we have 2 Mt+1 = 1:h − M1:h

2 Mt1:h − M1:h +

n 2 1 X i i,t −rt+1 − η∇fi,t (M1:h |A, B, {w}) n2 i=1

n n 2η X t 2X t i − ⟨M1:h − M1:h , ∇fi,t (Mi,t ⟨M1:h − M1:h , rt+1 |A, B, {w})⟩ − ⟩. 1:h n i=1 n i=1

(12)

Based on Lemma 6, we have # " n n 2 2 1 X i 1 X i i,t i,t ≤ 2 −rt+1 − η∇fi,t (M1:h |A, B, {w}) rt+1 + η ∇fi,t (M1:h |A, B, {w}) n2 i=1 n i=1 2 √ 2 12GκB κ5 W 2 mh 1/4 ≤ η log . γ2 γ

(13)

As fi,t (M1:h |A, B, {w}) is convex in terms of M1:h , we have ⟨M1:h − Mt1:h , ∇fi,t (Mi,t 1:h |A, B, {w})⟩ i,t i,t t =⟨M1:h − Mi,t 1:h + M1:h − M1:h , ∇fi,t (M1:h |A, B, {w})⟩ i,t t ≤fi,t (M1:h |A, B, {w}) − fi,t (Mi,t 1:h |A, B, {w}) + M1:h − M1:h i,t t ≤fi,t (M1:h |A, B, {w}) − fi,t (Mi,t 1:h |A, B, {w}) + M1:h − M1:h

∇fi,t (Mi,t 1:h |A, B, {w}) √ 2 6GκB κ5 W 2 mh 1/4 log γ2 γ

(14)

i ⟩, its upper bound is shown as follows For the term ⟨Mt1:h − M1:,h , −rt+1 i c i,t+1 , −ri ⟩ + ⟨M c i,t+1 − M1:,h , −ri ⟩ ⟨Mt1:h − M1:,h , −rt+1 ⟩ = ⟨Mt1:h − M t+1 t+1 1:,h 1:,h

c i,t+1 ≤ Mt1:h − M 1:,h c i,t+1 ≤ Mt1:h − M 1:,h

i rt+1

√ 6GκB κ5 W 2 mh 2 1/4 η log , 2 γ γ

(15)

c i,t+1 − M1:,h , −ri ⟩ is non-positive because of the property of a where the second inequality is due to the fact that ⟨M t+1 1:,h projection operator on a convex set, and the last inequality is based on Equation. Substituting Equations (13), (14) and (15) into Equation (12), we can get 2

Mt+1 − Mt1:h − M1:h 1:h − M1:h 2 √ √ n 5 2 2 2X 12GκB κ5 W 2 mh 1/4 t c i,t+1 η 6GκB κ W mh log1/4 2 ≤ η log + M − M 1:h 1:,h γ2 γ n i=1 γ2 γ √ n 2η X 6GκB κ5 W 2 mh 2 i,t 1/4 t + fi,t (M1:h |A, B, {w}) − fi,t (Mi,t |A, B, {w}) + M − M log 1:h 1:h 1:h n i=1 γ2 γ

(16)

Due to the convexity of fi,t (·) and Lemma 6, we have the following inequality: i,t fi,t (Mj,t 1:h |A, B, {w}) − fi,t (M1:h |A, B, {w}) i,t ≤ ∇fi,t (Mj,t Mj,t 1:h |A, B, {w}) 1:h − M1:h √ 6GκB κ5 W 2 mh 2 i,t j,t 1/4 t t ≤ log M − M + M − M 1:h 1:h 1:h 1:h γ2 γ

(17)

By adding and subtracting fi,t (Mj,t 1:h |A, B, {w}) on the left hand side of Equation (16) and rearranging it, we have the 10

following inequality based on Equation (17): n h i X fi,t (Mj,t |A, B, {w}) − f (M |A, B, {w}) i,t 1:h 1:h i=1

√ n X 5 2 mh 2 n 2 2 i,t+1 6GκB κ W 1/4 t c Mt1:h − M1:h − Mt+1 − M + M − M log 1:h 1:h 1:h 1:,h 2 2η γ γ i=1 √ n 5 2 X 2 6GκB κ W mh i,t j,t 1/4 t t M − M + 2 log M − M + 1:h 1:h 1:h 1:h γ2 γ i=1 2 √ n 2 12GκB κ5 W 2 mh 1/4 + log η 2η γ2 γ 2 √ n 2 12GκB κ5 W 2 mh n 2 2 1/4 t+1 t ≤ M1:h − M1:h − M1:h − M1:h log η + 2 2η 2η γ γ 2 √ √ 2 8ηn n 6GκB κ5 W 2 mh log1/4 , + (1 − β) γ2 γ ≤

(18)

where the second inequality is based on Lemma 9. Then by summing Equation (18) over t = 1, . . . , T , the theorem is proved. Theorem 11: Suppose Assumptions 1, 2 and 3 hold. Then by running Algorithm, we have the individual regret bound of the following order √ n nT Regret = Õ( ), (1 − β)γ 3 with the hyperparameters determined as follows: 1 • ϵ= √ T √ 8GκB κ8 W 2 T 1 • m = ⌈ γ log ⌉ 3 γ √ 8 2 1/4 2 600GκB κ W mdT • h = 2 log T log log T log 5/2 γ κ 2

η = mhγ2 √T Proof: Proof of Main Theorem Consider K∗ as the optimal linear policy in hindsight. Then, the individual regret is decomposed as follows: •

JTj (A1 ) − min JT (K) K

n h T X i X ∗ K∗ 1 ) − fi,t (xK fi,t (xtj,A1 , uj,A = t t , ut )

t=1 i=1 T X n h X

1 fi,t (xtj,A1 , uj,A ) − fi,t (Mj,t t 1:h |A, B, {w})

t=1 i=1 T X n h i X ∗ + fi,t (Mj,t 1:h |A, B, {w}) − fi,t (M1:h |A, B, {w})

t=1 i=1 T X n h X

∗

,m ,m fi,t (M∗1:h |A, B, {w}) − fi,t (xK , uK ) t t

(19)

t=1 i=1 T X n h i X ∗ ∗ ∗ ,m ,m K∗ + fi,t (xK , uK ) − fi,t (xK t t t , ut ) , t=1 i=1

where each term can be bounded as follows: 1) Based on Lemma 2, we have 1 1 |fi,t (xj,A , uj,A ) − fi,t (Mj,t t t 1:h |A, B, {w})| ≤

√ 144G2 κ2B κ10 W 4 n 2 √ log1/2 . 3 γ γ T (1 − β)

(20)

Pd ⊤ 2) As K∗ ∈ S, we have A + BK∗ = HLH−1 , where L is diagonal and can be written as L = l el , l=1 αl eq P 1/4 d 2 ⊤ ⊤ ∗ 3 αl ≤ 31 , l ∈ [d]. Then by setting M∗i = σi K∗ H i=1 ϕi µαj ej ej . Then by Lemma 8, we have ∥Mi ∥ ≤ κ γ, 11

q which implies ∥M∗1:h ∥ ≤ κ3 2h γ . In addition, based on the proof of Lemma 5.2 in Hazan, it can be shown that M∗1:h ∈ K. Now from Theorem 10, we have T X n h i X ∗ fi,t (Mj,t |A, B, {w}) − f (M |A, B, {w}) i,t 1:h 1:h t=1 i=1

n 2 M11:h − M∗1:h + T ≤ 2η

2 √ √ 8ηn n 2 6GκB κ5 W 2 mh 1/4 log + 2η (1 − β) γ2 γ

(21)

3) Based on our choice of h and Lemma 4, we have ∀i T h i ϵT X ∗ ∗ ,m ,m fi,t (M∗1:h |A, B, {w}) − fi,t (xK , uK ) ≤ . t t 2 t=1

(22)

4) With the selection of m and Lemma 3, we have ∀i T h X t=1

i ϵT ∗ ,m K∗ ,m K∗ K∗ fi,t (xK , u ) − f (x , u ) ≤ i,t t t t t 2

(23)

Substituting Equations (20), (21), (22) and (23) into Equation (19), we get JTj (A1 ) − min JT (K) K

2 √ √ n 8ηn n 6GκB κ5 W 2 mh 2 2 1/4 1 ∗ ≤ M1:h − M1:h + T + 2η log 2 2η (1 − β) γ γ √ 2 144G2 κ2B κ10 W 4 n √ log1/2 +nT + nϵT, γ γ 3 T (1 − β) where the final result is derived by replacing m, h, η with our selections.

(24)

A Spectral Filtering Approach to Regret Analysis of Distributed Online Control for Linear Dynamical Systems

Analyze & explore related research in Conceptio

Related documents