# Learning to Minimize Age of Information over an Unreliable Channel with
Energy Harvesting

Elif Tuğçe Ceran, Deniz Gündüz, and András György

###### Abstract

The time average expected age of information (AoI) is studied for status
updates sent over an error-prone channel from an energy-harvesting transmitter
with a finite-capacity battery. Energy cost of sensing new status updates is
taken into account as well as the transmission energy cost better capturing
practical systems. The optimal scheduling policy is first studied under the
hybrid automatic repeat request (HARQ) protocol when the channel and energy
harvesting statistics are known, and the existence of a threshold-based
optimal policy is shown. For the case of unknown environments, average-cost
reinforcement-learning algorithms are proposed that learn the system
parameters and the status update policy in real-time. The effectiveness of the
proposed methods is demonstrated through numerical results.

###### Index Terms:

Age of information, energy harvesting, hybrid automatic repeat request (HARQ),
Markov decision process, reinforcement learning, policy gradient, deep
Q-network (DQN).

00footnotetext: Part of this work is was presented at the IEEE Conference on
Computer Communications Workshops (INFOCOM WKSHPS), Paris, France, April 2019
[1].00footnotetext: This work was supported in part by the European Research
Council (ERC) Starting Grant BEACON (grant agreement no. 677854). E. T. Ceran
and D. Gündüz are with Imperial College London, UK (email: {e.ceran14,
<EMAIL_ADDRESS>A. György is with DeepMind, UK (email:
agyorgy@google.com).

##  I Introduction

Many status update systems, including wireless sensor networks in Internet of
things (IoT) applications, are powered by scavenging energy from renewable
sources (e.g., solar cells [2], wind turbines [3], piezoelectric generators
[4], etc.). Harvesting energy from ambient sources provides environmentally-
friendly and ubiquitous operation for remote sensing systems. Therefore, there
has been a growing interest in maximizing the timeliness of information in
energy harvesting (EH) communication systems [5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15, 16]. In these systems, the staleness of the information at the
receiver is measured by the age of information (AoI), defined as the time
elapsed since the generation time of the most recent status update
successfully received at the receiver.

Prior works have investigated online [5, 7, 10, 13, 14] as well as offline [5,
8, 15] methods for different scenarios in order to optimize the timeliness of
information under energy causality constraints in EH systems. The structure of
an optimal policy is derived and heuristic algorithms are proposed in [7, 10,
12, 13] for a finite-size battery considering only the cost of transmissions.
Until recently, literature on AoI assumed that the cost of sensing
(monitoring) the status of a process is negligible compared to the cost of
transmitting the status updates. However, in many practical sensing systems
acquiring a new sample of the underlying process of interest also has a
considerable energy cost [17, 18]. The sampling/sensing cost has been taken
into account in [18] and [19], where a status update system with automatic
repeat request (ARQ) and an unlimited energy source is considered. In [18],
closed form expressions are presented for the energy consumption and average
AoI with known transmission error probability, assuming that a packet is re-
transmitted until either it is received, or a prescribed maximum number of
transmissions is reached. In our previous work, we studied status-update
systems under a transmission-rate constraint, or equivalently, an average
power constraint [20, 21, 22].

In this paper, we study a status update system considering both the sensing
and transmission energy costs, better capturing practical systems.
size=,color=blue!20!white,size=,color=blue!20!white,todo:
size=,color=blue!20!white,A: What is better here? Other works also consider
transmission energy. Why is this sentence not in the previous paragraph?
size=,color=orange!20!white,size=,color=orange!20!white,todo:
size=,color=orange!20!white,E: modified Moreover, we consider an EH
transmitter, which uses the energy harvested from the environment to power the
sensing and communication operations. Unlike prior work [18], we consider the
intermittent availability of energy and a hybrid automatic repeat request
(HARQ) protocol, where the partial information obtained from previous
unsuccessful transmission attempts is combined to increase the probability of
successful decoding. When employing HARQ in status update systems, there is an
inherent trade-off between sending a new update after a failed transmission
attempt, which may result in a lower AoI, and retransmitting the failed
update, which has a lower probability of error. Introducing sensing cost to
the system model makes this trade-off even more challenging and interesting,
as retransmissions incur no sensing cost.

In most practical scenarios statistical information about either the energy
arrival process or the channel conditions are not available a-priori, or may
change over time [23]. Previous works on EH communication systems without
a-priori information on the random processes governing the system exploited
reinforcement learning (RL) methods in order to maximize throughput or
minimize delay [24, 25]. In this paper, we propose RL algorithms that can
adapt the status-update scheme to the unknown energy arrival process as well
as the channel statistics.

Our goal will be to identify the optimal policy that can judiciously balance
the AoI benefits of transmitting a new status update with its additional
sensing cost and lower success probability. The optimal decisions will depend
not only on the current AoI and retransmission count, but also on the battery
and energy harvesting states. We consider a value-based RL algorithm, _GR-
learning_ [26], a policy-based RL algorithm, _finite-difference policy
gradient (FDPG)_ [27], and a deep RL algorithm _deep Q-network (DQN)_ , and
compare their performances with that of the relative value iteration (RVI)
algorithm which assumes a-priori knowledge on the system characteristics. We
propose threshold policy with low computational complexity
size=,color=blue!20!white,size=,color=blue!20!white,todo:
size=,color=blue!20!white,A: Why do we propose a suboptimal policy? Why do we
use a threshold policy?
size=,color=orange!20!white,size=,color=orange!20!white,todo:
size=,color=orange!20!white,E: Modified and demonstrate that a policy gradient
algorithm exploiting the structural characteristics of a threshold policy
outperforms the GR-learning algorithm.

The main contributions of this paper are outlined as follows:

  * •

The average AoI is studied under energy replenishment constraints, i.e.,
energy causality as well as battery capacity constraints, imposed on the
transmitter, which limits the energy consumption in a stochastic manner.

  * •

The optimal policy is shown to be stationary, deterministic, and monotone with
respect to the AoI, while both retransmissions and preemption
size=,color=blue!20!white,size=,color=blue!20!white,todo:
size=,color=blue!20!white,A: This is not defined yet.
size=,color=orange!20!white,size=,color=orange!20!white,todo:
size=,color=orange!20!white,E: I thought preemption is a standard definition,
do we need to define it? Or did I misunderstood the comment? following a
failed transmission are considered.

  * •

Scheduling algorithms are designed using multiple average-cost RL algorithms;
in particular, a value-based RL algorithm, _GR-learning_ [26], a policy-based
RL algorithm, _FDPG_ [27], and a deep RL algorithm, _(DQN)_ , are used to
learn the optimal scheduling decisions when the transmission success
probabilities and energy arrival statistics are unknown.

  * •

Numerical simulations are conducted in order to investigate the effects of the
EH process on the average AoI. In particular, we have found that temporal
correlations in EH increase the average AoI significantly.

  * •

The average AoI with EH is compared with the average AoI under an average
transmission constraint, and it is shown that the average AoI obtained by the
EH transmitter is similar
size=,color=blue!20!white,size=,color=blue!20!white,todo:
size=,color=blue!20!white,A: What does ”approximates” mean? Does it mean they
are similar? In what sense?
size=,color=orange!20!white,size=,color=orange!20!white,todo:
size=,color=orange!20!white,E: modified to the one obtained under an average
transmission constraint for a battery with unlimited capacity and zero
sampling/sensing cost.

The rest of the paper is organized as follows. The system model is presented
in Section II. The problem of minimizing the average AoI with HARQ under
energy replenishment constraints is formulated as a Markov decision process
(MDP) and the structure of the optimal policy is investigated in Section III.
Section IV shows the application of RL algorithms to minimize the AoI in an
unknown environment. Simulation results are presented in Section V, and the
paper is concluded in Section VI.

##  II System Model

Figure 1: An EH status update system over an error-prone link in the presence
of ACK/NACK feedback.

We consider a time-slotted status update-system over an error-prone wireless
communication link (see Figure 1). The transmitter (TX) can sense the
underlying time-varying process and generate a status update in each time slot
at a certain energy cost. Status updates are communicated to the receiver (RX)
over a time-varying wireless channel. Each transmission attempt takes constant
time, which is assumed to be equal to the duration of one time slot.

The AoI measures the timeliness of the status information at the receiver, and
is defined at any time slot $t$ as the number of time slots elapsed since the
generation time $U(t)$ of the most up-to-date packet successfully decoded at
the receiver. Formally, the AoI at the receiver at time $t$ is defined as
$\Delta^{rx}_{t}\triangleq\min(t-U(t),\Delta_{max})$, where a maximum value
$\Delta_{max}$ on the AoI is imposed to limit the impact of the AoI on the
performance after some level of staleness is reached.
size=,color=blue!20!white,size=,color=blue!20!white,todo:
size=,color=blue!20!white,A: Clarify if receiving the update in the same time
slot counts to what age.
size=,color=orange!20!white,size=,color=orange!20!white,todo:
size=,color=orange!20!white,E: Sorry, I couldn’t understand the comment

We assume that the channel changes randomly from one time slot to the next in
an independent and identically distributed (i.i.d.) fashion, and the
instantaneous channel state information is available only at the receiver. We
further assume the availability of an error- and delay-free single-bit
feedback from the receiver to the transmitter for each transmission attempt.
Successful reception of the status update at the end of time slot $t$ is
acknowledged by an ACK signal (denoted by $K_{t}=1$), while a NACK signal is
sent in case of a failure (denoted by $K_{t}=0$).

There are three possible actions the transmitter can take in each time slot
$t$ (the transmitter’s action is denoted by $A_{t}$). It can either sample and
transmit a new status update ($A_{t}=\mathrm{n}$), remain idle
($A_{t}=\mathrm{i}$), or retransmit the last failed status update
($A_{t}=\mathrm{x}$). If an ACK is received at the transmitter, we can
restrict the action space to $\\{\mathrm{i},\mathrm{n}\\}$ as retransmitting
an already decoded status update is strictly suboptimal. Also note that, even
though the transmitter can just sense and generate a new update but not
transmit it, this would be suboptimal, so we do not consider such an action
separately.

We consider the HARQ protocol: that is, the received signals from previous
transmission attempts for the same packet are combined for decoding. The
probability of error using $r$ retransmissions, denoted by $g(r)$, depends on
$r$ and the particular HARQ scheme used for combining multiple transmission
attempts (an empirical method to estimate $g(r)$ is presented in [28]). As in
any reasonable HARQ strategy, we assume that $g(r)$ is non-zero for any $r$
and is non-increasing in the number of retransmissions $r$; that is,
$g(r_{1})\geq g(r_{2})>0$ for all $r_{1}\leq r_{2}$. We also assume that the
transmissions are successful with a positive probability $g(r)<1$ for all $r$.
Standard HARQ methods only combine information from a finite maximum number of
retransmissions [29]. Accordingly, we consider a truncated retransmission
count of a status update, denoted by $R_{t}$ for the status update transmitted
at time $t$, where $R_{t}\in\\{0,\ldots,R_{max}\\}$; that is, the receiver can
combine information from the last $R_{max}$ retransmissions at most. We set
$R_{0}=0$ so that there is no previously transmitted packet at the transmitter
at time $t=0$.

At the end of each time slot $t$, a random amount of energy is harvested and
stored in a rechargeable battery at the transmitter, denoted by
$E_{t}\in\mathcal{E}\triangleq\\{0,1,\ldots,E_{max}\\}$, following a first-
order discrete-time Markov model, characterized by the stationary transition
probabilities $p_{E}(e_{1}|e_{2})$, defined as $p_{E}(e_{1}|e_{2})\triangleq
Pr(E_{t+1}=e_{2}|E_{t}=e_{1})$, $\forall t$ and $\forall
e_{1},e_{2}\in\mathcal{E}$. It is also assumed that $p_{E}(0|e)>0$, $\forall
e\in\mathcal{E}$. Harvested energy is first stored in a rechargeable battery
with a limited capacity of $B_{\mathrm{max}}$ energy units. The energy
consumption for status sensing is denoted by
$E^{\mathrm{s}}\in\mathbb{Z}^{+}$, while the energy consumption for a
transmission attempt is denoted by $E^{\mathrm{tx}}\in\mathbb{Z}^{+}$.

The battery state at the beginning of time slot $t$, denoted by $B_{t}$, can
be written as follows:

$\displaystyle
B_{t+1}=\min(B_{t}+E_{t}-(E^{\mathrm{s}}+E^{\mathrm{tx}})\mathbbm{1}[A_{t}=\mathrm{n}]$
$\displaystyle-E^{\mathrm{tx}}\mathbbm{1}[A_{t}=\mathrm{x}],B_{\mathrm{max}}),$
(1)

and the energy causality constraints are given as:

$(E^{\mathrm{s}}+E^{\mathrm{tx}})\mathbbm{1}[A_{t}=\mathrm{n}]+E^{\mathrm{tx}}\mathbbm{1}[A_{t}=\mathrm{x}]\leq
B_{t},$ (2)

where the indicator function $\mathbbm{1}[C]$ is equal to $1$ if event $C$
holds, and zero otherwise. (II) implies that the battery overflows if energy
is harvested when the battery is full, while (2) imposes that the energy
consumed by sensing or transmission operations at time slot $t$ is limited by
the energy $B_{t}$ available in the battery at the beginning of that time
slot. We set $B_{0}=0$ so that the battery is empty at time $t=0$.

Let $\Delta^{tx}_{t}$ denote the number of time slots elapsed since the
generation of the most recently sensed status update at the transmitter side,
while $\Delta^{rx}_{t}$ denote the AoI of the most recently received status
update at the receiver side. $\Delta^{tx}_{t}$ resets to $1$ if a new status
update is generated at time slot $t-1$, and increases by one (up to
$\Delta_{max}$) otherwise, i.e.,

$\displaystyle\Delta^{tx}_{t+1}=\begin{cases}1&\textrm{ if
}A_{t}=\mathrm{n};\\\ \min(\Delta^{tx}_{t}+1,\Delta_{max})&\textrm{ otherwise.
}\end{cases}$

On the other hand, the AoI at the receiver side evolves as follows:

$\displaystyle\Delta^{rx}_{t+1}\\!=\\!\begin{cases}\min(\\!\Delta^{rx}_{t}\\!+\\!1,\\!\Delta_{max}\\!)&\textrm{if
}A_{t}\\!=\\!\mathrm{i}\textrm{ or }K_{t}\\!=\\!0;\\\ 1&\textrm{if
}A_{t}\\!=\\!\mathrm{n}\textrm{ and }K_{t}\\!=\\!1;\\\
\min(\\!\Delta^{tx}_{t}\\!+\\!1,\\!\Delta_{max}\\!)&\textrm{if
}A_{t}\\!=\\!\mathrm{x}\textrm{ and }K_{t}\\!=\\!1.\end{cases}$

Note that once the AoI at the receiver is at least as large as at the
transmitter, this relationship holds forever; thus it is enough to consider
cases when $\Delta^{rx}_{t}\geq\Delta^{tx}_{t}$.

To determine the success probability of a transmission, we need to keep track
of the number of current retransmissions. The number of retransmissions is
zero for a newly sensed and generated status update and increases up to
$R_{max}$ as we keep retransmitting the same packet. It is easy to see that
retransmitting when $\Delta^{tx}_{t+1}=\Delta_{max}$ is suboptimal, therefore
we explicitly exclude this action by setting the retransmission count to 0 in
this case. Also, it is suboptimal to generate a new update and retransmit the
old one, thus whenever a new status update is generated, the previous update
at the transmitter is dropped and cannot be retransmitted. Thus, the evolution
of the retransmission count is given as follows:

$\displaystyle R_{t+1}\\!=\\!\begin{cases}0&\textrm{ if }K_{t}=1\\\ &\textrm{
or }\Delta^{tx}_{t+1}=\Delta_{max};\\\ 1&\textrm{ if
}A_{t}\\!=\\!\mathrm{n}\textrm{ and }K_{t}\\!=\\!0;\\\ R_{t}&\textrm{ if
}A_{t}\\!=\\!\mathrm{i}\\\ &\textrm{ and
}\Delta^{tx}_{t+1}\neq\Delta_{max};\\\
\min(R_{t}\\!+\\!1\\!,\\!R_{max})&\textrm{ if
}A_{t}\\!=\\!\mathrm{x},K_{t}\\!=\\!0\\\ &\textrm{ and
}\Delta^{tx}_{t+1}\neq\Delta_{max}.\end{cases}$

The state of the system is formed by five components
$S_{t}=(E_{t},B_{t},\Delta^{rx}_{t},\Delta^{tx}_{t},R_{t})$. In each time
slot, the transmitter knows the state, and takes action from the set
$\mathcal{A}=\\{\mathrm{i},\mathrm{n},\mathrm{x}\\}$. The goal is to find a
policy $\pi$ which minimizes the expected average AoI at the receiver over an
infinite time horizon, which is given by:

######  Problem 1.

$\displaystyle
J^{*}\triangleq\min_{\pi}\lim_{T\rightarrow\infty}\frac{1}{T+1}\mathbb{E}\left[\sum_{t=0}^{T}{\Delta^{rx}_{t}}\right]$
(3) $\displaystyle\textrm{subject to }\eqref{eq:causality1}\textrm{ and
}\eqref{eq:causality2}.$

In [22], we have considered status updates with HARQ under an average power
constraint. In that case, it is possible to show that it is suboptimal to
retransmit a failed update after an idle period. Restricting the actions of
the transmitter accordingly, the AoI at the receiver after a successful
transmission event is equal to the number of retransmissions of the
corresponding update. Therefore in addition to the AoI at the receiver, we
only need to track the retransmission count. However, in the current scenario,
retransmissions of a status update can be interrupted due to energy outages,
which means that we also need to keep track of the AoI at the transmitter side
(hence we need to have both $\Delta^{rx}_{t}$ and $\Delta^{tx}_{t}$ in the
state of the system).

##  III MDP Formulation

It is easy to see that Problem 1 can be formulated as an average-cost finite-
state MDP: An MDP is defined by the quadruple
$\big{(}\mathcal{S},\mathcal{A},P,c\big{)}$ [30]: The finite set of states
$\mathcal{S}$ is defined as
$\mathcal{S}=\\{s=(e,b,\delta^{rx},\delta^{tx},r):e\in\mathcal{E},b\in\\{0,\ldots,B_{\mathrm{max}}\\},\delta^{rx},\delta^{tx}\in\\{1,\ldots,\Delta_{max}\\},r\in\\{0,\ldots,R_{max}\\},\Delta^{rx}\geq\Delta^{tx}\\}$,
while the finite set of actions
$\mathcal{A}=\\{\mathrm{i},\mathrm{n},\mathrm{x}\\}$ is already defined. Note
that action $\mathrm{x}$ cannot be taken in states with retransmission count
$r=0$. $P$ refers to the transition probabilities, where
$P(s^{\prime}|s,a)=\Pr(S_{t+1}=s^{\prime}\mid S_{t}=s,A_{t}=a)$ is the
probability that action $a$ in state $s$ at time $t$ will lead to state
$s^{\prime}$ at time $t+1$, which is characterized by the EH statistics and
channel error probabilities. The cost function
$c:\mathcal{S}\times\mathcal{A}\rightarrow\mathbbm{Z}$, is the AoI at the
receiver, and is defined as $c(s,a)=\delta^{rx}$ for any $s\in\mathcal{S}$,
$a\in\mathcal{A}$, independent of the action taken, where $\delta^{rx}$ is the
component of $s$ describing the AoI at the receiver.

To solve Problem 1, we need to find a policy for the transmitter, determining
its actions for every state $s\in\mathcal{S}$, which can minimize the average
AoI at the receiver.

It is easy to see that MDP formulated for Problem 1 is a communicating MDP by
Proposition 8.3.1 of [30]111By Proposition 8.3.1 of [30], MDP is communicating
since there exists a stationary policy which induces a recurrent Markov chain,
e.g., a state $(0,B_{0},\Delta_{max},\Delta_{max},R_{0})$ is reachable from
all other states considering a policy which never transmits and in a scenario
where no energy is harvested., i.e., for every pair of
$(s,s^{\prime})\in\mathcal{S}$, there exists a deterministic policy under
which $s^{\prime}$ is accessible from $s$. By Theorem 8.3.2 of [30], an
optimal stationary policy exists with constant gain. In particular, there
exists a function $h:\mathcal{S}\to\mathbb{R}$, called the differential cost
function for all $s=(e,b,\delta^{rx},\delta^{tx},r)\in\mathcal{S}$, satisfying
the following _Bellman optimality equations_ for the average-cost finite-state
finite-action MDP [30]:

$\displaystyle h(s)+J^{*}$
$\displaystyle=\min_{a\in\\{\mathrm{i},\mathrm{n},\mathrm{x}\\}}\big{(}\delta^{rx}+\mathbb{E}\left[h(s^{\prime})|a\right]\big{)},$
(4)

where
$s^{\prime}\triangleq(e^{\prime},b^{\prime},{\delta^{rx}}^{\prime},{\delta^{tx}}^{\prime},r^{\prime})$
is the next state obtained from $(e,b,\delta^{rx},\delta^{tx},r)$ after taking
action $a$, and $J^{*}$ represents the optimal achievable average AoI under
policy $\pi^{*}$. Note that the function $h$ satisfying (4) is unique up to an
additive factor, and with selecting this additive factor properly, it also
satisfies

$\displaystyle
h(s)=\mathbb{E}\left[\sum_{t=0}^{\infty}(\Delta^{rx}_{t}-J^{*})\big{|}S_{0}=s\right].$

We also introduce the state-action cost function:

$\displaystyle Q((e,b,\delta^{rx},\delta^{tx},r),a)$
$\displaystyle\triangleq\delta^{rx}+\mathbb{E}\left[h(e^{\prime},b^{\prime},{\delta^{rx}}^{\prime},{\delta^{tx}}^{\prime},r^{\prime})|a\right].$
(5)

Then an optimal policy, for any
$(e,b,\delta^{rx},\delta^{tx},r)\in\mathcal{S}$, takes the action achieving
the minimum in (5):

$\displaystyle\pi^{*}(e,b,\delta^{rx},\delta^{tx},r)$
$\displaystyle\in\operatorname*{arg\,min}_{a\in\\{\mathrm{i},\mathrm{n},\mathrm{x}\\}}\big{(}Q((e,b,\delta^{rx}\\!,\\!\delta^{tx}\\!,\\!r),a)\big{)}.$
(6)

An optimal policy solving (4), (5) and (6) defined above can be found by
relative value iteration (RVI) for finite-state finite-action average-cost
MDPs from Sections 8.5.5 and 9.5.3 of [30]: Starting with an arbitrary
initialization of $h_{0}(s)$, $\forall s\in\mathcal{S}$, and setting an
arbitrary but fixed reference state
$s^{ref}\triangleq(e^{ref},b^{ref},{\delta^{rx}}^{ref},{\delta^{tx}}^{ref},r^{ref})$,
a single iteration of the RVI algorithm
$\forall(s,a)\in\mathcal{S}\times\mathcal{A}$ is given as follows:

$\displaystyle Q_{n+1}(s,a)$
$\displaystyle\leftarrow\Delta^{rx}_{n}+\mathbb{E}\left[h_{n}(s^{\prime})\right],$
(7) $\displaystyle V_{n+1}(s)$
$\displaystyle\leftarrow\min_{a}(Q_{n+1}(s,a)),$ (8) $\displaystyle
h_{n+1}(s)$ $\displaystyle\leftarrow{V}_{n+1}(s)-{V}_{n+1}(s^{ref}),$ (9)

where $Q_{n}(s,a)$, $V_{n}(s)$ and $h_{n}(s)$ denote the state-action value
function, value function and differential value function at iteration $n$,
respectively. By Theorem 8.5.7 and Section 8.5.5 of [30], $h_{n}$ converges to
$h$, and $\pi_{n}^{*}(s)\triangleq\operatorname*{arg\,min}_{a}Q_{n}(s,a)$
converges to $\pi^{*}(s)$.

###  III-A Structure of the Optimal Policy

Next, we present the structure of the optimal policy and show that the
solution to the Problem 1 is of threshold-type.

######  Theorem 1.

There exits an optimal stationary policy $\pi^{*}(s)$ that is monotone with
respect to $\Delta_{t}^{rx}$, that is, $\pi^{*}(s)$ is of threshold-type.

###### Proof.

The proof is given in Appendix -A. ∎

Following Theorem 1, we present a threshold-based policy which will be termed
as a double-threshold policy in the rest of this paper.

$\displaystyle A_{t}=\begin{cases}\mathrm{i}&\textrm{ if
}\Delta^{rx}_{t}<\mathcal{T_{\mathrm{n}}}(e,b,\delta^{tx},r),\\\
\mathrm{n}&\textrm{ if
}\mathcal{T_{\mathrm{n}}}(e,b,\delta^{tx},r)\leq\Delta^{rx}_{t}<\mathcal{T_{\mathrm{x}}}(e,b,\delta^{tx},r),\\\
\mathrm{x}&\textrm{ if
}\Delta^{rx}_{t}\geq\mathcal{T_{\mathrm{x}}}(e,b,\delta^{tx},r),\end{cases}$
(10)

for some threshold values denoted by
$\mathcal{T_{\mathrm{n}}}(e,b,\delta^{tx},r)$ and
$\mathcal{T_{\mathrm{x}}}(e,b,\delta^{tx},r)$, where
$\mathcal{T_{\mathrm{n}}}(e,b,\delta^{tx},r)\leq\mathcal{T_{\mathrm{x}}}(e,b,\delta^{tx},r)$.

We can simplify the problem by making an assumption on the policy space in
order to obtain a simpler single-threshold policy, which will result in a more
efficient learning algorithm: We assume that a packet is retransmitted until
it is successfully decoded, provided that there is enough energy in the
battery, that is, the transmitter is not allowed to preempt an undecoded
packet and transmit a new one.

The solution to the simplified problem is also of threshold-type, that is,

$\displaystyle A_{t}=\begin{cases}\mathrm{i}&\textrm{ if
}\Delta^{rx}_{t}<\mathcal{T}(e,b,\delta^{tx},r),\\\ \mathrm{n}&\textrm{ if
}\Delta^{rx}_{t}\geq\mathcal{T}(e,b,\delta^{tx},r),\textrm{ and }r=0\\\
\mathrm{x}&\textrm{ if
}\Delta^{rx}_{t}\geq\mathcal{T}(e,b,\delta^{tx},r)\textrm{ and }r\neq
0,\end{cases}$ (11)

for some $\mathcal{T}(e,b,\delta^{tx},r)$.

In Section IV-B, we present a RL algorithm to find the threshold values
defined in this section.

##  IV RL Approach

In some scenarios, it can be assumed that the channel and energy arrival
statistics remain the same or change very slowly and the same environment is
experienced for a sufficiently long time before the time of deployment.
Accordingly, we can assume that the statistics regarding the error
probabilities and energy arrivals are available before the time of
transmission. In such scenarios, RVI algorithm presented in Section III can be
used. However, in most practical scenarios, channel error probabilities for
retransmissions and the EH characteristics are not known at the time of
deployment, or may change over time. In this section, we assume that the
transmitter does not know the system characteristics a-priori, and has to
learn them. In our previous works [20, 22, 21], we have employed learning
algorithms for constrained problems with countably infinite state spaces such
as average-cost SARSA. While these algorithms can be adopted to the current
framework by considering an average transmission constraint of 1, they do not
have convergence guarantees. However, Problem 1 constitutes an unconstrained
MDP with finite state and action spaces, and there exist RL algorithms for
unconstrained MDPs which enjoy convergence guarantees. Moreover, we have shown
the optimality of a threshold type policy for Problem 1, and RL algorithms
which exploit this structure can be considered. Thus, we employ three
different RL algorithms, and compare their performances in terms of the
average AoI as well as the convergence speed. First, we employ a value-based
RL algorithm, namely GR-learning, which converges to an optimal policy. Next,
we consider a structured policy search algorithm, namely FDPG, which does not
necessarily find the optimal policy but performs very well in practice, as
demonstrated through simulations in Section V. We also note that GR-learning
learns from a single trajectory generated during learning steps while FDPG
uses Monte-Carlo roll-outs for each policy update. Thus, GR-learning is more
amendable for applications in real-time systems. Finally, we employ the DQN
algorithm, which implements a non-linear neural network estimator in order to
learn the optimal status update policy.

###  IV-A GR-Learning with Softmax

The literature for average-cost RL is quite limited compared to discounted
cost problems [31, 32]. For the average AoI minimization problem in (3), we
employ a modified version of the GR-learning algorithm proposed in [26], as
outlined in Algorithm 1, with _Boltzmann_ (_softmax_) exploration. The
resulting algorithm is called _GR-learning with softmax_.

Notice that, by only knowing $Q(s,a)$, one can find the optimal policy
$\pi^{*}$ using (6) without knowing the transition probabilities $P$,
characterized by $g(r)$ and $p_{E}$. Thus, _GR-learning with softmax_ starts
with an initial estimate of $Q_{0}(s,a)$ and finds the optimal policy by
estimating state-action values in a recursive manner. In the $n^{th}$
iteration, after taking action $A_{n}$, the transmitter observes the next
state $S_{n+1}$ and the instantaneous cost value $\Delta^{rx}_{n}$. Based on
these, the estimate of $Q_{n+1}(s,a)$ is updated by a weighted average of the
previous estimate $Q_{n}(s,a)$ and the estimated expected value of the current
policy in the next state $S_{n+1}$. Moreover, we update the gain $J_{n}$ at
every time slot based on the empirical average of AoI.

In each time slot, the learning algorithm

  * •

observes the current state $S_{n}\in\mathcal{S}$,

  * •

selects and performs an action $A_{n}\in\mathcal{A}$,

  * •

observes the next state $S_{n+1}\in\mathcal{S}$ and the instantaneous cost
$\Delta^{rx}_{n}$,

  * •

updates its estimate of $Q(S_{n},A_{n})$ using the current estimate of $J_{n}$
by

$\displaystyle Q_{n+1}(S_{n},A_{n})\leftarrow
Q_{n}(S_{n},A_{n})+\alpha(m(S_{n},A_{n},n))$
$\displaystyle[\Delta^{rx}_{n}-J_{n}+Q_{n}(S_{n+1},A_{n+1})-Q_{n}(S_{n},A_{n})],$
(12)

where $\alpha(m(S_{n},A_{n},n))$ is the update parameter (learning rate) in
the $n^{th}$ iteration, and depends on the function $m(S_{n},A_{n},n)$, which
is the number of times the state–action pair $(S_{n},A_{n})$ has been visited
till the $n^{th}$ iteration.

  * •

updates its estimate of $J_{n}$ based on the empirical average as follows:

$\displaystyle J_{n+1}\leftarrow
J_{n}+\beta(n)\left[\frac{nJ_{n}+\Delta^{rx}_{n}}{n+1}-J_{n}\right]$ (13)

where $\beta(n)$ is the update parameter in the $n^{th}$ iteration.

The transmitter action selection method should balance the exploration of new
actions with the exploitation of actions known to perform well. We use the
Boltzmann (softmax) action selection method, which chooses each action
randomly relative to its expected cost as follows:

$\pi(a|S_{n})=\frac{\displaystyle\exp(-Q(S_{n},a)/\tau_{n})}{\displaystyle\sum_{a^{\prime}\in\mathcal{A}}{\exp(-Q(S_{n},a^{\prime})/\tau_{n})}}.$
(14)

Parameter $\tau_{n}$ in (14) is called the temperature parameter and decays
exponentially with decay parameter $\gamma_{\tau}\leq 1$ at each iteration.
High $\tau_{n}$ corresponds to more uniform action selection (exploration)
whereas low $\tau_{n}$ is biased toward the best action (exploitation).
According to Theorem 2 of [26], if $\alpha$, $\beta$ satisfy
$\sum_{m=1}^{\infty}\alpha(m),\sum_{m=1}^{\infty}\beta(m)\rightarrow\infty$,
$\sum_{m=1}^{\infty}\alpha^{2}(m),\sum_{m=1}^{\infty}\beta^{2}(m)<\infty$,
$\lim_{x\to\infty}\frac{\beta(m)}{\alpha(m)}\rightarrow 0$, GR-Learning
converges to an optimal policy.

Algorithm 1 GR-learning with softmax

1:error probabilities $g(r)$ and harvesting probabilities $p_{E}$ are unknown

2:$\tau_{0}\leftarrow 1$, COMMENT /* temperature parameter */

3:$\gamma\leftarrow 0.95$, COMMENT /* softmax decay coefficient */.

4:$Q_{0}\leftarrow 0$, $\forall_{(s,a)}$ COMMENT /* initialization of $Q$ */

5:$J_{0}\leftarrow 0$, COMMENT /* initialization of the gain */

6:for $n=\\{1,2,\ldots\\}$ do

7: Observe the current state $S_{n}$

8: for $a\in\mathcal{A}$ do
$\pi(a|S_{n})=\frac{\displaystyle\exp(-Q(S_{n},a)/\tau_{n})}{\displaystyle\sum_{a^{\prime}\in\mathcal{A}}{\exp(-Q(S_{n},a^{\prime})/\tau_{n})}}$

9: end for

10: Sample and Perform $A_{n}$ from $\pi(a|S_{n})$

11: observe the next state $S_{n+1}$ and cost $\Delta_{t}$

12: Update the estimates of $Q(S_{n},A_{n})$ and $J_{n}$ by  $\displaystyle
Q(S_{n},A_{n})$ $\displaystyle\leftarrow
Q(S_{n},A_{n})+\alpha(m(S_{n},A_{n},n))[\Delta_{t}-J_{n}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
+\min_{A_{n+1}}{Q(S_{n+1},A_{n+1}})-Q(S_{n},A_{n})]$ $\displaystyle J_{n+1}$
$\displaystyle\leftarrow J_{n}+\beta(n)[\frac{nJ_{n}+\Delta_{t}}{n+1}-J_{n}]$

13: Update step size parameters  $\displaystyle\tau_{n+1}$
$\displaystyle\leftarrow\gamma\tau_{n}$ $\displaystyle\alpha(n)$
$\displaystyle\leftarrow 1/\sqrt{m(S_{n},A_{n},n)}$ $\displaystyle\beta(n)$
$\displaystyle\leftarrow 1/n$ $\displaystyle m(S_{n},A_{n},n+1)$
$\displaystyle\leftarrow m(S_{n},A_{n},n)+1$ $\displaystyle m(s,a,n+1)$
$\displaystyle\leftarrow m(s,a,n),\forall(s,a)\neq(S_{n},A_{n})$

14:end for

###  IV-B Finite-Difference Policy Gradient (FDPG)

GR-learning in Section IV-A is a value-based RL method, which learns the
state-action value function for each state-action pair. In practice,
$\Delta_{max}$ can be large, which might slow down the convergence of GR-
learning due to a prohibitively large state space.

In this section, we are going to propose a learning algorithm which exploits
the structure of the optimal policy exposed in Theorem 1. A monotone policy is
shown to be average optimal in the previous section; however, it is not
possible to compute the threshold values directly for Problem 1.

Note that, $A_{t}=\mathrm{i}$ if $B_{t}<E^{\mathrm{tx}}$
($B_{t}<E^{\mathrm{tx}}+E^{\mathrm{s}}$) for $r\geq 1$ ($r=0$); that is,
$\mathcal{T}(e,b,\delta^{tx},r)=\Delta_{max}+1$ if $b<E^{\mathrm{tx}}$ for
$r\geq 1$ and $b<E^{\mathrm{tx}}+E^{\mathrm{s}}$ for $r=0$. This ensures that
energy causality constraints in (2) hold. Other thresholds will be determined
using policy gradient.

In order to employ the policy gradient method, we approximate the policy by a
parameterized smooth function with parameters $\theta(e,b,\delta^{tx},r)$, and
convert the discrete policy search problem into estimating the optimal values
of these continuous parameters, which can be numerically solved by stochastic
approximation algorithms [33]. Continuous stochastic approximation is much
more efficient than discrete search algorithms in general.

In particular, with a slight abuse of notation, we let
$\pi_{\theta}(e,b,\delta^{rx},\delta^{tx},r)$ denote the probability of taking
action $A_{t}=\mathrm{n}$ ($A_{t}=\mathrm{x}$) if $r=0$ ($r\neq 0$), and
consider the parameterized sigmoid function:

$\displaystyle\pi_{\theta}(e,b,\delta^{rx},\delta^{tx},r)\triangleq\frac{1}{1+e^{-\frac{\delta^{rx}-\theta(e,b,\delta^{tx},r)}{\tau}}}.$
(15)

We note that $\pi_{\theta}(e,b,\delta^{rx},\delta^{tx},r)\rightarrow\\{0,1\\}$
and $\theta(e,b,\delta^{tx},r)\rightarrow\mathcal{T}(e,b,\delta^{tx},r)$ as
$\tau\rightarrow 0$. Therefore, in order to converge to a deterministic policy
$\pi$, $\tau>0$ can be taken as a sufficiently small constant, or can be
decreased gradually to zero. The total number of parameters to be estimated is
$|\mathcal{E}|\times B_{\mathrm{max}}\times\Delta_{max}\times R_{max}+1$ minus
the parameters corresponding to $b<E^{\mathrm{tx}}$
($b<E^{\mathrm{tx}}+E^{\mathrm{s}}$) for $r>0$ ($r=0$) due to energy causality
constraints as stated previously.

With a slight abuse of notation, we map the parameters
$\theta(e,b,\delta^{tx},r)$ to a vector $\overline{\theta}$ of size
$d\triangleq|\mathcal{E}|\times B_{\mathrm{max}}\times\Delta_{max}\times
R_{max}+1$. Starting with some initial estimates of $\overline{\theta}_{0}$,
the parameters can be updated in each iteration $n$ using the gradients as
follows:

$\displaystyle\overline{\theta}_{n+1}=\overline{\theta}_{n}-\gamma(n)\leavevmode\nobreak\
{\partial J}/{\partial\overline{\theta}_{n}},$ (16)

where the step size parameter $\gamma(n)$ is a positive decreasing sequence
and satisfies the first two convergence properties given at the end of Section
IV-A from the theory of stochastic approximation [34].

Computing the gradient of the average AoI directly is not possible; however,
several methods exist in the literature to estimate the gradient [33]. In
particular, we employ the FDPG [27] method. In this method, the gradient is
estimated by estimating $J$ at slightly perturbed parameter values. First, a
random perturbation vector $D_{n}$ of size $d$ is generated according to a
predefined probability distribution, e.g., each component of $D_{n}$ is an
independent Bernoulli random variable with parameter $q\in(0,1)$. The
thresholds are perturbed with a small amount $\sigma>0$ in the directions
defined by $D_{n}$ to obtain
$\overline{\theta}_{n}^{\pm}(e,b,\delta^{tx},r)\triangleq\overline{\theta}_{n}(e,b,\delta^{tx},r)\pm\sigma
D_{n}$. Then, empirical estimates $\hat{J}^{\pm}$ of the average AoI
corresponding to the perturbed parameters $\overline{\theta}_{n}^{\pm}$,
obtained from Monte-Carlo rollouts, are used to estimate the gradient:

$\displaystyle{\partial
J}/{\partial\overline{\theta}_{n}}\approx(D_{n}^{\intercal}D_{n})^{-1}D_{n}^{\intercal}\frac{(\hat{J}^{+}-\hat{J}^{-})}{2\sigma},$
(17)

where $D_{n}^{\intercal}$ denotes the transpose of vector $D_{n}$. The pseudo
code of the finite difference policy gradient algorithm is given in Algorithm
2.

Algorithm 2 FDPG

1:error probabilities $g(r)$ and harvesting probabilities $p_{E}$ are unknown

2:$\tau_{0}\leftarrow 0.3$, COMMENT /* temperature parameter */

3:$\zeta\leftarrow 0.99$, COMMENT /* decaying coefficient for $\tau$ */.

4:$\overline{\theta}_{0}\leftarrow 0$ COMMENT /* initialization of
$\overline{\theta}$ */

5:for $n=\\{1,2,\ldots\\}$ do

6: Generate random perturbation vector $D_{n}=binomial(\\{0,1\\},q=0.5,d)$

7: Perturb parameters $\overline{\theta}_{n}$
$\overline{\theta}_{n}^{+}=\overline{\theta}_{n}+\beta D_{n}$,
$\overline{\theta}_{n}^{-}=\overline{\theta}_{n}-\beta D_{n}$

8: Estimate $\hat{J}_{n}^{\pm}$ from Monte-Carlo rollouts using policies
$\pi_{\theta_{n}^{\pm}}$:

9: for $t\in\\{1,\ldots,T\\}$ do

10: observe current state $S_{t}$ and use policy $\pi_{\theta_{n}^{\pm}}$

11: end for

12: Estimate $\hat{J}_{n}^{\pm}$ from Monte-Carlo rollouts using policy
$\pi_{\theta_{n}^{\pm}}$
$\hat{J}_{n}^{\pm}=\frac{1}{T}\sum_{t=1}^{T}{\Delta^{rx}_{t}}$

13: Compute the estimate of the gradient ${\partial
J}/{\partial\overline{\theta}_{n}}$

14: Update
$\overline{\theta}_{n+1}=\overline{\theta}_{n}-\gamma(n)\leavevmode\nobreak\
{\partial J}/{\partial\overline{\theta}_{n}}$
$\tau_{n+1}\leftarrow\zeta\tau_{n}$ COMMENT /* decrease $\tau$ */

15:end for

Similar steps can be followed to find the thresholds for the double-threshold
policy where $\mathcal{T}(e,b,\delta^{tx},r)$ and $\theta(e,b,\delta^{tx},r)$
are replaced by $\mathcal{T_{\mathrm{n}}}(e,b,\delta^{tx},r)$,
$\mathcal{T_{\mathrm{x}}}(e,b,\delta^{tx},r)$ and
$\theta_{\mathrm{n}}(e,b,\delta^{tx},r)$,
$\theta_{\mathrm{x}}(e,b,\delta^{tx},r)$ respectively.

###  IV-C Deep Q-Network (DQN)

A DQN uses a multi-layered neural network in order to estimate the values
$Q(s,a)$ of the underlying MDP; that is, for a given state $s$, DQN outputs a
vector of state-action values, $Q_{\theta}(s,a)$, where $\theta$ denotes the
parameters of the network. The neural network is a function from $2M$ inputs
to $|\mathcal{A}|$ outputs, which are the estimates of the Q-function
$Q_{\theta}(s,a)$. We apply the DQN algorithm of [35] to learn a scheduling
policy. We create a simple feed-forward neural network of $3$ layers, one of
which is the hidden layer with 24 neurons. We use Huber loss [36] and the Adam
algorithm [37] to conduct stochastic gradient descent to update the weights of
the neural network.

We exploit two important features of DQNs as proposed in [35]: experience
replay and a fixed target network, both of which provide algorithm stability.
For experience replay, instead of training the neural network with a single
observation $<\\!s,a,s^{\prime},c(s,a)\\!>$ at the end of each step, many
experiences (i.e., (state, action, next state, cost) quadruplets) can be
stored in the replay memory for batch training, and a minibatch of
observations randomly sampled at each step can be used. The DQN uses two
neural networks: a target network and an online network. The target network,
with parameters $\theta^{-}$, is the same as the online network except that
its parameters are updated with the parameters $\theta$ of the online network
after every $T$ steps, and $\theta^{-}$ is kept fixed in other time slots. For
a minibatch of observations for training, temporal difference estimation error
$e$ for a single observation can be calculated as

$\displaystyle\varepsilon\\!=\\!Q_{\theta}(s\\!,\\!a)\\!-\\!(\\!-\\!c(s,a)+\gamma
Q_{\theta^{-}}(s^{\prime}\\!,\\!\operatorname*{arg\,max}Q_{\theta}(s^{\prime}\\!,\\!a))).$
(18)

Huber loss is defined by the squared error term for small estimation errors,
and a linear error term for high estimation errors, allowing less dramatic
changes in the value functions, further improving the stability. For a given
estimation error $\varepsilon$ and loss parameter $d$, the Huber loss
function, denoted by $\mathrm{L}^{d}(\varepsilon)$ is defined as:

$\displaystyle\mathrm{L}^{d}(\varepsilon)=\begin{cases}\varepsilon^{2}&\textrm{
if }\varepsilon\leq d\\\ d(|\varepsilon|-\frac{1}{2}d))&\textrm{ if
}\varepsilon>d,\end{cases}$

and loss over minibatch $\mathcal{B}$ is computed as:

$\displaystyle\mathrm{L}_{\mathcal{B}}=\frac{1}{|\mathcal{B}|}\sum_{<s,a,s^{\prime},c(s,a)>\in\mathcal{B}}\mathrm{L}^{d}(\varepsilon).$

We apply the $\epsilon$-greedy policy to balance exploration and exploitation,
i.e., with probability $\epsilon$ the source randomly selects an action, and
with probability $1-\epsilon$ it chooses the action with the minimum Q value.
We let $\epsilon$ decay gradually from $\epsilon_{0}$ to $\epsilon_{min}$; in
other words, the source explores more at the beginning of training and
exploits more at the end. The hyperparameters of the DQN algorithm are tuned
for our problem experimentally, and are presented in Table I.

Table I: Hyperparameters of DQN algorithm used in the paper Parameter | Value | Parameter | Value
---|---|---|---
discount factor $\gamma$ | 0.99 | optimizer | Adam
minibatch size | 32 | loss function | Huber loss
replay memory length | 2000 |  exploration coeff. $\epsilon_{0}$ | 1
learning rate $\alpha$ | $10^{-4}$ |  $\epsilon$ decay rate $\beta$ | 0.9
episode length $T$ | 1000 | $\epsilon_{min}$ | 0.01
activation function | ReLU | hidden size | 24

##  V Simulation Results

In this section, we provide numerical results for all the proposed algorithms,
and compare the achieved average AoI. Motivated by previous research on HARQ
[38], [28], [29], we assume that the decoding error reduces exponentially with
the number of retransmissions, that is, $g(r)\triangleq p_{0}\lambda^{r}$ for
some $\lambda\in(0,1)$, where $p_{0}$ denotes the error probability of the
first transmission and $r$ is the retransmission count (set to $0$ for the
first transmission). The exact value of the rate $\lambda$ depends on the
particular HARQ protocol and the channel model. Following the _IEEE 802.16_
standard[29], the maximum number of retransmissions used for decoding is set
to $R_{max}=3$. In the following experiments, $\lambda$ and $p_{0}$ are set to
$0.5$. $E^{\mathrm{tx}}$ and $E^{s}$ are both assumed to be constant and equal
to 1 unit of energy unless otherwise stated. $\Delta_{max}$ is set to $40$.

We choose the exact step sizes for the learning algorithms by fine-tuning in
order to balance the algorithm stability in the early time steps with
nonnegligible step sizes in the later time steps. In particular, we use step
size parameters of $\alpha(m),\beta(m),\gamma(m)=y/(m+1)^{z}$, where
$0.5<z\leq 1$ and $y>0$ (which satisfy the convergence conditions), and choose
$y$ and $z$ such that the oscillations are low and the convergence rate is
high. We have observed that a particular choice of parameters gives similar
performance results for scenarios addressed in simulations results.

DQN algorithm in this section is configured as in Table I and trained for
$500$ episodes. The average AoI for DQN is obtained after $10^{5}$ time steps
and averaged over $100$ runs.

As a baseline, we have also included the performance of a greedy policy, which
senses and transmits a new status update whenever there is sufficient energy.
It retransmits the last transmitted status update when the energy in the
battery is sufficient only for transmission, and it remains idle otherwise;
that is,

$\displaystyle A^{greedy}_{t}=\begin{cases}\mathrm{i}&\textrm{if
}B_{t}<E^{\mathrm{tx}},\\\ \mathrm{n}&\textrm{if }B_{t}\geq
E^{\mathrm{tx}}+E^{s},\\\ \mathrm{x}&\textrm{if }E^{\mathrm{tx}}\leq
B_{t}<E^{\mathrm{tx}}+E^{s}.\\\ \end{cases}$ (19)

###  V-A Memoryless EH Process

We first investigate the average AoI with HARQ when the EH process,
$E_{t}\in\mathcal{E}=\\{0,1\\}$, is i.i.d. over time with probability
distribution $Pr(E_{t}=1)=p_{e}$, $\forall t$. Figure 2 illustrates the policy
obtained by the RVI algorithm in Section III. The resulting policy is more
likely to transmit if the battery level or the AoI is high as expected.
Moreover, the policy tends to retransmit the previous update rather than
sensing a new update when the battery level is low and the AoI is high. We can
also observe from the figure that the optimal policy exhibits a threshold
structure as shown in Theorem 1.

Figure 2: Optimal policy for memoryless EH when $B_{\mathrm{max}}=5$,
$R_{max}=3$, $p_{e}=0.5$ and $E^{\mathrm{s}}=E^{\mathrm{tx}}=1$. The decoding
error probabilities are given by $g(r)=2^{-(r+1)}$.

The effects of the battery capacity $B_{\mathrm{max}}$, energy consumption of
sensing $E^{\mathrm{s}}$, and the energy harvesting probability $p_{e}$ on the
average AoI are shown in Figure 3. As expected, the average AoI increases with
decreasing $B_{\mathrm{max}}$, decreasing $p_{e}$ and increasing
$E^{\mathrm{s}}$. We note that, when $E^{\mathrm{s}}=0$ and
$B_{\mathrm{max}}=\infty$, the problem defined in (3) corresponds to
minimizing the average AoI under an average transmission rate constraint
$p_{e}$, studied in [20, 22]. The average AoI under average transmission rate
constraint ($B_{\mathrm{max}}=\infty$) is also shown in Figure 3 and we also
observe that its performance can be approximated with a finite battery of size
of $B_{\mathrm{max}}=30$ at low $p_{e}$ values, while a battery size of
$B_{\mathrm{max}}=5$ is sufficient when $p_{e}$ increases.

Figure 3: Average AoI for different $B_{\mathrm{max}}$, $E^{\mathrm{s}}$ and
$p_{e}$ values for memoryless EH and $E^{\mathrm{tx}}=1$.

Figure 4 shows the evolution of the average AoI over time when the average-
cost RL algorithms are employed. It can be observed that the average AoI
achieved by the proposed RL algorithms, converge to values close to the one
obtained from the RVI algorithm, which has _a priori_ knowledge of $g(r)$ and
$p_{e}$, while the AoI of the greedy algorithm is significantly higher.
Although GR-learning enjoys theoretical guaranties to converge to the optimal
policy, the FDPG which benefits from the structural guarantees of a threshold
policy (including a single-threshold policy not allowing preemption of an
undecoded status update), performs better than GR-learning since it tries to
learn significantly smaller number of threshold values (i.e.,
$\Delta_{max}\times B_{\mathrm{max}}\times R_{max}+1$) compared to GR-
learning, which learns one value for each state-action pair (i.e.,
$\Delta_{max}^{2}\times
B_{\mathrm{max}}\times(R_{max}+1)\times|\mathcal{A}|$). We also observe that,
among the FDPG methods, the one with a single threshold converges faster but
the double-threshold policy finally attain on slightly lower AoI. Therefore,
the choice between the two may depend on the stochasticity of the environment.
DQN algorithm performs better than GR-learning but it requires a training time
before running the simulation and does not have convergence guarantees.
Moreover, its final performance is slightly worse than both of the FDPG
algorithms.

Figure 4: Performance of RL algorithms when $B_{\mathrm{max}}=5$,
$E^{\mathrm{s}}=E^{\mathrm{tx}}=1$, and $p_{e}=0.5$. FDPG with and without
preemption represent the double-threshold and the single-threshold policies,
respectively.

###  V-B Temporally Correlated EH

Next, we investigate the performance when the EH process has temporal
correlations. A symmetric two-state Markovian EH process is assumed, such that
$\mathcal{E}=\\{0,1\\}$ and $Pr(E_{t+1}=1|E_{t}=0)=Pr(E_{t+1}=0|E_{t}=1)=0.3$.
That is, if the transmitter is in harvesting state, it is more likely to
continue harvesting energy, and vice versa for the non-harvesting state.

Figure 5 illustrates the policy obtained by RVI. As it can be seen from the
figure, the resulting policy is less likely to transmit if the battery level
or the AoI is low. As shown in Theorem 1, the optimal policy exhibits a
threshold structure on $\Delta^{rx}$. Moreover, the policy tends to retransmit
the previous update rather than sensing a new update when the battery level is
low and the AoI is high. When the system is in the non-harvesting state (i.e.,
$E_{t}=0$), the transmitter is more conservative in transmitting the status
updates compared to the case $E_{t}=1$, e.g., it might not transmit even if
the battery is full depending on the AoI level.

(a) $E_{t}=1$

(a) $E_{t}=0$

Figure 5: Optimal policy for $B_{\mathrm{max}}=5$, $R_{max}=3$, $p_{E}(1,1)$,
$p_{E}(0,0)=0.7$, $E^{\mathrm{s}}=E^{\mathrm{tx}}=1$ and
$\Delta^{tx}_{t}=R_{t}+1$. The decoding error probabilities are given by
$g(r)=2^{-(r+1)}$.

Figure 7 shows the evolution of the average AoI over time when the average-
cost RL algorithms are employed in this scenario. It can be observed again
that the average AoI achieved by the FDPG method in Section IV-B performs very
close to the one obtained by the RVI algorithm, which has _a priori_ knowledge
of $g(r)$ and $p_{e}$. GR-learning, on the other hand, outperforms the greedy
policy but converges to the optimal policy much more slowly, and the gap
between the two RL algorithms is larger compared to the i.i.d. case. Tabular
methods in RL, like GR-learning, need to visit each state-action pair
infinitely often for RL to converge [31]. GR-learning in the case of
temporally correlated EH does not perform as well as in the i.i.d. case since
the state space becomes larger with the addition of the EH state. We also
observe that the gap between the final performances of single- and double-
threshold FDPG solutions is larger compared to the memoryless EH scenario,
while the single threshold solutions till converges faster. DQN algorithm
performs better than GR-learning but it requires a training time before
running the simulation and does not have convergence guarantees. Moreover, it
still falls short of the final performance of double-threshold FDPG.

Figure 6 illustrates the effect of preemption and the performance improvement
of double-threshold FDPG over single-threshold FDPG for a scenario where
preemption is inherently need, e.g., $g(r)$ is same for all retransmissions
$r$ representing a standard ARQ protocol and dropping a failed update improves
the performance. As it can be seen from Figure 6, although single-threshold
FDPG converges very close to the RVI without preemption, the average AoI
obtained by single-threshold FDPG is still considerable higher than that of
double-threshold FDPG for standard ARQ protocol.

Figure 6: The performance of FDPG algorithms when $B_{\mathrm{max}}=5$,
$R_{max}=3$, $p_{E}(1,1)$, $g(r)=0.5$, $\forall r$, $p_{E}(0,0)=0.7$ and
$E^{\mathrm{s}}=E^{\mathrm{tx}}=1$. FDPG with and without preemption represent
the double-threshold and the single-threshold policies, respectively. Figure
7: The performance of RL algorithms when $B_{\mathrm{max}}=5$, $p_{E}(1,1)$,
$p_{E}(0,0)=0.7$ and $E^{\mathrm{s}},E^{\mathrm{tx}}=1$. FDPG with and without
preemption represent the double-threshold and the single-threshold policies,
respectively.

Next, we investigate the impact of the burstiness of the EH process, measured
by the correlation coefficient between $E_{t}$ and $E_{t+1}$. Figure 8
illustrates the performance of the proposed RL algorithms for different
correlation coefficients, which can be computed easily for the 2-state
symmetric Markov chain; that is, $\rho\triangleq(2p_{E}(1,1)-1)$. Note that
$\rho=0$ corresponds to memoryless EH with $p_{e}=1/2$. We note that the
average AoI is minimized by transmitting new packets successfully at regular
intervals, which has been well investigated in previous works [5, 20, 6].
Intuitively, for highly correlated EH, there are either successive
transmissions or successive idle time slots, which increases the average AoI.
Hence, the AoI is higher for higher values of $\rho$. Figure 8 also shows that
both RL algorithms result in much lower average AoI than the greedy policy and
FDPG outperforms GR-learning since it benefits from the structural
characteristics of a threshold policy. We can also conclude that the single
threshold policy can be preferable in practice especially in highly dynamic
environments, as its performance is very close to that of the double threshold
FDPG, but with faster convergence.

Figure 8: The performance of RL algorithms obtained after $2\cdot 10^{4}$ time
steps and averaged over $1000$ runs for different temporal correlation
coefficients.

##  VI Conclusions

We have considered an EH system with a finite size battery and investigated
scheduling policies transmitting time-sensitive data over a noisy channel with
the average AoI as the performance measure. We have assumed the presence of an
Ack/NACK feedback from the receiver, and allowed retransmissions with an HARQ
protocol to increase the probability of correct reception of status updates.
This results in a trade-off between sending new status updates and
retransmitting failed status updates as the former results in a lower AoI at
the receiver while the latter is more likely to succeed. This trade-off is
exacerbated in the model considered in this paper by the introduction of a
sensing cost, which increases the cost of new status updates, and requires
judicious decisions at the transmitter due to limited and stochastic
availability of energy.

In addition to identifying a RVI solution for the optimal policy when the
system characteristics are known, efficient RL algorithms are presented for
practical applications when the system characteristics may not be known in
advance. The effects of the battery size, EH characteristics and the HARQ
structure on the average AoI are investigated through numerical simulations.

We have presented three types of RL algorithms with different levels of
complexity and training requirements and compared their performances for the
current problem under a variety of system setting. We have observed that FDPG
policies that exploit the threshold structure of the optimal policy provide
both better performance and convergence behaviour. Moreover a simplified
single threshold FDPG alternative is shown to further increase the convergence
speed with a negligible increase in the average AoI.

###  -A Proof of Theorem 1:

By (5) and (6), Theorem 1 holds if $Q((e,b,\delta^{rx},\delta^{tx},r),a)$ has
a sub-modular structure in $(\delta^{rx},a)$ [39]: that is, when the
difference between the $Q$ function is monotone with respect to the state-
action pair ($\delta^{rx},a$) for any $E^{h}_{t}=e$, $B_{t}=b$,
$\Delta_{t}^{tx}=\delta^{tx}$, and $R_{t}=r$. We show the submodularity by
verifying the following inequality for 3 action pairs
$(a_{1},a_{2})\in\\{(\mathrm{i},\mathrm{n}),(\mathrm{i},\mathrm{x}),(\mathrm{n},\mathrm{x})\\}$:

$\displaystyle
Q(e,b,\delta^{rx}+1,\delta^{tx},r,a_{2})-Q(e,b,\delta^{rx}+1,\delta^{tx},r,a_{1})$
$\displaystyle\leq
Q(e,b,\delta^{rx},\delta^{tx},r,a_{2})-Q(e,b,\delta^{rx},\delta^{tx},r,a_{1})$
(20)

Inequality (20) can be rewritten for $(a_{1},a_{2})=(\mathrm{i},\mathrm{n})$
using (5),

$\displaystyle
Q(e,b,\delta^{rx},\delta^{tx},r,\mathrm{n})=\delta^{rx}+\sum_{e^{\prime}\in\mathcal{E}}p_{E}(e,e^{\prime})$
$\displaystyle[g(r)h(e^{\prime},b+e-E^{s}-E^{tx},\delta^{rx}+1,1,1)$
$\displaystyle+(1-g(r))h(e^{\prime},b+e-E^{s}-E^{tx},1,1,0)]$ (21)

and

$\displaystyle
Q(e,b,\delta^{rx},\delta^{tx},r,\mathrm{i})=\delta^{rx}+\sum_{e^{\prime}\in\mathcal{E}}p_{E}(e,e^{\prime})$
$\displaystyle h(e^{\prime},b+e,\delta^{rx}+1,\delta^{tx}+1,r)$ (22)

(21) and (22) is inserted into (20) and since the next state
$E^{h}_{t+1}=e^{\prime}$ is independent of action ($A_{t}$) and AoI
($\Delta_{t}$), the following is equivalent to (20):

$\displaystyle g(0)\big{[}h(e^{\prime},b+e-E^{s}-E^{tx},\delta^{rx}+2,1,1)$
$\displaystyle-h(e^{\prime},b+e-E^{s}-E^{tx},\delta^{rx}+1,1,1)\big{]}$
$\displaystyle-\big{[}h(e^{\prime},b+e,\delta^{rx}+2,\delta^{tx}+1,r)$
$\displaystyle-h(e^{\prime},b+e,\delta^{rx}+1,\delta^{tx}+1,r)\big{]}\leq 0.$
(23)

Also we note that $\Delta_{t+1}^{rx}=\delta^{rx}+2$,
$\Delta_{t+1}^{tx}=\delta^{tx}+1$ and $R_{t}=r$ are truncated to
$\Delta_{max}$, $\Delta_{max}$ and $R_{max}$ respectively.

The same steps can be repeated for $(a_{1},a_{2})\in(\mathrm{i},\mathrm{x})$
and $(a_{1},a_{2})\in(\mathrm{n},\mathrm{x})$, and we obtain the following:

$\displaystyle
g(r)\big{[}h(e^{\prime},b+e-E^{tx},\delta^{rx}+2,\delta^{tx}+1,r+1)$
$\displaystyle-h(e^{\prime},b+e-E^{tx},\delta^{rx}+1,\delta^{tx}+1,r+1)\big{]}$
$\displaystyle-\big{[}h(e^{\prime},b+e,\delta^{rx}+2,\delta^{tx}+1,r)$
$\displaystyle-h(e^{\prime},b+e,\delta^{rx}+1,\delta^{tx}+1,r)\big{]}\leq 0$
(24) $\displaystyle
g(r)\big{[}h(e^{\prime},b+e-E^{tx},\delta^{rx}+2,\delta^{tx}+1,r+1)$
$\displaystyle-h(e^{\prime},b+e-E^{tx},\delta^{rx}+1,\delta^{tx}+1,r+1)\big{]}$
$\displaystyle-g(0)\big{[}h(e^{\prime},b+e-E^{s}-E^{tx},\delta^{rx}+2,1,1)$
$\displaystyle-h(e^{\prime},b+e-E^{s}-E^{tx},\delta^{rx}+1,1,1)\big{]}\leq 0$
(25)

Therefore, (23), (24) and (25) are the necessary and sufficient conditions for
submodularity of $Q$ function.

First, we note that Eqns. (23), (24) and (25) hold with equality for
$(\delta^{rx}+1,\delta^{rx})=(M,M-1)$. Then, we show by induction that if
(23), (24) and (25) hold for $(\delta^{rx}+2,\delta^{rx}+1)$ then they hold
for $(\delta^{rx}+1,\delta^{rx})$.

First, we check for $(a_{1},a_{2})=(\mathrm{i},\mathrm{x})$, and assume that
$h$ satisfies (23), (24) and (25). We define the related $Q$ functions with
optimal actions denoted by $a^{*}_{1}$, $a^{*}_{2}$, $a^{*}_{3}$ and
$a^{*}_{4}$ such that:

$\displaystyle Q(e,b\\!-\\!E^{tx},\delta^{rx}+1,\delta^{tx}+1,r+1,a^{*}_{1})$
(26) $\displaystyle\triangleq
h(e,b\\!-\\!E^{tx},\delta^{rx}\\!+\\!1,\delta^{tx}\\!+\\!1,r+1,)\\!+\\!J^{*}$
$\displaystyle Q(e,b-E^{tx},\delta^{rx},\delta^{tx}+1,r+1,a^{*}_{2})$ (27)
$\displaystyle\triangleq h(e,b-E^{tx},\delta^{rx},\delta^{tx}+1,r+1)+J^{*}$
$\displaystyle Q(e,b,\delta^{rx}+1,\delta^{tx}+1,r,a^{*}_{3})$ (28)
$\displaystyle\triangleq h(e,b,\delta^{rx}+1,\delta^{tx}+1,r)+J^{*}$
$\displaystyle Q(e,b,\delta^{rx},\delta^{tx},r,a^{*}_{4})\triangleq
h(e,b,\delta^{rx},\delta^{tx},r)+J^{*}$ . (29)

We need to show that (24) holds for $(\delta^{rx}+1,\delta^{rx})$, which can
be rewritten using (26), (27), (28) and (29):

$\displaystyle
g(r)\big{[}Q(e,b-E^{tx},\delta^{rx}+1,\delta^{tx}+1,r+1,a^{*}_{1})$
$\displaystyle-Q(e,b-E^{tx},\delta^{rx},\delta^{tx}+1,r+1,a^{*}_{2})\big{]}$
$\displaystyle-\big{[}Q(e,b,\delta^{rx}+1,\delta^{tx}+1,r,a^{*}_{3})$
$\displaystyle-Q(e,b,\delta^{rx},\delta^{tx},r,a^{*}_{4})\big{]}\leq 0$ (30)

We add terms
$g(r)[-Q(e,b-E^{tx},\delta^{rx}+1,\delta^{tx}+1,r+1,a^{*}_{2})+Q(e,b-E^{tx},\delta^{rx}+1,\delta^{tx}+1,r+1,a^{*}_{2})]$
and
$[Q(e,b,\delta^{rx},\delta^{tx},r,a^{*}_{3})-Q(e,b,\delta^{rx},\delta^{tx},r,a^{*}_{3})]$
to the LHS of (30) and obtain:

$\displaystyle
g(r)\big{[}Q(e,b-E^{tx},\delta^{rx}+1,\delta^{tx}+1,r+1,a^{*}_{1})$
$\displaystyle-Q(e,b-E^{tx},\delta^{rx}+1,\delta^{tx}+1,r+1,a^{*}_{2})$
$\displaystyle+Q(e,b-E^{tx},\delta^{rx}+1,\delta^{tx}+1,r+1,a^{*}_{2})$
$\displaystyle-Q(e,b-E^{tx},\delta^{rx},\delta^{tx}+1,r+1,a^{*}_{2})\big{]}$
$\displaystyle-\big{[}Q(e\\!,b\\!,\delta^{rx}\\!+\\!1,\delta^{tx}\\!+\\!1\\!,r\\!,a^{*}_{3})\\!-\\!Q(e,b,\delta^{rx}\\!,\delta^{tx}\\!,r,a^{*}_{3})$
$\displaystyle+Q(e\\!,b\\!,\delta^{rx},\delta^{tx},r,a^{*}_{3})-Q(e\\!,b\\!,\delta^{rx},\delta^{tx},r,a^{*}_{4})\big{]}\leq
0$ (31)

$Q(e,b_{1},\delta+1,r+1,a^{*}_{1})-Q(e,b_{1},\delta+1,r+1,a^{*}_{2})$ is
smaller than $0$ from the optimality of $a^{*}_{1}$. Similarly,
$Q(e,b,\delta^{rx},\delta^{tx},r,a^{*}_{4})-Q(e,b,\delta^{rx},\delta^{tx},r,a^{*}_{3})$
is smaller than $0$ from the optimality of $a^{*}_{4}$. Then, we only need to
show:

$\displaystyle g(r)[Q(e,b-E^{tx},\delta^{rx}+1,\delta^{tx}+1,r+1,a_{2}^{*})$
$\displaystyle-Q(e,b-E^{tx},\delta^{rx},\delta^{tx}+1,r+1,a_{2}^{*})]$
$\displaystyle-Q(e,b,\delta^{rx}+1,\delta^{tx}+1,r,a_{3}^{*})$
$\displaystyle+Q(e,b,\delta^{rx},\delta^{tx},r,a_{3}^{*})\leq 0.$ (32)

The condition in (32) can be checked for all possible values of
$(a_{2}^{*},a_{3}^{*})$ pair: First we investigate for the pair
$(a^{*}_{2},a^{*}_{3})=(\mathrm{i},\mathrm{i})$; that is,

$\displaystyle g(r)\big{[}$ $\displaystyle
1+h(e^{\prime},b-E^{tx}+e,\delta^{rx}+2,\delta^{tx}+1,r+1)$
$\displaystyle-h(e^{\prime},b-E^{tx}+e,\delta^{rx}+1,\delta^{tx}+1,r+1)\big{]}$
$\displaystyle-1+h(e^{\prime},b+e,\delta^{rx}+1,\delta^{tx}+1,r)$
$\displaystyle-h(e^{\prime},b+e,\delta^{rx}+2,\delta^{tx}+1,r)\leq 0.$ (33)

LHS of (33) is equivalent to LHS of (24) plus the term $g(r)-1$, which is
smaller than and equal to $0$ since (24) holds and $g(r)\leq 1$. For pair
$(a^{*}_{2},a^{*}_{3})=(\mathrm{x},\mathrm{x})$; that is,

$\displaystyle g(r)\big{[}1+g(r+1)h(e^{\prime},b-2E^{tx}+e,\delta+2,r+2)$
$\displaystyle-g(r\\!+\\!1)h(e^{\prime},b\\!-\\!2E^{tx}\\!+\\!e,\delta^{rx}\\!+\\!1,\delta^{tx}\\!+\\!1,r\\!+\\!1)\big{]}$
$\displaystyle-1-g(r)h(e^{\prime},b\\!-\\!E^{tx}\\!+\\!e,\delta^{rx}+2,\delta^{tx}+1,r+1)$
$\displaystyle+g(r)h(e^{\prime},b-E^{tx}+e,\delta^{rx}\\!+\\!1,\delta^{tx}\\!+\\!1,r\\!+\\!1)\leq
0$ (34)

Similarly, $g(r)-1$ is less than 0 and (34) holds.

For pair $(a^{*}_{2},a^{*}_{3})=(\mathrm{i},\mathrm{x})$:

$\displaystyle
g(r)\big{[}1+h(e^{\prime},b-E^{tx}+e,\delta^{rx}+2,\delta^{tx}+1,r+1)$
$\displaystyle-h(e^{\prime},b-E^{tx}+e,\delta^{rx}+1,\delta^{tx}+1,r+1)\big{]}$
$\displaystyle-\\!1\\!-\\!g(r)h(e,e^{\prime},b\\!-\\!E^{tx}\\!+\\!e,\delta^{rx}\\!+\\!2,\delta^{tx}\\!+\\!1,r\\!+1\\!)$
$\displaystyle+g(r)h(e^{\prime},b\\!-\\!E^{tx}\\!+\\!e,\delta^{rx}\\!+\\!1,\delta^{tx}\\!+\\!1,r+1)\leq
0,$ (35)

which is equal to:

$\displaystyle g(r)-1\leq 0.$ (36)

For pair $(a^{*}_{2},a^{*}_{3})=(\mathrm{x},\mathrm{i})$:

$\displaystyle g(r)\big{[}1+g(r+1)h(e^{\prime},b-2E^{tx}+e,\delta+2,r+2)$
$\displaystyle-g(r\\!+\\!1)h(e^{\prime},b\\!-\\!2E^{tx}\\!+\\!e,\delta^{rx}\\!+\\!1,\delta^{tx}\\!+\\!1,r\\!+\\!1)\big{]}$
$\displaystyle-1+h(e^{\prime},b+e,\delta^{rx}+1,\delta^{tx}+1,r)$
$\displaystyle-h(e^{\prime},b+e,\delta^{rx}+2,\delta^{tx}+1,r)\leq 0.$ (37)

which is equal to:

$\displaystyle g(r)g(r+1)\big{[}h(e^{\prime},b-2E^{tx},\delta+2,r+2)$
$\displaystyle-h(e^{\prime},b-2E^{tx}+e,\delta^{rx}+1,\delta^{tx}+1,r+1)\big{]}$
$\displaystyle-h(e^{\prime},b+e,\delta^{rx}+2,\delta^{tx}+1,r)$
$\displaystyle+h(e^{\prime},b+e,\delta^{rx}+1,\delta^{tx}+1,r)$
$\displaystyle+g(r)-1+\leq 0.$ (38)

From (24),
$-h(e^{\prime},b+e,\delta^{rx}+2,\delta^{tx}+1,r)+h(e^{\prime},b+e,\delta^{rx}+1,\delta^{tx}+1,r)\leq
g(r)(-h(e^{\prime},b+e-E^{tx},\delta^{rx}+2,\delta^{tx}+1,r+1)+h(e^{\prime},b+e-E^{tx},\delta+1,r+1))$,
and $1-g(r)\leq 0$; thus (38) is smaller than

$\displaystyle
g(r)\bigg{\\{}g(r+1)\big{[}h(e^{\prime},b-2E^{tx},\delta+2,r+2)$
$\displaystyle-h(e^{\prime},b-2E^{tx}+e,\delta^{rx}+1,\delta^{tx}+1,r+1)\big{]}$
$\displaystyle+(-h(e^{\prime},b+e-E^{tx},\delta^{rx}+2,\delta^{tx}+1,r+1)$
$\displaystyle+h(e^{\prime},b+e-E^{tx},\delta+1,r+1))\bigg{\\}},$ (39)

which is smaller than 0, since the expression inside the braces is equivalent
to (24) with $r\to r+1$ and $g(r)\geq 0$.

The same holds for $(a^{*}_{2},a^{*}_{3})=(\mathrm{x},\mathrm{n})$ and
$(a^{*}_{2},a^{*}_{3})=(\mathrm{n},\mathrm{x})$. Similar steps could be
followed for other $(a_{1},a_{2})=(\mathrm{i},\mathrm{n})$ and
$(a_{1},a_{2})=(\mathrm{n},\mathrm{x})\\}$ pairs and are not included in this
paper due to space limitations.

Thus, the condition is satisfied, i.e., $Q$ function is submodular in
$(\delta^{rx},a)$. From [39], it can be concluded that the status update
policy is of threshold-type.

## References

  * [1] E. T. Ceran, D. Gündüz, and A. György, “Reinforcement learning to minimize age of information with an energy harvesting sensor with harq and sensing cost,” in _IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , April 2019.
  * [2] C. Alippi and C. Galperti, “An adaptive system for optimal solar energy harvesting in wireless sensor network nodes,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 55, no. 6, pp. 1742–1750, July 2008\.
  * [3] M. A. Weimer, T. S. Paing, and R. A. Zane, “Remote area wind energy harvesting for low-power autonomous sensors,” in _IEEE Power Electronics Specialists Conference_ , June 2006, pp. 1–5.
  * [4] A. Nechibvute, A. Chawanda, and P. Luhanga, “Piezoelectric energy harvesting devices: An alternative energy source for wireless sensors,” _Smart Materials Research_ , p. 13, 2012.
  * [5] B. T. Bacinoglu, E. T. Ceran, and E. Uysal-Biyikoglu, “Age of information under energy replenishment constraints,” in _2015 Information Theory and Applications Workshop (ITA)_ , Feb 2015, pp. 25–31.
  * [6] R. D. Yates, “Lazy is timely: Status updates by an energy harvesting source,” in _IEEE International Symposium on Information Theory (ISIT)_ , June 2015, pp. 3008–3012.
  * [7] B. T. Bacinoglu and E. Uysal-Biyikoglu, “Scheduling status updates to minimize age of information with an energy harvesting sensor,” _CoRR_ , vol. abs/1701.08354, 2017. [Online]. Available: http://arxiv.org/abs/1701.08354
  * [8] A. Arafa and S. Ulukus, “Age minimization in energy harvesting communications: Energy-controlled delays,” _CoRR_ , vol. abs/1712.03945, 2017.
  * [9] X. Wu, J. Yang, and J. Wu, “Optimal status update for age of information minimization with an energy harvesting source,” _IEEE Transactions on Green Communications and Networking_ , vol. 2, no. 1, pp. 193–204, March 2018\.
  * [10] B. T. Bacinoglu, Y. Sun, E. Uysal-Biyikoglu, and V. Mutlu, “Achieving the age-energy tradeoff with a finite-battery energy harvesting source,” _CoRR_ , vol. abs/1802.04724, 2018.
  * [11] S. Feng and J. Yang, “Age of information minimization for an energy harvesting source with updating erasures: With and without feedback,” _CoRR_ , 2018\.
  * [12] A. Arafa, J. Yang, S. Ulukus, and H. V. Poor, “Age-minimal online policies for energy harvesting sensors with incremental battery recharges,” _Information Theory and Applications Workshop (ITA)_ , Feb 2018.
  * [13] M. A. Abd-Elmagid, H. S. Dhillon, and N. Pappas, “Online age-minimal sampling policy for rf-powered iot networks,” in _2019 IEEE Global Communications Conference (GLOBECOM)_ , 2019, pp. 1–6.
  * [14] M. Hatami, M. Jahandideh, M. Leinonen, and M. Codreanu, “Age-aware status update control for energy harvesting iot sensors via reinforcement learning,” 2020.
  * [15] E. Gindullina, L. Badia, and D. Gündüz, “Age-of-information with information source diversity in an energy harvesting system,” 2020.
  * [16] N. Pappas, Z. Chen, and M. Hatami, “Average aoi of cached status updates for a process monitored by an energy harvesting sensor,” in _2020 54th Annual Conference on Information Sciences and Systems (CISS)_ , 2020, pp. 1–5.
  * [17] J. Brusey, J. Kemp, E. Gaura, R. Wilkins, and M. Allen, “Energy profiling in practical sensor networks: Identifying hidden consumers,” _IEEE Sensors Journal_ , vol. 16, no. 15, pp. 6072–6080, Aug 2016.
  * [18] J. Gong, X. Chen, and X. Ma, “Energy-age tradeoff in status update communication systems with retransmission,” _ArXiv e-prints_ , Aug. 2018\.
  * [19] B. Zhou and W. Saad, “Joint status sampling and updating for minimizing age of information in the internet of things,” _CoRR_ , vol. abs/1807.04356, 2018\.
  * [20] E. T. Ceran, D. Gündüz, and A. György, “Average age of information with hybrid ARQ under a resource constraint,” in _IEEE Wireless Communications and Networking Conference (WCNC)_ , 2018.
  * [21] ——, “Reinforcement learning approach to age of information in multi-user networks,” in _IEEE International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC)_ , 2018.
  * [22] E. T. Ceran, D. Gündüz, and A. György, “Average age of information with hybrid arq under a resource constraint,” _IEEE Transactions on Wireless Communications_ , vol. 18, pp. 1900–1913, March 2019.
  * [23] D. Gunduz, K. Stamatiou, N. Michelusi, and M. Zorzi, “Designing intelligent energy harvesting communication systems,” _IEEE Communications Magazine_ , vol. 52, pp. 210–216, 2014.
  * [24] P. Blasco, D. Gunduz, and M. Dohler, “A learning theoretic approach to energy harvesting communication system optimization,” _IEEE Transactions on Wireless Communications_ , vol. 12, no. 4, pp. 1872–1882, April 2013.
  * [25] A. Ortiz, H. Al-Shatri, X. Li, T. Weber, and A. Klein, “Reinforcement learning for energy harvesting point-to-point communications,” in _2016 IEEE International Conference on Communications (ICC)_ , May 2016, pp. 1–6.
  * [26] A. Gosavi, “Reinforcement learning for long-run average cost,” _European Journal of Operational Research_ , vol. 155, pp. 654 – 674, 2004.
  * [27] J. Peters and S. Schaal, “Policy gradient methods for robotics,” in _2006 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , Oct 2006, pp. 2219–2225.
  * [28] V. Tripathi, E. Visotsky, R. Peterson, and M. Honig, “Reliability-based type ii hybrid ARQ schemes,” in _IEEE International Conference on Communications,_ , vol. 4, May 2003, pp. 2899–2903 vol.4.
  * [29] “IEEE standard for local and metropolitan area networks part 16: Air interface for fixed and mobile broadband wireless access systems amendment 2: Physical and medium access control layers for combined fixed and mobile operation in licensed bands and corrigendum 1 (incorporated into IEEE standard 802.16e-2005 and IEEE std 802.16-2004/cor1-2005),” _IEEE Std P802.16/Cor1/D5_ , 2006.
  * [30] M. L. Puterman, _Markov Decision Processes: Discrete Stochastic Dynamic Programming_. New York, NY, USA: John Wiley & Sons, 1994.
  * [31] R. S. Sutton and A. G. Barto, _Introduction to Reinforcement Learning_ , 1st ed. Cambridge, MA, USA: MIT Press, 1998\.
  * [32] S. Mahadevan, “Average reward reinforcement learning: Foundations, algorithms, and empirical results,” _Machine Learning_ , vol. 22, no. 1, pp. 159–195, 1996.
  * [33] J. C. Spall, _Introduction to Stochastic Search and Optimization_. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2003\.
  * [34] H. J. Kushner and G. G. Yin, _Stochastic Approximation Algorithms and Applications_. Orlando, FL, USA: New York: Springer-Verlag, 1997.
  * [35] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, “Human-level control through deep reinforcement learning,” _Nature_ , vol. 518, no. 7540, pp. 529–533, Feb. 2015.
  * [36] P. J. Huber, “Robust estimation of a location parameter,” _The Annals of Mathematical Statistics_ , vol. 35, no. 1, pp. 73–101, 03 1964. [Online]. Available: https://doi.org/10.1214/aoms/1177703732
  * [37] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _CoRR_ , vol. abs/1412.6980, 2014.
  * [38] P. Frenger, S. Parkvall, and E. Dahlman, “Performance comparison of HARQ with chase combining and incremental redundancy for HSDPA,” in _Proc. IEEE Vehicular Technology Conference_ , vol. 3, 2001, pp. 1829–1833.
  * [39] D. M. Topkis, “Minimizing a submodular function on a lattice,” _Operational Research_ , vol. 26, no. 2, pp. 305–321, Apr. 1978.