Average Age of Information with Hybrid ARQ
under a Resource Constraint
Elif Tuğçe Ceran, Deniz Gündüz, and András György

arXiv:1710.04971v1 [cs.IT] 1 Oct 2017

Department of Electrical and Electronic Engineering
Imperial College London
Email: {e.ceran14, d.gunduz, a.gyorgy}@imperial.ac.uk
Abstract—Scheduling of the transmission of status updates
over an error-prone communication channel is studied in order
to minimize the long-term average age of information (AoI) at
the destination, under an average resource constraint at the
source node, which limits the average number of transmissions.
After each transmission, the source receives an instantaneous
ACK/NACK feedback, and decides on the next update, without a
priori knowledge on the success of the future transmissions. The
optimal scheduling policy is studied under different feedback
mechanisms; in particular, standard automatic repeat request
(ARQ) and hybrid ARQ (HARQ) protocols are considered.
Average-cost reinforcement learning algorithms are proposed
when the error probabilities for the HARQ system are unknown.

I. I NTRODUCTION
We consider a source node which continually communicates the most up-to-date status packets to the destination. In
particular, we are interested in the age of information (AoI)
[1], [2] at the destination, for a system in which the source
node samples an underlying time-varying process and sends
the sample values over an imperfect link which introduces
delays. Our goal is to minimize the average AoI taking into
account packet retransmissions. Most of the prior work on AoI
either do not consider retransmissions, or consider a standard
automatic repeat request (ARQ) protocol, where, if a packet
cannot be decoded, it is retransmitted until correct decoding,
up to a maximum number of retransmissions (e.g., [3], [4]).
Here, we analyze the AoI for both the standard ARQ and
hybrid ARQ (HARQ) protocols. In the latter, the receiver
combines information from all previous transmission attempts
of a packet in order to increase the success probability of
decoding after each retransmission [5].
To address the trade-off between the success probability and
the freshness of the status update to be transmitted, we develop
scheduling policies to minimize the expected average AoI under an average transmission-rate constraint. This constraint is
motivated by the fact that sensors sending status updates have
usually limited energy supplies (e.g., are powered via energy
harvesting); hence, they cannot afford to send an unlimited
number of updates, or increase the signal-to-noise-ratio in the
transmission. First, we assume that the success probability
before each transmission attempt is known (which depends on
the number of previous unsuccessful transmissions); hence, the
source can judiciously decide when to retransmit, and when to
discard failed information and send a fresh update. Then, we
consider transmitting status updates over an unknown channel,

Process H(t)

ACK/ NACK feedback
Sample of the process
Source

Error-prone
channel

Destination

Figure 1. System model of a status update system over an error-prone pointto-point link in the presence of ACK/NACK feedback from the destination.

in which the success probabilities of transmission attempts are
not known a priori, and must be learned in an online fashion.
The main contributions of this paper are outlined as follows:
• An long-term average resource constraint is imposed
on the transmitter, which limits the average number of
transmissions.
• Both retransmissions and pre-emption following a failed
transmission are considered, corresponding, respectively,
to the HARQ and ARQ protocols.
• The optimal preemptive transmission policy for the standard ARQ protocol is shown to be threshold-type, and
the optimal threshold value is derived in closed-form.
• An average-cost reinforcement learning (RL) algorithm is
proposed to learn the optimal scheduling decisions when
the transmission success probabilities are unknown.
• Extensive simulations are conducted in order to show the
effect of feedback, resource constraint and ARQ/ HARQ
error correction algorithms on the data freshness.
A. Related Work
Earlier work on AoI considered queue-based models, in
which the status updates arrive at the source node randomly
as a memoryless Poisson process, and are stored in a buffer
before being transmitted to the destination [1], [2], [6]. Instead,
in this paper, we follow the so-called generate-at-will model
that has been recently considered in [4] and [7], in which the
status updates of the underlying process of interest can be
sampled and generated at any time by the source.
A constant packet failure probability for status update
systems is investigated for the first time in [3], but this work
focuses on an M/M/1 queuing model, and no feedback is
considered for retransmissions. The paper [4] considers broadcasting of status updates to multiple clients over an unreliable

broadcast channel. However, this paper only considers index
policies, which update the information at every time slot, since
no constraint is imposed on the number of updates.
Optimizing the scheduling decisions in an AoI system is
also investigated in [7], focusing on multiple receivers, which
leads to a different set of constraints than ours, as we limit the
average number of transmissions to a single receiver. The AoI
in the presence of HARQ is modeled through an M/G/1 queue
in [8]; however, no resource constraint is taken into account,
and the status update arrivals are assumed to be memoryless
and random, in contrast to our work, which considers general
and controlled status update generation.
The rest of the paper is organized as follows. In Section II,
the system model is presented, and the problem of minimizing
the average AoI with HARQ under a resource constraint is
formulated as a constrained Markov decision process (CMDP).
In Section III, a primal-dual algorithm is proposed to solve this
CMDP. Then, minimizing the AoI under the standard ARQ
protocol is investigated in Section IV, and a computationally
efficient solution is proposed. Section V introduces a reinforcement learning algorithm to minimize AoI in an unknown
environment. Simulation results are presented in Section VI,
and the paper is concluded in Section VII.
II. S YSTEM M ODEL AND P ROBLEM F ORMULATION
We consider a slotted status update system over an errorprone wireless link. The source monitors an underlying timevarying process, for which it is able to generate a status
update at the beginning of each time slot; this is known as the
generate-at-will model [4]. A transmission attempt of a status
update takes constant time, which is assumed to be equal to
the duration of one time slot.
We assume that the channel state changes randomly from
one time slot to the next in an independent and identically
distributed fashion. We further assume the availability of errorand delay-free single-bit feedback from the destination to
the source node. Successful reception of a status update is
acknowledged by an ACK signal, while a NACK signal is
sent in case of a failure. In the classical ARQ protocol, a
packet is retransmitted after each NACK feedback, until it
is successfully decoded, and the received signal is discarded
after each failed transmission attempt. However, in the AoI
framework there is no point in retransmitting a failed out-ofdate status packet if it has the same error probability with
a fresh status update. Hence, the source always removes a
failed status signal, and transmits a fresh status update (preemption). On the other hand, in the HARQ protocol, signals
from all previous transmission attempts are combined for
decoding; and therefore, the probability of error decreases with
every retransmission. In general, the error probability of each
retransmission attempt depends on the particular combining
technique used, as well as the channel conditions [5].
The AoI is defined as the time elapsed since the most upto-date packet at the destination is generated. Assume that the
most up-to-date packet at the destination at time t has a time
stamp of generation U (t), then the AoI at time t, denoted by

aging due to erronous transmission
aging due to resource constraint

minimum AoI level

t
at

i

i

n

x

x

n

x

i

n

i

i

i

n

δt
rt

1

2

3

4

5

3

4

2

3

1

1

2

3

0

0

0

1

2

0

1

0

0

0

0

0

0

Feedback

NACK NACK ACK NACK ACK

ACK

Figure 2. Illustration of the AoI in a slotted status update system with HARQ.

δt , is defined as: δt , t−U (t). Therefore, the AoI increases by
one when a transmission fails, while it decreases to one (or, to
the number of retransmissions in the case of HARQ) when a
status update is successfully decoded. The system model and
the evolution of AoI for a slotted status update system are
illustrated in Figures 1 and 2, respectively.
The probability of error after r retransmissions, denoted by
g(r), depends only on r, and the particular HARQ scheme
used for combining multiple transmission attempts. An empirical method to estimate g(r) is presented in [9]. As in
any reasonable HARQ strategy, g(r) is non increasing in
the number of retransmissions r, i.e., g(r1 ) ≥ g(r2 ) for all
r1 ≤ r2 . To simplify the analysis, we assume that there is a
maximum number of retransmissions rmax , and a packet is
assumed to be successfully decoded after rmax transmissions,
i.e., g(r) = 0, for all r ≥ rmax .
Let δt ∈ Z+ denote the AoI at time slot t, and rt ∈
{0, . . . , rmax } denote the transmission attempt number. We
define the state vector at time slot the t as st , (δt , rt ). At
each time slot, the source node takes one of the three possible
actions, denoted by a ∈ A, where A = {i, n, x}. It can i)
remain idle (a = i); ii) generate and transmit a new status
update packet (a = n); or, iii) retransmit the previously failed
packet (a = x).
The state transitions can be summarized as follows: The
next state (δt+1 , rt+1 ) is determined stochastically depending
on action at and the current state (δt , rt ):
Pr(δt+1 = δt + 1, rt+1 = rt |at = i, δt , rt ) = 1 (1a)
Pr(δt+1 = δt + 1, rt+1 = 1|at = n, δt , rt ) = g(0)
(1b)
Pr(δt+1 = 1, rt+1 = 0|at = n, δt , rt ) = 1−g(0) (1c)
Pr(δt+1 = δt + 1, rt+1 = rt + 1|at = x, δt , rt ) = g(rt )
(1d)
Pr(δt+1 = rt + 1, rt+1 = 0|at = x, δt , rt ) = 1−g(rt ) (1e)
and P r(δt+1 , rt+1 |at , δt , rt ) is zero elsewhere.
Note that if there is no resource constraint, remaining idle
for a time slot is not a favorable action since it increases the
AoI by 1. However, continuous transmission is typically not
possible in practice due to energy or interference constraints.

Thus, we impose a constraint on the average number of
transmissions denoted by Cmax .
This leads to the CMDP formulation, defined by the 5tuple {S, A, P, c, d} [10]. A countable set of states (δ, r) ∈ S
and a finite set of actions A = {i, n, x} are already defined.
P contains the transition probabilities outlined in (1). The
instantaneous cost ct at time slot t is equal to age δt , and
we use dt as the transmission count, that is, dt = 0 if at = i,
or dt = 1 otherwise.
Policies are represented by π : S × A → [0, 1], π ∈ Π,
where at maps states st ∈ S into actions at ∈ A with some
probability π(at |st ). We will use sπt = (δtπ , rtπ ) and aπt to
denote the states and actions, respectively, induced by policy
π. Let J π (s0 ) denote the infinite horizon average age, and
C π (s0 ) denote the expected average number of transmissions
when policy π is employed with initial state s0 . We restrict our
attention to stationary policies, and denote the set of feasible
policies by ΠF , such that C π ≤ Cmax , ∀π ∈ ΠF .
We can state the CMDP optimization problem as follows,
where Eπ [·] represents the expectation with respect to policy
π and error probabilities g(r):
Problem 1.

" T
#
1 π X π
(2)
δt s0 ,
Minimize J (s0 ) , lim sup E
T →∞ T
t=1
#
" T
1 π X
π
π
s.t. C (s0 ) = lim sup E
1[at 6= i] s0 ≤ Cmax .
T →∞ T
t=1
π

∗

We define a policy π ∗ to be optimal in ΠF if J ∗ , J π ≤
π
J for all π ∈ ΠF . A policy is said to be deterministic if it
chooses an action with certainty at each decision epoch, and
for convenience we denote a deterministic policy simply by π
[10]. Also, without loss of generalization, problem horizon is
assumed to begin when the information at the destination is
up-to-date, i.e. s0 = (1, 0); and s0 will be removed from the
notation for simplicity. We assume throughout this paper that
the MDP is unichain [10], [11], which is intuitive since any
reasonable policy for Problem 1 results in an ergodic Markov
chain.
A. Structure of the Optimal Policy
Note that a deterministic stationary policy which is optimal
for countable-state average-cost MDPs exist and can be found
under certain conditions defined in [11], [12]. However, the
optimal policies for constrained MDPs are no longer limited
to the set of deterministic policies [10], [13], and randomized
stationary policies should be considered. Since the CMDP
defined in Problem 1 has a single global constraint, Corollary 1
below follows immediately from Theorem 4.4 of [10].
Corollary 1. An optimal stationary policy for the CMDP
in Problem 1 exists, and it is a randomized mixture of two
deterministic policies.
The next proposition formalizes the simple observation that
retransmitting a packet immediately after a failed attempt is

better than waiting some slots and then retransmitting (since
the waiting time just increases the age in case of a successful
retransmission, and the age will be the same in case of a
failure). The proof of the proposition is trivial, and hence
omitted.
Proposition 1. There exists an optimal policy for Problem 1
that takes a retransmission action only after a failed transmission event, that is P r(a∗t+1 = x|a∗t = i) = 0.
Based on Proposition 1, the transition for rt in (1) can
be simplified when at = n, and we have rt+1 = 0 instead
of rt+1 = rt . In the next section, the methodology to solve
Problem 1 will be described.
III. P RIMAL -D UAL A LGORITHM

TO

M INIMIZE AO I

To solve the average cost CMDP in Problem 1, we adopt
the Lagrangian primal-dual method [10], [13]. Similar methods have been adopted in other wireless network problems
including [14], [15].
A. Relaxed Unconstrained MDP
Lagrangian relaxation of the constraint with non-negative
multiplier η can be written as:
!
" T
#
T
1 π X π
1 X
π
π
1[at 6= i] ,
Jη = lim
E
δt − η Cmax −
T →∞ T
T t=1
t=1
(3)
and the optimal Jη∗ for a given η is defined as Jη∗ , minπ Jηπ .
Following the methodology proposed in [10], for a constant
η, the above minimization is equivalent to an unconstrained
average-cost MDP, in which the instantaneous overall cost
becomes δt + η 1[aπt ∈ {n, x}].
Then, the problem is to minimize Jη which is the averagecost for the unconstrained problem for a given η. There exits an
optimal stationary deterministic policy, and thus, the optimality
equations can be written. Let h(δ, r) denote the differential
cost (bias) function, and ρ represent the gain, which is an
approximation of the average overall cost; i.e., Jη∗ → ρ [11].
The differential cost function h(δ, r) : S → R is defined
as the difference of the value function V (δ, r) with respect
to an arbitrary but fixed reference state (δ ref , rref ) [11], i.e.
h(δ ref , rref ) = 0, and ∀(δ, r) ∈ S,

h(δ, r) + ρ = min δ + η · 1[a 6= i] + Eπ [h(δ ′ , r′ )] ,
a∈{i,n,x}

(4)

′

′

where (δ , r ) denotes the next state when decision a is taken
at state (δ, r) with a transition matrix given in (1. Equations in
(4) are also known as the Bellman optimality equations [11].
For countable S and finite A, there exists a differential cost
function h(δ, r), ∀(δ, r) ∈ S, and a unique gain ρ, which
satisfy the optimality equations in (4). Moreover, for a given
η value the optimal stationary deterministic policy π ∗ (δ, r) is
given by:

πη∗ (δ, r) ∈ arg min δ + η · 1[a 6= i] + Eπ [h(δ ′ , r′ )] . (5)
a∈{i,n,x}

Note that the state space of possible status age values
is possibly countably infinite. In order to write a practical
algorithm that solves the Bellman equations in (4), we truncate
to the state space S N = {1, 2, . . . , N } × {0, 1, . . . , rmax }
which approaches to the original countable state CMDP as
N → ∞ [16], [7]. Under any reasonable policy for Problem 1,
probability of visiting a state with a large age value decreases
exponentially whereas the cost incurred due to a large age is
polynomial, so it is intuitive to truncate to a large N . The
state transition function when at = i, or at ∈ {n, x} but the
transmission fails can be written as δt+1 = ⌊δt + 1⌋N , where
y = ⌊x⌋N implies y = x if x ≤ N , and y = N otherwise;
which provides the finite state space approximation similarly
to [16], [7].
B. Relative Value Iteration
Value iteration (VI) algorithm can be used to solve
countable-state finite-action MDPs [11]. However, for averagecost problems with Bellman equations defined as in (4), value
functions in VI generally do not converge and differences
between successive value iterations approximate to the true
value of Jη∗ . Due to possible large values, it may result
in numerical instability [11]. Therefore, the relative value
iteration (RVI) algorithm [11] is adopted to solve (4). Starting
with an arbitrary but a fixed reference state (δref , rref ), a
single value iteration for the RVI algorithm [11] is given as
follows:
Qn+1 (δ, r, a) ← δ + η · 1[aπ 6= i] + Eπ [hn (δ ′ , r′ )] ,

(6)

Vn+1 (δ, r) ← min(Qn+1 (δ, r, a)),

(7)

hn+1 (δ, r) ← Vn+1 (δ, r) − Vn+1 (δ ref , rref ),

(8)

a

where Qn (δ, r, a), Vn (δ, r) and hn (δ ′ , r′ ) denote the state
action value function, value function and differential value
function for iteration n, respectively.
C. Finding the Approximate Lagrange Parameter η ∗ and
Randomization
We start with an initial parameter η0 for m = 0, and at
each iteration, run the RVI algorithm and compute ηm+1 as
follows:
ηm+1 ← ηm + α(Cηm − Cmax ).

(9)

We continue iteration until convergence, and find the optimal
parameter η ∗ .
Note that, it is not straightforward to obtain two different
η values for two different deterministic policies, such that the
randomization between the two results in an optimal stochastic
policy. Thus, a heuristic method will be adopted: after obtaining η ∗ , it can be perturbed by small ξ, and the optimal policies
for Lagrange parameters η ∗ + ξ and η ∗ − ξ are computed
and randomized with probabilities µ and 1 − µ, respectively.
The randomization probability µ can be computed using the
average power consumptions of Cη∗ +ξ and Cη∗ −ξ , such that
µCη∗ +ξ + (1 − µ)Cη∗ −ξ = Cmax . The average transmission

bη∗ +ξ , C
bη∗ −ξ can be computed by empirical estimation,
rates C
and randomization probability µ is given by:
µ=

bη∗ +ξ
Cmax − C
.
bη∗ −ξ − C
bη∗ +ξ
C

(10)

IV. AO I WITH C LASSICAL ARQ P ROTOCOL
Now, assume that the system adopts the classical ARQ
protocol; that is, failed transmissions are discarded at the destination. In this case, there is no point in re-transmitting an undecoded packet since the successful transmission probabilities
are the same for a retransmission and the transmission of a
new update. The state space reduces to δ ∈ {1, 2, . . . , N }
as rt = 0, ∀t, and the action space to A ∈ {n, x}. The
probability of error in a status update is p , g(0). State
transitions in (1), Bellman optimality equations in (4) and
the RVI algorithm can all be simplified accordingly. Thanks
to these simplifications, we are able to provide a closedform solution to the corresponding unconstrained MDP with
Lagrange relaxation.
Lemma 1. The optimal policy that minimizes Jη with the standard ARQ protocol admits a deterministic threshold structure
characterized as follows for some threshold value ∆:
(
n if δ ≥ ∆,
π(δ) =
(11)
i if δ < ∆.
Proof. Proof is not included here due to space limitations, but
will be provided in the extended version of the paper.
Theorem 1. Optimal threshold value for the standard ARQ
protocol is given by:
p
2η(1 − p) + p − p
∗
∆ =
.
(12)
1−p
Proof. Proof will be provided in the extended version of the
paper.
Note that the optimal threshold value in (12) depends on η,
which stands for the trade-off between the average AoI and the
constraint. We can compute the average transmission rate for
a given η using the optimal threshold policy in (12), denoted
by Cη . An approximate solution for η ∗ can be obtained by
solving Cη = Cmax . Together with (12) we can obtain the
threshold value for the CMDP as follows:
p
1
−
.
(13)
∆∗ =
Cmax (1 − p) 1 − p
The threshold policy defined in (13) is the optimal deterministic policy for the standard ARQ case when randomization is
not considered, which is not sufficient for the CMDP.
Corollary 2. The optimal policy for the constrained average
AoI problem with standard ARQ is a randomized mixture of
two different threshold policies defined in Theorem 1.
Since we have the threshold in closed-form for the optimal
deterministic policy, which corresponds to η ∗ ; we can compute
∆1 , ∆2 directly by using ∆∗ , instead of finding η1 , η2

Algorithm 1: Average-cost modified SARSA with softmax
1
2
3
4

Input : Lagrange parameter η
n ← 0 /* time iteration
τ ← 1 /* softmax temperature parameter
×3
QN×M
← 0 , ρ ← 0 /* initialization
η

*/
*/
*/

foreach n do

foreach a ∈ A do

5

exp(−Qη (sn , a)/τ )
π(a|sn ) = X
exp(−Qη (sn , a′ )/τ )

6

a′ ∈A

end
Sample an from π(a|Sn ), observe next state sn+1 and cost
cn = δn + η1{an =1,2}
foreach a ∈ A do
exp(−Qη (sn+1 , an+1 )/τ )
π(a|sn+1 ) = X
exp(−Qη (sn+1 , a′n+1 )/τ )

7
8
9
10

a′n+1 ∈A
11
12
13
14
15

16
17
18

end

end
Sample an+1 from π(an+1 |sn+1 )
Update Q√
η (sn , an ) as:
αn ← 1/ n
Qη (sn , an ) ←
Qη (sn , an ) + αn [cn − ρ + Qη (sn+1 , an+1 ) − Qη (sn , an )]
/* update ρ at every step
*/
ρ ← ρ + 1/n[cn − ρ]
n← n+1

first, and then computing ∆1 , ∆2 accordingly. We propose a
heuristic policy (optimal if (∆, C ∆ ) pairs form a convex set)
in order to minimize the average AoI with standard ARQ by
randomizing between the two policies corresponding to the
nearest integers to ∆∗ in (13), that is ∆1 , ⌊∆∗ ⌋, ∆2 ,
⌈∆∗ ⌉. Randomization coefficient µ ∈ [0, 1] can be computed
by using the power consumptions C ∆j of the deterministic
threshold policies corresponding to ∆j , j = 1, 2. From (13)
we have:
C ∆j , (1 − p)−1 (∆j + p/(1 − p))−1 .

(14)

Therefore, randomization factor µ of stochastic policy can be
found using ∆j , j = 1, 2 as in 10, and the resultant algorithm
is a threshold policy that uses ∆1 on the threshold with with
probability µ and ∆2 with probability (1 − µ) at each slot.
V. L EARNING

TO MINIMIZE

AO I IN

AN UNKNOWN

ENVIRONMENT

Here we consider a practical scenario, in which the source
node may not have a-priori information about the channel or
the decoding probabilities at the destination, or these may
change over time. Therefore, an online learning algorithm
is employed to learn g(r) over time without degrading the
performance significantly. The literature for average-cost reinforcement learning (RL) is quite limited compared to discounted cost problems. R-learning [17] is an average-cost RL
algorithm which is an off-policy method similar to Q-learning
[18], and initially proposed with a uniform exploration strategy
(ǫgreedy ).
For the average AoI minimization problem in Problem 1, a
modified version of the R-learning algorithm is employed. In

Figure 3. Deterministic policies πη−ξ (top) and πη+ξ (bottom) when
Cmax = 0.4, p0 = 0.3, and rmax = 9, for a time horizon T = 1000.
The results are averaged over 1000 trials. (Blue circles, red stars and green
diamonds represent actions πη (δ, r) = i, n and x, respectively.)

Algorithm 1 we use the softmax exploration strategy instead
of ǫgreedy for the current and the next states [18]. Then,
Algorithm 1 becomes an on-policy RL algorithm. Moreover,
we update the gain ρ at every time slot based on the empirical
average instead of updating at non-explored time slots and
losing information. The resultant algorithm is called averagecost SARSA with softmax.
VI. N UMERICAL R ESULTS
Decoding error probability is assumed to be given by
g(r) , p0 21−r , where p0 denotes the failure probability
of the first transmission, and r is the retransmission count.
The exponential behavior of the error probability follows
from previous research on HARQ [5], [9]. In Figure 3, we
illustrate the deterministic policies obtained by RVI and η
search for given Cmax , rmax and p0 values. Final policies
are generated by randomizing between πη−ξ and πη+ξ . As it
can be seen from the figure, the designed policy transmits less
as η increases, and vice versa.
Figure 4 illustrates the performance of the proposed randomized HARQ policy with respect to Cmax for different
p0 values. We also include the performance of deterministic
and randomized threshold policies with ARQ. As expected,
average AoI can be reduced by randomization between two
deterministic threshold policies. We observe that average AoI
decreases exponentially with respect to Cmax . The average
AoI also decreases with decreasing p0 and with increasing
rmax as expected.
Figure 5 shows the evolution of the average AoI over time
when the proposed average-cost SARSA learning algorithm is
employed. It can be observed that the average AoI achieved
by Algorithm 1 converges to the one obtained from the RVI
algorithm which has a priori knowledge of g(r). Average
AoI achieved by the proposed online learning algorithm is

12

12
p =0.5, ARQ, deterministic

RL, p 0 =0.5, r max =3

0

p =0.5, ARQ, randomized

RVI, p 0 =0.5, r max =3

p0=0.5, rmax=3, HARQ
0

8

p =0.1, r
0

max
max

RVI, p 0 =0.2,r max =9

=3, HARQ
=9, HARQ

6

Average AoI

p =0.3, r

Average AoI

10

0

10

8

RL, p 0 =0.2, r max =9

6
4

4

2
2

0
0.1

0
0.1
0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

Average number of transmissions, C max

Figure 4. Expected average AoI J π with respect to Cmax for ARQ and
HARQ protocols for different p0 and rmax values. Time horizon is set to
T = 1000, and the results are averaged over 1000 trials.

0.2

0.3

0.4

0.5

0.6

0.7

0.8

Average number of transmissions, C max

Figure 6. Performance of the RL (average-cost SARSA) with respect to RVI
Algorithm for n = 1000 iterations, and values are averaged over 1000 trials
for different p0 and rmax values (both the mean and the variance are shown).

R EFERENCES

Figure 5. Performance of the average-cost SARSA for rmax = 9, p0 = 0.2,
η = 10 and n ≤ 10000, averaged over 1000 trials (both the mean and the
variance are shown).

presented in Figure 6 as a function of Cmax , which shows
that the performance is close to that of RVI.
VII. C ONCLUSIONS
We have considered a wireless system transmitting timesensitive data over an imperfect channel with the average
AoI as the performance measure, which quantifies the timeliness of the data available at the destination. Considering
both the classical ARQ and the HARQ protocols, preemptive
scheduling policies have been proposed by taking into account
retransmissions under a resource constraint. In addition to
identifying a randomized threshold structure for the optimal
policy when the error probabilities are known, an efficient
RL algorithm is also proposed for practical applications, when
the system characteristics may not be known in advance. The
algorithms designed in this paper are relevant to other systems
concerning the timeliness of information, and the proposed
methodology can be used in other CMDP problems. As a
future work, the problem will be extended to time-correlated
channel statistics in a multi-user setting.

[1] S. Kaul, M. Gruteser, V. Rai, and J. Kenney, “Minimizing age of
information in vehicular networks,” in IEEE Coms. Society Conf. on
Sensor, Mesh and Ad Hoc Coms. and Nets., June 2011, pp. 350–358.
[2] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should
one update?” in INFOCOM, Proc. IEEE, March 2012, pp. 2731–2735.
[3] K. Chen and L. Huang, “Age-of-information in the presence of error,”
in IEEE Int’l Symp. on Inf. Theory (ISIT), July 2016, pp. 2579–2583.
[4] I. Kadota, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Minimizing
age of information in broadcast wireless networks,” in Annual Allerton
Conf. On on Communication, Control, and Computing, September 2016.
[5] P. Frenger, S. Parkvall, and E. Dahlman, “Performance comparison of
harq with chase combining and incremental redundancy for hsdpa,” in
IEEE Vehicular Technology Conf. Proc., vol. 3, 2001, pp. 1829–1833.
[6] M. Kashef and A. Ephremides, “Optimal packet scheduling for energy
harvesting sources on time varying wireless channels,” Journal of
Communications and Networks, vol. 14, no. 2, pp. 121–129, April 2012.
[7] Y. P. Hsu, E. Modiano, and L. Duan, “Age of information: Design and
analysis of optimal scheduling algorithms,” in 2017 IEEE International
Symposium on Information Theory (ISIT), June 2017, pp. 561–565.
[8] E. Najm, R. D. Yates, and E. Soljanin, “Status updates through M/G/1/1
queues with HARQ,” CoRR, vol. abs/1704.03937, 2017.
[9] V. Tripathi, E. Visotsky, R. Peterson, and M. Honig, “Reliability-based
type ii hybrid arq schemes,” in Communications, 2003. ICC ’03. IEEE
International Conference on, vol. 4, May 2003, pp. 2899–2903 vol.4.
[10] E. Altman, Constrained Markov decision processes, ser. Stochastic
modeling. Boca Raton, London: Chapman & Hall/CRC, 1999.
[11] M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. New York, NY, USA: John Wiley & Sons, 1994.
[12] L. I. Sennott, “Average cost optimal stationary policies in infinite state
markov decision processes with unbounded costs,” Operations Research,
vol. 37, no. 4, pp. 626–633, 1989.
[13] ——, “Constrained average cost Markov decision chains,” Probability
in Eng. and Informational Sciences, vol. 7, no. 1, p. 6983, 1993.
[14] M. H. Ngo and V. Krishnamurthy, “Monotonicity of constrained optimal
transmission policies in correlated fading channels with arq,” IEEE
Trans. on Signal Processing, vol. 58, no. 1, pp. 438–451, Jan 2010.
[15] A. Roy and A. Karandikar, “Optimal radio access technology selection
policy for lte-wifi network,” in Int’l Symp. Modeling and Opt. in Mobile,
Ad Hoc, and Wireless Nets. (WiOpt), May 2015, pp. 291–298.
[16] E. Altman, R. E. Azouzi, D. S. Menasché, and Y. Xu, “Forever young:
Aging control in dtns,” CoRR, vol. abs/1009.4733, 2010.
[17] S. Mahadevan, “Average reward reinforcement learning: Foundations,
algorithms, and empirical results,” Machine Learning, vol. 22, no. 1,
pp. 159–195, 1996.
[18] R. S. Sutton and A. G. Barto, Introduction to Reinforcement Learning,
1st ed. Cambridge, MA, USA: MIT Press, 1998.

