text:
\section{Proof of Theorem \ref{Ori_Lag}}
\label{proof_ori_lag}
First, we provide some definitions of terms which will be used in our proof. The definitions comply with \cite{sennott1993constrained}: Let $G\subset \mathcal{S}$ be nonempty set of states. Give $\mathbf{s}\in\mathcal{S}$, $\mathcal{R}(\mathbf{s},G)$ is defined as a class of policies such that $\mathbb{P}^\pi(\mathbf{s}_t\in G\, \text{for some}\, t\geq 1: \mathbf{s}_0=\mathbf{s})=1$ and the expected time $\tau_{\mathbf{s},G}(\pi)$ of the first passage from $\mathbf{s}$ to $G$ using $\pi$ is finite. Further, $\mathcal{R}^\star(\mathbf{s},G)\subset\mathcal{R}(\mathbf{s},G)$ are policies that have finite expected average AoI and finite expected energy of a first passage from $\mathbf{s}$ to $G$.
By \cite{sennott1993constrained}, it suffices to show the following conditions hold.
\begin{itemize}
    \item A1: For all $r>0$, the set $B(r)=\{\mathbf{s}: \exists\, u\,\, \text{s.t.} \,\,C_{\Delta}(\mathbf{s},u)+C_{E}(\mathbf{s},u)\leq r \}$ is finite.
    \item A2: There exists a stationary deterministic policy $g_1\in\Pi$ which induces a Markov chain with properties: the state space incurred by $g_1$ consists of a single (non-empty) positive recurrent class $\mathcal{X}$ and a set $\mathcal{Y}$ of transient states such that $g_1\in\mathcal{R}^\star(\mathbf{s}',\mathcal{X})$, for $\mathbf{s}'\in \mathcal{Y}$, Moreover, both the average age and energy costs on $\mathcal{X}$ are finite.
    \item A3: Given any two states $\mathbf{s}_1\neq\mathbf{s}_2$, there exists a policy $g_2$ such that $g_2\in\mathcal{R}^\star(\mathbf{s}_1,\{\mathbf{s}_2\})$
   \item A4: If a stationary deterministic policy $g_3$ has at least one positive recurrent state then it has a single positive recurrent class $\mathcal{X}$. Moreover, if initial state $\mathbf{s}_0\notin \mathcal{X}$, then $g_3\in\mathcal{R}^\star(\mathbf{s}_0,\mathcal{X})$.
 \item A5: There exists a policy $g_4$ such that $\bar{A}(g_4)<\infty$ and $\bar{E}(g_4)< E_{\text{max}}$.
\end{itemize}
For A1, given $r$, for any $\mathbf{s}'=(\Delta',\Lambda')\in B(r),\Delta'\leq \min_u\{C_{\Delta}(\mathbf{s}',u)+C_{E}(\mathbf{s}',u)\}\leq r$ by definition of $B(r)$. This means given $r$, the age of any state in $B(r)$ is upper bounded by $r$. Together with $\Delta\in\mathbb{N}^+$ and $\Lambda\in\{0,1,\cdots,M\}$, $B(r)$ is finite.

For A2, consider policy $g_1$ that takes action $u=1$ if $\Lambda=M$; otherwise, $u=0$. The set $\mathcal{X}=\{(\Delta,\Lambda):\Delta\in\mathbb{N}^+,\Lambda'=0,1,...,M\}$ is recurrent. This is because that the next state after $u=1$ is $(o,\Lambda')\in \mathcal{X}$ due to $0<p<1$, and the next state after $u=0$ is $(o+1,\Lambda')\in \mathcal{X}$, where $\Lambda'\in\{0,1,...,M\}$, $o\in\mathbb{N}^+$. Thus, $\mathcal{Y}=\emptyset$ and $g_1\in\mathcal{R}^\star(\mathbf{s}',\mathcal{X})$, given $\mathbf{s}'\in \mathcal{Y}$. Besides, $\bar{A}(g_1)=1/p_s$, $\bar{E}(g_1)\leq 1$ are finite, where $p_s=P_\Lambda(M)(1-p)$. Hence, A2 holds.

For A3, given $\mathbf{s}_1=(\Delta_1,\Lambda_1)$ and $\mathbf{s}_2=(\Delta_2,\Lambda_2)$, consider the policy $g_2$ that uses $g_1$ in the proof of A2 till entry to state $(1,\cdot)$, and then takes $u=0$ till $\Delta=\Delta_2$, after which policy repeats previous two stages. Based on analysis in proof of A2, it takes finite time to enter state $(1,\cdot)$ from $\mathbf{s}_1$. In addition, it takes $\Delta_2-1$ slots to reach the age $\Delta_2$. Thus, the two stages take finite time. Moreover, the probability that $\mathbf{s}\neq\mathbf{s}_2$ at the end of the two stage exponentially decreases with the number of the two stage being conducted. Hence, A3 holds.

For A4, the only way for $g_3$ to generate at least one recurrent class is that successful transmission occurs repeatedly under $g_3$. Note after successful transmission, state becomes $(1,\Lambda)$, $\Lambda\in\{0,1,\cdots,M\}$. Thus, any recurrent class must include $(1,\Lambda)$. Hence, there is only one recurrent class. Moreover, since $g_3$ will take $u=1$ repeatedly, for any initial state $\mathbf{s}_0\notin \mathcal{X}$, it takes finite time from $\mathbf{s}_0$ to $(1,\Lambda)$. Hence, A4 holds.

For A5, consider policy $g_4$ that takes action $u=1$ if $2\lceil 1/E_\text{max}\rceil$ divides $\Delta$ and $\Lambda=M$; otherwise, $u=0$. We have $\bar{E}(g_4)\leq 1/2\lceil 1/E_\text{max}\rceil \leq E_\text{max}/2<E_\text{max}$ and $\bar{A}(g_4)=\lceil 1/E_\text{max}\rceil+2\lceil 1/E_\text{max}\rceil^2(2/p_s-1)<\infty$, where $p_s$ is defined in proof of A2. This completes our proof.

\section{Proof of Theorem \ref{cost_cal}}
\label{opt_thres0}

The state transition diagram under the policy in the form of \eqref{optPol} is given in Fig. \ref{fig:trans_diag}, where $k$ is a threshold.

\begin{figure*}
    \centering
    \includegraphics[width=0.95\textwidth]{Trans_Diag.pdf}
    \caption{State Transition Diagram. Different lines correspond to different state transition probabilities as given in the legend.}
    \label{fig:trans_diag}
\end{figure*}

Define the steady state probability as follows:
\begin{align}
    x_{\Delta,\Lambda}\triangleq \mathbb{P}(\mathbf{s}=(\Delta,\Lambda))
\end{align}
Based on the state transition diagram, balance equations can be obtained as follows:
\begin{align}
 \! \! & x_{\Delta+1,\Lambda}\!=\!\sum_{b=0}^M x_{\Delta,b} P_\Lambda(\Lambda), & \forall 1\!\leq\! \Delta\!<\! k\\
 \! \! & x_{\Delta+1,\Lambda}\!=\!(\sum_{b=0}^M x_{\Delta,b}\!-\!(1\!-\! p)\!\!\!\sum_{b=h_{{l_k}-1}}^M \!\!x_{\Delta,b})P_\Lambda(\Lambda), & \forall k\!\leq \!\Delta\!<\!\delta_{l_k}\\
 \! \! &  \cdots \notag\\
  \! \! & x_{\Delta+1,\Lambda}\!=\!(\sum_{b=0}^M x_{\Delta,b}\!-\!(1\!-\!p)\!\!\sum_{b=h_L}^M \!\!x_{\Delta,b})P_\Lambda(\Lambda), & \forall  \delta_L\!\leq \!\Delta\\
\! \!  &\sum_{\Delta=1}^\infty \sum_{\Lambda=0}^M x_{\Delta,\Lambda}=1 &
\end{align}
Let $z_\Delta=\sum_{\Lambda=0}^M x_{\Delta,\Lambda}$. Then, the balance equations can be transformed as
\begin{align}
   & z_{\Delta+1}=z_\Delta & \forall 1\leq \Delta< k\label{be1}\\
   & z_{\Delta+1}=z_\Delta B_{{l_k}-1} & \forall k\leq \Delta<\delta_{l_k}\label{be2}\\
   &\ \ \ \vdots\notag\\
   & z_{\Delta+1}=z_\Delta B_{L} & \forall \delta_L\leq \Delta\\
   & \sum_{\Delta=1}^\infty z_\Delta=1 &\label{be3}
\end{align}
where $B_{r}=1-(1-p)\sum_{\Lambda=h_{r}}^M P_\Lambda(\Lambda)$, for ${l_k}-1\leq r\leq L$.

Solving the equations \eqref{be1}-\eqref{be3}, we obtain
\begin{align}
    z_1=&\Big[k+\frac{B_{{l_k}-1}}{1-B_{{l_k}-1}}
    +\mathbbm{1}_{\{{l_k}\leq L\}}B_{{l_k}-1}^{\delta_{l_k}-k}\Big(-\frac{1}{1-B_{{l_k}-1}}\notag\\
    &+\sum_{j={l_k}}^{L}\frac{1-\mathbbm{1}_{\{j<L\}}B_{j}^{\delta_{j+1}-\delta_j}}{1-B_j}w({l_k},j)\Big)\Big]^{-1},
\end{align}
where $\mathbbm{1}_{\{\cdot\}}$ is indicator function and $w(i,j)$ is defined as
\begin{align}
   w(i,j)=\mathbbm{1}_{\{i<j\}}\prod_{v=i}^{j-1}B_{v}^{\delta_{v+1}-\delta_v}+\mathbbm{1}_{\{i\geq j\}},
\end{align}
and for $\Delta>1$, $z_\Delta$ is given by
\begin{align}
    & z_\Delta=z_1,   & \forall 1<\Delta<k\\
    & z_\Delta=z_1 B_{{l_k}-1}^{\Delta-k}, &\forall k\leq \Delta<\delta_{j+1} \\
    & z_\Delta=w({l_k},j)B_{{l_k}-1}^{\delta_{l_k}-k}B_j^{\Delta-\delta_j}, &\forall \delta_j\leq \Delta<\delta_{j+1} \\
    & z_\Delta=w({l_k},L)B_{{l_k}-1}^{\delta_{l_k}-k}B_L^{\Delta-\delta_L}, &\forall \delta_L\leq \Delta
\end{align}

With this, the resultant average Lagrangian cost using the policy $\pi_k$ in the form of \eqref{optPol} with threshold $k\in\mathbb{N}^+$ is
\begin{align}
    &\bar{L}(\pi_k;\beta)\notag\\
    =&\sum_{\Delta=1}^{k-1}\Delta z_\Delta+\sum_{\Delta=k}^\infty \Big(\Delta+\beta \sum_{b= D(\Delta)}^{M}P_\Lambda(b)\Big)z_\Delta\\
    =&\sum_{\Delta=1}^{k-1}\Delta z_\Delta+\mathbbm{1}_{\{{l_k}=L+1\}}\cdot\sum_{\Delta=k}^\infty \Big(\Delta+\beta F(h_{{l_k}-1})\Big)z_k\notag\\
    &+\mathbbm{1}_{\{{l_k}\leq L\}}\Big(\mathbbm{1}_{\{{l_k}<L\}}\cdot\sum_{r={l_k}}^{L-1}\sum_{\Delta=\delta_r}^{\delta_{r+1}-1} (\Delta+\beta F(h_r))z_{\delta_r}\notag\\
    &+\sum_{\Delta=k}^{\delta_{l_k}-1} (\Delta+\beta F( h_{{l_k}-1}))z_k+\sum_{\Delta=\delta_L}^{\infty} (\Delta+\beta F(h_L))z_{\delta_L}\Big)\\
    =&z_1\Bigg\{\frac{k(k-1)}{2}+\frac{1}{(1-B_{{l_k}-1})^2}+\frac{k-1+\beta F(h_{{l_k}-1})}{1-B_{{l_k}-1}}\notag\\
    &+\mathbbm{1}_{\{{l_k}\leq L\}}B_{{l_k}-1}^{\delta_{l_k}-k}\bigg[-\frac{1}{(1-B_{{l_k}-1})^2}-\frac{\delta_{l_k}-1+\beta F(h_{{l_k}-1})}{1-B_{{l_k}-1}}\notag\\
    &+\sum_{j={l_k}}^{L}w({l_k},j)\Big(\frac{1-\mathbbm{1}_{\{j<L\}}B_{j}^{\delta_{j+1}-\delta_j}}{(1-B_j)^2}\notag\\
    &+\frac{-\mathbbm{1}_{\{j<L\}}B_{j}^{\delta_{j+1}-\delta_j}(\delta_{j+1}-1+\beta F(h_j))}{1-B_j}\notag\\
    &+\frac{\delta_j-1+\beta F(h_j)}{1-B_j}\Big)\bigg]\Bigg\}
\end{align}
where $F(h)\triangleq \sum_{b=h}^{M}P_\Lambda(b)$

And the average energy is
\begin{align}
    &\bar{E}(\pi_k)\notag\\
    =&\sum_{\Delta=k}^\infty \beta \sum_{b= D(\Delta)}^{M}P_\Lambda(b)z_\Delta\\
    =&z_1\Bigg\{\frac{\beta F(h_{{l_k}-1})}{1-B_{{l_k}-1}}+\mathbbm{1}_{\{{l_k}\leq L\}}B_{{l_k}-1}^{\delta_{l_k}-k}\bigg(-\frac{\beta F(h_{{l_k}-1})}{1-B_{{l_k}-1}}\notag\\
    &+\sum_{j={l_k}}^{L}w({l_k},j)\beta F(h_j)\frac{1-\mathbbm{1}_{\{j<L\}}B_{j}^{\delta_{j+1}-\delta_j}}{1-B_j}\bigg)\Bigg\}
\end{align}

\section{Proof of Theorem \ref{new}}
\label{proof_min_ub}
We use $\mathcal{F}(k)$ to denote the resultant cost expression $\bar{L}(\pi_k;\beta)$ for $k\geq \delta_L$. Then, $\mathcal{F}(k)$ is
\begin{align}
   &\mathcal{F}(k)=\notag\\
    &\frac{1-B_L}{B_L+k(1-B_L)}\left(\frac{k(k-1)}{2}+\frac{\beta F(h_{L})+k}{1-B_L}+\frac{B_L}{(1-B_L)^2}\right),
\end{align}

Next, we will find the minimum of $\mathcal{F}(k)$ for $k\geq \delta_L$.
To this end, we first show that $\mathcal{F}(k)$ firstly decreases and then increases with $k\in\mathbb{N}$. Then, we get optimal threshold on $[\delta_L,\infty)$ by comparing the $y$ that optimizes $\mathcal{F}(k)$ in the range $k\in\mathbb{N}$ with $\delta_L$.
Actually, after some basic calculation, we have
\begin{align}
  \mathcal{F}(k+1)-\mathcal{F}(k) = \frac{0.5k^2+(0.5+\frac{B_L}{1-B_L})k-\frac{\beta F(h_L)}{1-B_L}}{(k+1+\frac{B_L}{1-B_L})(k+\frac{B_L}{1-B_L})}\label{costfun}
\end{align}

Note that $1-B_L=(1-p)\sum_{b=h_L}^M P_\Lambda(b)>0$. Thus, the denominator is positive. Let $\mathcal{H}(k)=0.5k^2+(0.5+\frac{B_L}{1-B_L})k-\frac{\beta F(h_L)}{1-B_L}$. Since
$\mathcal{\delta}(k+1)-\mathcal{H}(k)=k+1+\frac{B_L}{1-B_L}>0$ for $k\geq 0$ and $\mathcal{H}(0)<0$, there exists $y\in\mathbb{N}$ such that $\mathcal{H}(k)<0$ for $k< y$ and $\mathcal{H}(k)\geq 0$ for $k\geq y$. Therefore, \eqref{costfun} is negative when $k<y$ and then becomes positive when $k\geq y$. This implies that $\mathcal{F}(k)$ firstly decreases and then increases with $k\in\mathbb{N}$, and $\mathcal{F}(y)$ is the minimum for $k\in \mathbb{N}$. Note that $y=\min\{k\in\mathbb{N}: \mathcal{H}(k)\geq 0\}$.
Let $\sigma$ denote the solution to $\mathcal{H}(\sigma)=0$. Then, we have
\begin{align}
    \sigma=-\frac{1+B_L}{2(1-B_L)}+\left(\frac{B_L^2}{(1-B_L)^2}+\frac{B_L+2\beta F(h_L)}{1-B_L}+\frac{1}{4}\right)^{0.5},
\end{align}
and $y=\lceil \sigma\rceil$.

If $y\leq \delta_L$, $\mathcal{F}$ increases with $k$ on the domain $[\delta_L,\infty)$ and the optimal threshold $k_{UB}$ in the domain is $\delta_L$; if $y> \delta_L$, $\mathcal{F}$ first decreases and increases with $k$ on the domain $[\delta_L,\infty)$, and thus the optimal threshold $k_{UB}$ is $y$. Hence, the optimal threshold on the domain $[\delta_L,\infty)$, which is denoted by $k_{UB}$, is
\begin{equation}
    k_{UB} = \max \{\delta_L,y\}
\end{equation}

\section{Proof of Theorem \ref{lem:special_case}}
\label{app: special_case}
To explore how the optimal threshold varies with $W$, $p$, respectively. We regard the optimal threshold as a function of $W$ and $p$, i.e.,
\begin{align}
    \mathcal{G}(W,p)\triangleq &-\frac{1+R}{2(1\!-\!R)}\!+\!\left(\!\frac{R^2}{(1\!-\!R)^2}\!+\!\frac{R\!+\!2\beta W}{1\!-\!R}\!+\!\frac{1}{4}\right)^{0.5},\\
    = & \frac{-2+(1-p)W}{2(1-p)W}+\!\Bigg(\!\frac{(1-(1-p)W)^2}{(1-p)^2W^2}\!\notag\\
    &+\!\frac{1-(1-p)W\!+\!2\beta W}{(1-p)W}\!+\!\frac{1}{4}\Bigg)^{0.5},
\end{align}
and then study partial derivatives $\frac{\partial \mathcal{G}(W,p)}{\partial W}$ and $\frac{\partial \mathcal{G}(W,p)}{\partial p}$.

(i) We have $\frac{\partial \mathcal{G}(W,p)}{\partial p}$ as
\begin{align}
    &\frac{\partial \mathcal{G}(W,p)}{\partial p}=\notag\\
    &\frac{1}{(1-p)^2W}\Bigg(-1+\frac{2-(1-p)W+2\beta(1-p)W^2}{\sqrt{(2-(1-p)W)^2+8\beta(1-p)W^2}}\Bigg)
    \label{eqn:der_p}
\end{align}
Since
\begin{align}
    &\big(2-(1-p)W\big)^2+8\beta(1-p)W^2\notag\\
    &-\big(2-(1-p)W+2\beta(1-p)W^2\big)^2\notag\\
    =& 4\beta(1-p)^2W^3(1-\beta W)
\end{align}
If $W >\frac{1}{\beta}$, then \eqref{eqn:der_p}$>0$. In the case, the $\mathcal{G}(W,p)$ increases with $p$. If $ W <\frac{1}{\beta}$, then \eqref{eqn:der_p}$<0$. In the case, the $\mathcal{G}(W,p)$ decreases with $p$.

(ii) It suffices to show that the maximum of
$$\Bigg\lceil\!\!-\!\frac{1+R}{2(1\!-\!R)}\!+\!\left(\!\frac{R^2}{(1\!-\!R)^2}\!+\!\frac{R\!+\!2\beta W}{1\!-\!R}\!+\!\frac{1}{4}\right)^{0.5}\!\!\Bigg \rceil$$ in \eqref{opt_threval_spec} is not larger than 1. In fact, when $\beta <\frac{1}{W}$ and $0<R<1$, we have
\begin{align}
    \frac{R^2}{(1\!-\!R)^2}\!+\!\frac{R\!+\!2\beta W}{1\!-\!R}\!+\!\frac{1}{4}&<\frac{R^2}{(1\!-\!R)^2}\!+\!\frac{R\!+2}{1\!-\!R}\!+\!\frac{1}{4}\\
    &\leq\left(1+\!\frac{1+R}{2(1\!-\!R)}\right)^2.
\end{align}
This completes the proof of (ii).

For (iii), we show that $\frac{\partial \mathcal{G}(W,p)}{\partial W}\geq 0$.
(iii) It suffices to show that $\frac{\partial \mathcal{G}(W,p)}{\partial W}\geq 0$.
In fact, we have
\begin{align}
    &\frac{\partial \mathcal{G}(W,p)}{\partial W}=\notag\\
    &\frac{1}{(1-p)W^2}\Bigg(1+\frac{-2+(1-p)W}{\sqrt{(2-(1-p)W)^2+8\beta(1-p)W^2}}\Bigg)
\end{align}
Since $0\!<\!\!\frac{2-(1-p)W}{\sqrt{(2-(1-p)W)^2+8\beta(1-p)W^2}}\!< \!1$, we have $\frac{\partial \mathcal{G}(W,p)}{\partial W}\!\!>\!0$.

\section{Proof of Lemma \ref{property_00}}
\label{proof_prop_dis_subprob}
By Proposition \ref{existence_discount_00}, we will use induction to show the results. Obviously, $V_0^{\alpha}(\mathbf{s})$ has properties (i) and (ii) since $V_0^{\alpha}(\mathbf{s})=0$. Then, it remains to show that given $V_n^{\alpha}(\mathbf{s})$ has the properties (i) and (ii), $V_{n+1}^{\alpha}(\mathbf{s})$ has these properties, $\forall n\geq 0$.

(i) Let $\Delta_1\geq \Delta_2$. By \eqref{iteration00}, to show that the result holds for $V_{n+1}^{\alpha}$, it suffices to show that for any $u\in A_{(\Delta_1,\Lambda)}$, there exists an action $u'\in A_{(\Delta_2,\Lambda)}$ such that $Q_{n+1}^{\alpha}(\Delta_1,\Lambda;u)\geq Q_{n+1}^{\alpha}(\Delta_2,\Lambda;u')$.

For any state, $0\in A_{(\Delta_1,\Lambda)}$. We have
\begin{align}
   &Q_{n+1}^{\alpha}(\Delta_1,\Lambda;0)\nonumber\\
   =&\Delta_1+\alpha\mathbb{E}[ V_n^{\alpha}(\Delta_1+1,\Lambda')]\\
  =&\Delta_1+\alpha\sum_{k=0}^{M} P_\Lambda(k)V_n^{\alpha}(\Delta_1+1,k)\\
  \geq&\Delta_2+\alpha\sum_{k=0}^{M} P_\Lambda(k)V_n^{\alpha}(\Delta_2+1,k)\label{appD_1}\\
  =& \Delta_2+\alpha\mathbb{E}[ V_n^{\alpha}(\Delta_2+1,\Lambda')]\\
  =&Q_{n+1}^{\alpha}(\Delta_2,\Lambda;0)
\end{align}

The inequality \eqref{appD_1} holds by our assumption that $V_n^{\alpha}$ has non-decreasing property.

Since $D(\Delta_1)\geq D(\Delta_2)$, if $1\in A_{(\Delta_1,\Lambda)}$, then $1\in A_{(\Delta_2,\Lambda)}$. In this case, we have
\begin{align}
   &Q_{n+1}^{\alpha}(\Delta_1,\Lambda;1)\nonumber\\
   =&\Delta_1+\beta+\alpha p \mathbb{E}[ V_n^{\alpha}(\Delta_1+1,\Lambda')]\nonumber\\
   &+\alpha (1-p) \mathbb{E}[ V_n^{\alpha}(1,\Lambda')]\\
   \geq & \Delta_2+\beta+\alpha p \mathbb{E}[ V_n^{\alpha}(\Delta_2+1,\Lambda')]\nonumber\\
   &+\alpha (1-p) \mathbb{E}[ V_n^{\alpha}(1,\Lambda')]\\
   =&Q_{n+1}^{\alpha}(\Delta_2,\Lambda;1)
\end{align}

(ii) Let $\Lambda_1\leq \Lambda_2$.
\begin{align}
   Q_{n+1}^\alpha(\Delta,\Lambda_1;0)&=\Delta+\alpha\mathbb{E}[ V_n^\alpha(\Delta+1,\Lambda')]\nonumber\\
  &= Q_{n+1}^\alpha(\Delta,\Lambda_2;0)
\end{align}
If $\Lambda_1\geq D(\Delta)$, then $\Lambda_2\geq D(\Delta)$.
\begin{align}
   Q_{n+1}^\alpha(\Delta,\Lambda_1;1)=&\Delta+\beta+\alpha p \mathbb{E}[ V_n^\alpha(\Delta+1,\Lambda')]\nonumber\\
   &+\alpha (1-p) \mathbb{E}[ V_n^\alpha(1,\Lambda')]\nonumber\\
   =&Q_{n+1}^\alpha(\Delta,\Lambda_2;1)
\end{align}
By \eqref{iteration00}, $V_{n+1}^\alpha$ has property (ii).

\section{Proof of Lemma \ref{disc_stru0}}
\label{proof_disc_stru}
To show the result, we first show that given $\Lambda$, the optimal action is increasing function of the age when the age satisfies $\Lambda\geq D(\Delta)$, and then show that the optimal action at certain age is the same for any $\Lambda$ as long as distortion requirement is satisfied.

(i) We show that given $\Lambda$, if $u=1$ is optimal for the state $(\Delta,\Lambda)$, then $u=1$ is also optimal for state $(\Delta+1,\Lambda)$, where $\Delta+1\leq D^{-1}(\Lambda)$.

Since $u=1$ is optimal for $(\Delta,\Lambda)$, we have
\begin{align}
    &Q^{\alpha}(\Delta,\Lambda;1)-Q^{\alpha}(\Delta,\Lambda;0)\nonumber\\
    =&\beta\!+\!\alpha (1\!-\!p)(\mathbb{E}V^{\alpha}(1,\Lambda')\!-\!\mathbb{E}V^{\alpha}(\Delta+1,\Lambda'))\label{thre_01}\leq 0
\end{align}
By Lemma \ref{property_00}, we have
\begin{align}
    &Q^{\alpha}(\Delta+1,\Lambda;1)-Q^{\alpha}(\Delta+1,\Lambda;0)\nonumber\\
    =&\beta\!+\!\alpha (1\!-\!p)(\mathbb{E}V^{\alpha}(1,\Lambda')\!-\!\mathbb{E}V^{\alpha}(\Delta+2,\Lambda'))\\
    \leq & \beta\!+\!\alpha (1\!-\!p)(\mathbb{E}V^{\alpha}(1,\Lambda')\!-\!\mathbb{E}V^{\alpha}(\Delta+1,\Lambda'))\leq 0
\end{align}

(ii) Next, we show that for $\Lambda<M$ and $\Delta\leq D^{-1}(\Lambda)$, $u^\star_{\alpha}(\Delta,\Lambda;\beta)=u^\star_{\alpha}(\Delta,M;\beta)$, where $u^\star_{\alpha}(\cdot;\beta)$ is optimal decision rule.

Since for any $\Lambda\in \{0,1,\cdots,M\}$, we have
\begin{align}
    &Q^{\alpha}(\Delta,\Lambda;1)-Q^{\alpha}(\Delta,\Lambda;0)\nonumber\\
    =&\beta\!+\!\alpha (1\!-\!p)(\mathbb{E}V^{\alpha}(1,\Lambda')\!-\!\mathbb{E}V^{\alpha}(\Delta+1,\Lambda')),
\end{align}
which does not depend on $\Lambda$. Thus,
$Q^{\alpha}(\Delta,\Lambda;1)-Q^{\alpha}(\Delta,\Lambda;0)=Q^{\alpha}(\Delta,M;1)-Q^{\alpha}(\Delta,M;0)$. Hence, $u^\star_{\alpha}(\Delta,\Lambda;\beta)=u^\star_{\alpha}(\Delta,M;\beta)$.

\section{Proof for verification of conditions in \cite{sennott1989average}}
\label{proof_cond}
We need to verify the conditions listed below:
	\begin{itemize}
		\item A1: $V^{\alpha}(\mathbf{s})$ defined in \eqref{disc_cost_opt_00} is finite $\forall \mathbf{s},\alpha$.
		\item A2: $\exists I\geq 0$ s.t. $-I\leq h^{\alpha} (\mathbf{s})\triangleq V^{\alpha}(\mathbf{s})-V^{\alpha}(\mathbf{0})$, $\forall \mathbf{s}, \alpha$.
		\item A3: $\exists F(\mathbf{s})\geq 0$ s.t. $h^{\alpha} (\mathbf{s})\leq F(\mathbf{s})$, $\forall \mathbf{s},\alpha$. Moreover, for each $\mathbf{s}$, $\exists \, u(\mathbf{s})$ s.t. $\sum_{\mathbf{s'}\in \mathcal{S}}\mathbb{P}(\mathbf{s'}|\mathbf{s},u(\mathbf{s}))F(\mathbf{s'})<\infty$.
		\item A4: $\sum_{\mathbf{s'}\in \mathcal{S}}\mathbb{P}(\mathbf{s'}|\mathbf{s},u)F(\mathbf{s'})<\infty$ $\forall \mathbf{s}, u$.
	\end{itemize}

In Proposition \ref{existence_discount_00}, we showed that a policy $f$ that chooses $u=0$ at every time slot satisfies $L_{\mathbf{s}}^{\alpha}(f;\beta)\!<\!\!\infty$.
By \eqref{disc_cost_opt_00}, we have $L_{\mathbf{s}}^{\alpha}(f;\beta)\geq V^{\alpha}(\mathbf{s})$, which implies A1.

By Lemma \ref{property_00}, we have $V^{\alpha}(\Delta',\Lambda)\geq V^{\alpha}(\Delta,\Lambda)$ for all $\Delta'\geq \Delta$ and $V^{\alpha}(\Delta,\Lambda)\geq V^{\alpha}(\Delta,\Lambda')$ for all $\Lambda'\geq \Lambda$. Hence, by setting $I=V^{\alpha}(\mathbf{0})-V^{\alpha}(1,M)$, where $\mathbf{0}=(1,M)$ is the reference state, we prove A2.

Let $g$ be the policy that transmits whenever the number of collected samples equals $M$. This ensures that any transmission satisfies distortion requirement. Under policy $g$, states that occur after successful delivery are recurrent. Actually, the probability that no transmission succeeds after $l$ slots is $(1-P_\Lambda(M)(1-p))^{l}$. State $\mathbf{0}$ follows a successful delivery and is recurrent.
 Hence, under policy $g$ the expected cost of the first passage from state $\mathbf{s}$ to $\mathbf{0}$, denoted by $c_{\mathbf{s},\mathbf{0}}(g)$, is finite.
 Let $g'$ be a mix policy where $g$ is used until entering state $\mathbf{0}$ and the optimal policy for the $\alpha$-discounted cost problem, denoted by $g_{\alpha}$, is used afterwards. Suppose $T$ is the first time slot when system enters $\mathbf{0}$. Then, we have,
   \begin{align}
   V^{\alpha}(\mathbf{s})
   	\leq &\mathbb{E}_{g'}[\sum_{t=1}^{T-1}\!\!\alpha^{t-1}C(\mathbf{s}_t,\!u_t;\beta)|\mathbf{s}]\nonumber\\
   	&+\!\mathbb{E}_{g'}[\sum_{t=T}^{\infty}\!\!\alpha^{t-1}C(\mathbf{s}_t,\!u_t;\beta)|\mathbf{0}]\\
   	\leq & c_{\mathbf{s},\mathbf{0}}(g)+ \mathbb{E}_{g_{\alpha}}(\alpha^{(T-1)})V^{\alpha}(\mathbf{0})\\
   	\leq & c_{\mathbf{s},\mathbf{0}}(g)+ V^{\alpha}(\mathbf{0}).
   \end{align}
   Hence, by setting $F(\mathbf{0})=0$ and $F(\mathbf{s})=c_{\mathbf{s},\mathbf{0}}(g)$ for $\mathbf{s}\!\neq \!\mathbf{0}$, we prove A3. After transition from $\mathbf{s}$ under any action, there will be at most two possible states. Since for all $\mathbf{s}$, $F(\mathbf{s})<\infty$, the sum of at most two $F(\cdot)$ is also finite. Hence, A4 holds.
\section{Conclusion}
\ifreport
In this chapter,
\else
In this paper,
\fi
we investigate an age minimization problem with constraints on the long-term average energy consumption and distortion of each update. The problem is formulated as a constrained MDP. Through the Lagrangian multiplier technique, we connect the problem to an average cost problem \eqref{avg_cost}, and show that the optimal policy is a mixture of two stationary deterministic policies (Theorem \ref{Ori_Lag}), each of which is optimal for the average cost problem and of a threshold-type (Theorem \ref{opt_stru}). Then, we obtain the average cost under the threshold-type policy, which is a piecewise function of threshold (Theorem \ref{cost_cal}), and we find the optimal threshold value in the last interval (Theorem \ref{new}). With these, we avoid dealing with infinite state space when using a classical solution RVI, and develop low-complexity algorithms. In the special case of the average cost problem, we obtain a closed-form solution (Corollary \ref{cor: special_case}). We show that the optimal threshold increases with the probability that distortion requirement is met, and the impact of transmission error probability $p$ on the optimal threshold depends on whether it is age or energy being the dominant issue (Theorem \ref{lem:special_case}).

\section{Introduction}
For status update systems, it is important that the destination
receives fresh updates. However, a traditional metric like delay cannot fully characterize the freshness of information updates. For example, if the information is updated infrequently, then the updates are not fresh even though the delay is small. To this end, the age of information or simply the age was introduced in \cite{kaul2011minimizing} as a metric to represent the freshness (more precisely the staleness) of an update that simultaneously take into the update frequency and the delay into a single metric.

\subsection{Problem and Applications}
In this paper, we consider a status update system, in which an access point receives measurements from multiple sensors, fuses them and transmits the aggregated sample to a remote monitor over wireless erasure channels.

Examples of the system can be found in wireless sensor networks (WSNs) and IoT systems. In certain IoT or WSNs applications like smart camera networks \cite{wang2013intelligent} or healthcare applications \cite{naresh2020internet}, multiple nodes (IoT devices/sensors) are used to observe a \emph{common} physical process. In ~\cite{kalor2019minimizing,zhou2020age,shao2021partially,9155238,tsai2021unifying}, the authors took this scenario into account in age relevant problems.
In addition, in wireless sensor networks or IoT systems, instead of allowing all nodes to directly communicate with the receiver, one node may be selected as a gateway/relay to forward collected data to the receiver in order to reduce the energy consumption \cite{gupta2005cluster}. Specifically, we have two examples as follows:

\emph{Example 1: healthcare.} In healthcare architectures \cite{abdelmoneem2019cloud,kong2016design}, a sink node like a mobile device or a smart watch collects health indicators from wearable biomedical and activity sensors including ECG
collection, blood pressure, blood oxygen. Then, the collected data is sent to a cloud or back-end server for further processing/analysis.

\emph{Example 2: smart agriculture.} In one mode of smart agriculture \cite{ayaz2019internet}, sensor nodes in a mesh network collect and transmit data first to the gateway, a designated node in the mesh network. Then, the gateway forwards this data to the farm management system using the WAN network.

Since wireless channels are not reliable and different sensor nodes may have their own sleep-wake schedules, the access point usually receives a random number of measurements at each time slot. In this work, we assume the sensors nodes (in different positions) observe a common process from different views. Under this assumption, the larger the number of received measurements, the higher the quality of the collected data in each time instant, and the less distortion of the update for the physical process. To ensure that precious resources are only used to forward samples of high quality, we impose a {\em distortion requirement} such that  at each time slot the access point can forward the fused/aggregated sample {\em only if} the number of received measurements is no less than a predefined threshold, which thus guarantees low distortion of each update.

In addition to jointly considering age and distortion, we note that nodes in status update systems are usually battery-powered and thus energy limited. See the two examples discussed earlier. Since communication energy/cost savings is a critical design consideration of any IoT device schedulers, the goal of this paper is to minimize the long-term average age under a long-term energy constraint, while respecting the aforementioned distortion requirement for each update.

\subsection{Related Works}
\begin{table*}[]
\footnotesize
\caption{Related Works}
\small
\label{Related_Works}
\begin{tabular}{lllll}
\hline\hline
Ref.        & Goal                                         & \begin{tabular}[c]{@{}l@{}}Energy \\ Constraint\end{tabular}                             & \begin{tabular}[c]{@{}l@{}}Distortion\\ Requirement\end{tabular}               & \begin{tabular}[c]{@{}l@{}}Channel\\ State Information\end{tabular}              \\ \hline
{\cite{gu2019timely}}          & \begin{tabular}[c]{@{}l@{}@{}}Minimize the average age by \\ optimizing the transmit power and the \\ maximum allowable transmission times \end{tabular} & \begin{tabular}[c]{@{}l@{}}Average power \\ consumption \end{tabular}
& No                                                                            & \begin{tabular}[c]{@{}l@{}@{}}Error-prone \\ channel with \\fixed probability\end{tabular}          \\ \hline

{\cite{huang2021age}}          & \begin{tabular}[c]{@{}l@{}}Minimize the weighted sum of \\ the age and total energy consumption\end{tabular} & \begin{tabular}[c]{@{}l@{}}Limit number of \\ retransmissions \end{tabular}                                                            & No                                                                            & \begin{tabular}[c]{@{}l@{}}Distribution information\\ or unknown\end{tabular}          \\ \hline
{\cite{9736576, yao2021age}} & Minimize long-term average age                                                                                & \begin{tabular}[c]{@{}l@{}}Average energy \\ consumption \end{tabular}                                                              & No                                                                            & \begin{tabular}[c]{@{}l@{}@{}}Fading channel\\ imperfect channel \\ information\end{tabular}               \\ \hline
{\cite{feng2021age}}          & \begin{tabular}[c]{@{}l@{}} Minimize long-term average age\end{tabular}         & \begin{tabular}[c]{@{}l@{}@{}}Energy causality\\ constraint at the \\ EH sensor\end{tabular} & No                                                                            & \begin{tabular}[c]{@{}l@{}}Erasure channel with \\ fixed error probability\end{tabular} \\ \hline

{\cite{zheng2020age}}          & \begin{tabular}[c]{@{}l@{}} Study age-energy region by \\ studying average age minimization\end{tabular}         & \begin{tabular}[c]{@{}l@{}}Limited by\\ harvested energy\end{tabular} & No                                                                            & Fixed noise power \\ \hline

{\cite{rajaraman2021not}}          & \begin{tabular}[c]{@{}l@{}}Minimize the weighted sum of the\\ age, distortion and energy\end{tabular}                                & No                                                                                & \begin{tabular}[c]{@{}l@{}}Soft constraint on controllable\\ distortion due to compression           \end{tabular}  &           No transmission failure                                                                       \\ \hline
{\cite{dong2020energy}}           & \begin{tabular}[c]{@{}l@{}}Minimize the weighted sum of the\\ age and distortion caused by noise\end{tabular}                                       & \begin{tabular}[c]{@{}l@{}}Limited by \\ harvested energy           \end{tabular}                                                          & \begin{tabular}[c]{@{}l@{}}Soft constraint on controllable\\ distortion due to observation noise           \end{tabular}                                              &  Gaussian channel                                                                                \\ \hline
{\cite{bastopcu2019age,bastopcu2021age}}    & Minimize the average age over a time $T$                                                                                & No                                                                                & \begin{tabular}[c]{@{}l@{}}Hard constraint on controllable \\ distortion due to processing time          \end{tabular}        & No transmission failure                                                          \\ \hline\hline
\end{tabular}
\end{table*}

There is a large body of literature that studies the trade-off between the age and energy. In \cite{gu2019timely}, the authors studied the trade-off in an IoT system by controlling the allowable times of retransmissions. \cite{huang2021age} studied power control policies that minimize the weighted sum of the age and energy consumption (including sensing and transmission energy costs) with constraint on times of retransmissions. \cite{yao2021age} and \cite{9736576} studied transmission scheduling over time-correlated fading channel to minimize long-term average age under an energy constraint. In \cite{zheng2020age}, the authors investigated the trade-off between the age and the storable energy at the IoT device in a wireless powered communication network. The authors in \cite{feng2021age} designed optimal online status updating policy to minimize the long-term average age at the destination, subject to the energy causality constraint at an energy-harvesting sensor.

Different from the above works, one key consideration of this work is the focus on the {\em distortion requirement}. This requirement is hard in the sense that it has to be met all the time. In contrast, some papers deal with a soft distortion requirement ~\cite{dong2020energy,rajaraman2021not}, which assume there exists a trade-off between the age and distortion. Although both requirements have applications, in practical system, it can be more difficult to satisfy requirements from different aspects of the system simultaneously. As will be seen, our paper directly links the distortion to the (random) number of received measurements at any time slot. In general, distortion may be caused by other sources as well. For example, the distortion considered in ~\cite{hu2020balancing,rajaraman2021not} is caused by by compression. In particular, \cite{rajaraman2021not} studied a scheduling problem which aims to minimize the weighted sum of the age, distortion and energy, where distortion is determined by the number of bits sent for each source.
Paper \cite{hu2020balancing} investigated the trade-off between the age and the distortion caused by compression via assigning compression bits to packets in the queue and transmission scheduling. Distortion may also be caused by observation noise. In \cite{dong2020energy}, the authors considered this type of distortion and studied the optimal power control policy that minimizes the weighted sum of the age and distortion.
In ~\cite{bastopcu2019age,bastopcu2021age}, the authors considered the distortion caused by the processing time and studied age-optimal distortion constrained updating policies. Specifically, \cite{bastopcu2019age} considered a fixed distortion requirement while \cite{bastopcu2021age} considered an age-dependent distortion requirement. For comparison, we summarize the related works in Table \ref{Related_Works}.

\subsection{Key Contributions}
In the paper, we focus on the setting for which the distortion requirement of each update is stricter when the age of the system is older.
The idea is that if the age is also a source of distortion (a reasonable assumption, since the larger the age, the more likely that the estimates are poorer), then as the age increases, we would like to place a stricter allowable allowable distortion criterion (i.e., larger lower bound) of new updates to ensure that the overall quality of transmission is maintained.
We then develop the optimal transmission control policy that minimizes the long-term average age under a long-term energy constraint while respecting the given age-based distortion requirement on each update.
Our key contributions are as follows:
\begin{itemize}
    \item We investigate the trade-offs among the age, energy and the distortion. Under our setting, we show that the optimal policy, which minimizes the long-term average age with the energy and distortion requirements, is a mixture of two stationary deterministic policies (Theorem \ref{Ori_Lag}). We also show that each stationary deterministic policy is optimal for a parameterized average cost problem, which aims to minimize the weighted sum of the age and energy while respecting the given age-based distortion requirement (Theorem \ref{Ori_Lag}). Further, we prove that the policy is of a threshold-type, i.e., a transmission is scheduled if (i) the age exceeds a certain threshold, and (ii) the distortion requirement is met (Theorem \ref{opt_stru}).
    \item We derive the average cost of the parameterized average cost problem (Theorem \ref{new}), and prove that it is a piecewise function of the earlier mentioned threshold (Theorem \ref{cost_cal}), and analytically characterize the property of the function (Theorem \ref{new}). By leveraging Theorems \ref{cost_cal} and \ref{new}, we circumvent the difficulty in dealing with an infinite state space when using classical solutions like the Relative Value Iteration (RVI). This allows us to develop low-complexity algorithms for both parameterized average cost problem (Algorithm \ref{alg0}) and the original problem (Algorithm \ref{alg1}).
    \item  In additional to characterizing the optimal policy for the general setting, we consider a special case of the parameterized average cost problem, where the distortion requirement is a constant that is independent of the age, arguable the most important setting for practical applications. In this important but simpler setting, we obtain a closed form expression for the optimal threshold (Corollary \ref{cor: special_case}), which allows us to examine the relationship among (a) the transmission threshold; (b) the probability of meeting the distortion requirement; and (c) the erasure probability of the access point's transmission. Specifically, we show that (i) the optimal threshold increases with the probability that the distortion requirement is met; (ii) when the energy is the dominant issue, the optimal threshold increases with the error probability of transmission from the access point to destination (Theorem \ref{lem:special_case}). But the situation reverses (from being an increasing function of the error probability to being a decreasing one) if the age is the dominant issue.
\end{itemize}

\section{System Model}
\label{scheduler}
We consider a status update system, in which an access point receives measurements from multiple sensors, fuses them, and then transmits the aggregated sample to a remote monitor/receiver, as shown in Fig. \ref{sysmodel}.
We consider a time-slotted system and use $t\in\{1,2,\cdots\}$ as the time index. At the beginning of each time slot, $M$ sensors measure the same physical process from their own perspectives and transmit the measurements to the access point over the wireless channels. Then, the access point decides whether to transmit an {\em update} to the remote monitor. Here an update can mean sending the entire set of received measurements to the remote monitor for further processing or it could mean sending the aggregated sample after fusing the data locally. The access point's action is denoted by $u_{t} \in \mathcal{U}\triangleq\{0,1\}$, where $u_{t}=1$ means transmission, and $u_{t}=0$ denotes forfeiting the transmission for time slot $t$.

We assume erasure channels. Specifically, the erasure probability of a transmission from the sensor $m$ to the access point is $q_m$, for $m\in\{1,2,\cdots,M\}$, and the erasure probability of the transmission from the access point to the receiver is $p$.
\ifreport
\begin{figure}[h]
    \centering
    \includegraphics[width=0.6\textwidth]{Age_dist/SysModel.pdf}
    \caption{System Model}
    \label{sysmodel}
\end{figure}
\else
\begin{figure}[h]
    \centering
    \includegraphics[width=0.32\textwidth]{SysModel.pdf}
    \caption{System Model}
    \label{sysmodel}
\end{figure}
\fi

\subsection{Age of Information}
Age of information (AoI), or simply the age, reflects the timeliness of the information at the remote monitor/receiver. It is defined as the time elapsed since the generation of the most recently received update sample at the receiver. Let $\Delta_{t}$ denote the age at the beginning of the time slot $t$. Let $U(t)$ denote the generation time of the last successfully received status update at time $t$. Then, $\Delta_{t}$ is given by $\Delta_{t}\triangleq t-U(t)$, which can be iteratively computed by
\begin{align}
\label{age_update}
& \Delta_{t+1}=

  \begin{cases
  1 & \text{if transmission is successful}, \\
  1+\Delta_{t} & \text{otherwise}.
  \end{cases}
\end{align}
In this work, we assume $\Delta_1=1$ for initialization.
\subsection{Distortion requirement and energy constraints}
\label{sec: const}
Since transmissions from sensors to the access point are not reliable, we use the random variable $\Lambda_t\in\{0,1,\cdots, M\}$ to denote the number of received measurements from $M$ sensors at time slot $t$. After fusing $\Lambda_t$ measurements to an aggregated sample, the corresponding distortion is a monotonically decreasing\footnote{In this work, the terms {\em decreasing} and {\em non-increasing} are considered interchangeable.} function $F_\mathrm{dist}(\Lambda_t)$ of $\Lambda_t$. To guarantee the quality of each update, we suspend access-point transmission whenever
\begin{align}
F_\mathrm{dist}(\Lambda_t)> F_\mathrm{thre}(\Delta_t),\label{eq:dist-111}
\end{align}
i.e., we prohibit the access point from transmitting a low-quality (high-distortion) sample since it is essentially a waste of resources. We allow the threshold $F_\mathrm{thre}$ to depend on the age at the receiver. While \eqref{eq:dist-111} has a clear physical meaning, we can simplify {\em distortion requirement} to: we always choose $u_t=0$, if
\begin{align}
&\Lambda_t< D(\Delta_t)\triangleq F_\mathrm{dist}^{-1}( F_\mathrm{thre}(\Delta_t)). \label{eq:dist-222}
\end{align}
The $D(\cdot)$ function is the concatenation of $F_{\mathrm{dist}}^{-1}()$ and $F_\mathrm{thre}()$, and we call it the {\em distortion function} that maps the age to the number of received measurements below which the access point will always discard the measurements ($u_t=0$) due to the lack of fidelity (distortion being too high).

We assume that $D(\cdot)$ is an increasing function of the age on $[1,\infty)$ (since the smallest age is 1). Since $\Lambda_t$ in condition ~\eqref{eq:dist-222} is an integer between $0$ and $M$, without loss of generality, we assume $D(\cdot)$ is a piecewise constant function satisfying:
\begin{align}
D(\Delta)=h_l, \text{\ \ if\ \ } \Delta\in[\delta_l,\delta_{l+1}),~\forall l\in[1,L].
\end{align}
Namely, if $\Delta$ falls into the interval $[\delta_l,\delta_{l+1})$, then $D(\Delta)=h_l$. Here we assume $\delta_1=1$, $\delta_{L+1}=\infty$ and $1\leq h_l<h_{l+1}\leq M$ for all $l<L$, since if $h_L> M$, the transmission will never be made after the age exceeds $\delta_L$ (condition \eqref{eq:dist-222} will always hold then).
Fig.~\ref{fig:distfun_inc} provides an example of the distortion function, where $L=3$ and $M=8$.
\ifreport
\begin{figure}
    \centering
    \includegraphics[width=0.55\textwidth]{Age_dist/Dfun_inc.pdf}
    \caption{Example of distortion function}
    \label{fig:distfun_inc}
\end{figure}
\else
\begin{figure}
    \centering
    \includegraphics[width=0.38\textwidth]{Dfun_inc.pdf}
    \caption{Example of distortion function}
    \vspace{-0.5cm}
    \label{fig:distfun_inc}
\end{figure}
\fi

The access point consumes energy for each transmission. We assume that each transmission consumes the same energy which is normalized as one unit energy, a setting similar to \cite{tsai2021jointly}. To avoid excessive energy consumption, we employ a long-term average energy consumption constraint for the access point, which will be formalized later in \eqref{avg_energy}. Note that in the system, sensors take measurements periodically, and their energy consumption is fixed and thus not included in our optimization problem.

\subsection{Optimization Problem}
Our objective is to design a transmission control policy $\pi$ that minimizes the following long-term average age
\begin{align}
	&\bar{A}(\pi)\triangleq \lim_{T \rightarrow \infty} \frac{1}{T}\mathbb{E_\pi}\big[\sum_{t=1}^T \Delta_t\big],
	\label{avg_age}
\end{align}
while the long-term average energy consumption $\bar{E}(\pi)$ must not exceed $E_{\text{max}}\in (0,1]$, i.e.
\begin{align}
	&\bar{E}(\pi)\triangleq \lim_{T \rightarrow \infty} \frac{1}{T}\mathbb{E_\pi}\big[\sum_{t=1}^T u_t\big]\leq E_\text{max},
	\label{avg_energy}
\end{align}
and the distortion requirement in \eqref{eq:dist-222} is satisfied for all $t$, i.e.
\begin{align}
    \Lambda_t\geq u_t D(\Delta_t),\ \  \forall t\geq 1,\label{dist_req}
\end{align}
where $\mathbb{E}_\pi$ denotes expectation under policy $\pi$.

\section{Constrained MDP Formulation and Lagrangian Relaxation}
\label{sec: formulation}
\subsection{Constrained MDP Formulation}
\label{components}
The optimization problem can be formulated as a constrained MDP.

\textbf{States:} The system state consists of the age and the number of received measurements at time $t$, i.e., $\mathbf{s}_t=(\Delta_t,\Lambda_t)$. Clearly, the state space, denoted by $\mathcal{S}\triangleq \{(\Delta,\Lambda): \Delta\in \mathbb{N}^+,  \Lambda\in\{0,1,\cdots,M\}\}$ is countably infinite.

\textbf{Actions:} Action set is $\mathcal{U}=\{0,1\}$ as defined in Section \ref{scheduler}. Here we directly embed the distortion requirement in \eqref{dist_req} in the setting by assigning a heterogeneous action set for each $\mathbf{s}_t$. That is, define $A_{\mathbf{s}_t}\triangleq \{u_t\in \mathcal{U}: \Lambda_t\geq u_t D(\Delta_t)\}$ as the admissible action set in state $\mathbf{s}_t$ satisfying the distortion requirement \eqref{dist_req}.
For example, with the distortion requirement in Fig. \ref{fig:distfun_inc}, we have $A_{(5, 5)}=\{0,1\}$ while $A_{(51, 5)}=\{0\}$.

\textbf{Transition Probability:} Given the current state $\mathbf{s}_{t}= (\Delta_{t}, \Lambda_{t})$ and action $u_{t}$ at time slot $t$, the transition probability to the state $\mathbf{s}_{t+1}=(\Delta_{t+1}, \Lambda_{t+1})$ at the next time slot $t+1$, which is denoted by $P_{\mathbf{s}_{t}\mathbf{s}_{t+1}}(u_t)$, is defined as
 \begin{align}
	P_{\mathbf{s}_{t}\mathbf{s}_{t+1}}(u_t)&\triangleq\mathbb{P}(\mathbf{s}_{t+1}|\mathbf{s}_{t},u_{t})=\mathbb{P}(\Delta_{t+1}|\Delta_t,u_t)P_\Lambda(\Lambda_{t+1}),
\end{align}
where
\begin{align}
&\mathbb{P}(\Delta_{t+1}|\Delta_t,u_t)=
  \begin{cases
  p & \text{if}\, \, u_{t}=1,\Delta_{t+1}=1+\Delta_t, \\
  1-p & \text{if} \, \, u_{t}=1,\Delta_{t+1}=1,\\
  1 &\text{if} \, \, u_{t}=0,\Delta_{t+1}=1+\Delta_t,\\
  0 & \text{otherwise},
  \end{cases}
\end{align}
and $P_\Lambda(\Lambda_{t+1})\triangleq\mathbb{P}(\Lambda\!=\!\Lambda_{t+1})$.

\textbf{Costs:} Given a state $\mathbf{s}_t=(\Delta_{t}, \Lambda_{t})$ and an action choice $u_t$ at time slot $t$, the cost of one slot is the age at the beginning of this slot, i.e., we have
\begin{equation}
	C_\Delta(\mathbf{s}_t,u_{t})=\Delta_{t}.
\end{equation}
Moreover, the energy consumption of one slot is
\begin{equation}
	C_E(\mathbf{s}_t,u_{t})=u_t.
\end{equation}

Let $\Pi$ denote the set of \emph{feasible} policies that satisfy the distortion requirement, i.e., $u_t\in A_{\mathbf{s}_t}$, $\forall t$. Then, our control problem can be reformulated as a constrained Average-age MDP:

\textit{Problem 1 (Average-age MDP):}
\begin{alignat}{2}
\label{ori_prob}
 \bar{A}^\star\triangleq   \min_{\pi\in\Pi} \quad & \bar{A}(\pi)= \limsup_{T \rightarrow \infty} \frac{1}{T}\mathbb{E_\pi}\big[\sum_{t=1}^T C_\Delta(\mathbf{s}_{t},u_{t})\big] &  \\
    \mathrm{s.t.} \quad & \bar{E}(\pi)=\limsup_{T \rightarrow \infty} \frac{1}{T}\mathbb{E_\pi}\big[\sum_{t=1}^T C_E(\mathbf{s}_{t},u_{t})\big] \leq E_{\text{max}}, &   \nonumber

\end{alignat}
where $\bar{A}^\star$ is the optimal average age.
\subsection{Lagrange Relaxation of the Constrained MDP}
We now solve \eqref{ori_prob}. Given Lagrange multiplier $\beta$, the instantaneous Lagrangian cost at time slot $t$ is defined by
\begin{align}	C(\mathbf{s}_{t},u_{t};\beta)\triangleq C_\Delta(\mathbf{s}_{t},u_{t})+\beta C_E(\mathbf{s}_{t},u_{t}).
	\label{inst_lag_cost}
\end{align}
Then, the long-term average Lagrangian cost under policy $\pi$ is
\begin{align}
	&\bar{L}(\pi;\beta)= \lim_{T \rightarrow \infty} \frac{1}{T}\mathbb{E_\pi}\big[\sum_{t=1}^T C(\mathbf{s}_{t},u_{t}; \beta)\big].\label{Lag_main}
\end{align}

We then solve the following average age-plus-cost MDP:

\textit{Problem 2 (Average age-plus-cost MDP):}
\begin{align}
	\bar{L}^\star(\beta)  \triangleq &\min_{\pi\in \Pi}  \bar{L}(\pi;\beta),
	\label{avg_cost}
\end{align}
where $\bar{L}^\star(\beta)$ is the optimal average Lagrangian cost with regard to $\beta$.

\begin{theorem}
\label{Ori_Lag}
There exists a stationary randomized policy that solves the average-age MDP \eqref{ori_prob}. This policy can be expressed as a mixture of two stationary deterministic policies $\pi_{\beta^\star,1}$ and $\pi_{\beta^\star,2}$, where $\pi_{\beta^\star,1}$ and $\pi_{\beta^\star,2}$ differ in
at most a single state $\mathbf{s}$, and are both optimal policies for the average age-plus-cost MDP \eqref{avg_cost} given $\beta^\star$. The mixture policy $\pi_{\beta^\star}$ uses $\pi_{\beta^\star,1}$ with probability $\mu$ and $\pi_{\beta^\star,2}$ with probability $1-\mu$ in state $s$; it uses either policy (since they coincide) in other states, where $\mu\in [0,1]$
\end{theorem}
\begin{proof}
Please see Appendix \ref{proof_ori_lag}.
\end{proof}
\vspace{0.1cm}

\section{Solving the average age-plus-Cost MDP}
\label{sec: average_cost}
In this section, we investigate optimal policies that solve \eqref{avg_cost} and characterize its unique structure. We also give a more detailed analysis for the special case when the distortion function $D(\cdot)$ is constant (previously we assume $D(\cdot)$ is increasing).

\subsection{Structure of the optimal policies}
\label{sec: main_res}
In this part, we first study the structure of the optimal policies, and then obtain the average cost function with regard to a threshold.

\begin{table*}[h]
\centering
\footnotesize
\caption{\small{Notations}}
\label{notations}
\begin{tabular}{l}
\hline\hline
$F(r)= \sum_{j=r}^{M}P_\Lambda(j), \ \ \forall \ 0\leq r\leq M$\\ \hline
$B_{l}=1-(1-p)F(h_l), \ \ \forall \ 1\leq l\leq L$\\ \hline
$w(i,j)=\mathbbm{1}_{\{i<j\}}\prod_{v=i}^{j-1}(B_{v})^{\delta_{v+1}-\delta_v}+\mathbbm{1}_{\{i\geq j\}}$
\\ \hline
 $J_{l}=-\frac{1}{(1-B_{{l}-1})^2}-\frac{\delta_{l}-1+\beta F(h_{{l}-1})}{1-B_{{l}-1}}$\\
 \ \ \ \ \ \ $+\sum_{j={l}}^{L}w({l},j)\Big(\frac{1-\mathbbm{1}_{\{j<L\}}(B_{j})^{\delta_{j+1}-\delta_j}\big(1+(\delta_{j+1}-1+\beta F(h_j))(1-B_j)\big)}{(1-B_j)^2}
    +\frac{\delta_j-1+\beta F(h_j)}{1-B_j}\Big), \ \ \forall \ 2\leq l\leq L$
 \\\hline $I_{l}=-\frac{1}{1-B_{{l}-1}}+\sum_{j={l}}^{L}\frac{1-\mathbbm{1}_{\{j<L\}}(B_{j})^{\delta_{j+1}-\delta_j}}{1-B_j}w(l,j), \ \ \forall \ 2\leq l\leq L$
 \\ \hline $O_{l}=\frac{1}{(1-B_{{l}-1})^2}+\frac{-1+\beta F(h_{{l}-1})}{1-B_{{l}-1}}, \ \ \forall \ 2\leq l\leq L+1$
 \\ \hline \hline
\end{tabular}
\vspace{-0.4cm}
\end{table*}

\begin{theorem}
\label{opt_stru}
For any fixed $\beta$, there exists an optimal age threshold $\Delta_\beta^\star$ such that the following policy
\begin{align}
&u^\star(\Delta,\Lambda;\beta)=
  \begin{cases
  1 & \text{if}\, \, \Delta\geq \Delta_{\beta}^\star \, \ \text{and}\, \ \Lambda\geq D(\Delta),\\
  0 & \text{otherwise},
  \end{cases} \label{optPol}
\end{align}
achieves the minimum average Lagrangian cost in \eqref{avg_cost}.

\end{theorem}
\begin{proof}
Please see Section \ref{proof_thre1}.
\end{proof}
By Theorem \ref{opt_stru}, the optimal policies for \eqref{avg_cost} are of threshold-type in the age. That is, if $\Lambda_t\!\!<\!\!D(\Delta_t)\!$, then the access point is prohibited to transmit due to the distortion criterion in \eqref{eq:dist-222}. If  $\Lambda_t\geq D(\Delta_t)$ at time $t$,  the optimal policy would transmit if and only if the age $\Delta_t$ exceeds $\Delta_\beta^\star$.

In Theorem \ref{cost_cal} below, we express the average Lagrangian cost as a function of any given threshold.
\par Recall that $\delta_l$ is the leftmost point of the $l$-th interval in the distortion requirement function $D(\cdot)$, see Fig.~\ref{fig:distfun_inc} and Sec.~\ref{sec: const}. Given any $k\in\mathbb{N}^+$, define
\begin{equation}
    l_k\triangleq \min\{l\leq L+1: \delta_l>k\}. \label{eqn:def_lk}
\end{equation}
Broadly speaking, $l_k$ is the inverse of $\delta_l$. The special definition in \eqref{eqn:def_lk} is because the given $D(\cdot)$ function (see Fig.~\ref{fig:distfun_inc}) may have a jump. Since, per our definition $\delta_{L+1}=\infty$, we always have $l_k\leq L+1$. We then have the following results.

\begin{theorem}
\label{cost_cal}
We use policy $\pi_k$ to denote the policy described in \eqref{optPol} but with an arbitrarily given threshold $k\in\mathbb{N}^+$. The long-term average Lagrangian cost of $\pi_k$ is expressed as:
\begin{footnotesize}
\begin{align}
   &\bar{L}(\pi_k;\beta) \notag\\
   =&\frac{0.5k^2-0.5k+(1-B_{{l_k}-1})^{-1}k
    +\mathbbm{1}_{\{l_k\leq L\}}J_{l_k} (B_{l_k-1})^{\delta_{l_k}-k}+O_{l_k}}{k-1+(1-B_{{l_k}-1})^{-1}
    +\mathbbm{1}_{\{l_k\leq L\}}I_{l_k} (B_{l_k-1})^{\delta_{l_k}-k}},\label{eqn:avg_cost}
\end{align}
\end{footnotesize}
for which the expressions of the deterministic sequences $\{B_{l}\}_{l=1}^L$, $\{J_{l}\}_{l=2}^L$, $\{I_{l}\}_{l=2}^L$, and $\{O_{l}\}_{l=2}^{L+1}$ are given in Table \ref{notations}.
\end{theorem}
\begin{proof}
Please see Appendix \ref{opt_thres0}.
\end{proof}

Even though the closed-form expression of $\bar{L}(\pi_k;\beta)$ greatly simplifies the problem, finding the optimal threshold $\Delta_\beta^\star$ through numerical search is still quite challenging since (i) the expression of \eqref{eqn:avg_cost} versus the threshold $k$ may exhibit complicated behavior (e.g., we have found some scenarios where \eqref{eqn:avg_cost} is neither convex nor concave) and (ii) the domain of $k$ is unbounded. Later in Theorem~\ref{new}, we prove that in a restricted sub-domain $k\geq \delta_L$, we can analytically find the best $k_\text{UB}$. Therefore, to search for the optimal $\Delta_\beta^\star$, we only need to exhaustively evaluate $\bar{L}(\pi_k;\beta)$ for all $k\in \{1,2,\cdots,\delta_L-1\}$, compare their values to $\bar{L}(\pi_{k_\text{UB}};\beta)$ in Theorems~\ref{cost_cal} and~\ref{new}, and then find the globally minimum $k^\star$.

\begin{theorem}
\label{new}
Among the sub-domain $k\geq \delta_L$, the $k$ that leads to the smallest $\bar{L}(\pi_k;\beta)$ is given by
\begin{align}
    k_\text{UB} &\triangleq \argmin_{k\geq \delta_L}\bar{L}(\pi_k;\beta)=\max\{\delta_L,y\}, \label{eqn:k0}
\end{align}
where
\begin{small}
\begin{align}
    y\!=\!\Bigg\lceil\!\!-\!\frac{1+B_L}{2(1-B_L)}\!+\!\left(\frac{B_L^2}{(1-B_L)^2}\!+\!\frac{B_L\!+\!2\beta F(h_L)}{1-B_L}\!+\!\frac{1}{4}\right)^{0.5}\!\Bigg \rceil.
\end{align}
\end{small}
\end{theorem}

\begin{proof}
Please see Appendix \ref{proof_min_ub}.
\end{proof}

\subsection{Special Case - Constant Distortion}
\label{sec:special_case}
Our results in Theorems~\ref{Ori_Lag} to \ref{new} hold for any increasing distortion requirement function $D(\cdot)$. We now consider a special case of constant $D(\Delta)=h\leq M$, $\forall \Delta$ (equivalently when $L=1$), arguably the most important scenario in practice since it says that the access-point only forwards the aggregated sample when its quality (distortion) meets a constant threshold.

\begin{corollary}
\label{cor: special_case}
Given $\beta$ and constant distortion function $D(\Delta)=h$, the optimal scheduler of problem \eqref{avg_cost} is analytically described as follows:
\begin{align}
&u_{\text{cons}}^{\star}(\Delta,\Lambda;\beta)=
  \begin{cases
  1 & \text{if}\, \,\Delta\geq \Delta_{\beta,\text{cons}}^\star\, \ \text{and}\, \ \Lambda\geq h,\\
  0 & \text{otherwise},
  \end{cases}
\end{align}
where the optimal threshold
$\Delta_{\beta,\text{cons}}^\star$ is given by
\begin{footnotesize}
\begin{align}
    \Delta_{\beta,\text{cons}}^\star\!\! =
    \!\max\Bigg\{\!1,\!\Bigg\lceil\!\!-\!\frac{1+R}{2(1\!-\!R)}\!+\!\sqrt{ \!\frac{R^2}{(1\!-\!R)^2}\!+\!\frac{R\!+\!2\beta W}{1\!-\!R}\!+\!\frac{1}{4}}\Bigg \rceil\Bigg\},
    \label{opt_threval_spec}
\end{align}
\end{footnotesize}
where $W=\sum_{j=h}^{M}P_\Lambda(j)$ and $R=1-(1-p) W$.
\end{corollary}

\textbf{Remark:} By Corollary \ref{cor: special_case}, the optimal threshold $\Delta_{\beta,\text{cons}}^\star$ depends on the Lagrangian multiplier $\beta$, distortion requirement $h$, the distribution of the random number of received measurements $\Lambda$ and channel unreliability $p$. By simple algebraic simplification of \eqref{opt_threval_spec}, it is easy to show that when $\beta=0$, which corresponds to the case without energy constraint, we have $\Delta_{\beta,\text{cons}}^\star=1$. In addition, $\Delta_{\beta,\text{cons}}^\star$ is non-decreasing with $\beta$. This is because the increase of $\beta$ implies higher weights of the energy cost. To save energy cost, the threshold should be increased to reduce the transmission frequency.

To provide more insights on the special case with constant distortion, we investigate how the measurements arrival probability $W=\mathbb{P}(\Lambda\geq h)$ and the access-point-to-receiver erasure probability $p$ affect the optimal threshold $\Delta_{\beta,\text{cons}}^\star$ in Theorem \ref{lem:special_case}.

\begin{theorem}
\label{lem:special_case}
Given $\beta>0$ and $D(\Delta)=h$, we have the following properties:

(i) If $\beta >\frac{1}{W}$, the optimal threshold $\Delta_{\beta,\text{cons}}^\star$ is increasing with respect to (w.r.t.) $p$; if $\beta <\frac{1}{W}$, the optimal threshold $\Delta_{\beta,\text{cons}}^\star$ is decreasing w.r.t.~$p$;

(ii) In fact, we can further strengthen the second half of (i) by the following: If $\beta <\frac{1}{W}$, the optimal threshold $\Delta_{\beta,\text{cons}}^\star=1$;

(iii) The optimal threshold $\Delta_{\beta,\text{cons}}^\star$ is increasing w.r.t.~$W$.
\end{theorem}
\begin{proof}
Please see Appendix \ref{app: special_case}.
\end{proof}

\textbf{Remark}
Note $\frac{1}{W}$ {\em is the expected duration until the next time (slot) that the access point can receive  enough measurements to meet the distortion requirement.} Roughly speaking, if the access point does not send an aggregated update at this time, it will have to wait $\frac{1}{W}$ time slots before the next time it receives enough measurements to meet the distortion requirement. Therefore, $\frac{1}{W}$ can be viewed as the {\em cost of suspension}. Also recall that the Lagrangian multiplier $\beta$ can be viewed as the energy price of one transmission. Jointly, the intuition of the theorem can be explained as follows:
\begin{itemize}
    \item
In the case $\beta >\frac{1}{W}$, the energy cost precedes the suspension cost. Then, as $p$ increases (channel worsens), it is better to reduce the transmission frequency in order to save energy while sacrificing slightly the age performance. As a result, the optimal threshold increases as stated in (i) of Theorem~\ref{lem:special_case}. On the other hand, if $\beta <\frac{1}{W}$, then the suspension cost dominates. The optimal threshold will decrease to ensure that we transmit more frequently to maintain a small average age (at the cost of increased energy consumption).
\item If $p=0$ (erasure probability is zero), we only need to consider the cost of sending one aggregated update. If we also have $\beta<\frac{1}{W}$, it means that the age cost outweighs the energy cost, which implies the optimal threshold is 1. Together with the second half  of (i), we will have (ii).
\item
The intuition of (iii) is as follows. For any given $\beta$, $W$, the optimal threshold $\Delta^\star_{\beta,\text{cons}}$ would balance the {\em marginal} age cost and the {\em marginal} energy cost in \eqref{avg_cost} so that any perturbation of the threshold in either the positive or negative direction will decrease the performance. Consider a slightly larger $W'>W$. Since $\frac{1}{W}$ is the expected duration between two consecutive slots when the distortion requirement is met, the duration under $W'$ would be slightly smaller. Note that using the new $W'$ would increase the marginal energy cost (since we send more frequently) but decrease the marginal age cost (since we send more frequently). As a result, to re-balance the two marginal costs, the optimal policy would further increase $\Delta^\star_{\beta,\text{cons}}$ under the new $W'$.
\end{itemize}

\subsection{Proof of Theorem \ref{opt_stru}}
\label{proof_thre1}
A method to study average cost MDPs is to relate them to discounted cost MDPs. In this section, we (i) define discounted cost MDPs; (ii) obtain optimal policies for the discounted cost MDPs; and (iii) extend the results to average cost MDPs.

Given discount factor $\alpha \in (0, 1)$ and an initial state $\mathbf{s}$, the total expected discounted Lagrangian cost under a policy $\pi\in\Pi$ is
\begin{align}
	&L_{\mathbf{s}}^{\alpha}(\pi;\beta)= \limsup_{T \rightarrow \infty} \mathbb{E}_{\pi}\big[\sum_{t=1}^T \alpha^{t-1}C(\mathbf{s}_{t},u_{t};\beta)|\mathbf{s}\big],
	\label{disc_cost0}
\end{align}

Then, the optimization problem of minimizing the total expected discounted Lagrangian cost can be cast as

\textit{Problem 3 (Discounted cost MDP):}
\begin{equation}
	V^{\alpha}(\mathbf{s})\triangleq\min_{\pi\in\Pi} \ L_{\mathbf{s}}^\alpha(\pi;\beta),
	\label{disc_cost_opt_00}
\end{equation}
where $V^{\alpha}(\mathbf{s})$ denotes the optimal total expected $\alpha$-discounted Lagrangian cost (for convenience, we omit $\beta$ in $V^{\alpha}(\mathbf{s})$).

We now introduce the optimality equation of $V^{\alpha}(\mathbf{s})$.
\begin{proposition}
\label{existence_discount_00}
	\noindent	(a) The optimal total expected $\alpha$-discounted Lagrangian cost, given by $V^{\alpha}(\Delta,\Lambda)$, satisfies the optimality equation as follows:
	\begin{align}
		V^{\alpha}\left(\Delta,\Lambda\right)=\min_{u\in A_{(\Delta,\Lambda)}}  Q^{\alpha}\left(\Delta,\Lambda;u\right), \label{opt_equ_disc_00}
	\end{align}
	where
	\begin{align}		Q^{\alpha}\left(\Delta,\Lambda;0\right)\!=&\Delta\!+\!\alpha \mathbb{E}V^{\alpha}\left(\Delta+1,\Lambda'\right);\label{q1_}\\

		Q^{\alpha}\left(\Delta,\Lambda;1\right)\!=&\Delta\!+\!\beta
		\!+\!\alpha \Big(p \mathbb{E}V^{\alpha}\!\left(\Delta\!+\!1, \Lambda'\right)\!+\!(1\!-\!p)\mathbb{E}V^{\alpha}\left(1,\Lambda'\right)\!\Big).\label{q2_}
	\end{align}

\noindent(b) A stationary deterministic policy determined by the right-hand-side of \eqref{opt_equ_disc_00} solves problem \eqref{disc_cost_opt_00}

\noindent (c) Let $V_n^{\alpha}(\mathbf{s})$ be the cost-to-go function such that
$V_0^{\alpha}(\mathbf{s})\!=\!0$, for all $\mathbf{s}\in\mathcal{S}$ and for $n\geq 0$,
		\begin{align}
		V_{n+1}^{\alpha}(\Delta,\Lambda)=\min_{u\in A_{(\Delta,\Lambda)}} Q_{n+1}^{\alpha}(\Delta,\Lambda;u),
		\label{iteration00}
	    \end{align}
	    where
	    \begin{align}
		\!\!Q_{n+1}^{\alpha}\!\left(\Delta,\Lambda;0\right)\!=&\Delta\!+\!\alpha\mathbb{E} V_{n}^{\alpha}\left(\Delta+1,\Lambda'\right);\label{q1}\\
		\!\!Q_{n+1}^{\alpha}\!\left(\Delta,\Lambda;1\right)\!=&\Delta\!+\!\beta\!+\!\alpha \Big(p\mathbb{E} V_{n}^{\alpha}\left(\Delta\!+\!1, \Lambda'\!\right)\!+\!(1\!-\!p)\mathbb{E}V_{n}^{\alpha}		\left(1,\Lambda'\right)\!\Big).\label{q2}
	    \end{align}
	    Then, we have $V_n^{\alpha}(\mathbf{s}) \rightarrow V^{\alpha}(\mathbf{s})$ as $n\rightarrow \infty$, $\forall \mathbf{s}, \alpha$.
\end{proposition}
\begin{proof}
According to \cite{sennott1989average}, it suffices to show that there exists a stationary deterministic policy $f\in\Pi$ such that for all $\alpha$ and $\mathbf{s}$, we have $L_{\mathbf{s}}^\alpha(f;\beta)\!<\!\!\infty$.
Let $f$ be a policy that chooses $u=0$ at every time slot. Obviously, $f$ satisfies the distortion constraint and thus $f\in\Pi$. Further, given the initial state $\mathbf{s}_1=(\Delta,\Lambda)$, we have
\begin{align}
	L_{\mathbf{s}_1}^\alpha(f;\beta)&= \limsup_{T \rightarrow \infty} \mathbb{E}_f\big[\sum_{t=1}^T \alpha^{t-1}\Delta_t|\mathbf{s}_{1}\big]\notag\\
	&=\sum_{n=0}^{\infty}\alpha^n(\Delta+n)\notag\\
	&=\frac{\Delta}{1-\alpha}+\frac{\alpha}{(1-\alpha)^2}<\infty.\notag
\end{align}
\end{proof}

Using the induction method in (c) of Proposition \ref{existence_discount_00}, we first show some properties of $V^{\alpha}(\mathbf{s})$ in Lemma \ref{property_00}.
\begin{lemma}
\label{property_00}
Given $\alpha$, the value function $V^{\alpha}(\mathbf{s})$ has properties:

(i) The value function $V^{\alpha}(\mathbf{s})$ is increasing w.r.t.~$\Delta$.

(ii) The value function $V^\alpha(\mathbf{s})$ is decreasing w.r.t.~$\Lambda$.
\end{lemma}
\begin{proof}
Please see Appendix \ref{proof_prop_dis_subprob}.
\end{proof}
\vspace{0.2cm}

Using the properties in Lemma \ref{property_00}, we further show that the optimal policies that solve discounted cost MDPs in \eqref{disc_cost_opt_00} are of threshold-type in Lemma \ref{disc_stru0}.
\begin{lemma}
\label{disc_stru0}
Given $\beta,\alpha$, the optimal policy that solves the discounted cost MDP \eqref{disc_cost_opt_00} is of threshold-type in the age. Specifically, there exists a threshold $\Delta_{\alpha,\beta}^{\star}$ such that it is optimal to transmit only when the age exceeds the threshold and the distortion requirement is met, i.e., $ \Delta\geq \Delta_{\alpha,\beta}^{\star} $ and $\Lambda\geq D(\Delta)$.
\end{lemma}
\begin{proof}
Please see Appendix \ref{proof_disc_stru}.
\end{proof}

 By \cite{sennott1989average}, under certain conditions (A proof of these conditions verification is provided in Appendix \ref{proof_cond}), the optimal policy for problem \eqref{avg_cost} can be viewed as a limit of a sequence of the optimal policies for the $\alpha$-discounted cost problems in \eqref{disc_cost_opt_00} as $\alpha\to 1$. Thus, there exist stationary deterministic policies that solve problem \eqref{avg_cost}, and the optimal policies are in the form \eqref{optPol}.

\section{Low-complexity Algorithm for average-age MDP}
\label{sec:alg_design}
In this section, we design a low-complexity algorithm for the average-age MDP. In particular, we first design a low-complexity algorithm to obtain the optimal policy for the average age-plus-cost MDP \eqref{avg_cost} given $\beta$, and then provide a way to determine optimal Lagrangian multiplier $\beta$.
\subsection{Optimal policy for average age-plus-cost MDP \eqref{avg_cost}}
In Theorem \ref{opt_stru}, we show that the optimal policy for \eqref{avg_cost} is of a threshold-type in the form of \eqref{optPol}. In order to obtain the optimal policy for \eqref{avg_cost}, it remains to obtain optimal threshold $\Delta_\beta^\star$. Using Theorems~\ref{cost_cal} and \ref{new}, we can find $\Delta_\beta^\star$ by the following Algorithm~\ref{alg0}.
\vspace{-0.2cm}
\begin{algorithm}
\SetAlCapFnt{\footnotesize}
\caption{\footnotesize Optimal Threshold Calculator}
\label{alg0}
\LinesNumbered
\footnotesize
\textbf{Input:} $\{\delta_j\}_{j=1}^L$, $\{h_j\}_{j=1}^L$, $l=2$, $k^\star=\infty$, $\bar{L}^\star=\infty$, \;
\For{$k=1$ to $\delta_L$}{
\eIf{$k=\delta_L$}{
Calculate $k_\text{UB}$ using \eqref{eqn:k0} and $\bar{L}(\pi_{k_\text{UB}};\beta)$ using \eqref{eqn:avg_cost}\;
\If{$\bar{L}(\pi_{k_\text{UB}};\beta)<\bar{L}^\star$}{
$\bar{L}^\star=\bar{L}(\pi_{k_\text{UB}};\beta)$\, $k^\star=k_\text{UB}$\;}
}{
\If{$k=\delta_{l-1}$}{
Calculate $B_{l-1}$, $O_l$, $I_l$ and $J_l$ using Table \ref{notations}\;
$l=l+1$\;
}
Calculate $\bar{L}(\pi_k;\beta)$ using \eqref{eqn:avg_cost}\;
\If{$\bar{L}(\pi_k;\beta)<\bar{L}^\star$}{
$\bar{L}^\star=\bar{L}(\pi_{k};\beta)$\, $k^\star=k$\;}
}
}
\textbf{Output:} $k^\star$, $\bar{L}^\star$;
\end{algorithm}

\textbf{Remark:} Relative value iteration (RVI) is a classical way to solve the average cost MDP. However, RVI requires updating value functions of all states in each iteration. Since the state space is infinite in this problem, the state space would have to be truncated before applying RVI, which could introduce a significant error from the optimal solution. Compared with RVI, the advantage of the proposed algorithm \ref{alg0} is as follows:

(i) In Algorithm \ref{alg0}, we avoid dealing with infinite space. Instead, we compare average costs of threshold-type policies with \emph{finite} different thresholds.

(ii) In terms of complexity, each iteration of RVI takes $O(MX)$, where $X$ is the bound for the age and should be larger than $\delta_L$ to reduce offset from the optimal solution. However, Algorithm \ref{alg0} takes $O(\delta_L+M)$ to find the optimal threshold /policy for \eqref{avg_cost}, which {\em has less complexity than even two iterations of RVI}.

\subsection{Lagrangian multiplier estimate}
In Theorem \ref{Ori_Lag}, we have shown that the optimal policy for the average-age MDP \eqref{ori_prob} is a mixture of two stationary deterministic policies $\pi_{\beta^\star,1}$ and $\pi_{\beta^\star,2}$, each of which is optimal for the average age-plus-cost MDP \eqref{avg_cost}.

Our idea is to construct two sequences $\beta_n$ and $\beta_n'$ such that they satisfy
$\beta_n\leq \beta_n'$, $\beta_n \uparrow \beta^\star$ and $\beta'_n\downarrow \beta^\star$. By \cite{ceran2019average}, in practice, we can use optimal policies $\pi^\star_{\beta^-}$ and $\pi^\star_{\beta^+}$ to approximate policies $\pi_{\beta^\star,1}$ and $\pi_{\beta^\star,2}$, where $\beta^-\triangleq \beta_n$ and $\beta^+ \triangleq \beta'_n$ for reasonably large $n$; and $\pi^\star_{\beta^-}$ and $\pi^\star_{\beta^+}$ are optimal policies that solve \eqref{avg_cost} associated with $\beta^-$ and $\beta^+$, respectively. With $\beta^-$ and $\beta^+$, the randomization factor $\mu$ is calculated by
\begin{align}
    \mu=\frac{E_\text{max}-\bar{E}(\pi^\star_{\beta^+})}{\bar{E}(\pi^\star_{\beta^-})-\bar{E}(\pi^\star_{\beta^+})},
    \label{mu_cal}
    \vspace{-0.3cm}
\end{align}
where $\bar{E}(\pi)$ is the average energy cost under policy $\pi$ as defined in \eqref{avg_energy}. Then, the optimal policy for the average-age MDP chooses $\pi^\star_{\beta^-}$ with probability $\mu$ and $\pi^\star_{\beta^+}$ with probability $1-\mu$ after each successful delivery.

In Algorithm \ref{alg1}, we provide a way to obtain parameters $\beta^+$, $\beta^-$ and $\mu$, which determines the optimal policy for the average-age MDP \eqref{ori_prob}. In particular, we use the bisection method to obtain $\beta^-$ and $\beta^+$ that follows the methodology in \cite{sennott1993constrained}.
In Algorithm~\ref{alg1}, the expression of the average energy cost with a threshold $k$ is
\begin{small}
\begin{align}
    &\bar{E}(\pi_k)=\Bigg\{\frac{ F(h_{{l_k}-1})}{1-B_{{l_k}-1}}+\mathbbm{1}_{\{l_k\leq L\}}(B_{{l_k}-1})^{\delta_{l_k}-k}\bigg(-\frac{ F(h_{{l_k}-1})}{1-B_{{l_k}-1}}\notag\\

    &+\sum_{j=l_k}^{L}w(l_k,j) F(h_j)\frac{1-\mathbbm{1}_{\{j<L\}}(B_{j})^{\delta_{j+1}-\delta_j}}{1-B_j}\bigg)\Bigg\}z^{-1},
    \label{avg_cost_cal}
\end{align}
\end{small}

where $z=k-1+(1-B_{{l_k}-1})^{-1}+\mathbbm{1}_{\{l_k\leq L\}}I_{l_k} (B_{{l_k}-1})^{\delta_{l_k}-k}$ and $l_k$ is defined previously in \eqref{eqn:def_lk}. The derivation of \eqref{avg_cost_cal} is part of the proof of Theorem \ref{cost_cal}.

\begin{algorithm}
\SetAlCapFnt{\footnotesize}
\caption{\footnotesize Low-complexity Optimal Transmission Scheduler Estimator}
\label{alg1}
\LinesNumbered
\footnotesize
\textbf{Input:} $\epsilon>0$, $\beta^{-}$, $\beta^{+}$ \;
\While{$|\beta^+-\beta^-|>\epsilon$}{
$\beta=(\beta^++\beta^-)/2$\;
For the new $\beta$, obtain optimal threshold $k^\star$using Algorithm~\ref{alg0}\;
Calculate average energy cost using \eqref{avg_cost_cal}\;
 \eIf{$\bar{E}(\pi_{k^\star})>E_{\text{max}}$}{
 $\beta^-=\beta$\;}{
 $\beta^+=\beta$\;
 }
 }
 Compute $\mu$ using \eqref{mu_cal}\;
\textbf{Output:} $\mu$, $\beta^+$ and $\beta^-$\;
\end{algorithm}

\vspace{-0.4cm}
\section{Simulations}
\label{sec:simu}
In this section, we numerically evaluate the performance of
the proposed algorithms.
\subsection{Optimal threshold for problem \eqref{avg_cost}}
\label{sec:simu1}
To provide more insights, we investigate how the optimal threshold varies with $\beta$ and error probabilities, respectively.
\subsubsection{Constant distortion requirement}
We first simulate the special case. In the simulation, we set $h=5$, $M=10$ and $q_m=q$, $\forall m$. Fig. \ref{fig:opt_thre_f} studies the optimal threshold versus $W$ given $p=0.5$ and $\beta \in\{5,10,20\}$, where $W$ is changed by changing $q$. From Fig. \ref{fig:opt_thre_f}, we observe that the optimal threshold increases with $W$. Fig. \ref{fig:opt_thre_p} studies the optimal threshold versus $p$ given $\beta=10$ and $W\in\{0.03,0.36,0.83\}$. From Fig. \ref{fig:opt_thre_p}, we observe that the optimal threshold increases with $p$ for $W=0.36$ or $W=0.83$ ($\beta>\frac{1}{W}$). Moreover, for all cases in Figs. \ref{fig:opt_thre_f} and \ref{fig:opt_thre_p} that satisfy $\beta<\frac{1}{W}$, the optimal threshold is one. These observations confirm our theoretical results in Theorem~\ref{lem:special_case}.
\begin{figure}
    \centering    \includegraphics[width=0.42\textwidth]{specCase_optThre_W}
    \caption{Optimal threshold $\Delta^\star_{\beta,\text{cons}}$ vs $W$ given $p=0.5$}
    \label{fig:opt_thre_f}
    \vspace{-0.5cm}
\end{figure}

\begin{figure}

    \centering    \includegraphics[width=0.42\textwidth]{specCase_optThre_p}
    \caption{Optimal threshold $\Delta^\star_{\beta,\text{cons}}$ vs $p$ given $\beta=10$}
    \label{fig:opt_thre_p}
   \vspace{-0.7cm}
\end{figure}

\subsubsection{Non-decreasing age-vs-distortion requirement}
For general non-decreasing distortion function, we set $M=8$, $L=3$, and $q_m=q$, $\forall m$. The distortion function is given by $\delta_1=1, \delta_2=25, \delta_3=50$ and $h_1=2, h_2=5, h_3=7$. Also see Fig.~\ref{fig:distfun_inc}.

Under the above mentioned parameter settings, we obtain the optimal threshold for different $\beta\in \{5, 25, 45\}$, and error probabilities $p\in \{0.1, 0.2,\cdots 0.9\}$ and $q \in \{0.1, 0.2,\cdots 0.9\}$ using Algorithm \ref{alg0}.
The results are summarized in Fig. \ref{fig:OptThre}.
In each sub-figure of Fig. \ref{fig:OptThre}, we investigate the impact of $p$ and $q$ on the optimal threshold. On one side, we observe that the optimal threshold decreases with $q$. This is consistent with the analysis result in the constant $D(\cdot)$ case in Sec.~\ref{sec:special_case} even though we do not have any analytical proof of this phenomenon. The intuition is that the increase of $q$ will reduce the probability that the distortion requirement is satisfied. This increases the demand for more transmission opportunities to maintain low age, which reduces the optimal threshold. On the other side, we observe that the optimal threshold either increases or deceases or first increases and then decreases with $p$ (see $q=0.6$ in Figs.~\ref{fig:thre_beta5},~\ref{fig:thre_beta25}, and \ref{fig:thre_beta45}). Whether the optimal threshold increases with $p$ depends on whether the age or the energy cost is the dominant issue, also see our discussion right after Theorem~\ref{new}. In particular, when the dominant issue to deal with is the energy cost, the optimal threshold increases with $p$. This is because increasing $p$ implies increasing energy consumption for a successful update. To save energy, the optimal threshold is increased. When the dominant issue to deal with is the age, the optimal threshold decreases with $p$. This is because that the increase of $p$ implies that more transmission attempts are needed for a successful delivery. To keep the age low, the optimal threshold should be reduced to provide more transmission opportunities.

Moreover, comparing Figs. \ref{fig:thre_beta5}, \ref{fig:thre_beta25} and \ref{fig:thre_beta45}, we observe that the optimal threshold increases with $\beta$. This is because as $\beta$ increases, more weights are placed on the energy cost, which requires increasing the threshold to reduce the energy cost.
\ifreport
 \begin{figure*}[]
 \centering
 \subfloat[$\beta=5$]{
 \includegraphics[scale=.35]{Age_dist/OptThre_N8_beta5.eps}
 \label{fig:thre_beta5}
 }\
 \subfloat[$\beta=25$]{
 \includegraphics[scale=.35]{Age_dist/OptThre_N8_beta25.eps}
 \label{fig:thre_beta25}
 }\\
 %
 \subfloat[$\beta=45$]{
 \includegraphics[scale=.35]{Age_dist/OptThre_N8_beta45.eps}
 \label{fig:thre_beta45}
 }
 \caption{The optimal threshold $\Delta_\beta^\star$ vs transmission error probabilities with different values of $\beta$}
 \label{fig:OptThre}
\end{figure*}
\else
\begin{figure*}[]
 \subfloat[$\beta=5$]{
 \includegraphics[scale=.28]{OptThre_N8_beta5}
 \label{fig:thre_beta5}
 }\
 \subfloat[$\beta=25$]{
 \includegraphics[scale=.28]{OptThre_N8_beta25}
 \label{fig:thre_beta25}
 }\
 \subfloat[$\beta=45$]{
 \includegraphics[scale=.28]{OptThre_N8_beta45}
 \label{fig:thre_beta45}
 }
 \caption{The optimal threshold $\Delta_\beta^\star$ vs transmission error probabilities with different values of $\beta$}
 \label{fig:OptThre}
\end{figure*}
\fi

\vspace{-0.2cm}
\subsection{Comparison with greedy policy}
Let $e_t$ denote the total energy consumption before the time slot $t$. Then, $\bar{e}_t=e_t/(t-1)$ denotes the average energy cost consumed before $t$. In this part, we compare the Algorithm \ref{alg1} with a greedy policy which transmits
whenever transmission is allowed (i.e., $\Lambda\geq D(\Delta)$) and if the empirical energy cost is less than the energy budget (i.e., $\bar{e}_t<E_\text{max}$).
The setting is same as in 2) of \ref{sec:simu1}.
\ifreport
\begin{figure}
    \centering
    \includegraphics[width=0.65\textwidth]{Age_dist/comp_greedy.eps}
    \caption{Average age vs energy constraint $E_{\text{max}}$ using the proposed policy (Algorithm \ref{alg1}) and greedy policy}
    \vspace{-0.7cm}
    \label{fig:comp_greedy}
\end{figure}
\else
\begin{figure}

    \centering    \includegraphics[width=0.41\textwidth]{comp_greedy2}
    \caption{Average age vs energy constraint $E_{\text{max}}$ using the proposed policy (Algorithm \ref{alg1}) and greedy policy}
    \label{fig:comp_greedy}
         \vspace{-0.7cm}
\end{figure}
\fi
When $E_{\text{max}}=1$, zero-waiting policy is obviously optimal and thus is considered uninteresting. In practical application like remote health, the transmission is likely to be only a small fraction of the total time duration because of the excessive energy consumption. This makes tight energy constraint more interesting to study.
In Fig. \ref{fig:comp_greedy}, we
observe that when $0.04\leq E_{\text{max}}\leq 0.2$, the improvement of our policy is quite significant, $30\%$ to $70\%$ reduction of cost.

\section{Conclusion}
\ifreport
In this chapter,
\else
In this paper,
\fi
we investigate an age minimization problem with constraints on the long-term average energy consumption and distortion of each update. The problem is formulated as a constrained MDP. Through the Lagrangian multiplier technique, we connect the problem to an average cost problem \eqref{avg_cost}, and show that the optimal policy is a mixture of two stationary deterministic policies (Theorem \ref{Ori_Lag}), each of which is optimal for the average cost problem and of a threshold-type (Theorem \ref{opt_stru}). Then, we obtain the average cost under the threshold-type policy, which is a piecewise function of threshold (Theorem \ref{cost_cal}), and we find the optimal threshold value in the last interval (Theorem \ref{new}). With these, we avoid dealing with infinite state space when using a classical solution RVI, and develop low-complexity algorithms. In the special, but practically very important case of constant distortion requirements, we obtain a closed-form solution (Corollary \ref{cor: special_case}). We show that the optimal threshold increases with the probability that distortion requirement is met, and the impact of transmission error probability $p$ on the optimal threshold depends on whether it is age or energy being the dominant issue (Theorem \ref{lem:special_case}).

\section{system model}
\label{scheduler}
We consider a status update system, in which an access point collects samples from multiple sensors, combines the samples to form update and then transmits the update to a remote monitor/receiver, as shown in Fig. \ref{sysmodel}.
We consider a time-slotted system and we use $t\in\{1,2,\cdots\}$ to index each time slot. At the beginning of each time slot, $M$ sensors sample the same physical process from their own view and attempt to transmit samples to the access point over the wireless channels. Then, the access point decides whether to transmit an update, which consists of all collected samples, to the remote monitor, i.e., selecting action $u_{t} \in \mathcal{U}\triangleq\{0,1\}$, where $u_{t}=1$ means transmission, and $u_{t}=0$ denotes suspension of the transmission.

We assume that all channels are error-prone. Specifically, the error probability of a transmission from the sensor $m$ to the access point is $q_m$, for $m\in\{1,2,\cdots,M\}$, and the error probability of the transmission from the access point to the receiver is $p$.
\ifreport
\begin{figure}[h]
    \centering
    \includegraphics[width=0.65\textwidth]{Age_dist/SysModel.pdf}
    \caption{System Model}
    \label{sysmodel}
\end{figure}
\else
\begin{figure}[h]
\vspace{-0.2cm}
    \centering
    \includegraphics[width=0.36\textwidth]{SysModel.pdf}
    \caption{System Model}
    \vspace{-0.5cm}
    \label{sysmodel}
\end{figure}
\fi

\subsection{Age of Information}
Age of information (AoI), or the age reflects the timeliness of the information at the receiver. It is defined as the time elapsed since the generation of the most recently received update at the receiver. Let $\Delta_{t}$ denote the age at the beginning of the time slot $t$. Let $U(t)$ denote the generation time of the last successfully received status update for time slot $t$. Then, $\Delta_{t}$ is given by $\Delta_{t}\triangleq t-U(t)$.

If the transmission of an update is not successful in a time slot, then the age increases by one, otherwise, the age drops to one.
Then, the value of $\Delta_{t+1}$ is updated as follows:

\begin{align}
\label{age_update}
& \Delta_{t+1}=

  \begin{cases
  1 & \text{if transmission is successful}, \\
  1+\Delta_{t} & \text{otherwise}.
  \end{cases}
\end{align}
We assume that $\Delta_1=1$.
\subsection{Distortion and Energy constraints}
\label{sec: const}
Since transmissions from sensors to the access point are not reliable, the number of samples collected by the access point at each time slot varies from $0$ to $M$.
Assume that the distortion of an update, which consists of all collected samples, depends on the number of collected samples.
We use $\Lambda_t$ to denote the number of collected samples at time slot $t$. To guarantee the quality of each update, we suspend access-point transmission whenever $\Lambda_t<D(\Delta_t)$, where $D(\cdot)$ is a function that maps the age to the minimum number of samples required for transmission.

We assume that $D(\cdot)$ is a non-decreasing function of the age on $[1,\infty)$ (since the smallest age is 1). Since $\Lambda_t$ is of integer value, without loss of generality, $D(\cdot)$ can be viewed as a piecewise constant function, which consists of $L\in \mathbb{N}^+$ intervals. Let $\delta_l$ denote the leftmost point of the $l$-th interval for $ 1\leq l\leq L$ and $\delta_{L+1}=\infty$. Then, the $l$-th interval is $[\delta_l,\delta_{l+1})$ and $\delta_1=1$. We use $h_l$ to denote the value over the $l$-th interval of domain, i.e, $h_l=D(\delta_l)$. Given $1\leq l<l'\leq L$, we have $h_l<h_{l'}$.
We assume that $h_1\geq 1$ and $h_L\leq M$. This is reasonable since if $h_L> M$, the transmission will never be conducted after the age exceeds $\delta_L$.
Fig. \ref{fig:distfun_inc} provides an example of the distortion function, where $L=3$ and $M=8$.
\ifreport
\begin{figure}
    \centering
    \includegraphics[width=0.55\textwidth]{Age_dist/Dfun_inc.pdf}
    \caption{Example of distortion function}
    \label{fig:distfun_inc}
\end{figure}
\else
\begin{figure}
    \centering
    \includegraphics[width=0.4\textwidth]{Dfun_inc.pdf}
    \caption{Example of distortion function}
    \vspace{-0.8cm}
    \label{fig:distfun_inc}
\end{figure}
\fi

The access point consumes energy for each transmission. We assume that each transmission consumes the same energy which is normalized as one unit energy, a setting similar to \cite{tsai2021jointly}. To avoid excessive energy consumption, we employ a long-term average energy consumption constraint for the access point. Note that in the system, sensors take samples periodically, and their energy consumption is fixed and thus not included in our optimization problem.

\subsection{Optimization Problem}
A transmission control policy $\pi=\{d_1,d_2,\cdots\}$ specifies the decision rules for each time slot, where a decision rule $d_t$ is a function that maps the past actions, past and current age and the number of collected samples to actions.
Our objective is to design a transmission control policy $\pi$ that minimizes the following long-term average age

\begin{align}
	&\bar{A}(\pi)\triangleq \lim_{T \rightarrow \infty} \frac{1}{T}\mathbb{E_\pi}\big[\sum_{t=1}^T \Delta_t\big],
	\label{avg_age}
\end{align}
while the long-term average energy consumption $\bar{E}(\pi)$ must not exceed $E_{\text{max}}\in (0,1]$, i.e.
\begin{align}
	&\bar{E}(\pi)\triangleq \lim_{T \rightarrow \infty} \frac{1}{T}\mathbb{E_\pi}\big[\sum_{t=1}^T u_t\big]\leq E_\text{max},
	\label{avg_energy}
\end{align}
and the distortion requirement is satisfied, i.e.
\begin{align}
    \Lambda_t\geq u_t D(\Delta_t),\ \  \forall t\geq 1,\label{dist_req}
\end{align}
where $\mathbb{E}_\pi$ denotes expectation under policy $\pi$.

\section{Constrained MDP Formulation and Lagrangian Relaxation}
\label{sec: formulation}
\subsection{Constrained MDP Formulation}
\label{components}
The optimization problem can be formulated as a constrained MDP. The components of the MDP are as follows:

\textbf{States:} The system state consists of the age and the number of collected samples, i.e., the system state at time slot $t$ is denoted by a tuple $\mathbf{s}_t=(\Delta_t,\Lambda_t)$. Then, the state space is given by $\mathcal{S}\triangleq \{(\Delta,\Lambda): \Delta\in \mathbb{N}^+,  \Lambda\in\{0,1,\cdots,M\}\}$, which is infinite.

\textbf{Actions:} Action set is $\mathcal{U}=\{0,1\}$ as defined in Section \ref{scheduler}. Due to distortion requirement in \eqref{dist_req}, $u=1$ can be taken only when $\Lambda\geq D(\Delta)$. Define $A_{\mathbf{s}_t}\triangleq \{u_t\in \mathcal{U}: \Lambda_t\geq u_t D(\Delta_t)\}$ as the admissible action set in state $\mathbf{s}_t$ which satisfies the distortion requirement.
For example, with distortion requirement in Fig. \ref{fig:distfun_inc}, we have $A_{(5, 5)}=\{0,1\}$ while $A_{(51, 5)}=\{0\}$.

\textbf{Transition Probability:} Given the current state $\mathbf{s}_{t}= (\Delta_{t}, \Lambda_{t})$ and action $u_{t}$ at time slot $t$, the transition probability to the state $\mathbf{s}_{t+1}=(\Delta_{t+1}, \Lambda_{t+1})$ at the next time slot $t+1$, which is denoted by $P_{\mathbf{s}_{t}\mathbf{s}_{t+1}}(u_t)$, is defined as
 \begin{align}
	P_{\mathbf{s}_{t}\mathbf{s}_{t+1}}(u_t)&\triangleq\mathbb{P}(\mathbf{s}_{t+1}|\mathbf{s}_{t},u_{t})\notag\\
&=\mathbb{P}(\Delta_{t+1}|\Delta_t,u_t)P_\Lambda(\Lambda_{t+1})
\end{align}
where
\begin{align}
&\mathbb{P}(\Delta_{t+1}|\Delta_t,u_t)=
  \begin{cases
  p & \text{if}\, \, u_{t}=1,\Delta_{t+1}=1+\Delta_t \\
  1-p & \text{if} \, \, u_{t}=1,\Delta_{t+1}=1,\\
  1 &\text{if} \, \, u_{t}=0,\Delta_{t+1}=1+\Delta_t,\\
  0 & \text{otherwise},
  \end{cases}
\end{align}
and $P_\Lambda(\Lambda_{t+1})\triangleq\mathbb{P}(\Lambda\!=\!\Lambda_{t+1})$.

\textbf{Costs:} Given a state $\mathbf{s}_t=(\Delta_{t}, \Lambda_{t})$ and an action choice $u_t$ at time slot $t$, the cost of one slot is the age at the beginning of this slot, i.e., we have
\begin{equation}
	C_\Delta(\mathbf{s}_t,u_{t})=\Delta_{t}.
\end{equation}
Moreover, the energy consumption of one slot is
\begin{equation}
	C_E(\mathbf{s}_t,u_{t})=u_t.
\end{equation}

Let $\Pi$ denote the set of \emph{feasible} policies that satisfy the distortion constraint, i.e., $u_t\in A_{\mathbf{s}_t}$, $\forall t$. Then, the transmission control problem can be formulated as a constrained Average-age MDP:

\textit{Problem 1 (Average-age MDP):}
\begin{alignat}{2}
\label{ori_prob}
 \bar{A}^\star\triangleq   \min_{\pi\in\Pi} \quad & \bar{A}(\pi)= \limsup_{T \rightarrow \infty} \frac{1}{T}\mathbb{E_\pi}\big[\sum_{t=1}^T C_\Delta(\mathbf{s}_{t},u_{t})\big] &  \\
    \mathrm{s.t.} \quad & \bar{E}(\pi)=\limsup_{T \rightarrow \infty} \frac{1}{T}\mathbb{E_\pi}\big[\sum_{t=1}^T C_E(\mathbf{s}_{t},u_{t})\big] \leq E_{\text{max}}, &   \nonumber

\end{alignat}
where $\bar{A}^\star$ is the optimal average age.
\subsection{Lagrange Relaxation of the Constrained MDP}
To obtain the optimal transmission control policy, we reformulate the average-age MDP in \eqref{ori_prob} as a parameterized average cost MDP. Given Lagrange multiplier $\beta$, the instantaneous Lagrangian cost at time slot $t$ is defined by
\begin{align}
	C(\mathbf{s}_{t},u_{t};\beta)=C_\Delta(\mathbf{s}_{t},u_{t})+\beta C_E(\mathbf{s}_{t},u_{t}).
	\label{inst_lag_cost}
\end{align}
Then, the long-term average Lagrangian cost under policy $\pi$ is given by
\begin{align}
	&\bar{L}(\pi;\beta)= \lim_{T \rightarrow \infty} \frac{1}{T}\mathbb{E_\pi}\big[\sum_{t=1}^T C(\mathbf{s}_{t},u_{t}; \beta)\big].\label{Lag_main}
\end{align}

Then, we have an average cost MDP, which aims at obtaining a feasible optimal policy $\pi\in\Pi$ that minimizes the long-term average Lagrangian cost above:

\textit{Problem 2 (Average cost MDP):}
\begin{align}
	\bar{L}^\star(\beta)  \triangleq &\min_{\pi\in \Pi}  \bar{L}(\pi;\beta).
	\label{avg_cost}
\end{align}
where $\bar{L}^\star(\beta)$ is the optimal average Lagrangian cost with regard to $\beta$.

A policy is \emph{stationary} if the decision rule is independent of time, i.e., $d_{t}=d$, for all $t$. Moreover, a policy is \emph{randomized} if $d_t: \mathcal{S}\rightarrow \mathcal{P}(\mathcal{U})$ specifies a probability distribution on the set of actions. The policy is \emph{deterministic} if $d_t: \mathcal{S} \rightarrow \mathcal{U}$ chooses an action with certainty.

\begin{theorem}
\label{Ori_Lag}
There exists a stationary randomized policy that solves the average-age MDP \eqref{ori_prob}. This policy can be expressed as a mixture of two stationary deterministic policies $\pi_{\beta^\star,1}$ and $\pi_{\beta^\star,2}$, where $\pi_{\beta^\star,1}$ and $\pi_{\beta^\star,2}$ differ in
at most a single state $\mathbf{s}$, and are both optimal policies for the average cost MDP \eqref{avg_cost} given $\beta^\star$. The mixture policy $\pi_{\beta^\star}$ uses $\pi_{\beta^\star,1}$ with probability $\mu$ and $\pi_{\beta^\star,2}$ with probability $1-\mu$ in state $s$; it uses either policy (since they coincide) in other states, where $\mu\in [0,1]$
\end{theorem}
\begin{proof-sketch}
Please see Appendix \ref{proof_ori_lag}.
\end{proof-sketch}
\vspace{0.1cm}

\section{Average Cost MDP with Non-decreasing Distortion Function}
\label{sec: average_cost}
In this section, we investigate optimal policies that solve \eqref{avg_cost}. In particular, we derive the structure of the optimal policies. With this, we obtain the expression of the average Lagrangian cost as a function of a threshold $k$ and prove a property of the function, which are used in designing low-complexity algorithms in Section \ref{sec:alg_design}. Moreover, we analyze a special case - constant distortion function to provide more insights.

\subsection{Structure of the optimal policies}
\label{sec: main_res}
In this part, we first study the structure of the optimal policies, and then obtain the average cost function with regard to a threshold.

\begin{table*}[h]
\centering
\footnotesize
\caption{\small{Notations}}
\label{notations}
\begin{tabular}{l}
\hline\hline
$F(r)= \sum_{j=r}^{M}P_\Lambda(j), \ \ \forall \ 0\leq r\leq M$\\ \hline
$B_{l}=1-(1-p)F(h_l), \ \ \forall \ 1\leq l\leq L$\\ \hline
$w(i,j)=\mathbbm{1}_{\{i<j\}}\prod_{v=i}^{j-1}(B_{v})^{\delta_{v+1}-\delta_v}+\mathbbm{1}_{\{i\geq j\}}$
\\ \hline
 $J_{l}=-\frac{1}{(1-B_{{l}-1})^2}-\frac{\delta_{l}-1+\beta F(h_{{l}-1})}{1-B_{{l}-1}}$\\
 \ \ \ \ \ \ $+\sum_{j={l}}^{L}w({l},j)\Big(\frac{1-\mathbbm{1}_{\{j<L\}}(B_{j})^{\delta_{j+1}-\delta_j}\big(1+(\delta_{j+1}-1+\beta F(h_j))(1-B_j)\big)}{(1-B_j)^2}
    +\frac{\delta_j-1+\beta F(h_j)}{1-B_j}\Big), \ \ \forall \ 2\leq l\leq L$
 \\\hline $I_{l}=-\frac{1}{1-B_{{l}-1}}+\sum_{j={l}}^{L}\frac{1-\mathbbm{1}_{\{j<L\}}(B_{j})^{\delta_{j+1}-\delta_j}}{1-B_j}w(l,j), \ \ \forall \ 2\leq l\leq L$
 \\ \hline $O_{l}=\frac{1}{(1-B_{{l}-1})^2}+\frac{-1+\beta F(h_{{l}-1})}{1-B_{{l}-1}}, \ \ \forall \ 2\leq l\leq L+1$
 \\ \hline \hline
\end{tabular}
\vspace{-0.4cm}
\end{table*}

\begin{theorem}
\label{opt_stru}
For any fixed $\beta$, there exists an optimal age threshold $\Delta_\beta^\star$ such that the following policy $\pi_\beta^\star =(d_{\beta}^{\star},d_{\beta}^{\star},\cdots)$ where
\begin{align}
&d_{\beta}^{\star}(\Delta,\Lambda)=
  \begin{cases
  1 & \text{if}\, \, \Delta\geq \Delta_{\beta}^\star \, \ \text{and}\, \ \Lambda\geq D(\Delta),\\
  0 & \text{otherwise},
  \end{cases} \label{optPol}
\end{align}
achieves the minimum average Lagrangian cost in \eqref{avg_cost}.

\end{theorem}
\begin{proof}
Please see Section \ref{proof_thre1}.
\end{proof}
By Theorem \ref{opt_stru}, the optimal policies for \eqref{avg_cost} are of threshold-type in the age. That is, if $D(\Delta_t)\!\!\!>\!\!\Lambda_t$, then the access point is not allowed to transmit due to the imposed maximum allowable distortion criterion. In the scenario  $D(\Delta_t)\!\leq\! \Lambda_t$,  the optimal policy would transmit if and only if the age $\Delta_t$ exceeds $\Delta_\beta^\star$.

Given a threshold, we can draw a state transition diagram under policy \eqref{optPol}, and obtain its average Lagrangian cost. In Theorem \ref{cost_cal}, we obtain the average cost as a function of threshold.
\par Recall that $\delta_l$ is the leftmost point of the $l$-th interval in the distortion requirement function $D(\cdot)$, see Fig.~\ref{fig:distfun_inc} and Sec.~\ref{sec: const}. Given any $k\in\mathbb{N}^+$, define
\begin{equation}
    l_k\triangleq \min\{l\leq L+1: \delta_l>k\}. \label{eqn:def_lk}
\end{equation}
Since per our definition $\delta_{L+1}=\infty$, we always have $l_k\leq L+1$. We then have the following results.

\begin{theorem}
\label{cost_cal}
Using policy $\pi_k$ in the form of \eqref{optPol} with threshold $k\in\mathbb{N}^+$, the long-term average Lagrangian cost is expressed as:
\begin{footnotesize}
\begin{align}
   &\bar{L}(\pi_k;\beta) \notag\\
   =&\frac{0.5k^2-0.5k+(1-B_{{l_k}-1})^{-1}k
    +\mathbbm{1}_{\{l_k\leq L\}}J_{l_k} (B_{l_k-1})^{\delta_{l_k}-k}+O_{l_k}}{k-1+(1-B_{{l_k}-1})^{-1}
    +\mathbbm{1}_{\{l_k\leq L\}}I_{l_k} (B_{l_k-1})^{\delta_{l_k}-k}},\label{eqn:avg_cost}
\end{align}
\end{footnotesize}
for which the expressions of $\{B_{l}\}_{l=1}^L$, $\{J_{l}\}_{l=2}^L$, $\{I_{l}\}_{l=2}^L$, and $\{O_{l}\}_{l=2}^{L+1}$ are given in Table \ref{notations}.
\end{theorem}
\begin{proof-sketch}
With aid of the state transition diagram under the policy $\pi_k$, we obtain steady state probability of each state, which enables us to obtain the average cost $\bar{L}(\pi_k;\beta)$.
\end{proof-sketch}

The closed-form expression of $\bar{L}(\pi_k;\beta)$ allows us to search for the optimal threshold $k^\star$ numerically.  Unfortunately, the expression of \eqref{eqn:avg_cost} versus the threshold $k$ may exhibit complicated behavior (e.g., neither convex nor concave) and the domain of $k$ is unbounded.  To overcome these two challenges, we prove in the subsequent Theorem~\ref{new} that among the domain of $k\geq \delta_L$, we can analytically find the optimal $k_\text{UB}$.  Therefore, to search for the optimal $k^\star$, we only need to exhaustively evaluate $\bar{L}(\pi_k;\beta)$ for all $k\in \{1,2,\cdots,\delta_L-1\}$, compare their values to $\bar{L}(\pi_{k_\text{UB}};\beta)$ in Theorems~\ref{cost_cal} and~\ref{new}, and then find the globally minimum $k^\star$. Also see our discussion of low-complexity algorithm in Sec.~\ref{sec:alg_design}.

\begin{theorem}
\label{new}
Among the sub-domain $k\geq \delta_L$, the $k$ that leads to the smallest $\bar{L}(\pi_k;\beta)$ is given by
\begin{align}
    k_\text{UB} &\triangleq \argmin_{k\geq \delta_L}\bar{L}(\pi_k;\beta)\\
    &=\max\{\delta_L,y\}, \label{eqn:k0}
\end{align}
where
\begin{small}
\begin{align}
    y\!=\!\Bigg\lceil\!\!-\!\frac{1+B_L}{2(1-B_L)}\!+\!\left(\frac{B_L^2}{(1-B_L)^2}\!+\!\frac{B_L\!+\!2\beta F(h_L)}{1-B_L}\!+\!\frac{1}{4}\right)^{0.5}\!\Bigg \rceil.
\end{align}
\end{small}
\end{theorem}

\begin{proof-sketch}
To find the $k$ that minimizes $\bar{L}(\pi_k;\beta)$ among the sub-domain $k\geq \delta_L$, we show that $\bar{L}(\pi_k;\beta)$ either increases, or first decreases and then increases with $k$ on the sub-domain.
\end{proof-sketch}

\subsection{Special Case - Constant Distortion}
\label{sec:special_case}
In this part, we consider a special case, where the distortion function is a constant function, i.e., $D(\Delta)=h\leq M$, $\forall \Delta$. Note that constant distortion function belongs to the set of non-decreasing distortion functions. Thus, the results in Section \ref{sec: main_res} hold for this special case.
Further, for the constant distortion function, $L\!=\!1$. By Theorem \ref{new}, we can directly obtain the optimal threshold. The results are summarized in the following corollary.

\begin{corollary}
\label{cor: special_case}
Given $\beta$ and constant distortion function $D(\Delta)=h$, there exists a stationary deterministic policy that solves problem \eqref{avg_cost}, which is in the form  $\pi_{\beta,\text{cons}}^{\star}=(d_{\beta,\text{cons}}^{\star},d_{\beta,\text{cons}}^{\star},\cdots)$, where
\begin{align}
&d_{\beta,\text{cons}}^{\star}(\Delta,\Lambda)=
  \begin{cases
  1 & \text{if}\, \,\Delta\geq \Delta_{\beta,\text{cons}}^\star\, \ \text{and}\, \ \Lambda\geq D(\Delta),\\
  0 & \text{otherwise},
  \end{cases}
\end{align}
where the optimal threshold
$\Delta_{\beta,\text{cons}}^\star$ is given by
\begin{footnotesize}
\begin{align}
    \Delta_{\beta,\text{cons}}^\star\!\! =
    \!\max\Bigg\{\!1,\!\Bigg\lceil\!\!-\!\frac{1+R}{2(1\!-\!R)}\!+\!\sqrt{ \!\frac{R^2}{(1\!-\!R)^2}\!+\!\frac{R\!+\!2\beta W}{1\!-\!R}\!+\!\frac{1}{4}}\Bigg \rceil\Bigg\},
    \label{opt_threval_spec}
\end{align}
\end{footnotesize}
where $W=\sum_{j=h}^{M}P_\Lambda(j)$ and $R=1-(1-p) W$.
\end{corollary}

\textbf{Remark:} By Corollary \ref{cor: special_case}, the optimal threshold $\Delta_{\beta,\text{cons}}^\star$ depends on Lagrangian multiplier $\beta$, distortion requirement $h$, the distribution on the number of collected samples $P_\Lambda(\cdot)$ and channel unreliability $p$. By simple algebraic simplification of \eqref{opt_threval_spec}, it is easy to show that when $\beta=0$, which corresponds to the case without energy constraint, we have $\Delta_{\beta,\text{cons}}^\star=1$. In addition, $\Delta_{\beta,\text{cons}}^\star$ is non-decreasing with $\beta$. This is because that the increase of $\beta$ implies higher weights of the energy cost. To save energy cost, the threshold should be increased to reduce the transmission frequency.

To provide more insights on the special case of constant distortion, we investigate how $W$ (determined by $h$, $P_\Lambda(\cdot)$) and $p$ affect the optimal threshold $\Delta_{\beta,\text{cons}}^\star$ in Theorem \ref{lem:special_case}.

\begin{theorem}
\label{lem:special_case}
Given $\beta>0$ and $D(\Delta)=h$, we have the following properties:

(i) If $\beta >\frac{1}{W}$, the optimal threshold $\Delta_{\beta,\text{cons}}^\star$ is non-decreasing with $p$; if $\beta <\frac{1}{W}$, the optimal threshold $\Delta_{\beta,\text{cons}}^\star$ is non-increasing with $p$;

(ii) In fact, we can further strengthen the second half of (i) by the following: If $\beta <\frac{1}{W}$, the optimal threshold $\Delta_{\beta,\text{cons}}^\star=1$;

(iii) The optimal threshold $\Delta_{\beta,\text{cons}}^\star$ is non-decreasing with $W$.
\end{theorem}
\begin{proof-sketch}
Please see Appendix \ref{app: special_case}.
\end{proof-sketch}
\vspace{0.2cm}

\textbf{Remark}
Note that the Lagrangian multiplier $\beta$ can be viewed as the energy price of one transmission, and $\frac{1}{W}$ {\em is the expected duration between two consecutive slots when the distortion requirement is met}, which implies the age price of suspension. Then, the intuition of the theorem can be explained as follows:
\begin{itemize}
    \item
In the case $\beta >\frac{1}{W}$, the energy cost matters. Then, as $p$ increases (channel worsens), the optimal threshold may be increased to save energy as stated in (i) of Theorem~\ref{lem:special_case}. In contrast, the age cost matters when $\beta <\frac{1}{W}$. Then, the optimal threshold needs to be decreased to obtain more transmission opportunities as $p$ increases.
\item For any $W$, if $p=0$ (reliable transmission from the access point to the receiver), then $\beta-\frac{1}{W}$ implies the instant cost of transmission minus the minimal instant cost of suspension. In the case, if $\beta-\frac{1}{W}<0$, then the optimal threshold is 1. Together with (i) that $\Delta^\star_{\beta,\text{cons}}$ is non-increasing with $p$ if $\beta<\frac{1}{W}$, we obtain (ii).
\item
The intuition of (iii) is as follows. For any given $\beta$, $W$, the optimal threshold $\Delta^\star_{\beta,\text{cons}}$ would perfectly balance the age cost and the energy cost in \eqref{avg_cost}. Consider a slightly larger $W'>W$. Since $\frac{1}{W}$ is the expected duration between two consecutive slots when the distortion requirement is met, the duration under $W'$ would be slightly smaller. The impact of having more chance to potentially transmit would increase the energy cost (since we send more frequently) and decrease the age cost (since we send more frequently). As a result, to re-balance the two, the optimal policy would further increase $\Delta^\star_{\beta,\text{cons}}$ under the new $W'$.
\end{itemize}

\subsection{Proof of Theorem \ref{opt_stru}}
\label{proof_thre1}
A method to study average cost MDPs is to relate them to discounted cost MDPs. In this section, we (i) define discounted cost MDPs; (ii) obtain optimal policies for the discounted cost MDPs; and (iii) extend results to the average cost MDPs.

Given discount factor $\alpha \in (0, 1)$ and an initial state $\mathbf{s}$, the total expected discounted Lagrangian cost under policies $\pi\in\Pi$ is given by
\begin{align}
	&L_{\mathbf{s}}^{\alpha}(\pi;\beta)= \limsup_{T \rightarrow \infty} \mathbb{E}_{\pi}\big[\sum_{t=1}^T \alpha^{t-1}C(\mathbf{s}_{t},u_{t};\beta)|\mathbf{s}\big],
	\label{disc_cost0}
\end{align}

Then, the optimization problem of minimizing the total expected discounted Lagrangian cost while satisfying distortion requirement can be cast as

\textit{Problem 3 (Discounted cost MDP):}
\begin{equation}
	V^{\alpha}(\mathbf{s})\triangleq\min_{\pi\in\Pi} \ L_{\mathbf{s}}^\alpha(\pi;\beta),
	\label{disc_cost_opt_00}
\end{equation}
where $V^{\alpha}(\mathbf{s})$ denotes the optimal total expected $\alpha$-discounted Lagrangian cost (for convenience, we omit $\beta$ in $V^{\alpha}(\mathbf{s})$).

In Proposition \ref{existence_discount_00}, we introduce the optimality equation of $V^{\alpha}(\mathbf{s})$.
\begin{proposition}
\label{existence_discount_00}
	\noindent	(a) The optimal total expected $\alpha$-discounted Lagrangian cost, given by $V^{\alpha}(\Delta,\Lambda)$, satisfies the optimality equation as follows:
	\begin{align}
		V^{\alpha}\left(\Delta,\Lambda\right)=\min_{u\in A_{(\Delta,\Lambda)}}  Q^{\alpha}\left(\Delta,\Lambda;u\right), \label{opt_equ_disc_00}
	\end{align}
	where
	\begin{align}
		Q^{\alpha}\left(\Delta,\Lambda;0\right)\!=&\Delta\!+\!\alpha \mathbb{E}V^{\alpha}\left(\Delta+1,\Lambda'\right);\label{q1_}\\

		Q^{\alpha}\left(\Delta,\Lambda;1\right)\!=&\Delta\!+\!\beta
		\!+\!\alpha \Big(p \mathbb{E}V^{\alpha}\left(\Delta+1, \Lambda'\right)\notag\\
		&+\!(1\!-\!p)\mathbb{E}V^{\alpha}\left(1,\Lambda'\right)\Big).\label{q2_}
	\end{align}

\noindent(b) A stationary deterministic policy determined by the right-hand-side of \eqref{opt_equ_disc_00} solves problem \eqref{disc_cost_opt_00}

\noindent (c) Let $V_n^{\alpha}(\mathbf{s})$ be the cost-to-go function such that
$V_0^{\alpha}(\mathbf{s})\!=\!0$, for all $\mathbf{s}\in\mathcal{S}$ and for $n\geq 0$,
		\begin{align}
		V_{n+1}^{\alpha}(\Delta,\Lambda)=\min_{u\in A_{(\Delta,\Lambda)}} Q_{n+1}^{\alpha}(\Delta,\Lambda;u),
		\label{iteration00}
	    \end{align}
	    where
	    \begin{align}
		Q_{n+1}^{\alpha}\left(\Delta,\Lambda;0\right)=&\Delta+\alpha\mathbb{E} V_{n}^{\alpha}\left(\Delta+1,\Lambda'\right);\label{q1}\\
		Q_{n+1}^{\alpha}\left(\Delta,\Lambda;1\right)=&\Delta+\beta+\alpha \Big(p\mathbb{E} V_{n}^{\alpha}\left(\Delta+1, \Lambda'\right) \notag\\&+(1-p)\mathbb{E}V_{n}^{\alpha}
		\left(1,\Lambda'\right)\Big).\label{q2}
	    \end{align}
	    Then, we have $V_n^{\alpha}(\mathbf{s}) \rightarrow V^{\alpha}(\mathbf{s})$ as $n\rightarrow \infty$, $\forall \mathbf{s}, \alpha$.
\end{proposition}
\begin{proof-sketch}
By \cite{sennott1989average}, it suffices to show that there exists a stationary deterministic policy $f\in\Pi$ such that for all $\alpha$ and $\mathbf{s}$, we have $L_{\mathbf{s}}^\alpha(f;\beta)\!<\!\!\infty$. A policy that chooses $u=0$ at every time slot satisfies this.
\end{proof-sketch}

Using the induction method in (c) of Proposition \ref{existence_discount_00}, we first show some properties of $V^{\alpha}(\mathbf{s})$ in Lemma \ref{property_00}.
\begin{lemma}
\label{property_00}
Given $\alpha$, the value function $V^{\alpha}(\mathbf{s})$ has properties:

(i) The value function $V^{\alpha}(\mathbf{s})$ is non-decreasing with $\Delta$.

(ii) The value function $V^\alpha(\mathbf{s})$ is non-increasing with $\Lambda$.
\end{lemma}
\begin{proof-sketch}
By Proposition \ref{existence_discount_00}, $V_n^{\alpha}(\mathbf{s}) \!\!\rightarrow\!\! V^{\alpha}(\mathbf{s})$ as $n\rightarrow \infty$. Thus, we show that $V_n^{\alpha}(\mathbf{s})$ has (i) and (ii) for $n\in \mathbb{N}$. Obviously, $V_0^{\alpha}(\mathbf{s})$ has properties (i) and (ii) since $V_0^{\alpha}(\mathbf{s})=0$. Then, we show that given $V_n^{\alpha}(\mathbf{s})$ has the properties (i) and (ii), $V_{n+1}^{\alpha}(\mathbf{s})$ has these properties, $\forall n\geq 0$.
\end{proof-sketch}
\vspace{0.2cm}

Using the properties in Lemma \ref{property_00}, we further show that the optimal policies that solve discounted cost MDPs in \eqref{disc_cost_opt_00} are of threshold-type in Lemma \ref{disc_stru0}.
\begin{lemma}
\label{disc_stru0}
Given $\beta,\alpha$, the optimal policy that solves the discounted cost MDP \eqref{disc_cost_opt_00} is of threshold-type in the age. Specifically, there exists a threshold $\Delta_{\alpha,\beta}^{\star}$ such that it is optimal to transmit only when the age exceeds the threshold and the distortion requirement is met, i.e., $ \Delta\geq \Delta_{\alpha,\beta}^{\star} $ and $\Lambda\geq D(\Delta)$.
\end{lemma}
\begin{proof}
Please see Appendix \ref{proof_disc_stru}.
\end{proof}

 By \cite{sennott1989average}, under certain conditions (A proof of these conditions verification is provided in Appendix \ref{proof_cond}), the optimal policy for problem \eqref{avg_cost} can be viewed as a limit of a sequence of the optimal policies for the $\alpha$-discounted cost problems in \eqref{disc_cost_opt_00} as $\alpha\to 1$. Thus, there exist stationary deterministic policies that solve problem \eqref{avg_cost}, and the optimal policies are in the form \eqref{optPol}.

\section{Low-complexity Algorithm for average-age MDP}
\label{sec:alg_design}
In this section, we design a low-complexity algorithm for the average-age MDP. In particular, we first design a low-complexity algorithm to obtain the optimal policy for the average cost MDP \eqref{avg_cost} given $\beta$, and then provide a way to determine optimal Lagrangian multiplier $\beta$.
\subsection{Optimal policy for average cost MDP \eqref{avg_cost}}
In Theorem \ref{opt_stru}, we show that the optimal policy for \eqref{avg_cost} is of a threshold-type in the form of \eqref{optPol}. In order to obtain the optimal policy for \eqref{avg_cost}, it remains to obtain optimal threshold $\Delta_\beta^\star$. Using Theorems~\ref{cost_cal} and \ref{new}, we can find $\Delta_\beta^\star$ by the following Algorithm~\ref{alg0}.

\begin{algorithm}
\caption{Optimal Threshold Calculator}
\label{alg0}
\LinesNumbered
\footnotesize
\textbf{Input:} $\{\delta_j\}_{j=1}^L$, $\{h_j\}_{j=1}^L$, $l=2$, $k^\star=\infty$, $\bar{L}^\star=\infty$, \;
\For{$k=1$ to $\delta_L$}{
\eIf{$k=\delta_L$}{
Calculate $k_\text{UB}$ using \eqref{eqn:k0} and $\bar{L}(\pi_{k_\text{UB}};\beta)$ using \eqref{eqn:avg_cost}\;
\If{$\bar{L}(\pi_{k_\text{UB}};\beta)<\bar{L}^\star$}{
$\bar{L}^\star=\bar{L}(\pi_{k_\text{UB}};\beta)$\, $k^\star=k_\text{UB}$\;}
}{
\If{$k=\delta_{l-1}$}{
Calculate $B_{l-1}$, $O_l$, $I_l$ and $J_l$ using Table \ref{notations}\;
$l=l+1$\;
}
Calculate $\bar{L}(\pi_k;\beta)$ using \eqref{eqn:avg_cost}\;
\If{$\bar{L}(\pi_k;\beta)<\bar{L}^\star$}{
$\bar{L}^\star=\bar{L}(\pi_{k};\beta)$\, $k^\star=k$\;}
}
}
\textbf{Output:} $k^\star$, $\bar{L}^\star$;
\end{algorithm}

\textbf{Remark:} Relative value iteration (RVI) is a classical way to solve the average cost MDP. However, RVI requires updating value functions of all states in each iteration. Since the state space is infinite in this problem, the state space would have to be truncated before applying RVI, which could introduce a significant error from the optimal solution. Compared with RVI, the advantage of the proposed algorithm \ref{alg0} is as follows:

(i) In Algorithm \ref{alg0}, we avoid dealing with infinite space. Instead, we compare average costs of threshold-type policies with \emph{finite} different thresholds.

(ii) In terms of complexity, each iteration of RVI takes $O(MX)$, where $X$ is the bound for the age and should be larger than $\delta_L$ to reduce offset from the optimal solution. However, Algorithm \ref{alg0} takes $O(\delta_L+M)$ to find optimal threshold /policy for \eqref{avg_cost}, which has less complexity than even two iterations of RVI.

\vspace{-0.5cm}
\subsection{Lagrangian multiplier estimate}
In Theorem \ref{Ori_Lag}, we have shown that the optimal policy for the average-age MDP \eqref{ori_prob} is a mixture of two stationary deterministic policies $\pi_{\beta^\star,1}$ and $\pi_{\beta^\star,2}$, each of which is optimal for the average cost MDP \eqref{avg_cost}.

Our idea is to construct two sequences $\beta_n$ and $\beta_n'$ such that they satisfy
$\beta_n\leq \beta_n'$, $\beta_n \uparrow \beta^\star$ and $\beta'_n\downarrow \beta^\star$. By \cite{ceran2019average}, in practice, we can use optimal policies $\pi^\star_{\beta^-}$ and $\pi^\star_{\beta^+}$ to approximate policies $\pi_{\beta^\star,1}$ and $\pi_{\beta^\star,2}$, where $\beta^-\triangleq \beta_n$ and $\beta^+ \triangleq \beta'_n$ for reasonably large $n$; and $\pi^\star_{\beta^-}$ and $\pi^\star_{\beta^+}$ are optimal policies that solve \eqref{avg_cost} associated with $\beta^-$ and $\beta^+$, respectively. With $\beta^-$ and $\beta^+$, the randomization factor $\mu$ is calculated by
\begin{align}
\vspace{-0.5cm}
    \mu=\frac{E_\text{max}-\bar{E}(\pi^\star_{\beta^+})}{\bar{E}(\pi^\star_{\beta^-})-\bar{E}(\pi^\star_{\beta^+})},
    \label{mu_cal}
    \vspace{-0.3cm}
\end{align}
where $\bar{E}(\pi)$ is the average energy cost under policy $\pi$ as defined in \eqref{avg_energy}. Then, the optimal policy for the average-age MDP chooses $\pi^\star_{\beta^-}$ with probability $\mu$ and $\pi^\star_{\beta^+}$ with probability $1-\mu$ after each successful delivery.

In Algorithm \ref{alg1}, we provide a way to obtain parameters $\beta^+$, $\beta^-$ and $\mu$, which determines the optimal policy for the average-age MDP \eqref{ori_prob}. In particular, we use bisection method to obtain $\beta^-$ and $\beta^+$ that follows the methodology in \cite{sennott1993constrained}.
In Algorithm~\ref{alg1}, the expression of the average energy cost with a threshold $k$ is
\begin{small}
\begin{align}
    &\bar{E}(\pi_k)=\Bigg\{\frac{ F(h_{{l_k}-1})}{1-B_{{l_k}-1}}+\mathbbm{1}_{\{l_k\leq L\}}(B_{{l_k}-1})^{\delta_{l_k}-k}\bigg(-\frac{ F(h_{{l_k}-1})}{1-B_{{l_k}-1}}\notag\\

    &+\sum_{j=l_k}^{L}w(l_k,j) F(h_j)\frac{1-\mathbbm{1}_{\{j<L\}}(B_{j})^{\delta_{j+1}-\delta_j}}{1-B_j}\bigg)\Bigg\}z^{-1},
    \label{avg_cost_cal}
\end{align}
\end{small}
where $z=k-1+(1-B_{{l_k}-1})^{-1}+\mathbbm{1}_{\{l_k\leq L\}}I_{l_k} (B_{{l_k}-1})^{\delta_{l_k}-k}$ and $l_k$ is defined previously in \eqref{eqn:def_lk}. The derivation of \eqref{avg_cost_cal} is part of the proof of Theorem \ref{cost_cal}.

\begin{algorithm}
\caption{Low-complexity Optimal Transmission Scheduler Estimator}
\label{alg1}
\LinesNumbered
\footnotesize
\textbf{Input:} $\epsilon>0$, $\beta^{-}$, $\beta^{+}$ \;
\While{$|\beta^+-\beta^-|>\epsilon$}{
$\beta=(\beta^++\beta^-)/2$\;
For the new $\beta$, obtain optimal threshold $k^\star$using Algorithm~\ref{alg0}\;
Calculate average energy cost using \eqref{avg_cost_cal}\;
 \eIf{$\bar{E}(\pi_{k^\star})>E_{\text{max}}$}{
 $\beta^-=\beta$\;}{
 $\beta^+=\beta$\;
 }
 }
 Compute $\mu$ using \eqref{mu_cal}\;
\textbf{Output:} $\mu$, $\beta^+$ and $\beta^-$\;
\end{algorithm}

\section{Simulations}
\label{sec:simu}
In this section, we numerically evaluate the performance of
the proposed algorithms.
\subsection{Optimal threshold for problem \eqref{avg_cost}}
\label{sec:simu1}
To provide more insights, we investigate how the optimal threshold varies with $\beta$ and error probabilities, respectively.
\subsubsection{Constant distortion requirement}
We first simulate the special case. In simulation, we set $h=5$, $M=10$ and $q_m=q$, $\forall m$. Fig. \ref{fig:opt_thre_f} studies the optimal threshold versus $W$ given $p=0.5$ and $\beta \in\{5,10,20\}$, where $W$ is changed by changing $q$. From Fig. \ref{fig:opt_thre_f}, we observe that the optimal threshold increases with $W$. Fig. \ref{fig:opt_thre_p} studies the optimal threshold versus $p$ given $\beta=10$ and $W\in\{0.03,0.36,0.83\}$. From Fig. \ref{fig:opt_thre_p}, we observe that the optimal threshold increases with $p$ for $W=0.36$ or $W=0.83$ ($\beta>\frac{1}{W}$). Moreover, for all cases in Figs. \ref{fig:opt_thre_f} and \ref{fig:opt_thre_p} that satisfy $\beta<\frac{1}{W}$, the optimal threshold is one. These observations confirm our theoretical results in Theorem~\ref{lem:special_case}.
\begin{figure}[H]
\vspace{-0.2cm}
    \centering
    \includegraphics[width=0.42\textwidth]{specCase_optThre_W.eps}
    \caption{Optimal threshold $\Delta^\star_{\beta,\text{cons}}$ vs $W$ given $p=0.5$}
    \label{fig:opt_thre_f}
    \vspace{-0.2cm}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.42\textwidth]{specCase_optThre_p.eps}
    \caption{Optimal threshold $\Delta^\star_{\beta,\text{cons}}$ vs $p$ given $\beta=10$}
    \label{fig:opt_thre_p}
   \vspace{-0.5cm}
\end{figure}

\subsubsection{Non-decreasing age-vs-distortion requirement}
For general non-decreasing distortion function, we set $M=8$, $L=3$, and $q_m=q$, $\forall m$. The distortion function is given by $\delta_1=1, \delta_2=25, \delta_3=50$ and $h_1=2, h_2=5, h_3=7$. Also see Fig.~\ref{fig:distfun_inc}.

With this, we obtain the optimal threshold for different $\beta\in \{5, 25, 45\}$, and error probabilities $p\in \{0.1, 0.2,\cdots 0.9\}$ and $q \in \{0.1, 0.2,\cdots 0.9\}$ using Algorithm \ref{alg0}.
The results are summarized in Fig. \ref{fig:OptThre}.
In each sub-figure of Fig. \ref{fig:OptThre}, we investigate the impact of $p$ and $q$ on the optimal threshold. On one side, we observe that the optimal threshold decreases with $q$. This is consistent with the analysis result in the constant $D(\cdot)$ case in Sec.~\ref{sec:special_case} even though we do not have any analytical proof of this phenomenon. The intuition is that the increase of $q$ will reduce the probability that the distortion requirement is satisfied. This increases the demand for more transmission opportunities to maintain low age, which reduces the optimal threshold. On the other side, we observe that the optimal threshold either increases or deceases or first increases and then decreases with $p$ (see $q=0.6$ in Figs.~\ref{fig:thre_beta5},~\ref{fig:thre_beta25}, and \ref{fig:thre_beta45}). Whether the optimal threshold increases with $p$ depends on whether the age or the energy cost is the dominant issue, also see our discussion right after Theorem~\ref{new}. In particular, when the dominant issue to deal with is the energy cost, the optimal threshold increases with $p$. This is because increasing $p$ implies increasing energy consumption for a successful update. To save energy, the optimal threshold is increased. When the dominant issue to deal with is the age, the optimal threshold decreases with $p$. This is because that the increase of $p$ implies that more transmission attempts are needed for a successful delivery. To keep the age low, the optimal threshold should be reduced to provide more transmission opportunities.

Moreover, comparing Figs. \ref{fig:thre_beta5}, \ref{fig:thre_beta25} and \ref{fig:thre_beta45}, we observe that the optimal threshold increases with $\beta$. This is because as $\beta$ increases, more weights are placed on the energy cost, which requires increasing the threshold to reduce the energy cost.
\ifreport
 \begin{figure*}[]
 \centering
 \subfloat[$\beta=5$]{
 \includegraphics[scale=.35]{Age_dist/OptThre_N8_beta5.eps}
 \label{fig:thre_beta5}
 }\
 \subfloat[$\beta=25$]{
 \includegraphics[scale=.35]{Age_dist/OptThre_N8_beta25.eps}
 \label{fig:thre_beta25}
 }\\
 %
 \subfloat[$\beta=45$]{
 \includegraphics[scale=.35]{Age_dist/OptThre_N8_beta45.eps}
 \label{fig:thre_beta45}
 }
 \caption{The optimal threshold $\Delta_\beta^\star$ vs transmission error probabilities with different values of $\beta$}
 \label{fig:OptThre}
\end{figure*}
\else
\begin{figure*}[]
 \subfloat[$\beta=5$]{
 \includegraphics[scale=.28]{OptThre_N8_beta5.eps}
 \label{fig:thre_beta5}
 }\
 \subfloat[$\beta=25$]{
 \includegraphics[scale=.28]{OptThre_N8_beta25.eps}
 \label{fig:thre_beta25}
 }\
 \subfloat[$\beta=45$]{
 \includegraphics[scale=.28]{OptThre_N8_beta45.eps}
 \label{fig:thre_beta45}
 }
 \caption{The optimal threshold $\Delta_\beta^\star$ vs transmission error probabilities with different values of $\beta$}
 \label{fig:OptThre}
      \vspace{-0.5cm}
\end{figure*}
\fi

\vspace{-0.2cm}
\subsection{Comparison with greedy policy}
Let $e_t$ denote the total energy consumption before the time slot $t$. Then, $\bar{e}_t=e_t/(t-1)$ denotes the average energy cost consumed before $t$. In this part, we compare the Algorithm \ref{alg1} with a greedy policy which transmits
whenever transmission is allowed (i.e., $\Lambda\geq D(\Delta)$) and if the empirical energy cost is less than the energy budget (i.e., $\bar{e}_t<E_\text{max}$).
The setting is same as in 2) of \ref{sec:simu1}.
\ifreport
\begin{figure}
    \centering
    \includegraphics[width=0.65\textwidth]{Age_dist/comp_greedy.eps}
    \caption{Average age vs energy constraint $E_{\text{max}}$ using the proposed policy (Algorithm \ref{alg1}) and greedy policy}
    \label{fig:comp_greedy}
\end{figure}
\else
\begin{figure}
 \vspace{-0.2cm}
    \centering
    \includegraphics[width=0.43\textwidth]{comp_greedy.eps}
    \caption{Average age vs energy constraint $E_{\text{max}}$ using the proposed policy (Algorithm \ref{alg1}) and greedy policy}
    \label{fig:comp_greedy}
         \vspace{-0.6cm}
\end{figure}
\fi

In Fig. \ref{fig:comp_greedy}, we observe that under either policy, the average age decreases with $E_{\text{max}}$. Moreover, Algorithm \ref{alg1} outperforms the greedy policy, and the gap between Algorithm \ref{alg1} and the greedy policy is the largest when under a tight energy constraint (small $E_\text{max}$).
\section{Structure of Average-Optimal Policy and Algorithm Design}
\label{structure}
In this section, we investigate the structure of the average-optimal policy and propose an efficient algorithm for the original problem \eqref{equiv1}.
\subsection{Threshold Structure of Average-Optimal Policy}
\label{struc}
\subsubsection{Threshold structure:}
The following theorem states that there exists a threshold-type stationary deterministic policy that is average-optimal. In particular, the problem is divided into two cases based on the relation between $d_1(1-p_2)$ and $d_2(1-p_1)$. Under these two cases, the threshold-type average-optimal policy shows opposite behaviors.
\begin{theorem}
\label{THRE_PROP}
There exists a stationary deterministic average-optimal transmission selection policy that is of threshold-type. Specifically,

\noindent(i) If $d_1(1-p_2)\leq d_2(1-p_1)$, then the average-optimal policy is of the form $\pi^*=(\zeta^*,\zeta^*,\cdots)$, where
\begin{align}
\label{type2}
 &\zeta^*(a)=
  \begin{cases
  2 & \text{if}\, \, 0\leq a\leq a_1^*, \\
  1 & \text{if} \, \,a_1^*< a,
  \end{cases}
\end{align}
where $a_1^*$ denotes the age threshold.

\noindent(ii) If $d_1(1-p_2)\geq d_2(1-p_1)$, then the average-optimal policy is of the form $\pi^*=(\zeta^*,\zeta^*,\cdots)$, where
\begin{align}
\label{type1}
 &\zeta^*(a)=
  \begin{cases
  1 & \text{if}\, \, 0\leq a\leq a_2^*, \\
  2 & \text{if} \, \,a_2^*< a,
  \end{cases}
\end{align}
where $a_2^*$ denotes the age threshold.

\end{theorem}
\begin{proof}
	Please see Section \ref{proof}.
\end{proof}

Define the mean delay of transmission mode $j\in\mathcal{U}$ as
\begin{align}
	\bar{d}_j\triangleq\frac{d_j}{1-p_j}.
	\label{mean_delay}
\end{align}
By Theorem \ref{THRE_PROP} (i), when the age exceeds a certain threshold, the optimal policy chooses the transmission with smaller mean delay. This result reveals an interesting phenomenon: While the transmission with minimum mean delay is the optimal decision for minimizing the average delay, this does not necessarily minimize the age.
In particular, when the age is below a certain threshold, the average age is reduced by choosing a faster transmission that has a higher mean delay (i.e., a higher error probability). The reason is that if successful, the age remains low. If it fails, it provides an opportunity to generate a later packet that can be transmitted in a shorter period of time.

In Section \ref{alg}, based on Theorem \ref{THRE_PROP} (ii), we will show that the averge-optimal policy under $d_1(1-p_2)\geq d_2(1-p_1)$ is to choose high rate transmission for each transmission opportunity. This is reasonable because both the delay and mean delay (including the impact of the error probability) of high rate transmission is shorter than that of low rate transmission.

\subsubsection{Proof of Theorem \ref{THRE_PROP}}
\label{proof}
One way to investigate the average cost MDPs is to relate them to the discounted cost MDPs. To prove Theorem \ref{THRE_PROP}, we (i) address a discounted cost MDP, i.e., establish the existence of a stationary deterministic policy that solves the MDP and then study the structure of the optimal policy; and (ii) extend the results to the average cost MDP problem in \eqref{avg_prob}.

Given an initial state $a$, the total expected $\alpha$-discounted cost under a transmission selection policy $\pi\in \Pi$ is given by
\begin{align}
	V^\alpha(a;\pi)=\limsup_{n\rightarrow\infty}\mathbb{E}\left[\sum_{i=0}^{n-1}\alpha^i C(a_i,u_i)\right],
	\label{disc_cost}
\end{align}
where $0<\alpha<1$ is the discount factor. Then, the optimization problem of minimizing the total expected $\alpha$-discounted cost can be cast as

\emph{Problem 2 (Discounted cost MDP)}
\begin{align}
	V^\alpha(a)\triangleq\min_{\pi\in \Pi} V^\alpha(a;\pi),
	\label{disc_prob}
\end{align}
where $V^\alpha(a)$ denotes the optimal total expected $\alpha$-discounted cost. A transmission selection policy is said to be \emph{$\alpha$-discounted cost optimal} if it solves the problem in \eqref{disc_prob}. In Proposition \ref{DISC_EXIST}, we show that there exists a stationary deterministic transmission selection policy which is $\alpha$-discounted cost optimal and provide a way to explore the property of the optimal policy.

\begin{proposition}
\label{DISC_EXIST}
(a) The optimal total expected $\alpha$-discounted cost $V^\alpha$ satisfies the following optimality equation:
\begin{align}
	V^\alpha(a)=\min_{u\in \mathcal{U}} Q^\alpha(a, u),
	\label{bellman_equ}
\end{align}
where
\begin{align}
	Q^\alpha(a, u)=C(a,u)+\alpha p_uV^\alpha(a+d_u)+\alpha(1-p_u)V^\alpha(d_u).
	\label{qvalue}
\end{align}

(b) The stationary deterministic policy determined by the right-hand-side of \eqref{bellman_equ} is $\alpha$-discounted cost optimal.

(c) Let $V_n^\alpha(a)$ be the cost-to-go function such that $V_0^\alpha(a)=\frac{d_1-d_2}{\alpha(p_2-p_1)}a$ and for $n\geq0$
\begin{align}
	V_{n+1}^\alpha(a)=\min_{u\in \mathcal{U}} Q_{n+1}^\alpha(a, u),
	\label{value_iter}
\end{align}
where
\begin{align}
	Q_{n+1}^\alpha(a, u)=C(a, u)+\alpha p_uV_n^\alpha(a+d_u)+\alpha(1-p_u)V_n^\alpha(d_u).
\end{align}
Then, we have that for each $\alpha$, $V_{n}^\alpha(a)\rightarrow V^\alpha(a)$ as $n\rightarrow \infty$.
\end{proposition}
 \ifreport
\begin{proof}
See Appendix \ref{proposition}.
\end{proof}
\else
\begin{proof}
See our technical report \cite{yao2020age}.
\end{proof}
\fi

Next, with the optimality equation \eqref{bellman_equ} and value iteration \eqref{value_iter}, we show that the optimal policy is of threshold-type in Lemma \ref{THRESHOLD}.

\begin{lemma} \label{THRESHOLD}
Given a discount factor $\alpha$,

(i) if $(1-\alpha p_2)d_1\leq (1-\alpha p_1)d_2$, then the $\alpha$-discounted cost optimal policy is of threshold-type, i.e., the optimal action is a non-increasing function of the age

(ii) if $(1-\alpha p_2)d_1\geq (1-\alpha p_1)d_2$, then the $\alpha$-discounted cost optimal policy is of threshold-type, i.e., the optimal action is a non-decreasing function of the age.

\end{lemma}

\begin{proof}
Please see Appendix \ref{discount_threshold}
\end{proof}

This lemma proves that the $\alpha$-discounted cost optimal policy is of threshold-type. Next, we extend the results to average cost MDP and show that there exists a stationary deterministic average-optimal policy which is of threshold-type. Based on the results in \cite{sennott1989average}, we have the following lemma, which provides a candidate for average-optimal policy.
\begin{lemma}
\label{CANDI}
	(i) Let $\alpha_n$ be any sequence of discount factors converging to 1 with $\alpha_n$-discounted cost optimal stationary deterministic policy $\pi^{\alpha_n}$. There exists a subsequence $\gamma_n$ and a stationary policy $\pi^*$ that is a limit point of $\pi^{\gamma_n}$.

	(ii) If $d_1(1-p_2)\leq d_2(1-p_1)$, $\pi^*$ is of threshold-type in \eqref{type2}; if $d_1(1-p_2)\geq d_2(1-p_1)$, $\pi^*$ is of threshold-type in \eqref{type1}.
\end{lemma}
\ifreport
\begin{proof}
See Appendix \ref{candidate_policy}.
\end{proof}
\else
\begin{proof}
See our technical report \cite{yao2020age}.
\end{proof}
\fi

\ifreport
By \cite{sennott1989average}, under certain conditions (A proof of these conditions verification is provided in Appendix \ref{app1}), $\pi^*$ is average-optimal.
\else
By \cite{sennott1989average}, under certain conditions (A proof of these conditions verification is provided in our technical report \cite{yao2020age}), $\pi^*$ is average-optimal.
\fi

\subsection{Algorithm Design}
\label{alg}
Recall that if $p(\beta)=0$, then the optimal transmission selection policies that solve \eqref{equiv1} and \eqref{equiv2} are identical. Given $\beta$, the optimal policy that solves \eqref{equiv2} is of threshold-type by Theorem \ref{THRE_PROP} and then \eqref{equiv2} can be re-expressed as
\begin{numcases}{p(\beta)=}
\min_{\pi \in \Pi_1} J(\pi,\beta), & if $d_1(1-p_2)< d_2(1-p_1)$\label{pBeta2}\\
\min_{\pi \in \Pi_2} J(\pi,\beta), & if $d_1(1-p_2)\geq d_2(1-p_1)$\label{pBeta1}
\end{numcases}
where $\Pi_1$ and $\Pi_2$ denote the sets of threshold-type policies in \eqref{type2} and \eqref{type1}, respectively.
Thus, the optimal policy that solves \eqref{equiv1} can be obtained with two steps:
\begin{itemize}

	\item \textbf{Step (i):} For each $\beta$, find the $\beta$-associated average-optimal policy $\pi^*_\beta$ such that $p(\beta)=J(\pi^*_\beta,\beta)$.
\item \textbf{Step (ii):} Find $\beta^*$ such that $p(\beta^*)=0$. This implies $\pi^*_{\beta^*}$ solves \eqref{equiv1}.
\end{itemize}
To narrow our searching range in (ii), in Lemma \ref{BETA_RANGE}, we provide a lower bound $\beta_\text{min}$ and an upper bound $\beta_\text{max}$ of $\beta^*$. Then, for (i), we only need to pay attention to $p(\beta)$ for $\beta\in[\beta_\text{min},\beta_\text{max}]$.

In particular, within the range of $\beta$, we show that $J$ in \eqref{pBeta2} is \emph{quasi-convex} in a threshold related variable, which enables us to devise a \emph{low-complexity} algorithm based on golden section search. Moreover, we show that $\pi^*_\beta$ that solves \eqref{pBeta1} always chooses $u=2$, which allows us to get the optimal policy for \eqref{equiv1} directly.

\begin{lemma}
\label{BETA_RANGE}
	The parameter $\beta^*$ is lower bounded by $\beta_\text{min}\triangleq 1.5d_2$ and upper bounded by $\beta_\text{max}\triangleq\min\Big\{(\frac{1}{1-p_1}+0.5)d_1,(\frac{1}{1-p_2}+0.5)d_2\Big\}$.
\end{lemma}
\ifreport
\begin{proof}
See Appendix \ref{range}.
\end{proof}
\else
\begin{proof}
See our technical report \cite{yao2020age}.
\end{proof}
\fi

In the following content, we provide a theoretical analysis step by step for our algorithm design in Algorithm \ref{alg1}, which returns the optimal threshold and optimal average age for \eqref{equiv1}.

\begin{algorithm}[]
\caption{Threshold-based Age-Optimal Policy}
\label{alg1}
\LinesNumbered
\footnotesize
given $d_1$, $d_2$, $p_1$, $p_2$,$\tau=(\sqrt{5}-1)/2$, tolerance $\epsilon_1$, $\epsilon_2$, $l=\beta_\text{min}$, $r=\beta_\text{max}$\;
\While {$r-l>\epsilon_1$}{
 $\beta=\frac{r+l}{2}$\;
 \eIf{$d_1(1-p_2)\geq d_2(1-p_1)$}{
 $m=0$, $k=0$, $J^*=J_2(0,0,\beta)$\;}
 {
 $k_\text{max}=\lfloor\frac{d_1}{d_2}\rfloor$, $J^*=f(1,0,\beta)$\;
	\ForEach{ $k_1\in \{0,1,\cdots,k_\text{max}\}$ }{
		\eIf{$\frac{\partial J_1(y, k_1,\beta)}{\partial y}\vert_{y=1}<0$}{
			$m=0$\;
			}{
		$y_0=0$, $y_1=1$, $y_2=y_1-(y_1-y_0)\tau$, $y_3=y_0+(y_1-y_0)\tau$\;
		\While{$p_2y_1 \geq y_0$ and $y_1-y_0>\epsilon_2$}{
			\eIf{$J_1(y_2,k_1,\beta)>J_1(y_3,k_1,\beta)$}{
			$y_0=y_2$\;
			}{
			$y_1=y_3$\;
			}
			$y_2=y_1-(y_1-y_0)\tau$, $y_3=y_0+(y_1-y_0)\tau$\;
		}
		$t_1=\lfloor\log_{p_2} y_0\rfloor$, $t_2=\lceil\log_{p_2} y_1\rceil$\;
		$m=\argmin_{m\in\{t_1,t_2\}} J_1({p_2}^{m};k,\beta)$\;
		}
	 \If{$J_1(p_2^{m}, k_1,\beta)\leq J^*$}{
	 $J^*=J_1(p_2^{m}, k_1,\beta)$\;
	}
	}
	}
	\eIf{$J^*\geq0$}{
 			$l=\beta$\;}{
 			$r=\beta$\;
		}

}
\end{algorithm}

\textbf{Step (i): Find the optimal policy $\pi^*_\beta$:}
Note that both of the threshold-type policies defined in \eqref{type2} and \eqref{type1} result in a Markov chain with a single positive recurrent class. Thus, given threshold $a_1^*$ in \eqref{type2} or $a_2^*$ in \eqref{type1}, we can obtain the expression of average cost under the corresponding threshold-type policy with aid of state transition diagram. With this, we obtain some nice properties of average cost function in Theorem \ref{CONVEXITY}, which enables us to get a low-complexity algorithm. Before providing the result, we define the integer threshold which will be used in the theorem and algorithm.

Recall that age $a\in \mathcal{S}$ is expressed as the sum of multiple $d_1$'s and $d_2$'s.
Note that under the threshold-type policy in \eqref{type2}, if $ a\leq a_1^*$, $\zeta(a)=2$. This implies that if $ a\leq a_1^*$, $a$ is in the form $a=d_j+l d_2, j\in\mathcal{U}, l\in \mathbb{N}$. Thus, it is sufficient to use the following integer threshold to represent the threshold-type policy in \eqref{type2}.
\begin{align}
	m_1&\triangleq\min \left\{l: d_1+ld_2> a_1^*,l \in  \mathbb{N}\right\},\label{3}\\
	n_1&\triangleq\min \left\{l: d_2+ld_2> a_1^*,l \in  \mathbb{N} \right\}\label{4}.
\end{align}
With this, the threshold policy in \eqref{type2} is rewritten as
\begin{align}
 &\zeta^*(a)=
  \begin{cases
  2 & \text{if}\, \,  a< d_1+m_1d_2\ \ \text{and}\ \ a< d_2+n_1d_2, \\
  1 & \text{if} \, \,a\geq d_1+m_1d_2\ \ \text{or}\ \ a\geq d_2+n_1d_2.
  \end{cases}
  \label{new_type2}
\end{align}
Similarly, the policy in \eqref{type1} can be rewritten as
\begin{align}
 &\zeta^*(a)=
  \begin{cases
  1 & \text{if}\, \,  a< d_1+m_2d_1\ \ \text{and}\ \ a< d_2+n_2d_1, \\
  2 & \text{if} \, \,a\geq d_1+m_2d_1\ \ \text{or}\ \ a\geq d_2+n_2d_1,
  \end{cases}
  \label{new_type1}
\end{align}
where
\begin{align}
m_2&\triangleq\min \left\{l: d_1+ld_1> a_2^*, l \in \mathbb{N}\right\},\label{1}\\
	n_2&\triangleq\min \left\{l: d_2+ld_1> a_2^*, l \in \mathbb{N} \right\}\label{2}.
\end{align}

Based on the analysis, \eqref{pBeta2} and \eqref{pBeta1} can be re-expressed as
\begin{numcases}{p(\beta)=}
\min_{m_1, k_1} J_1(m_1, k_1,\beta), \! & \!if $d_1(1-p_2)\!\!<\! d_2(\!1-p_1\!)$ \label{target2}\\
\min_{m_2, k_2} J_2(m_2, k_2,\beta),\! & \!if $d_1(1-p_2)\!\!\geq \!d_2(\!1-p_1\!)$ \label{target1}
\end{numcases}
where $k_1=n_1-m_1$ and $k_2=n_2-m_2$. Also, we use $J_1(m_1, k_1,\beta)$ and $J_2(m_2, k_2,\beta)$ to denote the average cost under the policies in \eqref{new_type2} and \eqref{new_type1}, respectively. We have $k_2\in \mathcal{K}_2\triangleq\{0,1\}$ and $k_1\in \mathcal{K}_1\triangleq\big\{0,\cdots,\lfloor\frac{d_1}{d_2}\rfloor\big\}$. In particular, according to the definition of $m_2$ and $n_2$, we have $(m_2+1)d_1>a_2^*\geq d_2+(n_2-1)d_1$ and $d_2+n_2d_1>a_2^*\geq m_2d_1$. Substitute $k_2=n_2-m_2$ into these two inequalities, we get $k_2\in \mathcal{K}_2$. Similarly, we have $k_1\in \mathcal{K}_1$.

\begin{table}[]
\renewcommand\arraystretch{2}
\caption{Notations}
\footnotesize
\begin{tabular}{p{0.8mm}l}
\hline\hline
$A_1$&$= p_2^{k_1}\big(d_2(1-p_1)-d_1(1-p_2)\big)\big(d_2(k_1+1)-d_1\big)$ \\
\hline
$B_1$&$= -A_2+p_2^{k_1}(1-p_2)(0.5d_1^2-\beta d_1+\frac{d_1^2}{1-p_1})+(1-p_1)(\beta d_2-0.5d_2^2-\frac{d_2^2}{1-p_2})$ \\
\hline
$C_1$&$= (1-p_1)(0.5d_2^2-\beta d_2+\frac{1}{1-p_2})d_2^2$ \\
\hline
$D_1$&$= \big(d_1(1-p_2)-d_2(1-p_1)\big)d_2p_2^{k_1}$\\
\hline
$A_2$&$= p_1^{k_2}\big(d_1(1-p_2)-d_2(1-p_1)\big)\big(d_1(1-{k_2})-d_2\big)$\\
\hline
$B_2$&$= -p_1^{k_2}(1-p_2)(0.5d_1^2-\beta d_1+\frac{d_1^2}{1-p_1})+(1-p_1)(0.5d_2^2-\beta d_2+\frac{d_2^2}{1-p_2})$\\
	&$  \ \ \  \
	-\big(d_1(1-p_2)-d_2(1-p_1)\big)(d_1-d_2)$\\
\hline
$C_2$&$= (1-p_2)(0.5d_1^2-\beta d_1+\frac{d_1^2}{1-p_1})$ \\
\hline
$D_2$&$= \big(d_2(1-p_1)-d_1(1-p_2)\big)d_1$ \\
\hline\hline
\end{tabular}
\label{notations}
\end{table}

In Theorem \ref{CONVEXITY}, we provide some nice properties for $J_1$ and $J_2$, which enables us to develop a low-complexity algorithm. To this end, we make a change of variable in Theorem \ref{CONVEXITY} (i), i.e., $m_1$ is replaced with $\log_{p_2}(y)$ in $J_1$, where $y\in (0,1]$.
Some notations used in this theorem are defined in Table \ref{notations}.

\begin{theorem}
\label{CONVEXITY}
Given $\beta\in [\beta_\text{min}, \beta_\text{max}]$,

(i) if $d_1(1-p_2)<d_2(1-p_1)$, then the average cost is given by
\begin{equation}
 	J_1(y, k_1,\beta)=\frac{A_1y^{2}+B_1y+C_1+D_1y\log_{p_2}(y)}{1-p_1+(-1+p_1+p_2^{k_1}(1-p_2))y},
 	\label{cost2}
 \end{equation}
where $y\triangleq p_2^{m_1}$. Moreover, $J_1(y, k_1,\beta)$ is quasi-convex in $y$ for $0<y\leq 1$, given $k_1\in\mathcal{K}_1$.

(ii) if $d_1(1-p_2)\geq d_2(1-p_1)$, then optimal average cost is given by
	\begin{equation}
		J_2(0, 0,\beta)=\frac{A_2+B_2+C_2}{1-p_1}.
		\label{cost1}
	\end{equation}
Moreover, the average-optimal policy chooses $u=2$ at every transmission opportunity.
\end{theorem}
\ifreport
\begin{proof}
See Appendix \ref{convex_prop}.
\end{proof}
\else
\begin{proof}
Proof of part (i) is provided in Appendix \ref{convex_prop}. For part (ii), the key idea is to show that for all $m_2$,
 $J_2(m_2, k_2,\beta)$ is non-decreasing in $k_2\in \mathcal{K}_2$, and then $J_2(m_2, 0,\beta)$ is non-decreasing in $m_2$. This implies that the optimal decision is $u=2$ at each transmission opportunity. Due to the space limitation, detailed proof is provided in our technical report \cite{yao2020age}.
\end{proof}
\fi

With the property in Theorem \ref{CONVEXITY} (i), we are able to use golden section search \cite{press2007section} to find the optimal value of $y$ under condition $d_1(1-p_2)<d_2(1-p_1)$. The details are provided in Algorithm \ref{alg1} (Line 12-20).
 Note that $\log_{p_2}(\cdot)$ is one-to-one functions. Thus, after obtaining the optimal $y$ that minimizes $J_1$, the corresponding optimal threshold $m_1$ can be easily obtained by comparing
$J_1({p_2}^{\lfloor \log_{p_2}(y)\rfloor}, k_1,\beta)$ and $J_1({p_2}^{\lceil \log_{p_2}(y)\rceil}, k_1,\beta)$). The details are provided in Algorithm \ref{alg1} (Line 21-22).
Till now, we have solved $\min_{m_1} J_1(m_1, k_1,\beta)$ given $k_1$ and $\beta$. Note that $k_1\in\mathcal{K}_1$ has finite and countable values. Then, we can easily solve \eqref{target2} under condition $d_1(1-p_2)< d_2(1-p_1)$ by searching for the optimal $k_1$ in the finite set $\mathcal{K}_1$.

Note that Theorem \ref{CONVEXITY} (ii) applies to all $\beta\in \![\beta_\text{min},\! \beta_\text{max}\!]$ including $\beta^*$. Thus, the optimal policy for \eqref{equiv1} is to take $u=2$ at every transmission opportunity, which is returned directly in Algorithm \ref{alg1} (Line 4-5). Under this condition, the step (ii) is only used to find optimal average cost $\beta^*$ for \eqref{equiv1}.

Moreover, in Line 9-10, we add a judgement sentence, i.e., if the condition $\frac{\partial J_1(y,k_1,\beta)}{\partial y}\vert_{y=1}<0$ is satisfied, then we can directly obtain the optimal $m_1$ without running golden section method. This further reduces the algorithm complexity. The judgement is based on the fact that $\lim_{y\rightarrow 0}\frac{\partial J_1(y, k_1,\beta)}{\partial y}<0$ (this is proved in the proof of Theorem \ref{CONVEXITY} in Appendix \ref{convex_prop}) and $J_1$ is quasi-convex. Thus, if $\frac{\partial J_1(y, k_1,\beta)}{\partial y}\vert_{y=1}<0$, then $J_1$ is non-increasing in $y$.

\textbf{Step (ii): Find $\beta^*$:} By Lemma \ref{TRANS}, if $p(\beta)>0$, then $\beta<\beta^*$; if $p(\beta)<0$, then $\beta>\beta^*$. Thus, we can use bisection method to search for $\beta^*$. The details are provided in Algorithm \ref{alg1} (Line 2-3 and Line 29-33).

redpajama_set_name: RedPajamaArXiv