\ifreport
\section{Proof of Theorem \ref{thm1}}\label{sec_analysis}


\subsection{Simplification of Problem \eqref{eq_problem}}

In \cite{AgeOfInfo2016,SunISIT2017}, it was shown that \emph{no new sample should be taken when the server is busy}. The reason is as follows: If a sample is taken when the server is busy, it has to wait in the queue for its transmission opportunity; meanwhile the sample is becoming stale. A better strategy is to take a new sample once the server becomes idle. By using the sufficient statistic of the Markov chain $X_n$, one can show that the second strategy is better. 

Because of this, we only need to consider a sub-class of sampling policies $\Pi_1\subset\Pi$ in which each sample is generated and submitted to the server after the previous sample is delivered, i.e.,
\begin{align}
\Pi_1 
 &= \{\pi\in\Pi: S_{i+1} \geq D_{i} = S_i + Y_i \text{ for all $i$}\}. 
\end{align}
Let $Z_i = S_{i+1} -D_{i} \geq0$ represent the waiting time between the delivery time $D_i$ of sample $i$ and the generation time $S_{i+1}$ of sample $i+1$. Since $S_1 = 0$, we have
$S_i =  S_{1} +\sum_{j=1}^{i} (Y_{j} + Z_j)=\sum_{j=1}^{i} (Y_{j} + Z_j)$ and $D_i = S_i + Y_i$. Given $(Y_1,Y_2,\ldots)$, $(S_1,S_2,\ldots)$ is uniquely determined by $(Z_1,Z_2,\ldots)$. Hence, one can also use $\pi = (Z_1,Z_2,\ldots)$ to represent a sampling policy in $\Pi_1$. 


Because $T_i $ is a regenerative process, 
using the renewal theory in \cite{Ross1996} and \cite[Section 6.1]{Haas2002}, one can show that in Problem \eqref{eq_problem}, $\frac{1}{i} 
\mathbb{E}[S_i]$ and $\frac{1}{i} 
\mathbb{E}[D_i]$ are convergent sequences and 

\begin{align}
&\limsup_{N\rightarrow \infty}\frac{1}{N}~\mathbb{E}\left[\sum_{n=1}^N p(\age_n)\right] \nonumber
\\
=& \lim_{i\rightarrow \infty}\frac{\mathbb{E}\left[\sum_{n=1}^{D_i} p(\age_n)\right]}{\mathbb{E}[D_i]} \nonumber\\
=& \lim_{i\rightarrow \infty}\frac{\sum_{j=1}^{i}\mathbb{E}\left[\sum_{n=D_{j}}^{D_{j+1}-1}p(\age_n)\right]}{\sum_{j=1}^{i} \mathbb{E}\left[Y_j+Z_j\right]}.\nonumber

\end{align}
In addition, for each policy in $\Pi_1$, it holds that $D_i \leq D_{i+1}$. In this case, the age $\age_n$ in \eqref{eq_age} can be expressed as 
\begin{align}
\age_n = n- S_i,~\text{if}~D_i\leq n < D_{i+1}. \nonumber
\end{align}
Hence,
\begin{align}\label{eq_sum1}
\sum_{n=D_{i}}^{D_{i+1}-1}\!\!p(\age_n)=\!\!\sum_{n=D_{i}}^{D_{i+1}-1}\!\!p(n-S_i)=\!\!\sum_{n=Y_{i}}^{Y_i+Z_i+Y_{i+1}-1}\!\!p(n), 
\end{align}
which is a function of $(Y_i,Z_i,Y_{i+1})$. Define 
\begin{align}\label{eq_sum}
q(Y_i,Z_i,Y_{i+1})= \sum_{n=Y_{i}}^{Y_i+Z_i+Y_{i+1}-1}\!\!p(n), 
\end{align}
then  \eqref{eq_problem} can be simplified as 
\begin{align}\label{eq_problem_S1}
\bar p_{\text{opt}} = \inf_{\pi\in\Pi_1}~&\lim_{i\rightarrow \infty}\frac{\sum_{j=1}^{i}\mathbb{E}\left[q(Y_j,Z_j,Y_{j+1})\right]}{\sum_{j=1}^{i} \mathbb{E}\left[Y_j+Z_j\right]}.


\end{align}

In order to solve \eqref{eq_problem_S1}, let us consider the following Markov decision problem with a parameter $c\geq 0$:

\begin{align}\label{eq_SD}
\!\!h(c)\!\triangleq\!\inf_{\pi\in\Pi_1}&\lim_{i\rightarrow \infty}\frac{1}{i}\sum_{j=0}^{i-1}\mathbb{E}\left[q(Y_j,Z_j,Y_{j+1})-c(Y_j+Z_j)\right]
\!\!\!\!

\end{align}
where $h(c)$ is the optimum  value of \eqref{eq_SD}. Similar with Dinkelbach's method  \cite{Dinkelbach67} for nonlinear fractional programming, the following lemma in \cite{Sun_reportISIT17} also holds for our Markov decision problem \eqref{eq_problem_S1}:

\begin{lemma} \label{lem_ratio_to_minus} \cite[Lemma 2]{Sun_reportISIT17}
The following assertions are true:
\begin{itemize}
\item[(a).] \emph{$\bar p_{\text{opt}}  \gtreqqless c $} if and only if $h(c)\gtreqqless 0$. 
\item[(b).] If $h(c)=0$, the solutions to \eqref{eq_problem_S1}
and \eqref{eq_SD} are identical. 
\end{itemize}
\end{lemma}

Hence, the solution to \eqref{eq_problem_S1} can be obtained by solving \eqref{eq_SD} and seeking $\bar p_{\text{opt}}\in\mathbb{R}$  that satisfies
\begin{align}\label{eq_c}
h(\bar p_{\text{opt}})=0. 
\end{align}

\subsection{Optimal Solution of  \eqref{eq_SD} for \emph{$c = \bar p_{\text{opt}}$} }


Next, we present an optimal solution to \eqref{eq_SD} for $c = \bar p_{\text{opt}}$.  

\begin{definition}
A policy $\pi\in\Pi_{1}$ is said to be a \emph{stationary randomized} policy, if it observes $Y_i$ and then chooses a waiting time $Z_i\in[0,\infty)$ 
based on the observed value of $Y_i$, 
according to a conditional probability measure $p(y,A)\triangleq\Pr[Z_i\in A| Y_i=y]$ that is invariant for all $i=1,2,\ldots$ Let $\Pi_{\text{SR}}$ ($\Pi_{\text{SR}}\subset \Pi_1$)  denote the set of stationary randomized policies, defined by
\begin{align}
&\Pi_{\text{SR}}\!=\!\{\pi\in\Pi_1: \text{Given the observation $Y_i=y_i$, $Z_i$ is chosen}\nonumber\\
&\text{according to the probability measure } p(y_i,A) \text{ for all } i\}.\nonumber
\end{align}
\end{definition}


\begin{lemma}\label{lem_SRoptimal} 
If the service times $Y_i$ are {i.i.d.}, then there exists a stationary randomized policy that is optimal for solving \eqref{eq_SD} with \emph{$c = \bar p_{\text{opt}}$}.
\end{lemma}
\begin{proof}


In \eqref{eq_SD}, the minimization of the term 
\begin{align}\label{eq_opt_stopping1}
&\mathbb{E}\left[q(Y_j,Z_j,Y_{j+1})- \bar p_{\text{opt}} (Y_j+Z_j)\right]\nonumber\\
=&\mathbb{E}\left[q(Y_j,Z_j,Y_{j+1})- \bar p_{\text{opt}} (Z_j+Y_{j+1})\right]
\end{align}
over $Z_j$ depends on $(Y_1,\ldots,Y_j, Z_1,\ldots,Z_{j-1})$ via $Y_j$. Hence, $Y_j$ is a sufficient statistic for determining $Z_j$ in \eqref{eq_SD}. This means that the rule for determining $Z_i$ can be represented by the conditional probability distribution $\Pr[Z_i\in A| Y_i=y_i]$, and in addition, there exists an optimal  solution $(Z_1,Z_2,\ldots)$ to \eqref{eq_SD}, in which $Z_i$ is determined by solving 
\begin{align}\label{eq_opt_stopping2}
\!\!\!\!\min_{\substack{\Pr[Z_i\in A| Y_i=y_i]}} \!\!\!\!\mathbb{E}\left[q(Y_i,Z_i,Y_{i+1})\!-\! \bar p_{\text{opt}} (Z_j+Y_{j+1})\big|Y_i=y_i \right]\!,\!\!
\end{align}
and then use  the observation $Y_i=y_i$ and the optimal conditional probability distribution $\Pr[Z_i\in A| Y_i=y_i]$ that solves \eqref{eq_opt_stopping2}  to decide $Z_i$. Finally, notice that the minimizer of \eqref{eq_opt_stopping2} depends on the joint distribution of $Y_i$ and $Y_{i+1}$. Because the $Y_i$'s are  \emph{i.i.d.},  the joint distribution of $Y_i$ and $Y_{i+1}$ is invariant for $i=1,2,\ldots$ Hence, the optimal conditional probability measure $\Pr[Z_i\in A| Y_i=y_i]$ solving \eqref{eq_opt_stopping2} is invariant for $i=1,2,\ldots$ By definition,  there exists a stationary randomized policy that is optimal for solving Problem \eqref{eq_SD} with $c = \bar p_{\text{opt}}$, which completes the proof.
\end{proof}


Next, by using an idea similar to that in the solution of \cite[Problem 5.5.3]{Bertsekas}, we can obtain 


\begin{lemma}\label{lem4}
If $p: \mathbb{R}\mapsto \mathbb{R}$ is non-decreasing and the service times $Y_i$ are {i.i.d.}, then an optimal solution $(Z_1,Z_2,\ldots)$ of \eqref{eq_SD} is given by

\begin{align}\label{lem4_eq1}
Z_i = \min\{n\in \mathbb{N}: \mathbb{E}\!\left[p(Y_i+n+Y_{i+1})|Y_i\right]\! \geq\! \beta \},
\end{align}
where \emph{$\beta = \bar p_{\text{opt}}$}.
\end{lemma}
\begin{proof}

Using \eqref{eq_sum} and $\beta = \bar p_{\text{opt}} $, \eqref{eq_opt_stopping2} can be expressed as
\begin{align}\label{eq_opt_stopping4}
\min_{\substack{\Pr[Z_i\in A| Y_i=y_i]}} \mathbb{E}\left[\sum_{n=0}^{Z_i+Y_{i+1}-1}\!\![p(n+Y_i)- \beta] \Bigg| Y_i\right].
\end{align}
It holds that  for $m =1, 2,3,\ldots$
\begin{align}\label{eq_opt_stopping5}
&\mathbb{E}\!\!\left[\sum_{n=0}^{m+Y_{i+1}}\!\!\!\![p(n+Y_i)- \beta] -\!\!\sum_{n=0}^{m+Y_{i+1}-1}\!\!\!\![p(n+Y_i)- \beta] \Bigg| Y_i\right]\nonumber\\
=& \mathbb{E}\!\left[p(Y_i+m+Y_{i+1})- \beta|Y_i\right].
\end{align}
Because $p: \mathbb{R}\mapsto \mathbb{R}$ is non-decreasing, if $Z_i$ is chosen according to  \eqref{lem4_eq1}, we can obtain
\begin{align}
&\mathbb{E}\!\left[p(Y_i+n+Y_{i+1})-\beta |Y_i\right] < 0,~ n = 0, \ldots,  Z_i-1, \\
&\mathbb{E}\!\left[p(Y_i+n+Y_{i+1})-\beta |Y_i\right] \geq 0,~ n \geq Z_i.\label{eq_opt_stopping6}
\end{align}
Based on \eqref{eq_opt_stopping5}-\eqref{eq_opt_stopping6}, it is easy to see that \eqref{lem4_eq1} is the optimal solution to \eqref{eq_opt_stopping4}. 
This completes the proof.
\end{proof}


Hence, Theorem~\ref{thm1} follows from Lemma \ref{lem_ratio_to_minus} and Lemma \ref{lem4}.


\ignore{
\begin{proof} 
\subsection{An Upper Bound of \emph{$g(\lambda)$}}

By restricting $\Pi_1$ in Problem \eqref{eq_problem_S1} to $\Pi_{\text{SR}}$, we obtain the following problem:
\begin{align}\label{eq_DPExpected_upper}
g_{\text{SR}} (\lambda) = \inf_{\pi\in\Pi_1}  L(\pi;\lambda),
\end{align}
where $g_{\text{SR}} (\lambda)$ is the optimum objective value of Problem \eqref{eq_DPExpected_upper}. Since $\Pi_{\text{SR}} \subset \Pi_1$, we can obtain

\begin{align}\label{eq_time_average_exp0}
g_{\text{SR}} (\lambda)\geq g (\lambda).
\end{align}

For any stationary randomized policy in $\Pi_{\text{SR}}$, the joint distribution of $(Y_i,Z_i,Y_{i+1})$ is invariant for different $i$. Therefore, the distribution of $q(Y_i,Z_i,Y_{i+1})$ is invariant for different $i$.
For any stationary randomized policy $\pi=(Z_1,Z_2,\ldots)\in \Pi_{\text{SR}}$, we have
\begin{align}\label{eq_convergence1}
&\frac{1}{i}\mathbb{E}\left[\sum_{j=1}^{i}q(Y_i,Z_i,Y_{i+1})\right]=\mathbb{E}\left[q(Y_1,Z_1,Y_{2})\right],\\
&\frac{1}{i}\mathbb{E}\left[\sum_{j=1}^{i} (Y_j+Z_j)\right]=\mathbb{E}[Y_1+Z_1].\label{eq_convergence2}
\end{align}
Hence, Problem \eqref{eq_DPExpected_upper} can be reformulated as Problem \eqref{eq_SR}.

\subsection{The Upper Bound of \emph{$\overline{p}_{\text{opt}}$} is Tight, i.e., \emph{$\overline{p}_{\text{SR}}=\overline{p}_{\text{opt}}$}}
We will show $\overline{p}_{\text{SR}}=\overline{p}_{\text{opt}}$ in 4 steps, where we will need the following definitions:
For each policy $\pi=(Z_1,Z_2,\ldots)$ in $\Pi_1$ (more general than stationary randomized policies), we  define 
\begin{align}\label{eq_time_average_exp1}
&{a}_{n,\pi}\!\triangleq\!{\frac{1}{n}\mathbb{E}\bigg[\sum_{j=1}^{n}q(Y_i,Z_i,Y_{i+1})\bigg]}\!-\! \frac{\overline{p}_{\text{opt}}}{n}{\mathbb{E}\bigg[\sum_{j=1}^{n} (Y_{j}+Z_{j})\bigg]}, \\
&{b}_{n,\pi}\triangleq\frac{1}{n}\mathbb{E}\left[\sum_{j=1}^{n} (Y_j+Z_j)\right].\label{eq_time_average_exp2}
\end{align}


Further, define $\Gamma_{\text{SR}}$ as the set of limit points of sequences $\big(({a}_{n,\pi_{}},{b}_{n,\pi}),n=1,2,\ldots\big)$ associated with all \emph{stationary randomized} policies $\pi\in\Pi_{\text{SR}}$. 
Because of \eqref{eq_convergence1} and \eqref{eq_convergence2},  for each stationary randomized policy $\pi\in\Pi_{\text{SR}}$, the sequence $({a}_{n,\pi},{b}_{n,\pi})$ has a unique limit point in the form of
\begin{align}\label{eq_form}
\left(\mathbb{E}[q(Y,Z,Y')]-\overline{p}_{\text{opt}}\mathbb{E}[Y+Z], \mathbb{E}[Y+Z]\right),
\end{align}
where $(Y,Z,Y')$ has the same joint distribution with $(Y_1,Z_1,Y_2)$.


Hence, $\Gamma_{\text{SR}}$ is the set of all points $(\mathbb{E}[q(Y,Z,Y')]- $ $\overline{p}_{\text{opt}}\mathbb{E}[Y+Z], \mathbb{E}[Y+Z])$, where each point is associated with a conditional probability measure $p(y,A)=\Pr[Z\in A|Y=y]$, $Y$ and $Y'$ are \emph{i.i.d.} random variables with the same distribution   as $Y_i$. 

\emph{Step 1:} {\emph{We will show that there exists an optimal policy \emph{$\pi_{\text{opt}}\in\Pi$} of Problem \eqref{eq_problem_S1} such that the sequence \emph{$({a}_{n,\pi_\text{opt}},{b}_{n,\pi_\text{opt}})$} associated with policy \emph{$\pi_{\text{opt}}$} has at least one limit point in \emph{$\Gamma_{\text{SR}}$}}.


In \eqref{eq_problem_S1}, the observation $Y_{i}$ is independent from the history state and control $Y_1,\ldots, Y_{i-1}$, $Z_1,\ldots, Z_{i-1}$. Therefore, $Y_i$ is the \emph{sufficient statistic} \cite[p. 252]{Bertsekas2005bookDPVol1} for solving Problem \eqref{eq_problem_S1}. This tells us that there exists an optimal policy $\pi_{\text{opt}}=(Z_0,Z_1,\ldots)\in\Pi$ of Problem \eqref{eq_problem_S1} in which the control action $Z_i$ is determined based on only $Y_i$, but not the history state and control $Y_0,\ldots, Y_{i-1}$, $Z_0,\ldots, Z_{i-1}$ \cite{Bertsekas2005bookDPVol1}. We will show that the sequence $({a}_{n,\pi_\text{opt}},{b}_{n,\pi_\text{opt}})$ associated with this policy $\pi_{\text{opt}}$ has at least one limit point in $\Gamma_{\text{SR}}$.}


It is known that $Z_{i}$ takes values in the standard Borel space $(\mathbb{R},\mathcal{{R}})$, where $\mathcal{{R}}$ is the Borel $\sigma$-field. According to \cite[Thoerem 5.1.9]{Durrettbook10}, for each ${i}$ there exists a conditional probability measure $p'_i(y,A)$ such that $p'_i(y,A)=\Pr(Z_{i}\in A|Y_i=y)$ for almost all $y$. That is, the control action $Z_{i}$ is determined based on $Y_i$ and the  conditional probability measure $p'_i(y,A)=\Pr(Z_{i}\in A|Y_i=y)$.


One can use this conditional probability $p'_i(y,A)$ to generate a stationary randomized policy $\pi'_{i,\text{SR}}\in \Pi_{\text{SR}}$. Then, the one-stage expectation $(\mathbb{E}[q(Y_i,Z_i,Y_{i+1})] - \overline{g}_{\text{opt}}\mathbb{E}[Y_{i}+Z_{i}], \mathbb{E}[Y_{i}+Z_{i}])$ is exactly the limit point generated by the stationary randomized policy $\pi'_{i,\text{SR}}$. Thus, $(\mathbb{E}[q(Y_i,Z_i,Y_{i+1})] - \overline{g}_{\text{opt}}\mathbb{E}[Y_{i}+Z_{i}], \mathbb{E}[Y_{i}+Z_{i}])\in \Gamma_{\text{SR}}$ for all $i=0,1,2,\ldots$
Using \eqref{eq_time_average_exp1}, \eqref{eq_time_average_exp2}, and the fact that $\Gamma_{\text{SR}}$ is convex, we can obtain $({a}_{n,\pi_\text{opt}},{b}_{n,\pi_\text{opt}})\in \!\Gamma_{\text{SR}}$ for all $n=1,2,3\ldots$ In other words, the sequence $({a}_{n,\pi_\text{opt}},{b}_{n,\pi_\text{opt}})$ is within $\Gamma_{\text{SR}}$.
Since $\Gamma_{\text{SR}}$ is a compact set, the sequence $({a}_{n,\pi_\text{opt}},{b}_{n,\pi_\text{opt}})$ must have a convergent subsequence, whose limit is in $\Gamma_{\text{SR}}$.


\emph{Step 1: We will show that $\Gamma_{\text{SR}}$ is a convex and compact set}.

It is easy to show that $\Gamma_{\text{SR}}$ is convex by considering a stationary randomized policy associated with $p(y,A)$ that is a mixture of two stationary randomized policies associated with $p_1(y,A)$ and $p_2(y,A)$, i.e., there exists $0<\lambda<1$ such that  $p(y,A)=\lambda p_1(y,A) + (1-\lambda) p_2(y,A)$.

For compactness, let $((d_j,e_j),j=1,2,\cdots)$ be any sequence of points in $\Gamma_{\text{SR}}$, we need to show that there is a convergent subsequence $(d_{j_k},e_{j_k})$ whose limit is also in $\Gamma_{\text{SR}}$.
Since $(d_j,e_j)\in\Gamma_{\text{SR}}$, there must exist $(Y,Z_{(j)},Y')$ with conditional probability $p_{j}(y,A)=\Pr[Z_{(j)}\in A|Y=y]$, such that $d_j=\mathbb{E}[q(Y,Z_{(j)},Y')]-\overline{p}_{\text{opt}}\mathbb{E}[Y+Z_{(j)}]$, $e_j=\mathbb{E}[Y+Z_{(j)}]$.
Let $\mu_j$ be the joint probability measure of $(Y,Z_{(j)},Y')$, then $(d_j,e_j)$ is uniquely determined by $\mu_j$.
For any $L$, we can obtain
\begin{align}
&\mu_j(Y\leq L, Z_{(j)}\leq L,Y'\leq L)\nonumber\\
\geq& \mu_j(Y+Z_{(j)}+Y'\leq L)\nonumber\\
\geq& 1- \frac{\mathbb{E}[Y+Z_{(j)}+Y']}{L},~\forall~j,\nonumber
\end{align}
where the last inequality is due to Markov's inequality. By \eqref{eq_finite}, we have $\mathbb{E}[Z_{(j)}]\leq M<\infty$ for all $j$. Using this and $\mathbb{E}[Y]<\infty$, we can obtain that
for any $\epsilon$, there is an $L$ such that $$\liminf_{j\rightarrow\infty} \mu_j(|Y|\leq L, |Z_{(j)}|\leq L,|Y'|\leq L)\geq 1-\epsilon.$$ Hence, the sequence of measures $\mu_j$ is tight. By Helly's selection theorem \cite[Theorem 3.9.2]{Durrettbook10}, there is a subsequence of measures $\mu_{j_k}$ that converges weakly to a limit measure $\mu_\infty$.


Let $(Y,Z_{(\infty)},Y')$ and $p_\infty(y,A)=\Pr[Z_\infty\in A|Y=y]$ denote the random vector and conditional probability corresponding to the limit measure $\mu_\infty$, respectively. We can define $d_\infty=\mathbb{E}[q(Y,Z_{(\infty)},Y')]-\overline{p}_{\text{opt}}\mathbb{E}[Y+Z_{(\infty)}]$, $e_\infty=\mathbb{E}[Y+Z_{(\infty)}]$.

Since the function $q(y,z,y')$ is in the form of an integral, it is continuous and thus measurable. Using the continuous mapping theorem \cite[Theorem 3.2.4]{Durrettbook10}, we can obtain that $q(Y,Z_{(j_k)},Y')$ converges weakly to $q(Y,Z_{(\infty)},Y')$. Then, using the condition \eqref{eq_bound}, together with the dominated convergence theorem (Theorem 1.6.7 of \cite{Durrettbook10}) and Theorem 3.2.2 of \cite{Durrettbook10}, we can obtain

$\lim_{k\rightarrow\infty}(d_{j_k},e_{j_k})=(d_\infty,e_\infty)$. 

Hence, $((d_j,e_j),j=1,2,\cdots)$ has a convergent subsequence.
Further, we can generate a stationary randomized policy $\pi_{\infty,\text{SR}}$ by using the conditional probability $p_\infty(y,A)$ corresponding to $\mu_\infty$. Then, $(d_\infty,e_\infty)$ is the limit point generated by the stationary randomized policy $\pi_{\infty,\text{SR}}$, which implies
$(d_\infty,e_\infty)\in\Gamma_{\text{SR}}$. In summary, any sequence $(d_j,e_j)$ in $\Gamma_{\text{SR}}$ has a convergent subsequence $(d_{j_k},e_{j_k})$ whose limit $(d_\infty,e_\infty)$ is also in $\Gamma_{\text{SR}}$. Therefore, $\Gamma_{\text{SR}}$ is a compact set.


\end{proof}}


\ignore{
\begin{theorem}(Optimality of Stationary Deterministic Policies) \label{lem_SD}
If $p: \mathbb{R}\mapsto \mathbb{R}$ is non-decreasing and the service times $Y_i$ are {i.i.d.}, then there exists a stationary deterministic policy that is optimal for solving \eqref{eq_opt_stopping3}.
\end{theorem}
\begin{proof}

\end{proof}}

\fi
{"config": "arxiv", "file": "1806.06243/sec_analysis_1.tex"}