# Optimal Policies for Age and Distortion in a Discrete-Time Model

Yunus İnan, , Reka Inovan, , Emre Telatar The authors are with École
Polytechnique Fédérale de Lausanne (EPFL), 1015 Lausanne, Switzerland. Emails:
{yunus.inan, reka.inovan<EMAIL_ADDRESS>
A short version of this work is presented at IEEE ITW 2021 [1].

###### Abstract

We study a discrete-time model where each packet has a cost of not being sent
— this cost might depend on the packet content. We study the tradeoff between
the age and the cost where the sender is confined to packet-based strategies.
The optimal tradeoff is found by an appropriate formulation of the problem as
a Markov Decision Process (MDP). We show that the optimal tradeoff can be
attained with finite-memory policies and we devise an efficient policy
iteration algorithm to find these optimal policies. We further study a related
problem where the transmitted packets are subject to erasures. We show that
the optimal policies for our problem are also optimal for this new setup.
Allowing coding across packets significantly extends the packet-based
strategies. We show that when the packet payloads are small, the performance
can be improved by coding.

###### Index Terms:

Age of Information, Distortion, Markov Decision Process, Policy Iteration

##  I Introduction

Timeliness of information is a crucial aspect of communications. Stale data
may have highly undesirable effects; think, for example, of sensor output for
self-driving vehicles, position of an airplane, coolant temperature in a power
plant, etc. This aspect of data is nicely captured by the recently studied
notion of Age-of-Information (AoI), by shifting the focus from delay to
freshness. At the same time, not all data is equally important. If, in an
attempt to reduce staleness our system drops important pieces of data, the
remedy may be worse than the disease. In this work, we study a simple setup
where the freshness and importance aspects may be treated together.

The loss, or misrepresentation of data and assigning higher cost to more
important data is well-captured by the tools of rate-distortion theory. As
said above, the question of freshness has been an object of study in the AoI
literature initiated by Kaul et al. [2]. Since the introduction of AoI, there
has been various uses of this metric in many applications. In this work, we
quantify the notion of importance by using a distortion metric. We analyze a
discrete-time model which allows us to analyze the tradeoff between timeliness
as measured by AoI and the distortion of the data. The tradeoff can be studied
by casting it as a problem of finding the optimal policy of a Markov Decision
Process (MDP) which identifies the packets to be dropped. We show that the
optimal policy for this MDP can be achieved by a system with finite memory and
we also provide an explicit algorithm to compute this policy, which also turns
out to be an optimal policy of a problem where the sender transmits packets
over an erasure channel with feedback. Lastly, for packets with small payload,
we show that one can improve the performance with variable-to-fixed length
coding techniques, such as Tunstall coding.

##  II Related Work

Freshness of data is recently recognized as a semantic aspect of
communication. Initial work by Kaul et al. introduced the AoI as a metric to
quantify this aspect [2, 3, 4]. Following Kaul et al., there have been many
studies adopting AoI as a freshness metric. The first strand involved
calculation of AoI in simple schemes, e.g. M/M/1 queues [2]. Subsequent
extensions involve more general queues [5, 6, 7, 8], multiple source streams
[9, 10, 11, 12], various queue management techniques such as the Last-Come-
First-Served (LCFS) protocol [13], and models that allow packet discards [14,
15, 16, 17] and deadlines [18]. A partial list of studies that seek to compute
or to minimize the age under energy or link constraints is [19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34]. For a comprehensive survey
over the AoI literature, see [35]; and for a tutorial, see [36].

Although the works cited above mostly assume error-free transmissions, some
others take into account that packets get lost or erased while passing through
the network. In [37], the AoI is studied in a model where transmissions are
error-prone. One may notice that a simple method to combat erasures is to send
the packet repeatedly. A more complicated method could send coded packets,
which are then to be conveyed through the erasure channel. A list of works
concerning coded transmissions with feedback is [38, 39, 40, 41, 42, 43, 44,
45]. An example of a study assuming no feedback is [46], where the authors
find the optimal coding strategy. In Section VI, we will discuss that the
optimal strategy for our discrete-time model is also optimal for a model where
communications take place over an erasure channel with feedback.

AoI has also found place in stochastic control literature. For instance, in
[47], a tradeoff between the information staleness and performance of a Linear
Quadratic Regulator (LQR) is illustrated. In [48], freshness is taken as basis
for an algorithm devised for distributed tracking of a linear system. These
works are aligned in the sense that using the fresh data to track and control
a system might improve the performance. This is because of the Markovian
nature of the processes that are tracked — the next state depends only on the
freshest data. However, this may not always be the case as the freshest may
not be the most important. This observation is in line with some further
studies. For instance in [49], a problem of generating timely updates in a
remote estimation setting has been proposed. The authors have investigated the
Mean-square-optimal and AoI-optimal strategies for the estimation of a Wiener
process through a queue and concluded that they are different; consequently
demonstrating a tradeoff between freshness and importance. In [50], the
authors generalized the settings to include an Ornstein–Uhlenbeck process. In
[31], a tradeoff between timeliness and distortion is shown for the case of
estimation through a Gaussian channel in a power constrained setting. There
also has been several works on integrating the notion of different data
importance and timeliness, e.g., by introducing non-linear cost to stale data
[51, 52], by considering separate data streams of different priorities [53,
54], or by modeling the distortion as a decreasing function of the service
time [55].

Our setup contains flavors from the above approaches, yet it features novel
aspects. For instance, the resource constraint is imposed by an external
scheduler, giving the sender turns to speak. Hence, as opposed to the works
[49, 50], the sender cannot decide when to send; but it rather decides what to
send. Furthermore, we adopt the view that data is formed into packets of
different importance levels, e.g., packets containing abnormal levels of
coolant temperature in a nuclear plant could be classified as important.
Consequently, the distortion metric we propose depends on whether the packets
are received or not, and the accumulated importance levels of the missed data
constitutes our distortion metric.

##  III Notation

Random variables are denoted with uppercase letters (e.g., $X$); and vectors
are denoted with boldface letters (e.g., $\boldsymbol{b}$). Sets are denoted
with script-style letters (e.g., $\mathcal{V}$). $l(\boldsymbol{b})$ is the
length of a vector $\boldsymbol{b}$, and $b_{i}$ is its $i^{\text{th}}$
element. For vectors $\boldsymbol{b}$ and $\boldsymbol{b}^{\prime}$,
$\boldsymbol{b}\|\boldsymbol{b}^{\prime}\mathrel{\mathop{\mathchar
58\relax}}=[b_{1},b_{2},\ldots,b^{\prime}_{1},b^{\prime}_{2},\ldots]$ is the
concatenation of the two vectors. $\boldsymbol{b}_{\geq
i}\mathrel{\mathop{\mathchar 58\relax}}=[b_{i},\dots,b_{l}]$ is segment of
$\boldsymbol{b}$ from its $i^{\text{th}}$ element until the end; and
$\boldsymbol{b}_{i}^{j}\mathrel{\mathop{\mathchar
58\relax}}=[b_{i},\dots,b_{j}]$ is the segment between its $i^{\text{th}}$ and
$j^{\text{th}}$ elements, $\boldsymbol{b}^{i}\mathrel{\mathop{\mathchar
58\relax}}=\boldsymbol{b}_{1}^{i}$ . $\boldsymbol{b}^{\prime}$ is a suffix of
$\boldsymbol{b}$ if there exists an $i>1$ such that
$\boldsymbol{b}^{\prime}=\boldsymbol{b}_{\geq i}$. If
$\boldsymbol{b}^{\prime}=\boldsymbol{b}_{\geq i}$ is suffix of
$\boldsymbol{b}$, then
$\boldsymbol{b}\setminus\boldsymbol{b}^{\prime}=\boldsymbol{b}^{i-1}$. For
$a,b\in\mathbb{R}$, $a\wedge b\mathrel{\mathop{\mathchar
58\relax}}=\min\\{a,b\\}$, and $a\vee b\mathrel{\mathop{\mathchar
58\relax}}=\max\\{a,b\\}$.

##  IV Problem Definition

In this section, we describe our discrete-time model in terms of the data to
be conveyed, the sender-receiver pair with their respective communication
protocol, and the channel in between.

We assume that the data is formed into packets, and at each time instant $t$,
a new packet arrives to the sender. The packet payloads originate from a set
of finite elements $\mathcal{X}$, and the probability of a payload taking a
particular value is time-invariant and independent of the past. Consequently,
the data is an independent and identically distributed (i.i.d.) process
$\\{X_{t}\\}_{t\in\mathbb{N}}$. The sender observes $X_{t}$ at time $t$ and
keeps $X_{t}$ in its buffer.

The communication protocol is as follows: The sender is allowed to speak at
times $T_{1},T_{2},\ldots$. The process $\\{T_{i}\\}_{i\in\mathbb{N}}$ is
independent of the process $\\{X_{t}\\}_{t\in\mathbb{N}}$, and has the
property that the interspeaking times $Z_{i}\mathrel{\mathop{\mathchar
58\relax}}=T_{i}-T_{i-1}$ are i.i.d.. Moreover, we assume that $Z_{i}$’s are
strictly positive and square integrable, i.e., $\Pr(Z_{i}>0)=1$ and
$E[Z_{i}^{2}]\leq\infty$. An example of such a random variable could be a
geometric random variable with $\Pr(Z_{i}=t)=p(1-p)^{t-1}$ for $t\geq 1$. The
speaking process $\\{T_{i}\\}_{i\in\mathbb{N}}$ is inspired by MAC layer
protocols where each sender is assigned time slots to speak. When the sender
is given a turn to speak, i.e., at each $T_{i}$, it selects a packet from its
buffer with timestamp $S_{i}\leq T_{i}$ and forwards $X_{S_{i}}$. Once
$X_{S_{i}}$ is forwarded, we restrict the sender to not send a packet with
timestamp less than $S_{i}$ at the subsequent speaking times
$T_{i+1},T_{i+2},\ldots$. Note that such restriction results in
$S_{i}<S_{i+1}$. The increasing sequence $\\{S_{i}\\}_{i\geq
0}=\mathrel{\mathop{\mathchar 58\relax}}\boldsymbol{S}$ is henceforth referred
as the ‘selection process’.

Transmissions between the sender and the receiver are noiseless and zero-
delay. Hence, by time $t$, the receiver has observed $X_{S_{i}}$ for every $i$
such that $T_{i}<t$. We also suppose that the packets are formed to contain
timestamps, i.e., the packet containing $X_{S_{i}}$ also contains the
information that it was generated at time $S_{i}$. Consequently, at time $t$,
the receiver is able to reconstruct the data as $Y_{j}(t)=X_{j}$ if $X_{j}$ is
among its observation up to time $t$; otherwise it sets
$Y_{j}(t)=\operatorname{?}$.

At this point, we have described our model. Now, we introduce the appropriate
distortion and timeliness metrics to study their tradeoff. Specifically, given
$d\mathrel{\mathop{\mathchar
58\relax}}\mathcal{X}\times\mathcal{X}\cup\\{\operatorname{?}\\}\to\mathbb{R}_{\geq
0}$, with

$d(x,x)=0\text{ and }d(x,\operatorname{?})=\mathrel{\mathop{\mathchar
58\relax}}v(x),$ (1)

and given a selection procedure $\boldsymbol{S}$, define

$D_{t}^{(\boldsymbol{S})}\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{t}\sum_{i=1}^{t}d(X_{i},Y_{i}(t))\text{\ and\
}D^{(\boldsymbol{S})}\mathrel{\mathop{\mathchar
58\relax}}=E\bigg{[}\limsup_{t\to\infty}D_{t}^{(\boldsymbol{S})}\bigg{]}.$ (2)

With an analogy to rate-distortion theory, observe that
$D_{t}^{(\boldsymbol{S})}$ quantifies average distortion between the source
and its reconstruction. $D^{(\boldsymbol{S})}$ is the expected long-term
average distortion.

Timeliness of information is quantified with the well-studied AoI metric.
Namely, with $i(t)\mathrel{\mathop{\mathchar 58\relax}}=\sup\\{i\geq
0\mathrel{\mathop{\mathchar 58\relax}}T_{i}<t\\}$, $T_{0}=S_{0}=0$; define for
all $t>0$,

$\Delta_{t}^{(\boldsymbol{S})}\mathrel{\mathop{\mathchar
58\relax}}=t-S_{i(t)},\text{\ and\
}\Delta^{(\boldsymbol{S})}\mathrel{\mathop{\mathchar
58\relax}}=E\bigg{[}\limsup_{t\to\infty}{\frac{1}{t}\sum_{\tau=1}^{t}\Delta_{\tau}^{(\boldsymbol{S})}}\bigg{]}\text{.}$
(3)

$\Delta_{t}^{(\boldsymbol{S})}$ is usually referred as the instantaneous age;
and similar to $D^{(\boldsymbol{S})}$, $\Delta^{(\boldsymbol{S})}$ is the
expectation of the long-term average age.

Note that $Y_{i}(t)$ can be either equal to $X_{i}$ or to
‘$\operatorname{?}$’. Therefore, specifying only $d(x,x)$ and
$d(x,\operatorname{?})$ — which is readily determined by $v(x)$ — is
sufficient to evaluate $D^{(\boldsymbol{S})}$. As a consequence, the sender
may base its selection $S_{i}$ on $\boldsymbol{V}^{T_{i}}$, where
$V_{t}\mathrel{\mathop{\mathchar 58\relax}}=v(X_{t})$. Therefore, the
selection $S_{i}$ is a map $S_{i}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{V}^{T_{i}}\to\\{S_{i-1}+1,\ldots,T_{i}\\}$ with
$\mathcal{V}\mathrel{\mathop{\mathchar
58\relax}}=\\{v(x)\mathrel{\mathop{\mathchar 58\relax}}{x\in\mathcal{X}}\\}$.
Intuitively, $V_{i}$ represents an importance score for the packet $i$; high
$V_{i}$ is interpreted as the content having high importance and not sending
it incurs a high penalty — this interpretation is also consistent with a model
where some arrivals are prioritized. Observe that the structure of the problem
stays the same if all elements of $\mathcal{V}$ are multiplied by a positive
constant. If $\mathcal{V}$ does not contain $0$, then without loss of
generality one can assume that the minimum element in $\mathcal{V}$ is $1$ and
it is an ordered set as
$1=v_{1}<v_{2}<\ldots<v_{|\mathcal{V}|}\mathrel{\mathop{\mathchar
58\relax}}=v_{\max}<\infty$.

Now that we have the full description of the setting, we aim to characterize
the achievable region of $(\Delta^{(\boldsymbol{S})},D^{(\boldsymbol{S})})$
pairs. We attempt to characterize this region in the sequel and conclude this
section with a few remarks.

  * (i)

The model we propose is reminiscent of a remote estimation problem of a
discrete-time stochastic process through a discrete-time queue. However, we
require that the sender sends a packet exactly at speaking times, which is
equivalent to force the sender to send as soon as the queue is idle in a
discrete-time queueing setting. In [56] and [49], it is shown that the optimal
policies need not be of this type. This makes our problem different and allows
us to make the relaxation that $S_{i}$ need not be stopping times.

  * (ii)

If $0\in\mathcal{V}$, there are multiple interpretations. $V_{t}=0$ can be
interpreted as either the data is totally trivial (need not be reconstructed),
or interpreted as the source having not generated data at time $t$. The second
interpretation allows us to model a source which generates data sporadically.
Now there is the question of allowing $X_{t}$ to be sent or not. Our model
allows sending of $X_{t}$, i.e., in the second interpretation, informs the
receiver that there has not been any data generated by the source, and
$\Delta_{t}$ decreases accordingly. The reduction of $\Delta_{t}$ can be
avoided by appropriate reformulation — to be discussed in Remark 1.

##  V The Age-Distortion Tradeoff

###  V-A Markov Decision Problem Formulation as a Lower Bound

To study the age-distortion tradeoff, we study the family of weighted costs
$\eta\Delta^{(\boldsymbol{S})}+D^{(\boldsymbol{S})}$ for $\eta>0$. It is known
that the boundary of the achievable
$(\Delta^{(\boldsymbol{S})},D^{(\boldsymbol{S})})$ region can be characterized
by studying this family. We seek to obtain a tractable lower bound for
$\eta\Delta^{(\boldsymbol{S})}+D^{(\boldsymbol{S})}$, and then we further
optimize this lower bound over $\boldsymbol{S}$. First, we derive a simpler
expression for $\Delta^{(\boldsymbol{S})}$. Observe that

$\limsup_{t\to\infty}{\frac{1}{t}\sum_{\tau=1}^{t}\Delta_{\tau}^{(\boldsymbol{S})}}=\limsup_{i\to\infty}\frac{\sum_{j=1}^{i}Q_{j}^{(\boldsymbol{S})}}{\sum_{j=1}^{i}Z_{j}}$
(4)

where

$Q_{j}^{(\boldsymbol{S})}\mathrel{\mathop{\mathchar
58\relax}}=(T_{j}-S_{j})Z_{j+1}+\frac{Z_{j+1}(Z_{j+1}+1)}{2}.$ (5)

Since
$\displaystyle\lim_{i\to\infty}\textstyle\frac{1}{i}\sum_{j=1}^{i}\frac{Z_{j+1}(Z_{j+1}+1)}{2}=\frac{1}{2}E[Z_{1}(Z_{1}+1)]=\mathrel{\mathop{\mathchar
58\relax}}\nu$ and
$\lim_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}Z_{j}=E[Z_{1}]=\mathrel{\mathop{\mathchar
58\relax}}\mu$ with probability 1 by the law of large numbers, we obtain

$\Delta^{(\boldsymbol{S})}=E\bigg{[}\frac{1}{\mu}\limsup_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}(T_{j}-S_{j})Z_{j+1}+\frac{\nu}{\mu}\bigg{]}.$
(6)

Note that $\Delta^{(\boldsymbol{S})}$ cannot be smaller than $\nu/\mu$. We
subtract $\nu/\mu$ to obtain the excess age, given by

$\Delta_{e}^{(\boldsymbol{S})}\mathrel{\mathop{\mathchar
58\relax}}=E\bigg{[}\frac{1}{\mu}\limsup_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}(T_{j}-S_{j})Z_{j+1}\bigg{]}$
(7)

and determine the feasible
$(\Delta_{e}^{(\boldsymbol{S})},D^{(\boldsymbol{S})})$ pairs. With the same
reasoning as above, we study the family
$\eta\Delta_{e}^{(\boldsymbol{S})}+D^{(\boldsymbol{S})}$. When the selection
process $\boldsymbol{S}$ satisfies a certain square-integrability condition,
we can find alternative expressions for $\Delta_{e}^{(\boldsymbol{S})}$ and
$D^{(\boldsymbol{S})}$.

######  Theorem 1.

Let $\mathcal{S}_{2}$ be the set of selection processes $\boldsymbol{S}$ with
$\sup_{i}E[(T_{i}-S_{i})^{2}]<\infty$. Then for any
$\boldsymbol{S}\in\mathcal{S}_{2}$,

$\displaystyle\Delta_{e}^{(\boldsymbol{S})}$
$\displaystyle=E\bigg{[}\limsup_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}(T_{j}-S_{j})\bigg{]},$
(8) $\displaystyle D^{(\boldsymbol{S})}$
$\displaystyle=\frac{1}{\mu}E\bigg{[}\limsup_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}D(\boldsymbol{V}^{T_{j}},S_{j-1},S_{j})\bigg{]},$
(9)

where

$D(\boldsymbol{V}^{T_{j}},S_{j-1},S_{j})\mathrel{\mathop{\mathchar
58\relax}}=\sum_{j^{\prime}=S_{j-1}+1}^{S_{j}-1}V_{j^{\prime}}$ (10)

is the penalty incurred by skipping the portion
$[V_{S_{j-1}+1},\ldots,V_{S_{j}-1}]$ of $\boldsymbol{V}^{T_{j}}$.

###### Proof.

See Appendix -A. ∎

At this point, we would like to eliminate some of the non-optimal selection
processes. More specifically, we show that if a packet with importance value
$v_{\min}$ and with timestamp less than $T_{i}$ is selected at time $T_{i}$,
then one can find another selection process which performs at least as well.

######  Lemma 1.

Consider a selection process $\boldsymbol{S}$ with $S_{i_{0}}<T_{i_{0}}$ and
$V_{S_{i_{0}}}=v_{\min}$ for some $i_{0}$. Then one can find another process
$\tilde{\boldsymbol{S}}$ with $V_{\tilde{S}_{i_{0}}}>v_{\min}$ and such that
$\Delta_{e}^{(\tilde{\boldsymbol{S}})}\leq\Delta_{e}^{(\boldsymbol{S})}$ and
$D^{(\tilde{\boldsymbol{S}})}\leq D^{(\boldsymbol{S})}$.

###### Proof.

See Appendix -B. ∎

Lemma 1 helps restrict the search space for possibly optimal selection
processes. The processes we study in the sequel will not select a minimum-
importance packet if it has not arrived exactly at the speaking time. Let us
denote the class of such selection processes as $\mathcal{S}_{2}^{\prime}$.

A search for an optimal strategy based on the expressions in Theorem 1 seems
to be a complex task. We aim to obtain a further lower bound for
$\eta\Delta_{e}^{(\boldsymbol{S})}+D^{(\boldsymbol{S})}$ which turns out to be
an entity that is amenable for analysis. This lower bound is given in

######  Theorem 2.

Define

$J_{i}(\eta)^{(S_{1}^{T_{i}})}\mathrel{\mathop{\mathchar
58\relax}}=E\bigg{[}\sum_{j=1}^{i}\frac{1}{\mu}D(\boldsymbol{V}^{T_{j}},S_{j-1},S_{j})+\eta(T_{j}-S_{j})\bigg{]}$
(11)

and

$J(\eta)^{(\boldsymbol{S})}\mathrel{\mathop{\mathchar
58\relax}}=\limsup_{i\to\infty}\frac{1}{i}J_{i}(\eta)^{(S_{1}^{T_{i}})}.$ (12)

Then, for any $\boldsymbol{S}\in\mathcal{S}_{2}^{\prime}$,
$J(\eta)^{(\boldsymbol{S})}\leq
D^{(\boldsymbol{S})}+\eta\Delta_{e}^{(\boldsymbol{S})}$.

###### Proof.

See Appendix -A. ∎

A straightforward implication is

$J^{*}(\eta)\mathrel{\mathop{\mathchar
58\relax}}=\inf_{\boldsymbol{S}\in\mathcal{S}_{2}^{\prime}}J(\eta)^{(\boldsymbol{S})}\leq\inf_{\boldsymbol{S}\in\mathcal{S}_{2}^{\prime}}\big{(}D^{(\boldsymbol{S})}+\eta\Delta_{e}^{(\boldsymbol{S})}\big{)}.$
(13)

As we shall see later in Section V-C, it turns out that the inequality (13) is
indeed an equality. The key reason to introduce $J(\eta)^{(\boldsymbol{S})}$
is that its infimization can be formulated as a MDP, which we do next. This
requires identifying the states and the actions of the MDP and verifying that
(i) the distribution of the next state and (ii) the one-step cost depend only
on the current state-action pair. We claim that the buffer content at the
$i^{\text{th}}$ speaking time

$\boldsymbol{B}_{i}\mathrel{\mathop{\mathchar
58\relax}}=\boldsymbol{V}_{S_{i-1}+1}^{T_{i}},$ (14)

and the number of packets to be dropped $A_{i}\mathrel{\mathop{\mathchar
58\relax}}=S_{i}-S_{i-1}$ constitutes this state-action pair. To see this,
note that given $\boldsymbol{B}_{i}$ and $A_{i}$, (i) the next buffer content
is independent of the past; and (ii) the one-step cost

$\frac{1}{\mu}D(\boldsymbol{V}^{T_{i}},S_{i-1},S_{i})+\eta(T_{i}-S_{i})$ (15)

is a function only of $\boldsymbol{B}_{i}$ and $A_{i}$. This is because the
above is equal to

$\frac{1}{\mu}\sum_{k=1}^{s-1}b_{k}+\eta(l(\boldsymbol{b})-s);$ (16)

with $\boldsymbol{b}=\boldsymbol{B}_{i}$ and $s=A_{i}$. Since (i) and (ii) are
satisfied, the problem is indeed an MDP whose state at instant $i$ is the
buffer content $\boldsymbol{B}_{i}$; and whose action at instant $i$ is
$A_{i}$. The assumption $S_{0}=0$ allows us to choose $\boldsymbol{B}_{0}$ as
an empty buffer.

The formulation above is an infinite-horizon average-cost MDP [57] with states
$\boldsymbol{b}\in\mathcal{V}^{*}\mathrel{\mathop{\mathchar
58\relax}}=\cup_{k=1}^{\infty}\mathcal{V}^{k}$; and the set of possible
actions for a state $\boldsymbol{b}$ is given by
$s\in\\{1,\ldots,l(\boldsymbol{b})\\}$, where $l(\boldsymbol{b})$ is the
length of the buffer $\boldsymbol{b}$. Consequently, the sender chooses the
packet with timestamp $S_{i}=T_{i}+s-l(\boldsymbol{b})$ at time $T_{i}$.
Observe that setting $s=l(\boldsymbol{b})$ corresponds to the selection of the
freshest packet whereas setting $s=1$ corresponds to the selection of the
oldest packet in the buffer. Furthermore, since we are interested in the
selection procedures in $\mathcal{S}_{2}^{\prime}$, $s\neq l(\boldsymbol{b})$
only if $b_{s}>v_{\min}$.

In general, the optimal policies of an MDP need not be stationary (the current
action is a deterministic function of the current state). We will show in
Section V-C that for our problem, the optimal policy is indeed stationary.
When we consider a stationary selection process $\boldsymbol{S}$, we
explicitly write the argument $(\boldsymbol{b})$. Let us recall

######  Definition 1 (Unichain policy, [57]).

If a stationary policy $s(\boldsymbol{b})$ induces a Markov chain with a
single recurrent class and a possibly empty set of transient states, it is
called unichain.

In an average-cost dynamic programming setting, we evaluate a unichain policy
$s(\boldsymbol{b})$, $\boldsymbol{b}\in\mathcal{V}^{*}$ by solving the linear
system with unknowns $h(\boldsymbol{b})$, $\boldsymbol{b}\in\mathcal{V}^{*}$
and $\lambda$; given by

$h(\boldsymbol{b})+\lambda=\frac{1}{\mu}\sum_{k=1}^{s(\boldsymbol{b})-1}b_{k}+\eta(l(\boldsymbol{b})-s(\boldsymbol{b}))+E[h(\boldsymbol{b}_{\geq
s(\boldsymbol{b})+1}\|\boldsymbol{V}^{Z})],$ (17)

where $Z$ is the next interspeaking time, $\boldsymbol{V}^{Z}$ is a vector of
i.i.d. $V$’s of length $Z$, $h(\boldsymbol{b})$ is called the relative value
of state $\boldsymbol{b}$, and $\lambda$ is the average cost induced by this
policy. Since (17) determines $h(\boldsymbol{b})$ up to an additive constant,
we take a reference state — see [57, Chapter 4] — as one of the
$\boldsymbol{b}\in\mathcal{V}^{*}$ and we set $h(\boldsymbol{b})=0$. We also
note that for a unichain policy, the linear system given by (17) has a unique
solution [57].

######  Remark 1.

To cover the case where $v=0$ is interpreted as the source having not
generated any data and $\Delta_{t}$ should not decrease upon the sending of
$v=0$; one can proceed as follows: The set of possible actions for a state
$\boldsymbol{b}$ is extended to $\\{0,1,\ldots,l(\boldsymbol{b})\\}$, and
$s>0$ only if $b_{s}>0$. That is, the sender is allowed to choose only the
packets with $v>0$. Also note that for the all-zero buffer, the only possible
action is to set $s=0$, i.e., nothing has arrived since the last selection and
hence there is nothing to send. Observe that in this case $\Delta_{t}$ does
not drop.

Although we have characterized a lower bound based on a MDP formulation, the
formulated problem has a countably infinite state space, $\mathcal{V}^{*}$. It
is known that for this class of problems, analysis of optimal policies become
formidably complex in general. Moreover, it is not certain that a stationary
policy attains the infimum in (13). The complexity of this problem leads us to
consider a finite-state modification of the problem; and the next section is
devoted for this modified version.

###  V-B Policy Iteration with a Truncated State Space

We now consider a finite-state version of the problem where the sender forgets
the packets that have arrived more than $K$ time slots ago. That is, the
current buffer content at time $T_{i}$ becomes

$\boldsymbol{B}_{i}\mathrel{\mathop{\mathchar
58\relax}}=\boldsymbol{V}_{(S_{i-1}+1)\vee(T_{i}-K+1)}^{T_{i}}.$ (18)

Consequently, the buffer length is limited to at most $K$, and the state space
becomes finite. Denote this finite state space by $\mathcal{V}^{\leq
K}\mathrel{\mathop{\mathchar 58\relax}}=\cup_{l\leq K}\mathcal{V}^{l}$. One
may notice that by restricting the state space, we might not attain the
infimal value $J^{*}(\eta)$. However, as we shall see later in V-C, the
optimal policy of the original _infinite_ state space problem will base its
decisions only on a bounded buffer. Thus, we do not lose optimality provided
that $K$ is large enough.

A slight modification of (17) is enough to obtain the linear system whose
solution yields the relative values and the average cost. First, observe that
if the buffer state $\boldsymbol{b}$ has length more than $K$, i.e., if
$l(\boldsymbol{b})>K$, then $h(\boldsymbol{b})$ can be replaced with

$\sum_{k=1}^{l({\boldsymbol{b}})-K}b_{k}+h(\boldsymbol{b}_{\geq
l(\boldsymbol{b})-K+1}).$ (19)

as the first $l(\boldsymbol{b})-K$ terms will be forgotten in the truncated
problem. Let $p_{i}\mathrel{\mathop{\mathchar 58\relax}}=\Pr(Z=i)$ and
$q_{i}\mathrel{\mathop{\mathchar 58\relax}}=\Pr(Z\geq i)$. Then the linear
system of equations to evaluate a unichain stationary policy
$s(\boldsymbol{b})$, $\boldsymbol{b}\in\mathcal{V}^{\leq K}$ becomes

$\displaystyle h(\boldsymbol{b})+\lambda$
$\displaystyle=\frac{1}{\mu}\sum_{k=1}^{s(\boldsymbol{b})-1}b_{k}+\eta(l(\boldsymbol{b})-s(\boldsymbol{b}))\mbox{}+\frac{1}{\mu}\sum_{k=s(\boldsymbol{b})+1}^{l}b_{k}q_{K+k-l}+\frac{E[V]}{\mu}E[(Z-K)^{+}]$
$\displaystyle\phantom{=}+\sum_{k=1}^{K-l+s(\boldsymbol{b})}p_{k}E[h(\boldsymbol{b}_{\geq
s(\boldsymbol{b})+1}\|\boldsymbol{V}^{k})]+\sum_{k=K-l+s(\boldsymbol{b})+1}^{K-1}p_{k}E[h(\boldsymbol{b}_{\geq
k-(K-l)+1}\|\boldsymbol{V}^{k})]+q_{K}E[h(\boldsymbol{V}^{K})]$ (20)
$\displaystyle=\mathrel{\mathop{\mathchar
58\relax}}C_{\boldsymbol{h}}(\boldsymbol{b},s(\boldsymbol{b})),$ (21)

with $h(v_{\min})=0$. This choice of the reference state also sets $h(b)=0$
for $b\in\mathcal{V}$. Namely, for buffers that contain only one packet, the
relative value will be equal to zero.

At this point, we have obtained the policy evaluation method for our finite-
state problem. A first attempt could be to find the optimal policies
numerically. We consider the well-known policy iteration algorithm [57]. A
brief description is given in Algorithm 1.

1Start with the stationary policy $s^{(0)}(\boldsymbol{b})=l(\boldsymbol{b})$.

2 Evaluate $s^{(i)}(\boldsymbol{b})$ according to (V-B) to find
$h^{(i)}(\boldsymbol{b})$, $\boldsymbol{b}\in\mathcal{V}^{\leq K}$ and
$\lambda^{(i)}$.

3 $\text{For all }\boldsymbol{b}\in\mathcal{V}^{\leq K}$, set
$s^{(i+1)}(\boldsymbol{b})=\arg\min_{\begin{subarray}{c}s\mathrel{\mathop{\mathchar
58\relax}}s\leq l(\boldsymbol{b})\\\ b_{s}\neq v_{\min}\text{ if
}s<l(\boldsymbol{b})\end{subarray}}C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},s)$

If $s^{(i+1)}(\boldsymbol{b})=s^{(i)}(\boldsymbol{b})$ for all
$\boldsymbol{b}\in\mathcal{V}^{\leq K}$, terminate. Else go to step 2.

Algorithm 1 Policy iteration

Although the number of states is now finite, it is not clear that the policy
iteration algorithm yields a unichain policy. We shall show this in the
following lemma.

######  Lemma 2.

If the buffer size is limited to $K$, the policy iteration terminates with an
optimal unichain policy in $\mathcal{S}_{2}^{\prime}$.

###### Proof.

Consider all truncated policies, e.g., non-stationary, history dependent but
can only choose the most recent $K$ packets in the buffer. Since
$\\{V_{i}\\}_{i\geq 0}$ is an i.i.d. process, any policy eventually reaches a
state consisting of only $v_{\min}$’s and must choose the most recent packet.
Hence, the buffer must be eventually renewed for any policy in
$\mathcal{S}_{2}^{\prime}$ and as a result, there must be a single recurrent
class. Therefore, there exists an optimal stationary and deterministic
strategy that is unichain and this policy can be found with the policy
iteration algorithm [57]. ∎

######  Remark 2.

Intuitively, step 3 of the above algorithm modifies $s^{(i)}(\boldsymbol{b})$
in the following way: Consider two processes starting at the state
$\boldsymbol{b}$. The first one is iterated with respect to $s^{(i)}$, whereas
the second one is iterated with a different action $\tilde{s}(\boldsymbol{b})$
at the first step and with $s^{(i)}$ subsequently. Now consider the expected
accumulated costs of these two processes until they reach the same state. If
the second process has a smaller expected accumulated cost, changing all
$s^{(i)}(\boldsymbol{b})$ to
$\tilde{s}(\boldsymbol{b})=s^{(i+1)}(\boldsymbol{b})$ results in a better
policy; otherwise try another $\tilde{s}(\boldsymbol{b})$.

###  V-C The Exact Buffer Size for an Optimal Policy

Truncating the state space restricts the actions that may be taken. Therefore,
in general, the infimum in (13) may not be attained with a truncated buffer.
As we have said in the previous section, it turns out that this is not the
case for our problem and the infimum is indeed attained with a finite buffer
size. In this section we quantify this buffer size.

First, consider the policy $s(\boldsymbol{b})=l(\boldsymbol{b})$ for all
$\boldsymbol{b}\in\mathcal{V}^{\leq K}$, i.e., always send the most recent
packet in the buffer. One can observe that this policy induces a Markov chain
with only $|\mathcal{V}|=2$ states regardless of $K$. We shall now show that
this policy is optimal for $\eta$ above some threshold $\eta_{\max}$.

######  Lemma 3.

For $\eta\geq\eta_{\max}\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{\mu}(v_{\max}-v_{\min})$ and for any $M\geq 1$, the
optimal policy among $\mathcal{V}^{\leq M}$ is
$s(\boldsymbol{b})=l(\boldsymbol{b})$; which can be implemented with a buffer
size of 1.

###### Proof.

We show that the policy $s(\boldsymbol{b})=l(\boldsymbol{b})$ remains
unchanged under policy iteration. Start the policy iteration with
$s^{(0)}(\boldsymbol{b})=l(\boldsymbol{b})$. Recalling Remark 2, we will show
that perturbing the policy at initial step cannot decrease the expected
accumulated cost until the original and perturbed processes coincide. Assume
the perturbed action is $\tilde{s}(\boldsymbol{b})=l(\boldsymbol{b})-k$ for a
$k>0$. Notice that the two processes will coincide immediately at the next
step and the difference of the accumulated costs will be
$k\eta-\frac{1}{\mu}(b_{l(\boldsymbol{b})-k}-b_{l(\boldsymbol{b})})\geq\eta-\frac{1}{\mu}(v_{\max}-v_{\min})\geq
0$. Hence the policy remains unchanged. ∎

Considering the truncated state space $\mathcal{V}^{\leq K}$, we give some
properties of optimal policies.

######  Property 1.

For an optimal stationary policy $s^{*}(\boldsymbol{b})$, and optimal relative
values $h^{*}(\boldsymbol{b})$, the following hold:

  * (i)

For any state $\boldsymbol{b}\|\boldsymbol{b}^{\prime}$, either
$s^{*}(\boldsymbol{b}\|\boldsymbol{b}^{\prime})=l(\boldsymbol{b})+s^{*}(\boldsymbol{b}^{\prime})$
or $s^{*}(\boldsymbol{b}\|\boldsymbol{b}^{\prime})\leq l(\boldsymbol{b})$.

  * (ii)

$h^{*}(\boldsymbol{b}^{\prime})\leq
h^{*}(\boldsymbol{b}\|\boldsymbol{b}^{\prime})\leq\frac{1}{\mu}(b_{1}+\ldots+b_{l(\boldsymbol{b})})+h^{*}(\boldsymbol{b}^{\prime})$
for $\boldsymbol{b}$, $\boldsymbol{b}^{\prime}\in\mathcal{V}^{\leq K}$.

###### Proof.

See Appendix -C. ∎

To get a sense of how far can the optimal policy go back in time, i.e., to
measure how large $T_{i}-S_{i}$ can be, it may be informative to consider the
following extreme case, which yields a lower bound on the maximal possible
value of $T_{i}-S_{i}$.

######  Lemma 4.

For the state
$\boldsymbol{b}=[v_{\max},\underbrace{v_{\min},\ldots,v_{\min}}_{L-1}]$,

$s^{*}(\boldsymbol{b})=\begin{cases}1,\quad&\eta\leq\frac{1}{\mu}\frac{(v_{\max}-v_{\min})}{L-1}\\\
L,\quad&\eta>\frac{1}{\mu}\frac{(v_{\max}-v_{\min})}{L-1}\end{cases}.$ (22)

###### Proof.

Since we work with policies in $\mathcal{S}_{2}^{\prime}$, the two possible
actions for this state are either choosing the $v_{\max}$ at the beginning or
choosing the $v_{\min}$ at the end. Referring to Remark 2, suppose at
iteration $i$ we have $s^{(i)}(\boldsymbol{b})=l(\boldsymbol{b})$ and
$\tilde{s}(\boldsymbol{b})=1$; and we aim to find the difference of
accumulated costs until the original and the perturbed processes coincide.
Observe that these processes coincide immediately after the first step and the
difference will be $\eta(L-1)+\frac{1}{\mu}(v_{\min}-v_{\max})$. Then,
$s^{(i+1)}(\boldsymbol{b})=1$ if
$\eta(L-1)\leq\frac{1}{\mu}(v_{\max}-v_{\min})$; otherwise
$s^{(i+1)}(\boldsymbol{b})=l(\boldsymbol{b})$. Note that the difference does
not depend on $i$ and hence the statement for $s^{(i+1)}(\boldsymbol{b})$ is
also true for $s^{*}(\boldsymbol{b})$. ∎

The above lemma therefore gives a necessary buffer size for a possibly optimal
policy as it tells that at
$\eta=\frac{1}{\mu}\frac{(v_{\max}-v_{\min})}{L-1}$, the first packet in the
buffer given in Lemma 4 is chosen by the optimal policy. Hence, attaining the
optimal policy requires a buffer size of at least
$\lceil\frac{1}{\mu}\frac{(v_{\max}-v_{\min})}{\eta}\rceil$. Observe that this
does not imply that the optimal policy is reached within this particular
finite buffer size. Nevertheless, we can prove that this is indeed the case.

######  Theorem 3.

For $M\geq K(\eta)\mathrel{\mathop{\mathchar
58\relax}}=\lceil\frac{1}{\mu}\frac{(v_{\max}-v_{\min})}{\eta}\rceil$, the
optimal policy among $\mathcal{V}^{\leq M}$ is attained by a policy with
buffer size $K(\eta)$. Furthermore, if $b_{s^{*}(\boldsymbol{b})}=v_{i}$, then
$l(\boldsymbol{b})-s^{*}(\boldsymbol{b})<K_{i}(\eta)\mathrel{\mathop{\mathchar
58\relax}}=\lceil\frac{1}{\mu}\frac{(v_{i}-v_{\min})}{\eta}\rceil$ for all
$1\leq i\leq|\mathcal{V}|$.

###### Proof.

See Appendix -D. ∎

Theorem 3 implies that when the policy iteration terminates, the policy it
outputs not only solves the Bellman equation for the state space
$\mathcal{V}^{\leq M}$ for every $M\geq K(\eta)$, but it also solves the
Bellman equation for the countable state space $\mathcal{V}^{*}$. Since
$h^{*}(\boldsymbol{b})$ is finite and $s^{*}(\boldsymbol{b})$ is attained for
every $\boldsymbol{b}$, a straightforward extension of Proposition 2.1 in [57,
Chapter 4] concludes that $s^{*}(\boldsymbol{b})$ is indeed the optimal policy
that attains $J^{*}(\eta)$. Let
$\boldsymbol{S}^{*}=\\{s^{*}(\boldsymbol{B}_{i})\\}_{i\geq 0}$ be the random
sequence of the actions taken by the stationary and deterministic policy
$s^{*}(\boldsymbol{b})$. Recall the inequality

$J^{*}(\eta)\leq
D^{(\boldsymbol{S}^{*})}+\eta\Delta_{e}^{(\boldsymbol{S}^{*})}$ (23)

given in Theorem 2. Furthermore, observe that the buffer state process
$\\{\boldsymbol{B}_{i}\\}$ controlled by $\boldsymbol{S}^{*}$ is a renewal
process — this follows from Lemma 2. Hence, by the renewal reward theorem [58,
Theorem 3.6.1] we have

$\begin{split}\Delta_{e}^{(\boldsymbol{S}^{*})}&=E\bigg{[}\limsup_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}(T_{j}-S_{j})\bigg{]},\\\
&=E\bigg{[}\lim_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}(T_{j}-S_{j})\bigg{]}\\\
&=\lim_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}E\big{[}T_{j}-S_{j}\big{]}\end{split}$
(24)

and similarly

$D^{(\boldsymbol{S}^{*})}=\frac{1}{\mu}\lim_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}E\big{[}D(\boldsymbol{V}^{T_{j}},S_{j-1},S_{j})\big{]}.$
(25)

The above shows that in fact the inequality (23) is an equality. Therefore,
the optimal policies for the MDP give the tangent lines to the exact boundary
curve of the achievable $(\Delta_{e},D)$ region. Consequently, by varying
$\eta$, this curve can be found. We end this section with the following
corollary that summarizes the above results.

######  Corollary 1.

The optimal policy among untruncated state space policies is attained with a
buffer size $K(\eta)$ and can be found with the policy iteration algorithm run
over the state space $\mathcal{V}^{\leq K(\eta)}$, which returns
$J^{*}(\eta)$. Furthermore, the least upper bound to the family of straight
lines $D+\eta\Delta_{e}=J^{*}(\eta)$, $\eta>0$ gives the boundary of the
achievable $(\Delta_{e},D)$ region.

###  V-D An Efficient Algorithm to Find the $(\Delta_{e},D)$ Region

Although one can run the generic policy iteration algorithm to find the
tangent lines to the achievable $(\Delta_{e},D)$ region, this turns out to be
highly inefficient. In this section, we provide an efficient modification of
the policy iteration algorithm. The main idea is to exploit the following
property. We omit its proof as it is a straightforward extension of Property
1(i).

######  Property 2.

Consider the policy iteration algorithm (Algorithm 1). For any
$\boldsymbol{b}$, the policy $s^{(i)}(\boldsymbol{b})$ is either equal to
$s^{(i)}(\boldsymbol{b}_{\geq 2})+1$, or to $1$. Furthermore, if
$s^{(i)}(\boldsymbol{b})=s^{(i)}(\boldsymbol{b}_{\geq 2})+1$, then
$h^{(i)}(\boldsymbol{b})=b_{1}/\mu+h^{(i)}(\boldsymbol{b}_{\geq 2})$.

Property 2 implies that if $s^{(i)}(\boldsymbol{b})\neq 1$, then there must
exist a $\boldsymbol{b}^{\prime}$, which is a suffix of $\boldsymbol{b}$, and
with $s^{(i)}(\boldsymbol{b}^{\prime})=1$. Consequently,

$h^{(i)}(\boldsymbol{b})=h^{(i)}(\boldsymbol{b^{\prime}})+\sum_{b\in\boldsymbol{b}\setminus\boldsymbol{b}^{\prime}}b/\mu.$
(26)

The above observation leads to an improvement in the policy evaluation stage
of the algorithm as we shall see shortly. Denote the set of states
$\boldsymbol{b}^{\prime}$ with $s^{(i)}(\boldsymbol{b}^{\prime})=1$ as
$\mathcal{B}_{1}$. In light of (26), we see that since the relative values for
the other states $\boldsymbol{b}\notin\mathcal{B}_{1}$ can be determined based
on the states in $\mathcal{B}_{1}$, it is sufficient for the linear system in
the policy evaluation step to include the states in $\mathcal{B}_{1}$. We
observed empirically that $|\mathcal{B}_{1}|$ is much smaller compared
$|\mathcal{V}^{\leq K}|$. As solving a linear system with $n$ variables has
$O(n^{3})$ complexity, reducing the set of variables to $\mathcal{B}_{1}$
results in a significant improvement.

If the algorithm is modified as suggested above, the policy evaluation step
gives $h^{(i)}(\boldsymbol{b}^{\prime})$,
$\boldsymbol{b}^{\prime}\in\mathcal{B}_{1}$, and the average cost
$\lambda^{(i)}$. To find other $h^{(i)}(\boldsymbol{b})$’s, we refer to
equation (26), which suggests that the appropriate data structure to represent
the states is a tree structure, denoted as $\mathcal{T}$, where a state
$\boldsymbol{b}$ has children $\\{b\|\boldsymbol{b}\\}_{b\in\mathcal{V}}$.
That is, $\boldsymbol{b}_{\geq 2}$ is the parent of $\boldsymbol{b}$, denoted
by $\operatorname{parent}(\boldsymbol{b})$, and every suffix of
$\boldsymbol{b}$ is its ancestor. Then the final statement of Property 2
translates into the recursion
$h^{(i)}(\boldsymbol{b})=b_{1}/\mu+h^{(i)}(\operatorname{parent}(\boldsymbol{b}))$
for $\boldsymbol{b}\notin\mathcal{B}_{1}$.

Along with Property 2, Theorem 3 also provides simplifications for the search
of an optimal policy. Namely, for a state $\boldsymbol{b}$, and for any
iteration $j$, $s^{(j)}(\boldsymbol{b})\neq s$ for an
$s<l(\boldsymbol{b})-K_{b_{s}}(\eta)$, where $K_{b_{s}}(\eta)=K_{i}(\eta)$ if
$b_{s}=v_{i}$. Using the above facts, we are ready to provide a more efficient
version of the policy iteration algorithm, Algorithm 2, which is tuned for our
problem. The for loops over the tree $\mathcal{T}$ (lines 9 and 12) are in
breadth-first manner. Recall that $h^{(i)}(b)=0$ for $b\in\mathcal{V}$ and we
set $h^{(i)}(\delta)=0$ where $\delta$ denotes the empty string.

1

2

Input: $\eta$

Output: $J^{*}(\eta)$

3 Initialize  __

4 $K\leftarrow K(\eta)$;

5 $s^{(0)}(\boldsymbol{b})\leftarrow l(\boldsymbol{b})$;

6 $\mathcal{B}_{1}\leftarrow\\{v_{\min}\\}$;

7 Set $\delta$ as the root of $\mathcal{T}$ and add the children
$\\{b\|\boldsymbol{b}\\}_{b\in\mathcal{V}}$ for every buffer
$\boldsymbol{b}\in\mathcal{T}$ such that $l(\boldsymbol{b})<K$;

8 $i\leftarrow 0$;

9

10repeat

/* Policy evaluation */

11 Find $\lambda^{(i)}$, $h^{(i)}(\boldsymbol{b}^{\prime})$,
$\boldsymbol{b}^{\prime}\in\mathcal{B}_{1}$ by solving (V-B);

12 for  _$\boldsymbol{b}\in\mathcal{T}\setminus\mathcal{B}_{1}$ with
$l(\boldsymbol{b})>1$_ do

13 $h^{(i)}(\boldsymbol{b})\leftarrow
h^{(i)}(\operatorname{parent}(\boldsymbol{b}))+b_{1}/\mu$;

14

/* Policy update */

15 $\mathcal{B}_{1}\leftarrow\\{v_{\min}\\}$;

16 for  _$\boldsymbol{b}\in\mathcal{T}$ with $l(\boldsymbol{b})>1$_ do

17 if  _$l(\boldsymbol{b}) <K_{b_{1}}(\eta)$ and
$C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},1)<C_{\boldsymbol{h}^{(i)}}(\operatorname{parent}(\boldsymbol{b}),s^{(i+1)}(\operatorname{parent}(\boldsymbol{b})))+b_{1}/\mu$_
then

18 $s^{(i+1)}(\boldsymbol{b})\leftarrow 1$;

19 Add $\boldsymbol{b}$ to $\mathcal{B}_{1}$;

20

21 else

22 $s^{(i+1)}(\boldsymbol{b})\leftarrow
s^{(i+1)}(\operatorname{parent}(\boldsymbol{b}))+1$;

23

24

25 $i\leftarrow i+1$.

26until  _$\boldsymbol{s}^{(i+1)}=\boldsymbol{s}^{(i)}$_ ;

return $\lambda^{(i)}$

Algorithm 2 Efficient Policy Iteration v1($\eta$)

Although Algorithm 2 is much more efficient compared to the generic policy
iteration, one needs to evaluate
$C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},s)$’s — defined in (21) — for both
policy evaluation and update stages. Observe that calculating one of these
quantities takes exactly $|\mathcal{V}^{\leq K}|=O(|\mathcal{V}^{K}|)$
iterations. We can allocate some memory to store these quantities and reduce
the time complexity. First, let
$\operatorname{parent_{\mathcal{B}_{1}}}(\boldsymbol{b})$ be the longest
ancestor of $\boldsymbol{b}$ that is in $\mathcal{B}_{1}$. Then,
$\operatorname{parent_{\mathcal{B}_{1}}}(\boldsymbol{b})=\operatorname{parent_{\mathcal{B}_{1}}}(\operatorname{parent}(\boldsymbol{b}))$
and
$\operatorname{parent_{\mathcal{B}_{1}}}(\boldsymbol{b}^{\prime})=\boldsymbol{b}^{\prime}$
for $\boldsymbol{b}^{\prime}\in\mathcal{B}_{1}$. Moreover, let the cost of an
edge between $\boldsymbol{b}$ and its parent be $b_{1}/\mu$ and let
$\operatorname{cost}^{(i)}(\boldsymbol{b})$ denote the cost of going from
$\boldsymbol{b}$ to $\operatorname{parent_{\mathcal{B}_{1}}}(\boldsymbol{b})$.
Obviously, $\operatorname{cost}^{(i)}(\boldsymbol{b}^{\prime})=0$ for
$\boldsymbol{b}^{\prime}\in\mathcal{B}_{1}\cup\\{\delta\\}$.

Now, observe that the linear system of equations in (V-B) can be written as

$\displaystyle h^{(i)}(\boldsymbol{b}^{\prime})+\lambda$
$\displaystyle=\eta(l(\boldsymbol{b}^{\prime})-1)+E[h^{(i)}(\operatorname{parent}(\boldsymbol{b}^{\prime})\|\boldsymbol{V}^{Z})]$
$\displaystyle=\eta(l(\boldsymbol{b}^{\prime})-1)+E\bigg{[}\operatorname{cost}^{(i)}(\operatorname{parent}(\boldsymbol{b}^{\prime})\|\boldsymbol{V}^{Z})+h(\operatorname{parent_{\mathcal{B}_{1}}}(\operatorname{parent}(\boldsymbol{b}^{\prime})\|\boldsymbol{V}^{Z}))\bigg{]}.$
(27)

The policy iteration algorithm starts with
$s^{(0)}(\boldsymbol{b})=l(\boldsymbol{b})$. Therefore,
$h^{(0)}(\boldsymbol{b})=\operatorname{cost}^{(0)}(\boldsymbol{b})=\sum_{i<l(\boldsymbol{b})}b_{i}$
and one can also set
$\operatorname{parent_{\mathcal{B}_{1}}}(\boldsymbol{b})=v_{\min}$. We will
initialize the procedure accordingly so that the policy evaluation step makes
use of these quantities at the first iteration. We aim to update
$\operatorname{cost}^{(i)}(\boldsymbol{b})$ and
$\operatorname{parent_{\mathcal{B}_{1}}}(\boldsymbol{b})$ in the policy update
step. To this end, we need the temporary variable

$\operatorname{temp}^{(i)}(\boldsymbol{b})=\min_{s\leq
l(\boldsymbol{b})}C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},s).$ (28)

Then the condition for the policy update becomes
$C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},1)<\operatorname{temp}^{(i)}(\operatorname{parent}(\boldsymbol{b}))+b_{1}/\mu$;
and $\operatorname{temp}^{(i)}(\boldsymbol{b})$ will be updated accordingly.
Note that for $b\in\mathcal{V}$, $\operatorname{temp}^{(i)}(b)=\lambda^{(i)}$.
The modified version is given in Algorithm 3.

1

2

Input: $\eta$

Output: $J^{*}(\eta)$

3 Initialize  __

4 $K\leftarrow K(\eta)$;

5 $s^{(0)}(\boldsymbol{b})\leftarrow l(\boldsymbol{b})$;

6 $\mathcal{B}_{1}\leftarrow\\{v_{\min}\\}$;

7 Set $\delta$ as the root of $\mathcal{T}$ and add the children
$\\{b\|\boldsymbol{b}\\}_{b\in\mathcal{V}}$ for every buffer
$\boldsymbol{b}\in\mathcal{T}$ such that $l(\boldsymbol{b})<K$;

8 For all $\boldsymbol{b}$,
$\operatorname{cost}(\boldsymbol{b})\leftarrow\sum_{i<l(\boldsymbol{b})}b_{i}$
and $\operatorname{parent_{\mathcal{B}_{1}}}^{(0)}(\boldsymbol{b})\leftarrow
v_{\min}$;

9 $i\leftarrow 0$;

10

11repeat

/* Policy evaluation */

12 Find $\lambda^{(i)}$, $h^{(i)}(\boldsymbol{b}^{\prime})$,
$\boldsymbol{b}^{\prime}\in\mathcal{B}_{1}$ by solving (V-D);

13 for  _$\boldsymbol{b}\in\mathcal{T}\setminus\mathcal{B}_{1}$ with
$l(\boldsymbol{b})>1$_ do

14 $h^{(i)}(\boldsymbol{b})\leftarrow
h^{(i)}(\operatorname{parent}(\boldsymbol{b}))+b_{1}/\mu$ if
$\boldsymbol{b}\notin\mathcal{B}_{1}$;

15

/* Policy update */

16 $\mathcal{B}_{1}\leftarrow\\{v_{\min}\\}$;

17 for  _$b\in\\{v_{\min},\ldots,v_{\max}\\}$_ do

18 $\operatorname{temp}^{(i)}(b)\leftarrow\lambda^{(i)}$.

19 for  _$\boldsymbol{b}\in\mathcal{T}$ with $l(\boldsymbol{b})>1$_ do

20 if  _$l(\boldsymbol{b}) <K_{b_{1}}(\eta)$ and
$C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},1)<\operatorname{temp}^{(i)}(\operatorname{parent}(\boldsymbol{b}))+b_{1}/\mu$_
then

21 $s^{(i+1)}(\boldsymbol{b})\leftarrow 1$;

22 Add $\boldsymbol{b}$ to $\mathcal{B}_{1}$;

23 $\operatorname{temp}^{(i)}(\boldsymbol{b})\leftarrow
C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},1)$;

24 $\operatorname{cost}^{(i)}(\boldsymbol{b})\leftarrow 0$;

25
$\operatorname{parent_{\mathcal{B}_{1}}}^{(i)}(\boldsymbol{b})\leftarrow\boldsymbol{b}$;

26

27 else

28
$s^{(i+1)}(\boldsymbol{b})=s^{(i+1)}(\operatorname{parent}(\boldsymbol{b}))+1$;

29
$\operatorname{temp}^{(i)}(\boldsymbol{b}^{(i)})\leftarrow\operatorname{temp}^{(i)}(\operatorname{parent}(\boldsymbol{b}))+b_{1}/\mu$;

30
$\operatorname{cost}^{(i)}(\boldsymbol{b})\leftarrow\operatorname{cost}^{(i)}(\operatorname{parent}(\boldsymbol{b}))+b_{1}/\mu$;

31
$\operatorname{parent_{\mathcal{B}_{1}}}^{(i)}(\boldsymbol{b})\leftarrow\operatorname{parent_{\mathcal{B}_{1}}}^{(i)}(\operatorname{parent}(\boldsymbol{b}))$;

32

33

34 $i\leftarrow i+1$.

35until  _$\boldsymbol{s}^{(i+1)}=\boldsymbol{s}^{(i)}$_ ;

return $\lambda^{(i)}$

Algorithm 3 Efficient Policy Iteration v2($\eta$)

Recall that the number of elements in $\mathcal{T}$ is $O(|\mathcal{V}|^{K})$.
The complexity of a single iteration in Algorithm 3 is found as follows:

  * (i)

In the policy evaluation, the equation system (V-D) is constructed in
$O(|\mathcal{B}_{1}||\mathcal{V}|^{K})$ time, and solved in
$O(|\mathcal{B}_{1}|^{3})$.

  * (ii)

The policy update runs over all states. Furthermore, for each state
$\boldsymbol{b}$, calculation of $C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},1)$
also requires iterations over all states. Hence, it has
$O(|\mathcal{V}|^{2K})$ time complexity.

As we stated before, $|\mathcal{B}_{1}|$ is usually very small compared to
$|\mathcal{V}|^{K}$. The bottleneck then seems to be the policy update stage,
which requires $O(|\mathcal{V}|^{2K})$ steps. However, the policy update stage
can be further improved such that the complexity decreases to
$O(K|\mathcal{V}|^{K})$. This modification is given in Appendix -E.

Now that we have an efficient algorithm yielding $J^{*}(\eta)$, and with help
of Corollary 1, we should be able to find the boundary curve by varying
$\eta$. One may notice that initializing the trees and policies for every
$\eta$ can be avoided with a minor modification. The idea is as follows:
Choose a decreasing sequence $\eta_{1}>\eta_{2}>\ldots>\eta_{n}$ with
$\eta_{1}=\eta_{\max}=\tfrac{1}{\mu}(v_{\max}-v_{\min})$. Note that
$K(\eta_{1})=1$. Run the algorithm in the order of $\eta_{m}$’s and when
$K(\eta_{m+1})>K(\eta_{m})$, append new states to the tree $\mathcal{T}$. At
$(m+1)^{\text{th}}$ run, one can also start with the optimal policy found for
$\eta_{m}$. If $\eta_{1},\ldots,\eta_{n}$ are chosen densely, the boundary
curve can be well-approximated.

However, finding the boundary region everywhere would be optimistic. Theorem 3
implies that the necessary buffer size scales with $\frac{1}{\eta}$. This
suggests that even though the algorithm gives the almost exact curve, it is
impractical to do so. To overcome this difficulty, one may rely on approximate
dynamic programming algorithms; or resort to Monte Carlo estimations for the
policy evaluation [57].

Note that any straight line $D+\eta\Delta_{e}=J^{*}(\eta)$ in the
$(\Delta_{e},D)$ plane is a lower bound to the feasible region. Hence, any
family of straight lines obtained in such manner gives a lower bound in
general — and if we were able to run the algorithm for every $\eta>0$, this
would give the exact boundary curve. As before, let
$\eta_{1}>\eta_{2}>\ldots>\eta_{n}$ be a densely chosen sequence for which the
algorithm is run. Let $\Delta_{e}^{(n-1,n)}$ be the abscissa of the point
where the last two lines $D+\eta_{n-1}\Delta_{e}=J^{*}(\eta_{n-1})$ and
$D+\eta_{n}\Delta_{e}=J^{*}(\eta_{n})$ intersect. Then, one can see that the
supremum of the straight lines obtained for $\eta_{1},\ldots,\eta_{n}$
approximately gives the tradeoff curve for
$\Delta_{e}\leq\Delta_{e}^{(n-1,n)}$, while it gives a lower bound for
$\Delta_{e}>\Delta_{e}^{(n-1,n)}$. This is because all intersection points
that lie on the supremum, and the line segments connecting them are
achievable. This straight-line converse bound is referred as ‘PI converse’ in
the numerical examples.

We end this section with some numerical examples. We have calculated the
optimal policies with Algorithm 3, and unfortunately we have not observed any
simple structure for optimal policies for $|\mathcal{V}|=2$. We also evaluated
some simple policies described below and compared their performances with the
family of straight lines generated by Algorithm 3, referred as ‘PI’ in Figures
1 and 2. These simple policies are:

  * (S1)

Send the oldest important data within a maximum buffer size $K$.

  * (S2)

Send the newest important data within a maximum buffer size $K$.

  * (S3)

Send the newest important data that has arrived more than $K$ slots ago. If
there is no such data, send the oldest important one.

Each strategy above induces a finite-state Markov chain. Moreover, when $Z$ is
geometrically distributed, all the Markov chains induced by these strategies
have closed-form stationary distributions. $\Delta_{e}$ and $D$ pertaining to
these strategies will accordingly have closed-form expressions. We provide
these expressions in Appendix -F.

To compare these strategies, we also give a simple converse bound and observe
their approach towards this bound for large $\Delta_{e}$.

######  Lemma 5.

Suppose $V=v_{i}$ with probability $\alpha_{i}$. Let $j^{*}$ be the maximum
index such that $\sum_{i=j^{*}}^{|\mathcal{V}|}\alpha_{i}\geq\frac{1}{\mu}$.
Then for any $\Delta_{e}^{(\boldsymbol{S})}$, $D^{(\boldsymbol{S})}\geq
D_{\min}=\sum_{i=1}^{j^{*}-1}\alpha_{i}v_{i}+\big{(}\sum_{i=j^{*}}^{|\mathcal{V}|}\alpha_{i}-\frac{1}{\mu}\big{)}v_{j^{*}}$.

###### Proof Sketch.

The sender can send at most $\frac{1}{\mu}$ fraction of the data. We then
optimize over its selection of data to obtain the result. ∎

In the first numerical example, provided in Figure 1, $\Pr(Z=1)=0.2$ and
$\mathcal{V}=\\{1,20\\}$ with $\Pr(V=1)=0.7$. The blue family of straight
lines correspond to the lines $D+\eta\Delta_{e}=J^{*}(\eta)$, obtained for
different $\eta$ values. We could calculate until
$\eta=\frac{v_{\max}-v_{\min}}{17\mu}$, which indicates that we used a maximum
buffer size of 17. The region lying under this family of lines is
unachievable, and the supremum of this family gives the boundary of the
feasible region until the red solid line, which is the straight-line converse
bound described above. The curves corresponding to strategies S1, S2 and S3
are red dashed, green dashed and cyan dotted curves, and plotted for $K\leq
20$. The simple lower bound $D_{\min}=2.7$ is drawn as the solid black line.
One can see that S2 nearly coincides with PI. Note that we observe an
asymptotic behavior as the sender will never be able to allocate all of its
resources to send all of the important packets.

Figure 1: Comparison of the strategies for $\mathcal{V}=\\{1,20\\}$ and
$\Pr(V=1)=0.7$. $Z$ is taken as a Geometric random variable with success
probability $0.2$. (S2 almost coincides with PI)

The second numerical example differs from the first one with $\Pr(Z=1)=0.3$
and $\Pr(V=1)=0.8$. The simple strategies calculated for $K\leq 40$ together
with the policy iteration results obtained until a buffer size of 17 are
plotted in Figure 2. Here, $D_{\min}=0.7$ could be achieved in finite-age as
the sender can send all the important packets while keeping
$\sup_{i}E[(S_{i}-T_{i})^{2}]<\infty$.

Figure 2: Comparison of the strategies for $\mathcal{V}=\\{1,20\\}$ and
$\Pr(V=1)=0.8$. $Z$ is taken as a Geometric random variable with success
probability $0.3$.

##  VI Relation to an Erasure Channel with Feedback

We have observed that the model discussed primarily in this work is similar to
transmitting a stream of packets over an erasure channel with feedback. Recall
that the setting for transmission over discrete memoryless channels with
feedback requires the feedback for the data transmitted at time $t$ to be
revealed just after time $t$. For an erasure channel, the knowledge of an
erasure event indicator at time $t$, i.e., $\mathbbm{1}\\{X_{t}\text{ is
erased}\\}$ is sufficient for a perfect feedback.

We note that the main difference between our model and a feedback erasure
channel stems from the restriction that the feedback for data $t$ is revealed
_just after_ time $t$. If we assume that the sender knows about a possible
erasure event _just before_ time $t$; it may send the data $t$, or it may keep
data $t$ in its buffer for a later transmission. This relaxation exactly gives
the model we described with interspeaking times distributed according to a
geometric distribution, i.e., $\Pr(Z_{i}=z)=(1-p)p^{z-1}$ where $p$ is the
erasure probability for a discrete memoryless erasure channel. Also note that
one can model some erasure channels with memory by varying the distribution of
$Z$.

Consider a modification of our model which requires that the constituent
feedback is revealed just after the transmission. Now, we formalize the
modified setting. Just before time $t$, the sender commits to a packet with
timestamp $C_{t}\leq t$. Then, at time $t$, the committed packet $X_{C_{t}}$
is transmitted through the erasure channel. If the packet is erased, the
sender commits to packet with timestamp $C_{t+1}$ just before time $t+1$ —
which is not necessarily equal to $C_{t}$ — and the procedure is repeated
until the committed data is sent. If the committed data $X_{C_{t}}$ is sent
successfully, then $S_{i(t)+1}=C_{t}$ where $i(t)=\sup\\{i\geq
0\mathrel{\mathop{\mathchar 58\relax}}T_{i}<t\\}$; and the past of
$S_{i(t)+1}$ contributes to the distortion and cannot be modified later. The
age and distortion metrics are defined similar to the ones in Section IV.

Observe that for any sequence of commitments
$\\{C_{t}\\}_{t>0}=\mathrel{\mathop{\mathchar 58\relax}}\boldsymbol{C}$, there
must exist a selection procedure $\boldsymbol{S}$ in the original problem such
that

$D^{(\boldsymbol{C})}+\eta\Delta^{(\boldsymbol{C})}\geq
D^{(\boldsymbol{S})}+\eta\Delta^{(\boldsymbol{S})}.$ (29)

This is because in the original problem, selections are made with more
information — the erasure event is known beforehand. Conversely, for any
_stationary_ policy $\boldsymbol{S}$ in the original problem, there exists a
$\boldsymbol{C}$ in the latter problem where the sender commits to
$C_{t}=t+s(\boldsymbol{B}_{t})-l(\boldsymbol{B}_{t})$ where
$\boldsymbol{B}_{t}\mathrel{\mathop{\mathchar 58\relax}}=V_{S_{i(t)}+1}^{t}$.
As a consequence, the sender with no erasure information beforehand can also
attain the infimal value $J^{*}(\eta)$, as we know from Corollary 1 that the
optimal policy for the original problem is stationary. Together with the
inequality (29), we conclude that for both problems the tradeoff curve is the
same. In brief, whether erasures are revealed just before or after
transmissions do not change the tradeoff between age and distortion.

##  VII When Timestamps Become Significant

We have shown that the optimal value for an $\eta>0$ is attained with a
bounded buffer policy, say of $K$. In the model so far, packets contain the
timestamps as part of their headers. Consequently, there was no need to send
additional information to the receiver to tell it which packet among the $K$
packets in the buffer is being sent. If the packets do not have headers, this
additional information must be included. If $K$ is much smaller compared to
$|\mathcal{X}|$, this additional information is insignificant. In this
section, we treat the case of headerless packets when $K$ is comparable to
$|\mathcal{X}|$. We take binary $\mathcal{X}=\\{0,1\\}$ and
$\mathcal{V}=\\{1,v\\}$ with 1 being the important packet. We study the
setting described in Section IV but with the difference that the sender is
allowed to send $N$ bits at each speaking time. We assume that $Z$ is
distributed geometrically with success probability $p$, i.e. $\Pr(Z=1)=p$.

Consider the optimal policy to attain $J^{*}(\eta)$ in (13), which is of
bounded buffer size $K(\eta)$. Recall that at each speaking time, the sender
is able to send one packet. If $X$ is binary, then without any coding, the
optimal policy is feasible only if $N\geq 1+\lceil\log(K(\eta))\rceil$;
otherwise it is not able to describe the timestamps of selected data, e.g.,
for a state $\boldsymbol{b}$ with $l(\boldsymbol{b})=K(\eta)$, the timestamps
must be of length $\lceil\log(K(\eta))\rceil$ and the remaining one bit
corresponds to the data. However, it seems unreasonable to use almost all of
the $N$ bits for timestamp description. Can one come up with methods that do
not require explicit timing information to be sent and allocate more bits to
describe the data itself? The rest of this section elaborates on some possible
tradeoffs with this point of view.

###  VII-A Buffer Ignorant Strategies

Think of the following strategy: Always send the most recent $N=\log(K(\eta))$
bits. In this case, it is easy to see $\Delta_{e}=0$ and
$D=\mu_{V}(1-p)^{N}=\mu_{V}K(\eta)^{\log(1-p)}\simeq\mu_{V}\big{(}\frac{v-1}{\eta}\big{)}^{\log(1-p)}$,
where $\mu_{V}\mathrel{\mathop{\mathchar 58\relax}}=E[V]=(1-q)+vq$, and
$q=\Pr(V=v)$. We know that for the optimal policies described in Section V,
$D_{\min}$ given in Lemma 5 yields a lower bound for distortion. For a binary
$X$, and thus $V$, one can obtain

$D_{\min}=\begin{cases}1-p,&p\geq q\\\ \mu_{V}-pv&p<q\end{cases}.$ (30)

If
$\eta\geq\frac{1}{v-1}\big{(}\frac{\mu_{V}}{D_{\min}}\big{)}^{\frac{1}{\log(1-p)}}$
then $D\leq D_{\min}$, implying that the perfect timing information strategies
are beaten by the timing ignorant strategy described as sending the most
recent $N$ bits. In other words, one does better by sending $N$ bits of most
recent data instead of sending one bit together with its timestamp.

The above arguments motivate the following question: What are the limits of
these timing ignorant strategies? Note that both the sender and receiver know
the speaking times $T_{i}$. Suppose for a moment that the receiver knows the
selection times $S_{i}$ as well. With this assumption, the receiver has the
perfect knowledge of the buffer length at time $T_{i}$, which is
$T_{i}-S_{i-1}$. Hence, if the sender bases his strategies solely on its
buffer size, ignoring the buffer content, it does not have to include any
timing information and is able to use all its $N$-bit budget for sending data.
An example could be as follows: Suppose $N=3$. Then the sender could send
$1,3,5^{\text{th}}$ bits whenever the buffer size is $5$. Since the receiver
knows the buffer size and the sender’s strategy, it will know upon its
reception of $3$ bits that they correspond to $1,3,5^{\text{th}}$ bits.
Although we have previously coined the term ‘timing ignorant’ for such
strategies, a more suitable term could be ‘buffer ignorant’; as the sender
ignores what is in its buffer.

######  Remark 3.

One may notice that this procedure is a simple online compression algorithm
for the binary source $\\{X_{i}\\}$, with the restriction that the sender can
only send $N$ bits at each speaking time. Together with the unsophisticated
receiver that only constructs the $N$ bits it receives at each speaking time,
this scheme operates at $\Delta_{e}=0$ and $D=\mu_{V}(1-p)^{N}$.

Let us study the ‘buffer ignorant’ strategies further. Since the transmitter
does not use the buffer content and has to choose $N$ bits among them, a
simple choice could be in size-$N$ bit contiguous chunks. Adopting the
terminology from Section V, such strategies correspond to sending
$X_{S_{i}-N+1}^{S_{i}}$ at time $T_{i}$ from a buffer of size
$L_{i}\mathrel{\mathop{\mathchar 58\relax}}=T_{i}-S_{i-1}$. Nothing from the
past $X^{S_{i}}$ can be sent after time $T_{i}$ and therefore with similar
arguments we have previously done, one can formulate the problem of finding
optimal selection times as a MDP. The corresponding MDP will have the buffer
lengths as its states, which implies that we encounter another countable
state-space problem with its state-space being $\mathbb{Z}^{+}$. When the
buffer length is $l$, and the selection index is $s$, the one-step cost can be
written as

$g(l,s)=\mu_{V}p(s-N)^{+}+\eta(l-s).$ (31)

The corresponding Bellman equation is given by

$h(l)+\lambda=\min_{s\leq
l}\bigg{\\{}\mu_{V}p(s-N)^{+}+\eta(l-s)+E[h(l-s+Z)]\bigg{\\}}\vrule
width=0.0pt,depth=15.0pt$ (32)

for $l>1$ and with $h(1)=0$, where the buffer of length one is chosen as the
reference state. It is not difficult to see that this choice also implies
$h(l)=0$ for $l\leq N$, as the sender can immediately empty the buffer for
such states.

Similar to Property 2, we must have either $s^{*}(l)=N$ or
$s^{*}(l)=s^{*}(l-1)+1$ for the optimal policy. Therefore as $l$ increases,
the optimal policy tends to leave more bits at the end. Although this
observation suggests that the optimal policy may be attained with an unbounded
buffer, one can show that this is not the case. Similar coupling arguments as
we did in the proof of Theorem 3 lead to the conclusion that the optimal
policy cannot leave more than $\frac{N\mu_{V}}{\eta}$ bits at the end. Thus, a
simple policy iteration algorithm run for a sufficiently large state-space
also solves the Bellman equation for the infinite-state problem.

The optimal policies may not be simple-to-describe. However, when $Z$ is
geometrically distributed, the numerical simulations indicate that single-
threshold policies are optimal. These policies are characterized as

$s(l)=\min\\{\max\\{l-\tau,N\\},l\\}$ (33)

for some $\tau\geq 0$. In other words, the sender always keeps $\tau$ unsent
bits in the buffer if possible. We do not have an analytical proof for this
result, but it is not unreasonable to believe that these simple policies are
optimal because of the memorylessness property of $Z$. Recall that the states
of Markov chains incurred by such strategies are described with the buffer
length $l$. Denote the stationary probabilities as $\pi_{l}$. In this special
case, the stationary probabilities (and consequently the average age and
distortion) incurred by such strategies have closed-form expressions.

######  Corollary 2.

The $(\Delta_{e},D)$ curve attained by single-threshold strategies has a
parametric description that is available in closed-form. Let
$\bar{p}\mathrel{\mathop{\mathchar 58\relax}}=1-p$,
$S_{j}^{(0)}\mathrel{\mathop{\mathchar 58\relax}}=(1+jp)$ and
$S_{j}^{(n)}\mathrel{\mathop{\mathchar 58\relax}}=\sum_{k=0}^{j}S_{k}^{(n-1)}$
for $n\geq 1$. Also let $S_{j}^{(n)}=0$ for $j<0$. For $0\leq j\leq\tau-1$,
the stationary probabilities are given by

$\pi_{\tau-j}=\pi_{\tau+1}\frac{1+\sum_{k=0}^{\lceil\tau/N\rceil}(-1)^{k+1}S_{j-kN}^{(k)}p^{k}\bar{p}^{(k+1)(N-1)}}{\bar{p}^{j+1}}$
(34)

with

$\pi_{\tau+1}=\bigg{[}\sum_{j=0}^{\tau-1}\frac{1+\sum_{k=0}^{\lceil\tau/N\rceil}(-1)^{k+1}S_{j-kN}^{(k)}p^{k}\bar{p}^{(k+1)(N-1)}}{\bar{p}^{j+1}}+\frac{1}{p}\bigg{]}^{-1}.$
(35)

and $\pi_{\tau+1+j}=\bar{p}^{j}\pi_{\tau+1}$ for $j>0$. The $(\Delta_{e},D)$
curve therefore has a parametric description $(\Delta_{e}(\tau),D(\tau))$
given by

$\Delta_{e}(\tau)=\sum_{j=1}^{\tau-1}j\pi_{N+j}+\frac{\tau\pi_{\tau+1}\bar{p}^{N-1}}{p}.$
(36)

and

$D(\tau)=\frac{\mu_{V}\pi_{\tau+1}\bar{p}^{N}}{p^{2}}.$ (37)

######  Remark 4.

If the bits sent are equal in terms of their importance, i.e., $v_{1}=v_{2}$,
then buffer ignorant strategies are optimal among the strategies without
timestamp coding. This is because strategies as such already assume that $1$
and $0$ are of equal importance and there is no need to indicate which bit is
more important. Consequently, for the binary erasure channel, i.e., $N=1$; the
only optimal buffer ignorant strategy is to send the last bit if the bits are
equally important.

Until now, we have only considered integer $N$. However, the erasure channel
between the sender and receiver could admit $K$ inputs, where $K$ is not
necessarily a power of $2$. This would imply a non-integer $N=\log K$.
Studying such $N$ requires strategies with some knowledge of the buffer
content and possibly requires some coding. We will elaborate on how to handle
these cases in the next section.

###  VII-B Revealing Partial Buffer Content

The previous section was devoted to buffer ignorant strategies. Now, we allow
some knowledge of the buffer content to improve buffer ignorant strategies and
also to cover the case of a non-integer $N$.

Let us first show the improvement by coding over the buffer ignorant
strategies for an integer $N$. Take the single-threshold strategy $s(l)$
described in (33) together with the threshold $\tau$. Consider the state
$l>\tau+N$, where the dictated action is to keep $\tau$ bits for future and
send $N$ of the remaining bits. Then $l-\tau-N$ bits will never be sent and
hence the distortion penalty will be $\mu_{V}(l-\tau-N)$. We aim to show that
the distortion penalty can be decreased with some coding while preserving or
decreasing the age penalty.

To that end, consider an alternative way of describing the buffer ignorant
strategy above: the sender sends the first $N$ bits of the sequence
$x_{l-\tau},x_{l-\tau-1},\ldots,x_{1}$ regardless of the content. It is
therefore reasonable to think that a parser with a dictionary of size $2^{N}$
which sends the identity of the first parsed word in the same sequence could
result in an improvement. One could resort to some variable-to-fixed length
source coding techniques, such as Tunstall coding. Tunstall coding is known to
maximize the expected number of bits parsed among prefix-free and variable-to-
fixed length dictionaries. Let $E[L_{\text{Tun}}]$ be the expected number of
bits parsed. With Tunstall coding, the expected number of unsent bits will be
$l-\tau-E[L_{\text{Tun}}]$ and since $E[L_{\text{Tun}}]\geq N$, the distortion
cost decreases. Thus, Tunstall algorithm improves the buffer ignorant
strategies. Also note that for non-integer $N$, Tunstall algorithm can be used
to determine parsing methods.

Figure 3: For the same setting in Figure 1, the curves pertaining to optimal
buffer ignorant strategies (BI, colored in red) together with their improved
versions with Tunstall coding (BIT, colored in cyan) are plotted for the same
source in Figure 1. The curves corresponding to $N=3$ are dashed, and the
curves corresponding to $N=6$ are dotted.

We end this section by presenting some numerical results that illustrate the
improvement with buffer ignorant strategies and Tunstall coding. We use the
same source and interspeaking time distribution as in Figure 1, i.e.,
$\mathcal{V}=\\{1,20\\}$ with $\Pr(V=1)=0.7$ and $\Pr(Z=1)=0.2$. Recall that
we were able to find the optimal policies with Algorithm 3 up to a buffer size
of 17. This suggests that the sender describes the timing information with
$\lceil\log 17\rceil=5$ bits and with an additional bit to describe the
content, which implies that the left end of the PI converse line segment can
be attained with sending $N=6$ bits — note that this converse bound is valid
only for strategies of Section V, and not for buffer ignorant strategies. As
we suggested, the timing information can be sacrificed to allocate the whole
budget for the data description in an attempt to improve the performance. This
improvement is evident even for $N=3$, where the optimal buffer ignorant
strategy (BI, $N=3$) and its improved version with Tunstall coding (BIT,
$N=3$) perform better than the optimal PI curve as seen in Figure 3. For
$N=6$, there is drastical improvement and one can approach zero distortion
with finite age — see BI and BIT, $N=6$ in Figure 3.

###  VII-C Discussion about other possible coding strategies

The buffer ignorant strategies discussed in the previous section only depend
on the buffer size and we have shown that these strategies can be improved by
revealing some buffer content. One can argue that these coding strategies
might be far from optimal, as they use partial knowledge. The sender could
base its strategies on all past speaking times and the past buffer content.
Calculating the tightest $(\Delta_{e},D)$ curve corresponding to this broad
class of strategies seems to be formidably complex. Even with the sole
knowledge of the current buffer content, the problem becomes difficult. We
illustrate this with an example. Suppose the current buffer content is
$\boldsymbol{b}=[v,v,1,1,v,v,v,1,1,1,v,v,v,1]$ and the sender could only send
$N=3$ bits. The single-threshold strategy with $\tau=4$ will choose the index
$s(\boldsymbol{b})=10$ and send $(1,1,1)$, which does not contain any
important data. If the index $s=13$ is chosen, $(v,v,v)$ will be sent and this
might be a better strategy; however, the description of $s=13$ must be somehow
included in the $N=3$ bits and all three important data might not be sent.
Encoding both the data and their indices into a fixed number of bits
complicates the possible actions and thus the problem appears to be very hard.
We also observe an interesting tradeoff in this situation. In our MDP,
sacrificing perfect state information results in a smaller policy space with
policies of lower penalties, i.e., if $k$ bits are allocated for timestamp
description, $N-k$ information bits can be sent and when $k$ decreases, the
number of possible actions also decreases but their one step costs can
possibly be smaller.

##  VIII Discussion

In this work, we have studied a discrete-time model where the sender is only
allowed to speak at time slots assigned by an external scheduler. In the
absence of a distortion measure, it is clear that the optimal strategy is to
send the freshest packet in the buffer at each speaking time as this will
minimize the age. However, if this freshest packet has low importance, it may
be beneficial to send a packet of higher importance instead, sacrificing
freshness for lowering distortion. Hence, it is immediate that a tradeoff
between the age and the distortion exists. It turns out that the optimal
tradeoff can be attained with bounded buffer policies, and these policies can
be found with numerical methods. Unfortunately, they turn out to be not
simple-to-describe.

We observed that the usual policy iteration methods were inefficient for our
specific problem, and we devised an algorithm based on appropriate data
structures and problem-specific simplifications. The new algorithm performs
significantly better — the time complexity decreases from
$O(|\mathcal{V}|^{3K})$ to $O(K|\mathcal{V}|^{K})$, where $K$ is the exact
buffer size needed for attaining the optimal tradeoff. However, at the high-
age regime, $K$ is large and in turn, the optimal tradeoff cannot be computed.
One could try to find simple-to-describe policies that are not too far from
the optimal tradeoff at this regime.

The main results of this work also apply when the process of importance levels
$\\{V_{i}\\}_{i\geq 0}$ is an ergodic Markov chain — one can verify the
conditions (i) and (ii) with the same state and action spaces defined in
Section V-A. Consequently, the necessary buffer size will be the same and one
is able to find the optimal curve as in the i.i.d. case.

The problem we formulated in the first place turns out to be closely related
to a problem of transmitting packets over an erasure channel with perfect
feedback. The difference is that in our setting, erasure events are revealed
before transmissions. Nevertheless, we have shown that for both problems, the
optimal tradeoff is the same.

Until Section VII, we assumed that the timing information is contained in the
header of a packet, which is much smaller in size compared to the payload. In
Section VII, we studied the case where the packets need not contain perfect
timing information, and consist of at most $N$ bits. As a consequence, if one
decides to sacrifice age for lowering distortion, some additional information
must be included in the $N$ bits in order to tell the receiver to which time
the information bits pertain. Therefore, if the sender decides not to send the
freshest data, it not only sacrifices age but may also decrease the amount of
information bits to be sent. We have studied some simple policies, called
buffer ignorant, where the sender ignores what is in the buffer and allocates
all its $N$-bit budget for the information bits. When the timing information
dominates the payload, buffer ignorant policies improve drastically over the
optimal policies found in Section V, which include the timing information.
Later, we have shown that buffer ignorant policies can be further improved by
revealing some buffer content and using variable-to-fixed length coding.
However, it seems very challenging to find the optimal tradeoff when any
strategy that sends $N$ bits at a time is allowed.

## References

  * [1] Y. İnan, R. Inovan, and E. Telatar, “Optimal policies for age and distortion in a discrete-time model,” in _2021 IEEE Information Theory Workshop (ITW)_ , 2021, pp. 1–6.
  * [2] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in _2012 Proceedings IEEE INFOCOM_ , 2012, pp. 2731–2735.
  * [3] S. Kaul, M. Gruteser, V. Rai, and J. Kenney, “Minimizing age of information in vehicular networks,” in _2011 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks_ , 2011, pp. 350–358.
  * [4] S. Kaul, R. Yates, and M. Gruteser, “On piggybacking in vehicular networks,” in _2011 IEEE Global Telecommunications Conference - GLOBECOM 2011_ , 2011, pp. 1–5.
  * [5] J. P. Champati, H. Al-Zubaidy, and J. Gross, “Statistical guarantee optimization for age of information for the d/g/1 queue,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2018, pp. 130–135.
  * [6] A. Soysal and S. Ulukus, “Age of information in g/g/1/1 systems,” in _2019 53rd Asilomar Conference on Signals, Systems, and Computers_ , 2019, pp. 2022–2027.
  * [7] Y. Inoue, H. Masuyama, T. Takine, and T. Tanaka, “A general formula for the stationary distribution of the age of information and its application to single-server queues,” _IEEE Transactions on Information Theory_ , vol. 65, no. 12, pp. 8305–8324, 2019.
  * [8] C. Kam, S. Kompella, and A. Ephremides, “Age of information under random updates,” in _2013 IEEE International Symposium on Information Theory_ , 2013, pp. 66–70.
  * [9] R. D. Yates and S. Kaul, “Real-time status updating: Multiple sources,” in _2012 IEEE International Symposium on Information Theory Proceedings_ , 2012, pp. 2666–2670.
  * [10] M. Moltafet, M. Leinonen, and M. Codreanu, “On the age of information in multi-source queueing models,” _IEEE Transactions on Communications_ , vol. 68, no. 8, pp. 5003–5017, 2020.
  * [11] E. Najm and E. Telatar, “Status updates in a multi-stream m/g/1/1 preemptive queue,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2018, pp. 124–129.
  * [12] V. Tripathi and S. Moharir, “Age of information in multi-source systems,” in _GLOBECOM 2017 - 2017 IEEE Global Communications Conference_ , 2017, pp. 1–6.
  * [13] S. K. Kaul, R. D. Yates, and M. Gruteser, “Status updates through queues,” in _2012 46th Annual Conference on Information Sciences and Systems (CISS)_ , 2012, pp. 1–6.
  * [14] M. Costa, M. Codreanu, and A. Ephremides, “On the age of information in status update systems with packet management,” _IEEE Transactions on Information Theory_ , vol. 62, no. 4, pp. 1897–1910, 2016.
  * [15] R. D. Yates, “The age of gossip in networks,” in _2021 IEEE International Symposium on Information Theory (ISIT)_ , 2021, pp. 2984–2989.
  * [16] ——, “Age of information in a network of preemptive servers,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2018, pp. 118–123.
  * [17] R. Nasser, I. Issa, and I. Abou-Faycal, “Age distribution in arbitrary preemptive memoryless networks,” in _2022 IEEE International Symposium on Information Theory (ISIT) (ISIT 2022)_ , Espoo, Finland, Jun. 2022.
  * [18] C. Kam, S. Kompella, G. D. Nguyen, J. E. Wieselthier, and A. Ephremides, “Age of information with a packet deadline,” in _2016 IEEE International Symposium on Information Theory (ISIT)_ , 2016, pp. 2564–2568.
  * [19] X. Wu, J. Yang, and J. Wu, “Optimal status update for age of information minimization with an energy harvesting source,” _IEEE Transactions on Green Communications and Networking_ , vol. 2, no. 1, pp. 193–204, 2018.
  * [20] R. D. Yates, “Lazy is timely: Status updates by an energy harvesting source,” in _2015 IEEE International Symposium on Information Theory (ISIT)_ , 2015, pp. 3008–3012.
  * [21] S. Farazi, A. G. Klein, and D. R. Brown, “Age of information in energy harvesting status update systems: When to preempt in service?” in _2018 IEEE International Symposium on Information Theory (ISIT)_ , 2018, pp. 2436–2440.
  * [22] B. T. Bacinoglu, E. T. Ceran, and E. Uysal-Biyikoglu, “Age of information under energy replenishment constraints,” in _2015 Information Theory and Applications Workshop (ITA)_ , 2015, pp. 25–31.
  * [23] A. Arafa and S. Ulukus, “Age-minimal transmission in energy harvesting two-hop networks,” in _GLOBECOM 2017 - 2017 IEEE Global Communications Conference_ , 2017, pp. 1–6.
  * [24] ——, “Timely updates in energy harvesting two-hop networks: Offline and online policies,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 8, pp. 4017–4030, 2019.
  * [25] ——, “Age minimization in energy harvesting communications: Energy-controlled delays,” in _2017 51st Asilomar Conference on Signals, Systems, and Computers_ , 2017, pp. 1801–1805.
  * [26] B. T. Bacinoglu and E. Uysal-Biyikoglu, “Scheduling status updates to minimize age of information with an energy harvesting sensor,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 1122–1126.
  * [27] S. Feng and J. Yang, “Minimizing age of information for an energy harvesting source with updating failures,” in _2018 IEEE International Symposium on Information Theory (ISIT)_ , 2018, pp. 2431–2435.
  * [28] ——, “Optimal status updating for an energy harvesting sensor with a noisy channel,” in _IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2018, pp. 348–353.
  * [29] A. Arafa, J. Yang, and S. Ulukus, “Age-minimal online policies for energy harvesting sensors with random battery recharges,” in _2018 IEEE International Conference on Communications (ICC)_ , 2018, pp. 1–6.
  * [30] B. T. Bacinoglu, Y. Sun, E. Uysal–Bivikoglu, and V. Mutlu, “Achieving the age-energy tradeoff with a finite-battery energy harvesting source,” in _2018 IEEE International Symposium on Information Theory (ISIT)_ , 2018, pp. 876–880.
  * [31] Y. Dong, P. Fan, and K. B. Letaief, “Energy harvesting powered sensing in iot: Timeliness versus distortion,” _IEEE Internet of Things Journal_ , vol. 7, no. 11, pp. 10 897–10 911, 2020.
  * [32] E. T. Ceran, D. Gündüz, and A. György, “Average age of information with hybrid arq under a resource constraint,” in _2018 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2018, pp. 1–6.
  * [33] B. Wang, S. Feng, and J. Yang, “To skip or to switch? minimizing age of information under link capacity constraint,” in _2018 IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_ , 2018, pp. 1–5.
  * [34] Y. Inan and E. Telatar, “Age-Optimal causal labeling of memoryless processes,” in _2022 IEEE International Symposium on Information Theory (ISIT) (ISIT 2022)_ , Espoo, Finland, Jun. 2022.
  * [35] R. D. Yates, Y. Sun, D. R. Brown III, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” 2020.
  * [36] A. Kosta, N. Pappas, and V. Angelakis, _Age of Information: A New Concept, Metric, and Tool_ , 2017.
  * [37] K. Chen and L. Huang, “Age-of-information in the presence of error,” in _2016 IEEE International Symposium on Information Theory (ISIT)_ , 2016, pp. 2579–2583.
  * [38] S. Feng and J. Yang, “Age-optimal transmission of rateless codes in an erasure channel,” in _ICC 2019 - 2019 IEEE International Conference on Communications (ICC)_ , 2019, pp. 1–6.
  * [39] A. Baknina and S. Ulukus, “Coded status updates in an energy harvesting erasure channel,” in _2018 52nd Annual Conference on Information Sciences and Systems (CISS)_ , 2018, pp. 1–6.
  * [40] S. Feng and J. Yang, “Age of information minimization for an energy harvesting source with updating erasures: Without and with feedback,” _IEEE Transactions on Communications_ , vol. 69, no. 8, pp. 5091–5105, 2021.
  * [41] A. Arafa, J. Yang, S. Ulukus, and H. V. Poor, “Using erasure feedback for online timely updating with an energy harvesting sensor,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 607–611.
  * [42] P. Parag, A. Taghavi, and J.-F. Chamberland, “On real-time status updates over symbol erasure channels,” in _2017 IEEE Wireless Communications and Networking Conference (WCNC)_ , 2017, pp. 1–6.
  * [43] R. D. Yates, E. Najm, E. Soljanin, and J. Zhong, “Timely updates over an erasure channel,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 316–320.
  * [44] H. Sac, T. Bacinoglu, E. Uysal-Biyikoglu, and G. Durisi, “Age-optimal channel coding blocklength for an m/g/1 queue with harq,” in _2018 IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_ , 2018, pp. 1–5.
  * [45] E. Najm, R. Yates, and E. Soljanin, “Status updates through m/g/1/1 queues with harq,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 131–135.
  * [46] E. Najm, E. Telatar, and R. Nasser, “Optimal age over erasure channels,” _IEEE Transactions on Information Theory_ , pp. 1–1, 2022.
  * [47] T. Soleymani, J. S. Baras, and K. H. Johansson, “Stochastic control with stale information–part i: Fully observable systems,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_ , 2019, pp. 4178–4182.
  * [48] A. Mitra, J. A. Richards, S. Bagchi, and S. Sundaram, “Finite-time distributed state estimation over time-varying graphs: Exploiting the age-of-information,” in _2019 American Control Conference (ACC)_ , 2019, pp. 4006–4011.
  * [49] Y. Sun, Y. Polyanskiy, and E. Uysal, “Sampling of the wiener process for remote estimation over a channel with random delay,” _IEEE Transactions on Information Theory_ , vol. 66, no. 2, pp. 1118–1135, 2020.
  * [50] T. Z. Ornee and Y. Sun, “Sampling and remote estimation for the ornstein-uhlenbeck process through queues: Age of information and beyond,” _IEEE/ACM Transactions on Networking_ , vol. 29, no. 5, pp. 1962–1975, 2021\.
  * [51] A. Kosta, N. Pappas, A. Ephremides, and V. Angelakis, “Age and value of information: Non-linear age case,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 326–330.
  * [52] ——, “The cost of delay in status updates and their value: Non-linear ageing,” _IEEE Transactions on Communications_ , vol. 68, no. 8, pp. 4905–4918, 2020.
  * [53] S. K. Kaul and R. D. Yates, “Age of information: Updates with priority,” in _2018 IEEE International Symposium on Information Theory (ISIT)_ , 2018, pp. 2644–2648.
  * [54] E. Najm, R. Nasser, and E. Telatar, “Content based status updates,” _IEEE Transactions on Information Theory_ , vol. 66, no. 6, pp. 3846–3863, 2020.
  * [55] M. Bastopcu and S. Ulukus, “Age of information for updates with distortion,” in _2019 IEEE Information Theory Workshop (ITW)_ , 2019, pp. 1–5.
  * [56] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,” _IEEE Transactions on Information Theory_ , vol. 63, no. 11, pp. 7492–7508, 2017.
  * [57] D. P. Bertsekas, _Dynamic Programming and Optimal Control, Vol. II_ , 3rd ed. Athena Scientific, 2007.
  * [58] S. Ross, _Stochastic processes_ , ser. Wiley series in probability and statistics: Probability and statistics. Wiley, 1996.
  * [59] D. Williams, _Probability with Martingales_ , ser. Cambridge mathematical textbooks. Cambridge University Press, 1991\.
  * [60] S. Resnick, _A Probability Path_ , ser. Modern Birkhäuser Classics. Birkhäuser Boston, 2003.

###  -A Proofs of Theorems 1 and 2

Define $W_{j}\mathrel{\mathop{\mathchar 58\relax}}=T_{j}-S_{j}$ for the rest
of the proof and denote ‘almost surely’ by _a.s._.

####  -A1 Proof of Theorem 1

We first prove a convergence result in Lemma 6 below, from which the equation
(8) follows as a corollary.

######  Lemma 6.

$\frac{1}{i}\sum_{j=1}^{i}W_{j}(Z_{j+1}-\mu)\to 0$ a.s. if
$\sup_{j}E[W_{j}^{2}]<\infty$.

###### Proof.

We use the result that if $\sum_{i}b_{i}/i$ converges, then
$\frac{1}{i}\sum_{j\leq i}b_{j}\to 0$ — known as Kronecker’s Lemma [59].
Therefore, it is sufficient to show $\sum_{i}W_{i}(Z_{i+1}-\mu)/i$ converges
_a.s._. We now show that $M_{n}\mathrel{\mathop{\mathchar
58\relax}}=\sum_{i=2}^{n}W_{i-1}(Z_{i}-\mu)/{(i-1)}$,
$M_{1}\mathrel{\mathop{\mathchar 58\relax}}=0$ is a martingale with respect to
the filtration $\mathcal{F}_{n}\mathrel{\mathop{\mathchar
58\relax}}=\sigma(Z_{1},\ldots,Z_{n},\boldsymbol{X}_{1}^{T_{n}})$.

Observe that
$E[M_{n}|\mathcal{F}_{n-1}]=M_{n-1}+E[W_{n-1}(Z_{n}-\mu)|\mathcal{F}_{n-1}]/(n-1)=M_{n-1}$
as $W_{n-1}$ is $\mathcal{F}_{n-1}$-measurable and $Z_{n}$ is independent of
$\mathcal{F}_{n-1}$ with $E[Z_{n}]=\mu$. Since $M_{n}$ consists of
uncorrelated increments, one can write

$E[M_{n}^{2}]=\sum_{i=2}^{n}\frac{E[W_{i-1}^{2}]\text{Var}(Z)}{(i-1)^{2}}.$
(38)

Note that we assumed $E[Z^{2}]<\infty$, hence $\text{Var}(Z)<\infty$.
Moreover, since $\sup_{j}E[W_{j}^{2}]<\infty$,
$\sum_{i}\frac{E[W_{i}^{2}]}{i^{2}}<\infty$. As a consequence,
$\sup_{n}E[M_{n}^{2}]<\infty$ and the _a.s._ convergence of $M_{n}$ follows
from the martingale convergence theorem. ∎

Now we prove (9) and complete the proof of Theorem 1. Define

$Y_{j}=\begin{cases}X_{j},&j\in\boldsymbol{S}\\\
\operatorname{?},&\text{else.}\end{cases}$ (39)

Given $t$, define $i=i(t)\mathrel{\mathop{\mathchar 58\relax}}=\sup\\{j\geq
0\mathrel{\mathop{\mathchar 58\relax}}T_{j}\leq t\\}$. Observe that for $j\leq
i$, $Y_{j}(t)=Y_{j}$. Thus,

$D_{t}^{(\boldsymbol{S})}=\frac{1}{t}\sum_{j\leq
S_{i}}d(X_{j},Y_{j})+\frac{1}{t}\sum_{j=S_{i}+1}^{t}d(X_{j},Y_{j}(t)).$ (40)

Upper bound $D_{t}^{(\boldsymbol{S})}$ as

$\begin{split}D_{t}^{(\boldsymbol{S})}&\leq\frac{1}{t}\sum_{j\leq
S_{i}}d(X_{j},Y_{j})+\frac{1}{t}(T_{i+1}-S_{i})v_{\max}\\\
&\leq\frac{1}{T_{i}}\sum_{j\leq
S_{i}}d(X_{j},Y_{j})+\frac{1}{t}(Z_{i+1}+W_{i})v_{\max}.\end{split}$ (41)

Since $\sup_{j}E[W_{j}^{2}]<\infty$, $W_{i}$ is _a.s._ finite for all $i$ and
hence $Z_{i+1}+W_{i}$ is _a.s._ finite. Thus
$\frac{1}{t}(Z_{i+1}+W_{i})v_{\max}\to 0$ _a.s._ Then, we obtain

$\limsup_{t\to\infty}{D_{t}^{(\boldsymbol{S})}}\leq\limsup_{i\to\infty}\frac{1}{T_{i}}\sum_{j\leq
S_{i}}d(X_{j},Y_{j}).$ (42)

Now, we lower bound $D_{t}^{(\boldsymbol{S})}$ as

$\begin{split}D_{t}^{(\boldsymbol{S})}\geq\frac{1}{t}\sum_{j\leq
S_{i}}d(X_{j},Y_{j})&\geq\frac{1}{T_{i+1}}\sum_{j\leq
S_{i}}d(X_{j},Y_{j})=\frac{1}{T_{i}+Z_{i+1}}\sum_{j\leq
S_{i}}d(X_{j},Y_{j})\end{split}$ (43)

and take $\limsup$ on both sides to obtain

$\limsup_{t\to\infty}{D_{t}^{(\boldsymbol{S})}}\geq\limsup_{i\to\infty}\frac{1}{T_{i}+Z_{i+1}}\sum_{j\leq
S_{i}}d(X_{j},Y_{j}).$ (44)

Finally, observe that $\frac{T_{i}}{i}\to\mu$ and $\frac{Z_{i+1}}{i}\to 0$
_a.s._ Hence,

$\begin{split}\limsup_{t\to\infty}{D_{t}^{(\boldsymbol{S})}}&=\frac{1}{\mu}\limsup_{i\to\infty}\frac{1}{i}\sum_{j\leq
S_{i}}d(X_{j},Y_{j})\\\
&=\frac{1}{\mu}\limsup_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}D(\boldsymbol{V}^{T_{j}},S_{j},S_{j-1}),\end{split}$
(45)

which ends the proof of Theorem 1.

####  -A2 Proof of Theorem 2

Since $\sup_{j}E[W_{j}^{2}]<\infty$, it follows that
$\sup_{i}E[(\frac{1}{i}\sum_{j=1}^{i}W_{j})^{2}]<\infty$. Thus, the family
$(\frac{1}{i}\sum_{j=1}^{i}W_{j})_{i\in\mathbb{N}}$ is uniformly integrable
[59, Chapter 13]. One can then use the reverse Fatou’s lemma for uniformly
integrable families [60] to obtain

$\Delta_{e}^{(\boldsymbol{S})}=E\bigg{[}\limsup_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}W_{j}\bigg{]}\geq\limsup_{i\to\infty}E\bigg{[}\frac{1}{i}\sum_{j=1}^{i}W_{j}\bigg{]}.$
(46)

A similar reasoning for $D^{(\boldsymbol{S})}$ follows from the fact that each
$D(\boldsymbol{V}^{T_{j}},S_{j},S_{j-1})$ is smaller than
$v_{\max}(W_{j-1}+Z_{j})$. Therefore,
$\\{D(\boldsymbol{V}^{T_{i}},S_{i},S_{i-1})\\}_{i\geq 0}$ is a uniformly
integrable family, and one proceeds in a similar way as above to obtain

$D^{(\boldsymbol{S})}\geq\limsup_{i\to\infty}\frac{1}{\mu}E\bigg{[}\frac{1}{i}\sum_{j=1}^{i}D(\boldsymbol{V}^{T_{j}},S_{j},S_{j-1})\bigg{]}.$
(47)

As $\limsup_{n}a_{n}+\limsup_{n}b_{n}\geq\limsup_{n}(a_{n}+b_{n})$, the
inequality $J(\eta)^{(\boldsymbol{S})}\leq
D^{(\boldsymbol{S})}+\eta\Delta_{e}^{(\boldsymbol{S})}$ holds. This completes
the proof.

###  -B Proof of Lemma 1

We construct $\\{\tilde{S}_{i}\\}$ iteratively as follows:

$\tilde{S}_{i}=\begin{cases}S_{i},&i<i_{0}\\\
\min\\{s>S_{i_{0}}\mathrel{\mathop{\mathchar 58\relax}}V_{s}>v_{\min}\\}\wedge
T_{i_{0}},&i=i_{0}\\\ \tilde{S}_{i-1}+1,&S_{i}\leq\tilde{S}_{i-1},\ i>i_{0}\\\
S_{i},&S_{i}>\tilde{S}_{i-1},\ i>i_{0}\end{cases}.$ (48)

Verbally, at time $i_{0}$, $\tilde{\boldsymbol{S}}$ takes the next packet
whose importance value is more than $v_{\min}$ (if no such packet, selects the
freshest one) and then selects consecutive packets irrespective of their
importance values while it cannot choose anything that $\boldsymbol{S}$
chooses. If $\tilde{\boldsymbol{S}}$ can choose the packet that
$\boldsymbol{S}$ chooses at some time instant after $i_{0}$, it does so
forever. Since $\tilde{S}_{j}\geq S_{j}$ for all $j$, we have for all $i$

$\frac{1}{i}\sum_{j=1}^{i}(T_{j}-\tilde{S}_{j})\leq\frac{1}{i}\sum_{j=1}^{i}(T_{j}-S_{j}),$
(49)

and consequently
$\Delta_{e}^{(\tilde{\boldsymbol{S}})}\leq\Delta_{e}^{(\boldsymbol{S})}$. For
$i>i_{0}$, if $S_{i}=\tilde{S}_{i}$, then

$\frac{1}{i}\sum_{j=1}^{i}D(\boldsymbol{V}^{T_{j}},\tilde{S}_{j-1},\tilde{S}_{j})\leq\frac{1}{i}\sum_{j=1}^{i}D(\boldsymbol{V}^{T_{j}},S_{j-1},S_{j}).$
(50)

This is because $V_{s}\leq V_{\tilde{s}}$ for every
$s\in\\{S_{1},\ldots,S_{i}\\}$ and
$\tilde{s}\in\\{\tilde{S}_{1},\ldots,\tilde{S}_{i}\\}$. If
$S_{i}<\tilde{S}_{i}$ at $i>i_{0}$, then $\tilde{S}$ must have skipped at most
$\tilde{S}_{i_{0}}-S_{i_{0}}$ packets with minimum importance. Then we have

$\begin{split}&\frac{1}{i}\sum_{j=1}^{i}D(\boldsymbol{V}^{T_{j}},\tilde{S}_{j-1},\tilde{S}_{j})\leq\frac{1}{i}\sum_{j=1}^{i}D(\boldsymbol{V}^{T_{j}},S_{j-1},S_{j})+\frac{1}{i}v_{\min}(\tilde{S}_{i_{0}}-S_{i_{0}})\leq\frac{1}{i}\sum_{j=1}^{i}D(\boldsymbol{V}^{T_{j}},S_{j-1},S_{j})+\frac{1}{i}v_{\min}(T_{i_{0}}-S_{i_{0}}).\end{split}$
(51)

Since $T_{i_{0}}-S_{i_{0}}$ is almost surely finite,
$\frac{1}{i}(T_{i_{0}}-S_{i_{0}})\to 0$. Therefore

$\limsup_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}D(\boldsymbol{V}^{T_{j}},\tilde{S}_{j-1},\tilde{S}_{j})\leq\limsup_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}D(\boldsymbol{V}^{T_{j}},S_{j-1},S_{j})$
(52)

and consequently $D^{(\tilde{\boldsymbol{S}})}\leq D^{(\boldsymbol{S})}$.

###  -C Proof of Property 1

In the following proofs, $g(\boldsymbol{b},s)$ refers to the one step costs of
the MDP and $E_{\boldsymbol{b},s}[h(\boldsymbol{B}^{\prime})]$ refers to the
expected relative value of the next state accessed under the action $s$, i.e.,
$g(\boldsymbol{b},s)=\sum_{k=1}^{s-1}b_{k}+\eta(l(\boldsymbol{b})-s)$ and
$E_{\boldsymbol{b},s}[h(\boldsymbol{B}^{\prime})]=E[h(\boldsymbol{b}_{\geq
s+1}\|\boldsymbol{V}^{Z})]$.

  * (i)

Let $\boldsymbol{q}\mathrel{\mathop{\mathchar
58\relax}}=\boldsymbol{b}\|\boldsymbol{b}^{\prime}$. Suppose
$s^{*}(\boldsymbol{q})\neq l(\boldsymbol{b})+s^{*}(\boldsymbol{b}^{\prime})$
and $s^{*}(\boldsymbol{q})>l(\boldsymbol{b})$. Then by the optimality
condition, $s^{*}(\boldsymbol{q})=\arg\min_{s\leq
l(\boldsymbol{q})}g(\boldsymbol{q},s)+E_{\boldsymbol{q},s}[h(\boldsymbol{B}^{\prime})]=l(\boldsymbol{b})+\arg\min_{s\leq
l(\boldsymbol{b}^{\prime})}g(\boldsymbol{b}^{\prime},s)+E_{\boldsymbol{b}^{\prime},s}[h(\boldsymbol{B}^{\prime})]=l(\boldsymbol{b})+s^{*}(\boldsymbol{b}^{\prime})$,
which contradicts the statement. Therefore, if
$s^{*}(\boldsymbol{q})>l(\boldsymbol{b})$, then
$s^{*}(\boldsymbol{q})=l(\boldsymbol{b})+s^{*}(\boldsymbol{b}^{\prime})$.

  * (ii)

We use $\boldsymbol{u}$ instead of $\boldsymbol{b}^{\prime}$ for notational
convenience and let $\boldsymbol{q}\mathrel{\mathop{\mathchar
58\relax}}=\boldsymbol{b}\|\boldsymbol{u}$. The second upper bound is easy to
show as the policy is restricted to $s>l(\boldsymbol{b})$. To prove
$h^{*}(\boldsymbol{u})\leq h^{*}(\boldsymbol{q})$, we will find a lower bound
for $h^{*}(\boldsymbol{q})-h^{*}(\boldsymbol{u})$ and show that it is non-
negative. Observe that

$\begin{split}h^{*}(\boldsymbol{q})-h^{*}(\boldsymbol{u})&=h^{*}(\boldsymbol{q})-\min_{s}E_{\boldsymbol{u},s}[g(s,\boldsymbol{u})+h^{*}(\boldsymbol{U}^{\prime})-\lambda^{*}]\\\
&\geq
h^{*}(\boldsymbol{q})-E_{\boldsymbol{u},s}[g(s,\boldsymbol{u})+h^{*}(\boldsymbol{U}^{\prime})-\lambda^{*}]\\\
&=E_{\boldsymbol{q},s^{*}(\boldsymbol{q})}[g(s,\boldsymbol{q})+h^{*}(\boldsymbol{Q}^{\prime})]-E_{\boldsymbol{u},s}[g(s,\boldsymbol{u})+h^{*}(\boldsymbol{U}^{\prime})]\end{split}$
(53)

for any $s$. Therefore, changing the actions that govern the Markov chain
$\\{\boldsymbol{U}_{i}\\}$ leads to further lower bounds. Now, we will use a
similar coupling idea as done in the proof of Lemma 1. Consider the two Markov
chains above where the first one starts from $\boldsymbol{q}$ and the other
from $\boldsymbol{u}$. Assume the two processes are coupled with having the
same future arrivals for the consequent buffer states. Moreover, the former
chain is controlled with its respective optimal policy $\boldsymbol{s}^{*}$,
whereas the latter is controlled as follows: If possible, choose the data
chosen by the first process; otherwise choose the oldest data possible. Denote
this policy as $\tilde{\boldsymbol{s}}$ and let $\\{\boldsymbol{Q}_{i}\\}$ be
the Markov chain pertaining to the former process. Then these two processes
will follow the paths

$\begin{split}\boldsymbol{q}=\boldsymbol{Q}_{0}\stackrel{{\scriptstyle
s^{*}(\boldsymbol{Q}_{0})}}{{\to}}\boldsymbol{Q}_{1}\stackrel{{\scriptstyle
s^{*}(\boldsymbol{Q}_{1})}}{{\to}}\boldsymbol{Q}_{2}\to\ldots\to\boldsymbol{Q}_{\tau}\\\
\boldsymbol{u}=\boldsymbol{U}_{0}\stackrel{{\scriptstyle\tilde{s}(\boldsymbol{U}_{0})}}{{\to}}\boldsymbol{U}_{1}\stackrel{{\scriptstyle\tilde{s}(\boldsymbol{U}_{1})}}{{\to}}\boldsymbol{U}_{2}\to\ldots\to\boldsymbol{U}_{\tau}\end{split}$
(54)

and eventually end in the same state
$\boldsymbol{Q}_{\tau}=\boldsymbol{U}_{\tau}$ after a random time $\tau$. This
is because all possible policies induce the same recurrent class as mentioned
in Lemma 2. Replacing $h^{*}(\boldsymbol{Q}^{\prime})$,
$h^{*}(\boldsymbol{U}^{\prime})$ in (53) several times, we obtain

$h^{*}(\boldsymbol{q})-h^{*}(\boldsymbol{u})\geq
E\bigg{[}\sum_{i=0}^{\tau}g(\boldsymbol{Q}_{i},s^{*}(\boldsymbol{Q}_{i}))-g(\boldsymbol{U}_{i},\tilde{s}(\boldsymbol{U}_{i}))\bigg{]}.$
(55)

Observe that the right-hand side is equal to the expectation of the difference
of accumulated costs incurred by the two processes until they reach the same
state. Note that $\boldsymbol{U}_{i}$ is a suffix of $\boldsymbol{Q}_{i}$ for
all $i$. Therefore, the age penalty of the former process will be greater.
Furthermore, the latter process chooses every data that can be chosen by the
former one, except the ones in the first portion $\boldsymbol{b}$, whose miss
do not contribute to the distortion penalty of the latter process. Since both
accumulated age and distortion penalties of the former process
$\\{\boldsymbol{Q}_{i}\\}$ cannot be smaller than those of
$\\{\boldsymbol{U}_{i}\\}$, the expectation in (55) is non-negative. Hence the
proof is complete.

###  -D Proof of Theorem 3

For simplicity, we prove the case with $|\mathcal{V}|=3$ and we set
$v_{\min}=1$ without loss of generality. The same proof technique may be
extended to larger $|\mathcal{V}|$, e.g., with induction.

Assume the policy iteration algorithm is executed with a sufficiently large
buffer size $M$. We first show that packets of importance $v_{2}$ are never
chosen by the optimal policy if choosing them incurs an age penalty greater
than $K_{2}\mathrel{\mathop{\mathchar
58\relax}}=\lceil\frac{v_{2}-1}{\eta\mu}\rceil$, i.e., they must not be
generated more than $K_{2}$ time slots ago. We use the same coupling idea of
two controlled Markov chains with different policies, as we have done in the
proofs of Lemma 1 and Property 1(ii).

Take a state $\boldsymbol{b}\in\mathcal{V}^{\leq M}$ with length greater than
$K_{2}$, with $b_{1}=v_{2}$ (this equality is without loss of generality) and
suppose $s^{*}(\boldsymbol{b})=1$. We will show that there is a better
strategy than $s^{*}(\boldsymbol{b})=1$, which contradicts the optimality of
$s^{*}$. Consider now
$\tilde{s}(\boldsymbol{b})=\min\\{k>1\mathrel{\mathop{\mathchar
58\relax}}b_{k}>1\\}$, i.e, the index of first non-1 data (whose importance is
greater than 1) in the remaining buffer. Optimality of $s^{*}$ requires the
following inequality to hold (the argument $\boldsymbol{b}$ of
$\tilde{s}(\boldsymbol{b})$ is omitted), otherwise the policy iteration would
not have converged.

$E\big{[}\eta(\tilde{s}-1)+h^{*}(b_{2}^{l}\|\boldsymbol{V}^{Z})-h^{*}(b_{\tilde{s}+1}^{l}\|\boldsymbol{V}^{Z})\big{]}-\frac{1}{\mu}v_{2}\leq
0$ (56)

Now, consider two coupled processes $\\{\boldsymbol{Q}_{i}\\}$,
$\\{\boldsymbol{U}_{i}\\}$ with $\boldsymbol{Q}_{0}\mathrel{\mathop{\mathchar
58\relax}}=(b_{2}^{l}\|\boldsymbol{V}^{Z})$,
$\boldsymbol{U}_{0}\mathrel{\mathop{\mathchar
58\relax}}=(b_{\tilde{s}+1}^{l}\|\boldsymbol{V}^{Z})$ where the actions of
$\\{\boldsymbol{U}_{i}\\}$ are modified. The modification will be the same as
in the proof of Property 1(ii): Choose the packet chosen by the first process
if possible; otherwise choose the oldest possible. As shown in the proof of
Property 1(ii), altering the policy increases the expected relative value.
Consequently, we obtain a lower bound to the expectation in (56). Again, as
every policy has the same recurrent class, the two processes coincide with
probability one. When they coincide, one of the following occurs:

  * (i)

$\\{\boldsymbol{Q}_{i}\\}$ misses a non-1 data that is taken by
$\\{\boldsymbol{U}_{i}\\}$. Then the accumulated cost is greater than
$\frac{1}{\mu}v_{2}$.

  * (ii)

$\\{\boldsymbol{U}_{i}\\}$ takes a packet of importance 1 at the end. Then the
accumulated penalty incurred by age will be greater than $\eta
l(\boldsymbol{b})$ (using the fact that $\\{\boldsymbol{U}_{i}\\}$ remains a
suffix of $\\{\boldsymbol{Q}_{i}\\}$ for all $i$) and the accumulated cost
from distortion will be greater than $\frac{1}{\mu}$ (since
$\\{\boldsymbol{U}_{i}\\}$ takes an extra packet of importance 1). The total
cost will be greater than $\eta l(\boldsymbol{b})+\frac{1}{\mu}\geq\eta
K_{2}(\eta)+\frac{1}{\mu}\geq\frac{1}{\mu}v_{2}$.

Therefore, we conclude that $\frac{1}{\mu}v_{2}$ is a lower bound to the
expectation in (56). Hence the left-hand side of (56) can never be negative
and $s^{*}$ cannot be optimal — if it is equal to zero, then $s^{*}$ and
$\tilde{s}$ are indifferent, so one can drive the process with $\tilde{s}$.

Now we proceed in a similar fashion to prove the case for $v_{3}$. Consider a
state $\boldsymbol{b}$ with $l(\boldsymbol{b})>K_{3}\mathrel{\mathop{\mathchar
58\relax}}=\lceil\frac{v_{3}-1}{\eta\mu}\rceil$, $b_{1}=v_{3}$ and suppose
$s^{*}(\boldsymbol{b})=1$. Choose
$\tilde{s}(\boldsymbol{b})=\min\\{k>1\mathrel{\mathop{\mathchar
58\relax}}b_{k}>1,\ l(\boldsymbol{b})-k<K_{2}\text{ if }b_{k}=v_{2}\\}$, i.e.,
take the first non-1 data but with the constraint that if it has importance
$v_{2}$, it must be generated within the most recent $K_{2}$ time slots.

Define $\\{\boldsymbol{Q}_{i}\\}$ and $\\{\boldsymbol{U}_{i}\\}$ in a similar
fashion. The modification done to the actions on $\\{\boldsymbol{U}_{i}\\}$
will have a minor difference compared to the previous case. Again, if
$\boldsymbol{U}_{i}$ cannot choose a data that is chosen by
$\boldsymbol{Q}_{i}$, it chooses the first non-1 data but with the following
extra condition: If its importance is $v_{2}$, take it if has been generated
less than $K_{2}$ time slots ago; otherwise skip it and do the same for the
next non-1 data. This modification ensures that $\boldsymbol{U}_{i}$ will
choose every possible data that may be chosen by $\boldsymbol{Q}_{i}$. When
the two processes coincide, one of the following occurs:

  * (i)

$\\{\boldsymbol{Q}_{i}\\}$ misses $v_{3}$ that is taken by
$\\{\boldsymbol{U}_{i}\\}$. Then the accumulated cost is greater than
$\frac{1}{\mu}v_{3}$.

  * (ii)

$\\{\boldsymbol{Q}_{i}\\}$ misses $v_{2}$ that is taken by
$\\{\boldsymbol{U}_{i}\\}$. Then the accumulated cost incurred by age will be
greater than $\eta(l(\boldsymbol{b})-K_{2})$ (as $\\{\boldsymbol{U}_{i}\\}$
has remained a suffix of $\\{\boldsymbol{Q}_{i}\\}$ and has taken this
$v_{2}$, whose index must be greater than $l(\boldsymbol{b})-K_{2}$). The
accumulated cost from distortion will be greater than $\frac{1}{\mu}v_{2}$.
Consequently, the total cost will be greater than
$\eta(l(\boldsymbol{b})-K_{2})+\frac{1}{\mu}v_{2}\geq\frac{v_{3}-1}{\mu}-\frac{v_{2}-1}{\mu}+\frac{1}{\mu}v_{2}=\frac{1}{\mu}v_{3}$.

  * (iii)

$\\{\boldsymbol{U}_{i}\\}$ takes a 1 at the end. Then the accumulated cost
incurred by age will be greater than $\eta l(\boldsymbol{b})$ (again, using
the fact that $\\{\boldsymbol{U}_{i}\\}$ remains a suffix of
$\\{\boldsymbol{Q}_{i}\\}$) and the accumulated cost from distortion will be
greater than $\frac{1}{\mu}$ (since $\\{\boldsymbol{U}_{i}\\}$ takes an extra
1). The total cost will be greater than $\eta
l(\boldsymbol{b})+\frac{1}{\mu}\geq\frac{1}{\mu}v_{3}$.

Similar to the case of $v_{2}$, the expectation (56) can never be negative and
hence $s^{*}$ cannot be optimal.

All in all, we have shown that starting the policy iteration algorithm with a
buffer size $M>K_{3}$, the algorithm terminates with an optimal policy that
does not use more than a buffer size of $K_{3}$. This implies that the
solution of the Bellman equation lies within buffers of size at most $K_{3}$.

###  -E Policy Update Improvement

As discussed before, the policy update stage of Algorithm 3 can be improved to
run in $O(K|\mathcal{V}|^{K})$ time. Our aim is to improve the calculation of
$C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},1)$ at step 16 of Algorithm 3. Recall
that $p_{z}\mathrel{\mathop{\mathchar 58\relax}}=\Pr(Z=z)$, and
$q_{z}\mathrel{\mathop{\mathchar 58\relax}}=\Pr(Z\geq z)$. We omit the
argument of $l(\boldsymbol{b})$ for brevity. Let us rewrite
$C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},1)$ by first conditioning on $Z=z$ as

$\displaystyle C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},1)$
$\displaystyle=\eta(l-1)+\sum_{z=1}^{\infty}p_{z}E[h^{(i)}(\boldsymbol{b}_{\geq
2}\|\boldsymbol{V}^{z})]$
$\displaystyle=\eta(l-1)+\sum_{z=1}^{K-l}p_{z}E[h^{(i)}(\boldsymbol{b}_{\geq
2}\|\boldsymbol{V}^{z})]+p_{K-l+1}E[h^{(i)}(\boldsymbol{b}_{\geq
2}\|\boldsymbol{V}^{K-l+1})]$ (57)
$\displaystyle\phantom{=}+\sum_{z=K-l+2}^{\infty}p_{z}E[h^{(i)}(\boldsymbol{b}_{\geq
2}\|\boldsymbol{V}^{z})]$ (58)

and note that for $z>K-l+1$, $h^{(i)}(\boldsymbol{b}_{\geq
2}\|\boldsymbol{V}^{z})=b_{2}/\mu+h^{(i)}(\boldsymbol{b}_{\geq
3}\|\boldsymbol{V}^{z})$ since the length of $\boldsymbol{b}_{\geq
2}\|\boldsymbol{V}^{z}$ exceeds $K$. In line with this result, we rewrite the
summation of (57) and (58) as

$\displaystyle\kappa^{(i)}(\boldsymbol{b}_{\geq 2},K)$
$\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=p_{K-l+1}E[h^{(i)}(\boldsymbol{b}_{\geq
2}\|\boldsymbol{V}^{K-l+1})]+q_{K-l+2}b_{2}/\mu+\sum_{z=K-l+2}^{\infty}p_{z}E[h^{(i)}(\boldsymbol{b}_{\geq
3}\|\boldsymbol{V}^{z})]$ $\displaystyle=p_{K-l(\boldsymbol{b}_{\geq
2})}E[h^{(i)}(\boldsymbol{b}_{\geq
2}\|\boldsymbol{V}^{K-l(\boldsymbol{b}_{\geq
2})})]+q_{K-l(\boldsymbol{b}_{\geq
2})+1}b_{2}/\mu+\sum_{z=K-l(\boldsymbol{b}_{\geq
2})+1}^{\infty}p_{z}E[h^{(i)}(\boldsymbol{b}_{\geq 3}\|\boldsymbol{V}^{z})]$
(59)

The key observation here is that the last term is equal to
$\kappa^{(i)}(\boldsymbol{b}_{\geq
3},K)=\kappa^{(i)}(\operatorname{parent}(\boldsymbol{b}_{\geq 2}),K)$.
Therefore, we have the recursive relation

$\kappa^{(i)}(\boldsymbol{b},K)\mathrel{\mathop{\mathchar
58\relax}}=p_{K-l(\boldsymbol{b})}E[h^{(i)}(\boldsymbol{b}\|\boldsymbol{V}^{K-l(\boldsymbol{b})})]\\\
+q_{K-l(\boldsymbol{b})+1}b_{1}/\mu+\kappa^{(i)}(\operatorname{parent}(\boldsymbol{b}),K)$
(60)

with the initial condition

$\kappa^{(i)}(\delta,K)\mathrel{\mathop{\mathchar
58\relax}}=q_{K}E[h^{(i)}(\boldsymbol{V}^{K})]+\frac{E[V]}{\mu}E[(Z-K)^{+}].$
(61)

The recursive relation (60) can be implemented exactly the same as the other
updates that take place in lines 17-26 of Algorithm 3. Finally, we have

$C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},1)=\eta(l-1)+\sum_{z=1}^{K-l}p_{z}E[h^{(i)}(\boldsymbol{b}_{\geq
2}\|\boldsymbol{V}^{z})]+\kappa^{(i)}(\operatorname{parent}(\boldsymbol{b}),K).$
(62)

Knowing $\kappa^{(i)}(\operatorname{parent}(\boldsymbol{b}),K)$, both
$C_{\boldsymbol{h}^{(i)}}(\boldsymbol{b},1)$ and
$\kappa^{(i)}(\boldsymbol{b},K)$ can be calculated in $O(|\mathcal{V}|^{K-l})$
steps. Consequently, the total amount of calculations done for all length-$l$
states is $O(|\mathcal{V}|^{K})$, and consequently for the depth-$K$ tree
$\mathcal{T}$, the amount of calculations done is $O(K|\mathcal{V}|^{K})$.

###  -F Closed-Form Expressions for the Simple Strategies

####  -F1 S1 — Send the oldest important data among the most recent $K$

For a buffer $\boldsymbol{b}$, let $s$ be the index of the first important
data among the $K$ most recently arrived packets. Let $a=(K\wedge
l(\boldsymbol{b}))-s+1$; and if there is no important data among the $K$ most
recent packets, set $a=0$. Let $A_{i}$ be the value of $a$ at time instant
$i$. It can be verified that the process $\\{A_{i}\\}$ is a Markov chain with
state space $\\{0,1,\ldots,K\\}$. Let $p_{a,a^{\prime}}$ denote the transition
probability from state $a$ to $a^{\prime}$; and $\pi_{a}$ denote the
stationary probability of state $a$. Recall that $Z$ is a geometric random
variable and denote $p\mathrel{\mathop{\mathchar 58\relax}}=\Pr(Z=1)$ and
$q\mathrel{\mathop{\mathchar 58\relax}}=\Pr(V=v_{2})$. Let
$\bar{x}\mathrel{\mathop{\mathchar 58\relax}}=1-x$.

Now, let us calculate $p_{a,a^{\prime}}$. Observe that when we are at state
$a$, the first element in the buffer is selected and the remaining $a-1$
elements are untouched and need not be known. Conditioned on the next speaking
time being $a^{\prime}-a<z\leq K-a$, the probability that the next state being
$a^{\prime}$ is equal to $\bar{q}^{z-(a^{\prime}-a)-1}q$. This is because the
first $z-(a^{\prime}-a)-1$ elements must be $v_{1}$ and the next should be
$v_{2}$. For $z>K-a$, since we only check the most recent $K$ data in the
buffer, the first $K-a^{\prime}$ must be $v_{1}$ and the next one should be
$v_{2}$. Thus we obtain the probability as $\bar{q}^{K-a^{\prime}}q$.
Averaging over $z$, we have

$p_{a,a^{\prime}}=\sum_{z=a^{\prime}-a+1}^{\infty}\bar{p}^{z-1}p\bar{q}^{(z-a^{\prime}+a-1)\wedge(K-a^{\prime})}q.$
(63)

With a similar reasoning, we calculate $p_{a^{\prime},a}$ as

$p_{a^{\prime},a}=\sum_{z=1}^{\infty}\bar{p}^{z-1}p\bar{q}^{(z+a^{\prime}-a-1)\wedge(K-a)}q=\sum_{z=a^{\prime}-a+1}^{\infty}\bar{p}^{z-a^{\prime}+a-1}p\bar{q}^{(z-1)\wedge(K-a)}q=\bigg{(}\frac{\bar{q}}{\bar{p}}\bigg{)}^{a^{\prime}-a}p_{a,a^{\prime}}.$
(64)

It is easy to see that $p_{0,a}=p_{1,a}$ as the buffer is emptied in both
cases; and $p_{a,0}=p_{a,1}\tfrac{\bar{q}}{q}$ as the only difference between
the transition from state $a$ to state 0, or to state 1 is the most recent
element being $v_{1}$ or $v_{2}$.

We now claim that the chain is reversible. The claim is easily verified by
noting that the distribution $(\pi_{a}\mathrel{\mathop{\mathchar
58\relax}}a=0,\dots,K)$ described by

$\pi_{0}=(\bar{q}/q)\pi_{1},\ \pi_{a}=(\bar{q}/\bar{p})^{K-a}\pi_{K},\
a=1,\dots,K-1$

with

$\pi_{K}=\big{(}1-\tfrac{\bar{q}}{\bar{p}}\big{)}/\big{(}1-\tfrac{p}{q}\big{(}\tfrac{\bar{q}}{\bar{p}}\big{)}^{K}\big{)}$
(65)

satisfies the detailed balance equations
$\pi_{a}p_{a,a^{\prime}}=\pi_{a^{\prime}}p_{a,a^{\prime}}$.

The average excess age is then calculated straightforwardly:

$\Delta_{e}^{(S1)}(K)=\sum_{k=1}^{K}(k-1)\pi_{k}=\frac{K-1}{\big{(}1-\tfrac{p}{q}\big{(}\tfrac{\bar{q}}{\bar{p}}\big{)}^{K}\big{)}}-\frac{\tfrac{\bar{q}}{\bar{p}}\big{(}1-\big{(}\tfrac{\bar{q}}{\bar{p}}\big{)}^{K}\big{)}}{\big{(}1-\tfrac{p}{q}\big{(}\tfrac{\bar{q}}{\bar{p}}\big{)}^{K}\big{)}\big{(}1-\frac{\bar{q}}{\bar{p}}\big{)}}.$
(66)

For $q=p$, one takes $\frac{\bar{q}}{\bar{p}}\to 1$ in (66) to obtain
$\Delta_{e}^{(S1)}=\frac{(K-1)K}{2(K+\frac{\bar{p}}{p})}$.

The average distortion is calculated as follows: Unimportant packets are sent
$\pi_{0}$ fraction of the speaking times, and the remaining time is allocated
to the transmission of important packets. Hence, unimportant packets are sent
$p\pi_{0}$ fraction of the time and important packets are sent $p(1-\pi_{0})$
fraction of the time. Consequently,

$D^{(S1)}(K)=(\bar{q}-p\pi_{0})v_{1}+(q-p(1-\pi_{0}))v_{2}.$ (67)

####  -F2 S2 — Send the newest important data among the most recent $K$

Compared to the other strategies, the analysis will be relatively simpler. For
a buffer $\boldsymbol{b}$, let $s$ be the index of the newest important data
among the $K$ most recent and let the state be $a=l-s+1$. If there is no
important data among the $K$ most recent, set $a=0$. Observe that regardless
of the value of $a$, the packets (if any) that remain the buffer after
transmission are of minimum importance and will be ignored at the next
speaking time. Hence, at the next speaking time, the next state $a^{\prime}$
will not depend on the current state $a$, and we have an i.i.d. process. Let
$\pi_{a}$ be the probability of the next state being equal to $a$. Conditioned
on the next speaking time $z$, this probability is equal to
$q\bar{q}^{a-1}\mathbbm{1}\\{a\leq z\\}$. Hence, for $0<a\leq K$

$\pi_{a}=\sum_{z\geq
a}^{\infty}q\bar{q}^{a-1}\bar{p}^{z-1}p=q(\bar{p}\bar{q})^{a-1},$ (68)

and
$\pi_{0}=1-\sum_{a=1}^{K}\pi_{a}=\frac{\bar{q}p+q(\bar{p}\bar{q})^{K}}{1-\bar{p}\bar{q}}$.
The age and distortion are calculated similar to (66) and (67).

####  -F3 S3 — Send the newest important data that has arrived more than $K$
slots ago. If there is no such data, send the oldest important one

We set the state associated to a buffer $\boldsymbol{b}$ as follows: If
$\boldsymbol{b}$ does not contain an important data arrived more than $K$ time
slots ago, set $a=(K\wedge l(\boldsymbol{b}))-s+1$ as the state; and if there
is no important data in the buffer, set $a=0$. Note that this is exactly the
same as in S1. If $\boldsymbol{b}$ does contain an important data that has
arrived more than $K$ time slots ago, set $a=K+1$. Hence the state space will
be $\\{0,1,\ldots,K+1\\}$. Similar to the analysis of S1, $\\{A_{i}\\}$ will
be a Markov chain. We want to calculate the transition probabilities
$p_{K+1,a}$ for $0<a<K+1$. Since at state $K+1$, an important data has arrived
more than $K$ slots ago, $\boldsymbol{b}$ is of the form
$\boldsymbol{b}=[v_{2},v_{1},\ldots,v_{1},\underbrace{\ldots}_{K}]$, where the
last $K$ data need not be known. Conditioned on the speaking time $z$, the
probability of ending up in state $a$ is then should be $\bar{q}^{z+K-a}q$.
Consequently,

$p_{K+1,a}=\sum_{z=1}^{\infty}\bar{p}^{z-1}p\bar{q}^{K-a+z}q=\frac{pq\bar{q}^{K-a+1}}{1-\bar{p}\bar{q}}.$
(69)

Now, we aim to find $p_{a,K+1}$ for $0<a<K+1$. Since $\boldsymbol{b}$ is of
the form $\boldsymbol{b}=[\ldots,v_{2},\underbrace{\ldots}_{a-1}]$, and the
last $a-1$ data need not be known, the next speaking time should be greater
than $K-a+1$. Moreover, there must be at least one important data among the
first $z-(K-a+1)$. Then, we obtain

$p_{a,K+1}=\sum_{z>K-a+1}\bar{p}^{z-1}p(1-\bar{q}^{z-(K-a+1)})=\frac{q\bar{p}^{K-a+1}}{1-\bar{p}\bar{q}}.$
(70)

Calculation of $p_{a,a^{\prime}}$, $0<a\leq a^{\prime}<K+1$ is similar to the
one in S1. Since $\boldsymbol{b}=[\ldots,v_{2},\underbrace{\ldots}_{a-1}]$,
the next speaking time should be greater than $a^{\prime}-a$, and the first
$z-(a^{\prime}-a+1)$ data must be unimportant while the
$z-(a^{\prime}-a)^{\text{th}}$ data must be important. Thus,

$p_{a,a^{\prime}}=\sum_{z>a^{\prime}-a}\bar{p}^{z-1}p\bar{q}^{z-a^{\prime}+a}q=\frac{pq\bar{p}^{a^{\prime}-a}}{1-\bar{p}\bar{q}}.$
(71)

A similar analysis reveals that for $0<a^{\prime}\leq a<K+1$,

$p_{a,a^{\prime}}=\sum_{z=1}^{\infty}\bar{p}^{z-1}p\bar{q}^{z-a^{\prime}+a-1}q=\frac{pq\bar{q}^{a-a^{\prime}}}{1-\bar{p}\bar{q}}.$
(72)

Finally, as we discussed in the analysis of S1, $p_{0,a}=p_{1,a}$ and
$p_{a,0}=p_{a,1}\tfrac{\bar{q}}{q}$. Hence, we have found all the transition
probabilities. We will verify that $\\{A_{i}\\}$ is a reversible Markov chain.
The detailed balance equations for the state pairs $(a,K+1)$ with $a>0$
require the stationary distribution $\pi$ to satisfy

$\pi_{K+1}p_{K+1,a}=\pi_{a}p_{a,K+1}$ (73)

and thus we find
$\pi_{a}=p\big{(}\tfrac{\bar{q}}{\bar{p}}\big{)}^{K+1-a}\pi_{K+1}$ for $a>0$.
Detailed balance equations for the state pair $(0,1)$ further yield
$\pi_{0}=(\bar{q}/q)\pi_{1}=\tfrac{p\bar{q}}{q}\big{(}\tfrac{\bar{q}}{\bar{p}}\big{)}^{K}\pi_{K+1}$.
One can easily verify that this choice satisfies not only (73) but all the
detailed balance equations. Thus, we have verified the reversibility of the
chain and found its stationary distribution.

Let us start the chain with the stationary distribution and let
$\Delta_{i}\mathrel{\mathop{\mathchar
58\relax}}=l(\boldsymbol{B}_{i})-s(\boldsymbol{B}_{i})$ be the instantaneous
excess age at the $i^{\text{th}}$ speaking time. If $0\leq A_{i}\leq K$, then
$\Delta_{i}=(A_{i}-1)\vee 0$. When $A_{i}=K+1$, however, $\Delta_{i}$ is
random. It turns out that the distribution of $\Delta_{i}-(K-1)$ conditioned
on $A_{i}=K+1$ is geometrically distributed. To see this, observe

$\begin{split}\Pr(\Delta_{i}=K-1+z^{\prime}|A_{i}=K+1)&=\frac{\Pr(\Delta_{i}=K-1+z^{\prime},A_{i}=K+1)}{\pi_{K+1}}\\\
&=\frac{1}{\pi_{K+1}}\sum_{a=1}^{K+1}\pi_{a}\sum_{z\geq
K-a+1+z^{\prime}}\bar{p}^{z-1}pq\bar{q}^{z^{\prime}-1}+\frac{\pi_{0}}{\pi_{K+1}}\sum_{z\geq
K+z^{\prime}}\bar{p}^{z-1}pq\bar{q}^{z^{\prime}-1}\\\
&=\frac{1}{\pi_{K+1}}\sum_{a=1}^{K+1}\pi_{a}\bar{p}^{K-a+z^{\prime}}q\bar{q}^{z^{\prime}-1}+\frac{\pi_{0}}{\pi_{K+1}}\bar{p}^{K+z^{\prime}-1}q\bar{q}^{z^{\prime}-1}\\\
&=\sum_{a=1}^{K+1}p^{\mathbbm{1}\\{a\leq
K\\}}\big{(}\tfrac{\bar{q}}{\bar{p}}\big{)}^{K+1-a}\bar{p}^{K-a+z^{\prime}}q\bar{q}^{z^{\prime}-1}+p\tfrac{\bar{q}}{q}(\tfrac{\bar{q}}{\bar{p}}\big{)}^{K}\bar{p}^{K+z^{\prime}-1}q\bar{q}^{z^{\prime}-1}\\\
&=(\bar{p}\bar{q})^{z^{\prime}-1}(1-\bar{p}\bar{q}).\end{split}$ (74)

Then, the average excess age is found as

$\Delta_{e}^{(S3)}(K)=\sum_{k=1}^{K}(k-1)\pi_{k}+\pi_{K+1}\big{(}\tfrac{1}{1-\bar{p}\bar{q}}+K-1\big{)}.$
(75)

The average distortion is calculated the same as in (67).

###  -G Proof of Corollary 2

Denote the stationary probabilities of each state $l$ as $\pi_{l}$ and
$p_{i}\mathrel{\mathop{\mathchar 58\relax}}=\Pr(Z=i)=p\bar{p}^{i-1}$ with
$\bar{p}\mathrel{\mathop{\mathchar 58\relax}}=1-p$. Assume $\tau>N$ for the
moment. The derivation for $\tau\leq N$ will easily follow.

Let $s_{i}^{j}\mathrel{\mathop{\mathchar 58\relax}}=\sum_{l=i}^{j}\pi_{l}$ and
$s_{i}\mathrel{\mathop{\mathchar 58\relax}}=s_{i}^{\infty}$. The stationary
probabilities are the solution to the linear system

$\begin{split}\pi_{1}&=p_{1}s_{1}^{N}\\\
\pi_{2}&=p_{2}s_{1}^{N}+p_{1}\pi_{N+1}\\\ \ldots\\\
\pi_{\tau}&=p_{\tau}s_{1}^{N}+p_{\tau-1}\pi_{N+1}+\ldots+p_{1}\pi_{N+\tau-1}\\\
\pi_{\tau+1}&=p_{\tau+1}s_{1}^{N}+p_{\tau}\pi_{N+1}+\ldots+p_{1}s_{N+\tau}\\\
\ldots\\\
\pi_{\tau+j}&=p_{\tau+j}s_{1}^{N}+p_{\tau+j-1}\pi_{N+1}+\ldots+p_{j}s_{N+\tau}\\\
\ldots\end{split}$ (76)

Observe that

$\pi_{j+1}=\bar{p}\pi_{j}+p\pi_{N+j},\ 1\leq j\leq\tau-1$ (77)

and

$\pi_{j+1}=\bar{p}\pi_{j},\ j\geq\tau+1.$ (78)

Summing up the equalities in (77), with indices up to $j+1$, we obtain

$s_{2}^{j+1}=\bar{p}s_{1}^{j}+ps_{N+1}^{N+j}$ (79)

and hence

$\pi_{j+1}+ps_{2}^{j}=\bar{p}\pi_{1}+ps_{N+1}^{N+j}.$ (80)

Note that the first equation in (76) implies $\bar{p}\pi_{1}=ps_{2}^{N}$ and
thus we get

$\pi_{j+1}+ps_{2}^{j}=ps_{2}^{N}+ps_{N+1}^{N+j}$ (81)

and

$\bar{p}\pi_{j+1}=ps_{j+2}^{N+j},\ 1\leq j\leq\tau-1,$ (82)

which implies for $j=\tau-1$

$\pi_{\tau}=p\sum_{k=1}^{N+\tau-1}\pi_{\tau+k}=\frac{\pi_{\tau+1}(1-\bar{p}^{N-1})}{\bar{p}}$
(83)

where the last equality follows from (78). Now repeated application of (77)
gives

$\pi_{\tau-j}=\pi_{\tau+1}\frac{1-(1+jp)\bar{p}^{N-1}}{\bar{p}^{j+1}},\ 0\leq
j\leq N-1.$ (84)

Our aim is now to find all stationary probabilities in terms of
$\pi_{\tau+1}$. With the above, we are able to find $\pi_{\tau-j}$, $0\leq
j\leq N-1$ in terms of $\pi_{\tau+1}$. For $j>N-1$, we try to observe a
pattern. First, try to calculate $\pi_{\tau-N}$ by (77), which gives

$\pi_{\tau-N}=\pi_{\tau+1}\frac{1-(1+Np)\bar{p}^{N-1}+p\bar{p}^{2(N-1)}}{\bar{p}^{N+1}}.$
(85)

Once more, repeated application of (77) gives

$\begin{split}\pi_{\tau-
N-j}=\pi_{\tau+1}\frac{1-(1+(N+j)p)\bar{p}^{N-1}}{\bar{p}^{N+j+1}}+\pi_{\tau+1}\frac{p(\sum_{k=0}^{j}(1+kp))\bar{p}^{2(N-1)}}{\bar{p}^{N+j+1}}\end{split}$
(86)

for $0\leq j\leq N-1$. Doing the same procedure, we observe the following
pattern: Let $S_{j}^{(0)}\mathrel{\mathop{\mathchar 58\relax}}=(1+jp)$ and
$S_{j}^{(n)}\mathrel{\mathop{\mathchar 58\relax}}=\sum_{k=0}^{j}S_{k}^{(n-1)}$
for $n\geq 1$. Also let $S_{j}^{(n)}=0$ for $j<0$. Then,

$\pi_{\tau-j}=\pi_{\tau+1}\frac{1+\sum_{k=0}^{\lceil\tau/N\rceil}(-1)^{k+1}S_{j-kN}^{(k)}p^{k}\bar{p}^{(k+1)(N-1)}}{\bar{p}^{j+1}}.$
(87)

Finally, since the probabilities sum up to one, we have

$\begin{split}1&=s_{1}^{\tau}+s_{\tau+1}=s_{1}^{\tau}+\frac{\pi_{\tau+1}}{p}\\\
&=\pi_{\tau+1}\sum_{j=0}^{\tau-1}\frac{1+\sum_{k=0}^{\lceil\tau/N\rceil}(-1)^{k+1}S_{j-kN}^{(k)}p^{k}\bar{p}^{(k+1)(N-1)}}{\bar{p}^{j+1}}+\frac{\pi_{\tau+1}}{p}\end{split}$
(88)

and therefore

$\pi_{\tau+1}=\bigg{[}\sum_{j=0}^{\tau-1}\frac{1+\sum_{k=0}^{\lceil\tau/N\rceil}(-1)^{k+1}S_{j-kN}^{(k)}p^{k}\bar{p}^{(k+1)(N-1)}}{\bar{p}^{j+1}}+\frac{1}{p}\bigg{]}^{-1}.$
(89)

After calculating all $\pi_{j}$s, it is straightforward to obtain expressions
for $\Delta_{e}$ and $D$ as

$\Delta_{e}=\sum_{j=1}^{\tau-1}j\pi_{N+j}+\tau\sum_{j=\tau}^{\infty}\pi_{N+j}=\sum_{j=1}^{\tau-1}j\pi_{N+j}+\frac{\tau\pi_{\tau+1}\bar{p}^{N-1}}{p}$
(90)

and

$D=\mu_{V}\sum_{j=1}^{\infty}j\pi_{\tau+N+j}=\frac{\mu_{V}\pi_{\tau+1}\bar{p}^{N}}{p^{2}}.$
(91)