Semi-Markov Decision Process Framework for Age of Incorrect Information Minimization

For a remote estimation system, we study age of incorrect information (AoII), which is a recently proposed semantic-aware freshness metric. In particular, we assume an information source observing a discrete-time finite-state Markov chain (DTMC) and employing push-based transmissions of status update packets towards the monitor which is tasked with remote estimation of the source. The source-to-monitor channel delay is assumed to have a general discrete-time phase-type (DPH) distribution, whereas the zero-delay reverse channel ensures that the source has perfect information on AoII and the remote estimate. A multi-threshold transmission policy is employed where packet transmissions are initiated when the AoII process exceeds a threshold which may be different for each estimation value. In this general setting, our goal is to minimize the weighted sum of time average of an arbitrary function of AoII and estimation, and transmission costs, by suitable choice of the thresholds. We formulate the problem as a semi-Markov decision process (SMDP) with the same state-space as the original DTMC to obtain the optimum multi-threshold policy whereas the parameters of the SMDP are obtained by using a novel stochastic tool called dual-regime absorbing Markov chain (DR-AMC), and its corresponding absorption time distribution named as dual-regime DPH (DR-DPH).