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

In this section, we prove Theorem \ref{thm1} in three steps: 

First, we  show that no sample should be generated when the server is busy, which simplifies the optimal online sampling problem. Second, we study the Lagrangian dual problem of the simplified problem, and decompose the Lagrangian dual problem into a series of \emph{mutually independent} per-sample control problems. Each of these per-sample control problems has a simple solution. Next, we show that the Lagrangian duality gap of our Markov decision problem is zero. By this, Problem \eqref{eq_problem} is solved. The details are as follows.

\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$. Then,
$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]}\\
\text{s.t.}~~& \lim_{i\rightarrow \infty} \frac{1}{i}\sum_{j=1}^{i} \mathbb{E}\left[Y_j+Z_j\right] \geq \frac{1}{f_{\max}}.
\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]\!\!\!\!\\
\text{s.t.}~&\lim_{i\rightarrow \infty} \frac{1}{i}\sum_{j=1}^{i} \mathbb{E}\left[Y_j+Z_j\right] \geq \frac{1}{f_{\max}},\nonumber
\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{Lagrangian Dual Problem of  \eqref{eq_SD} for \emph{$c = \bar p_{\text{opt}}$} }
Although \eqref{eq_SD} is not a convex optimization problem, it is possible to use the Lagrangian dual approach to solve \eqref{eq_SD} and show that it admits no duality gap. 

When $c = \bar p_{\text{opt}}$, define the following Lagrangian
\begin{align}\label{eq_Lagrangian}
& L(\pi;\lambda) \nonumber\\
=&\lim_{i\rightarrow \infty}\frac{1}{i}\sum_{j=0}^{i-1}\!\mathbb{E}\!\left[q(Y_j,Z_j,Y_{j+1})\!-\! (\bar p_{\text{opt}} + \lambda)(Y_j\!+\!Z_j)\right] + \frac{\lambda}{f_{\max}},
\end{align}
where $\lambda\geq0$ is the dual variable. 
Let
\begin{align}\label{eq_primal}
g(\lambda) \triangleq \inf_{\pi\in\Pi_1}  L(\pi;\lambda).
\end{align}
Then, the Lagrangian dual problem of \eqref{eq_SD} is defined by
\begin{align}\label{eq_dual}
d \triangleq \max_{\lambda\geq 0}g(\lambda),
\end{align}
where $d$ is the optimum value of \eqref{eq_dual}. 
Weak duality \cite{Bertsekas2003,Boyd04} implies that $d \leq h(\bar p_{\text{opt}})$. In Section \ref{sec:dual}, we will establish strong duality, i.e., $d = h(\bar p_{\text{opt}})$.


Next, we present the optimal solution to \eqref{eq_primal}.  

\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_primal}.
\end{lemma}
\begin{proof}


In \eqref{eq_primal}, 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}} + \lambda)(Y_j+Z_j)\right]
\end{align}
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_primal}. 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]$. Also, there exists an optimal  solution $(Z_1,Z_2,\ldots)$ to \eqref{eq_primal}, 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}} + \lambda)(Y_i+Z_i)\big|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]$ solving \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_primal}, which completes the proof.
\end{proof}


Next, similar to \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_primal} 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}} + \lambda$}.
\end{lemma}
\begin{proof}

Using \eqref{eq_sum} and $\beta = \bar p_{\text{opt}} + \lambda$, \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=Y_{i}}^{Y_i+Z_i+Y_{i+1}-1}\!\![p(n)- \beta] \Bigg| Y_i\right].
\end{align}
Because $p: \mathbb{R}\mapsto \mathbb{R}$ is non-decreasing and the choice of $Z_i$ given by \eqref{lem4_eq1}, we have
\begin{align}
&\mathbb{E}\!\left[p(n)-\beta |Y_i\right] \leq 0,~ n = Y_i, \ldots, Y_i + Z_i + Y_{i+1}-1, \nonumber\\
&\mathbb{E}\!\left[p(n)-\beta |Y_i\right] \geq 0,~ n \geq Y_i + Z_i + Y_{i+1}.\nonumber
\end{align}
This tells us that the optimal $Z_i$ for solving  \eqref{eq_opt_stopping4} is given by \eqref{lem4_eq1}, which completes the proof.
\end{proof}

\subsection{Zero Duality Gap between \eqref{eq_SD} and \eqref{eq_dual}} \label{sec:dual}


Similar to Theorem 7 in \cite{Sun_reportISIT17}, strong duality can be established in the following lemma:
\begin{lemma}\label{thm_zero_gap}
If \emph{$c= \bar p_{\text{opt}}$}, the following assertions are true:
\begin{itemize}
\vspace{0.5em}
\item[(a).] The duality gap between \eqref{eq_SD} and \eqref{eq_dual} is zero, i.e., \emph{$d = h(\bar p_{\text{opt}})$}.
\vspace{0.5em}
\item[(b).] A common optimal solution to \eqref{eq_problem},  \eqref{eq_problem_S1}, and \eqref{eq_SD} is given by \eqref{thm1_eq4}, \eqref{thm1_eq5}, and \eqref{lem4_eq1}. The optimal value of \eqref{eq_problem} is given by \eqref{thm1_eq3}.
\end{itemize}

\end{lemma}

\begin{proof}
The key proof idea is to show that \eqref{eq_SD} has a \emph{geometric multiplier} \cite[Definition 6.1.1]{Bertsekas2003}.\footnote{Note that geometric multiplier is   different from the traditional Lagrangian multiplier.} According to \cite[Proposition 6.2.3]{Bertsekas2003}, if the set of geometric multipliers is non-empty, then the duality gap must be zero, no matter for convex or non-convex optimization problems. 
The proof details are provided in Appendix \ref{app4}.
\end{proof}

Hence, Theorem~\ref{thm1} follows from Lemma \ref{thm_zero_gap}.


\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.tex"}