#  Goal-oriented Policies for Cost of Actuation Error Minimization in Wireless
Autonomous Systems

Emmanouil Fountoulakis, Nikolaos Pappas, and Marios Kountouris

###### Abstract

We consider the minimization of the cost of actuation error under resource
constraints for real-time tracking in wireless autonomous systems. A
transmitter monitors the state of a discrete random process and sends updates
to a receiver over an unreliable wireless channel. The receiver then takes
actions according to the estimated state of the source. For each discrepancy
between the real state of the source and the estimated one, we consider a
different cost of actuation error. This models the case where some states, and
consequently the corresponding actions to be taken, are more important than
others. We provide two algorithms, a first one reaching an optimal solution
but of high complexity, and a second low-complexity one that provides a
suboptimal solution. Our simulation results evince that the performance of the
two algorithms are quite close.

##  I Introduction

†† This work has been performed while E. Fountoulakis was with the
Communication Systems Department, EURECOM, France. He is now with Ericsson,
Sweden. Email<EMAIL_ADDRESS>N. Pappas is with the
Department of Computer and Information Science, Linköping University, Sweden.
Email<EMAIL_ADDRESS>M. Kountouris is with the Communication Systems
Department, EURECOM, France. Email<EMAIL_ADDRESS>The work of
E. Fountoulakis and M. Kountouris has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (Grant agreement No. 101003431). The work of N. Pappas
has been supported in part by the Swedish Research Council (VR), ELLIIT,
Zenith, and the European Union (ETHER, 101096526).

Emerging cyber-physical and real-time autonomous systems are envisioned to
introduce various applications and services, in which information distilled
from measurements or observations is valuable when it is fresh, accurate, and
useful to the specific goal of the data exchange. In this context, a relevant
yet challenging problem is that of remote real-time tracking and actuation
driven by sampled and potentially delayed measurements transmitted over a
wireless channel using limited resources.

Conventional communication system design has mainly remained agnostic to the
significance of transmitted messages, in particular at the physical and medium
access layers. The optimization of system performance has been dominated by
metrics such as throughput, delay, and packet drop rate. Although these
performance metrics have turned out to be instrumental for enabling reliable
and efficient communication, they fall short of differentiating the packets
according to their information content and its value. A recently developed
metric, named Age of Information (AoI), has been proposed to measure the
freshness and the timeliness of information [1, 2, 3]. However, baseline AoI-
based metrics do not take into account the source evolution and the
significance of the generated information with respect to the communication
task/goal and the context. Several variants of AoI have been proposed for
tackling the problem of remote estimation in status update systems [4, 5, 6,
7]. Nevertheless, the aforementioned works do not consider the cost of
actuation error, as they mainly focus on the discrepancy between the source
and the estimated value of the process at the destination. A recently proposed
approach, which is also adopted in this paper, takes into account the
semantics of the information, i.e., significance, goal-oriented usefulness,
and contextual importance of information as a means to leverage the synergy
between data generation and processing, information transmission, and signal
reconstruction [8, 9, 10, 11].

In this work, we consider the problem of real-time tracking and estimation of
an information source from a remote actuator. A transmitter samples and sends
information about the state of a source in the form of status update packets
to a remote actuator (receiver) over an unreliable wireless channel. The
actuator takes actions depending on the estimated state of the remote source.
We also consider that the transmitter has limited resources, which prevents it
from sampling and transmitting updates continuously. This paper extends the
results of [12, 13], where the problem of remote monitoring of a discrete
Markov source is considered and semantics-empowered policies are proposed to
significantly reduce both the real-time reconstruction and the cost of
actuation errors, as well as the amount of ineffective updates. Specifically,
we consider a more general discrete stochastic source process and resource
constraints, which make the solution essentially different. The problem is
formulated as a Constrained Markov Decision Process (CMDP), and two goal-
oriented semantic-aware policies are proposed. A key takeaway is that it is
optimal for the transmitter to remain silent even if there is a discrepancy
between the actual state of the source and its estimate at the receiver, due
to the delay induced by the wireless channel, the high transition probability,
and the large actuation error.

##  II System Model

We consider a time slotted communication system in which a transmitter
monitors a discrete random process and sends status updates to a receiver over
an error-prone wireless channel. Let $t\in\mathbb{Z}_{>0}$ denote the $t$-th
slot. The receiver operates as a remote actuator and performs actions
according to the estimated state of the source. The state of the process is
modeled by a Discrete-Time Markov Chain (DTMC) $\left\\{X_{t}\right\\}_{t\in
Z_{>0}}$, and is assumed to be ergodic. The state of the source takes values
from the set $\left\\{0,1,\ldots,N\right\\}$, where $N\in\mathbb{Z}_{>0}$.
Each state corresponds to a specific action that has to be performed by the
actuator.

The channel realization is denoted by $h_{t}$, and is equal to $1$ if a packet
is successfully received at time slot $t$ and $0$ otherwise. The success
probability is defined as $p_{s}=\Pr(h_{t}=1)$, and the failure probability as
$p_{f}=\Pr(h_{t}=0)=1-p_{s}$. For every successful transmission, the receiver
updates its information regarding the state of the source with a new estimate
denoted by $\hat{X}_{t}$. The receiver sends an acknowledgement (ACK)/negative
ACK for successful/failed transmissions. We assume that ACK/NACK information
is sent and received instantaneously and error free. If the receiver does not
successfully receive an update, it uses its previous estimate as the current
one, i.e., $\hat{X}_{t+1}=\hat{X}_{t}$. We consider that the sampling and
transmission processes take a time slot to be performed. Therefore, the
receiver receives an update from the transmitter with one slot delay, if a
transmission is successful at time slot $t$, and the actuator updates its
state at slot $t+1$.

The transmitter generates a status update $X_{t}$ by sampling the source at
will. The decision to sample and transmit at time slot $t$ is denoted by
$\alpha_{t}$, where

$\displaystyle\alpha_{t}=\begin{cases}1\text{, if the source is sampled and
its state transmitted,}\\\ 0\text{, otherwise.}\end{cases}$ (1)

###  II-A Performance metrics

We consider that the actuator (receiver) takes actions according to the
estimated state of the source. If the estimated state is different from the
real state of the source, an actuation error occurs depending on a pre-defined
function. The cost of actuation error captures the significance (semantics) of
the error at the point of actuation. Note that some errors may have a larger
or a more critical impact than others. Let $C_{i,j}$ denote the cost of being
in state $i$ at the source, and in state $j$, estimated at the receiver, at
time slot $t$, i.e., $X_{t}=i$ and $\hat{X}_{t}=j$. We assume that the costs
$C_{i,j}$ are given and remain the same over the time horizon. Furthermore,
for every sampling and transmission actions, we consider a cost $c$. This cost
can represent, for instance, the power consumption for both sampling and
transmission procedures.

##  III Problem Formulation

The objective of this work is to minimize the average total cost of actuation
error under average resource constraints. The expected time averages of the
transmission and actuation costs are defined as

$\displaystyle\bar{c}\triangleq\lim\limits_{T\rightarrow\infty}\frac{1}{T}\sum\limits_{t=1}^{T}\mathbb{E}\left\\{\alpha_{t}c\right\\}\text{,
}\bar{C}\triangleq\lim\limits_{T\rightarrow\infty}\frac{1}{T}\sum\limits_{t=1}^{T}\mathbb{E}\left\\{C_{i,j}^{t}\right\\}\text{,}$
(2)

respectively. To this end, we formulate our stochastic optimization problem as

$\displaystyle\min\limits_{\pi}\quad\bar{C}^{\pi}\text{,
s.~{}t.,}\quad\bar{c}^{\pi}\leq c_{\text{max}}\text{,}$ (3)

where $\pi$ is the policy that decides the rule of selecting the right value
$\alpha_{t}$ at every time slot $t$, and $c>0$ is the time-averaged cost
constraint. The problem in (3) is a CMDP. The system state is described by
tuple $S_{t}=(X_{t},\hat{X}_{t},C_{t})$, actions $\alpha_{t}\in\mathcal{A}$,
where $\mathcal{A}=\left\\{0,1\right\\}$, and the transition matrix is
described by $P_{i,j}=\Pr\left\\{X_{t+1}=j|X_{t}=i\right\\}$. We assume that
the transmitter has knowledge of the channel and source statistics.

##  IV Proposed Algorithms

In this section, we provide two optimization algorithms for solving problem
(3) optimally and suboptimally.

###  IV-A Optimal Solution

The problem in (3) is a CMDP, which is, in general, difficult to be solved
[14]. In order to solve the constrained problem, we relax the constraints in
(3) by utilizing Lagrangian multipliers. We show that this approach can
provide the optimal solution.

We define the Lagrangian function as

$\displaystyle\mathcal{L}(\pi,\lambda)=\lim\limits_{T\rightarrow\infty}\frac{1}{T}\sum\limits_{t=1}^{T}\mathbb{E}_{\pi}\left\\{C_{t}+\lambda\alpha_{t}c\right\\}-\lambda
c\text{,}$ (4)

where the immediate cost is $f(S_{t})=C_{t}+\lambda\alpha_{t}c\text{.}$ In
order to proceed with the solution in (3), we consider the following
optimization problem

$\displaystyle\min\limits_{\pi\in\Pi}\mathcal{L}(\pi,\lambda)\text{,}$ (5)

for any given $\lambda\geq 0$111For $\lambda=0$, one may expect that the
optimal policy is to always transmit because the sampling and the transmission
processes are costless. However, our simulation results show that this is not
always optimal even for cost-free transmissions.. Since $\lambda c$ is
independent of the chosen policy $\pi$, the problem in (5) is equivalent to
the following optimization problem

$\displaystyle\min\limits_{\pi\in\Pi}h(\lambda,\pi)=\min\limits_{\pi\in\Pi}\lim\sup\limits_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}^{\pi}\left(\sum\limits_{t=0}^{T-1}C_{t}+\lambda\alpha_{t}c\right)\text{.}$
(6)

A policy that achieves $\mathcal{L}^{*}(\lambda)$ is called $\lambda$-optimal,
denoted by $\pi_{\lambda}^{*}$, and is a solution to the following
optimization problem
$\min\limits_{\pi_{\lambda}}\mathcal{L}(\pi,\lambda)\text{.}$ Since the
dimension of the state space $\mathcal{S}$ is finite, the growth condition
[14, Eq. 11.21] is satisfied. In addition, the immediate cost function is
bounded below ($\geq 0$). Since these conditions are satisfied, the optimal
value of the CMDP problem in (3), $\bar{C}_{\pi}^{*}$, and the optimal value
of the (5), $\mathcal{L}^{*}(\lambda)$, ensure the following relation [14,
Corollary 12.2]

$\displaystyle\bar{C}_{\pi^{*}}=\sup\limits_{\lambda\geq
0}\mathcal{L}^{*}(\lambda)\text{.}$ (7)

######  Theorem 1 (Mixture of two randomized policies).

[15, Theorem 4.4] The optimal policy $\pi^{*}$ is a mixture of two
deterministic policies $\pi^{*}_{\lambda^{-}}$, $\pi^{*}_{\lambda^{+}}$.

The optimal policy is written symbolically as
$\pi^{*}=\eta\pi^{*}_{\lambda^{-}}+(1-\eta)\pi^{*}_{\lambda^{+}}\text{,}$
where $\eta$ is a probabilistic factor. We characterize $\eta$, $\lambda^{-}$,
and $\lambda^{+}$, later in this paper.

We now proceed to find the solution to the problem (5). To obtain the optimal
policy of an infinite horizon average cost Markov Decision Process (MDP), it
is sufficient to solve the following Bellman equation [16]

$\displaystyle\theta_{\lambda}+V(S_{t})=$
$\displaystyle\min\limits_{\alpha_{t}\in\mathcal{A}}\left\\{C_{a_{t}}+\lambda\alpha_{t}c+\sum\limits_{S_{t+1}\in\mathcal{S}}P_{S_{t},S_{t+1}}V(S_{t+1})\right\\}\text{,}$
(8)

where $\theta_{\lambda}$ is the optimal value of (6), for a given $\lambda>0$,
and $V(S_{t+1})$ is the cost-to-go or value function. This is known to be a
challenging problem [16]. We apply the value iteration algorithm and the
bisection method to solve the problem and to find the optimal Lagrange
multiplier, respectively. The detailed steps are provided in Algorithm $1$
222There is no closed form expression for $\eta$ [17], thus we numerically
search for $\eta\in\left[0,1\right]$..

1 Initialization: $\lambda\leftarrow 0$, $\lambda_{-}\leftarrow 0$,
$\lambda_{+}$ large positive number, and $\epsilon>0$

2 Run $\text{VI}(\lambda)$

3 if  _$\bar{c}\leq c_{\text{max}}$_ then

4 $\pi^{*}\leftarrow\pi^{*}_{\lambda}$

5else

6 while  _$|\lambda_{+}-\lambda_{-}| >\epsilon$_ do

7 Run $\text{VI}(\frac{\lambda_{+}-\lambda_{-}}{2})$

8 if  _$\bar{c}\geq c_{\text{max}}$_ then

9 $\lambda_{-}\leftarrow\lambda$

10 else

11 $\lambda_{+}\leftarrow\lambda$

12

13 $\lambda^{*}\leftarrow\frac{\lambda_{+}+\lambda_{-}}{2}$,
$\lambda^{*}_{+}\leftarrow\lambda_{-}$, $\lambda_{+}^{*}\leftarrow\lambda_{-}$

14 $\text{VI}(\lambda^{*})$

15 if  _$\bar{c}=c_{\text{max}}$_ then

16 $\pi^{*}=\pi^{*}_{\lambda}$

17 else

18 $\pi^{*}=\eta\pi_{\lambda^{*}_{-}}+(1-\eta)\pi_{\lambda^{*}_{+}}$

19

20

21

22function $\text{VI}(\lambda)$:

23 Initialization: $V^{0}=V^{1}=0$, $\forall s\in\mathcal{S}$, choose a small
$\epsilon>0$, set $n=1$

24 while  _$||V^{n}-V^{n-1}||\geq\epsilon(1-\gamma)/2\gamma$_ do

25 for  _each $s\in\mathcal{S}$ compute_ do

26

27
$V^{n}(s)=\min\limits_{\alpha_{t}}\left\\{C_{\alpha_{t}}+\lambda\alpha_{t}c+\gamma\sum\limits_{S_{t+1}\in\mathcal{S}}\Pr\left\\{S_{t+1}|S_{t},\alpha_{t}\right\\}V^{n-1}(S_{t+1})\right\\}$

28 $n\leftarrow n+1$

return policy $\pi$

Algorithm 1 Value Iteration Algorithm

###  IV-B Suboptimal low-complexity algorithm

Although the value iteration algorithm is proven to converge to the optimal
solution, it suffers from high computational complexity, known as the _curse
of dimensionality_ [18]. Our goal is to provide a low-complexity algorithm
that guarantees that the average cost constraints are satisfied and which
provides a solution close to the optimal one. Using tools from Lyapunov
optimization theory, we provide a real-time algorithm named Drift-Plus-Penalty
(DPP). We reformulate the problem in (3), and we define the objective function
$g(t)$ as

$\displaystyle g(t)=$
$\displaystyle\begin{cases}\left(\sum\limits_{k=i}^{N}C_{k,j}P_{i,k}(1-p_{s})+\sum\limits_{k=i}^{N}C_{k,i}P_{i,k}p_{s}\right)\text{,
if }\alpha_{t}=1\text{,}\vspace{3mm}\\\
\left(\sum\limits_{k=i}^{N}C_{k,j}\mathcal{P}_{i,k}\right)\text{,
otherwise.}\end{cases}$ (9)

The expected time average of the objective function is defined as
$\bar{g}\triangleq\lim\sup\limits_{T\rightarrow\infty}\frac{1}{T}\sum\limits_{t=1}^{T}\mathbb{E}\left\\{g(t)\right\\}\text{.}$
The reformulated stochastic optimization problem is the following

$\min\limits_{\alpha_{t}}\quad\bar{g}\text{, }\text{ }\text{ s.~{}t.,
}\bar{c}\leq c_{\text{max}}\text{.}$ (10)

In order to satisfy the average cost constraints, we map the average cost
constraint in eqrefoptproblemLyapuno into a virtual queue [19]. We show below
that the time average cost problem is transformed into a queue stability
problem.

Let $\left\\{Z(t)\right\\}$ be the virtual queue associated with constraint
$\eqref{optproblemLyapuno}$. The virtual queue is updated at every time slot
$t$ as

$\displaystyle Z(t+1)=\max[Z(t)-c,0]+\alpha_{t}c\text{.}$ (11)

Process $\left\\{Z(t)\right\\}$ can be viewed as a virtual queue with arrivals
$\alpha_{t}$ and service rate $c$. This idea is based on the fundamental
Lyapunov drift theorem [20].

With the above definitions in mind, we can now proceed to describe our
proposed algorithm and provide performance guarantees regarding the average
cost constraint.

######  Lemma 1.

If $Z(t)$ is rate stable333A discrete time process $Q(t)$ is rate stable if
$\lim\limits_{t\rightarrow\infty}\frac{Q(t)}{t}=0\text{, with probability
1.}$, then the constraint in (10) is satisfied.

###### Proof.

By using the basic sample property [19][Lemma 2.1, Chapter 2], we obtain:

$\displaystyle\frac{Z(t)}{t}-\frac{Z(0)}{t}\geq\frac{1}{t}\sum\limits_{\tau=0}^{t-1}c\alpha_{t}-\frac{1}{t}\sum\limits_{\tau=0}^{t-1}c\text{.}$
(12)

If $Z(t)$ is rate stable, then
$\lim\limits_{t\rightarrow\infty}\frac{Z(t)}{t}=0$. By taking the time average
expectations in $\eqref{ineq:sampleproperty}$ on both sides, we obtain the
result. ∎

In order to stabilize virtual queue $Z(t)$, and therefore by Lemma 1 to
satisfy the average cost constraints, we first define the Lyapunov function as
$L(Z(t))\triangleq\frac{1}{2}Z^{2}(t)$ and the Lyapunov drift as

$\displaystyle\Delta(Z(t))\triangleq\mathbb{E}\left\\{L(Z(t+1))-L(Z(t))|Z(t)\right\\}\text{.}$
(13)

The above conditional expectation is with respect to the random source state
transitions, channel states, and transmission decisions. We apply the DPP
algorithm to minimize the time average expected cost while stabilizing the
virtual queues, $Z(t)$. Specifically, this approach seeks to minimize an upper
bound on the following expression

$\displaystyle\Delta(Z(t))+W\mathbb{E}\left\\{g(t)\right\\}\text{,}$ (14)

where $W>0$ is an importance factor to scale the penalty. By utilizing
$(\max\left[Q-b,0\right]+A)^{2}\leq Q^{2}+A^{2}+b^{2}+2Q(A-b)$, we get the
following upper bound on the expression in (14)

$\displaystyle\Delta(Z(t))+W\mathbb{E}\left\\{g(t)\right\\}$
$\displaystyle\leq
B+W\mathbb{E}\left\\{g(t)\right\\}+\mathbb{E}\left\\{Z(t)(c\alpha_{t}-c_{\text{max}})\right\\}\text{,}$
(15)

where $B<\infty$, and
$B\geq\frac{(\alpha_{t}c_{\text{max}})^{2}+c_{\text{max}}^{2}}{2}.$

###  IV-C Drift-Plus Penalty Algorithm

At every time slot $t$, the transmitter observes the state of the source
$(X_{t})$ and the estimated state at the destination $(\bar{X}_{t})$, and it
takes a decision according to the following optimization problem

$\displaystyle\min\limits_{\alpha_{t}}\quad$ $\displaystyle
Wg(t)+Z(t)(c\alpha_{t}-c_{\text{max}})\text{.}$ (16)

######  Lemma 2.

We consider a class of stationary policies, possibly randomized, denoted by
$\Omega$. A policy $\omega(t)$ that belongs to the class $\Omega$ is an i.i.d.
process that takes probabilistic decisions independent of the state of the
system, at every time slot $t$. Let $y(t)=c\alpha_{t}-c_{\text{max}}$, and
$c(t)=c\alpha_{t}$. Then, if the problem in (10) is strictly feasible, and the
second moments of $y(t)$ and $g(t)$ are bounded, then there is $\epsilon>0$
for which there is an $\omega(t)$ policy such that the following holds

$\displaystyle\mathbb{E}\left\\{y(t)\right\\}\leq\epsilon\text{,
}\mathbb{E}\left\\{g^{*}(t)\right\\}=g_{\omega}\leq
g^{\text{opt}}+\epsilon\text{,}$

where $y^{*}(t)$ and $g^{*}(t)$ are the resulting values of the $\omega$
policy, and $g^{\text{opt}}$ is the optimal value function in (10) achievable
by any optimal stationary randomized policy.

###### Proof.

Since the cost for sampling and transmission is bounded, the second moment of
$c(t)$ is also bounded. Furthermore, since the values of the matrix $C$ are
bounded, the second moment of $g(t)$ is also bounded. Therefore, we have

$\displaystyle\mathbb{E}\left\\{c(t)^{2}\right\\}\leq c^{2}\text{,
}\mathbb{E}\left\\{g(t)^{2}\right\\}\leq C_{\text{max}}^{2}\text{,}$

where $C_{\text{max}}$ is the maximum value of instantaneous actuation cost.
Then, the boundedness assumptions in [19][Ch. 4.2.1] are satisfied. Therefore,
from Theorem 4.5 in [19], we get the result. ∎

######  Theorem 2.

The DPP algorithm satisfies any feasible set of average cost constraints.

###### Proof.

Since the DPP algorithm seeks to minimize the expression in (16), we obtain
that

$\displaystyle\Delta(Z(t))+W\mathbb{E}\left\\{g(t)|S_{t}\right\\}$ (17)
$\displaystyle\leq
B+Z(t)\mathbb{E}\left\\{y_{\text{DPP}}(t)\right\\}+W\mathbb{E}\left\\{g_{\text{DPP}}(t)\right\\}$
(18) $\displaystyle\leq
B+Z(t)\mathbb{E}\left\\{y^{*}(t)\right\\}+W\mathbb{E}\left\\{g^{*}(t)\right\\}\text{,}$
(19)

where $y^{*}(t)$ and $g^{*}(t)$ are the resulting values after applying policy
$\omega$. By considering the bound in Lemma 2, we get

$\displaystyle\Delta(Z(t))+W\mathbb{E}\left\\{g(t)|S_{t}\right\\}\leq
B+\epsilon Z(t)+W(g^{\text{opt}}+\epsilon)\text{,}$ (20)

and taking $\epsilon\rightarrow 0$, we have

$\displaystyle\Delta(Z(t))+W\mathbb{E}\left\\{g(t)|S_{t}\right\\}\leq
B+Wg^{\text{opt}}\text{.}$ (21)

The above expression is in the exact form of the Lyapunov optimization theory
[19][Theorem 4.2]. Therefore, the virtual queue is mean rate stable, and the
average constraints are satisfied. ∎

##  V Simulation Results

In this section, we compare the performance of the two proposed algorithms
with the baseline algorithm proposed in [12] in terms of average real-time
reconstruction error and cost of actuation error. The baseline policy decides
on sampling and transmission whenever there is a discrepancy between the
states at the source and at the destination, i.e., $X_{t}\neq\bar{X}_{t}$. In
our setup, the average cost constraint, $c_{\text{max}}$, is set to $0.2$,
with a cost of sampling and transmission equal to $1$. Therefore, a feasible
policy decides $20\%$ of the time for sampling and transmission. Note that the
baseline algorithm does not take into account the sampling and transmission
costs.

We consider two cases for the source dynamics: a slowly varying source and a
fast varying source. We consider that the Markov source has four states and is
modeled as a birth-death process. The cost of the actuation error matrix
remains fixed in both cases. The values of the matrix are shown below

$\displaystyle C=\left(\begin{array}[]{l|cccc}&0&1&2&3\\\ \hline\cr
0&0&10&50&30\\\ 1&10&0&40&20\\\ 2&20&10&0&10\\\
3&30&20&40&0\end{array}\right)\text{,}$ (27)

where element $C_{i,j}$ is the cost of actuation error for the source being in
state $i$ while the estimated value, $\hat{X}$, is $j$.

###  V-A Slowly varying source

In Fig. 1, we compare the average reconstruction error and the average cost of
actuation error resulting from the three algorithms for the case of a slowly
varying source. The transition of the Markov source is shown below:

$\displaystyle P=\left[\begin{matrix}0.8&0.2&0&0\\\ 0.1&0.8&0.1&0\\\
0&0.1&0.8&0.1\\\ 0&0&0.2&0.8\end{matrix}\right].$ (28)

(a)

(b)

Figure 1: Performance of proposed policies as a function of the success
probability for a slowly varying source.

We consider that the source remains in the same state with a high probability
$(0.8)$. In Fig. 1a, we observe that the proposed DPP and VIA algorithms have
very similar performance and provide lower average reconstruction error than
the baseline algorithm. Moreover, in Fig. 1b, we see that the difference
between the cost of actuation error performance of the baseline and the
proposed algorithms increases. This is because the baseline algorithm decides
on sampling and transmission whenever there is a discrepancy between the
source and the destination, without explicitly taking into account the cost of
actuation error.

###  V-B Rapidly varying source

In the case of a rapidly varying source, we consider that the Markov source
remains in the same state with probability $0.2$. The corresponding transition
matrix is

$\displaystyle P=\left[\begin{matrix}0.2&0.8&0&0\\\ 0.4&0.2&0.4&0\\\
0&0.4&0.2&0.4\\\ 0&0&0.8&0.2\end{matrix}\right].$ (29)

In Figs. 2a and 2b, we provide results for the average reconstruction error
and average cost of actuation error, respectively. We observe that the
performance of the baseline algorithm is better than that of VIA and DPP as
far as the reconstruction error is concerned. However, the proposed algorithms
still provide superior performance in terms of cost of actuation error, which
is the metric of interest in this paper. The reason is that the algorithms
proposed here take into account both the cost of actuation error and the
statistics of the Markov source. Therefore, a main observation from the
results is that _low reconstruction error does not necessarily imply a low
average cost of actuation error_. The reason is that these are two different
performance metrics, and in a remote monitoring system with delayed
measurements, it is crucial to take into account the statistics of the source
and how the states of the source vary with the time horizon.

(a)

(b)

Figure 2: Performance of proposed policies as a function of the success
probability for a rapidly varying source.

##  VI Conclusion

In this work, we studied the minimization of the actuation error under
resource constraints for real-time tracking of a remote source over wireless.
We provided an optimal solution to the optimization problem and a low-
complexity algorithm that guarantees the satisfaction of the average cost
constraints. Our simulation results show that the performance of the low-
complexity algorithm is close to optimal. We observed that an optimal policy
for this problem takes into account not only the discrepancy in state between
the source and the destination, but also the cost of actuation error that
occurs due to this discrepancy, as well as the statistics of the source.
Depending on the setup, it is sometimes beneficial to remain silent rather
than perform sampling and transmitting a status update to the destination when
there are delayed measurements sent to the actuator.

## References

  * [1] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?,” in Proc. IEEE INFOCOM,, pp. 2731–2735, 2012.
  * [2] A. Kosta, N. Pappas, V. Angelakis, et al., “Age of information: A new concept, metric, and tool,” Foundations and Trends® in Networking, vol. 12, no. 3, pp. 162–259, 2017.
  * [3] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 5, pp. 1183–1210, 2021.
  * [4] K. Huang, W. Liu, M. Shirvanimoghaddam, Y. Li, and B. Vucetic, “Real-time remote estimation with hybrid arq in wireless networked control,” IEEE Trans. on Wireless Commun., vol. 19, no. 5, pp. 3490–3504, 2020.
  * [5] Y. Sun, Y. Polyanskiy, and E. Uysal, “Sampling of the wiener process for remote estimation over a channel with random delay,” IEEE Trans. on Inform. Theory, vol. 66, no. 2, pp. 1118–1135, 2019.
  * [6] H. Tang, Y. Sun, and L. Tassiulas, “Sampling of the wiener process for remote estimation over a channel with unknown delay statistics,” Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pp. 51–60, 2022.
  * [7] X. Zheng, S. Zhou, and Z. Niu, “Urgency of information for context-aware timely status updates in remote control systems,” IEEE Trans. on Wireless Commun., vol. 19, no. 11, pp. 7237–7250, 2020.
  * [8] M. Kountouris and N. Pappas, “Semantics-empowered communication for networked intelligent systems,” IEEE Communications Magazine, vol. 59, no. 6, pp. 96–102, 2021.
  * [9] D. Gündüz, Z. Qin, I. E. Aguerri, H. S. Dhillon, Z. Yang, A. Yener, K. K. Wong, and C.-B. Chae, “Beyond transmitting bits: Context, semantics, and task-oriented communications,” IEEE Journal on Selected Areas in Communications, vol. 41, no. 1, pp. 5–41, 2023.
  * [10] P. A. Stavrou and M. Kountouris, “A rate distortion approach to goal-oriented communication,” in Proc. IEEE ISIT, pp. 590–595, 2022.
  * [11] Q. Lan et al., “What is semantic communication? a view on conveying meaning in the era of machine intelligence,” Journal of Communications and Information Networks, vol. 6, no. 4, pp. 336–371, 2021.
  * [12] N. Pappas and M. Kountouris, “Goal-oriented communication for real-time tracking in autonomous systems,” in Proc. IEEE ICAS, 2021.
  * [13] M. Salimnejad, M. Kountouris, and N. Pappas, “Real-time reconstruction of markov sources and remote actuation over wireless channels,” arXiv preprint arXiv:2302.13927, 2023.
  * [14] E. Altman, Constrained Markov decision processes, vol. 7.  CRC Press, 1999.
  * [15] F. J. Beutler and K. W. Ross, “Optimal policies for controlled markov chains with a constraint,” Journal of mathematical analysis and applications, vol. 112, no. 1, pp. 236–252, 1985.
  * [16] D. P. Bertsekas, Dynamic Programming and Optimal Control, Vol. II.  Athena Scientific, 3rd ed., 2007.
  * [17] D.-J. Ma, A. M. Makowski, and A. Shwartz, “Estimation and optimal control for constrained markov chains,” in Proc. IEEE CDC, pp. 994–999, 1986.
  * [18] W. B. Powell, Approximate Dynamic Programming: Solving the curses of dimensionality, vol. 703.  John Wiley & Sons, 2007.
  * [19] M. J. Neely, Stochastic Network Optimization with Application to Communication and Queueing Systems.  Morgan & Claypool, 2010.
  * [20] S. P. Meyn and R. L. Tweedie, Markov chains and stochastic stability.  Springer Science & Business Media, 2012.

  *[AoI]: Age of Information
  *[CMDP]: Constrained Markov Decision Process
  *[DTMC]: Discrete-Time Markov Chain
  *[ACK]: acknowledgement
  *[MDP]: Markov Decision Process
  *[DPP]: Drift-Plus-Penalty