# Structure-Enhanced DRL for Optimal Transmission Scheduling

Jiazheng Chen  Wanchun Liu  Daniel E. Quevedo  Saeed R. Khosravirad  Yonghui
Li  Branka Vucetic  Part of the work has been submitted to IEEE ICC 2023
[1].J. Chen, W. Liu, Y. Li, and B. Vucetic are with the School of Electrical
and Information Engineering, The University of Sydney, Sydney, NSW 2006,
Australia (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>branka.vucetic@sydney.edu.au). D. E. Quevedo is with
the School of Electrical Engineering and Robotics, Queensland University of
Technology (QUT), Brisbane, Australia. (e-mail: dquevedo@ieee.org). S. R.
Khosravirad is with the Nokia Bell Laboratories, Murry Hill, NJ 07964 USA
(e-mail: saeed.khosravirad@nokia-bell-labs.com). (W. Liu is the corresponding
author.)

(September 2022)

###### Abstract

Remote state estimation of large-scale distributed dynamic processes plays an
important role in Industry 4.0 applications. In this paper, we focus on the
transmission scheduling problem of a remote estimation system. First, we
derive some structural properties of the optimal sensor scheduling policy over
fading channels. Then, building on these theoretical guidelines, we develop a
structure-enhanced deep reinforcement learning (DRL) framework for optimal
scheduling of the system to achieve the minimum overall estimation mean-square
error (MSE). In particular, we propose a structure-enhanced action selection
method, which tends to select actions that obey the policy structure. This
explores the action space more effectively and enhances the learning
efficiency of DRL agents. Furthermore, we introduce a structure-enhanced loss
function to add penalties to actions that do not follow the policy structure.
The new loss function guides the DRL to converge to the optimal policy
structure quickly. Our numerical experiments illustrate that the proposed
structure-enhanced DRL algorithms can save the training time by 50% and reduce
the remote estimation MSE by 10% to 25%, when compared to benchmark DRL
algorithms. In addition, we show that the derived structural properties exist
in a wide range of dynamic scheduling problems that go beyond remote state
estimation.

###### Index Terms:

Remote state estimation, deep reinforcement learning, sensor scheduling,
threshold structure.

##  I Introduction

Wireless networked control systems (WNCSs) consisting of distributed sensors,
actuators, controllers, and plants are a key component for Industry 4.0 and
have been widely applied in many areas such as industrial automation, vehicle
monitoring systems, building automation and smart grids [2]. In particular,
providing high-quality real-time remote estimation of dynamic system plant
states plays an important role in ensuring control performance and stability
of WNCSs [3, 4]. For large-scale WNCSs, transmission scheduling of wireless
sensors over limited bandwidth needs to be properly designed to guarantee
remote estimation performance.

There are many existing works on the transmission scheduling of WNCSs. In [5],
the optimal scheduling problem of a multi-loop WNCS with limited communication
resources was investigated for minimizing the transmission power consumption
under a WNCS stability constraint. In [6, 7], optimal sensor scheduling
problems of remote estimation systems were investigated for achieving the best
overall estimation mean-square error (MSE). In particular, dynamic decision-
making problems were formulated as Markov decision processes (MDPs), which can
be solved by classical methods, such as policy and value iterations. The
recent work [8] reduces the computation complexity for solving optimal
scheduling problems through approximate dynamic programming. However, the
conventional model-based solutions are not feasible in large-scale scheduling
problems because of the curse of dimensionality caused by high-dimensional
state and action spaces.111In [5, 6, 7], only the optimal scheduling of two-
sensor systems has been solved effectively by the proposed methods.

In recent years, deep reinforcement learning (DRL) has been developed to deal
with large MDPs by using deep neural networks as function approximators [9,
10]. Some works [11, 12, 13, 14] have used the deep Q-network (DQN), a simple
DRL method, to solve multi-sensor-multi-channel scheduling problems in
different remote estimation scenarios. In particular, sensor scheduling
problems for systems with 6 sensors have been solved effectively, providing
significant performance gains over heuristic methods in terms of estimation
quality. The more recent work [15] has introduced DRL algorithms with an
actor-critic structure to solve scheduling problems at a much larger scale
(that cannot be handled by the DQN). However, existing works merely use the
general DRL frameworks to solve specific scheduling problems, without
questioning what features distinguish sensor scheduling problems from other
MDPs. Also, we note that a drawback of general DRL is that it often cannot
perform policy exploration effectively for specific tasks [16], which can lead
to getting stuck in local minima or even total failure. Thus, the existing
DRL-based solutions could be far from optimal.

A key feature that we will exploit in our current work is that optimal
transmission scheduling policies of remote estimation systems often have
threshold structures [17, 18, 7], which means that there exist switching
boundaries dividing the state space into multiple regions for different
scheduling actions. In other words, an optimal policy has a structure where
the action only changes at the switching boundaries of the state space. In
particular, [17] focuses on an energy-constrained single-sensor-single-channel
system and proves that the optimal policy has a threshold in terms of the
sensor’s age of information (AoI), determining whether the sensor will be
scheduled or not. In [18], the authors considered a multi-sensor-multi-channel
system, where all channels are static, and each sensor has a constant packet-
drop probability at all frequency channels. This work also showed that the
optimal scheduling policy has a multi-dimensional threshold structure in terms
of all sensor AoI. As an extension, the work in [7] (a two-sensor system),
assumed that different sensors could have different numbers of packets for
carrying each measurement. The demonstrated threshold property of the optimal
policy is related to the sensor AoI and the remaining packet numbers of each
sensor. There are two limitations of the channel models adopted in the above
works: 1) fading channel models are commonly adopted in practice, where
channel states are time-varying, and 2) wireless propagation via different
frequency bandwidths has different properties, leading to different channel
qualities. Not limited to remote estimation systems, in [19], the threshold
structure of an optimal sensor scheduling policy has also been identified for
minimizing the average sum AoI. However, this work only considered a single-
channel system, and the transmission success or failure was determined before
a scheduling action. Therefore, the theoretical works [17, 18, 7, 19] only
derived the structural properties of optimal policies under some ideal
assumptions. It is an open challenge to prove the existence of structural
results of the optimal scheduling policy of a general multi-sensor-multi-
channel system over practical fading channels. Furthermore, there is no
existing work in the open literature utilizing the structural properties to
guide DRL algorithms for effectively solving optimal scheduling problems.

In this paper, we consider the optimal sensor scheduling problem of a general
$N$-sensor-$M$-channel remote estimation system over fading channels. The main
contributions of this work are summarized as follows.

  * $\bullet$

We prove that the optimal sensor scheduling policy has a threshold structure
in terms of both the AoI states of all sensors and the corresponding channel
states, where the channel states of different sensors at different frequencies
are different. To the best of our knowledge, this is the first structural
result of optimal scheduling policies over fading channels in the literature.
In addition, we show that such a structural property exists in a wide range of
dynamic scheduling/resource allocation problems, not limited to remote state
estimations. Interestingly, we also give a counterexample to show when such a
property does not exist.

  * $\bullet$

We first formulate the sensor scheduling problem into an MDP, and then develop
novel structure-enhanced DRL algorithms for solving the problem, building on
the derived threshold properties of the optimal policy. In particular, we
design a structure-enhanced action selection method, which tends to select
actions that obey the threshold structure. Such an action selection method can
explore the action space more effectively and enhance the learning efficiency
of DRL agents. Furthermore, we introduce a structure-enhanced loss function to
add penalties to actions that do not follow the threshold structure. The new
loss function guides the DRL to converge to the optimal policy structure
quickly. We apply the proposed action selection method and the novel loss
function to redesign the most commonly adopted DRL frameworks for scheduling,
i.e., DQN and deep deterministic policy gradient (DDPG), referred to as the
structure-enhanced DQN and DDPG algorithms.

  * $\bullet$

Our extensive numerical results illustrate that the proposed structure-
enhanced DRL algorithms can save the training time by 50% while reducing the
remote estimation MSE by 10% to 25% compared with benchmark DRL algorithms.
Importantly, the structure-enhanced DRL algorithms can converge and perform
well under some system settings that cannot be solved by any of the benchmark
DRL algorithms.

Figure 1: Remote state estimation system with $N$ processes and $M$ channels.

Outline: The system model of the remote state estimation system is described
in Section II. The sensor scheduling problem formulation and the introduction
of the structural properties are presented in Section III. The proofs of
structural properties of the optimal scheduling policy are given in Section
IV. The structure-enhanced DRL algorithms for the formulated problem are
presented in Section V. The numerical results are shown and analyzed in
Section VI, followed by conclusions in Section VII.

##  II System Model

We consider a remote estimation system with $N$ dynamic processes, each
measured by a sensor, which pre-processes the raw measurements and sends its
state estimates to a remote estimator through one of $M$ wireless channels, as
illustrated in Fig. 1.

###  II-A Dynamic Process Model and Local State Estimation

Each dynamic process $n$ is modeled as a discrete-time linear time-invariant
(LTI) system as [11, 20, 21]

$\displaystyle\mathbf{x}_{n,t+1}$
$\displaystyle=\mathbf{A}_{n}\mathbf{x}_{n,t}+\mathbf{w}_{n,t},$ (1)
$\displaystyle\mathbf{y}_{n,t}$
$\displaystyle=\mathbf{C}_{n}\mathbf{x}_{n,t}+\mathbf{v}_{n,t},n\in\\{1,\dots,N\\},t\in\\{1,\dots\\},$

where $\mathbf{x}_{n,t}\in\mathbb{R}^{l_{n}}$ is process $n$’s state at time
$t$, and $\mathbf{y}_{n,t}\in\mathbb{R}^{e_{n}}$ is the state measurement of
the sensor $n$, $\mathbf{A}_{n}\in\mathbb{R}^{l_{n}\times l_{n}}$ and
$\mathbf{C}_{n}\in\mathbb{R}^{e_{n}\times l_{n}}$ are the system matrix and
the measurement matrix, respectively, $\mathbf{w}_{n,t}\in\mathbb{R}^{l_{n}}$
and $\mathbf{v}_{n,t}\in\mathbb{R}^{e_{n}}$ are the process disturbance and
the measurement noise modeled as independent and identically distributed
(i.i.d) zero-mean Gaussian random vectors
$\mathcal{N}(\mathbf{0},\mathbf{W}_{n})$ and
$\mathcal{N}(\mathbf{0},\mathbf{V}_{n})$, respectively. _We assume that the
spectral radius of $\mathbf{A}_{n},\forall n$, is greater than one, which
means that the dynamic processes are unstable, making the remote estimation
problem more interesting_ (see [20] and references therein).

Due to the presence of noise in (1), each sensor $n$ executes a classic Kalman
filter to pre-process the raw measurement and generate state estimate
$\mathbf{x}^{s}_{n,t}$ at each time $t$ [20] as

$\displaystyle\mathbf{x}_{n,t|t-1}^{s}$
$\displaystyle=\mathbf{A}_{n}\mathbf{x}_{n,t-1}^{s}$ (2a)
$\displaystyle\mathbf{P}_{n,t|t-1}^{s}$
$\displaystyle=\mathbf{A}_{n}\mathbf{P}_{n,t-1}^{s}\mathbf{A}_{n}^{\top}+\mathbf{W}_{n}$
(2b) $\displaystyle\mathbf{K}_{n,t}$
$\displaystyle=\mathbf{P}_{n,t|t-1}^{s}\mathbf{C}_{n}^{\top}(\mathbf{C}_{n}\mathbf{P}_{n,t|t-1}^{s}\mathbf{C}_{n}^{\top}+\mathbf{V}_{n})^{-1}$
(2c) $\displaystyle\mathbf{x}_{n,t}^{s}$
$\displaystyle=\mathbf{x}_{n,t|t-1}^{s}+\mathbf{K}_{n,t}(\mathbf{y}_{n,t}-\mathbf{C}\mathbf{x}_{n,t|t-1}^{s})$
(2d) $\displaystyle\mathbf{P}_{n,t}^{s}$
$\displaystyle=(\mathbf{I}_{n}-\mathbf{K}_{n,t}\mathbf{C}_{n})\mathbf{P}_{n,t|t-1}^{s}$
(2e)

where $\mathbf{x}_{n,t|t-1}^{s}$ and $\mathbf{P}_{n,t|t-1}^{s}$ are the prior
state estimate and the corresponding estimation error covariance of sensor
$n$, respectively, $\mathbf{x}_{n,t}^{s}$ and $\mathbf{P}_{n,t}^{s}$ are the
posterior state estimate and the corresponding estimation error covariance of
sensor $n$ at time $t$, respectively. In particular, sensor $n$ sends the
estimate $\mathbf{x}^{s}_{n,t}$ to the remote estimator (not
$\mathbf{y}_{n,t}$) as a packet, once scheduled, and the local state
estimation error covariance matrix is defined as

$\mathbf{P}_{n,t}^{s}\triangleq\mathbb{E}\left[(\mathbf{x}_{n,t}^{s}-\mathbf{x}_{n,t})(\mathbf{x}_{n,t}^{s}-\mathbf{x}_{n,t})^{\top}\right].$
(3)

$\mathbf{K}_{n,t}$ is the Kalman gain of sensor $n$, and $\mathbf{I}_{n}$ is
an identity matrix. Note that (2a) and (2b) present the prediction steps while
(2c), (2d), and (2e) are the updating steps. We note that local Kalman filters
are commonly assumed to operate in the steady state mode in the literature
(see [20] and references therein222The $n$th local Kalman filter converges to
steady state if $(\mathbf{A}_{n},\mathbf{C}_{n})$ is observable and
$(\mathbf{A}_{n},\sqrt{\mathbf{W}_{n}})$ is controllable.). We thus assume
that the error covariance matrix has converged to a constant, i.e.,
$\mathbf{P}_{n,t}^{s}=\bar{\mathbf{P}}_{n},\forall t,n$.

###  II-B Wireless Communications and Remote State Estimation

There are only $M$ wireless channels (e.g., subcarriers) for the $N$ sensors’
transmissions, where $M\leq N$. We consider independent and identically
distributed (i.i.d.) block fading channels, where the channel quality is fixed
during each packet transmission and varies packet by packet, independently.
Let the $N\times M$ matrix $\mathbf{H}_{t}$ denote the channel state of the
system at time $t$, where the element in the $n$th row and $m$th column, say
$h_{n,m,t}\in\mathcal{H}\triangleq\left\\{1,2,\dots,\bar{h}\right\\}$,
represents the channel state between sensor $n$ and the remote estimator at
channel $m$. In particular, there are $\bar{h}$ quantized channel states in
total. The distribution of $h_{n,m,t}$ is given as

$\operatorname{Pr}(h_{n,m,t}=i)=q^{(n,m)}_{i},\forall t,$ (4)

where $\sum_{i=1}^{\bar{h}}q^{(n,m)}_{i}=1,\forall n,m$. The instantaneous
channel state $\mathbf{H}_{t}$ is available at the remote estimator based on
standard channel estimation methods.

The packet drop probability at channel state $i^{\prime}\in\mathcal{H}$ is
denoted as $\tilde{p}_{i^{\prime}}$. Without loss of generality, we assume
that $\tilde{p}_{1}\geq\tilde{p}_{2}\geq\dots\geq\tilde{p}_{\bar{h}}$. We also
define the packet success rate for the channel state $h_{n,m,t}$ as
$p_{n,m,t}\in\\{p_{1},\dots,p_{\bar{h}}\\}$, where $p_{i^{\prime}}\triangleq
1-\tilde{p}_{i^{\prime}}$.

Due to the limited communication channels, only $M$ out of $N$ sensors can be
scheduled at each time step. Let $a_{n,t}\in\\{0,1,2,\dots,M\\}$ represent the
channel allocation for sensor $n$ at time $t$, where

$a_{n,t}=\left\\{\begin{array}[]{ll}0&\text{if sensor $n$ is not
scheduled}\vspace{-0.1cm}\\\ m&\text{if sensor $n$ is scheduled to channel
$m$.}\end{array}\right.$ (5)

In particular, we assume that each sensor can be scheduled to at most one
channel and that each channel is assigned to one sensor [15]. Then, the
constraints on $a_{n,t}$ are given as

$\sum_{m=1}^{M}\bm{\mathbbm{1}}\left(a_{n,t}=m\right)\leq
1,\quad\sum_{n=1}^{N}\bm{\mathbbm{1}}\left(a_{n,t}=m\right)=1,$ (6)

where $\bm{\mathbbm{1}}(\cdot)$ is the indicator function.

Considering schedule actions and packet dropouts, sensor $n$’s estimate may
not be received by the remote estimator in every time slot. We define the
packet reception indicator as

$\eta_{n,t}=\left\\{\begin{array}[]{ll}1,&\text{if sensor $n$'s packet is
received at time $t$}\\\ 0,&\text{otherwise}.\end{array}\right.$

Considering the randomness of $\eta_{n,t}$ and assuming that the remote
estimator performs state estimation at the beginning of each time slot, the
remote state estimate that minimizes the estimation MSE follows the stochastic
recursion:

$\displaystyle\hat{\mathbf{x}}_{n,t+1}$
$\displaystyle=\left\\{\begin{array}[]{ll}\mathbf{A}_{n}\mathbf{x}_{n,t}^{s},&{\text{if
$\eta_{n,t}=1$}}\\\
\mathbf{A}_{n}\hat{\mathbf{x}}_{n,t},&{\text{otherwise}},\end{array}\right.$
(9)

where $\mathbf{A}_{n}$ is the system matrix of process $n$ defined in (1). If
sensor $n$’s packet is not received, then the remote estimator propagates its
estimate in the previous time slot to estimate the current state. From (1) and
(9), we derive the estimation error covariance as

$\displaystyle\mathbf{P}_{n,t}$
$\displaystyle\triangleq\mathbb{E}\left[\left(\hat{\mathbf{x}}_{n,t}-\mathbf{x}_{n,t}\right)\left(\hat{\mathbf{x}}_{n,t}-\mathbf{x}_{n,t}\right)^{\top}\right]$
(10)
$\displaystyle=\left\\{\begin{array}[]{ll}\mathbf{A}_{n}\bar{\mathbf{P}}_{n}\mathbf{A}^{\top}_{n}+\mathbf{W}_{n},&{\text{if
$\eta_{n,t}=1$}}\\\
\mathbf{A}_{n}{\mathbf{P}}_{n,t}\mathbf{A}^{\top}_{n}+\mathbf{W}_{n},&{\text{otherwise}},\end{array}\right.$
(13)

where $\bar{\mathbf{P}}_{n}$ is the local estimation error covariance of
sensor $n$ defined under (3).

Let $\tau_{n,t}\in\\{1,2,\dots\\}$ denote the age-of-information (AoI) of
sensor $n$ at time $t$, which measures the amount of time elapsed since the
latest sensor packet was successfully received. Then, we have

$\tau_{n,t+1}=\begin{cases}1&{\text{if $\eta_{n,t}=1$}}\\\
\tau_{n,t}+1&{\text{otherwise.}}\end{cases}$ (14)

If a sensor is frequently scheduled at good channels, then the corresponding
average AoI is small. However, due to the scheduling constraint (6), this is
often not possible. This leads to estimator stability issues, as studied,
e.g., in [15].

From (13) and (14), the error covariances can be written in terms of the AoI
as

$\mathbf{P}_{n,t}=f_{n}^{\tau_{n,t}}(\bar{\mathbf{P}}_{n}),$ (15)

where
$f_{n}(\mathbf{X})=\mathbf{A}_{n}\mathbf{X}\mathbf{A}_{n}^{\top}+\mathbf{W}_{n}$
and $f^{\tau+1}_{n}(\cdot)=f_{n}(f^{\tau}_{n}(\cdot))$. It has been proved
that the estimation MSE, i.e., $\operatorname{Tr}(\mathbf{P}_{n,t})$,
_monotonically increases with the AoI state $\tau_{n,t}$ [20]_.

##  III Problem Formulation and Threshold structure

In this paper, we aim to find a dynamic scheduling policy $\pi(\cdot)$ that
uses the AoI states of all sensors, as well as the channel states to minimize
the expected total discounted estimation MSE of all $N$ processes over the
infinite time horizon.

######  Problem 1.

$\max_{\pi}\lim_{T\to\infty}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{n=1}^{N}-\gamma^{t}\operatorname{Tr}(\mathbf{P}_{n,t})\right],$
(16)

where $\gamma\in(0,1)$ is a discount factor.

Problem 1 is a Markovian sequential decision-making problem. This is because
the instantaneous estimation MSE, $\mathbf{P}_{n,t}$, only depends on the AoI
state $\tau_{n,t}$ in (15), which is Markovian (14), and the channel states
are i.i.d.. Therefore, we formulate Problem 1 as an MDP.333Not all MDPs for
transmission scheduling of remote estimation systems have a feasible solution.
However, once the remote estimation stability condition in terms of the
dynamic process parameters and the channel statistics is satisfied, the MDP
has a solution. We assume that the remote estimation stability condition of
our system is satisfied, and only focus on the optimal solution of the MDP in
the rest of the paper. The detailed stability condition can be found in our
previous work [15].

###  III-A MDP Formulation

1) The state of the MDP is defined as
$\mathbf{s}_{t}\triangleq\left(\bm{\tau}_{t},\mathbf{H}_{t}\right)\in\mathcal{S}\triangleq\mathbb{N}^{N}\times\mathcal{H}^{N\times
M}$, where
$\bm{\tau}_{t}=(\tau_{1,t},\tau_{2,t},\dots,\tau_{N,t})\in\mathbb{N}^{N}$ is
the AoI state vector. Thus, $\mathbf{s}_{t}$ takes into account both the AoI
and channel states.

2) The overall schedule action of the $N$ sensors is defined as
$\mathbf{a}_{t}=(a_{1,t},a_{2,t},\dots,a_{N,t})\in\mathcal{A}\triangleq\left\\{0,1,2,\dots,M\right\\}^{N}$
under the constraint (6). There are $N!/(N-M)!$ actions of the $N$-choose-$M$
problem in total. The policy $\pi$ is a state-action mapping, i.e.,
$\mathbf{a}_{t}=\pi(\mathbf{s}_{t})$.

3) The transition probability
$\operatorname{Pr}(\mathbf{s}_{t+1}|\mathbf{s}_{t},\mathbf{a}_{t})$ is the
probability of the next state $\mathbf{s}_{t+1}$ given the current state
$\mathbf{s}_{t}$ and the action $\mathbf{a}_{t}$. Since the state transition
is independent of the time index given the action $\mathbf{a}$ and the state
$\mathbf{s}$, we drop the subscript $t$ here and use $\mathbf{s}$ and
$\mathbf{s}^{+}$ to represent the current and the next states, respectively.
Due to the i.i.d. fading channel states, we have

$\operatorname{Pr}(\mathbf{s}^{+}|\mathbf{s},\mathbf{a})=\operatorname{Pr}(\bm{\tau}^{+}|\bm{\tau},\mathbf{H},\mathbf{a})\operatorname{Pr}(\mathbf{H}^{+}),$
(17)

where $\operatorname{Pr}(\mathbf{H}^{+})$ can be obtained from (4), and
$\operatorname{Pr}(\bm{\tau}^{+}|\bm{\tau},\mathbf{H},\mathbf{a})=\prod_{n=1}^{N}\operatorname{Pr}(\tau^{+}_{n}|\tau_{n},\mathbf{H},a_{n})$
and

$\displaystyle\operatorname{Pr}(\tau^{+}_{n}|\tau_{n},\mathbf{H},a_{n})=\left\\{\begin{array}[]{l}p_{n,m},\qquad\;\;\text{if
$\tau^{+}_{n}=1,a_{n}=m$}\\\ 1-p_{n,m},\ \ \,\text{if
$\tau^{+}_{n}=\tau_{n}+1,a_{n}=m$}\\\ 1,\qquad\quad\,\text{\ \ if
$\tau^{+}_{n}=\tau_{n}+1,a_{n}=0$}\\\ 0,\qquad\quad\,{\ \
\text{otherwise.}}\end{array}\right.$ (22)

which is derived based on (4) and (14).

4) The immediate reward of Problem 1 at time $t$ is defined as the negative
sum estimation MSE, $\sum_{n=1}^{N}-\operatorname{Tr}(\mathbf{P}_{n,t})$.
Since $\mathbf{P}_{n,t}$ defined in (15) is a function of $\tau_{n,t}$, the
reward is represented as $r(\mathbf{s}_{t})$ and _monotonically decreases with
each AoI state_.

###  III-B Threshold Structure of the Optimal MDP Solution

Unlike the existing works [7, 18], which only considered oversimplified
systems over static channels, we aim to derive the structural property of the
optimal policy of the general multi-sensor-multi-channel system over fading
channels as below.

######  Definition 1 (Channel-State Threshold Policy).

For a channel-state threshold scheduling policy, if channel $m$ is assigned to
sensor $n$ at the state $\mathbf{s}=(\bm{\tau},\mathbf{H})$, then for state
$\mathbf{s}^{\prime}=(\bm{\tau},\mathbf{H}^{\prime}_{n,m})$, where
$\mathbf{H}^{\prime}_{n,m}$ is identical to $\mathbf{H}$ except the
sensor-$n$-channel-$m$ state with $h^{\prime}_{n,m}>h_{n,m}$, then channel $m$
is still assigned to sensor $n$.

######  Definition 2 (AoI-State Threshold Policy).

For an AoI-state threshold scheduling policy, if channel $m$ is assigned to
sensor $n$ at the state $\mathbf{s}=(\bm{\tau},\mathbf{H})$, then for state
$\mathbf{s}^{\prime}=(\bm{\tau}^{\prime}_{(n)},\mathbf{H})$, where
$\bm{\tau}^{\prime}_{(n)}$ is idential to $\bm{\tau}$ except sensor $n$’s AoI
with $\tau^{\prime}_{n}\geq\tau_{n}$, then either channel $m$ or a better
channel is assigned to sensor $n$.

Definition 1 states that sensor $n$ is scheduled at channel $m$ at a certain
state, if the channel quality of $h_{n,m}$ improves while the AoI and the
other channel states are the same, then the threshold policy still assigns
channel $m$ to sensor $n$. For Definition 2, if the AoI state of sensor $n$ is
increased while the other states remain the same, the policy must schedule
sensor $n$ to a channel that is no worse than the previous one.

To illustrate that an optimal policy may have a threshold structure, we find
the optimal policy of a two-sensor-single-channel system by solving the MDP
with the conventional value iteration algorithm, which is illustrated in Fig.
2. We see that action-switching curves exist in both AoI and channel state
spaces, and the properties in Definitions 1 and 2 are observed. Inspired by
the above result, in the following, we will prove that the optimal policy has
the structural properties in Definitions 1 and 2.444We note that in [7, 18],
only threshold structural results in terms of the AoI states are proved over
static channels. Moreover, the proofs have some limitations: 1) In [7], the
authors proved the threshold structure for a multi-dimensional state and
action scenario based on Theorem 8.11.3 in [22], which, however, can only be
used for single-dimensional scenarios. 2) In [18], the proof of the optimal
policy’s structural property only considered a part of the action space;
however, the full action space must be examined to show the optimally.

(a) Schedule actions at AoI states

(b) Schedule actions at channel states

Figure 2: Structure of the optimal scheduling policy with $N=2$ and $M=1$,
where $\bullet$ and $\times$ represent the schedule of sensor 1 and 2,
respectively.

##  IV Threshold Structure of Optimal Policies

We derive the structural properties of the optimal scheduling policy by using
value iteration concepts, which require the definition of the optimal value
function, $V^{*}(\mathbf{s}_{t}):\mathcal{S}\to\mathbb{R}$, and the state-
action value function,
$Q(\mathbf{s}_{t},\mathbf{a}_{t}):\mathcal{S}\times\mathcal{A}\to\mathbb{R}$
as below.

Given the current state $\mathbf{s}_{t}=(\bm{\tau}_{t},\mathbf{H}_{t})$, the
optimal value function is the maximum expected discounted sum of the future
cost, i.e., achieved by the optimal policy $\pi^{*}(\cdot)$.

$V^{*}(\mathbf{s}_{t})=\max_{\pi}\mathbb{E}\left[\sum_{t^{\prime}=t}^{\infty}\gamma^{t^{\prime}-t}r\left(\mathbf{s}_{t^{\prime}}\right)\right].$
(23)

The optimal value function satisfies the Bellman equation:

$\displaystyle
V^{*}(\mathbf{s}_{t})=r(\mathbf{s}_{t})+\gamma\max_{\mathbf{a}_{t}\in\mathcal{A}}\left[\sum_{\mathbf{s}_{t+1}}\operatorname{Pr}(\mathbf{s}_{t+1}|\mathbf{s}_{t},\mathbf{a}_{t})V^{*}(\mathbf{s}_{t+1})\right],$
(24)

where the optimal action $\mathbf{a}^{*}$ is obtained by the optimal policy
$\pi^{*}(\cdot)$, i.e.,

$\mathbf{a}_{t}^{*}\triangleq\pi^{*}(\mathbf{s}_{t})=\mathop{\arg\max}_{\mathbf{a}_{t}\in\mathcal{A}}\left[\sum_{\mathbf{s}_{t+1}}\operatorname{Pr}(\mathbf{s}_{t+1}|\mathbf{s}_{t},\mathbf{a}_{t})V^{*}(\mathbf{s}_{t+1})\right].$
(25)

Given the current state-action pair $\mathbf{s}_{t}$ and $\mathbf{a}_{t}$, the
state-action value function, which is also called the Q-value function,
measures the expected discounted sum of the future cost under the optimal
policy $\pi^{*}(\cdot)$ as

$Q(\mathbf{s}_{t},\mathbf{a}_{t})=r(\mathbf{s}_{t})+\gamma\sum_{\mathbf{s}_{t+1}}\operatorname{Pr}(\mathbf{s}_{t+1}|\mathbf{s}_{t},\mathbf{a}_{t})V^{*}(\mathbf{s}_{t+1}).$
(26)

From (24) and (26), it directly follows that the optimal value function and
the Q-value function satisfy:

$V^{*}(\mathbf{s}_{t})=Q(\mathbf{s}_{t},\mathbf{a}_{t}^{*})\geq
Q(\mathbf{s}_{t},\mathbf{a}_{t}).$ (27)

For notation simplicity, we use $\mathbf{a},\mathbf{s},\mathbf{s}^{+}$ to
represent $\mathbf{a}_{t},\mathbf{s}_{t},\mathbf{s}_{t+1}$ in the following.

We prove the channel-state and the AoI-state threshold properties of the
optimal scheduling policy based on the classical value iteration algorithm, as
it can achieve the optimal solution [23, 24]. In the value iteration, the
initial value function and its $\tilde{t}$-th iteration are
$V^{0}(\mathbf{s})\in\mathcal{V}$ and
$V^{\tilde{t}}(\mathbf{s})\in\mathcal{V}$, respectively, where $\mathcal{V}$
is the set of any measurable function, i.e.,
$\mathcal{V}:\mathcal{S}\to\mathbb{R}$. At the $\tilde{t}$-th iteration, we
have $V^{\tilde{t}+1}=\mathsf{B}\left[V^{\tilde{t}}\right]$, where
$\mathsf{B}[\cdot]:\mathcal{V}\to\mathcal{V}$ is the Bellman operator:

$\displaystyle\mathsf{B}\left[V^{\tilde{t}}\right](\mathbf{s})=r(\mathbf{s})+\gamma\max_{\mathbf{a}\in\mathcal{A}}\left[\sum_{\mathbf{s}^{+}}\operatorname{Pr}(\mathbf{s}^{+}|\mathbf{s},\mathbf{a})V^{\tilde{t}}(\mathbf{s}^{+})\right].$
(28)

We next elucidate the convergence and the optimality of value iterations.

######  Lemma 1 ([23, 24] ).

If the optimal policy exists, then the operator $\mathsf{B}$ has a unique
fixed point $V^{*}\in\mathcal{V}$ and for all $V^{0}\in\mathcal{V}$, the
sequence $\\{V^{\tilde{t}}\\}$ defined by
$V^{\tilde{t}+1}=\mathsf{B}[V^{\tilde{t}}]$ converges in norm to $V^{*}$, i.e.

$\lim_{\tilde{t}\to\infty}V^{\tilde{t}}=V^{*}.$ (29)

Before proceeding further, we derive the following technical lemma about the
monotonicity of the optimal value function.

######  Lemma 2 (Monotonicity).

Consider states $\mathbf{s}=(\bm{\tau},\mathbf{H})$ and
$\mathbf{s}^{\prime}=(\bm{\tau}^{\prime}_{(i)},\mathbf{H})$, where
$\bm{\tau}^{\prime}_{(i)}=(\tau_{1},\dots,\tau^{\prime}_{i},\dots,\tau_{N})$
and $\tau^{\prime}_{i}\geq\tau_{i}$. The following holds

$V^{*}(\mathbf{s}^{\prime})\leq V^{*}(\mathbf{s}).$ (30)

###### Proof.

See Appendix A. ∎

Lemma 2 will assist in the comparison of value functions with different AoI
states in the proof of the channel-state threshold and the AoI-state threshold
properties.

###  IV-A Channel-State Threshold Property

In this part, we completely prove that the optimal policy of a general multi-
sensor-multi-channel system has the channel-state threshold property in
Definition 1.

######  Theorem 1.

The optimal policy $\pi^{*}(\cdot)$ of the multi-sensor-multi-channel system
has the channel-state threshold property in Definition 1.

###### Proof.

From the Q-value definition in (26), the theorem can be translated as: if for
state $\mathbf{s}=(\bm{\tau},\mathbf{H})$, the inequality
$Q(\mathbf{s},\mathbf{a}^{*})\geq
Q(\mathbf{s},\mathbf{a}),\forall\mathbf{a}\in\mathcal{A}$ exists, where
${a}^{*}_{i}=m$, then for state
$\mathbf{s}^{\prime}=(\bm{\tau},\mathbf{H}^{\prime}_{i,m})$, where
$\mathbf{H}^{\prime}_{i,m}$ and $\mathbf{H}$ are identical except the element
$h^{\prime}_{i,m}>h_{i,m}$, the following inequality holds
$Q(\mathbf{s}^{\prime},{\mathbf{a}^{\prime}}^{*})\geq
Q(\mathbf{s}^{\prime},\mathbf{a})$, where ${\mathbf{a}^{\prime}}^{*}$ is the
optimal action at the state $\mathbf{s}^{\prime}$ with
${a^{\prime}_{i}}^{*}=m$. Since
$Q(\mathbf{s}^{\prime},{\mathbf{a}^{\prime}}^{*})\geq
Q(\mathbf{s}^{\prime},\mathbf{a}^{*})$, we only need to prove
$Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq
Q(\mathbf{s}^{\prime},\mathbf{a}^{\prime})$, where ${a}^{\prime}_{i}\neq m$.
To prove $Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq
Q(\mathbf{s}^{\prime},\mathbf{a}^{\prime})$, we will prove
$Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq Q(\mathbf{s},\mathbf{a}^{*})$ and
then
$Q(\mathbf{s},\mathbf{a}^{\prime})=Q(\mathbf{s}^{\prime},\mathbf{a}^{\prime})$.
In the following, we use $\mathbf{H}^{\prime}$ to represent
$\mathbf{H}^{\prime}_{i,m}$ for the notation simplicity.

First, from (4) and (14), we have

$\displaystyle\operatorname{Pr}(\bm{\tau}^{+}|\bm{\tau},\mathbf{H},\mathbf{a})=\prod_{n=1}^{N}\operatorname{Pr}(\tau_{n}^{+}|\tau_{n},\mathbf{h}_{n},a_{n})=\operatorname{Pr}(\tau_{i}^{+}|\tau_{i},\mathbf{h}_{i},a_{i})\operatorname{Pr}(\bm{\tau}_{\backslash
i}^{+}|\bm{\tau}_{\backslash i},\mathbf{H}_{\backslash
i},\mathbf{a}_{\backslash i}),$ (31)

where $\bm{\tau}_{\backslash
i}=(\tau_{1},\dots,\tau_{i-1},\tau_{i+1},\dots,\tau_{N})$ and
$\mathbf{a}_{\backslash i}=(a_{1},\dots,a_{i-1},a_{i+1},\dots,a_{N})$
represent the AoI states and the actions of all sensors except sensor $i$,
respectively, and $\mathbf{h}_{i}=(h_{i,1},h_{i,2},\dots,h_{i,M})$ is the
vector channel states between sensor $i$ and the remote estimator and
$\mathbf{H}_{\backslash i}=(\mathbf{h}_{1},\dots,\mathbf{h}_{i-1},\\\
\mathbf{h}_{i+1},\dots,\mathbf{h}_{N})$. By using (17) and (31), it can be
derived that

$\displaystyle Q(\mathbf{s},\mathbf{a})$
$\displaystyle=r(\mathbf{s})+\gamma\sum_{\mathbf{s}^{+}}\operatorname{Pr}(\mathbf{s}^{+}|\mathbf{s},\mathbf{H},\mathbf{a})V^{*}(\mathbf{s}^{+})$
(32)
$\displaystyle=r(\mathbf{s})+\gamma\sum_{\mathbf{H}^{+}}\sum_{\bm{\tau}^{+}}\operatorname{Pr}(\mathbf{H}^{+})\operatorname{Pr}(\bm{\tau}^{+}|\bm{\tau},\mathbf{H},\mathbf{a})V^{*}(\mathbf{s}^{+})$
(33)
$\displaystyle=r(\mathbf{s})+\gamma\sum_{\mathbf{H}^{+}}\sum_{\bm{\tau}_{\backslash
i}^{+}}\sum_{\tau_{i}^{+}}\operatorname{Pr}(\mathbf{H}^{+})\operatorname{Pr}(\bm{\tau}_{\backslash
i}^{+}|\bm{\tau}_{\backslash i},\mathbf{H}_{\backslash
i},\mathbf{a}_{\backslash
i})\operatorname{Pr}(\tau_{i}^{+}|\tau_{i},\mathbf{h}_{i},a_{i})V^{*}(\mathbf{s}^{+}).$
(34)

Based on (34), we have

$\displaystyle
Q(\mathbf{s}^{\prime},\mathbf{a}^{*})=r(\mathbf{s}^{\prime})\\!+\\!\gamma\sum_{{\mathbf{H}^{\prime}}^{+}}\sum_{\bm{\tau}_{\backslash
i}^{+}}\sum_{\tau_{i}^{+}}\operatorname{Pr}({\mathbf{H}^{\prime}}^{+})\operatorname{Pr}(\bm{\tau}_{\backslash
i}^{+}|\bm{\tau}_{\backslash i},\mathbf{H}_{\backslash
i},\mathbf{a}^{*}_{\backslash
i})\operatorname{Pr}(\tau_{i}^{+}|\tau_{i},\mathbf{h}^{\prime}_{i},a^{*}_{i})V^{*}({\mathbf{s}^{\prime}}^{+})$
(35) $\displaystyle\quad\
\\!\geq\\!r(\mathbf{s})\\!+\\!\gamma\sum_{\mathbf{H}^{+}}\sum_{\bm{\tau}_{\backslash
i}^{+}}\sum_{\tau_{i}^{+}}\operatorname{Pr}(\mathbf{H}^{+})\operatorname{Pr}(\bm{\tau}_{\backslash
i}^{+}|\bm{\tau}_{\backslash i},\\!\mathbf{H}_{\backslash
i},\\!\mathbf{a}^{*}_{\backslash
i})\operatorname{Pr}(\tau_{i}^{+}|\tau_{i},\\!\mathbf{h}_{i},\\!a^{*}_{i})V^{*}(\mathbf{s}^{+})\\!=\\!Q(\mathbf{s},\mathbf{a}^{*}),$
(36)

where the inequality is derived by replacing the parameter
${\mathbf{H}^{\prime}}^{+}$ with ${\mathbf{H}}^{+}$, and then using
$r(\mathbf{s}^{\prime})=r(\mathbf{s})$,
$h^{\prime}_{i,m}>h_{i,m},a^{*}_{i}=m$, and the following inequality

$\displaystyle p^{\prime}_{i,m}\\!V^{*}\\!(1,\\!\bm{\tau}_{\backslash
i}^{+},\\!\mathbf{H}^{+})\\!+\\!(1\\!\\!-\\!p^{\prime}_{i,m})V^{*}\\!(\tau_{i}\\!+\\!1,\\!\bm{\tau}_{\backslash
i}^{+},\\!\mathbf{H}^{+})\\!\geq\\!p_{i,m}\\!V^{*}\\!(1,\\!\bm{\tau}_{\backslash
i}^{+},\\!{\mathbf{H}}^{+})\\!+\\!(1\\!\\!-\\!p_{i,m})V^{*}\\!(\tau_{i}\\!+\\!1,\\!\bm{\tau}_{\backslash
i}^{+},\\!{\mathbf{H}}^{+})$ (37)

achieved by $p^{\prime}_{i,m}\geq p_{i,m}$ and
$V^{*}(1,\\!\bm{\tau}_{\backslash i}^{+},\\!\mathbf{H}^{+})\geq
V^{*}(\tau_{i}\\!+\\!1,\\!\bm{\tau}_{\backslash i}^{+},\\!\mathbf{H}^{+})$
from Lemma 2.

Second, we derive that

$\displaystyle
Q(\mathbf{s},\mathbf{a})=r(\mathbf{s})\\!+\\!\gamma\sum_{\mathbf{H}^{+}}\sum_{\bm{\tau}_{\backslash
i}^{+}}\sum_{\tau_{i}^{+}}\operatorname{Pr}(\mathbf{H}^{+})\operatorname{Pr}(\bm{\tau}_{\backslash
i}^{+}|\bm{\tau}_{\backslash i},\mathbf{H}_{\backslash
i},\mathbf{a}^{\prime}_{\backslash
i})\operatorname{Pr}(\tau_{i}^{+}|\tau_{i},\mathbf{h}_{i},a^{\prime}_{i})V^{*}(\mathbf{s}^{+})$
(38) $\displaystyle\quad\
\\!=\\!r(\mathbf{s}^{\prime})\\!+\\!\gamma\sum_{{\mathbf{H}^{\prime}}^{+}}\sum_{\bm{\tau}_{\backslash
i}^{+}}\sum_{\tau_{i}^{+}}\operatorname{Pr}({\mathbf{H}^{\prime}}^{+})\operatorname{Pr}(\bm{\tau}_{\backslash
i}^{+}|\bm{\tau}_{\backslash i},\\!\mathbf{H}_{\backslash
i},\\!\mathbf{a}^{\prime}_{\backslash
i})\\!\operatorname{Pr}(\tau_{i}^{+}|\tau_{i},\\!\mathbf{h}^{\prime}_{i},\\!a^{\prime}_{i})V^{*}({\mathbf{s}^{\prime}}^{+})\\!=\\!Q(\mathbf{s}^{\prime},\\!\mathbf{a}),$
(39)

where the second equality is derived by replacing the parameter
${\mathbf{H}^{\prime}}^{+}$ with ${\mathbf{H}}^{+}$, and then using
$h^{\prime}_{i,m}>h_{i,m},a^{\prime}_{i}\neq m$, and
$\operatorname{Pr}(\tau_{i}^{+}|\tau_{i},\mathbf{h}_{i},a^{\prime}_{i})V^{*}(\mathbf{s}^{+})=\operatorname{Pr}(\tau_{i}^{+}|\tau_{i},\mathbf{h}^{\prime}_{i},a^{\prime}_{i})V^{*}({\mathbf{s}^{\prime}}^{+})$.
∎

###  IV-B AoI-State Threshold Property

We consider three network scenarios with different numbers of sensors and
channels as below.

####  IV-B1 Two-sensor-single-channel systems

As presented in Theorem 2, we prove that the optimal policy of a two-sensor-
single-channel system is an AoI-state threshold policy in Definition 2. In
other words, if the optimal action at a state is to schedule sensor $n$, then
the optimal action is still to schedule sensor $n$ at all states that only
increase sensor $n$’s AoI.

######  Theorem 2.

The optimal policy $\pi^{*}(\cdot)$ of the two-sensor-single-channel system
has the AoI-state threshold property in Definition 2: suppose that for state
$\mathbf{s}=(\bm{\tau},\mathbf{H})$, the optimal action is to schedule sensor
$i$, i.e. $a^{*}_{i}=1$, then for state
$\mathbf{s}^{\prime}=(\bm{\tau}^{\prime}_{(i)},\mathbf{H}),$ where
$\tau^{\prime}_{i}\geq\tau_{i}$, the optimal action is still
$a^{\prime*}_{i}=1$.

######  Remark 1 (Analytical Challenges).

Although Theorem 2 looks simple, the proof is highly nontrivial.

First, the main difficulty of the proof is that different actions cause the
transition of the AoI states in multiple dimensions, resulting in the
comparison of multi-dimensional value functions. However, Lemma 2 can only
compare the optimal value functions with AoI state changes within one
dimension. For example, given states
$\mathbf{s}=(\bm{\tau},\mathbf{H}),\mathbf{s}^{\prime}=(\bm{\tau}^{\prime},\mathbf{H})$,
and $\mathbf{s}^{\circ}=(\bm{\tau}^{\circ},\mathbf{H})$, where
$\bm{\tau}=(\tau_{i},\tau_{j}),\bm{\tau}^{\prime}=(\tau_{i}^{\prime},\tau_{j}),\bm{\tau}^{\circ}=(\tau_{i}^{\prime},\tau_{j}^{\prime\prime}),\tau_{i}^{\prime}\geq\tau_{i}$,
and $\tau_{j}^{\prime\prime}\leq\tau_{j}$, it is easy to have
$V(\mathbf{s})\geq V(\mathbf{s}^{\prime})$, but is not possible to compare
$V(\mathbf{s})$ and $V(\mathbf{s}^{\circ})$.

Second, one may think that the proof of Theorem 2 is intuitive as a larger AoI
of sensor $i$ results in a lower reward, and scheduling sensor $i$ can improve
the reward more efficiently than scheduling other sensors. This is a
misunderstanding. Theorem 2 is equivalent to saying that the inequality
$Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq Q(\mathbf{s}^{\prime},\mathbf{a})$
can be derived from $Q(\mathbf{s},\mathbf{a}^{*})\geq
Q(\mathbf{s},\mathbf{a})$, where $a^{*}_{i}=1$. We drop the constant channel
state, $\mathbf{H}$, in the optimal value functions for simplicity. Based on
(26), $Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq
Q(\mathbf{s}^{\prime},\mathbf{a})$ is equal to

$\displaystyle\\!\\!\\!p_{i,1}V^{*}(1,\tau_{j}\\!+\\!1)\\!+\\!(1\\!-\\!p_{i,1})V^{*}(\tau^{\prime}_{i}\\!+\\!1,\tau_{j}\\!+\\!1)\\!\geq\\!p_{j,1}V^{*}(\tau^{\prime}_{i}\\!+\\!1,1)\\!+\\!(1\\!-\\!p_{j,1})V^{*}(\tau^{\prime}_{i}\\!+\\!1,\tau_{j}\\!+\\!1),$
(40)

and $Q(\mathbf{s},\mathbf{a}^{*})\geq Q(\mathbf{s},\mathbf{a})$ is equal to

$\displaystyle\\!\\!\\!p_{i,1}V^{*}(1,\tau_{j}\\!+\\!1)\\!+\\!(1\\!-\\!p_{i,1})V^{*}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1)\\!\geq\\!p_{j,1}V^{*}(\tau_{i}\\!+\\!1,1)\\!+\\!(1\\!-\\!p_{j,1})V^{*}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1).$
(41)

We see that (40) cannot be derived directly based on (41), since it also
related to the packet success rates of different sensors, i.e. $p_{i,1}$ and
$p_{j,1}$.

###### Proof.

As mentioned in Remark 1, we will prove (40) based on (41), which depends on
the key technical lemma below in terms of the optimal value functions and the
packet success rates, which depends on the channel states.

######  Definition 3 (Meet and Joint [25, 22]).

Let $x^{\prime}\vee x^{\prime\prime}=\max\\{x^{\prime},x^{\prime\prime}\\}$
and $x^{\prime}\wedge x^{\prime\prime}=\min\\{x^{\prime},x^{\prime\prime}\\}$
denote the join and meet of two real numbers, respectively. Define
$\mathbf{x}^{\prime}\vee\mathbf{x}^{\prime\prime}=(x^{\prime}_{1}\vee
x^{\prime\prime}_{1},\dots,x^{\prime}_{n}\vee x^{\prime\prime}_{n})$ and
$\mathbf{x}^{\prime}\wedge\mathbf{x}^{\prime\prime}=(x^{\prime}_{1}\wedge
x^{\prime\prime}_{1},\dots,x^{\prime}_{n}\wedge x^{\prime\prime}_{n})$ as the
joint and meet of the vectors $\mathbf{x}^{\prime}$ and
$\mathbf{x}^{\prime\prime}\in\mathbb{R}^{n}$, respectively.

######  Lemma 3 (Probabilistic Supermodularity, $N=2$, $M=1$).

Given states $\mathbf{s}=(\bm{\tau},\mathbf{H})$ and
$\mathbf{s}^{\circ}=(\bm{\tau}^{\circ},\mathbf{H})$, where
$\bm{\tau}^{\circ}=(\tau^{\prime\prime}_{i},\tau^{\prime}_{j}),\tau^{\prime\prime}_{i}\leq\tau_{i}$,
$\tau^{\prime}_{j}\geq\tau_{j}$, and $i\neq j\in\\{1,2\\}$, the following
holds

$p_{j,,1}V^{*}(\mathbf{s}\wedge\mathbf{s}^{\circ})+(p_{j,1}-p_{i,1})V^{*}(\mathbf{s}\vee\mathbf{s}^{\circ})\geq
p_{j,1}V^{*}(\mathbf{s})+(p_{j,1}-p_{i,1})V^{*}(\mathbf{s}^{\circ}).$ (42)

###### Proof.

See Appendix B. ∎

In what follows, we denote the state as $\mathbf{s}=(\tau_{i},\tau_{j})$,
since the transition of the channel states is constant during the proof. From
(41), it directly follows that

$\displaystyle p_{i,1}V^{*}(1,\tau_{j}\\!+\\!1)\geq
p_{j,1}V^{*}(\tau_{i}\\!+\\!1,1)\\!-\\!(p_{j,1}\\!-\\!p_{i,1})V^{*}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1).$
(43)

By applying Lemma 3 to the right-hand side of (43), we have

$\displaystyle p_{i,1}V^{*}(1,\tau_{j}+1)\geq
p_{j,1}V^{*}(\tau^{\prime}_{i,1}+1,1)-(p_{j,1}-p_{i,1})V^{*}(\tau^{\prime}_{i}+1,\tau_{j}+1),$

which is exactly (40). Thus, we have proved
$Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq Q(\mathbf{s}^{\prime},\mathbf{a})$.
∎

####  IV-B2 Multi-sensor-single-channel systems

It is intractable to prove that the optimal policy has the AoI-state threshold
property in this case. Similar to the two-sensor case, we first try to prove
the probabilistic supermodularity. However, there are more than two AoI states
changing when applying value iterations, making it difficult to find a set of
useful inequalities to prove the target inequality. We can also construct some
other inequalities in terms of the optimal value function and the packet
success rates that can be used to prove the threshold property, but these
inequalities cannot be proved either.

Although the AoI-state threshold property of the optimal policy is not fully
derived, we prove an asymptotic structural property as below.

######  Theorem 3.

The optimal policy $\pi^{*}(\cdot)$ of a multi-sensor-single-channel system
with $N>2$ has an asymptotic AoI-state threshold property: suppose that for
state $\mathbf{s}=(\bm{\tau},\mathbf{H})$, the optimal action is to transmit
the estimation of sensor $i$, i.e. $a^{*}_{i}=1$, then for all states
$\mathbf{s}^{\prime}=(\bm{\tau}^{\prime}_{(i)},\mathbf{H}),$ where
$\tau^{\prime}_{i}\gg\tau_{i}$, the optimal policy is still
$a^{\prime*}_{i}=1$.

Theorem 3 shows that the threshold structure still exists in the optimal
policy of a multi-sensor-single-channel system, at least in the large AoI
domain.

###### Proof.

This theorem is equivalent to stating that if for state
$\mathbf{s}=(\bm{\tau},\mathbf{H})$, the inequality
$Q(\mathbf{s},\mathbf{a}^{*})\geq
Q(\mathbf{s},\mathbf{a}),\forall\mathbf{a}\in\mathcal{A}$ exists, where
$a_{i}^{*}=1$, then for state
$\mathbf{s}^{\prime}=(\bm{\tau}^{\prime}_{(i)},\mathbf{H}),$ where
$\tau^{\prime}_{i}\gg\tau_{i}$, we have
$Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq Q(\mathbf{s}^{\prime},\mathbf{a})$.
Similar to Theorem 2, we need to develop the following lemmas yet in an
asymptotic manner.

######  Lemma 4.

Given states $\mathbf{s}=(\bm{\tau},\mathbf{H})$ and
$\mathbf{s}^{\prime}=(\bm{\tau}^{\prime}_{(i)},\mathbf{H})$, where
$\tau^{\prime}_{i}\gg\tau_{i}$, the following holds

$V^{*}(\mathbf{s}^{\prime})\ll V^{*}(\mathbf{s}).$ (44)

###### Proof.

See Appendix C. ∎

Based on Lemma 4, we derive the asymptotic probabilistic supermodularity
below.

######  Lemma 5 (Asymptotic Probabilistic Supermodularity, $N>2$, $M=1$).

Given states $\mathbf{s}=(\bm{\tau},\mathbf{H})$ and
$\mathbf{s}^{\circ}=(\bm{\tau}^{\circ},\mathbf{H})$, where
$\bm{\tau}=(\tau_{1},\dots,\tau_{i},\dots,\tau_{j},\dots,\tau_{N})$ and
$\bm{\tau}^{\circ}=(\tau_{1},\dots,\tau^{\prime\prime}_{i},\dots,\tau^{\prime}_{j},\dots,\tau_{N})$
with $\tau_{i}\gg\tau^{\prime\prime}_{i}$, $\tau_{j}\leq\tau^{\prime}_{j}$,
and $i\neq j\in\\{1,\dots,N\\}$, the probabilistic supermodularity in (42)
holds.

###### Proof.

See Appendix D. ∎

In the following, we will prove $Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq
Q(\mathbf{s}^{\prime},\mathbf{a})$ based on $Q(\mathbf{s},\mathbf{a}^{*})\geq
Q(\mathbf{s},\mathbf{a})$ and similar to the proof of Theorem 2, we write the
state as $\mathbf{s}=(\tau_{i},\tau_{j},\bm{\tau}_{\backslash i,j})$. Using
(26), $Q(\mathbf{s},\mathbf{a}^{*})\geq Q(\mathbf{s},\mathbf{a})$ is equal to

$\displaystyle p_{i,1}V^{*}(1,\tau_{j}+1,\bm{\tau}_{\backslash i,j}^{+})\geq
p_{j,1}V^{*}(\tau_{i}+1,1,\bm{\tau}_{\backslash
i,j}^{+})-(p_{j,1}-p_{i,1})V^{*}(\tau_{i}+1,\tau_{j}+1,\bm{\tau}_{\backslash
i,j}^{+}).$ (45)

By applying Lemma 5 to the right-hand side of (45), we have

$p_{i,1}V^{*}(1,\tau_{j}+1,\bm{\tau}_{\backslash i,j}^{+})\geq
p_{j,1}V^{*}(\tau^{\prime}_{i}\\!+\\!1,1,\bm{\tau}_{\backslash
i,j}^{+})\\!-\\!(p_{j,1}\\!-\\!p_{i,1})V^{*}(\tau^{\prime}_{i}\\!+\\!1,\tau_{j}\\!+\\!1,\bm{\tau}_{\backslash
i,j}^{+}),$ (46)

and thus

$\displaystyle p_{i,1}V^{*}(1,\tau_{j}\\!+\\!1,\bm{\tau}_{\backslash
i,j}^{+})\\!+\\!(1\\!-\\!p_{i,1})V^{*}(\tau^{\prime}_{i}\\!+\\!1,\tau_{j}\\!+\\!1,\bm{\tau}_{\backslash
i,j}^{+})$ (47) $\displaystyle\quad\geq
p_{j,1}V^{*}(\tau^{\prime}_{i}\\!+\\!1,1,\bm{\tau}_{\backslash
i,j}^{+})+(1\\!-\\!p_{j,1})V^{*}(\tau^{\prime}_{i}\\!+\\!1,\tau_{j}\\!+\\!1,\bm{\tau}_{\backslash
i,j}^{+}),$ (48)

which is exactly $Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq
Q(\mathbf{s}^{\prime},\mathbf{a})$ based on (26). ∎

####  IV-B3 Multi-sensor-multi-channel systems

This case is more complex than the single-channel one, due to the increased
state dimension introduced by the multi-dimensional channel. Thus, the AoI-
state threshold property of the optimal policy cannot be derived strictly. In
the following, we develop another structural property of the optimal policy.

######  Proposition 1.

If for state $\mathbf{s}=(\bm{\tau},\mathbf{H})$, the optimal action is
$\mathbf{a}^{*}=(a^{*}_{1},\dots,a^{*}_{i},\dots,a^{*}_{N}),a^{*}_{i}=m$, and
for state $\mathbf{s}^{\prime}=(\bm{\tau}^{\prime}_{(i)},\mathbf{H}),$ where
$\tau^{\prime}_{i}\geq\tau_{i}$, the optimal channel assignments except for
channel $m$ keep constant, i.e. $a^{*}_{n}={a^{\prime}_{n}}^{*},\forall
a^{*}_{n}\neq 0,$ and $i\neq n$, then the optimal action for sensor $j$ at
state $\mathbf{s}^{\prime}$ is to not occupy channel $m$, if sensor $j$ is not
scheduled at state $\mathbf{s}$, i.e., ${a_{j}}^{*}=0$, and its channel
condition is worse than that of sensor $i$, i.e., $h_{i,m}\geq h_{j,m}$.

Proposition 1 says that sensor $i$’s allocated channel won’t be occupied by
other sensors with worse channel conditions when sensor $i$’s AoI increases
and the optimal channel assignment rules for other channels remain the same.

###### Proof.

This proposition equivalent to that if for state
$\mathbf{s}=(\bm{\tau},\mathbf{H})$, the inequality
$Q(\mathbf{s},\mathbf{a}^{*})\geq Q(\mathbf{s},\mathbf{a})$ exists, where
$a^{*}_{i}=m$ and $a^{*}_{j}=0$, then for state
$\mathbf{s}^{\prime}=(\bm{\tau}^{\prime}_{(i)},\mathbf{H}),$ where
$\tau^{\prime}_{i}\geq\tau_{i}$, the following inequality holds
$Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq
Q(\mathbf{s}^{\prime},\mathbf{a}^{\prime})$, where $a^{\prime}_{j}=m,\forall
h_{i,m}\geq h_{j,m}$ and $a^{*}_{\backslash i,j}=a^{\prime}_{\backslash i,j}$.

Therefore, we will prove $Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq
Q(\mathbf{s}^{\prime},\mathbf{a}^{\prime})$ based on
$Q(\mathbf{s},\mathbf{a}^{*})\geq Q(\mathbf{s},\mathbf{a})$ in the following.
Taking (34) into $Q(\mathbf{s},\mathbf{a}^{*})\geq
Q(\mathbf{s},\mathbf{a}^{\prime})$, we have

$\displaystyle\sum_{\bm{\tau}_{\backslash
i,j}^{+}}\sum_{\mathbf{H}^{+}}\sum_{\tau_{i}^{+}}\sum_{\tau_{j}^{+}}\operatorname{Pr}(\bm{\tau}_{\backslash
i,j}^{+}|\bm{\tau}_{\backslash i,j},\mathbf{H}_{\backslash
i,j},\mathbf{a}^{*}_{\backslash
i,j})\operatorname{Pr}(\mathbf{H}^{+})\operatorname{Pr}(\tau_{i}^{+}|\tau_{i},\\!\mathbf{h}_{i},\\!a^{*}_{i})\operatorname{Pr}(\tau_{j}^{+}|\tau_{j},\\!\mathbf{h}_{j},\\!a^{*}_{j})V^{*}(\mathbf{s}^{+})$
(49) $\displaystyle\\!\geq\\!\sum_{\bm{\tau}_{\backslash
i,j}^{+}}\sum_{\mathbf{H}^{+}}\sum_{\tau_{i}^{+}}\sum_{\tau_{j}^{+}}\operatorname{Pr}(\bm{\tau}_{\backslash
i,j}^{+}|\bm{\tau}_{\backslash i,j},\\!\mathbf{H}_{\backslash
i,j},\\!\mathbf{a}^{\prime}_{\backslash
i,j})\\!\operatorname{Pr}(\mathbf{H}^{+})\\!\operatorname{Pr}(\tau_{i}^{+}|\tau_{i},\\!\mathbf{h}_{i},\\!a^{\prime}_{i})\\!\operatorname{Pr}(\tau_{j}^{+}|\tau_{j},\\!\mathbf{h}_{j},\\!a^{\prime}_{j})V^{*}(\mathbf{s}^{+}).$
(50)

Based on $a^{*}_{\backslash i,j}=a^{\prime}_{\backslash i,j}$, we have

$\operatorname{Pr}(\bm{\tau}_{\backslash i,j}^{+}|\bm{\tau}_{\backslash
i,j},\mathbf{H}_{\backslash i,j},\mathbf{a}^{*}_{\backslash
i,j})=\operatorname{Pr}(\bm{\tau}_{\backslash i,j}^{+}|\bm{\tau}_{\backslash
i,j},\mathbf{H}_{\backslash i,j},\mathbf{a}^{\prime}_{\backslash i,j}).$ (51)

Thus, from (50), the following inequality can be derived

$\displaystyle\\!\\!\sum_{\tau_{i}^{+}}\\!\sum_{\tau_{j}^{+}}\operatorname{Pr}\\!\left(\tau_{i}^{+}|\tau_{i},\\!\mathbf{h}_{i},\\!a^{*}_{i}\right)\\!\operatorname{Pr}\\!\left(\tau_{j}^{+}|\tau_{j},\\!\mathbf{h}_{j},\\!a^{*}_{j}\right)\\!\\!V^{*}\\!\\!\left(\mathbf{s}^{+}\right)\\!\geq\\!\sum_{\tau_{i}^{+}}\\!\sum_{\tau_{j}^{+}}\operatorname{Pr}\\!\left(\tau_{i}^{+}|\tau_{i},\\!\mathbf{h}_{i},\\!a^{\prime}_{i}\right)\\!\operatorname{Pr}\\!\left(\tau_{j}^{+}|\tau_{j},\\!\mathbf{h}_{j},\\!a^{\prime}_{j}\right)\\!\\!V^{*}\\!\\!\left(\mathbf{s}^{+}\right).\\!\\!$
(52)

For notation simplicity, the state can be rewritten as
$\mathbf{s}=(\tau_{i},\tau_{j})$, because the states except for $\tau_{i}$ and
$\tau_{j}$ are constant. Based on $a^{*}_{i}=m,a^{*}_{j}=0,a^{\prime}_{i}=0,$
and $a^{\prime}_{j}=m$, the left-hand side and the right hand side of (50) are
equal to

$\displaystyle\begin{cases}p_{i,m}\\!V^{*}(1,\\!\tau_{j}\\!+\\!\\!1)\\!+\\!(1\\!\\!-\\!p_{i,m})V^{*}(\tau_{i}\\!+\\!\\!1,\\!\tau_{j}\\!+\\!\\!1)\\\
p_{j,m}\\!V^{*}(\tau_{i}\\!+\\!\\!1,\\!1)\\!+\\!(1\\!\\!-\\!p_{j,m})V^{*}(\tau_{i}\\!+\\!\\!1,\\!\tau_{j}\\!+\\!\\!1).\end{cases}$
(53)

Then, the following inequality can be derived

$\displaystyle p_{i,m}V^{*}(1,\tau_{j}+1)$ $\displaystyle\\!\geq
p_{j,m}V^{*}(\tau_{i}+1,1)+(p_{i,m}-p_{j,m})V^{*}(\tau_{i}+1,\tau_{j}+1)$ (54)
$\displaystyle\\!\geq
p_{j,m}V^{*}(\tau^{\prime}_{i}+1,1)+(p_{i,m}-p_{j,m})V^{*}(\tau^{\prime}_{i}+1,\tau_{j}+1),$
(55)

where the first inequality is derived by (50), (51), and (53), and the second
inequality is by using Lemma 2 and $p_{i,m}\geq p_{j,m}$. The inequality (55)
can be rewritten as

$\displaystyle
p_{i,m}V^{*}(1,\\!\tau_{j}\\!+\\!\\!1)\\!+\\!(1\\!-\\!p_{i,m})V^{*}(\tau^{\prime}_{i}\\!+\\!\\!1,\\!\tau_{j}\\!+\\!\\!1)\\!\geq\\!p_{j,m}V^{*}(\tau^{\prime}_{i}\\!+\\!\\!1,\\!1)\\!+\\!(1\\!-\\!p_{j,m})V^{*}(\tau^{\prime}_{i}\\!+\\!\\!1,\\!\tau_{j}\\!+\\!\\!1).$
(56)

According to the analysis from (50) to (53), it directly follows
$Q(\mathbf{s}^{\prime},\mathbf{a}^{*})\geq
Q(\mathbf{s}^{\prime},\mathbf{a}^{\prime})$ from (56). ∎

######  Remark 2 (Generality of the derived results).

We note that all the theoretical results proved in this section merely rely on
two features of the formulated optimal scheduling problem: 1) the reward
function of each user is a monotonically increasing function in terms of its
AoI state, and 2) the total reward function of the problem is the sum of
individual rewards. In other words, for other scheduling problems of different
systems, if the two features are satisfied, the structural properties still
hold. For example, if a scheduling problem is for minimizing the overall
expected sum AoI (i.e., the instantaneous reward is
$r(\mathbf{s}_{t})=\sum_{n=1}^{N}-\tau_{n,t}$), not the sum estimation MSE,
then the optimal policy does have the same structural properties.

######  Remark 3 (Counterexample).

We can show that if the considered optimal scheduling problem of a multi-
sensor remote estimation system has a reward function as the negative product
of the individual estimation MSE, i.e.,
$r(\mathbf{s})=-\prod_{i=1}^{N}\operatorname{Tr}(\mathbf{P}_{i,t})$, which
does not satisfy the second feature in Remark 2, then the threshold structure
may not exist. Fig 3 illustrates the optimal scheduling policy of a two-
sensor-single-channel remote estimation system with the constructed reward
function. We see that the optimal policy is not a threshold policy as in
Theorem 2.

Figure 3: The optimal policy of a two-sensor-single-channel scheduling problem
with the multiplicative reward function, where $\bullet$ and $\times$
represent the schedule of sensor 1 and 2, respectively.

##  V Structure-Enhanced DRL

In the literature, DQN and DDPG are the most commonly adopted off-policy DRL
algorithms for solving optimal scheduling problems (see [11, 15] and
references therein), and they provide significant performance improvements
over heuristic policies. Next, we develop threshold structure-enhanced (SE)
DQN and DDPG for solving Problem 1 based on the structural properties in
Definitions 1 and 2. The performance improvement of SE algorithms will be
presented in Section VI.

###  V-A Structure-Enhanced DQN

Based on (24) and (26), we have the Bellman equation in terms of the Q-values
of the optimal policy:

$Q(\mathbf{s}_{t},\mathbf{a}_{t})=r(\mathbf{s}_{t})+\mathbb{E}_{\mathbf{s}_{t+1}}\left[\gamma\max_{\mathbf{a}_{t+1}}Q\left(\mathbf{s}_{t+1},\mathbf{a}_{t+1}\right)\right].$
(57)

A well-trained DQN uses a neural network (NN) with the parameter set
$\bm{\theta}$ to approximate $Q(\mathbf{s}_{t},\mathbf{a}_{t})$ by
$Q(\mathbf{s}_{t},\mathbf{a}_{t};\bm{\theta})$ and use it to find the optimal
action, i.e.,
$\mathbf{a}^{*}_{t}=\operatorname{argmax}_{\mathbf{a}_{t}\in\mathcal{A}}Q(\mathbf{s}_{t},\mathbf{a}_{t};\bm{\theta})$.
Considering the action space defined in Section III-A, the DQN has $N!/(N-M)!$
Q-value outputs of different state-action pairs. To train the DQN, one needs
to sample data (consisting of states, actions, rewards, and next states),
define a loss function of $\bm{\theta}$ based on the collected data, and
minimize the loss function to find the optimized $\bm{\theta}$. However, the
conventional DQN training method has never utilized structures of optimal
policies before.

To utilize the knowledge of the threshold policy structure for enhancing the
DQN training performance, we propose 1) an SE action selection method based on
Definitions 1 and 2 to select reasonable actions and hence enhance the data
sampling efficiency; and 2) an SE loss function definition to add the penalty
to sampled actions that do not follow the threshold structure.

Our SE-DQN training algorithm has three stages: 1) the DQN with loose SE
action selection stage, which only utilizes part of the structural property,
2) the DQN with tight SE action selection stage utilizes the full structural
property, and 3) the conventional DQN stage. The first two stages use the SE
action selection schemes and the SE loss function to train the DQN fast,
resulting in a reasonable threshold policy, and the last stage is for further
policy exploration. In what follows, we present the loose and tight SE action
selection schemes and the SE loss function.

####  V-A1 Loose SE action selection

We randomly select an action $\mathbf{a}^{\epsilon}$ from the entire action
space with a probability of $\epsilon$ for action exploration; with a
probability of $(1-\epsilon)$, we generate the SE action $\hat{\mathbf{a}}$ as
below. For simplicity, we drop the time index when describing action
selections.

The threshold structure suggests that the actions of $\mathbf{s}$ and the
state with a smaller AoI or channel state are correlated. Thus, one can infer
the action based on the action at the state with a smaller channel, or AoI
state, based on the channel-state and the AoI-state threshold properties in
Definitions 1 and 2, respectively. We only consider the AoI-state threshold
property for loose SE action selection, as it is difficult to find actions
that satisfy both structural properties at the beginning of training. We will
utilize both of them in the tight SE action selection stage.

Given the state $\mathbf{s}=(\bm{\tau},\mathbf{H})$, we define the state with
a smaller sensor $n$’s AoI as
$\dot{\mathbf{s}}^{(n)}=(\dot{\bm{\tau}}^{(n)},\mathbf{H})$, where

$\dot{\bm{\tau}}^{(n)}=(\tau_{1},\dots,\tau_{n}-1,\dots,\tau_{N}).$ (58)

For each $n$, we calculate the corresponding action based on the Q-values as

$\displaystyle\dot{\mathbf{a}}^{(n)}\triangleq(\dot{a}^{(n)}_{1},\dots,\dot{a}^{(n)}_{n},\dots,\dot{a}^{(n)}_{N})=\mathop{\arg\max}_{\dot{\mathbf{a}}}Q(\dot{\mathbf{s}}^{(n)},\dot{\mathbf{a}};\bm{\theta}).\
$ (59)

Recall that $\dot{a}^{(n)}_{n}\in\\{0,1,\dots,M\\}$ is the channel index
assigned to sensor $n$ at the state $\dot{\mathbf{s}}^{(n)}$.

If $\dot{a}^{(n)}_{n}>0$, then the AoI-state threshold property implies that
channel $\dot{a}^{(n)}_{n}$ or a better channel is assigned to sensor $n$ at
the state $\mathbf{s}$. We define the set of channels with better quality as

$\mathcal{M}^{(n)}\triangleq\\{m^{\prime}|h_{n,m^{\prime}}>h_{n,\dot{a}^{(n)}_{n}},m^{\prime}=1,\dots,M\\}.$
(60)

Then, the SE action for sensor $n$, say $\hat{a}_{n}$, is randomly chosen from
the set $\mathcal{M}^{(n)}$ with probability $\xi$, and is equal to
$\dot{a}^{(n)}_{n}$ with probability $1-\xi$.

If $\dot{a}^{(n)}_{n}=0$, then the AoI-state threshold property cannot help
with determining the action. Then, we define the action selected by the greedy
policy (i.e., the conventional DQN method) at the state $\mathbf{s}$ as

$\tilde{\mathbf{a}}\triangleq(\tilde{a}_{1},\tilde{a}_{2},\dots,\tilde{a}_{N})=\mathop{\arg\max}_{\mathbf{a}}Q(\mathbf{s},\mathbf{a};\bm{\theta}).$
(61)

Thus, we set the SE action of sensor $n$ identical to the one generated by the
conventional DQN method, i.e., $\hat{a}_{n}=\tilde{a}_{n}$.

Now we can define the SE action for $N$ sensors as
$\hat{\mathbf{a}}=(\hat{a}_{1},\hat{a}_{2},\dots,\hat{a}_{N})$. If such an
action meets the constraint

$\displaystyle\sum_{m=1}^{M}\bm{\mathbbm{1}}\left(\hat{a}_{n}=m\right)\leq
1,\quad\sum_{n=1}^{N}\bm{\mathbbm{1}}\left(\hat{a}_{n}=m\right)\leq 1,$ (62)

which is less restrictive than (6), we select the action $\mathbf{a}$ as
$\hat{\mathbf{a}}$ and assign the unused channels randomly to unscheduled
sensors; otherwise, $\mathbf{a}$ is identical to that of the conventional
method as $\tilde{\mathbf{a}}$.

####  V-A2 Tight SE action selection

By using the loose SE action selection, we first infer the scheduling action
of sensor $n$ at the state $\mathbf{s}$ based on the action of the state with
a smaller AoI, $\dot{\mathbf{s}}^{(n)}$. Then, we check whether the loose SE
action satisfies the channel-state threshold property as below.

For notation simplicity, we use $m>0$ to denote the SE channel selection for
sensor $n$. Given the state $\mathbf{s}$, we define the state with a smaller
channel $m$’s state for sensor $n$ as
$\ddot{\mathbf{s}}^{(n,m)}=(\bm{\tau},\ddot{\mathbf{H}}^{(n,m)})$, where
$\ddot{\mathbf{H}}^{(n,m)}$ and $\mathbf{H}$ are identical except the element
$\ddot{h}^{(n,m)}_{n,m}=h_{n,m}-1$. Then, we calculate the corresponding
action

$\ddot{\mathbf{a}}^{(n,m)}\\!\\!\triangleq\\!(\ddot{a}^{(n,m)}_{1}\\!\\!\\!,\\!\dots,\\!\ddot{a}^{(n,m)}_{n}\\!\\!\\!,\dots,\ddot{a}^{(n,m)}_{N})\\!=\\!\mathop{\arg\max}_{\ddot{\mathbf{a}}}Q(\ddot{\mathbf{s}}^{(n,m)}\\!\\!\\!,\ddot{\mathbf{a}};\\!\bm{\theta}).$
(63)

From the channel-state and the AoI-state threshold properties, the scheduling
action $\ddot{a}^{(n,m)}_{n}$ should be identical to $m$. Thus, if
$\ddot{a}^{(n,m)}_{n}=m$, then the SE action for sensor $n$ is
$\hat{a}_{n}=m$; otherwise, $\hat{a}_{n}$ is identical to the conventional DQN
action. The SE action satisfying both the threshold properties is
$\hat{\mathbf{a}}=(\hat{a}_{1},\hat{a}_{2},\dots,\hat{a}_{N})$. If such an
action meets the constraint (6), then it is executed as
$\mathbf{a}=\hat{\mathbf{a}}$; otherwise, we select the greedy action
$\mathbf{a}=\tilde{\mathbf{a}}$.

####  V-A3 SE loss function

During the training, each transition
$(\mathbf{s}_{t},\mathbf{a}_{t},\hat{\mathbf{a}}_{t},\tilde{\mathbf{a}}_{t},r_{t},\mathbf{s}_{t+1})$
is stored in a replay memory, where $r_{t}\triangleq r(\mathbf{s}_{t})$
denotes the immediate reward. Different from the conventional DQN, we include
both the SE action $\hat{\mathbf{a}}$ and the greedy action
$\tilde{\mathbf{a}}$, in addition to the executed action $\mathbf{a}$.

Algorithm 1 SE-DQN for sensor scheduling in the remote estimation system

1:Initialize replay memory $\mathcal{D}$ to capacity $N$

2:Initialize policy network with random weights $\bm{\theta}$

3:Initialize target network with weights $\hat{\bm{\theta}}=\bm{\theta}$

4:for episode $=1,2,\dots,E_{1}$ do

5: Initialize state $\mathbf{s}_{0}$

6: for $t=1,2,\dots,T$ do

7: Generate $\hat{\mathbf{a}}_{t}$ and select action $\mathbf{a}_{t}$ by the
loose SE action selection method of SE-DQN

8: Execute action $\mathbf{a}_{t}$ and observe $r_{t}$ and $\mathbf{s}_{t+1}$

9: Compute action
$\tilde{\mathbf{a}}_{t}=\mathop{\arg\max}_{\mathbf{a}}Q(\mathbf{s}_{t},\mathbf{a};\bm{\theta})$

10: Store transition
$(\mathbf{s}_{t},\mathbf{a}_{t},\hat{\mathbf{a}}_{t},\tilde{\mathbf{a}}_{t},r_{t},\mathbf{s}_{t+1})$
in $\mathcal{D}$

11: Sample a random batch of transitions
$(\mathbf{s}_{i},\mathbf{a}_{i},\hat{\mathbf{a}}_{i},\tilde{\mathbf{a}}_{i},r_{i},\mathbf{s}_{i+1})$

12: Calculate $\mathsf{TD}_{i}$ and $\mathsf{AD}_{i}$ based on (64) and (65)

13: Update $\bm{\theta}$ according to equation (68)

14: Every $t^{\prime}$ steps set $\hat{\bm{\theta}}=\bm{\theta}_{t}$

15: end for

16:end for

17:for episode $=E_{1},\dots,E_{2}$ do

18: Repeat algorithm from line 5 to line 15 by adopting the tight SE action
selection method

19:end for

20:for episode $=E_{2},\dots,E$ do

21: Execute the DQN algorithm as in [11]

22:end for

Let
$\mathcal{T}_{i}\triangleq(\mathbf{s}_{i},\mathbf{a}_{i},\hat{\mathbf{a}}_{i},\tilde{\mathbf{a}}_{t},r_{i},\mathbf{s}_{i+1})$
denote the $i$th transition of a sampled batch from the replay memory. Same as
the conventional DQN, we define the temporal-difference (TD) error of
$\mathcal{T}_{i}$ as

$\mathsf{TD}_{i}\triangleq
y_{i}-Q(\mathbf{s}_{i},\mathbf{a}_{i};\bm{\theta}),$ (64)

where
$y_{i}=r_{i}+\gamma\max_{{\mathbf{a}}_{i+1}}Q(\mathbf{s}_{i+1},{\mathbf{a}}_{i+1};\bm{\theta})$
is the estimation of Q-value at next step. This is to measure the gap between
the left and right sides of the Bellman equation (57). A larger gap indicates
that the approximated Q-values are far from the optimal. Different from DQN,
we introduce the action-difference (AD) error as below to measure the
difference of Q-value between actions selected by the SE strategy and the
greedy strategy:

$\mathsf{AD}_{i}\triangleq
Q(\mathbf{s}_{i},\hat{\mathbf{a}}_{i};\bm{\theta})-Q(\mathbf{s}_{i},\tilde{\mathbf{a}}_{i};\bm{\theta}).$
(65)

Since the optimal policy has the threshold structure, the inferred action
$\hat{\mathbf{a}}$ should be identical to the optimal action
$\tilde{\mathbf{a}}$. Thus, a well-trained $\bm{\theta}$ should lead to a
small difference in (65).

Based on (64) and (65), we define the loss function of $\mathcal{T}_{i}$ as

$L_{i}(\bm{\theta})=\left\\{\begin{array}[]{l}\begin{aligned}
&\alpha_{1}\mathsf{TD}^{2}_{i}+(1-\alpha_{1})\mathsf{AD}^{2}_{i},\quad\text{if
$\mathbf{a}_{i}=\hat{\mathbf{a}}_{i}$}\\\
&\mathsf{TD}^{2}_{i},\qquad\qquad\qquad\qquad\
\;\text{otherwise},\end{aligned}\end{array}\right.$ (66)

where $\alpha_{1}$ is a hyperparameter to balance the importance of
$\mathsf{TD}_{i}$ and $\mathsf{AD}_{i}$. In other words, if the SE action is
executed, both the TD and AD errors are taken into account; otherwise, the
conventional TD-error-based loss function is adopted.

Given the batch size $B$, the overall loss function is

$L(\bm{\theta})=\frac{1}{B}\sum_{i=1}^{B}L_{i}(\bm{\theta}).$ (67)

To optimize $\bm{\theta}$, we adopt the well-known gradient descent method and
calculate the gradient as below

$\nabla_{\bm{\theta}}L(\bm{\theta})=\frac{1}{B}\sum_{i=1}^{B}\nabla_{\bm{\theta}}L_{i}(\bm{\theta}),$
(68)

where $\nabla_{\bm{\theta}}L_{i}(\bm{\theta})$ is given as

$\nabla_{\bm{\theta}}L_{i}(\bm{\theta})=\left\\{\begin{array}[]{l}\begin{aligned}
&\\!\\!\\!-2((1-\alpha_{1})\mathsf{AD}_{i}\nabla_{\bm{\theta}}\left(Q\left(\mathbf{s}_{i},\hat{\mathbf{a}}_{i};\bm{\theta})-Q(\mathbf{s}_{i},\tilde{\mathbf{a}}_{i};\bm{\theta}\right)\right)\\\
&\ \
+\alpha_{1}\mathsf{TD}_{i}\nabla_{\bm{\theta}}Q(\mathbf{s}_{i},\mathbf{a}_{i};\bm{\theta})),\quad\text{if
$\mathbf{a}_{i}=\hat{\mathbf{a}}_{i}$}\\\
&\\!\\!\\!-2(\mathsf{TD}_{i}\nabla_{\bm{\theta}}Q(\mathbf{s}_{i},\mathbf{a}_{i};\bm{\theta})),\qquad\;\,\text{otherwise}.\end{aligned}\end{array}\right.$
(69)

The details of the SE-DQN algorithm are given in Algorithm 1.

###  V-B Structure-Enhanced DDPG

Different from the DQN, which has one NN to estimate the Q-value, a DDPG agent
has two NNs [26], a critic NN with parameter $\bm{\theta}$ and an actor NN
with the parameter $\bm{\mu}$. In particular, the actor NN approximates the
optimal policy $\pi^{*}(\mathbf{s})$ by $\mu(\mathbf{s};\bm{\mu})$, while the
critic NN approximates the Q-value of the optimal policy
$Q(\mathbf{s},\mathbf{a})$ by $Q(\mathbf{s},\mathbf{a};\bm{\theta})$. In
general, the critic NN judges whether the generated action of the actor NN is
good or not, and the latter can be improved based on the former. The critic NN
is updated by minimizing the TD error similar to the DQN. The actor-critic
framework enables DDPG to solve MDPs with continuous and large action space,
which cannot be handled by the DQN.

To solve our scheduling problem with a discrete action space, we adopt an
action mapping scheme similar to the one adopted in [15]. We set the direct
output of the actor NN with $N$ continuous values, ranging from $-1$ to $1$,
corresponding to sensors $1$ to $N$, respectively. Recall that the DQN has
$N!/(N-M)!$ outputs. The $N$ values are sorted in descending order. The
sensors with the highest $M$ ranking are assigned to channels $1$ to $M$,
respectively. The corresponding ranking values are then linearly normalized to
$[-1,1]$ as the output of the final outputs of the actor NN, named as the
virtual action $\mathbf{v}$. It directly follows that the virtual action
$\mathbf{v}$ and the real scheduling action $\mathbf{a}$ can be mapped from
one to the other directly. Therefore, we use the virtual action $\mathbf{v}$,
instead of the real action $\mathbf{a}$, when presenting the SE-DDPG
algorithm.

Similar to the SE-DQN, the SE-DDPG has the loose SE-DDPG stage, the tight SE-
DDPG stage, and the conventional DDPG stage. The $i$th sampled transition is
denoted as

$\mathcal{T}_{i}\triangleq(\mathbf{s}_{i},\mathbf{v}_{i},\hat{\mathbf{v}}_{i},\tilde{\mathbf{v}}_{t},r_{i},\mathbf{s}_{i+1}).$
(70)

We present the SE action selection method and the SE loss function in the
sequel.

####  V-B1 SE action selection

The general action selection approach for the SE-DDPG is identical to that of
the SE-DQN, by simply converting $\mathbf{v}_{i}$,
$\mathbf{v}^{\epsilon}_{i}$, $\tilde{\mathbf{v}}_{i}$, and
$\hat{\mathbf{v}}_{i}$ to $\mathbf{a}_{i}$, $\mathbf{a}^{\epsilon}_{i}$,
$\tilde{\mathbf{a}}_{i}$, and $\hat{\mathbf{a}}_{i}$, respectively. Different
from DQN with $\epsilon$-greedy actions, the action generated by the DDPG
based on the current state is

$\tilde{\mathbf{v}}_{i}=\mu(\mathbf{s}_{i};\bm{\mu}),$ (71)

and the random action $\mathbf{v}^{\epsilon}_{i}$ was generated by adding
noise to the original continuous output of the actor NN.

####  V-B2 SE loss function

Different from the SE-DQN, the SE-DDPG needs different loss functions for
updating the critic NN and the actor NN. For the critic NN, we use the same
loss function as in (67), and thus the gradient for the critic NN update is
identical to (68). Note that for DDPG, the next virtual action
$\tilde{\mathbf{v}}_{i+1}$ is the direct output of the actor NN given the next
state $\mathbf{s}_{i+1}$, i.e.,
$\tilde{\mathbf{v}}_{i+1}=\mu(\mathbf{s}_{i+1};\bm{\mu})$. Thus, when
calculating the TD error (64), we have $y_{i}=r_{i}+\gamma
Q(\mathbf{s}_{i+1},{\mu}(\mathbf{s}_{i+1};\bm{\mu});\bm{\theta})$.

For the actor NN, we introduce the difference between actions selected by the
SE strategy $\hat{\mathbf{v}}_{i}$ and the actor NN $\tilde{\mathbf{v}}_{i}$,
when $\hat{\mathbf{v}}_{i}$ is executed, i.e.,
$\mathbf{v}_{i}=\hat{\mathbf{v}}_{i}$. If the SE action is not selected, then
the loss function is the Q-value given the state-action pair, which is
identical to the conventional DDPG. Given the hyperparameter $\alpha_{2}$, the
loss function for the transition $\mathcal{T}_{i}$ is defined as

$L_{i}(\bm{\mu})=\left\\{\begin{array}[]{l}\begin{aligned}
&\alpha_{2}Q(\mathbf{s}_{i},\tilde{\mathbf{v}}_{i};\bm{\theta})+(1-\alpha_{2})\left(\mathbf{v}_{i}-\tilde{\mathbf{v}}_{i}\right)^{2},\
\ \text{if $\mathbf{v}_{i}=\hat{\mathbf{v}}_{i}$}\\\
&Q(\mathbf{s}_{i},\tilde{\mathbf{v}}_{i};\bm{\theta}),\qquad\qquad\qquad\qquad\qquad\
\ \ \text{otherwise},\end{aligned}\end{array}\right.$ (72)

Algorithm 2 SE-DDPG for sensor scheduling in the remote estimation system

1:Initialize replay memory $\mathcal{D}$ to capacity $N$

2:Initialize actor network and critic network with random weights $\bm{\mu}$
and $\bm{\theta}$

3:Initialize target network and with weight $\hat{\bm{\mu}}=\bm{\mu}$,
$\hat{\bm{\theta}}=\bm{\theta}$

4:for episode $=1,2,\dots,E_{1}$ do

5: Initialize a random noise $\mathcal{N}$ for action exploration

6: Initialize state $\mathbf{s}_{0}$

7: for $t=1,2,\dots,T$ do

8: Generate $\hat{\mathbf{v}}_{t}$ and select action $\mathbf{v}_{t}$ by the
loose SE action selection method of SE-DDPG

9: Mapping virtual action $\mathbf{v}_{t}$ to real action $\mathbf{a}_{t}$

10: Execute action $\mathbf{a}_{t}$ and observe $r_{t}$ and $\mathbf{s}_{t+1}$

11: Compute action $\tilde{\mathbf{v}}_{t}=\mu(\mathbf{s}_{t};\bm{\mu})$

12: Store transition
$(\mathbf{s}_{t},\mathbf{v}_{t},\hat{\mathbf{v}}_{t},\tilde{\mathbf{v}}_{t},r_{t},\mathbf{s}_{t+1})$
in $\mathcal{D}$

13: Sample a random batch of transitions
$(\mathbf{s}_{i},\mathbf{v}_{i},\hat{\mathbf{v}}_{i},\tilde{\mathbf{v}}_{i},r_{i},\mathbf{s}_{i+1})$

14: Calculate $\mathsf{TD}_{i}$ and $\mathsf{AD}_{i}$ based on (64) and (65)
but with the virtual actions
$\mathbf{v}_{i},\hat{\mathbf{v}}_{i},\tilde{\mathbf{v}}_{i}$

15: Update $\bm{\theta}$ according to equation (68)

16: Update $\bm{\mu}$ according to equation (76)

17: Update the target network:  $\displaystyle\hat{\bm{\mu}}$
$\displaystyle\leftarrow\delta\bm{\mu}+(1-\delta)\hat{\bm{\mu}}$ (73)
$\displaystyle\hat{\bm{\theta}}$
$\displaystyle\leftarrow\delta\bm{\theta}+(1-\delta)\hat{\bm{\theta}}$ (74)

18: end for

19:end for

20:for episode $E_{1}=1,2,\dots,E_{2}$ do

21: Repeat algorithm from line 5 to line 18 by adopting the tight SE action
selection method

22:end for

23:for episode $E_{2}=1,2,\dots,E$ do

24: Execute the conventional DDPG algorithm as in [26]

25:end for

and hence the overall loss function given the sampled batch is

$L(\bm{\mu})=\frac{1}{B}\sum_{i=1}^{B}L_{i}(\bm{\mu}).$ (75)

By replacing (71) and (72) in (75) and applying the chain rule, we can derive
the gradient of the overall loss function in terms of $\bm{\mu}$ as

$\nabla_{\bm{\mu}}L(\bm{\mu})=\frac{1}{B}\sum_{i=1}^{B}\nabla_{\bm{\mu}}L_{i}(\bm{\mu}),$
(76)

where $\nabla_{\bm{\mu}}L_{i}(\bm{\mu})$ is given by:

$\nabla_{\bm{\mu}}L_{i}(\bm{\mu})=\left\\{\begin{array}[]{l}\begin{aligned}
&\alpha_{2}\nabla_{\tilde{\mathbf{v}}_{i}}Q(\mathbf{s}_{i},\tilde{\mathbf{v}}_{i};\bm{\theta})\nabla_{\bm{\mu}}\mu(\mathbf{s}_{i};\bm{\mu})-2(1-\alpha_{2})\\\
&\ \
\left(\mathbf{v}_{i}-\mu\left(\mathbf{s}_{i};\bm{\mu}\right)\right)\nabla_{\bm{\mu}}\mu(\mathbf{s}_{i};\bm{\mu}),\quad\text{if
$\mathbf{v}_{i}=\hat{\mathbf{v}}_{i}$}\\\
&\nabla_{\tilde{\mathbf{v}}_{i}}Q(\mathbf{s}_{i},\tilde{\mathbf{v}}_{i};\bm{\theta})\nabla_{\bm{\mu}}\mu(\mathbf{s}_{i};\bm{\mu}),\qquad\text{otherwise}.\end{aligned}\end{array}\right.$
(77)

The details of the proposed SE-DDPG algorithm are given in Algorithm 2.

##  VI Numerical Experiments

In this section, we evaluate and compare the performance of the proposed SE-
DQN and SE-DDPG with the benchmark DQN and DDPG.

###  VI-A Experiment Setups

TABLE I: Summary of Hyperparameters Hyperparameters of SE-DQN and SE-DDPG | Value
---|---
Initial values of $\epsilon$ and $\xi$ | 1
Decay rates of $\epsilon$ and $\xi$ | 0.999
Minimum $\epsilon$ and $\xi$ | 0.01
Mini-batch size, $B$ | 128
Experience replay memory size, $K$ | 20000
Discount factor, $\gamma$ | 0.95
Hyperparameters of SE-DQN |
Learning rate | 0.0001
Decay rate of learning rate | 0.001
Target network update frequency | 100
Weight of SE-DQN loss function, $\alpha_{1}$ | 0.5
Input dimension of network | $N+N\times M$
Output dimension of network | $N!/(N-M)!$
Hyperparameters of SE-DDPG |
Learning rate of actor network | 0.0001
Learning rate of critic network | 0.001
Decay rate of learning rate | 0.001
Soft parameter for target update, $\delta$ | 0.005
Weight of critic network loss function, $\alpha_{1}$ | 0.5
Weight of actor network loss function, $\alpha_{2}$ | 0.9
Input dimension of actor network | $N+N\times M$
Output dimension of actor network | $N$
Input dimension of critic network | $2N+N\times M$
Output dimension of critic network | $1$

Figure 4: Average sum MSE of all processes during training with $N=6,M=3$.

Figure 5: Average sum MSE of all processes during training with
$N\\!=10,M\\!=5$.

Our numerical experiments run on a computing platform with an Intel Core i5
9400F CPU @ 2.9 GHz with 16GB RAM and an NVIDIA RTX 2070 GPU. For the remote
estimation system, we set the dimensions of the process state and the
measurement as $l_{n}=2$ and $e_{n}=1$, respectively. The system matrices
$\\{\mathbf{A}_{n}\\}$ are randomly generated with the spectral radius within
the range of $(1,1.4)$. The entries of $\mathbf{C}_{n}$ are drawn uniformly
from the range $(0,1)$, $\mathbf{W}_{n}$ and $\mathbf{V}_{n}$ are identity
matrices. The fading channel state is quantized into $\bar{h}=5$ levels, and
the corresponding packet drop probabilities are $0.2,0.15,0.1,0.05,$ and
$0.01$. The distributions of the channel states of each sensor-channel pair
$(n,m)$, i.e., $q^{(n,m)}_{1},\dots,q^{(n,m)}_{\bar{h}}$ are generated
randomly.

During the training, we use the ADAM optimizer for calculating the gradient
and reset the environment for each episode with $T=500$ steps. The episode
numbers for the loose SE action, the tight SE action, and the conventional DQN
stages are 50, 100, and 150, respectively. The settings of the hyperparameters
for Algorithm 1 and Algorithm 2 are summarized in Table I.

###  VI-B Performance Comparison

Fig. 4 and Fig. 5 illustrate the average sum MSE of all processes during the
training achieved by the SE-DRL algorithms and the benchmarks under some
system settings. Fig. 4 shows that the SE-DQN saves about $50\%$ training
episodes for the convergence, and also decreases the average sum MSE for
$10\%$ than the conventional DQN. Fig. 5 shows that the SE-DDPG saves about
$30\%$ training episodes and reduces the average sum MSE by $10\%$, when
compared to the conventional DDPG. Also, we see that the conventional DQN and
DDPG stages (i.e. the last 150 episodes) in Fig 4 and 5 cannot improve much of
the training performance. This implies that the SE stages have found near
optimal policies.

TABLE II: Performance Comparison of the SE-DRL and the Benchmarks in terms of the Average Estimation MSE System Scale $(N,M)$ |  Param. setup | DQN | SE-DQN | DDPG | SE-DDPG
---|---|---|---|---|---
$(6,3)$ | 1 | 52.4121 | 47.6766 | 48.4075 | 47.0594
| 2 | 67.4247 | 49.8476 | 53.3675 | 44.7423
| 3 | 84.1721 | 59.9127 | 56.9504 | 55.2409
| 4 | 79.5902 | 65.1640 | 64.4313 | 58.5534
$(6,2)$ | 5 | 55.7092 | 50.5983 | 51.3488 | 47.1210
| 6 | $-$ | 80.2522 | 77.4124 | 72.4863
| 7 | $-$ | 78.7715 | 85.3182 | 75.8465
| 8 | $-$ | 58.6024 | 61.4121 | 57.8539
$(10,5)$ | 9 | $-$ | $-$ | 68.0247 | 62.4727
| 10 | $-$ | $-$ | 89.6290 | 78.4138
| 11 | $-$ | $-$ | 90.2812 | 81.1148
| 12 | $-$ | $-$ | $-$ | 147.2844
$(20,10)$ | 13 | $-$ | $-$ | 181.4135 | 159.4321
| 14 | $-$ | $-$ | 163.1257 | 142.1850
| 15 | $-$ | $-$ | 173.0940 | 144.8166
| 16 | $-$ | $-$ | 215.2231 | 160.2304

Figure 6: Average sum AoI of all processes during the training with $N=6,M=3$.

In Table II, we test the performance of well-trained SE-DRL algorithms for
different numbers of sensors and channels, and different settings of system
parameters, i.e., $\mathbf{A}_{n}$, $\mathbf{C}_{n}$, and
$q^{(n,m)}_{1},\dots,q^{(n,m)}_{\bar{h}}$, based on 10000-step simulations. We
see that for 6-sensor-3-channel systems, the SE-DQN reduces the average MSE by
$10\%$ to $25\%$ over DQN, while both DDPG and SE-DDPG achieve similar
performance as the SE-DQN. This suggests that the SE-DQN is almost optimal and
that the DDPG and the SE-DDPG cannot improve further. In 6-sensor-2-channel
systems, the DQN cannot converge in most experiments but the SE-DQN and SE-
DDPG can still perform better than DDPG. In 10-sensor-5-channel systems,
neither the DQN nor the SE-DQN can converge, and the SE-DDPG achieves a $10\%$
MSE reduction over the DDPG. In particular, the SE-DDPG is the only converged
algorithm in Experiment 12. In 20-sensor-10-channel systems, we see that the
SE-DDPG can reduce the average MSE by $15\%$ to $25\%$. Therefore, the
performance improvement of the SE-DDPG appears significant for large systems.

In addition, to demonstrate that the SE-DRL algorithms can also be applied to
other scenarios, we consider a multi-sensor scheduling problem for minimizing
the overall expected sum AoI as mentioned in Remark 3. In Fig 6, we see that
the SE-DQN can effectively reduce the average sum AoI by $10\%$ compared with
the DQN.

We also test the effectiveness of the channel-state threshold property and the
loose SE action selection stage in the SE-DRL algorithms. Fig. 8 illustrates
that without using the channel-threshold property in the SE-action selection
process, although the convergence speed is not affected much, such a training
method does not converge to a near-optimal policy and leads to a noticeably
higher estimation MSE than the original SE-DDPG. In Fig. 8, we see that if one
disables the loose SE-action selection stage, the training convergence time
doubles compared with the original SE-DDPG, though both converged algorithms
provide similar performance. Thus, both the channel-threshold-enabled action
selection and the loose action selection stage are critical to guarantee the
performance of the SE-DRL algorithms.

Figure 7: Training performance comparison between SE-DDPG with and without
using the channel-state threshold property, where $N\\!=10,M\\!=5$.

Figure 8: Training performance comparison between SE-DDPG with and without the
loose SE-action selection stage, where $N\\!=10,M\\!=5$.

##  VII Conclusion

In this paper, we have proved that the optimal scheduling policy of the remote
estimation system satisfies a number of threshold properties. Then, based on
these theoretical guidelines, we have developed the structure-enhanced deep
reinforcement learning (SE-DRL) algorithms for solving the optimal scheduling
problem. In particular, we have proposed a novel action selection method and a
new loss function to improve training efficiency. Our numerical results have
illustrated that SE-DRL algorithms can save training time by 50% and reduce
the estimation mean-square error (MSE) by 10% to 25%, when compared with
benchmark DRL algorithms. In addition, the results also show that SE-DRL can
effectively solve a range of optimal scheduling problems, not limited to
remote state estimation systems. For future work, we will investigate other
structural properties of optimal scheduling and resource allocation policies
for wireless communications and networked systems, and then use these
properties to develop tailored DRL algorithms.

##  Appendix A Proof of Lemma 2

Similar to the Q-value function, we define a W-function for the value
function,
$W(\mathbf{s},\mathbf{a},V^{\tilde{t}}):\mathcal{S}\times\mathcal{A}\times\mathcal{V}\to\mathbb{R}$

$W(\mathbf{s},\mathbf{a},V^{\tilde{t}})=r(\mathbf{s})+\gamma\sum_{\mathbf{s}^{+}}\operatorname{Pr}(\mathbf{s}^{+}|\mathbf{s},\mathbf{a})V^{\tilde{t}}(\mathbf{s}^{+}).$
(78)

According to Lemma 1, the converge of the optimal value function,
$V^{*}(\mathbf{s})$, is independent of the initial value function
$V^{0}(\mathbf{s})$. Therefore, given states
$\mathbf{s}=(\bm{\tau},\mathbf{H})$ and
$\mathbf{s}^{\prime}=(\bm{\tau}^{\prime}_{(i)},\mathbf{H})$, where
$\tau^{\prime}_{i}\geq\tau_{i}$, we can assume that $V^{0}(\mathbf{s})$ is
monotonic, i.e.

$V^{0}\left(\mathbf{s}^{\prime}\right)\leq V^{0}\left(\mathbf{s}\right).$ (79)

To prove Lemma 2 based on (79) and Lemma 1, it is sufficient to show that the
value function $V^{1}(\mathbf{s})$ is monotonic, i.e.

$V^{1}\left(\mathbf{s}^{\prime}\right)\leq V^{1}\left(\mathbf{s}\right),$ (80)

and then the monotonicity of the value function can be preserved by the
Bellman operator $\mathsf{B}[\cdot]$ from $V^{0}(\mathbf{s})$ to
$V^{*}(\mathbf{s})$. During the value iteration, we define the optimal action
and the optimal policy at $\tilde{t}$th iteration as

$\mathbf{a}^{\tilde{t}}\triangleq\pi^{\tilde{t}}(\mathbf{s})=r(\mathbf{s})+\gamma\mathop{\arg\max}_{\mathbf{a}\in\mathcal{A}}\left[\sum_{\mathbf{s}^{+}}\operatorname{Pr}(\mathbf{s}^{+}|\mathbf{s},\mathbf{a})V^{\tilde{t}-1}(\mathbf{s}^{+})\right].$
(81)

From (28) and (81), it directly follows the relationship between the value
function and the W-functions:

$V^{\tilde{t}+1}(\mathbf{s})=W(\mathbf{s},\mathbf{a}^{\tilde{t}},V^{\tilde{t}})\geq
W(\mathbf{s},\mathbf{a},V^{\tilde{t}}).$ (82)

To prove (80), we use (82) and the optimal action
$\mathbf{a}^{1}=\pi^{1}\left(\mathbf{s}^{\prime}\right)$ to derive the
following inequality,

$\displaystyle
V^{1}\left(\mathbf{s}^{\prime}\right)-V^{1}\left(\mathbf{s}\right)\leq
W(\mathbf{s}^{\prime},\mathbf{a}^{1},V^{0})-W(\mathbf{s},\mathbf{a}^{1},V^{0}).$
(83)

By using (17) and (31), (83) can be derived that

$\displaystyle
W(\mathbf{s}^{\prime},\mathbf{a}^{1},V^{0})-W(\mathbf{s},\mathbf{a}^{1},V^{0})$
(84)
$\displaystyle=\left[r\left(\bm{\tau}^{\prime}\right)-r\left(\bm{\tau}\right)\right]+\gamma\Bigg{[}\sum_{\mathbf{H}^{+}}\sum_{{\bm{\tau}_{\backslash
i}}^{+}}\sum_{{\tau_{i}^{\prime}}^{+}}\operatorname{Pr}(\mathbf{H}^{+})\operatorname{Pr}({\bm{\tau}_{\backslash
i}}^{+}|\bm{\tau}_{\backslash i},\mathbf{H}_{\backslash
i},\mathbf{a}^{1}_{\backslash
i})\operatorname{Pr}({\tau^{\prime}_{i}}^{+}|{\tau^{\prime}_{i}},\mathbf{h}_{i},a^{1}_{i})V^{0}({\mathbf{s}^{\prime}}^{+})$
(85) $\displaystyle\quad-\sum_{\mathbf{H}^{+}}\sum_{{\bm{\tau}_{\backslash
i}}^{+}}\sum_{{\tau_{i}}^{+}}\operatorname{Pr}({\bm{\tau}_{\backslash
i}}^{+}|\bm{\tau}_{\backslash i},\mathbf{H}_{\backslash
i},\mathbf{a}^{1}_{\backslash
i})\operatorname{Pr}({\tau_{i}}^{+}|{\tau_{i}},\mathbf{h}_{i},a^{1}_{i})V^{0}(\mathbf{s}^{+})\Bigg{]},$
(86)

which implies that the states except for $\tau_{i}$ are constant. Therefore,
the states can be written as $\mathbf{s}=\tau_{i}$ and
$\mathbf{s}^{\prime}=\tau^{\prime}_{i}$ for notation simplicity. Then, using
(79) and
$\operatorname{Pr}({\tau^{\prime}_{i}}^{+}={\tau^{\prime}_{i}}+1|{\tau^{\prime}_{i}},\mathbf{h}_{i},a^{1}_{i})=\operatorname{Pr}({\tau_{i}}^{+}={\tau_{i}}+1|{\tau_{i}},\mathbf{h}_{i},a^{1}_{i})$,
we have

$\displaystyle\operatorname{Pr}({\tau^{\prime}_{i}}^{+}={\tau^{\prime}_{i}}+1|{\tau^{\prime}_{i}},\mathbf{h}_{i},a^{1}_{i})V^{0}({\tau^{\prime}_{i}}+1)\leq\operatorname{Pr}({\tau_{i}}^{+}={\tau_{i}}+1|{\tau_{i}},\mathbf{h}_{i},a^{1}_{i})V^{0}({\tau_{i}}+1).$
(87)

Similarly, we use
$\operatorname{Pr}({\tau^{\prime}_{i}}^{+}=1|{\tau^{\prime}_{i}},\mathbf{h}_{i},a^{1}_{i})=\operatorname{Pr}({\tau_{i}}^{+}=1|{\tau_{i}},\mathbf{h}_{i},a^{1}_{i})$
to derive that

$\displaystyle\operatorname{Pr}({\tau^{\prime}_{i}}^{+}=1|{\tau^{\prime}_{i}},\mathbf{h}_{i},a^{1}_{i})V^{0}(1)=\operatorname{Pr}({\tau_{i}}^{+}=1|{\tau_{i}},\mathbf{h}_{i},a^{1}_{i})V^{0}(1).$
(88)

Based on (79), (87), (88), and
$r\left(\tau^{\prime}_{i}\right)<r\left(\tau_{i}\right)$, the following
inequality can be derived from (86)

$\displaystyle\\!\\!\\!\\!\left[r\left(\tau^{\prime}_{i}\right)-r\left(\tau_{i}\right)\right]+\gamma\bigg{[}\sum_{{\tau_{i}^{\prime}}^{+}}\operatorname{Pr}({\tau^{\prime}_{i}}^{+}|{\tau^{\prime}_{i}},\mathbf{h}_{i},a^{1}_{i})V^{0}({\tau^{\prime}_{i}}^{+})-\sum_{{\tau_{i}}^{+}}\operatorname{Pr}({\tau_{i}}^{+}|{\tau_{i}},\mathbf{h}_{i},a^{1}_{i})V^{0}({\tau_{i}}^{+})\bigg{]}\leq
0.$ (89)

From (83), (86), and (89), we have $V^{1}\left(\mathbf{s}^{\prime}\right)\leq
V^{1}\left(\mathbf{s}\right)$.

Thus, the monotonicity of the value function $V^{0}(\mathbf{s})$ propagates
through the Bellman operator $\mathsf{B}[\cdot]$ to the optimal value function
$V^{*}(\mathbf{s})$.

##  Appendix B Proof of Lemma 3

In this proof, we also need the submodularity of the value function.
Therefore, similar to the proof of Lemma 2, we assume that the initial value
function $V^{0}(\mathbf{s})$ is submodular and probabilistic supermodular.
Thus, given states $\mathbf{s}=(\bm{\tau},\mathbf{H})$ and
$\mathbf{s}^{\circ}=(\bm{\tau}^{\circ},\mathbf{H})$ where
$\bm{\tau}^{\circ}=(\tau^{\prime\prime}_{i},\tau^{\prime}_{j})$ with
$\tau^{\prime\prime}_{i}\leq\tau_{i}$ and $\tau^{\prime}_{j}\geq\tau_{j}$, we
obtain that

$\displaystyle
V^{0}\left(\mathbf{s}\vee\mathbf{s}^{\circ}\right)+V^{0}\left(\mathbf{s}\wedge\mathbf{s}^{\circ}\right)$
$\displaystyle\leq
V^{0}\left(\mathbf{s}\right)+V^{0}\left(\mathbf{s}^{\circ}\right),$ (90a)
$\displaystyle
p_{j,1}V^{0}\left(\mathbf{s}\wedge\mathbf{s}^{\circ}\right)+(p_{j,1}-p_{i,1})V^{0}\left(\mathbf{s}\vee\mathbf{s}^{\circ}\right)$
$\displaystyle\geq
p_{j,1}V^{0}\left(\mathbf{s}\right)+(p_{j,1}-p_{i,1})V^{0}\left(\mathbf{s}^{\circ}\right).$
(90b)

To prove Lemma 3 based on (90a), (90b) and Lemma 1, it is sufficient to show
that the value function $V^{1}(\mathbf{s})$ is submodular and probabilistic
supermodular, i.e.

$\displaystyle
V^{1}\left(\mathbf{s}\vee\mathbf{s}^{\circ}\right)+V^{1}\left(\mathbf{s}\wedge\mathbf{s}^{\circ}\right)$
$\displaystyle\leq
V^{1}\left(\mathbf{s}\right)+V^{1}\left(\mathbf{s}^{\circ}\right),$ (91a)
$\displaystyle
p_{j,1}V^{1}\left(\mathbf{s}\wedge\mathbf{s}^{\circ}\right)+(p_{j,1}-p_{i,1})V^{1}\left(\mathbf{s}\vee\mathbf{s}^{\circ}\right)$
$\displaystyle\geq
p_{j,1}V^{1}\left(\mathbf{s}\right)+(p_{j,1}-p_{i,1})V^{1}\left(\mathbf{s}^{\circ}\right),$
(91b)

and then these properties of the value function can be preserved by the
Bellman operator $\mathsf{B}[\cdot]$ from $V^{0}(\mathbf{s})$ to
$V^{*}(\mathbf{s})$.

Similar to the proof of Lemma 2, we write the states as $\mathbf{s}=\bm{\tau}$
and $\mathbf{s}^{\circ}=\bm{\tau}^{\circ}$, as the channel states are
constant. Then, we have
$\bm{\tau}\vee\bm{\tau}^{\circ}=(\tau_{i},\tau^{\prime}_{j})$ and
$\bm{\tau}\wedge\bm{\tau}^{\circ}=(\tau^{\prime\prime}_{i},\tau_{j})$. In
terms of the policy, since we only consider the system with a single channel
in this proof, we write the optimal policy as ${\pi^{\tilde{t}}}(\bm{\tau})=i$
to represent that sensor $i$ is scheduled for the state $\bm{\tau}$, i.e.
$a^{\tilde{t}}_{i}=1$.

In the following, we prove (91a) by cases (a) and (b), and (91b) by cases (a’)
and (b’) with different packet success rates.

  * (a)

If $p_{j,1}\leq p_{i,1}$, then there are four cases with different optimal
actions of the states:

(a.1)
${\pi^{1}}(\bm{\tau}\vee\bm{\tau}^{\circ})={\pi^{1}}(\bm{\tau}\wedge\bm{\tau}^{\circ})=i$,
(a.2)
${\pi^{1}}(\bm{\tau}\vee\bm{\tau}^{\circ})={\pi^{1}}(\bm{\tau}\wedge\bm{\tau}^{\circ})=j$,
(a.3) ${\pi^{1}}(\bm{\tau}\vee\bm{\tau}^{\circ})=i$ and
${\pi^{1}}(\bm{\tau}\wedge\bm{\tau}^{\circ})=j$, (a.4)
${\pi^{1}}(\bm{\tau}\vee\bm{\tau}^{\circ})=j$ and
${\pi^{1}}(\bm{\tau}\wedge\bm{\tau}^{\circ})=i$.

  * (a.1)

If
${\pi^{1}}(\bm{\tau}\vee\bm{\tau}^{\circ})={\pi^{1}}(\bm{\tau}\wedge\bm{\tau}^{\circ})=i$,
then based on (82), we have

$\displaystyle
V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})+V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-V^{1}(\bm{\tau})-V^{1}(\bm{\tau}^{\circ})$
(92) $\displaystyle\leq
W(\bm{\tau}\vee\bm{\tau}^{\circ},i,V^{0})+W(\bm{\tau}\wedge\bm{\tau}^{\circ},i,V^{0})-W(\bm{\tau},i,V^{0})-W(\bm{\tau}^{\circ},i,V^{0}).$
(93)

Using (78) and
$r(\bm{\tau}\vee\bm{\tau}^{\circ})+r(\bm{\tau}\wedge\bm{\tau}^{\circ})=r(\bm{\tau})+r(\bm{\tau}^{\circ})$,
(93) can be derived that

$\displaystyle\gamma
p_{i,1}\left[V^{0}(1,\tau^{\prime}_{j}+1)+V^{0}(1,\tau_{j}+1)-V^{0}(1,\tau_{j}+1)-V^{0}(1,\tau^{\prime}_{j}+1)\right]$
(94)
$\displaystyle+\gamma(1\\!-\\!p_{i,1})\big{[}V^{0}(\tau_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)\\!+\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\tau_{j}\\!+\\!1)\\!-\\!V^{0}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1)\\!-\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)\big{]}$
(95) $\displaystyle\leq 0,$ (96)

where the inequality is based on (90a). From (93) and (96), we can derive
(91a).

  * (a.2)

If
${\pi^{1}}(\bm{\tau}\vee\bm{\tau}^{\circ})={\pi^{1}}(\bm{\tau}\wedge\bm{\tau}^{\circ})=j$,
the proof is similar to the case (a.1) by showing
$W(\bm{\tau}\vee\bm{\tau}^{\circ},j,V^{0})+W(\bm{\tau}\wedge\bm{\tau}^{\circ},j,V^{0})-W(\bm{\tau},j,V^{0})-W(\bm{\tau}^{\circ},j,V^{0})\leq
0$.

  * (a.3)

If ${\pi^{1}}(\bm{\tau}\vee\bm{\tau}^{\circ})=i$ and
${\pi^{1}}(\bm{\tau}\wedge\bm{\tau}^{\circ})=j$, then

$\displaystyle
V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})+V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-V^{1}(\bm{\tau})-V^{1}(\bm{\tau}^{\circ})$
$\displaystyle\\!\\!\leq\\!W(\bm{\tau}\vee\bm{\tau}^{\circ},i,V^{0})+W(\bm{\tau}\wedge\bm{\tau}^{\circ},j,V^{0})-W(\bm{\tau},i,V^{0})-W(\bm{\tau}^{\circ},j,V^{0})$
$\displaystyle\\!\\!=\\!\gamma\big{[}p_{i,1}V^{0}(1,\tau^{\prime}_{j}\\!+\\!1)\\!+\\!(1\\!-\\!p_{i,1})V^{0}(\tau_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)\\!+\\!p_{j,1}V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,1)\\!+\\!(1\\!-\\!p_{j,1})V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\tau_{j}\\!+\\!1)$
$\displaystyle\quad\\!-\\!p_{i,1}V^{0}(1,\tau_{j}\\!+\\!1)\\!-\\!(1\\!-\\!p_{i,1})V^{0}(\tau_{i}\\!+\\!1,\\!\tau_{j}\\!+\\!1)\\!-\\!p_{j,1}V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,1)\\!-\\!(1\\!-\\!p_{j,1})V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\\!\tau^{\prime}_{j}\\!+\\!1)\big{]}$
$\displaystyle\\!\\!=\\!\gamma\big{[}p_{i,1}V^{0}(1,\\!\tau^{\prime}_{j}\\!+\\!\\!1)\\!+\\!(p_{i,1}\\!-\\!p_{j,1}\\!)V^{0}(\tau^{\prime\prime}_{i}\\!\\!+\\!\\!1,\\!\tau_{j}\\!+\\!\\!1)\\!-\\!p_{i,1}V^{0}(1,\\!\tau_{j}\\!+\\!\\!1)\\!-\\!(p_{i,1}\\!-\\!p_{j,1})V^{0}(\tau^{\prime\prime}_{i}\\!\\!+\\!\\!1,\\!\tau^{\prime}_{j}\\!+\\!\\!1)\big{]}$
$\displaystyle\quad+\gamma(1\\!-\\!p_{i,1})\big{[}V^{0}\big{(}\tau_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)\\!+\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\tau_{j}\\!+\\!1)\\!-\\!V^{0}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1)\\!-\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)\big{]}$
$\displaystyle\\!\leq\\!0,$

where the last inequality is based on (90a) and (90b).

  * (a.4)

If ${\pi^{1}}(\bm{\tau}\vee\bm{\tau}^{\circ})=j$ and
${\pi^{1}}(\bm{\tau}\wedge\bm{\tau}^{\circ})=i$, then

$\displaystyle
V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})+V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-V^{1}(\bm{\tau})-V^{1}(\bm{\tau}^{\circ})$
(97)
$\displaystyle\\!\leq\\!W(\bm{\tau}\vee\bm{\tau}^{\circ},j,V^{0})+W(\bm{\tau}\wedge\bm{\tau}^{\circ},i,V^{0})-W(\bm{\tau},i,V^{0})-W(\bm{\tau}^{\circ},j,V^{0})$
(98) $\displaystyle\\!=\\!\gamma
p_{j,1}[V^{0}(\tau_{i}\\!+\\!1,1)\\!-\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,1)]\\!+\\!\gamma(1\\!-\\!p_{j,1})[V^{0}(\tau_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)\\!-\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)]$
(99)
$\displaystyle\quad\\!+\\!\gamma(1-p_{i,1})[V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1)-V^{0}(\tau_{i}+1,\tau_{j}+1)]$
(100)
$\displaystyle\\!\leq\\!\gamma(1\\!-\\!p_{i,1})[V^{0}(\tau_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)\\!+\\!V^{0}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1)\\!-\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)\\!-\\!V^{0}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1)],$
(101)

where the last inequality is based on $p_{j,1}\leq
p_{i,1},V^{0}(\tau_{i}\\!+\\!1,1)\leq
V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,1)$ and
$V^{0}(\tau_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)\leq
V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)$ from the
proof of Lemma 2. From (90a) and (101), we have

$\displaystyle
V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})+V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-V^{1}(\bm{\tau})-V^{1}(\bm{\tau}^{\circ})\leq
0,$ (102)

which is exactly (91a).

  * (b)

If $p_{j,1}\geq p_{i,1}$, the proof is similar to the case (a).

Similarly, we prove (91b) by different cases with different packet success
rates.

  * (a’)

If $p_{j,1}\leq p_{i,1}$, then

$\displaystyle\\!\\!\\!\\!p_{j,1}V^{1}(\bm{\tau})+(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}^{\circ})-p_{j,1}V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})$
(103)
$\displaystyle\\!\\!\\!\\!\\!=\\!p_{j,1}\\!\left[V^{1}(\tau_{i}\\!+\\!\\!1,\tau_{j}\\!+\\!\\!1)\\!-\\!V^{1}(\tau^{\prime\prime}_{i}\\!+\\!\\!1,\tau_{j}\\!+\\!\\!1)\right]\\!+\\!(p_{i,1}\\!-\\!p_{j,1})\\!\left[V^{1}(\tau_{i}\\!+\\!\\!1,\tau^{\prime}_{j}\\!+\\!\\!1)\\!-\\!V^{1}(\tau^{\prime\prime}_{i}\\!+\\!\\!1,\tau^{\prime}_{j}\\!+\\!\\!1)\right],\\!\\!$
(104) $\displaystyle\\!\\!\\!\\!\\!\leq 0,$ (105)

where the last inequality is based on the proof of Lemma 2.

  * (b’)

If $p_{j,1}\geq p_{i,1}$, then there are four cases with different optimal
actions of the states:

(b’.1) ${\pi^{1}}(\bm{\tau})\\!=\\!{\pi^{1}}(\bm{\tau}^{\circ})\\!=\\!i$,
(b’.2) ${\pi^{1}}(\bm{\tau})\\!=\\!{\pi^{1}}(\bm{\tau}^{\circ})\\!=\\!j$,
(b’.3) ${\pi^{1}}(\bm{\tau})\\!=\\!i$ and
${\pi^{1}}(\bm{\tau}^{\circ})\\!=\\!j$, (b’.4) ${\pi^{1}}(\bm{\tau})\\!=\\!j$
and ${\pi^{1}}(\bm{\tau}^{\circ})\\!=\\!i$.

  * (b’.1)

If ${\pi^{1}}(\bm{\tau})={\pi^{1}}(\bm{\tau}^{\circ})=i$, then

$\displaystyle
p_{j,1}V^{1}(\bm{\tau})+(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}^{\circ})-p_{j,1}V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})$
(106)
$\displaystyle\\!\leq\\!p_{j,1}W(\bm{\tau},i,\\!V^{0})\\!+\\!(p_{j,1}\\!-\\!p_{i,1})W(\bm{\tau}^{\circ}\\!,i,\\!V^{0})\\!-\\!p_{j,1}W(\bm{\tau}\\!\wedge\\!\bm{\tau}^{\circ}\\!,i,\\!V^{0})\\!-\\!(p_{j,1}\\!-\\!p_{i,1})W(\bm{\tau}\\!\vee\\!\bm{\tau}^{\circ}\\!,i,\\!V^{0})\\!$
(107)
$\displaystyle\\!=\\!p_{i,1}\left[r(\tau_{i},\tau^{\prime}_{j})\\!-\\!r(\tau^{\prime\prime}_{i},\tau^{\prime}_{j})\right]\\!+\\!\gamma
p_{j,1}\left[p_{i,1}V^{0}(1,\tau_{j}\\!+\\!1)\\!+\\!(1-p_{i,1})V^{0}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1)\right]$
(108)
$\displaystyle\quad+\gamma(p_{j,1}-p_{i,1})\left[p_{i,1}V^{0}(1,\tau^{\prime}_{j}+1)+(1-p_{i,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1)\right]$
(109) $\displaystyle\quad-\gamma
p_{j,1}\left[p_{i,1}V^{0}(1,\tau_{j}+1)+(1-p_{i,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1)\right]$
(110)
$\displaystyle\quad-\gamma(p_{j,1}-p_{i,1})\left[p_{i,1}V^{0}(1,\tau^{\prime}_{j}+1)+(1-p_{i,1})V^{0}(\tau_{i}+1,\tau^{\prime}_{j}+1)\right].$
(111)

From (90b), we have

$\displaystyle\\!\\!\\!\\!\\!\\!p_{j,1}V^{0}(1,\tau_{j}\\!+\\!1)+(p_{j,1}-p_{i,1})V^{0}(1,\tau^{\prime}_{j}+1)-V^{0}(1,\tau_{j}+1)-p_{i,1}V^{0}(1,\tau^{\prime}_{j}+1)\leq
0$ (112)

and

$\displaystyle
p_{j,1}V^{0}(\tau_{i}+1,\tau_{j}+1)+(p_{j,1}-p_{i,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1)$
(113) $\displaystyle-
p_{j,1}V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1)-(p_{j,1}-p_{i,1})V^{0}(\tau_{i}+1,\tau^{\prime}_{j}+1)\leq
0.$ (114)

Based on $r(\tau_{i},\tau^{\prime}_{j})\leq
r(\tau^{\prime\prime}_{i},\tau^{\prime}_{j})$, (111), (112), and (113), it can
be derived that

$\displaystyle
V^{1}(\bm{\tau})+(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}^{\circ})-p_{j,1}V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})\leq
0,$ (115)

which is exactly (91b).

  * (b’.2)

If ${\pi^{1}}(\bm{\tau})={\pi^{1}}(\bm{\tau}^{\circ})=j$, the proof is similar
to the case (b’.1) by showing
$p_{j,1}W(\bm{\tau},j,V^{0})\\!+\\!(p_{j,1}\\!-\\!p_{i,1})W(\bm{\tau}^{\circ},j,V^{0})\\!-\\!p_{j,1}W(\bm{\tau}\\!\wedge\\!\bm{\tau}^{\circ},j,V^{0})\\!-\\!(p_{j,1}\\!-\\!p_{i,1})W(\bm{\tau}\\!\vee\\!\bm{\tau}^{\circ},j,V^{0})\leq
0$.

  * (b’.3)

If ${\pi^{1}}(\bm{\tau})=i$ and ${\pi^{1}}(\bm{\tau}^{\circ})=j$, then

$\displaystyle
p_{j,1}V^{1}(\bm{\tau})+(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}^{\circ})-p_{j,1}V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})$
(116)
$\displaystyle\\!\leq\\!p_{j,1}W(\bm{\tau},i,\\!V^{0})\\!+\\!(p_{j,1}\\!-\\!p_{i,1})W(\bm{\tau}^{\circ}\\!,j,\\!V^{0})\\!-\\!p_{j,1}W(\bm{\tau}\\!\wedge\\!\bm{\tau}^{\circ}\\!,i,\\!V^{0})\\!-\\!(p_{j,1}\\!-\\!p_{i,1})W(\bm{\tau}\\!\vee\\!\bm{\tau}^{\circ}\\!,j,\\!V^{0})$
(117) $\displaystyle\\!\leq\\!\\!\gamma
p_{j,1}\\!\\!\left[p_{j,1}\\!V^{0}(\tau^{\prime\prime}_{i}\\!\\!+\\!\\!1,\\!1)\\!+\\!(p_{j,1}\\!\\!-\\!p_{i,1})V^{0}(\tau_{i}\\!+\\!\\!1,\\!\tau^{\prime}_{j}\\!+\\!\\!1)\\!-\\!p_{j,1}\\!V^{0}(\tau_{i}\\!+\\!\\!1,\\!1)\\!-\\!(p_{j,1}\\!\\!-\\!p_{i,1})V^{0}(\tau^{\prime\prime}_{i}\\!\\!+\\!\\!1,\\!\tau^{\prime}_{j}\\!+\\!\\!1)\right]\\!\\!\\!$
(118)
$\displaystyle\quad-\gamma[(p_{j,1}-p_{i,1})V^{0}(\tau_{i}+1,\tau^{\prime}_{j}+1)-(p_{j,1}-p_{i,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1)]$
(119)
$\displaystyle\quad+\gamma[p_{j,1}V^{0}(\tau_{i}+1,\tau_{j}+1)-p_{j,1}V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1)]$
(120) $\displaystyle\quad-\gamma
p_{i,1}p_{j,1}\left[V^{0}(\tau^{\prime\prime}_{i}+1,1)+V^{0}(\tau_{i}+1,\tau_{j}+1)-V^{0}(\tau_{i}+1,1)-V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1)\right],$
(121)

where the inequality is based on $r(\tau_{i},\tau^{\prime}_{j})\leq
r(\tau^{\prime\prime}_{i},\tau^{\prime}_{j})$. Then, from (90b), we have

$\displaystyle
p_{j,1}V^{0}(\tau^{\prime\prime}_{i}\\!+\\!\\!1,\\!1)\\!+\\!(p_{j,1}\\!-\\!p_{i,1})V^{0}(\tau_{i}\\!+\\!\\!1,\\!\tau^{\prime}_{j}\\!+\\!\\!1)\\!\geq\\!p_{j,1}V^{0}(\tau_{i}\\!+\\!\\!1,\\!1)\\!+\\!(p_{j,1}\\!-\\!p_{i,1})V^{0}(\tau^{\prime\prime}_{i}\\!+\\!\\!1,\\!\tau^{\prime}_{j}\\!+\\!\\!1).\\!\\!$
(122)

From $p_{j}<1$ and (122), (121) is smaller than the following equation

$\displaystyle\gamma\left[p_{j,1}-p_{j,1}p_{i,1}\right]\left[V^{0}(\tau^{\prime\prime}_{i}+1,1)+V^{0}(\tau_{i}+1,\tau_{j}+1)-V^{0}(\tau_{i}+1,1)-V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1)\right]\\!\\!,$
(123)

which is smaller than 0 from (90a) and $p_{j,1}>p_{j,1}p_{i,1}$. Thus, based
on (121) and (123), it can be derived that

$\displaystyle
p_{j,1}V^{1}(\bm{\tau})+(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}^{\circ})-p_{j,1}V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})\leq
0,$ (124)

which is exactly (91b).

  * (b’.4)

If ${\pi^{1}}(\bm{\tau})=j$ and ${\pi^{1}}(\bm{\tau}^{\circ})=i$, then based
on the case (a’) and $p_{j,1}\geq p_{i,1}$, we have

$\displaystyle
p_{i,1}V^{1}(\bm{\tau})+(p_{i,1}-p_{j,1})V^{1}(\bm{\tau}^{\circ})\leq
p_{i,1}V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})+(p_{i,1}-p_{j,1})V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ}).$
(125)

In addition, as Theorem 2 is derived by the probabilistic supermodularity, the
optimal policy of $V^{1}(\mathbf{s})$ can also be proved to have the AoI-state
threshold property in terms of $\tau_{j}$ in this case. Thus, we obtain that
${\pi^{1}}(\bm{\tau}\vee\bm{\tau}^{\circ})=j$ from ${\pi^{1}}(\bm{\tau})=j$,
which implies that

$W\left(\left(\tau_{i},\tau^{\prime}_{j}\right),j,V^{0}\right)\geq
W\left(\left(\tau_{i},\tau^{\prime}_{j}\right),i,V^{0}\right),\vspace{-0.2cm}$
(126)

based on (82). Using (78), (126) is derived to

$\displaystyle
p_{j,1}V^{0}(\tau_{i}\\!+\\!1,1)\\!+\\!(1\\!-\\!p_{j,1})V^{0}(\tau_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1)\geq
p_{i,1}V^{0}(1,\tau^{\prime}_{j}\\!+\\!1)\\!+\\!(1\\!-\\!p_{i,1})V^{0}(\tau_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1),\\!\\!$
(127)

which is exactly

$\displaystyle
p_{j,1}V^{0}(\tau_{i}+1,1)+(p_{i,1}-p_{j,1})V^{0}(\tau_{i}+1,\tau^{\prime}_{j}+1)\geq
p_{i,1}V^{0}(1,\tau^{\prime}_{j}+1).$ (128)

Similarly, we derive the following inequality based on (78), (82) and
${\pi^{1}}(\bm{\tau}^{\circ})=i$,

$\displaystyle p_{i,1}V^{0}(1,\tau^{\prime}_{j}+1)\geq
p_{j,1}V^{0}(\tau^{\prime\prime}_{i}+1,1)+(p_{i,1}-p_{j,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1).$
(129)

Then, based on (128) and (129), we have

$\displaystyle
p_{j,1}V^{0}(\tau_{i}\\!+\\!\\!1,\\!1)\\!+\\!(p_{j,1}\\!-\\!p_{i,1})V^{0}(\tau^{\prime\prime}_{i}\\!+\\!\\!1,\tau^{\prime}_{j}\\!+\\!\\!1)\\!\geq\\!p_{j,1}V^{0}(\tau^{\prime\prime}_{i}\\!+\\!\\!1,\\!1)\\!+\\!(p_{j,1}\\!-\\!p_{i,1})V^{0}(\tau_{i}\\!+\\!\\!1,\tau^{\prime}_{j}\\!+\\!\\!1),\\!\\!$
(130)

which is opposite to the (90b). Therefore, this case cannot exist at the 1st
iteration. As the value function of the last iteration is probabilistic
supermodular, this case can also be proved to be non-existence by the same
method for all other iterations in the value iteration.

Thus, the submodularity and the probabilistic supermodularity of the value
function $V^{0}(\mathbf{s})$ propagates through the Bellman operator
$\mathsf{B}[\cdot]$ to the optimal value function $V^{*}(\mathbf{s})$.

##  Appendix C Proof of Lemma 4

Similar to the proof of Lemma 2, we assume that the initial value function
$V^{0}(\mathbf{s})$ has the following property given states
$\mathbf{s}=(\bm{\tau},\mathbf{H})$ and
$\mathbf{s}^{\prime}=(\bm{\tau}^{\prime}_{(i)},\mathbf{H})$ where
$\tau^{\prime}_{i}\gg\tau_{i}$,

$V^{0}\left(\mathbf{s}^{\prime}\right)\ll V^{0}\left(\mathbf{s}\right).$ (131)

To prove Lemma 4 based on (131) and Lemma 1, it is sufficient to show that the
value function $V^{1}(\mathbf{s})$ has the same property, i.e.

$V^{1}\left(\mathbf{s}^{\prime}\right)\ll V^{1}\left(\mathbf{s}\right).$ (132)

Similar to the proof of Lemma 3, we write the states as $\mathbf{s}=\bm{\tau}$
and $\mathbf{s}^{\prime}=\bm{\tau}^{\prime}_{(i)}$, and the action as
${\pi^{\tilde{t}}}(\mathbf{s})=i$ to represent $a^{\tilde{t}}_{i}=1$ for the
state $\mathbf{s}$. Moreover, we drop the constant AoI states in different
optimal value functions according to (86). For example, given states
$\bm{\tau}=(\tau_{1},\dots,\tau_{i},\dots,\tau_{N})$ and
$\bm{\tau}^{\prime}=(\tau_{1},\dots,\tau^{\prime}_{i},\dots,\tau_{N})$, we
write them as $\bm{\tau}=(\tau_{i})$ and
$\bm{\tau}^{\prime}=(\tau^{\prime}_{i})$. In the following, we prove (132) by
cases with different optimal actions of the states.

  * (a)

If ${\pi^{1}}\left(\bm{\tau}^{\prime}_{(i)}\right)=i$, then

$\displaystyle
V^{1}\left(\bm{\tau}^{\prime}\right)-V^{1}\left(\bm{\tau}\right)$ (133)
$\displaystyle\leq
W\left(\bm{\tau}^{\prime},i,V^{0}\right)-W\left(\bm{\tau},i,V^{0}\right)$
(134)
$\displaystyle=p_{i,1}\left[r(\tau^{\prime}_{i},\tau_{j})-r(\tau_{i},\tau_{j})\right]$
(135)
$\displaystyle\quad\\!+\\!\gamma\left[p_{i,1}V^{0}(1,\tau_{j}\\!+\\!\\!1)\\!+\\!(1\\!-\\!p_{i,1})V^{0}(\tau^{\prime}_{i}\\!+\\!\\!1,\tau_{j}\\!+\\!\\!1)\\!-\\!p_{i,1}V^{0}(1,\tau_{j}\\!+\\!\\!1)\\!-\\!(1\\!-\\!p_{i,1})V^{0}(\tau_{i}\\!+\\!\\!1,\tau_{j}\\!+\\!\\!1)\right]\\!\\!$
(136) $\displaystyle\ll 0,$ (137)

where the last inequality is base on $r(\tau^{\prime}_{i},\tau_{j})\ll
r(\tau_{i},\tau_{j})$ and (131).

  * (b)

If ${\pi^{1}}\left(\bm{\tau}^{\prime}_{(i)}\right)=j$, then the proof is
similar to the case (a) by showing
$W\left(\bm{\tau}^{\prime},j,V^{0}\right)-W\left(\bm{\tau},j,V^{0}\right)\ll
0$.

##  Appendix D Proof of Lemma 5

Similar to the proof of Lemma 2, we assume that the initial value function
$V^{0}(\mathbf{s})$ is probabilistic supermodular given states
$\mathbf{s}=(\bm{\tau},\mathbf{H})$ and
$\mathbf{s}^{\circ}=(\bm{\tau}^{\circ},\mathbf{H})$, where
$\bm{\tau}^{\circ}=(\tau^{\prime\prime}_{i},\tau^{\prime}_{j})$ with
$\tau^{\prime\prime}_{i}\ll\tau_{i}$ and $\tau^{\prime}_{j}\geq\tau_{j}$,

$\displaystyle
p_{j,1}V^{0}\left(\mathbf{s}\wedge\mathbf{s}^{\circ}\right)+(p_{j,1}-p_{i,1})V^{0}\left(\mathbf{s}\vee\mathbf{s}^{\circ}\right)\geq
p_{j,1}V^{0}\left(\mathbf{s}\right)+(p_{j,1}-p_{i,1})V^{0}\left(\mathbf{s}^{\circ}\right).$
(138)

To prove Lemma 5 based on (138) and Lemma 1, it is sufficient to show that the
value function $V^{1}(\mathbf{s})$ is probabilistic supermodular, i.e.

$p_{j,1}V^{1}\left(\mathbf{s}\wedge\mathbf{s}^{\circ}\right)+(p_{j,1}-p_{i,1})V^{1}\left(\mathbf{s}\vee\mathbf{s}^{\circ}\right)\geq
p_{j,1}V^{1}\left(\mathbf{s}\right)+(p_{j,1}-p_{i,1})V^{1}\left(\mathbf{s}^{\circ}\right).$
(139)

Similar to the proof of Lemma 4, we write the states as
$\mathbf{s}=\bm{\tau}=(\tau_{i},\tau_{j})$ and
$\mathbf{s}^{\circ}=\bm{\tau}^{\circ}=(\tau^{\prime\prime}_{i},\tau^{\prime}_{j})$,
and the action as ${\pi^{\tilde{t}}}(\mathbf{s})=i$ to represent
$a^{\tilde{t}}_{i}=1$, then
$\bm{\tau}\vee\bm{\tau}^{\circ}=(\tau_{i},\tau^{\prime}_{j})$ and
$\bm{\tau}\wedge\bm{\tau}^{\circ}=(\tau^{\prime\prime}_{i},\tau_{j})$. In the
following, we prove (139) by case (a) and (b) with different packet success
rates.

  * (a)

If $p_{j,1}\leq p_{i,1}$, then

$\displaystyle
p_{j,1}V^{1}(\bm{\tau})+(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}^{\circ})-p_{j,1}V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})$
(140)
$\displaystyle=p_{j,1}[V^{1}(\bm{\tau})-V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})]+(p_{i,1}-p_{j,1})[V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})-V^{1}(\bm{\tau}^{\circ})]$
(141) $\displaystyle\leq 0,$ (142)

where the last inequality is derived based on the proof of Lemma 2.

  * (b)

If $p_{j,1}\geq p_{i,1}$, then there are ten cases with different optimal
actions of the states.

(b.1) ${\pi^{1}}(\bm{\tau})={\pi^{1}}(\bm{\tau}^{\circ})=i$, (b.2)
${\pi^{1}}(\bm{\tau})={\pi^{1}}(\bm{\tau}^{\circ})=j$, (b.3)
${\pi^{1}}(\bm{\tau})=i$ and ${\pi^{1}}(\bm{\tau}^{\circ})=j$, (b.4)
${\pi^{1}}(\bm{\tau})=j$ and ${\pi^{1}}(\bm{\tau}^{\circ})=i$, (b.5)
${\pi^{1}}(\bm{\tau})={\pi^{1}}(\bm{\tau}^{\circ})=k,(k\neq i,j)$ (b.6)
${\pi^{1}}(\bm{\tau})=i$ and ${\pi^{1}}(\bm{\tau}^{\circ})=k$, (b.7)
${\pi^{1}}(\bm{\tau})=k$ and ${\pi^{1}}(\bm{\tau}^{\circ})=i$, (b.8)
${\pi^{1}}(\bm{\tau})=j$ and ${\pi^{1}}(\bm{\tau}^{\circ})=k$, (b.9)
${\pi^{1}}(\bm{\tau})=k$ and ${\pi^{1}}(\bm{\tau}^{\circ})=j$, (b.10)
${\pi^{1}}(\bm{\tau})=k_{1}$ and ${\pi^{1}}(\bm{\tau}^{\circ})=k_{2}$.

For the cases (b.1), (b.2), (b.3), and (b.4), the proof is the same as the
proof of Lemma 3, because the states, except for sensor $i$ and sensor $j$,
are constant in these cases. Therefore, in the sequel, we only prove the other
cases. In addition, for the cases with ${\pi^{1}}(\bm{\tau})=k$ or
${\pi^{1}}(\bm{\tau}^{\circ})=k$, the states are written as
$\bm{\tau}=(\tau_{i},\tau_{j},\tau_{k})$, as the AoI state $\tau_{k}$ is not
constant.

  * (b.5)

If ${\pi^{1}}(\bm{\tau})={\pi^{1}}(\bm{\tau}^{\circ})=k,(k\neq i,j)$, then

$\displaystyle
p_{j,1}V^{1}(\bm{\tau})+(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}^{\circ})-p_{j,1}V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})$
(143)
$\displaystyle\leq\\!p_{j,1}W(\bm{\tau}\\!,k,\\!V^{0})\\!+\\!(p_{j,1}\\!-\\!p_{i,1})W(\bm{\tau}^{\circ}\\!\\!,k,\\!V^{0})\\!-\\!p_{j,1}W(\bm{\tau}\\!\\!\wedge\\!\bm{\tau}^{\circ}\\!\\!,k,\\!V^{0})\\!-\\!(p_{j,1}\\!-\\!p_{i,1})W(\bm{\tau}\\!\vee\\!\bm{\tau}^{\circ}\\!\\!,k,\\!V^{0})\\!\\!$
(144) $\displaystyle\leq\gamma
p_{j,1}\\!\left[p_{k,1}V^{0}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1,1)\\!+\\!(1\\!-\\!p_{k,1})V^{0}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1,\tau_{k}\\!+\\!1)\right]$
(145)
$\displaystyle\quad+\gamma(p_{j,1}-p_{i,1})[p_{k,1}V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1,1)+(1-p_{k,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1,\tau_{k}+1)]$
(146) $\displaystyle\quad-\gamma
p_{j,1}[p_{k,1}V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1,1)+(1-p_{k,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1,\tau_{k}+1)]$
(147)
$\displaystyle\quad-\gamma(p_{j,1}-p_{i,1})[p_{k,1}V^{0}(\tau_{i}+1,\tau^{\prime}_{j}+1,1)+(1-p_{k,1})V^{0}(\tau_{i}+1,\tau^{\prime}_{j}+1,\tau_{k}+1)],$
(148)

where the second inequality is based on
$r(\bm{\tau}\\!\vee\\!\bm{\tau}^{\circ})<r(\bm{\tau})$. Using (138), it can be
derived that

$\displaystyle\gamma
p_{k,1}[p_{j,1}V^{0}(\tau_{i}+1,\tau_{j}+1,1)+(p_{j,1}-p_{i,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1,1)$
(149) $\displaystyle\quad-
p_{j,1}V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1,1)-(p_{j,1}-p_{i,1})V^{0}(\tau_{i}+1,\tau^{\prime}_{j}+1,1)]\leq
0$ (150)

and

$\displaystyle\gamma(1-p_{k,1})[p_{j,1}V^{0}(\tau_{i}+1,\tau_{j}+1,\tau_{k}+1)+(p_{j,1}-p_{i,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1,\tau_{k}+1)$
(151) $\displaystyle\quad-
p_{j,1}V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1,\tau_{k}+1)-(p_{j,1}-p_{i,1})V^{0}(\tau_{i}+1,\tau^{\prime}_{j}+1,\tau_{k}+1)]\leq
0.\vspace{-0.4cm}$ (152)

Based on (148), (150), and (152), we have

$\displaystyle
p_{j,1}V^{1}(\bm{\tau})+(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}^{\circ})-p_{j,1}V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})\leq
0,\vspace{-0.2cm}$ (153)

which is exactly (139).

  * (b.6)

If ${\pi^{1}}(\bm{\tau})=i$ and ${\pi^{1}}(\bm{\tau}^{\circ})=k$, then

$\displaystyle
p_{j,1}V^{1}(\bm{\tau})+(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}^{\circ})-p_{j,1}V^{1}(\bm{\tau}\wedge\bm{\tau}^{\circ})-(p_{j,1}-p_{i,1})V^{1}(\bm{\tau}\vee\bm{\tau}^{\circ})$
(154) $\displaystyle\leq
p_{j,1}W(\bm{\tau},i,\\!V^{0})\\!+\\!(p_{j,1}\\!-\\!p_{i,1})W(\bm{\tau}^{\circ}\\!\\!,k,\\!V^{0})\\!-\\!p_{j,1}W(\bm{\tau}\\!\wedge\\!\bm{\tau}^{\circ}\\!\\!,k,\\!V^{0})\\!-\\!(p_{j,1}\\!-\\!p_{i,1})W(\bm{\tau}\\!\vee\\!\bm{\tau}^{\circ}\\!\\!,i,\\!V^{0})\\!\\!$
(155) $\displaystyle\leq\gamma
p_{j,1}\\!\left[p_{i,1}V^{0}(1,\tau_{j}\\!+\\!1,\tau_{k}\\!+\\!1)\\!+\\!(1\\!-\\!p_{i,1})V^{0}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1,\tau_{k}\\!+\\!1)\right]$
(156)
$\displaystyle\quad+\gamma(p_{j,1}-p_{i,1})[p_{k,1}V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1,1)+(1-p_{k,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1,\tau_{k}+1)]$
(157) $\displaystyle\quad-\gamma
p_{j,1}[p_{k,1}V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1,1)+(1-p_{k,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1,\tau_{k}+1)]$
(158)
$\displaystyle\quad-\gamma(p_{j,1}-p_{i,1})[p_{i,1}V^{0}(1,\tau^{\prime}_{j}+1,\tau_{k}+1)+(1-p_{i,1})V^{0}(\tau_{i}+1,\tau^{\prime}_{j}+1,\tau_{k}+1)].$
(159)

Using Lemma 4 and $\tau_{i}\gg\tau^{\prime\prime}_{i}$, we have

$\displaystyle
V^{0}(\tau_{i}\\!+\\!1,\\!\tau_{j}\\!+\\!1,\\!\tau_{k}\\!+\\!1)\\!\ll\\!V^{0}(1,\\!\tau_{j}\\!+\\!1,\\!\tau_{k}\\!+\\!1)\\!-\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\\!\tau_{j}\\!+\\!1,\\!1)\\!-\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\\!\tau_{j}\\!+\\!1,\\!\tau_{k}\\!+\\!1)$
(160)

and

$\displaystyle
V^{0}(\tau_{i}\\!+\\!1,\\!\tau^{\prime}_{j}\\!+\\!1,\\!\tau_{k}\\!+\\!1)\\!\ll\\!V^{0}(1,\\!\tau^{\prime}_{j}\\!+\\!1,\\!\tau_{k}\\!+\\!1)\\!-\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\\!\tau^{\prime}_{j}\\!+\\!1,\\!1)\\!-\\!V^{0}(\tau^{\prime\prime}_{i}\\!+\\!1,\tau^{\prime}_{j}\\!+\\!1,\\!\tau_{k}\\!+\\!1).$
(161)

From (160), (161), $V(\mathbf{s})<0$, and $0<p_{i,1},p_{j,1}<1$, we can derive
that $V^{0}(\tau_{i}\\!+\\!1,\\!\tau_{j}\\!+\\!1,\\!\tau_{k}\\!+\\!1)$ and
$V^{0}(\tau_{i}\\!+\\!1,\\!\tau^{\prime}_{j}\\!+\\!1,\\!\tau_{k}\\!+\\!1)$ are
dominate elements in (159). Therefore, to prove (139) from (159), we only to
prove the following inequality

$\displaystyle(1\\!-\\!p_{i,1})[p_{j,1}V^{0}(\tau_{i}\\!+\\!1,\tau_{j}\\!+\\!1,\tau_{k}\\!+\\!1)+(p_{j,1}-p_{i,1})V^{0}(\tau^{\prime\prime}_{i}+1,\tau^{\prime}_{j}+1,\tau_{k}+1)$
(162) $\displaystyle\quad-
p_{i,1}V^{0}(\tau^{\prime\prime}_{i}+1,\tau_{j}+1,\tau_{k}+1)+(p_{j,1}-p_{i,1})V^{0}(\tau_{i}+1,\tau^{\prime}_{j}+1,\tau_{k}+1)]\leq
0,$ (163)

which can be derived from (138) directly.

For cases (b.7), (b.8), (b.9), and (b.10), the proof is similar to the case
(b.6)

Thus, the probabilistic supermodularity of the value function
$V^{0}(\mathbf{s})$ propagates through the Bellman operator
$\mathsf{B}[\cdot]$ to the optimal value function $V^{*}(\mathbf{s})$.

## References

  * [1] J. Chen, W. Liu, D. E. Quevedo, Y. Li, and B. Vucetic, “Structure-enhanced deep reinforcement learning for optimal transmission scheduling,” in _Proc. IEEE ICC_ , 2023. [Online]. Available: https://doi.org/10.48550/arXiv.2205.11861
  * [2] P. Park, S. Coleri Ergen, C. Fischione, C. Lu, and K. H. Johansson, “Wireless network design for control systems: A survey,” _IEEE Commun. Surv. Tutor._ , vol. 20, no. 2, pp. 978–1013, May 2018.
  * [3] K. Huang, W. Liu, Y. Li, B. Vucetic, and A. Savkin, “Optimal downlink-uplink scheduling of wireless networked control for industrial IoT,” _IEEE Internet Things J._ , vol. 7, no. 3, pp. 1756–1772, Mar. 2020.
  * [4] L. Schenato, B. Sinopoli, M. Franceschetti, K. Poolla, and S. S. Sastry, “Foundations of control and estimation over lossy networks,” _Proc. IEEE_ , vol. 95, no. 1, pp. 163–187, Mar. 2007.
  * [5] K. Gatsis, M. Pajic, A. Ribeiro, and G. J. Pappas, “Opportunistic control over shared wireless channels,” _IEEE Trans. Autom. Control_ , vol. 60, no. 12, pp. 3140–3155, Mar, 2015.
  * [6] D. Han, J. Wu, H. Zhang, and L. Shi, “Optimal sensor scheduling for multiple linear dynamical systems,” _Automatica_ , vol. 75, pp. 260–270, Jan, 2017\.
  * [7] S. Wu, X. Ren, S. Dey, and L. Shi, “Optimal scheduling of multiple sensors over shared channels with packet transmission constraint,” _Automatica_ , vol. 96, pp. 22–31, Oct. 2018.
  * [8] A. Forootani, R. Iervolino, M. Tipaldi, and S. Dey, “Transmission scheduling for multi-process multi-sensor remote estimation via approximate dynamic programming,” _Automatica_ , vol. 136, pp. 1–14, Feb, 2022. Art. no. 110061\.
  * [9] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [10] Z. Zhao, W. Liu, D. E. Quevedo, Y. Li, and B. Vucetic, “Deep learning for wireless networked systems: a joint estimation-control-scheduling approach,” _arXiv preprint_ , Oct, 2022. [Online]. Available: https://doi.org/10.48550/arXiv.2210.00673
  * [11] 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. 1–8, Mar. 2020. Art. no. 108759\.
  * [12] W. Liu, K. Huang, D. E. Quevedo, B. Vucetic, and Y. Li, “Deep reinforcement learning for wireless scheduling in distributed networked control,” _submitted to Automatica_ , 2021. [Online]. Available: https://doi.org/10.48550/arXiv.2109.12562
  * [13] B. Demirel, A. Ramaswamy, D. E. Quevedo, and H. Karl, “DeepCAS: A deep reinforcement learning algorithm for control-aware scheduling,” _IEEE Contr. Syst. Lett._ , vol. 2, no. 4, pp. 737–742, Oct. 2018.
  * [14] L. Yang, H. Rao, M. Lin, Y. Xu, and P. Shi, “Optimal sensor scheduling for remote state estimation with limited bandwidth: A deep reinforcement learning approach,” _Inf. Sci._ , vol. 588, pp. 279–292, Apr. 2022.
  * [15] G. Pang, W. Liu, Y. Li, and B. Vucetic, “DRL-based resource allocation in remote state estimation,” _accepted by IEEE Trans. Wirel. Commun._ , 2022\. [Online]. Available: https://doi.org/10.48550/arXiv.2205.12267
  * [16] Z. D. Guo and E. Brunskill, “Directed exploration for reinforcement learning,” _arXiv preprint_ , Jun 2019. [Online]. Available: https://doi.org/10.48550/arXiv.1906.07805
  * [17] 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, June, 2020.
  * [18] S. Wu, K. Ding, P. Cheng, and L. Shi, “Optimal scheduling of multiple sensors over lossy and bandwidth limited channels,” _IEEE Trans. Netw. Syst._ , vol. 7, no. 3, pp. 1188–1200, Jan. 2020.
  * [19] Y.-P. Hsu, E. Modiano, and L. Duan, “Age of information: Design and analysis of optimal scheduling algorithms,” in _Proc. IEEE Int. Symp. Inf. Theory_ , June. 2017, pp. 561–565.
  * [20] 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, June, 2022.
  * [21] W. Liu, D. E. Quevedo, K. H. Johansson, B. Vucetic, and Y. Li, “Stability conditions for remote state estimation of multiple systems over multiple markov fading channels,” _IEEE Trans. Autom. Control_ , early access, Aug. 2022.
  * [22] M. L. Puterman, _Markov decision processes: discrete stochastic dynamic programming_. John Wiley & Sons, 2014\.
  * [23] ——, “Markov decision processes,” _Handbooks in operations research and management science_ , vol. 2, pp. 331–434, 1990.
  * [24] O. Hernández-Lerma and J. B. Lasserre, _Further topics on discrete-time Markov control processes_. Berlin, Germany: Springer, 2012, vol. 42.
  * [25] D. M. Topkis, _Supermodularity and complementarity_. Princeton university press, 1998.
  * [26] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra, “Continuous control with deep reinforcement learning,” _arXiv preprint_ , Sep. 2015. [Online]. Available: https://doi.org/10.48550/arXiv.1509.02971