Minimizing Age of Incorrect Information over a Channel with Random Delay

We investigate a transmitter-receiver pair in a slotted-time system. The transmitter observes a dynamic source and sends updates to a remote receiver through a communication channel. We assume that the channel is error-free but suffers a random delay. We consider two more practical cases to facilitate the analysis. In the first case, the update is guaranteed to be delivered within a certain number of time slots. In the second case, once the transmission time exceeds a predetermined value, the update is immediately discarded, leaving the channel free for a new transmission on demand. The receiver will maintain an estimate of the current state of the dynamic source using the received updates. In this paper, we adopt the Age of Incorrect Information (AoII) as the performance metric and investigate the problem of optimizing the transmitter's action in each time slot to minimize AoII. We first characterize the optimization problem using the Markov decision process and investigate the performance of the threshold policy, under which the transmitter transmits updates only when the AoII exceeds the threshold $\tau$. By delving into the characteristics of the system evolution, we precisely compute the expected AoII achieved by the threshold policy using the Markov chain. Then, we prove that the optimal policy exists and provide a computable relative value iteration algorithm to estimate the optimal policy. Next, by leveraging the policy improvement theorem, we prove that, under an easy-to-verify condition, the optimal policy is the threshold policy with $\tau=1$. Finally, numerical results are laid out to highlight the performance of the optimal policy.