Early Sampling: Sampling with Incomplete Queue State Information to Minimize the Age

In many existing communication models, the channel state (i.e busy or idle) is conveyed to the sampler via ACKs which are often assumed to be instantaneous. Previous literature shows that in this ideal feedback setting, an optimal sampling policy that minimizes the age of information (AoI), should not sample when the channel is busy, and therefore, must always wait for the ACK of the previous sample before taking the next sample. However, this may not be optimal when the feedback channel (backward channel) has a random delay. In this work, we study the structure of the optimal sampling policy to minimize the AoI when the channel state (i.e., the forward queue state) is not immediately perceived by the sampler due to random delays in the feedback channel. In this setting, we show that it is not always optimal to wait for ACKs before sampling, and thus, early sampling with the available incomplete channel state information may be better. We show that, under certain conditions on the distribution of the ACK delays, the (asymptotically) optimal policy reduces to a mixture of two threshold policies.