# Stability Enforced Bandit Algorithms for Channel Selection in Remote State
Estimation of Gauss-Markov Processes

Alex S. Leong, , Daniel E. Quevedo, , and Wanchun Liu,
A. S. Leong is with Defence Science and Technology Group, Melbourne,
Australia. E-mail<EMAIL_ADDRESS>D. E. Quevedo is with the School
of Electrical Engineering and Robotics, Queensland University of Technology,
Brisbane, Australia. E-mail<EMAIL_ADDRESS>W. Liu is with the School of
Electrical and Information Engineering, University of Sydney, Sydney,
Australia. Email<EMAIL_ADDRESS>
###### Abstract

In this paper we consider the problem of remote state estimation of a Gauss-
Markov process, where a sensor can, at each discrete time instant, transmit on
one out of M different communication channels. A key difficulty of the
situation at hand is that the channel statistics are unknown. We study the
case where both learning of the channel reception probabilities and state
estimation is carried out simultaneously. Methods for choosing the channels
based on techniques for multi-armed bandits are presented, and shown to
provide stability. Furthermore, we define the performance notion of estimation
regret, and derive bounds on how it scales with time for the considered
algorithms.

###### Index Terms:

Learning, multi-armed bandits, regret, stability, state estimation

##  I Introduction

The use of machine learning techniques for estimation and control has gained
increasing attention in recent years [1, 2, 3]. Learning based estimation and
control holds the promise of enabling the solution of problems which are
difficult or even intractable using traditional control design techniques.

In this paper we focus on the problem of remote state estimation of a Gauss-
Markov process, where the channel statistics are constant but unknown. As a
motivating example, consider the use of unmanned aerial vehicles (UAVs) for
providing wireless communication capabilities [4, 5], with the UAV acting as a
mobile aerial base station collecting information from wireless sensors. The
use of such systems can allow for monitoring of processes which are difficult
to access otherwise, e.g., in a hostile or contested environment. The UAV
would transmit collected information to a remote estimator via one of $M$
different channels, e.g., using $M$ different frequency bands. Characteristics
of the individual channels can vary substantially at different
locations/environments [4, 6], which makes it difficult to have accurate
knowledge of the channel statistics whenever the UAV moves to a different
location. In this paper we will assume that, at any given location, the
channel statistics are constant but unknown.

Learning of transmission schedules for a single system over a channel with
unknown packet reception probability has been studied in [7], while learning
of power allocations for multiple control systems connected over an unknown
non-stationary channel is considered in [8]. With multiple channels, channel
allocation for multiple processes using deep reinforcement learning have been
considered in [9, 10, 11]. While the use of deep reinforcement learning
techniques can find schedules which perform well, in general stabilizing
properties of the learned policies are not guaranteed. Furthermore, many
training samples may be needed during learning. In this paper, we consider a
remote state estimation where, at every time instant, a sensor or controller
can choose one of $M$ unknown channels for transmission. The aim is to learn
the best channel while guaranteeing stability of the system and being _sample
efficient_ (via maintaining _low regret_).

We will view the channel selection task as a multi-armed bandit type problem
[12, 13]. The multi-armed bandit problem is a simple example of a
reinforcement learning problem which captures the exploration vs. exploitation
tradeoff, between basing decisions only on knowledge currently obtained about
a system (“exploit”) vs. trying out alternative decisions which may
potentially be better (“explore”). Among many applications in a wide variety
of domains, multi-armed bandit techniques have been used to address scheduling
problems in wireless communications [14, 6, 15, 16].

In contrast to classical multi-armed bandit problems, here the underlying
processes are dynamical systems, which raises additional challenges on
stability and performance. In this paper, we will study the use of the
$\varepsilon$-greedy algorithm [17], as well as several algorithms based on
the Thompson Sampling technique [18], to carry out channel selection in the
context of remote state estimation. Thompson Sampling is a sampling based
algorithm for the multi-armed bandit problem, which has been shown to be
optimal with respect to the accumulated regret in certain problems.
Interestingly, Thompson sampling has been previously used to address problems
in stochastic [19, 20] and linear quadratic control [21].

_Summary of contributions_ : The main contributions of the current work are as
follows:

  * •

We propose the use of bandit algorithms for channel selection in the context
of remote state estimation, including a new stability-aware Bayesian sampling
algorithm.

  * •

We prove that the considered algorithms can guarantee stability of the remote
estimation process.

  * •

We study performance of these algorithms by introducing the notion of
estimation regret, and prove that the $\varepsilon$-greedy algorithm has
linear estimation regret, while the sampling based algorithms can achieve
logarithmic estimation regret.

The remainder of the paper is organized as follows: The system model is
provided in Section II. A selection of bandit algorithms for channel selection
are presented in Section III. Stability and performance bounds of these
algorithms are studied in Sections IV and V respectively. Numerical studies
are given in Section VI. Section VII draws conclusions.

_Notation_ : Given a matrix $X$, we say that $X\geq 0$ if $X$ is positive
semi-definite. For matrices $X$ and $Y$, we say that $X\leq Y$ if $Y-X\geq 0$.
The spectral radius of a matrix $X$ is denoted by $\rho(X)$. The beta
distribution with parameters $\alpha$ and $\beta$ is denoted by
$\textnormal{Beta}(\alpha,\beta)$, with expected value
$\alpha/(\alpha+\beta)$. $\mathds{1}(\cdot)$ is the indicator function that
returns 1 if its argument is true and 0 otherwise.

##  II System Model

Figure 1: Remote state estimation over unknown channels

We consider a discrete-time plant described by a Gauss-Markov process:

$x_{k+1}=Ax_{k}+w_{k},$ (1)

with sensor measurements

$y_{k}=Cx_{k}+v_{k},$

where $w_{k}\sim\mathcal{N}(0,Q)$, $v_{k}\sim\mathcal{N}(0,R)$, see Fig. 1.
The sensor runs a local Kalman filter, with local state estimates
$\hat{x}_{k}^{s}\triangleq\mathbb{E}[x_{k}|y_{0},\dots,y_{k}]$ and estimation
error covariances
$P_{k}^{s}\triangleq\mathbb{E}[(x_{k}-\hat{x}_{k}^{s})(x_{k}-\hat{x}_{k}^{s})^{T}|y_{0},\dots,y_{k}]$.
We assume that the pair $(A,C)$ is observable and the pair $(A,Q^{1/2})$ is
controllable, which implies that $P_{k}^{s}$ converges to some $\overline{P}$
as $k\rightarrow\infty$ [22]. We will assume steady state, so that
$P_{k}^{s}=\overline{P},\forall k$.

As depicted in Fig. 1, the local state estimates are transmitted over lossy
channels to a remote estimator. There are $M$ such channels, each i.i.d.
Bernoulli with packet reception probabilities $\theta_{m},m=1,\dots,M$. For
notational simplicity, we will assume that all the packet reception
probabilities are different, i.e., $\theta_{i}\neq\theta_{j},\forall i\neq j$.

At every time step $k$, we can choose one of the $M$ channels to transmit
over. This decision is determined by the remote estimator, which notifies the
sensor via a transmission (Tx) management channel. As the information
transmitted on the transmission management channel is normally only a few bits
in length, we assume that these transmissions are error-free, see also [9].

A key issue is that none of the packet reception probabilities are known.
Ideally, we would like to always use the best channel (i.e., the channel with
the highest packet reception probability). But since the packet reception
probabilities are unknown, this requires us to find/learn the best channel by
trying out different channels and observing their outcomes. The situation
resembles a multi-armed bandit type problem [12, 13], with the channels acting
as the different arms. The difference between the situation considered in this
paper and classical multi-armed bandit problems is that the underlying
estimation process has dynamics. This raises additional issues such as
stability, as investigated in the current work.

Before proceeding, we recall (see, e.g., [23]) that the remote estimator has
estimation error covariance

$P_{k}=\left\\{\begin{array}[]{cc}\overline{P},&\gamma_{k}=1\\\
h(P_{k-1}),&\gamma_{k}=0\end{array}\right.$ (2)

where

$h(X)\triangleq AXA^{\top}+Q.$ (3)

In the above, $\gamma_{k}=1$ means that the transmission at time $k$ was
successful, while $\gamma_{k}=0$ means that the transmission was lost. We
assume that $P_{0}=\overline{P}.$

When $A$ is unstable, we know that if the same channel $m$ is chosen at every
time step, then the remote estimator has bounded expected estimation error
covariance for all $k$ if and only if its packet reception probability
satisfies $\theta_{m}>\theta_{c}$ [24, 25], where

$\theta_{c}\triangleq 1-\frac{1}{\rho(A)^{2}}.$ (4)

Accordingly, in this paper we make the assumption that at least one of the
channels has packet reception probability larger than $\theta_{c}$, i.e.,

$\theta^{*}\triangleq\max_{m}\theta_{m}>\theta_{c}.$ (5)

###  II-A Preliminaries

For later reference, we mention some properties of the operator $h(.)$ defined
in (3).

######  Lemma 1.

The operator $h(.)$ defined in (3) satisfies:
(i) $h(X)\leq h(Y)$ if $X\leq Y$
(ii) $h(\overline{P})\geq\overline{P}$
(iii) $\textnormal{tr}(h(\overline{P}))>\textnormal{tr}(\overline{P})$.

###### Proof.

The proof of (i) follows easily from the definition (3). Proofs of (ii) and
(iii) can be found in [26]. ∎

Note that Lemma 1 implies that $P_{k}\geq\overline{P},\forall k$, for $P_{k}$
evolving according to (2).

The following recursion (6) for the expected error covariances will also be
used later. Let $\theta(k)$ be the reception probability at time $k$. From (2)
we have

$\displaystyle\mathbb{E}[P_{k+1}|P_{k}]$
$\displaystyle=\mathbb{E}[P_{k+1}|P_{k},\gamma_{k}=1]\mathbb{P}(\gamma_{k}=1)$
$\displaystyle\quad+\mathbb{E}[P_{k+1}|P_{k},\gamma_{k}=0]\mathbb{P}(\gamma_{k}=0)$
$\displaystyle=\theta(k)\overline{P}+(1-\theta(k))(AP_{k}A^{\top}+Q).$

Then, since $h(.)$ is linear, we can obtain

$\mathbb{E}[P_{k+1}]=\mathbb{E}[\mathbb{E}[P_{k+1}|P_{k}]]=\theta(k)\overline{P}+(1-\theta(k))h(\mathbb{E}[P_{k}]).$
(6)

##  III Bandit Algorithms for Channel Selection

In this section we present a selection of multi-armed bandit algorithms for
carrying out channel selection, mainly based on the $\varepsilon$-greedy and
Thompson sampling approaches [18]. Thompson sampling is computationally
efficient and can be easily implemented, requiring very little tuning apart
from the choice of a prior distribution. There exist other bandit algorithms
such as those based on the upper confidence bound (UCB) approach, which are
not considered in the current work. Numerical studies however have shown that
in many situations the performance of Thompson sampling is highly competitive
against even well-tuned UCB algorithms [27, 28, 29].

Algorithm 1 $\varepsilon$-greedy

1:Initialize: $\alpha_{m,1}=1,\beta_{m,1}=1,\quad m=1,\dots,M$

2:for $k=1,2,\dots$ do

3: Set
$\hat{\theta}_{m,k}^{\varepsilon}=\frac{\alpha_{m,k}}{\alpha_{m,k}+\beta_{m,k}},\quad
m=1,\dots,M$

4: With probability $\varepsilon>0$, choose $m_{k}^{\varepsilon}$ uniformly
from $\\{1,\dots,M\\},$ else choose111If multiple channels have the same
maximum estimated packet reception probability, then a channel is chosen
uniformly at random from these (maximizing) channels.
$m_{k}^{\varepsilon}=\textnormal{arg}\max_{m}\hat{\theta}_{m,k}^{\varepsilon}$

5: Observe $\gamma_{k}$

6: Update sample means via  $\displaystyle\alpha_{m,k+1}$
$\displaystyle=\alpha_{m,k}+\gamma_{k},$ $\displaystyle\textnormal{ if
}m=m_{k}^{\varepsilon}$ $\displaystyle\beta_{m,k+1}$
$\displaystyle=\beta_{m,k}+1-\gamma_{k},$ $\displaystyle\textnormal{ if
}m=m_{k}^{\varepsilon}$ $\displaystyle\alpha_{m,k+1}$
$\displaystyle=\alpha_{m,k},\,\beta_{m,k+1}=\beta_{m,k},$
$\displaystyle\textnormal{ if }m\neq m_{k}^{\varepsilon}$

###  III-A $\varepsilon$-greedy

We first consider the well-known $\varepsilon$-greedy algorithm [17], which
with probability $\varepsilon>0$ chooses a channel uniformly at random
(“explore”), and with probability $1-\varepsilon$ chooses the channel with the
maximum estimated (via a sample mean) packet reception probability
(“exploit”). After transmitting over this channel and observing $\gamma_{k}$,
i.e., whether the transmission was successful, we update the sample means of
the packet reception probabilities. The procedure is stated in Algorithm 1,
where we have expressed the estimated packet reception probabilities in terms
of the quantities $\alpha_{m,k}$ and $\beta_{m,k}$. These can be regarded as
pseudo-counts of the number of successful and non-successful transmissions
respectively on channel $m$ [18], and are updated using the formulas
$\alpha_{m,k+1}=\alpha_{m,k}+\gamma_{k}$ and
$\beta_{m,k+1}=\beta_{m,k}+1-\gamma_{k}$. This allows us to emphasize
similarities in the implementation with the other algorithms considered below.

###  III-B Thompson Sampling

Thompson sampling is a sampling based approach which draws samples
$\hat{\theta}_{m,k}^{\textnormal{TS}},m=1,\dots,M$ from the posterior
distribution of the unknown packet reception probability of each arm/channel.
The posterior distribution can be shown to have a beta distribution if the
prior distribution is beta distributed [18], as we will assume here. In
particular, the prior beta distribution with
$\alpha_{m,1}=1,\beta_{m,1}=1,\,m=1,\dots,M$ is uniformly distributed in
$[0,1]$. The channel that is selected is then given by

$m^{\textnormal{TS}}_{k}=\textnormal{arg}\max_{m}\hat{\theta}_{m,k}^{\textnormal{TS}}.$

After transmitting over this channel and observing $\gamma_{k}$, the posterior
is then updated to a $\textnormal{Beta}(\alpha_{m,k+1},\beta_{m,k+1})$
distribution, using the same formulas for updating $\alpha_{m,k}$ and
$\beta_{m,k}$ as in Section III-A. The procedure is summarized in Algorithm 2.

Algorithm 2 Thompson Sampling (TS)

1:Initialize: $\alpha_{m,1}=1,\beta_{m,1}=1,\quad m=1,\dots,M$

2:for $k=1,2,\dots$ do

3: Sample
$\hat{\theta}_{m,k}^{\textnormal{TS}}\sim\textnormal{Beta}(\alpha_{m,k},\beta_{m,k}),\quad
m=1,\dots,M$

4: Choose
$m_{k}^{\textnormal{TS}}=\textnormal{arg}\max_{m}\hat{\theta}_{m,k}^{\textnormal{TS}}$
and observe $\gamma_{k}$

5: Update posteriors to $\textnormal{Beta}(\alpha_{m,k+1},\beta_{m,k+1})$ via
$\displaystyle\alpha_{m,k+1}$ $\displaystyle=\alpha_{m,k}+\gamma_{k},$
$\displaystyle\textnormal{ if }m=m_{k}^{\textnormal{TS}}$
$\displaystyle\beta_{m,k+1}$ $\displaystyle=\beta_{m,k}+1-\gamma_{k},$
$\displaystyle\textnormal{ if }m=m_{k}^{\textnormal{TS}}$
$\displaystyle\alpha_{m,k+1}$
$\displaystyle=\alpha_{m,k},\,\beta_{m,k+1}=\beta_{m,k},$
$\displaystyle\textnormal{ if }m\neq m_{k}^{\textnormal{TS}}$

###  III-C Optimistic Bayesian Sampling

In [28] a modification of Thompson sampling called “Optimistic Bayesian
sampling” (OBS) was proposed and studied. Recall that in Thompson sampling, at
time $k$ one would draw samples
$\hat{\theta}_{m,k}^{\textnormal{TS}},m=1,\dots,M$ and then select
$m^{\textnormal{TS}}_{k}=\textnormal{arg}\max_{m}\hat{\theta}_{m,k}^{\textnormal{TS}}.$
In OBS we would also draw samples
$\hat{\theta}_{m,k}^{\textnormal{TS}},m=1,\dots,M$, but now select

$\displaystyle m^{\textnormal{OBS}}_{k}$
$\displaystyle=\textnormal{arg}\max_{m}\hat{\theta}_{m,k}^{\textnormal{OBS}},$

where

$\displaystyle\hat{\theta}_{m,k}^{\textnormal{OBS}}$
$\displaystyle\triangleq\max\left(\hat{\theta}_{m,k}^{\textnormal{TS}},\mathbb{E}[\hat{\theta}_{m,k}^{\textnormal{TS}}]\right)=\max\left(\hat{\theta}_{m,k}^{\textnormal{TS}},\frac{\alpha_{m,k}}{\alpha_{m,k}\\!+\\!\beta_{m,k}}\right).$

The procedure is summarized in Algorithm 3.

Algorithm 3 Optimistic Bayesian Sampling (OBS)

1:Initialize: $\alpha_{m,1}=1,\beta_{m,1}=1,\quad m=1,\dots,M$

2:for $k=1,2,\dots$ do

3: Sample
$\hat{\theta}_{m,k}^{\textnormal{TS}}\sim\textnormal{Beta}(\alpha_{m,k},\beta_{m,k}),\quad
m=1,\dots,M$

4: Set
$\hat{\theta}_{m,k}^{\textnormal{OBS}}=\max\left(\hat{\theta}_{m,k}^{\textnormal{TS}},\frac{\alpha_{m,k}}{\alpha_{m,k}\\!+\\!\beta_{m,k}}\right)$

5: Choose
$m_{k}^{\textnormal{OBS}}=\textnormal{arg}\max_{m}\hat{\theta}_{m,k}^{\textnormal{OBS}}$
and observe $\gamma_{k}$

6: Update posteriors to $\textnormal{Beta}(\alpha_{m,k+1},\beta_{m,k+1})$ via
$\displaystyle\alpha_{m,k+1}$ $\displaystyle=\alpha_{m,k}+\gamma_{k},$
$\displaystyle\textnormal{ if }m=m_{k}^{\textnormal{OBS}}$
$\displaystyle\beta_{m,k+1}$ $\displaystyle=\beta_{m,k}+1-\gamma_{k},$
$\displaystyle\textnormal{ if }m=m_{k}^{\textnormal{OBS}}$
$\displaystyle\alpha_{m,k+1}$
$\displaystyle=\alpha_{m,k},\,\beta_{m,k+1}=\beta_{m,k},$
$\displaystyle\textnormal{ if }m\neq m_{k}^{\textnormal{OBS}}$

The motivation for OBS is to result in increased selection probabilities for
arms which are uncertain [28]. For classical multi-armed bandit problems,
simulations have shown that OBS can outperform Thompson sampling in certain
situations [28, 30].

###  III-D Stability-aware Bayesian Sampling

In the context of selecting channels for the purpose of remote state
estimation of dynamical systems as in (1), it is important to take into
account the long term estimation performance. In particular, the fundamental
bound (4) suggests that, unlike when using OBS, one should not artificially
stimulate the selection probabilities for channels which seem to be poor. More
specifically, if the current mean-estimate
$\alpha_{m,k}/(\alpha_{m,k}+\beta_{m,k})$ of the reception probability is less
than the critical threshold $\theta_{c}$, then it is questionable whether this
channel should be chosen with a probability higher than that prescribed by
Thompson sampling.

Motivated by the above, in this paper, we propose a _stability-aware
modification_ of OBS which uses the OBS sample
$\hat{\theta}_{m,k}^{\textnormal{OBS}}$ only if
$\alpha_{m,k}/(\alpha_{m,k}+\beta_{m,k})>\theta_{c}$, while using the Thompson
sample $\hat{\theta}_{m,k}^{\textnormal{TS}}$ otherwise. The algorithm, here
named _Stability-aware Bayesian Sampling_ (SBS), can thus be characterized by:

$\hat{\theta}_{m,k}^{\textnormal{SBS}}=\eta_{m,k}\hat{\theta}_{m,k}^{\textnormal{OBS}}+(1-\eta_{m,k})\hat{\theta}_{m,k}^{\textnormal{TS}},\quad
m=1,\dots,M$ (7)

and

$m_{k}^{\textnormal{SBS}}=\arg\max_{m}\hat{\theta}_{m,k}^{\textnormal{SBS}},$

where

$\eta_{m,k}=\begin{cases}1&\text{if
$\alpha_{m,k}/(\alpha_{m,k}+\beta_{m,k})>\theta_{c}$}\\\
0&\text{otherwise.}\end{cases}$ (8)

The method is summarized in Algorithm 4.

Algorithm 4 Stability-aware Bayesian Sampling (SBS)

1:Initialize: $\alpha_{m,1}=1,\beta_{m,1}=1,\quad m=1,\dots,M$

2:for $k=1,2,\dots$ do

3: Sample
$\hat{\theta}_{m,k}^{\textnormal{TS}}\sim\textnormal{Beta}(\alpha_{m,k},\beta_{m,k}),\quad
m=1,\dots,M$

4: Set
$\hat{\theta}_{m,k}^{\textnormal{SBS}}=\eta_{m,k}\hat{\theta}_{m,k}^{\textnormal{OBS}}+(1-\eta_{m,k})\hat{\theta}_{m,k}^{\textnormal{TS}}$,
where
$\hat{\theta}_{m,k}^{\textnormal{OBS}}=\max\left(\hat{\theta}_{m,k}^{\textnormal{TS}},\frac{\alpha_{m,k}}{\alpha_{m,k}\\!+\\!\beta_{m,k}}\right)$
and
$\eta_{m,k}=\mathds{1}(\alpha_{m,k}/(\alpha_{m,k}+\beta_{m,k})>\theta_{c})$

5: Choose
$m_{k}^{\textnormal{SBS}}=\textnormal{arg}\max_{m}\hat{\theta}_{m,k}^{\textnormal{SBS}}$
and observe $\gamma_{k}$

6: Update posteriors to $\textnormal{Beta}(\alpha_{m,k+1},\beta_{m,k+1})$ via
$\displaystyle\alpha_{m,k+1}$ $\displaystyle=\alpha_{m,k}+\gamma_{k},$
$\displaystyle\textnormal{ if }m=m_{k}^{\textnormal{SBS}}$
$\displaystyle\beta_{m,k+1}$ $\displaystyle=\beta_{m,k}+1-\gamma_{k},$
$\displaystyle\textnormal{ if }m=m_{k}^{\textnormal{SBS}}$
$\displaystyle\alpha_{m,k+1}$
$\displaystyle=\alpha_{m,k},\,\beta_{m,k+1}=\beta_{m,k},$
$\displaystyle\textnormal{ if }m\neq m_{k}^{\textnormal{SBS}}$

##  IV Stability of Remote State Estimation with Channel Selection

In this section, we show that the $\varepsilon$-greedy algorithm will ensure
stability of the remote estimator, provided the exploration rate $\varepsilon$
is not too high, while all of the sampling based channel selection schemes
presented in the previous section (Thompson sampling, OBS, and SBS) will
ensure stability. It is important to emphasize that Theorems 1 and 2, stated
below, cover the challenging case where channel qualities are unknown, and
where channel selection and learning are done in real-time.

Let $m_{k}$ be the channel chosen at time $k$, and define

$m^{*}\triangleq\textnormal{argmax}_{m}\theta_{m}.$

######  Theorem 1.

Suppose condition (5) holds. Then under the $\varepsilon$-greedy algorithm,
the expected estimation error covariance $\mathbb{E}[P_{k}]$ is bounded for
all $k$ if and only if

$0<\varepsilon<\frac{\theta^{*}-\theta_{c}}{\theta^{*}-\frac{1}{M}\sum_{m=1}^{M}\theta_{m}}.$
(9)

###### Proof.

Because of the exploration phase, where with probability $\varepsilon>0$ a
channel is chosen randomly, it is easy to see that each channel will be
accessed infinitely often. Hence the estimates of the packet reception
probabilities for each of the channels will converge to their true values as
$k\rightarrow\infty$. Thus, during the exploitation phase we have

$\mathbb{P}(m_{k}=m^{*}|\textnormal{exploit})\rightarrow 1\textnormal{ as
}k\rightarrow\infty,$

while during the exploration phase we have

$\mathbb{P}(m_{k}=m^{*}|\textnormal{explore})=\frac{1}{M}.$

Then, given any $\delta>0$, there exists a $K(\delta)<\infty$ such that

$\mathbb{P}(\textnormal{reception at time
}k)\geq(1-\varepsilon)\theta^{*}(1-\delta)+\frac{\varepsilon}{M}\sum_{m=1}^{M}\theta_{m}$

for all $k>K(\delta)$. Now let

$\theta^{\prime}\triangleq(1-\varepsilon)\theta^{*}(1-\delta)+\frac{\varepsilon}{M}\sum_{m=1}^{M}\theta_{m}.$

For $k>K(\delta)$, we have by Lemma 1 and a similar derivation to (6)

$\mathbb{E}[P_{k+1}]\leq\theta^{\prime}\overline{P}+(1-\theta^{\prime})h(\mathbb{E}[P_{k}]).$

By induction, it follows that $\\{\mathbb{E}[P_{k}]\\}$ will be upper bounded
by a sequence $\\{V_{k}\\}$ defined by

$\displaystyle V_{k}$ $\displaystyle=\mathbb{E}[P_{k}],\quad k\leq K(\delta)$
$\displaystyle V_{k+1}$
$\displaystyle=\theta^{\prime}\overline{P}+(1-\theta^{\prime})h(V_{k}),\quad
k\geq K(\delta).$

The sequence $\\{V_{k}\\}$ converges if and only if
$\theta^{\prime}>\theta_{c}$. If

$(1-\varepsilon)\theta^{*}+\frac{\varepsilon}{M}\sum_{m=1}^{M}\theta_{m}>\theta_{c},$
(10)

then one can always find a sufficiently small $\delta>0$ to satisfy
$\theta^{\prime}>\theta_{c}$. As (10) is equivalent to the condition (9), this
proves the “if” direction of the theorem.

For the “only if” direction, first define

$\tilde{\theta}\triangleq\theta^{*}(1-\varepsilon)+\frac{\varepsilon}{M}\sum_{m=1}^{M}\theta_{m},$
(11)

and note that, for a given $\varepsilon$,

$\mathbb{P}(\textnormal{reception at time }k)\leq\tilde{\theta}$

holds, because $\tilde{\theta}$ is the reception probability assuming the
optimal $m^{*}$ is always chosen during the exploitation phase. If
$\varepsilon\geq(\theta^{*}-\theta_{c})/(\theta^{*}-\frac{1}{M}\sum_{m=1}^{M}\theta_{m})$,
then $\mathbb{P}(\textnormal{reception at time
}k)\leq\tilde{\theta}\leq\theta_{c}$, and thus

$\mathbb{E}[P_{k+1}]\geq\theta_{c}\overline{P}+(1-\theta_{c})h(\mathbb{E}[P_{k}]).$

Define a sequence $\\{\tilde{V}_{k}\\}$ by

$\tilde{V}_{k+1}=\theta_{c}\overline{P}+(1-\theta_{c})h(\tilde{V}_{k}),$

which from the definition of $\theta_{c}$ is a divergent sequence. An
induction argument shows that $\mathbb{E}[P_{k}]\geq\tilde{V}_{k},\forall k$.
This implies that $\mathbb{E}[P_{k}]$ also diverges and completes the proof. ∎

######  Remark 1.

If
$(\theta^{*}-\theta_{c})/(\theta^{*}-\frac{1}{M}\sum_{m=1}^{M}\theta_{m})>1$,
then Theorem 1 establishes that the $\varepsilon$-greedy algorithm provides
estimation stability for all $\varepsilon>0$.

We next consider stability of the sampling based algorithms. We first give a
preliminary result.

######  Lemma 2.

Under i) Thompson sampling, ii) OBS, and iii) SBS, all channels will be used
infinitely often, and

$\mathbb{P}(m_{k}=m^{*})\rightarrow 1\textnormal{ as }k\rightarrow\infty.$
(12)

###### Proof.

For Thompson sampling and OBS, this is proved in [28] (see also [27] for the
two armed bandit case under Thompson sampling). For SBS we note that, in view
of (7), it holds that
$\hat{\theta}_{m,k}^{\textnormal{TS}}\leq\hat{\theta}_{m,k}^{\textnormal{SBS}}\leq\hat{\theta}_{m,k}^{\textnormal{OBS}}$.
Thus, intuitively (12) should also hold, as SBS in a sense lies in between
Thompson sampling and OBS (and convergence holds for both of these schemes). A
rigorous proof of Lemma 2 for SBS can be given using similar arguments as in
[28]. The details are omitted for brevity. ∎

######  Theorem 2.

Suppose condition (5) holds. Then under i) Thompson sampling, ii) OBS, and
iii) SBS, the expected error covariance $\mathbb{E}[P_{k}]$ is bounded for all
$k$.

###### Proof.

From Lemma 2, we know that under all three sampling based schemes, given any
$\delta>0$, there exists a $K(\delta)<\infty$ such that

$\mathbb{P}(\textnormal{reception at time }k)\geq\theta^{*}(1-\delta),\forall
k>K(\delta).$

Pick a sufficiently small $\delta$ such that
$\theta^{\prime}\triangleq\theta^{*}(1-\delta)>\theta_{c}$ still holds. Then
for $k>K(\delta)$, we have by Lemma 1 and a similar derivation to (6) that

$\mathbb{E}[P_{k+1}]\leq\theta^{\prime}\overline{P}+(1-\theta^{\prime})h(\mathbb{E}[P_{k}]).$

Define a sequence $\\{V_{k}\\}$ by

$\displaystyle V_{k}$ $\displaystyle=\mathbb{E}[P_{k}],\quad k\leq K(\delta)$
$\displaystyle V_{k+1}$
$\displaystyle=\theta^{\prime}\overline{P}+(1-\theta^{\prime})h(V_{k}),\quad
k\geq K(\delta).$

Using an induction argument, we can show that $V_{k}$ upper bounds
$\mathbb{E}[P_{k}]$ for all $k$. Since $\theta^{\prime}>\theta_{c}$, the
sequence $\\{V_{k}\\}$ converges, and in particular $V_{k}$ is bounded for all
$k$. Hence $\mathbb{E}[P_{k}]$ is also bounded for all $k$. ∎

######  Remark 2.

Suppose the system matrix $A$, and hence $\theta_{c}$, is not known exactly,
but we believe $\theta_{c}$ to be equal to $\hat{\theta}_{c}$. Then in Line 4
of Algorithm 4 we would replace $\theta_{c}$ by $\hat{\theta}_{c}$. However,
even with an incorrect value $\hat{\theta}_{c}$, we still have
$\hat{\theta}_{m,k}^{\textnormal{TS}}\leq\hat{\theta}_{m,k}^{\textnormal{SBS}}\leq\hat{\theta}_{m,k}^{\textnormal{OBS}}$
and Lemma 2 would still hold. Hence SBS guarantees stability even for an
incorrect $\hat{\theta}_{c}$, provided condition (5) holds for the true
$\theta_{c}$.

##  V Performance Bounds

In the multi-armed bandit literature, it is common to analyze the performance
of an algorithm via the notion of _regret_ [12, 13], which is defined as the
difference between the expected cumulative reward from always playing the
optimal arm and the expected cumulative reward using a particular bandit
algorithm. The $\varepsilon$-greedy algorithm when applied to the standard
multi-armed bandit problem is well known to achieve linear regret. More
sophisticated algorithms which can achieve logarithmic regret (which, in a
sense, is best possible [31]) include UCB [32], $\varepsilon$-greedy with a
carefully chosen decaying exploration probability [32], and Thompson sampling
[33, 34].

For the remote estimation problem at hand, it is convenient to regard the
trace of the estimation error covariance $\textnormal{tr}P_{k}$ as a _cost_ ,
or alternatively regard $-\textnormal{tr}P_{k}$ as a _reward_ , see also [9].
Motivated by the notion of regret in standard multi-armed bandit problems, in
this paper we define the _estimation regret_ over a horizon $T$ for the remote
state estimation problem as

$\begin{split}\textnormal{regret}^{E}(T)&\triangleq\sum_{k=1}^{T}\big{(}-\textnormal{tr}\mathbb{E}[P_{k}^{*}]-(-\textnormal{tr}\mathbb{E}[P_{k}])\big{)}\\\
&=\sum_{k=1}^{T}\textnormal{tr}(\mathbb{E}[P_{k}]-\mathbb{E}[P_{k}^{*}]).\end{split}$
(13)

In (13), $\mathbb{E}[P_{k}^{*}]$ is the expected error covariance assuming
that the optimal channel $m^{*}$ is always chosen, and $\mathbb{E}[P_{k}]$ is
the expected error covariance when using a particular channel selection
algorithm. Thus, (13) constitutes a measure of the degree of suboptimality
incurred from using a particular algorithm. Stationary and transient
performance of an algorithm can be quantified by inspecting how fast the
regret grows in relation to the horizon length $T$.

To state our results, we first recall some order notation.

######  Definition 1.

Given functions $f(.)$ and $g(.)$, we say that $f(T)=O(g(T))$ if there exist
constants $c$ and $T_{0}$, such that $|f(T)|\leq cg(T),\forall T\geq T_{0}$.
We say that $f(T)=\Omega(g(T))$ if $g(T)=O(f(T))$, and that
$f(T)=\Theta(g(T))$ if both $f(T)=O(g(T))$ and $f(T)=\Omega(g(T))$. We say
that $f(T)=o(g(T))$ if $\lim_{T\rightarrow\infty}f(T)/g(T)=0$.

For $\varepsilon$-greedy, the estimation regret scales linearly with $T$.

######  Theorem 3.

Suppose conditions (5) and (9) hold. Then under the $\varepsilon$-greedy
algorithm, we have

$\textnormal{regret}^{E}(T)=\Theta(T).$

###### Proof.

We first show that $\textnormal{regret}^{E}(T)=O(T)$. By Theorem 1, there
exists some bounded $\mathcal{P}^{\varepsilon}$ such that

$\mathbb{E}[P_{k}]\leq\mathcal{P}^{\varepsilon},\quad\forall k.$

We have

$\displaystyle\textnormal{regret}^{E}(T)$
$\displaystyle=\sum_{k=1}^{T}\textnormal{tr}(\mathbb{E}[P_{k}]-\mathbb{E}[P_{k}^{*}])$
$\displaystyle\leq\sum_{k=1}^{T}\textnormal{tr}\mathbb{E}[P_{k}]$
$\displaystyle\leq\textnormal{tr}(\mathcal{P}^{\varepsilon})T=O(T).$

We now show that $\textnormal{regret}^{E}(T)=\Omega(T)$. Recall the definition
$\tilde{\theta}$ from (11). Note that we have

$\displaystyle\mathbb{E}[P_{k}]$
$\displaystyle\geq\tilde{\theta}\overline{P}+(1-\tilde{\theta})h(\mathbb{E}[P_{k-1}])\geq\tilde{\theta}\overline{P}+(1-\tilde{\theta})h(\mathbb{E}[P_{k-1}^{*}]),$
$\displaystyle\mathbb{E}[P_{k}^{*}]$
$\displaystyle=\theta^{*}\overline{P}+(1-\theta^{*})h(\mathbb{E}[P_{k-1}^{*}]).$

Then

$\displaystyle\textnormal{tr}(\mathbb{E}[P_{k}]-\mathbb{E}[P_{k}^{*}])$
$\displaystyle\geq\textnormal{tr}\big{(}(\theta^{*}-\tilde{\theta})(h(\mathbb{E}[P_{k-1}^{*}])-\overline{P})\big{)}$
$\displaystyle\geq(\theta^{*}-\tilde{\theta})\min_{k\geq
1}\textnormal{tr}\big{(}h(\mathbb{E}[P_{k-1}^{*}])-\overline{P}\big{)}$
$\displaystyle\triangleq r.$ (14)

By the definition (11) and Lemma 1, we have $r>0$. Hence

$\displaystyle\textnormal{regret}^{E}(T)$
$\displaystyle=\sum_{k=1}^{T}\textnormal{tr}(\mathbb{E}[P_{k}]-\mathbb{E}[P_{k}^{*}])$
$\displaystyle\geq rT=\Omega(T).$

∎

For the Bernoulli bandit problem with per stage rewards in $\\{0,1\\}$, it is
known that the regret scales logarithmically with $T$ under Thompson sampling
[33, 34]. An “age-of-information regret” measure was recently considered in
[29], where the per stage cost is unbounded, and can increase by (at most) one
at every time step. It is shown that this age-of-information regret also
scales logarithmically with $T$. In the current work, it follows from (3) that
the per stage cost $\mathbb{E}[P_{k}]$ (or reward $-\mathbb{E}[P_{k}]$) may
also become unbounded, and furthermore can increase at an exponential rate.
Interestingly, for the estimation regret introduced in (13), a bound that is
logarithmic in $T$ still holds.

Let us refer to sub-optimal channels as those whose packet reception
probabilities are not equal to the optimal $\theta^{*}$. We begin with a
preliminary result.

######  Lemma 3.

Let $N_{\textnormal{sub}}(T)$ denote the number of uses of sub-optimal
channels over horizon $T$. Then, under i) Thompson sampling, ii) OBS, and iii)
SBS, we have

$\mathbb{E}[N_{\textnormal{sub}}(T)]=\Theta(\log T).$

###### Proof.

The property that $\mathbb{E}[N_{\textnormal{sub}}(T)]=O(\log T)$ is shown for
Thompson sampling in [33, 34]. The corresponding result for OBS is proved in
[30], based on similar arguments as in [33]. For SBS,
$\mathbb{E}[N_{\textnormal{sub}}(T)]=O(\log T)$ can be shown by making use of
the relation
$\hat{\theta}_{m,k}^{\textnormal{TS}}\leq\hat{\theta}_{m,k}^{\textnormal{SBS}}\leq\hat{\theta}_{m,k}^{\textnormal{OBS}}$
and the arguments of [30]. The (rather lengthy) details are omitted for
brevity.

We next recall a result from [31], namely that any policy with
$\mathcal{R}(T)=o(T^{a})$ for every $a>0$ satisfies
$\mathbb{E}[N_{\textnormal{sub}}(T)]=\Omega(\log T)$, where
$\mathcal{R}(T)\triangleq\mathbb{E}\big{[}\sum_{k=1}^{T}(\theta^{*}-\theta(k))\big{]}$
is the classical notion of regret for the Bernoulli bandit problem, see e.g.
[33, 34]. Since for Thompson sampling, OBS, and SBS, we have

$\mathcal{R}(T)=O\big{(}\mathbb{E}[N_{\textnormal{sub}}(T)]\big{)}=O(\log
T)=o(T^{a}),\,\forall a>0,$

where the first equality follows from standard arguments [33, 34] and the
second equality is what we have just shown, the property
$\mathbb{E}[N_{\textnormal{sub}}(T)]=\Omega(\log T)$ therefore holds for all
three schemes. ∎

Figure 2: Channel selection based on schedule $\mathcal{A}$, where ‘w’ and ‘b’
refer to the worst and the best channel selection, respectively.

######  Theorem 4.

Suppose that condition (5) holds. Then under i) Thompson sampling, ii) OBS,
and iii) SBS, we have

$\textnormal{regret}^{E}(T)=\Theta(\log T).$

Before giving the formal proof of this result, we first provide a sketch of
the proof strategy for the upper bound $\textnormal{regret}^{E}(T)=O(\log T)$.
Following the idea of [29], which showed a logarithmic bound for the age-of-
information regret, we will upper bound the estimation regret with the regret
that is achieved using an alternative schedule, say $\mathcal{A}$, that
replaces all uses of sub-optimal channels with the worst channel. In [29],
this schedule $\mathcal{A}$ is then further upper bounded by a “worst-case”
schedule $\mathcal{B}$ that groups all the uses of the worst channel together.
However, for the problem at hand, as the expected error covariance can
increase exponentially fast if the worst channel does not stabilize the remote
estimator, this argument will give the desired logarithmic regret bound only
in problem instances where the worst channel (and hence all channels) is
stabilizing. To cover more interesting and challenging situations, to
establish Theorem 4, we will consider a division of the time interval into
“epochs” separated by successive uses of the worst channel, see Fig. 2.
Through a careful analysis, we will show that the accumulated regret within
each epoch is bounded, while the expected number of epochs is logarithmic in
$T$. As a consequence the required logarithmic regret upper bound is
established. The detailed proof of Theorem 4 now follows.

###### Proof.

We will first prove that $\textnormal{regret}^{E}(T)=O(\log T)$. Define the
reception probability of the worst channel as

$\theta_{w}\triangleq\min_{m}\theta_{m}.$

Given any schedule of channel selections, let schedule $\mathcal{A}$ denote an
alternative schedule which replaces all uses of sub-optimal channels with the
worst channel. Let $\mathbb{E}[P_{k}^{\mathcal{A}}]$ be the expected error
covariance under this replacement procedure. Then from (6) and Lemma 1, we can
easily show that
$\mathbb{E}[P_{k}]\leq\mathbb{E}[P_{k}^{\mathcal{A}}],\,\forall k.$ In
particular,

$\sum_{k=1}^{T}\textnormal{tr}\mathbb{E}[P_{k}]\leq\sum_{k=1}^{T}\textnormal{tr}\mathbb{E}[P_{k}^{\mathcal{A}}].$
(15)

Then, we have

$\text{regret}^{E}(T)\leq\text{regret}^{\mathcal{A}}(T)\triangleq\sum_{k=1}^{T}\text{tr}\left(\mathbb{E}[P^{\mathcal{A}}_{k}]-\mathbb{E}[P^{*}_{k}]\right).$
(16)

Thus, we only need to prove that $\text{regret}^{\mathcal{A}}(T)=O(\log T)$.

Let $k^{w}_{i}\in\mathbb{N},i\geq 1$ denote the time index of the $i$th usage
of the worst channel based on schedule $\mathcal{A}$. The time horizon is
divided by $\\{k^{w}_{i}\\}$ into epochs, as illustrated in Fig. 2. The $i$th
epoch starts from $k^{w}_{i}$ and ends before $k^{w}_{i+1}$, and is of epoch
length $\ell_{i}\triangleq k^{w}_{i+1}-k^{w}_{i}\geq 1$. Note that $\ell_{i}$
is a random process with a time-varying distribution due to the bandit
algorithms. We define

$\Delta^{w}_{i}\triangleq\mathbb{E}[P^{\mathcal{A}}_{k^{w}_{i}}]-\mathbb{E}[P^{*}_{k^{w}_{i}}]$
(17)

as the gap between the expected estimation error covariances achieved by
schedule $\mathcal{A}$ and the persistent schedule of the best channel.

Let $k^{b}_{i,j}\in\mathbb{N},i,j\geq 1$ denote the time index based on
schedule $\mathcal{A}$ of the $j$th usage of the best channel in epoch $i$,
when the epoch length $\ell_{i}>1$ (see Fig. 2). Let
$k^{b}_{0,j}\in\mathbb{N},j\geq 1$ denote the time index of the $j$th usage of
the best channel before the first epoch and $\ell_{0}$ denote the total number
of time slots before the first epoch. Then, we define

$\Delta^{b}_{i,j}\triangleq\mathbb{E}[P^{\mathcal{A}}_{k^{b}_{i,j}}]-\mathbb{E}[P^{*}_{k^{b}_{i,j}}],i\geq
0,j\geq 1,\text{ if }\ell_{i}>1.$ (18)

In particular, we have $\Delta^{b}_{i,j}=0$ when $i=0$, since schedule
$\mathcal{A}$ is identical to the persistent schedule of the best channel
before the first epoch.

We use random variable $N_{w}$ to denote the number of uses of the worst
channel within a time interval of length $T$. Then,
$\text{regret}^{\mathcal{A}}(T)$ in (16) can be upper bounded as

$\displaystyle\text{regret}^{\mathcal{A}}(T)$
$\displaystyle\leq\\!\mathbb{E}\\!\\!\left[\sum_{j=1}^{\ell_{0}-1}\\!\\!\text{tr}\Delta^{b}_{0,j}+\\!\sum_{i=1}^{N_{w}}\left(\text{tr}\Delta^{w}_{i}+\sum_{j=1}^{\ell_{i}-1}\\!\text{tr}\Delta^{b}_{i,j}\right)\right]\\!\\!$
(19)
$\displaystyle=\mathbb{E}\\!\\!\left[\\!\sum_{i=1}^{N_{w}}\left(\text{tr}\Delta^{w}_{i}+\sum_{j=1}^{\ell_{i}-1}\\!\text{tr}\Delta^{b}_{i,j}\right)\right],$

where the expectation is over $N_{w}$ and $\\{\ell_{i}\\}$. To prove the
desired result, we will analyze
$\left(\text{tr}\Delta^{w}_{i}+\sum_{j=1}^{\ell_{i}-1}\text{tr}\Delta^{b}_{i,j}\right)$
first.

_Analysis of per epoch regret_ : By applying the estimation error covariance
updating rule (2) into (18), we have

$\displaystyle\Delta^{b}_{i,j}$
$\displaystyle=(1-\theta^{*})h(\mathbb{E}[P^{\mathcal{A}}_{k^{b}_{i,j}-1}])+\theta^{*}\overline{P}$
(20)
$\displaystyle\quad-\left((1-\theta^{*})h(\mathbb{E}[P^{*}_{k^{b}_{i,j}-1}])+\theta^{*}\overline{P}\right)$
$\displaystyle=(1-\theta^{*})A\left(\mathbb{E}[P^{\mathcal{A}}_{k^{b}_{i,j}-1}]-\mathbb{E}[P^{*}_{k^{b}_{i,j}-1}]\right)A^{\top}.$

For the time slots in epoch $i$ when $\ell_{i}>1$, it directly follows that

$\Delta^{b}_{i,j}=(1-\theta^{*})^{j}A^{j}\Delta^{w}_{i}(A^{j})^{\top},1\leq
j\leq\ell_{i}-1.$ (21)

Applying the trace operator to inequality (21), it can be obtained that

$\displaystyle\text{tr}\Delta^{b}_{i,j}$
$\displaystyle=(1-\theta^{*})^{j}\text{tr}\left(A^{j}\Delta^{w}_{i}(A^{j})^{\top}\right)$
(22)
$\displaystyle\leq(1-\theta^{*})^{j}\text{tr}((A^{j})^{\top}A^{j})\text{tr}\Delta^{w}_{i}$
(23)
$\displaystyle\leq\kappa_{1}(\epsilon)(1-\theta^{*})^{j}(\rho(A)+\epsilon)^{2j}\text{tr}\Delta^{w}_{i}$
(24)

where $\epsilon>0$ is arbitrary and $\kappa_{1}(\epsilon)>0$. Inequality (23)
is due to the property that $\text{tr}(UV)\leq\text{tr}(U)\text{tr}(V)$ for
any positive semidefinite matrices $U$ and $V$, see e.g. [35, p.445].
Inequality (24) is due to the fact that $\text{tr}((A^{j})^{\top}A^{j})$ is
the sum of squares of all elements of $A^{j}$, and is obtained based on the
lemma below about the element-wise bounds of matrix powers [36, Lemma 2]:

######  Lemma 4.

Consider a $z$-by-$z$ matrix $Z$, and let $[Z]_{i,i^{\prime}}$ denote the
element at the $i$th row and $i^{\prime}$th column of $Z$.

(i) For any $\epsilon>0$, there exists a $\kappa_{1}(\epsilon)>0$ such that
$\big{|}[Z^{j}]_{i,i^{\prime}}\big{|}^{2}\leq\kappa_{1}(\epsilon)(\rho(Z)+\epsilon)^{2j},\forall
i,i^{\prime}\in\\{1,\dots,z\\}$.

(ii) There exist $\kappa_{2}>0$ and $L\in\mathbb{N}$ such that
$\big{|}[Z^{j}]_{i,i^{\prime}}\big{|}^{2}$ is periodically lower bounded by
$\kappa_{2}\rho(Z)^{2j}$ with period $L$.

From assumption (5), we can find a sufficiently small $\epsilon$ such that
$(1-\theta^{*})(\rho(A)+\epsilon)^{2}<1$. Using the inequality (24), we obtain

$\sum_{j=1}^{\ell_{i}-1}\text{tr}\Delta^{b}_{i,j}\leq\frac{\kappa_{1}(\epsilon)\text{tr}\Delta^{w}_{i}}{1-(1-\theta^{*})(\rho(A)+\epsilon)^{2}}.$
(25)

Therefore, the regret of epoch $i$ is bounded as

$\text{tr}\Delta^{w}_{i}+\sum_{j=1}^{\ell_{i}-1}\\!\text{tr}\Delta^{b}_{i,j}\leq\kappa(\epsilon)\text{tr}\Delta^{w}_{i},$
(26)

where $\kappa(\epsilon)\triangleq
1+\frac{\kappa_{1}(\epsilon)}{1-(1-\theta^{*})(\rho(A)+\epsilon)^{2}}>0$.

_Analysis of $\textnormal{tr}\Delta^{w}_{i}$_: By applying the estimation
error covariance updating rule (2) into (17), we have

$\displaystyle\Delta^{w}_{i}$
$\displaystyle=(1-\theta_{w})h(\mathbb{E}[P^{\mathcal{A}}_{k^{w}_{i}-1}])+\theta_{w}\overline{P}$
(27)
$\displaystyle\quad-\left((1-\theta^{*})h(\mathbb{E}[P^{*}_{k^{w}_{i}-1}])+\theta^{*}\overline{P}\right)$
$\displaystyle\leq(1-\theta_{w})h(\mathbb{E}[P^{\mathcal{A}}_{k^{w}_{i}-1}])+\theta_{w}\overline{P}$
$\displaystyle=(1-\theta_{w})h(\mathbb{E}[P^{\mathcal{A}}_{k^{w}_{i}-1}]-\mathbb{E}[P^{*}_{k^{w}_{i}-1}])$
$\displaystyle\quad+(1-\theta_{w})h(\mathbb{E}[P^{*}_{k^{w}_{i}-1}])+\theta_{w}\overline{P}$
$\displaystyle\leq(1-\theta_{w})A(\mathbb{E}[P^{\mathcal{A}}_{k^{w}_{i}-1}]-\mathbb{E}[P^{*}_{k^{w}_{i}-1}])A^{\top}+G$

where
$G\triangleq(1-\theta_{w})\left(A\mathcal{P}A^{\top}+Q\right)+\theta_{w}\overline{P}$,
and $\mathcal{P}$ is a bound on $\mathbb{E}[P^{*}_{k}]$ which exists due to
the stability condition (5).

Next, using a similar argument as in the proof of Theorem 2, we note that the
expected error covariances $\\{\mathbb{E}[P^{\mathcal{A}}_{k}]\\}$ are bounded
by a positive semidefinite matrix $\mathcal{P}^{\prime}$ for all $k$. From
(27), it directly follows that
$\Delta^{w}_{i}\leq(1-\theta_{w})A\mathcal{P}^{\prime}A^{\top}+G$. Then, we
can find a positive constant $\xi$ such that

$\text{tr}\Delta^{w}_{i}\leq\xi,\forall i.$ (28)

By taking (26) and (28) into (19) and using Lemma 3,

$\displaystyle\text{regret}^{E}(T)$
$\displaystyle\leq\text{regret}^{\mathcal{A}}(T)$
$\displaystyle\leq\mathbb{E}\\!\\!\left[\sum_{i=1}^{N_{w}}\kappa(\epsilon)\xi\right]=\kappa(\epsilon)\xi\mathbb{E}[N_{w}]=O(\log
T).$

To conclude, we now prove that $\textnormal{regret}^{E}(T)=\Omega(\log T)$. We
have

$\displaystyle\textnormal{regret}^{E}(T)$
$\displaystyle=\sum_{k=1}^{T}\textnormal{tr}(\mathbb{E}[P_{k}]-\mathbb{E}[P_{k}^{*}])$
$\displaystyle=\mathbb{E}\bigg{[}\sum_{k=1}^{T}\textnormal{tr}(\mathbb{E}[P_{k}]-\mathbb{E}[P_{k}^{*}])\mathds{1}(\theta(k)=\theta^{*})$
$\displaystyle\quad+\sum_{k=1}^{T}\textnormal{tr}(\mathbb{E}[P_{k}]-\mathbb{E}[P_{k}^{*}])\mathds{1}(\theta(k)\neq\theta^{*})\bigg{]}$
$\displaystyle\geq\mathbb{E}\bigg{[}\sum_{k=1}^{T}\textnormal{tr}(\mathbb{E}[P_{k}]-\mathbb{E}[P_{k}^{*}])\mathds{1}(\theta(k)\neq\theta^{*})\bigg{]}.$

Let $\theta^{\circ}$ denote the second largest packet reception probability.
When $\theta(k)\neq\theta^{*}$, we can show similar to (14) that

$\displaystyle\textnormal{tr}(\mathbb{E}[P_{k}]-\mathbb{E}[P_{k}^{*}])$
$\displaystyle\geq\textnormal{tr}\big{(}(\theta^{*}-\theta^{\circ})(h(\mathbb{E}[P_{k-1}^{*}])-\overline{P})\big{)}$
$\displaystyle\geq(\theta^{*}-\theta^{\circ})\min_{k\geq
1}\textnormal{tr}\big{(}h(\mathbb{E}[P_{k-1}^{*}])-\overline{P}\big{)}$
$\displaystyle\triangleq r^{\circ}>0.$

Thus

$\displaystyle\textnormal{regret}^{E}(T)$ $\displaystyle\geq
r^{\circ}\mathbb{E}\bigg{[}\sum_{k=1}^{T}\mathds{1}(\theta(k)\neq\theta^{*})\bigg{]}$
$\displaystyle=r^{\circ}\mathbb{E}[N_{\textnormal{sub}}(T)]$
$\displaystyle=\Omega(\log T),$

where the last line follows from Lemma 3. This completes the proof that
$\textnormal{regret}^{E}(T)=\Omega(\log T)$, and hence establishes Theorem 4.
∎

######  Remark 3.

We note that some works on learning based control have made assumptions that
the underlying system is stable [37], or can be stabilized for all possible
controls [21], when carrying out a regret analysis. This stands in contrast to
Theorem 4, stated above, which merely requires that at least one of the $M$
channels is stabilizing for the remote estimator. Our result thus considers
scenarios where some of the sub-optimal channels can cause the expected error
covariance to diverge if they are used too often.

##  VI Numerical Studies

Figure 3: Learning using Stability-aware Bayesian Sampling

We consider a situation with $M=4$ channels. Figure 3 illustrates how
Stability-aware Bayesian sampling (SBS) learns, and increasingly uses, the
optimal channel, for a situation where

$A=\begin{bmatrix}1.5&0.2\\\ 0.3&0.9\end{bmatrix},\quad
C=\begin{bmatrix}1&1\end{bmatrix},\quad Q=I,\quad R=1$

and the (unknown) channel success probabilities are given by

$\bm{\theta}=(\theta_{1},\theta_{2},\theta_{3},\theta_{4})=(0.8,\;0.7,\;0.6,\;0.5).$

Table I illustrates the empirical estimation regret for a number of different
channel probabilities
$\bm{\theta}=(\theta_{1},\theta_{2},\theta_{3},\theta_{4})$ and system
matrices $A$, $C$, $Q$, $R$. All bandit algorithms studied in this work,
namely $\varepsilon$-greedy, Thompson sampling (TS), OBS, and SBS, are
considered. The regret is computed over horizon $T=1000$, and averaged over
100000 runs. For $\varepsilon$-greedy, we considered different values of
$\varepsilon$ in steps of 0.02, with the value giving the smallest simulated
regret presented in Table I.

TABLE I: Estimation regret of different algorithms $\bm{\theta}$ | $A$ | $C$ | $Q$ | $R$ | $\theta_{c}$ | $\varepsilon$ |  $\varepsilon$-greedy | TS | OBS | SBS
---|---|---|---|---|---|---|---|---|---|---
$(0.8,0.75,0.55,0.5)$ | 1.45 | 1 | 1 | 1 | 0.524 | 0.12 | 263 | 143 | 136 | 135
$(0.7,0.6,0.5,0.4)$ | 1.45 | 1 | 1 | 1 | 0.524 | 0.18 | 996 | 679 | 596 | 603
$(0.6,0.5,0.4,0.3)$ | 1.45 | 1 | 1 | 1 | 0.524 | 0.22 | 10319 | 8253 | 6823 | 6276
$(0.7,0.6,0.4,0.3)$ | $\begin{bmatrix}1.2&0.1\\\ 0.2&1.1\end{bmatrix}$ | $\begin{bmatrix}1&1\end{bmatrix}$ | $I$ | 1 | 0.408 | 0.10 | 582 | 295 | 274 | 273
$(0.65,0.55,0.45,0.35)$ | $\begin{bmatrix}1.2&0.1\\\ 0.2&1.1\end{bmatrix}$ | $\begin{bmatrix}1&1\end{bmatrix}$ | $I$ | 1 | 0.408 | 0.12 | 886 | 517 | 473 | 483
$(0.55,0.45,0.35,0.25)$ | $\begin{bmatrix}1.2&0.1\\\ 0.2&1.1\end{bmatrix}$ | $\begin{bmatrix}1&1\end{bmatrix}$ | $I$ | 1 | 0.408 | 0.18 | 4723 | 3424 | 2727 | 2430
$(0.9,0.8,0.7,0.5)$ | $\begin{bmatrix}1.5&0.2\\\ 0.3&0.9\end{bmatrix}$ | $\begin{bmatrix}1&1\end{bmatrix}$ | $I$ | 1 | 0.603 | 0.14 | 290 | 104 | 98 | 97
$(0.8,0.7,0.6,0.5)$ | $\begin{bmatrix}1.5&0.2\\\ 0.3&0.9\end{bmatrix}$ | $\begin{bmatrix}1&1\end{bmatrix}$ | $I$ | 1 | 0.603 | 0.18 | 803 | 403 | 354 | 363
$(0.7,0.6,0.5,0.4)$ | $\begin{bmatrix}1.5&0.2\\\ 0.3&0.9\end{bmatrix}$ | $\begin{bmatrix}1&1\end{bmatrix}$ | $I$ | 1 | 0.603 | 0.22 | 7185 | 6178 | 3903 | 3106

As expected, the $\varepsilon$-greedy algorithm is outperformed by the
sampling based algorithms. In all the considered scenarios OBS and SBS can
achieve at least some improvement in performance over Thompson
sampling.222Note that when looking at individual simulation runs, we cannot
say that any one scheme will outperform any other. In many scenarios the
performance of OBS and SBS are quite close to each other. However in more
challenging situations, where there are only few stabilizing channels (just
one or two), SBS seems to be able to outperform OBS. This could be due to the
fact that in these cases using non-stabilizing channels more than necessary
can significantly degrade performance.

In Fig. 4 we plot the estimation regret over time for the $\varepsilon$-greedy
and Thompson sampling algorithms. Plots for OBS and SBS are qualitatively
similar to Thompson sampling and are omitted. The parameters used are the same
as those mentioned at the start of Section VI. We see a linear scaling (at
larger times) for $\epsilon$-greedy and a logarithmic scaling in the case of
Thompson sampling, in agreement with Theorems 3 and 4.

Figure 4: Estimation regret over time

##  VII Conclusion

We have studied a remote state estimation problem where a sensor can choose
between a number of channels with unknown channel statistics, with which to
transmit over. We have made use of bandit algorithms to learn the statistics
of the channels, while simultaneously carrying out the estimation procedure.
Stability of the estimator using these algorithms has been shown, and bounds
on the estimation regret have been derived. Future work will include the use
of bandit algorithms in the allocation of channels to multiple processes.

## References

  * [1] L. Buşoniu, T. de Bruin, D. Tolić, J. Kober, and I. Palunko, “Reinforcement learning for control: Performance, stability, and deep approximators,” _Annual Reviews in Control_ , vol. 46, pp. 8–28, 2018.
  * [2] L. Hewing, K. P. Wabersich, M. Menner, and M. N. Zeilinger, “Learning-based model predictive control: Toward safe learning in control,” _Annu. Rev. Control Robot. Auton. Syst._ , vol. 3, pp. 269–296, 2020.
  * [3] G. Cherubini, M. Guay, and S. Tarbouriech, Eds., _Special Issue on Learning and Control_. IEEE Control Systems Letters, Jul. 2020, vol. 4, no. 3.
  * [4] Y. Zeng, R. Zhang, and T. J. Lim, “Wireless communications with unmanned aerial vehicles: Opportunities and challenges,” _IEEE Commun. Mag._ , vol. 54, no. 5, pp. 36–42, May 2016.
  * [5] N. Mohamed, J. Al-Jaroodi, I. Jawhar, A. Idries, and F. Mohammed, “Unmanned aerial vehicles applications in future smart cities,” _Techn. Forecasting & Social Change_, vol. 153, no. 119293, Apr. 2020.
  * [6] F. Li, D. Yu, H. Yang, J. Yu, H. Karl, and X. Cheng, “Multi-armed-bandit-based spectrum sharing algorithms in wireless networks: A survey,” _IEEE Wireless Commun._ , vol. 27, no. 1, pp. 24–30, Feb. 2020.
  * [7] S. Wu, X. Ren, Q.-S. Jia, K. H. Johansson, and L. Shi, “Learning optimal scheduling policy for remote state estimation under uncertain channel condition,” _IEEE Trans. Control Netw. Syst._ , vol. 7, no. 2, pp. 579–591, Jun. 2020.
  * [8] M. Eisen, K. Gatsis, G. J. Pappas, and A. Ribeiro, “Learning in wireless control systems over nonstationary channels,” _IEEE Trans. Signal Process._ , vol. 67, no. 5, pp. 1123–1137, Mar. 2019.
  * [9] A. S. Leong, A. Ramaswamy, D. E. Quevedo, H. Karl, and L. Shi, “Deep reinforcement learning for wireless sensor scheduling in cyber-physical systems,” _Automatica_ , vol. 113, pp. 476–486, Mar. 2020.
  * [10] A. Redder, A. Ramaswamy, and D. E. Quevedo, “Deep reinforcement learning for scheduling in large-scale networked control systems,” in _Proc. IFAC NecSys_ , Chicago, USA, Sep. 2019.
  * [11] W. Liu, K. Huang, D. E. Quevedo, B. Vucetic, and Y. Li, “Deep reinforcement learning for wireless scheduling in distributed networked control,” 2021. [Online]. Available: https://arxiv.org/pdf/2109.12562.pdf
  * [12] A. Slivkins, _Introduction to Multi-Armed Bandit_. now Publishers Inc., 2019.
  * [13] T. Lattimore and C. Szepesvári, _Bandit Algorithms_. Cambridge University Press, 2020.
  * [14] Y. Gai, B. Krishnamachari, and R. Jain, “Learning multiuser channel allocations in cognitive radio networks: A combinatorial multi-armed bandit formulation,” in _Proc. IEEE DySPAN_ , Singapore, Apr. 2010.
  * [15] T. Stahlbuhk, B. Shrader, and E. Modiano, “Learning algorithms for scheduling in wireless networks with unknown channel statistics,” _Ad Hoc Networks_ , vol. 85, pp. 131–144, 2019.
  * [16] S. Takeuchi, M. Hasegawa, K. Kanno, A. Uchida, N. Chauvet, and M. Naruse, “Dynamic channel selection in wireless communications via a multi-armed bandit algorithm using laser chaos time series,” _Scientific Reports_ , vol. 10, no. 1574, 2020.
  * [17] R. S. Sutton and A. G. Barto, _Reinforcement Learning_ , 2nd ed. Massachusetts: The MIT Press, 2018.
  * [18] D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen, “A tutorial on Thompson sampling,” _Foundations and Trends in Machine Learning_ , vol. 11, no. 1, pp. 1–96, 2018.
  * [19] M. J. Kim, “Thompson sampling for stochastic control: The finite parameter case,” _IEEE Trans. Autom. Control_ , vol. 62, no. 12, pp. 6415–6422, Dec. 2017.
  * [20] D. Banjević and M. J. Kim, “Thompson sampling for stochastic control: The continuous parameter case,” _IEEE Trans. Autom. Control_ , vol. 64, no. 10, pp. 4137–4152, Oct. 2019.
  * [21] Y. Ouyang, M. Gagrani, and R. Jain, “Posterior sampling-based reinforcement learning for control of unknown linear systems,” _IEEE Trans. Autom. Control_ , vol. 65, no. 8, pp. 3600–3607, Aug. 2020.
  * [22] B. D. O. Anderson and J. B. Moore, _Optimal Filtering_. New Jersey: Prentice Hall, 1979.
  * [23] L. Shi, M. Epstein, and R. M. Murray, “Kalman filtering over a packet-dropping network: A probabilistic perspective,” _IEEE Trans. Autom. Control_ , vol. 55, no. 3, pp. 594–604, Mar. 2010.
  * [24] Y. Xu and J. P. Hespanha, “Estimation under uncontrolled and controlled communications in networked control systems,” in _Proc. IEEE Conf. Decision and Control_ , Seville, Spain, December 2005, pp. 842–847.
  * [25] L. Schenato, “Optimal estimation in networked control systems subject to random delay and packet drop,” _IEEE Trans. Autom. Control_ , vol. 53, no. 5, pp. 1311–1317, Jun. 2008.
  * [26] L. Shi and H. Zhang, “Scheduling two Gauss-Markov systems: An optimal solution for remote state estimation under bandwidth constraint,” _IEEE Trans. Signal Process._ , vol. 60, no. 4, pp. 2038–2042, Apr. 2012\.
  * [27] O.-C. Granmo, “Solving two-armed Bernoulli bandit problems using a Bayesian learning automaton,” _Int. J. Intelligent Computing and Cybernetics_ , vol. 3, no. 2, pp. 207–234, 2010.
  * [28] B. C. May, N. Korda, A. Lee, and D. S. Leslie, “Optimistic Bayesian sampling in contextual-bandit problems,” _J. Machine Learning Research_ , pp. 2069–2106, 2012.
  * [29] S. Fatale, K. Bhandani, U. Narula, S. Moharir, and M. K. Hanawal, “Regret of age-of-information bandits,” _IEEE Trans. Commun._ , vol. 70, no. 1, pp. 87–100, Jan. 2022.
  * [30] J. Mellor, “Decision making using Thompson sampling,” Ph.D. dissertation, University of Manchester, 2014.
  * [31] T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” _Adv. Appl. Math._ , vol. 6, no. 1, pp. 4–22, Mar. 1985.
  * [32] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” _Machine Learning_ , vol. 47, pp. 235–256, 2002\.
  * [33] S. Agrawal and N. Goyal, “Near-optimal regret bounds for Thompson sampling,” _J. ACM_ , vol. 64, no. 5, 2017.
  * [34] E. Kaufmann, N. Korda, and R. Munos, “Thompson sampling: An asymptotically optimal finite-time analysis,” in _Proc. Int. Conf. Algorithmic Learning Theory_ , Lyon, France, Oct. 2012, pp. 199–213.
  * [35] R. A. Horn and C. R. Johnson, _Matrix Analysis_ , 2nd ed. Cambridge, UK: Cambridge University Press, 2013.
  * [36] W. Liu, D. E. Quevedo, Y. Li, K. H. Johansson, and B. Vucetic, “Remote state estimation with smart sensors over Markov fading channels,” _IEEE Trans. Autom. Control_ , vol. 67, no. 6, pp. 2743–2757, Jun. 2022.
  * [37] S. Lale, K. Azizzadenesheli, B. Hassibi, and A. Anandkumar, “Adaptive control and regret minimization in linear quadratic Gaussian (LQG) setting,” in _Proc. Amer. Control Conf._ , New Orleans, USA, May 2021, pp. 2517–2522.


# The defect, the Malgrange functor, and linear control systems

Alex Martsinkovsky  Mathematics Department
Northeastern University
Boston, MA 02115, USA<EMAIL_ADDRESS>In memory of Jeremy
Russell

(Date: August 28, 2024, 7 h 18 min)

###### Abstract.

The notion of defect of a finitely presented functor on a module category is
extended to arbitrary additive functors. The new defect and the contravariant
Yoneda embedding form a right adjoint pair. The main result identifies the
defect of the covariant Hom modulo projectives with the Bass torsion of the
fixed argument. When applied to a linear control systems, it shows that the
defect of the Malgrange functor of the system modulo projectives is isomorphic
to the autonomy of the system. Furthermore, the defect of the contravariant
Hom modulo injectives is shown to be isomorphic to the cotorsion coradical of
the fixed argument. Since the Auslander-Gruson-Jensen transform of cotorsion
is isomorphic to torsion, the above results raise two important questions: a)
what is a control-theoretic interpretation of the covariant Yoneda embedding
of the Malgrange module modulo injectives, and b) what is a control-theoretic
interpretation of the Auslander-Gruson-Jensen duality?

###### 2010 Mathematics Subject Classification:

Primary: 18A25 ; Secondary: 16S90, 16D90, 18E40, 18E99, 93B05, 93B07, 93B25,
93B99, 93C05

Supported in part by the Shota Rustaveli National Science Foundation of
Georgia Grant NFR-18-10849

###### Contents

  1. 1 Introduction
  2. 2 The Malgrange functor of a linear control system
  3. 3 The defect of a finitely presented functor
  4. 4 The defect of an arbitrary additive functor
  5. 5 Concluding remarks and open questions

##  1\. Introduction

Blanket assumption. All functors in this paper are assumed additive.

A general notion of torsion was introduced and studied in [11, 12, 13]. Two
aspects of that work deserve special mention. First, it is the utmost
generality of that concept – the definition works for arbitrary modules over
arbitrary rings. For arbitrary modules over commutative domains it coincides
with the classical torsion. For finitely presented modules over arbitrary
rings it coincides with the Bass torsion, defined as the kernel of the
canonical bidualization map. Secondly, the functorial techniques used in the
definition of torsion allowed to introduce for the first time a new concept
called cotorsion. It is worth mentioning that 116 years had passed from
Poincaré’s discovery of torsion ([5, p. 33]) to the introduction of cotorsion
in 2016. The Auslander-Gruson-Jensen functor effects a duality between the two
concepts [12].

In June 2017, in a private communication to the author, Mohamed Barakat
pointed out a connection between torsion and linear control systems (LCSs). To
wit, thinking of an LCS as described by its Malgrange module (see below), one
observes that its torsion submodule represents the autonomy of the system,
i.e., the part of the system that cannot be controlled. It was this
observation, already known to control theorists, that made this author a
strong advocate of a functorial approach to the study of LCSs.

Functor categories have several advantages over module categories. First, they
have nice homological properties. Secondly, the category of modules over a
ring can be embedded in a functor category via the so-called Yoneda
embedding(s). Thirdly, the module category can be recovered from a functor
category as a certain Serre quotient. These fundamental properties were
established by M. Auslander in his seminal paper [2]. In that work he studied
coherent, a.k.a. finitely presented, functors. Knowing a finite presentation
of an additive functor allows for direct calculations because, in many cases,
such calculations are reduced to repeated applications of the Yoneda lemma
coupled with the standard exactness properties of the Hom functor. Roughly
speaking, finite presentation allows to translate questions about functors
back into the language of modules. This tool is completely missing when the
functor is not finitely presented.

On the other hand, many naturally arising functors are not, in general,
finitely presented. Examples include tensor products and their derived
functors, various torsion functors and their derived functors (e.g., local
cohomology), the covariant Hom functors modulo projectives, the contravariant
Hom functors modulo injectives, and others. To remedy this deficiency, in this
paper we introduce another “bridge” from functors to modules, called the
defect. For finitely presented functors this tool was already present in [2],
but we were able to extend this notion to arbitrary additive functors. For a
given functor, its defect is defined as the class (actually, a set) of all
natural transformations from the functor to the forgetful functor. We also
prove that the defect and the contravariant Yoneda embedding form a right
adjoint pair.

For an additive contravariant functor, we define its defect dually as the set
of all natural transformations from the forgetful functor to the functor in
question. Of course, by the Yoneda lemma, this set is just the value of the
functor on the regular module, and the definition remains the same as for
finitely presented functors.

Significant progress in a functorial approach to the study of control systems
was recently achieved by Sebastian Posur in [15], where he obtained a
categorical framework for behaviors in algebraic system theory.

The present paper provides a functorial description of the autonomy,
understood here as the torsion submodule, showing that the autonomy is
isomorphic to the defect of the (projectively) stabilized Malgrange functor,
where the Malgrange functor is defined as the covariant functor represented by
the Malgrange module.

Here is a brief outline of the paper.

Section 2 deals with LCSs. We recall basic definitions and the Malgrange
isomorphism.

In Section 3 we recall basic facts about finitely presented functors.

In Section 4 the defect of an arbitrary additive functor is introduced.
Proposition 4.6 shows that the Yoneda embedding and the defect form a right
adjoint pair. Theorem 4.10 computes the defect of a covariant Hom modulo
projectives, which turns out, somewhat surprisingly, to be isomorphic to the
Bass torsion $\mathfrak{t}$ of the fixed argument. The surprise is that, in
this role, one would expect the better behaved torsion radical $\mathfrak{s}$,
introduced in [12]. However, in the case of current interest – when the
argument is finitely presented – $\mathfrak{s}$ and $\mathfrak{t}$ coincide
(see [12] for more details).

Parallel to that, the defect of the contravariant Hom modulo injectives is
isomorphic to the cotorsion $\mathfrak{q}$ of the fixed argument. It was shown
in [12] that, under the duality effected by the Auslander-Gruson-Jensen
transform, $\mathfrak{q}$ is sent to $\mathfrak{s}$.

We recall from [12] that $\mathfrak{s}$ is the largest subfunctor of
$\mathfrak{t}$ preserving filtered colimits. As we just remarked, it coincides
with $\mathfrak{t}$ on finitely presented modules, but the two may differ on
infinite modules. That $\mathfrak{t}$ is a radical (in the sense of Stenström)
follows at once since it is the reject of the regular module or, equivalently,
of the class of projectives. The torsion functor $\mathfrak{s}$ is a radical,
too, but whether it is a reject of a suitable class is an open question.
Moreover, the only known to the author proof that $\mathfrak{s}$ is a radical
[12, Theorem 2.19] is based on the fact that the Bass torsion has this
property. It appears that $\mathfrak{s}$ and $\mathfrak{t}$ are in a truly
symbiotic relationship.

Section 5 contains some open questions on further possible connections with
LCSs.

For the module-theoretic terminology used here, consult [1].

Acknowledgments. I am grateful to Mohamed Barakat, Vakhtang Lomadze, Alban
Quadrat, and Sebastian Posur for stimulating discussions and their patience
while answering my numerous questions.

##  2\. The Malgrange functor of a linear control system

By an LCS we understand an underdetermined system of linear differential
equations. Such a system can be written in the form

(2.1) $x^{\prime}(t)=Ax(t)+Bu(t).$

Here the functions $x(t)$ are called the state variables, whereas the $u(t)$
are the so called input variables. The inputs $u(t)$ are free in the sense
that they can be chosen arbitrarily. The symbols $A$ and $B$ stand for
matrices with entries in a suitable ring of differential operators. We assume
there are only finitely many equations and finitely many variables, making $A$
and $B$ finite. The coefficients can be constant, polynomial, or analytic
functions. To control the system (2.1) one needs output variables $y(t)$:

(2.2) $y(t)=Cx(t)+Du(t)$

for some chosen matrices $C$ and $D$. The classical form of a control system
is then given by

(2.3) $\begin{cases}x^{\prime}(t)&=Ax(t)+Bu(t)\\\
y(t)&=Cx(t)+Eu(t)\end{cases}$

Strictly speaking, the second equation is not an intrinsic part of the system.
Nevertheless, it is a common practice to refer to (2.3) as “the system”.
Notice also that there is nothing to “solve for” in the second equation – this
is just an explicit definition of the output.

Rewriting (2.3) in the form $AX=0$ (with $A$ here different from the $A$ in
(2.3)), we have that an LCS is just a system of linear equations in modules
over a suitable ring $D$ of differential operators. It was a simple but
important observation by Malgrange [10, 3, $2^{\circ}$, p. 84], sometimes
referred to as the Malgrange isomorphism, that solutions of $AX=0$ can be
realized as homomorphisms from the module presented by the transpose $A^{T}$
of $A$. We want to rephrase this in a functorial language.

Associated with the matrix $A$ above is the system $AX=0$ of linear equations
in left $D$-modules. Given a left $D$-module $V$, the solution-set $S(V)$ of
the system in $V$ is a subset of $V^{n}$, where $n$ is the number of variables
in the system. This subset, as is easily seen, is also a subgroup of the
underlying abelian group of $V^{n}$. (Since $D$ need not be commutative,
$S(V)$ is not, in general, a submodule.) As a result, we obtain an additive
covariant functor $S$, the solution-set functor, from left $D$-modules to
abelian groups. Let $M$ be the left module with free presentation given by
$A^{T}$. The Malgrange isomorphism is now the statement that the functor $S$
is represented by $M$:

$S\simeq(M,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt).$

######  Remark 2.1.

In its simplest form, when $A=a\in D$ is a 1 x 1 matrix, and $D$ is a
commutative ring, the Malgrange isomorphism is probably known to everybody:

$\big{(}D/(a),N\big{)}\simeq\\{x\in N\mid ax=0\\},$

where $N$ is any $D$-module.

We shall refer to the finitely presented left $D$-module with presentation
matrix $A^{T}$ as the Malgrange module of the system $AX=0$. The corresponding
representable functor $(M,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)$ will be called the Malgrange functor of the system.

Recall that a control system is said to be controllable if any final stage can
be reached, by choosing the inputs, from any initial state in finite time. Not
every system is controllable, and the part of the system that cannot be
controlled is known as the autonomy of the system. In terms of the Malgrange
module $M$ of the system, the autonomy corresponds to the torsion submodule of
$M$. This was originally observed by J.-F. Pommaret in 1989 in the context of
differential algebra. In 1991, M. Fliess gave a module-theoretic formulation
of this result. In this paper, we are interested in a functorial approach to
the study of control systems, which brings about a natural question: can the
autonomy be described in terms of the Malgrange functor associated with the
system? The main result of this paper gives a positive answer to the algebraic
reformulation of this question.

##  3\. The defect of a finitely presented functor

In this section we recall the definition and basic properties of finitely
presented functors and of the category they form. In particular, we recall the
definition of the defect of a finitely presented functor. The canonical
reference for this material is [2].

######  Definition 3.1.

A functor $F$ is said to be finitely generated if there is a module $X$ and a
natural transformation $\alpha:(X,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt)\to F$ which is epic on each
component.111The symbol $(X,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)$ denotes $\operatorname{\mathrm{Hom}}(X,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt)$.

######  Proposition 3.2.

Let $F$ and $G$ be functors. If $F$ is finitely generated, then the class of
all natural transformations $g:F\to G$, denoted by $\mathrm{Nat}(F,G)$, is a
set.

###### Proof.

Let $\alpha:(X,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt)\to F$
be a componentwise epimorphism. Then, the assignment $g\mapsto g\alpha$ yields
an injection $\mathrm{Nat}(F,G)\to\mathrm{Nat}((X,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt),F)$. By the Yoneda lemma,
the latter is isomorphic to $F(X)$, which is a set. Hence $\mathrm{Nat}(F,G)$
is a set, too. ∎

######  Definition 3.3.

A functor $F$ is said to be finitely presented if there are modules $X$ and
$Y$ and a homomorphism $f:Y\to X$ such that the sequence

(3.1) $(X,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)\overset{(f,\hskip 1.13791pt\rule{4.2679pt}{0.4pt}\hskip
1.13791pt)}{\longrightarrow}(Y,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)\longrightarrow F\longrightarrow 0$

is componentwise exact.

Thus every finitely presented functor is finitely generated and, as a
consequence of Proposition 3.2, the totality of all finitely presented
functors and natural transformations between them, denoted here by
${\mathrm{fp}}(\Lambda\mathchar 45\relax\mathrm{Mod},\mathbf{Ab})$, is a
category.

The notions of monomorphism, epimorphism, and isomorphism between functors are
defined componentwise and coincide with the corresponding categorical
definitions.

######  Proposition 3.4.

${\mathrm{fp}}(\Lambda\mathchar 45\relax\mathrm{Mod},\mathbf{Ab})$ has kernels
and cokernels.

###### Proof.

See [2, Proposition 2.1]. For a more direct proof, see [3, Proposition 3.1]. ∎

######  Proposition 3.5.

${\mathrm{fp}}(\Lambda\mathchar 45\relax\mathrm{Mod},\mathbf{Ab})$ is abelian.

###### Proof.

The canonical morphism from the coimage to the image is an isomorphism because
it is an isomorphism componentwise. ∎

######  Proposition 3.6.

${\mathrm{fp}}(\Lambda\mathchar 45\relax\mathrm{Mod},\mathbf{Ab})$ has enough
projectives.

###### Proof.

The projectives are precisely the representables, which can be seen by
applying the Yoneda lemma. ∎

######  Remark 3.7.

The projectives in ${\mathrm{fp}}(\Lambda\mathchar
45\relax\mathrm{Mod},\mathbf{Ab})$ can also be characterized as the left-exact
finitely presented functors. Indeed, the representables are of this form. On
the other hand, a finitely presented functor clearly preserves arbitrary
products. If it is left-exact, it also preserves finite limits. It follows
that it preserves arbitrary limits, and by a theorem of Watts, it must be
representable.

An important invariant of a finitely presented functor is its defect, a notion
introduced (without a name) by Auslander in [2, pp. 202 and 209]. We recall it
now.

######  Definition 3.8.

Let $F$ be a covariant functor with presentation (3.1). The module

$w(F):=\operatorname{\mathrm{Ker}}f$

is called the defect of $F$.

The following known result follows directly from this definition.

######  Lemma 3.9.

The defect of a finitely presented functor is zero if and only if the functor
vanishes on injectives. ∎

The notion of defect for a contravariant functor is defined similarly [ibid.]

######  Definition 3.10.

Let $F$ be a contravariant functor with presentation

(3.2) $(\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt,Y)\overset{(\hskip 1.13791pt\rule{4.2679pt}{0.4pt}\hskip
1.13791pt,f)}{\longrightarrow}(\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt,X)\longrightarrow F\longrightarrow 0.$

The module $v(F):=\operatorname{\mathrm{Coker}}f$ is called the defect of $F$.

It is immediate from the definition that $v(F)\simeq F(\Lambda)$. The
following lemma is now obvious.

######  Lemma 3.11.

The defect of a finitely presented contravariant functor is zero if and only
if the functor vanishes on the regular module. ∎

######  Remark 3.12.

The first phenomenological study of the defect of a finitely presented functor
was undertaken by Jeremy Russell in [17].

##  4\. The defect of an arbitrary additive functor

The goal of this section is to make the notion of defect applicable to
arbitrary additive functors on $\Lambda\mathchar 45\relax\mathrm{Mod}$, the
category of left $\Lambda$-modules, with values in abelian groups. We remind
the reader that Auslander’s definition applies to finitely presented functors
only.

Recall that the contravariant Yoneda embedding, denoted here by
$\operatorname{\yen^{\bullet}}$, is a functor $\Lambda\mathchar
45\relax\mathrm{Mod}\longrightarrow{\mathrm{fp}}(\Lambda\mathchar
45\relax\mathrm{Mod},\mathbf{Ab})$ which sends a module $A$ to the
representable functor $(A,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)$. In particular, $\operatorname{\yen^{\bullet}}(\Lambda)$ is the
forgetful functor $(\Lambda,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)$. We can now introduce a defect of an arbitrary additive functor

######  Definition 4.1.

Let $F:\Lambda\mathchar 45\relax\mathrm{Mod}\longrightarrow\mathbf{Ab}$ be an
arbitrary additive covariant functor. Define the defect $w(F)$ of $F$ by
setting

$w(F):=(F,\operatorname{\yen^{\bullet}}(\Lambda)),$

where the right-hand side is the class of all natural transformations
$F\to\operatorname{\yen^{\bullet}}(\Lambda)$.

By Proposition 3.2, if $F$ is finitely generated, then $w(F)$ is a set.
However, since the forgetful functor is a biadjoint, the following theorem,
due to G. M. Kelly [8, Theorem (1.5)], shows that the finiteness assumption
can be dropped.222I am grateful to Alex Sorokin for bringing this result to my
attention.

######  Theorem 4.2.

Let $F,G:\mathbf{L}\longrightarrow\mathbf{K}$ be two functors. The class
$(F,G)$ of natural transformations from $F$ to $G$ constitutes a set provided
either

  1. (i)

$\mathbf{K}$ has a generator and $F$ has a left adjoint, or

  2. (ii)

$\mathbf{K}$ has a cogenerator and $G$ has a right adjoint, or

  3. (iii)

$\mathbf{L}$ has a generator and $F$ has a right adjoint, or

  4. (iv)

$\mathbf{L}$ has a generator and $G$ has a left adjoint. ∎

Thus $w(F)$ is always a set. Notice also that the symbol $w$ is, in fact, an
additive contravariant functor from the large category of additive functors
$\mathrm{Mod}\mathchar 45\relax\Lambda\to\mathbf{Ab}$ to abelian groups.
Moreover, the bimodule structure on $\Lambda$ gives rise to the structure of a
left $\Lambda$-module on each component of the defect. In summary, we have

######  Lemma 4.3.

The defect is an additive contravariant functor from the large functor
category back to modules:

$w:(\Lambda\mathchar
45\relax\mathrm{Mod},\mathbf{Ab})\longrightarrow\Lambda\mathchar
45\relax\mathrm{Mod}.$

It is represented by the forgetful functor
$\operatorname{\yen^{\bullet}}(\Lambda)$ and, in particular, is left-
exact.333It can be shown that the defect, viewed as a functor on finitely
presented functors, is a biadjoint([4]). In particular, it is exact. However,
in general, $w$ is not right-exact. ∎

In preparation for the next proposition we sketch some basic properties of
additive functors. Let ${\\{F_{i}:\Lambda\mathchar
45\relax\mathrm{Mod}\longrightarrow\mathbf{Ab}\\}}$ be a family of such
functors. Define an additive functor $\prod F_{i}$ componentwise:
$\big{(}\prod F_{i}\big{)}(X):=\prod\big{(}F_{i}(X)\big{)}$. Notice that the
right-hand side is unambiguously defined as a product of abelian groups.
Furthermore, the structure maps
$\pi_{j}(X):\prod\big{(}F_{i}(X)\big{)}\longrightarrow F_{j}(X)$ give rise to
natural transformations $\pi_{j}:\prod F_{i}\longrightarrow F_{j}$. It is now
a straightforward verification that $\prod F_{i}$ is a product of the $F_{i}$
with structure maps $\pi_{j}$. As an immediate consequence, we have

######  Lemma 4.4.

For any functor $F$ and any family ${\\{F_{i}\\}}$ of functors there is a
canonical isomorphism $(F,\prod F_{i})\cong\prod(F,F_{i})$. ∎

The proof of the next lemma is also straightforward.

######  Lemma 4.5.

The contravariant Yoneda embedding sends direct sums to direct products. In
particular, $\operatorname{\yen^{\bullet}}(\coprod
A_{i})\simeq\prod\big{(}\operatorname{\yen^{\bullet}}(A_{i})\big{)}$, where
the $A_{i}$ are $\Lambda$-modules.444This is a particular case of a more
general observation: products in the large functor category can be defined and
computed componentwise. While the proof of the lemma is very simple, the
reader should not fall into a trap and claim that the lemma is completely
trivial. Indeed, the product in the right-hand side is to be taken in the
functor category! ∎

We are now ready to prove

######  Proposition 4.6.

The defect and the contravariant Yoneda embedding form a right adjoint pair,
i.e., for any additive covariant functor $F$ and any $\Lambda$-module $A$,
there is an isomorphism

(4.1) $(F,\yen^{\bullet}(A))\simeq\big{(}A,w(F)\big{)}.$

natural in $F$ and $A$.

###### Proof.

We are going to look at the left-hand side of the claimed isomorphism as the
value of the additive contravariant functor $G:=\big{(}F,\yen^{\bullet}(\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt)\big{)}$ on $A$. This is a
functor from $\Lambda\mathchar 45\relax\mathrm{Mod}$ to (large) abelian
groups.555Notice that, by Theorem 4.2, $G(\Lambda)$ is a small abelian group.
It is well-known (see, for example, the discussion preceding [11, Lemma 3.16])
that the canonical natural transformation from any additive contravariant
functor to the result of the Yoneda embedding of its value on $\Lambda$ is an
isomorphism on $\Lambda$. Thus, we have a canonical natural transformation
$\sigma:G\to\big{(}\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt,G(\Lambda)\big{)}$, which evaluates to an isomorphism on $\Lambda$.
The discussion preceding this proposition shows that $G$ converts direct sums
to direct products, and therefore $\sigma$ is an isomorphism on all
projectives. Since the codomain of $\sigma$ is clearly left-exact,
$\big{(}\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt,G(\Lambda)\big{)}$ is the zeroth right-derived functor $R_{0}G$ of
$G$.666The use of a subscript rather than a superscript is only for mnemonic
purposes to indicate that $G$ is a contravariant functor. But, as is easily
checked, $G$ is itself left-exact and therefore $\sigma$ is an isomorphism.
The proof of the functoriality in each variable is straightforward. ∎

######  Remark 4.7.

The above proposition gives yet another proof that $w$ is left-exact.

######  Remark 4.8.

J. Fisher Palmquist and D. Newell introduced a notion of the dual of an
additive covariant functor [6, pp. 299-300]. In our notation, the value
$F^{\ast}(A)$ of the dual of $F$ on $A$ is defined as
$(F,\yen^{\bullet}(A))$.777The reader should notice that the $(\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)^{\scaleto{\ast\mathstrut}{5pt}}$ operation flips the variance of
the functor.,888Similarly, if $F$ is contravariant,
$F^{\scaleto{\ast\mathstrut}{5pt}}(A)$ is defined as
$(F,\yen_{\scaleto{\bullet\mathstrut}{5pt}}(A))$, where
$\yen_{\scaleto{\bullet\mathstrut}{5pt}}$ denotes the covariant Yoneda
embedding. Thus the lemma says there is a functorial in $F$ isomorphism
$F^{\ast}\simeq(\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt,w(F))$. In particular, $w(F)$ represents $F^{\ast}$.

######  Proposition 4.9.

For finitely presented functors the new defect is isomorphic to the defect
defined by Auslander.

###### Proof.

Map the presentation (3.1) on page 3.1 into $(\Lambda,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt)$ and use the Yoneda lemma
together with the left-exactness of the Hom functor. ∎

We can now show that the just defined defect of the covariant Hom modulo
projectives is isomorphic to the Bass torsion of the representing object. By
the Bass torsion $\mathfrak{t}(A)$ of a $\Lambda$-module $A$ we understand the
kernel of the canonical evaluation map $A\to A^{\ast\ast}$. It consists of all
elements of $A$ on which all linear forms $A\to\Lambda$ vanish.

######  Theorem 4.10.

Let $\Lambda$ be an arbitrary ring. For any left $\Lambda$-module $A$, there
is a canonical isomorphism

$\varepsilon:w(\underline{A,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt})\overset{\simeq}{\longrightarrow}\mathfrak{t}(A),$

functorial in $A$.

###### Proof.

Start with the defining exact sequence

(4.2) $0\longrightarrow P(A,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)\overset{\iota}{\longrightarrow}(A,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)\overset{\pi}{\longrightarrow}(\underline{A,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt})\longrightarrow 0,$

where $P(A,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt)$ denotes
the subfunctor of $(A,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)$ consisting of all maps factoring through projectives, and pick any
$\alpha\in\big{(}(\underline{A,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt}),\operatorname{\yen^{\bullet}}(\Lambda)\big{)}$. By the Yoneda
lemma, $\alpha\pi=(f_{\alpha},\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt)$ for some uniquely determined $f_{\alpha}:\Lambda\to A$. Since
$\Lambda$ is projective, $\pi_{\Lambda}=0$ and therefore
$(f_{\alpha},\Lambda)=0$. This means that $hf_{\alpha}=0$ for any linear form
$h:A\to\Lambda$. In particular, $hf_{\alpha}(1)=0$, i.e., any linear form
vanishes on $f_{\alpha}(1)$, and therefore $f_{\alpha}(1)\in\mathfrak{t}(A)$.
Thus, we have a well-defined canonical $\Lambda$-linear map

$\varepsilon:\big{(}(\underline{A,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt}),\operatorname{\yen^{\bullet}}(\Lambda)\big{)}\longrightarrow\mathfrak{t}(A):\alpha\mapsto
f_{\alpha}(1).$

If $f_{\alpha}(1)=0$ then $f_{\alpha}=0$ and therefore $\alpha\pi=0$. Since
$\pi$ is epic, this shows that $\alpha=0$ and therefore $\varepsilon$ is
injective.

To show that $\varepsilon$ is surjective, pick an arbitrary
$b\in\mathfrak{t}(A)$ and define a homomorphism $f_{b}:\Lambda\to A$ of left
$\Lambda$-modules by sending $\lambda\mapsto\lambda b$. This map gives rise to
a natural transformation $\beta:=(f_{b},\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt):(A,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt)\to(\Lambda,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt)$. Since any linear form
$A\to\Lambda$ vanishes on $b$, we have that $\beta\iota=0$ and $\beta$ must be
of the form $\alpha\pi$ for some $\alpha\in\big{(}(\underline{A,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt}),\operatorname{\yen^{\bullet}}(\Lambda)\big{)}$. The foregoing
arguments now show that $\varepsilon(\alpha)=b$, proving that $\varepsilon$ is
surjective.

Verification of the functoriality of $\varepsilon$ is straightforward. ∎

######  Remark 4.11.

The defect of the covariant Hom modulo injectives is 0. Indeed, a presentation
of $(\overline{A,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt})$ is
determined by a short exact sequence $0\to A\overset{f}{\to}I\to\Sigma A\to
0$, and therefore $w(\overline{A,\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt})=\operatorname{\mathrm{Ker}}f=0$.

For the sake of completeness, we briefly discuss the contravariant case.
Recall that the defect of the finitely presented contravariant functor $F$
with presentation (3.2) was defined as
$v(F):=\operatorname{\mathrm{Coker}}f=F(\Lambda)$. This makes extending the
covariant defect to arbitrary additive functors obvious.

######  Definition 4.12.

Let $F$ be an additive contravariant functor. The defect $v(F)$ is defined by
setting $v(F):=F(\Lambda)$.

It is immediate that $v$ is an exact covariant functor from contravariant
additive functors back to modules. Straight from the definition we have $v(F)$
is zero if and only if $F$ vanishes on the regular module.

######  Example 4.13.

Trivially, $v(\underline{\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt,A})\simeq 0$.

######  Remark 4.14.

The reader may wonder why the definition of $v$ looks so different from that
of $w$. In fact, the two definitions are similar: by the Yoneda lemma,
$F(\Lambda)\simeq\big{(}\yen_{\bullet}(\Lambda),F\big{)}$, where
$\yen_{\bullet}$ stands for the covariant Yoneda embedding. Thus the
definition of $v$ can also be stated as

$v(F)=\big{(}\yen_{\bullet}(\Lambda),F\big{)}.$

######  Example 4.15.

A natural companion for the covariant Hom modulo projectives is the
contravariant Hom modulo injectives, $(\overline{\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt,A})$. In general, this
functor is not finitely presented. Computing its defect, we have

$v(\overline{\hskip 1.13791pt\rule{6.82864pt}{0.4pt}\hskip
1.13791pt,A})\simeq(\overline{\Lambda,A})=\mathfrak{q}(A),$

where $\mathfrak{q}$ is the cotorsion coradical introduced in [12]. Thus the
defect of the contravariant Hom modulo injectives is isomorphic to the
cotorsion of the fixed argument.

Interpreting the foregoing results in the context of linear control systems
(see Section 2), we have

######  Theorem 4.16.

The autonomy of a linear control system is isomorphic to the defect of its
Malgrange functor modulo projectives. ∎

##  5\. Concluding remarks and open questions

In the previous section we saw that the defect of $(\underline{A,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt})$ is isomorphic the Bass
torsion $\mathfrak{t}(A)$ of $A$. If $A$ is finitely presented, then
$\mathfrak{t}(A)$ coincides with $\mathfrak{s}(A)$ ([12, Proposition 2.13]),
where $\mathfrak{s}$ is the torsion radical introduced in [ibid.]. Thus,
assuming that a control system is represented by finitely many equations in
finitely many unknowns, both $\mathfrak{s}$ and $\mathfrak{t}$ represent the
autonomy. This brings about

Question A. Which torsion radical, if any, $\mathfrak{s}$ or $\mathfrak{t}$,
represents the autonomy of a general system?

It was shown in [12] that $\mathfrak{s}$ is the largest subfunctor of
$\mathfrak{t}$ preserving filtered colimits. This property prevents the
pathological behavior of torsion responsible for the fact that the Bass
torsion of the additive group of the rationals coincides with that group. This
yields

Question B. Is it possible to view the autonomy as a subfunctor of the
identity functor on a suitable category? If so, does it preserve filtered
colimits?

Recall that the Auslander-Gruson-Jensen (AGJ) transform of an additive functor
$F$ is defined by the formula $DF(N):=(F,N\otimes\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt)$ (or $(F,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt\otimes N)$). This is an
additive functor on modules over the opposite ring. It was shown in [12], that
the AGJ transform of the cotorsion $\mathfrak{q}=(\overline{\Lambda,\hskip
1.13791pt\rule{6.82864pt}{0.4pt}\hskip 1.13791pt})$ is isomorphic to
$\mathfrak{s}$. It is yet another advantage of $\mathfrak{s}$ over the Bass
torsion. Returning to control systems, we have

Question C. Given a control system with Malgrange module $M$, what is the
control-theoretic interpretation of the cotorsion $(\overline{\Lambda,M})$ of
the Malgrange module? Recall that the cotorsion of a module is simply its
quotient by the trace of the class of injectives.

For certain classes of LCSs, one has a duality between the controllability of
a system and the observability of the dual system (see [7, 14, 18, 16, 9]).
The module-theoretic and functorial analogs of the autonomy discussed above
beg for the next question.

Question D. Is there a control-theoretic interpretation of the Auslander-
Gruson-Jensen duality?

## References

  * [1] F. W. Anderson and K. R. Fuller.  Rings and categories of modules, volume 13 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 1992.
  * [2] M. Auslander.  Coherent functors.  In Proc. Conf. Categorical Algebra (La Jolla, Calif., 1965), pages 189–231. Springer, New York, 1966.
  * [3] M. Auslander.  A functorial approach to representation theory.  In Representations of algebras (Puebla, 1980), volume 944 of Lecture Notes in Math., pages 105–179. Springer, Berlin-New York, 1982\.
  * [4] S. Dean and J. Russell.  The Auslander-Gruson-Jensen recollement.  J. Algebra, 511:440–454, 2018.
  * [5] J. Dieudonné.  A history of algebraic and differential topology. 1900–1960.  Birkhäuser Boston, Inc., Boston, MA, 1989.
  * [6] J. Fisher Palmquist and D. C. Newell.  Bifunctors and adjoint pairs.  Trans. Amer. Math. Soc., 155:293–303, 1971.
  * [7] P. A. Fuhrmann.  Duality in polynomial models with some applications to geometric control theory.  IEEE Trans. Automat. Control, 26(1):284–295, 1981.
  * [8] F. E. J. Linton.  Autonomous categories and duality of functors.  J. Algebra, 2:315–349, 1965.
  * [9] V. Lomadze.  Duality for multidimensional linear systems with homological dimension $\leq 1$.  SIAM J. Control Optim., 59(1):417–433, 2021.
  * [10] B. Malgrange.  Systemes différentiels à coefficients constants.  Semin. Bourbaki 15 (1962/63), No. 246, 11 p. (1964).
  * [11] A. Martsinkovsky and J. Russell.  Injective stabilization of additive functors, I. Preliminaries.  J. Algebra, 530:429–469, 2019.
  * [12] A. Martsinkovsky and J. Russell.  Injective stabilization of additive functors. II. (Co)torsion and the Auslander-Gruson-Jensen functor.  J. Algebra, 548:53–95, 2020.
  * [13] A. Martsinkovsky and J. Russell.  Injective stabilization of additive functors, III. Asymptotic stabilization of the tensor product.  Algebra Discrete Math., 31(1):120–151, 2021.
  * [14] J. W. Nieuwenhuis and J. C. Willems.  Duality for linear time invariant finite-dimensional systems.  In Analysis and optimization of systems (Antibes, 1988), volume 111 of Lect. Notes Control Inf. Sci., pages 13–21. Springer, Berlin, 1988.
  * [15] S. Posur.  An abelian ambient category for behaviors in algebraic systems theory, 2023. arXiv 2303.02636
  * [16] J. Rudolph.  Duality in time-varying linear systems: a module-theoretic approach.  Linear Algebra Appl., 245:83–106, 1996.
  * [17] J. Russell.  Applications of the defect of a finitely presented functor.  J. Algebra, 465:137–169, 2016.
  * [18] A. J. van der Schaft.  Duality for linear systems: external and state space characterization of the adjoint system.  In Analysis of controlled dynamical systems (Lyon, 1990), volume 8 of Progr. Systems Control Theory, pages 393–403. Birkhäuser Boston, Boston, MA, 1991.