  We study the structure of the optimal sampling policy to minimize the average
age of information when the channel state (i.e., busy or idle) is not
immediately perceived by the transmitter upon the delivery of a sample due to
random delays in the feedback (ACK) channel. In this setting, we show that it
is not always optimal to wait for ACKs before sampling, and thus, early
sampling before the arrival of an ACK may be optimal. We show that, under
certain conditions on the distribution of the ACK delays, the optimal policy is
a mixture of two threshold policies.
