  Age of Incorrect Information (AoII) is a newly introduced performance metric
that considers communication goals. Therefore, comparing with traditional
performance metrics and the recently introduced metric - Age of Information
(AoI), AoII achieves better performance in many real-life applications.
However, the fundamental nature of AoII has been elusive so far. In this paper,
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
performance of AoII-optimal policy.
