  Age of Incorrect Information (AoII) is a newly introduced performance metric
that is adaptable to a variety of communication goals. It has advantages over
both the traditional performance metrics and the recently introduced metric -
Age of Information (AoI). However, the fundamental nature of AoII has been
elusive so far. In this work, we consider the AoII in a system where a
transmitter sends updates about a multi-state Markovian source to a remote
receiver through an unreliable channel. The communication goal is to minimize
AoII subject to a power constraint. We cast the problem into a Constrained
Markov Decision Process (CMDP) and prove that the optimal policy is a mixture
of two deterministic threshold policies. Afterward, by leveraging the notion of
Relative Value Iteration (RVI) and the structural properties of threshold
policy, we propose an efficient algorithm to find the threshold policies as
well as the mixing coefficient. Lastly, numerical results are laid out to
highlight the effects of system parameters on the performance of AoII-optimal
policy.
