  In this work, we consider the problem of jointly minimizing the average cost
of sampling and transmitting status updates by users over a wireless channel
subject to average Age of Information (AoI) constraints. Errors in the
transmission may occur and a scheduling policy has to decide if the users
sample a new packet or attempt for retransmission of the packet sampled
previously. The cost consists of both sampling and transmission costs. The
sampling of a new packet after a failure imposes an additional cost on the
system. We formulate a stochastic optimization problem with the average cost in
the objective under average AoI constraints. To solve this problem, we propose
three scheduling policies; a) a dynamic policy, that is centralized and
requires full knowledge of the state of the system, b) two stationary
randomized policies that require no knowledge of the state of the system. We
utilize tools from Lyapunov optimization theory in order to provide the dynamic
policy, and we prove that its solution is arbitrary close to the optimal one.
In order to provide the randomized policies, we model the system by utilizing
Discrete Time Markov Chain (DTMC). We provide closed-form and approximated
expressions for the average AoI and its distribution, for each randomized
policy. Simulation results show the importance of providing the option to
transmit an old packet in order to minimize the total average cost.
