Online Adversarial Stabilization of Unknown Networked Systems

Online Adversarial Stabilization of

Unknown Networked Systems

JING YU,

California Institute of Technology, United States

DIMITAR HO,

California Institute of Technology, United States

ADAM WIERMAN,

California Institute of Technology, United States

We investigate the problem of stabilizing an unknown networked linear system under communication con-

straints and adversarial disturbances. We propose the first provably stabilizing algorithm for the problem.

The algorithm uses a distributed version of nested convex body chasing to maintain a consistent estimate of

the network dynamics and applies system level synthesis to determine a distributed controller based on this

estimated model. Our approach avoids the need for system identification and accommodates a broad class of

communication delay while being fully distributed and scaling favorably with the number of subsystems.

CCS Concepts:

•

Theory of computation

→

Adversary models

;

Distributed algorithms

; Online learning

algorithms; Quadratic programming.

Additional Key Words and Phrases: online control; learning-based control; adversarial control; distributed

control; stability; communication delay

ACM Reference Format:

Jing Yu, Dimitar Ho, and Adam Wierman. 2023. Online Adversarial Stabilization of Unknown Networked

Systems.

Proc. ACM Meas. Anal. Comput. Syst.

7, 1, Article 26 (March 2023), 43 pages. https://doi.org/10.1145/

3579452

1 INTRODUCTION

Large-scale networked dynamical systems play a crucial role in many emerging engineering systems

such as the power grid [

], autonomous vehicles [

], and swarm robots [

]. Motivated by the

success of learning-based control methods for single-agent (centralized) linear systems, there has

been growing interest in learning distributed controllers for unknown networked systems composed

of interconnected and spatially distributed linear time-invariant (LTI) subsystems [

However, since most existing literature ports centralized learning-based control techniques over

to the distributed setting, almost all previous work assumes that the underlying dynamics are stable,

or that a stabilizing and distributed controller is known. For a large-scale networked system, such

assumptions are often unrealistic, because designing stabilizing distributed controllers itself is a

significant task even if the dynamics model is available [7, 30, 35, 64, 81, 92].

Recent work has begun to lift the assumption of the knowledge of a stabilizing controller in the

centralized case, e.g. [

]. This line of work follows the approach of system identification,

either by letting the unstable system run open-loop or by exciting the system via control inputs.

However, such approaches induce explosive transient behaviors due to the instability of the under-

lying system. Without proper generalization to the networked setting, such explosive behavior can

cause catastrophic system degradation before a proper stabilizing controller can be learned.

Authors’ addresses: Jing Yu, California Institute of Technology, Pasadena, United States, jing@caltech.edu; Dimitar Ho,

California Institute of Technology, Pasadena, United States, dho@caltech.edu; Adam Wierman, California Institute of

Technology, Pasadena, United States, adamw@caltech.edu.

This work is licensed under a Creative Commons Attribution International 4.0 License.

2023 Copyright held by the owner/author(s).

2476-1249/2023/3-ART26

https://doi.org/10.1145/3579452

Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 26. Publication date: March 2023.

26:2

Jing Yu, Dimitar Ho, and Adam Wierman

Table 1. Maximum and top

90%

infinity norm of the state (

∥

푥

(

푡

)

∥

∞

) for different disturbance profiles averaged

over 10 runs. Simulation details are provided in Section 5.

Algorithm

Correlated Gaussian (Top

90%

)

Uniform (Top

90%

)

State-dependent (Top

90%

)

This work

(

)

(

)

(

)

SysID

(

)

(

)

(

)

Further, until now, scalability and information constraints have only been considered separately

in learning-based distributed controller design; no general approach exists. On the other hand,

information constraints and scalability have been the central topics in distributed control for the

past decade due to their theoretical challenge and practical importance [

Therefore, it is crucial to simultaneously consider such constraints when designing learning-based

distributed control algorithms for networked systems.

1.1 Contributions

In this work, we overcome the aforementioned challenges by leveraging recent advances in online

learning and distributed control. In particular, we propose an approach that combines a distributed

version of nested convex body chasing (NCBC), in order to maintain a consistent estimate of

the network dynamics, with system level synthesis (SLS), in order to determine a distributed

controller based on the selected consistent model. This combination yields the first online algorithm

that provably stabilizes a networked LTI system with information constraints under adversarial

disturbances (Theorem 4.4). The proposed algorithm (Algorithm 2) is distributed and scales favorably

to the number of subsystems in the network.

The proposed approach in this paper is fundamentally different than traditional system identifica-

tion based methods, which incur prohibitively large state norm under adversarial disturbances, even

in the simplest setting (see Table 1). The reason is that system identification-based approaches seek

to learn the full system dynamics, which requires full excitation of the system against worst-case

disturbances. On the other hand, our approach does not require precise knowledge of the system.

Instead, we maintain model estimates that are consistent with the observations generated by the

unknown system at all times. A consequence of focusing on consistency is a natural endogenous

exploration-exploitation scheme where our algorithm performs well (small state norm) while the

selected model stays consistent, and gains information about the system whenever it observes a

large state norm that renders the selected model inconsistent.

The main result of this paper is an input-to-state stability guarantee (Theorem 4.4), where we

draw novel connections between the path length property of NCBC techniques and system stability

analysis. This follows from a set of novel technical results for SLS in the learning-based control

context. In particular, we generalize a previous result [

] on the characterization of the closed loop

under SLS controllers that are synthesized from an arbitrary and potentially incorrect system model

(Lemma 3.2). This result enables the analysis of our algorithm when each subsystem uses local,

asynchronous, and wrong model information for local controller synthesis. Further, we derive a

novel perturbation result with explicit constants for finite-horizon SLS synthesis (Theorem 3.4) that

globally bounds the sensitivity of the optimal solution to the SLS problem (a quadratic program

with equality and sparsity constraints) with respect to the model. This result is also applicable in

other contexts such as a class of MPC problems studied in [6, 15, 68].

1.2 Related work

This work contributes to a large and growing body of work on the topics related to learning-based

control design, online control, and distributed control. We briefly review the literature most related

to this work below.

Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 26. Publication date: March 2023.

Online Adversarial Stabilization of Unknown Networked Systems

26:3

Stabilization of unknown systems.

Stabilizing unknown linear systems has long been a

fundamental problem studied in adaptive control theory [

]. It recently reemerged as a learning

problem and received considerable attention from the machine learning community [

Most works have been developed under single-agent setting, with a no-noise assumption [

] or

Gausssian noise models [

]. Under the adversarial noise setting, which is the focus of this paper,

the only work that guarantees stabilization for LTI systems is [

], with a system identification-

based approach that achieves order-optimal regret. In contrast, we propose a novel framework

for stabilization under adversarial noise that does not rely on accurate identification of the true

dynamics. In particular, our method is the first algorithm to stabilize a networked LTI system under

adversarial disturbances with information constraints while simultaneously achieving magnitudes

of improvement in empirical performance over the state-of-the-art identification-based approach

[18] in the single-agent setting, despite the regret-optimal guarantee in [18].

Distributed control.

Motivated by large-scale cyberphysical systems that are composed of

physically distributed subsystems with local dynamical interactions, there is a large body of work

on control design for networked systems [

]. Cyberphysical systems such as the power grid

are commonly constrained by a communication layer that allows specific structure of information

exchange among the subsystems. such information structure imposes significant challenges for

optimal control design, often rendering the problem NP-hard [

]. In [

], it was shown that a large

class of practically relevant distributed control problems is convex and tractable to solve. Since

then, many works have focused on this class of problems [

]. However, [

] observes that the

complexity of computation and implementation of distributed controllers developed under this

setting can be prohibitively expensive, thus not scalable to large-scale systems. The System Level

Synthesis (SLS) framework is developed as a scalable alternative to distributed control design [

In particular, SLS allows order-constant complexity for synthesis and implementation, due to its

special parameterization and implementation of the feedback controller. As a result, many works

have adopted SLS as the basis for novel (learning-based) control algorithms in both distributed and

centralized setting [

]. We contribute to the literature on SLS by developing a suit of

technical results for SLS controllers that can find applications beyond the setting of this work.

Learning distributed controllers.

Many learning-based control algorithms for networked

systems adopt a centralized learning or computational approach with the objective of regret

minimization, e.g., [

]. All prior work use the stochastic noise or no-noise model and

assume a known stabilizing distributed controller is given [

–

]. As far as we are aware,

no previous work accommodates communication delay while doing both learning and control. The

most related to our work are [

] and [

], where learning-based SLS controllers are designed to

control unknown networked systems. Both of the methods require the knowledge of a stabilizing

and distributed controller. [

] is only applicable to small-uncertainty scenarios, while [

] requires

a stabilizing distributed controller and performs centralized learning. In this work, we focus on

stabilization and propose the first distributed learning-based control algorithm that guarantees

stability for unknown networked systems under adversarial disturbances.

Online learning.

The problem of online stabilization for unknown dynamical systems is an

instance of online decision making problems, where an agent makes a sequence of decisions based

on the feedback from an unknown environment with the goal of cost minimization. Online decision

making is studied extensively in the online learning literature, with a line of work [

] that

makes interesting connections between convex function and body chasing [

] and linear control

theory. In particular, [

] proposes an online nonlinear robust control method based on convex

body chasing that guarantees finite mistakes under adversarial disturbances without the need for

system identification. While [

] considers binary cost functions, we present novel technical results

Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 26. Publication date: March 2023.

26:4

Jing Yu, Dimitar Ho, and Adam Wierman

that establish the first connection between convex body chasing and stability analysis for both

single-agent and networked linear dynamical systems.

1.3 Notation

Let

∥ · ∥

be the

ℓ

norm and

∥ · ∥

퐹

be the Frobenius norm. We denote the

(

푖, 푗

)

th position of a

matrix

푀

(

푖, 푗

)

and use

푀

(

, 푗

)

,푀

(

푖,

)

for the

푗

th column and

푖

th row of

푀

respectively. We

use

[

푁

]

for the set of positive integers up to

푁

. Positive integers are denoted as

. Bold face

lower cases are reserved for vector signal of the form

[

푥

(

)

푇

,푥

(

)

푇

, . . .

]

푇

with

푥

(

푡

) ∈

푛

an infinite sequence of vectors indexed by time

푡

. We reserve bold face capital letters for causal

linear operators/transfer matrices with components

퐾

[

]

,퐾

[

]

, . . .,

such that







퐾

[

]

. . .

퐾

[

]

퐾

[

]

. . .







We write

to mean that

푦

(

푡

)

푡

푘

퐺

[

푘

]

푥

(

푡

−

푘

)

. Given any binary matrix

C ∈ {

}

푁

we say

푀

∈ C

for a matrix

푀

∈

푁

if the sparsity of

푀

. We use

{

푒

푗

}

푛

푗

for the standard

basis in

푛

2 PRELIMINARIES AND PROBLEM SETUP

We consider the task of stabilizing an unknown networked system made up of

푁

interconnected,

heterogeneous linear time-invariant (LTI) subsystems, illustrated in Figure 1(a). For each subsystem

푖

∈ [

푁

]

, let

푥

푖

(

푡

) ∈

푛

푖

푢

푖

(

푡

) ∈

푚

푖

푤

푖

(

푡

) ∈

푛

푖

be the local state, control, and disturbance vectors

respectively. Each subsystem

푖

has dynamics,

푥

푖

(

푡

)

∑︁

푗

∈N(

푖

)

퐴

푖푗

푥

푗

(

푡

퐵

푖푗

푢

푗

(

푡

)

푤

푖

(

푡

)

(1)

where we write

푗

∈N(

푖

)

if the states or control actions of subsystem

푗

affect those of subsystem

푖

through the open-loop network dynamics (

푖

∈N(

푖

)

). Concatenating all the subsystem dynamics,

we can represent the global dynamics as

푥

(

푡

)

퐴푥

(

푡

퐵푢

(

푡

푤

(

푡

)

(2)

where

푥

(

푡

) ∈

푛

푥

푢

(

푡

) ∈

푛

푢

푤

(

푡

) ∈

푛

푥

, with

푛

푥

푁

푖

푛

푖

and

푛

푢

푁

푖

푚

푖

, and we define

퐴

푖푗

, 퐵

푖푗

≡

for all

푗

∉

푖

)

. The networked LTI model

(1)

has been extensively studied in the

networked control literature for various applications such as robotic swarms [

], voltage control

for the distribution network of the power grid [

], and many other large-scale cyber-physical

systems [

]. An example is the linearized swing equation for power systems, where the global

system is composed of a mesh of interacting buses [

]. In this setting, the states

푥

푖

of each bus

푖

is two-dimensional and corresponds to the phase angle relative to some given setpoint and the

associated frequency. The input

푢

푖

at bus

푖

is the controllable load, while

푤

푖

is the bounded load

disturbances that are often correlated in space and time.

We assume that the topology among the subsystems is known,

i.e.

, the sets

푖

)

for

푖

∈ [

푁

]

are known. However, the parameters of the dynamics (entries of matrices

퐴

푖푗

퐵

푖푗

) are unknown.

Let

휃

푖

denote the unknown

local parameter

for subsystem

푖

, i.e.,

휃

푖

퐴

푖푗

, 퐵

푖푗

푗

∈N(

푖

)

. Further, let

(

휃

, . . .,휃

푁

)

be the

global parameter

. We write

퐴

(

)

and

퐵

(

)

(equivalently

퐴

푖푗

(

휃

푖

)

퐵

푖푗

(

휃

푖

)

to emphasize that

퐴

and

퐵

are matrices constructed with appropriate zeros according to the network

topology (known), and the nonzero entries specified by

(unknown).

Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 26. Publication date: March 2023.

Online Adversarial Stabilization of Unknown Networked Systems

26:5

Dynamics

<latexit sha1_base64="JFzINiAFUxsg4rjuHJ6iAMUSQNo=">AAAB63icbVBNS8NAEJ3Ur1q/qh69LBbBU0lE1GPRi8cK9gPaWDbbTbt0dxN2J2Ip/QtePCji1T/kzX9j0uagrQ8GHu/NMDMviKWw6LrfTmFldW19o7hZ2tre2d0r7x80bZQYxhsskpFpB9RyKTRvoEDJ27HhVAWSt4LRTea3HrmxItL3OI65r+hAi1Awipn09OCVeuWKW3VnIMvEy0kFctR75a9uP2KJ4hqZpNZ2PDdGf0INCib5tNRNLI8pG9EB76RUU8WtP5ndOiUnqdInYWTS0khm6u+JCVXWjlWQdiqKQ7voZeJ/XifB8MqfCB0nyDWbLwoTSTAi2eOkLwxnKMcpocyI9FbChtRQhmk8WQje4svLpHlW9S6q53fnldp1HkcRjuAYTsGDS6jBLdShAQyG8Ayv8OYo58V5dz7mrQUnnzmEP3A+fwBCMI28</latexit>

x

1

<latexit sha1_base64="yg0xGo6m9KuHiPLdwJNJSS5gT/w=">AAAB6nicbVDLTgJBEOzFF+IL9ehlIjHxRHYJUY8kXjxilEcCK5kdemHC7OxmZtZICJ/gxYPGePWLvPk3DrAHBSvppFLVne6uIBFcG9f9dnJr6xubW/ntws7u3v5B8fCoqeNUMWywWMSqHVCNgktsGG4EthOFNAoEtoLR9cxvPaLSPJb3ZpygH9GB5CFn1Fjp7umh0iuW3LI7B1klXkZKkKHeK351+zFLI5SGCap1x3MT40+oMpwJnBa6qcaEshEdYMdSSSPU/mR+6pScWaVPwljZkobM1d8TExppPY4C2xlRM9TL3kz8z+ukJrzyJ1wmqUHJFovCVBATk9nfpM8VMiPGllCmuL2VsCFVlBmbTsGG4C2/vEqalbJ3Ua7eVku1ShZHHk7gFM7Bg0uowQ3UoQEMBvAMr/DmCOfFeXc+Fq05J5s5hj9wPn8ACc2NmQ==</latexit>

x

2

<latexit sha1_base64="Os5uqW6rvxlw9CevnT29gDrV/jE=">AAAB6nicbVDLTgJBEOz1ifhCPXqZSEw8kV0k6pHEi0eM8khgJbNDL0yYnd3MzBoJ4RO8eNAYr36RN//GAfagYCWdVKq6090VJIJr47rfzsrq2vrGZm4rv72zu7dfODhs6DhVDOssFrFqBVSj4BLrhhuBrUQhjQKBzWB4PfWbj6g0j+W9GSXoR7QvecgZNVa6e3o47xaKbsmdgSwTLyNFyFDrFr46vZilEUrDBNW67bmJ8cdUGc4ETvKdVGNC2ZD2sW2ppBFqfzw7dUJOrdIjYaxsSUNm6u+JMY20HkWB7YyoGehFbyr+57VTE175Yy6T1KBk80VhKoiJyfRv0uMKmREjSyhT3N5K2IAqyoxNJ29D8BZfXiaNcsm7KFVuK8VqOYsjB8dwAmfgwSVU4QZqUAcGfXiGV3hzhPPivDsf89YVJ5s5gj9wPn8AC1GNmg==</latexit>

x

3

<latexit sha1_base64="O3gxJ1PymaIznOPedqXX0qdf8EM=">AAAB6nicbVDLTgJBEOzFF+IL9ehlIjHxRHYJUY8kXjxilEcCK5kdZmHC7OxmptdICJ/gxYPGePWLvPk3DrAHBSvppFLVne6uIJHCoOt+O7m19Y3Nrfx2YWd3b/+geHjUNHGqGW+wWMa6HVDDpVC8gQIlbyea0yiQvBWMrmd+65FrI2J1j+OE+xEdKBEKRtFKd08P1V6x5JbdOcgq8TJSggz1XvGr249ZGnGFTFJjOp6boD+hGgWTfFropoYnlI3ogHcsVTTixp/MT52SM6v0SRhrWwrJXP09MaGRMeMosJ0RxaFZ9mbif14nxfDKnwiVpMgVWywKU0kwJrO/SV9ozlCOLaFMC3srYUOqKUObTsGG4C2/vEqalbJ3Ua7eVku1ShZHHk7gFM7Bg0uowQ3UoQEMBvAMr/DmSOfFeXc+Fq05J5s5hj9wPn8ADNWNmw==</latexit>

x

4

<latexit sha1_base64="YrN/clwoRM7+Ognfd0ZXVOlt4BI=">AAAB6nicbVDLTgJBEOz1ifhCPXqZSEw8kV2CjyOJF48Y5ZHASmaHXpgwO7uZmTUSwid48aAxXv0ib/6NA+xBwUo6qVR1p7srSATXxnW/nZXVtfWNzdxWfntnd2+/cHDY0HGqGNZZLGLVCqhGwSXWDTcCW4lCGgUCm8Hweuo3H1FpHst7M0rQj2hf8pAzaqx09/Rw3i0U3ZI7A1kmXkaKkKHWLXx1ejFLI5SGCap123MT44+pMpwJnOQ7qcaEsiHtY9tSSSPU/nh26oScWqVHwljZkobM1N8TYxppPYoC2xlRM9CL3lT8z2unJrzyx1wmqUHJ5ovCVBATk+nfpMcVMiNGllCmuL2VsAFVlBmbTt6G4C2+vEwa5ZJ3UarcVorVchZHDo7hBM7Ag0uowg3UoA4M+vAMr/DmCOfFeXc+5q0rTjZzBH/gfP4ADlmNnA==</latexit>

x

5

<latexit sha1_base64="eKTAITp1zurCZhkjJa0wGPT38rE=">AAAB6nicbVDLTgJBEOz1ifhCPXqZSEw8kV1C0COJF48Y5ZHASmaHXpgwO7uZmTUSwid48aAxXv0ib/6NA+xBwUo6qVR1p7srSATXxnW/nbX1jc2t7dxOfndv/+CwcHTc1HGqGDZYLGLVDqhGwSU2DDcC24lCGgUCW8Hoeua3HlFpHst7M07Qj+hA8pAzaqx09/RQ7RWKbsmdg6wSLyNFyFDvFb66/ZilEUrDBNW647mJ8SdUGc4ETvPdVGNC2YgOsGOppBFqfzI/dUrOrdInYaxsSUPm6u+JCY20HkeB7YyoGeplbyb+53VSE175Ey6T1KBki0VhKoiJyexv0ucKmRFjSyhT3N5K2JAqyoxNJ29D8JZfXiXNcsmrliq3lWKtnMWRg1M4gwvw4BJqcAN1aACDATzDK7w5wnlx3p2PReuak82cwB84nz8P3Y2d</latexit>

x

6

(a) System with communication graph

퐶

<latexit sha1_base64="Yfgfr4NXdGWceHRL8ymbsbhL4xg=">AAACw3icbZFdS8MwFIbT+j2/pl56ExyK9GK0IurlUAQvJzgV1jHS7HSGpWlJUnGU/knv9NeYdp3uwzcEXt7nhJzkBAlnSrvul2WvrK6tb2xu1bZ3dvf26weHzypOJYUOjXksXwOigDMBHc00h9dEAokCDi/B6K7gL+8gFYvFkx4n0IvIULCQUaJN1K9/YyM/gCETGeFsKJy8hmdUoSAiWrKP3Dlzp8v35wqds2JVBM8i94/gJTSBTokWScXmgVPGJfJBDH47K2vKZPqMfr3hNt1SeNl4lWmgSu1+/dMfxDSNQGjKiVJdz010LyNSM8ohr/mpgoTQERlC11hBIlC9rJxBjk9NMsBhLM0WGpfp7ImMREqNo8BUmo7f1CIrwv9YN9XhTS9jIkk1CDq5KEw51jEuBooHTALVfGwMoZKZXjF9I5JQbcZefIK3+ORl83zR9K6al48XjdZt9R2b6BidoHPkoWvUQg+ojTqIWi0rtGIrse/tkS1tPSm1rerMEZqTnf8Ad7+7Gw==</latexit>

⇤

00000

⇤⇤⇤

000

0

⇤⇤

000

00

⇤⇤⇤

0

000

⇤⇤⇤

⇤

0

⇤

0

⇤⇤

(b)

퐴

퐵

matrix with pa-

rameter

<latexit sha1_base64="g8w+t6fLkHKG6v0U9XvvBqtKjgM=">AAACpXicbVFNTwIxEO2u3/iFevTSCKIn0jVGPRq9eDEBA2jCEtItAzZ0u5u2ayQb/pm/wpv/xu66EkDfTJOX96btdBrEgmtDyJfjrqyurW9sbpW2d3b39ssHhx0dJYpBm0UiUi8B1SC4hLbhRsBLrICGgYDnYHyf+c9voDSPZMtMYuiFdCT5kDNqrNQvf2CLahX7AYy4TIOQGsXfp9jDtXyRWh6+X8IFfp2ZO+/ViiR5enNWVvprkyU9c2wsHkTyykyfqT7IwazFarXUL1dIneTAf4lXkAoq0OiXP/1BxJIQpGGCat31SGx6KVWGMwHTkp9oiCkb0xF0LZU0BN1L8ylP8alVBngYKbukwbk6vyOlodaTMLCVtsVXvexl4n9eNzHDm17KZZwYkOznomEisIlw9mV4wBUwIyaWUKa47RWzV6ooM/ZjsyF4y0/+SzoXde+qftm8qNzeFePYRMfoBJ0jD12jW/SAGqiNmHPiPDhN58k9cx/dltv5KXWdYs8RWoDb/wYSeK+6</latexit>

Fig. 1. Example networked LTI system with information constraints.

Example 1.

Consider the networked system in Figure 1(a) where each subsystem

푖

∈ [

]

has

푥

푖

(

푡

) ∈

and

푢

푖

(

푡

) ∈

. For each

푖

, the set

푖

)

contains the subsystems that has a dashed arrow

pointing towards

푥

푖

in the figure. For example,

)

{

}

. Each

퐴

푖푗

and

퐵

푖푗

for

푗

∈N(

푖

)

a scalar. The stacked global dynamics has matrix

퐴

and

퐵

with structure shown in Figure 1(b). The

unknown local parameter

휃

푖

corresponds to the

∗

entries of the

푖

row of

퐴

and

퐵

, while the global

parameter

is a vector containing

∗

entries in matrix

퐴

and

퐵

We now introduce three core assumptions needed for our algorithm and analysis. As we highlight

below, these are standard assumptions in the learning-based control literature.

Assumption 1 (Adversarial disturbances).

∥

푤

(

푡

)

∥

∞

≤

푊

for

(2)

Assumption 2 (Compact Parameter Set).

The network structure

푖

)

for

푖

∈ [

푁

]

is known.

The true system parameter

★

휃

★

, . . .,휃

푁,

★

is an element of a known compact convex set

×···×P

푁

, which is a product space of local parameter sets where

휃

푖,

∗

∈ P

푖

. The known

parameter set is bounded such that there exists a known constant

휅

>

where

∥

[

퐴

(

)

퐵

(

)

]

∥

퐹

≤

휅

for all

∈ P

Assumption 3 (Controllability).

For all

∈ P

(

퐴

(

)

,퐵

(

))

is controllable.

Bounded adversarial disturbances is a common model in the adversarial online learning and

control problems [

]. Since we make no assumptions on how large the bound on the distur-

bance

푊

is, Assumption 1 models a variety of disturbance models, such as bounded and correlated

stochastic noise or state-dependent disturbances such as the linearization and discretization error

for nonlinear continuous dynamics [

]. Moreover, the known bound

푊

can be relaxed to an

unknown parameter

휂

with

휂

≤

푊

for a known constant

푊

to reduce conservatism for large

푊

Assumptions 2 and 3 are standard in the learning-based control literature, e.g., see [

]. We

impose controllability in Assumption 3 for ease of exposition but it can be relaxed to stabilizability

by adjusting the choice of model-based controller to an infinite-horizon controller such as the one

proposed in [89] for the algorithm.

2.1 Stability

One of the fundamental goals for control design is to ensure stability. In this paper, we aim to learn

a stabilizing controller for the networked linear system

(2)

in the sense of input to state stability

(ISS) [

]. ISS is one of the main notions of stability for both linear and nonlinear systems [

Here we adapt the ISS definition to the

ℓ

∞

-norm.

Definition 2.1 (ISS).

A dynamical system of the form

(2)

is said to be input to state stable (ISS) if

there exist functions

훽

→

that is continuous, strictly increasing, and bijective with

Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 26. Publication date: March 2023.

26:6

Jing Yu, Dimitar Ho, and Adam Wierman

respect to the second argument with

lim

푡

→∞

훽

(

푎,푡

)

for all

푎

≥

푡

∈

, and

훾

→

that is

continuous, strictly increasing, and bijective such that for all initial state

푥

(

)

, disturbance sequence

, and time

푡

≥

푡

for

푡

∈

, we have

∥

푥

(

푡

)

∥

∞

≤

훽

(

∥

푥

(

푡

)

∥

∞

,푡

−

푡

훾

(

sup

푡

≥

푡

∥

푤

(

푡

)

∥

∞

)

2.2 Distributed design and information constraints

For large-scale networks such as the power grid with state dimension in the orders of thousands

to millions, it is unrealistic and prohibitively costly for a central agent to learn a global policy

online. A promising remedy is to decompose the global policy learning into a

local

one, where each

subsystem in the network learns a local policy in a distributed fashion. In this work, we propose a

distributed learning-based control algorithm for the networked linear system

(2)

that guarantees

stability of the global system.

In addition to distributed design, networks of the form

(1)

are often modelled with additional

information constraints that require careful consideration. In this work we consider two common

information constraints. The first is

communication delay

, where the dynamical system is endowed

with a communication network that specify delayed information transmission among subsystems.

The second is

local information

, where each subsystem only computes with (delayed) local informa-

tion within a specified neighborhood, and discard information outside of the neighborhood. We

come back to these information constraints and present definitions in Sections 4.1 and 4.2.

2.3 Algorithm preliminaries

Our proposed algorithm makes use of two emerging techniques, one from the learning community,

i.e., nested convex body chasing (NCBC), and one from the control community, i.e., system level

synthesis (SLS). We provide important background on each below before introducing our algorithm

in the next section.

2.3.1 Preliminaries on NCBC.

The Nested Convex Body Chasing (NCBC) problem is a well-studied

online learning problem [

]. At every round

푡

, the player is presented a convex body

푡

⊂

푛

which is nested in the previous body, e.g.,

푡

⊆ K

푡

−

. The player selects a point

푞

푡

∈K

푡

with the

objective of minimizing the total path length of the selection for

푇

rounds, e.g.,

푇

푡

∥

푞

푡

−

푞

푡

∥

There are many algorithms for the NCBC problem such as greedy projection of the previously

selected point onto the current body [

]. Among these, the Steiner point selector has been shown

to achieve optimal competitive ratio against the offline optimal selector [

]. The Steiner point of a

convex body

can be interpreted as the average of the extreme points and is defined as

(K)

푣

∥

푣

∥≤

[

푔

(

푣

)

]

where

푔

(

푣

)

argmax

푥

∈K

푣

⊤

푥

and the expectation is taken with respect to the uniform distribution

over the unit ball. The Steiner point selector achieves the following total path length,

푇

∑︁

푡

∥

푡

)−

푡

)∥ ≤

푛

diam

)

for all

푇

∈

(3)

We note that the Steiner point can be approximated with any accuracy by solving sampling based

linear programs, [12, Algorithm 3].

2.3.2 Preliminaries on SLS.

Even when the dynamics

(1)

is known, it remains challenging to design

distributed and localized control policies that accommodates communication delay and information

constraints due to nonconvexity and computational scalability issues. Motivated by this problem,

[

] introduces the SLS framework that synthesizes distributed controllers by parameterizing

controllers with the closed-loop system responses induced under them. In [

], SLS plays a

central role for model-based learning algorithm design and analysis.

Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 26. Publication date: March 2023.

Online Adversarial Stabilization of Unknown Networked Systems

26:7

We illustrate SLS via a simple example. Consider a fixed static controller

퐾

∈

푛

푢

푛

푥

such

that

푢

(

푡

)

퐾푥

(

푡

)

. Then the system

(2)

has the following closed-loop responses to the exogenous

disturbances

푥

(

푡

)

푡

∑︁

푘

(

퐴

퐵퐾

)

푘

푤

(

푡

−

푘

−

)

, 푢

(

푡

)

푡

∑︁

푘

퐾

(

퐴

퐵퐾

)

푘

푤

(

푡

−

푘

−

)

(4)

where we absorb the initial state

푥

(

)

into

푤

(−

)

. Instead of directly synthesizing

퐾

, SLS optimizes

the linear operators that map

and

. Let

푥

[

푘

]

(

퐴

퐵퐾

)

푘

and

푢

[

푘

]

퐾

(

퐴

퐵퐾

)

푘

. Then

(4)

can be written as

푥

(

푡

)

푡

푘

푥

[

푘

]

푤

(

푡

−

푘

−

)

and

푢

(

푡

)

푡

푘

푢

[

푘

]

푤

(

푡

−

푘

−

)

. In signal

and transfer matrix form,

and

. We call

and

with components

푥

[

푘

]

and

푢

[

푘

]

the

closed-loop responses

. More generally, for a fixed linear causal controller

, the closed

loop dynamics of (2) can be written in signal/transfer matrix notation as

(5)

where

is the block-downshift operator with identity matrices of size

푛

푥

푛

푥

in all the first block

sub-diagonal positions and zeros everywhere else. Operator

are block diagonal matrices with

matrix

퐴

and

퐵

on the diagonal respectively. We can similarly derive the closed-loop responses

→

and

→

from (5) as

(

퐼

−Z(

)

−

(

퐼

−Z(

)

−

Therefore, SLS uses the closed-loop responses

and

as the alternative parameterization for

controller

. The following theorem characterizes an affine subspace of the achievable system

responses

and

under some feedback linear controller

Theorem 2.2 (Adapted from [

]).

For system

(2)

, any linear causal operators

with finite

impulse response of horizon

퐻

and satisfying the following

푥

[

]

퐼,

푥

[

푘

]

퐴

푥

[

푘

퐵

푢

[

푘

]

for

푘

, . . .,퐻

−

(6a)

푥

[

휏

]

for

휏

≥

퐻

(6b)

are closed-loop responses for

(2)

under a stabilizing linear controller

. Moreover, given any linear

causal operators

that satisfy

(6)

, the following SLS controller constructed using

푤

(

푡

)

푥

(

푡

)−

퐻

−

∑︁

푘

푥

[

푘

]

푤

(

푡

−

푘

)

(7a)

푢

(

푡

)

퐻

−

∑︁

푘

푢

[

푘

]

푤

(

푡

−

푘

)

(7b)

with

푤

(

)

푥

(

)

achieves the desired closed-loop response prescribed by

We remark that here we are restricting to the space of linear causal operators with

finite impulse

responses

(FIR) up to horizon

퐻

, instead of the entire space of linear causal operators. The horizon

퐻

is a system-dependent design parameter relating to controllability of

(2)

. Under Assumption

퐻

≤

푛

푥

. Moreover,

(6)

provides affine constraints on finite number of nonzero parameters of

the closed-loop responses. Therefore, one can tractably optimize the closed-loop responses with

respect to a convex cost. A common choice is the Linear Quadratic Regulator (LQR) cost on the

Proc. ACM Meas. Anal. Comput. Syst., Vol. 7, No. 1, Article 26. Publication date: March 2023.