Learning in Networked Control Systems

Though adaptive control [1] of unknown Linear Quadratic Gaussian (LQG) systems [2] is a well-studied topic by now [3, 4, 5, 6], existing algorithms cannot be utilized for controlling an unknown NCS in which plant and network parameters are unknown. In departure from the traditional adaptive controllers for LQG systems, an algorithm now also needs to continually estimate the unknown network behaviour besides simultaneously learning and controlling the plant in an online manner. An important concern is that in general it is not optimal to design and operate network estimator independently of the process controller. Thus, the optimal controls $u(t)$ should utilize the information gained about network quality in addition to using the information gained about plant parameters. Similarly, decisions made by the network scheduler should also “aid” the controller in “learning” the unknown plant parameters.

This work addresses the problem of adaptive control of a simple NCS in which data packets from the controller to the plant, are communicated over an unreliable channel. We model the plant as a LQG system. We propose a learning rule that maintains estimates and confidence sets for both a) (unknown) plant parameters $(A_{(\star)},B_{(\star)})$, and also b) (unknown) channel reliability $p_{(\star)}$. Controls are then generated using the principle of optimism in face of uncertainty [7], and depend upon both a) and b). We denote our algorithm as Upper Confidence Bounds for Networked Control Systems (UCB-NCS).

We show that UCB-NCS yields the same asymptotic performance as the optimal controller that has knowledge of the system and network parameters. We also quantify its finite-time performance by providing upper-bounds on its “regret” [8]. Regret scales as $\tilde{O}\left(C\sqrt{T}\right)$, where $T$ is the operating time horizon and $C$ is a problem dependent constant. It also depends on the channel reliability through a certain quantity which we call the “margin of stability” $\eta$ (14). A larger value of $\eta$ means that the learning algorithm has a lower regret.

UCB-NCS has many appealing properties. For instance, network estimator needs to communicate only occasionally the value of its optimistic estimate of network reliability to the controller which then uses it to generate controls.

We assume that the system of interest is linear, and evolves as follows

where $A_{(\star)}\in\mathbb{R}^{n\times n},B_{(\star)}\in\mathbb{R}^{n\times m}$ are the system matrices, $\ell(t)\in\left\{0,1\right\}$ is the instantaneous state of the wireless channel, and $x(t)\in\mathbb{R}^{n},u(t)\in\mathbb{R}^{m}$ are the system state and control input at time $t$ respectively. $\{\ell(t)\}_{t=1}^{T}$ are Bernoulli i.i.d. with mean value $p_{(\star)}$. $\{w(t)\}_{t=1}^{T}$ is the process noise, and is assumed to be i.i.d. with

The objective is to minimize the operating cost

We let $\theta_{(\star)}:=\left(A_{(\star)},B_{(\star)},p_{(\star)}\right)$ denote the system parameters. $\theta_{(\star)}$ is not known to controller. We assume that the system is scalar, i.e., $m=n=1$.

Note that (1) is a Jump Markov Linear System (JMLS), and if the system parameter $\theta_{(\star)}$ is known, the optimal controls can be obtained by using Dynamic Programming [9].

There are matrices $\left\{K_{\theta_{(\star)}}(\ell)\right\}_{\ell\in\{0,1\}}$ such that the optimal control at $t$ is given by $K_{\theta_{(\star)}}(\ell(t))x(t)$. We let $\left\{K_{\theta}(\ell)\right\}_{\ell\in\{0,1\}}$ denote the optimal matrices when system parameter is equal to $\theta$.

We let $V_{\theta}(x,\ell)$ denote the “cost-to-go” when system state is equal to $x$, channel state is $\ell$ and system dynamics are described by $\theta$. In fact value function is piecewise linear, and we let $\{P_{\theta}(\ell)\}_{\ell\in\{0,1\}}$ denote the corresponding matrices. We also let $J_{\theta}$ be the optimal operating cost.

Notation: For a random variable (r.v.) $X$, let $X_{\mathcal{F}}$ denote its projection onto the space of $\mathcal{F}$ measurable funcions, i.e., its conditional expectation w.r.t. sigma-algebra $\mathcal{F}$. For $x,y\in\mathbb{Z}$²²2$\mathbb{Z}$ denotes the set of integers., we let $[x,y]:=\left\{x,x+1,\ldots,y\right\}$. For a set of r.v. s $\mathcal{X}$, we let $\sigma(\mathcal{X})$ denote the smallest sigma-algebra with respect to which each r.v. in $\mathcal{X}$ is measurable. For functions $f(x),g(x)$, we say $f(x)=O(g(x))$ if $\lim_{x\to\infty}f(x)/g(x)=1$. For a set $\mathcal{X}$, we let $\mathcal{X}^{c}$ denote its complement.

Let $\mathcal{F}_{t}:=\sigma\left(\left\{(x(s),u(s))\right\}_{s=1}^{t-1}\cup\{x(t)\}\right)$. A learning policy, or an adaptive controller is a collection of maps $\left\{\mathcal{F}_{t}\mapsto u(t)\right\}_{t=1}^{T}$. Let $\hat{\theta}(t):=\left(\hat{A}(t),\hat{B}(t),\hat{p}(t),\right)$ denote the estimates of $\theta_{(\star)}=(A_{(\star)},B_{(\star)},p_{(\star)})$ at time $t$ defined as follows. Let $z(s):=x(s+1)$, and $\lambda>0$.

Define

Let $\mathcal{C}(t)=\left(\mathcal{C}_{1}(t),\mathcal{C}_{2}(t),\mathcal{C}_{3}(t)\right)$ be the confidence intervals associated with the estimates $\left(\hat{A}(t),\hat{B}(t),\hat{p}(t)\right)$ at time $t$ defined as follows,

where

The learning rule decomposes the cumulative time into episodes, and implements a single stationary controller within each single episode that chooses $u(t)$ as a function of $x(t)$. Let $\tau_{k}$ denote the starting time of $k$-th episode. The controller implemented within episode $k$ is obtained at time $\tau_{k}$ by solving the following optimization problem.

where $\Theta$ is the set of “allowable” parameters. Let $\theta(\tau_{k})$ denote a solution to above problem. It implements the optimal controller corresponding to the case when true system parameters are equal to $\theta(\tau_{k})$. $u(t)=K_{\theta(\tau_{k})}(\ell(t))x(t)$. Thus, $u(t)=K_{\theta(\tau_{k})}(\ell(t))x(t)$ for $t\in\left[\tau_{k},\tau_{k+1}-1\right]$.

A new episode begins when either $V_{1}(t)$ or $V_{2}(t)$ doubles or the operating time spent in current episode becomes equal to length of previous episode. The learning rule also ensures that the durations of episodes are at least $L$ time-slots, i.e., $\tau_{k+1}-\tau_{k}\geq L$. We set

i.e., it is the current value of the UCB estimate of $\theta_{(\star)}$. UCB-NCS is summarized in Algorithm 1.

We now analyze the estimation errors $e_{1}(t):=\hat{A}(t)-A,e_{2}(t):=\hat{B}(t)-B$.

We now bound $|x(t)|$ under UCB-NCS. System evolution under UCB-NCS is given by

where

Thus,

where

Consider the deviations

and the events,

where $\sigma^{2}_{p_{(\star)}}:=p_{(\star)}(1-p_{(\star)})$, and $\alpha>2$. It follows from Azuma-Hoeffding inequality that

Fix a sufficiently large $L>0$³³3It suffices to let $L>\left(2\alpha\sigma^{2}_{p_{(\star)}}/\epsilon^{2}\right)^{2}$, and define

The following result by combining union bound with the bound (12).

We now focus on upper-bounding $|G(s,t)|$ on $\mathcal{J}$.

Throughout, we assume that the true system parameter $\theta_{(\star)}$, and the set $\Theta$ used by UCB-NCS, satisfy the following.

Consider an element of $\mathcal{J}$, and assume there are $k$ episodes during the time period $[s,t]$. Let $N_{i,k},i=0,1$ denote the number of times channel state assumes value $i$, and let $\theta_{k}$ denote the UCB estimate of $\theta_{(\star)}$ during the $k$-th episode. Let $D_{k}$ denote the duration of $k$-th episode. We have the following,

where the first inequality follows from definition of $\mathcal{J}$ (13), while the second follows from Assumption 1.

Let

Following is easily proved.

Define $R(T)$, the regret incurred by UCB-NCS until time $T$ as follows

For $\theta=(A,B,p)$, define

Similarly, let $\{\ell_{\theta}(t)\}_{t=1}^{T}$ be drawn i.i.d. according to $\theta$.

We now bound the terms $R_{1},R_{2}$ on $\mathcal{E}$.