  In this paper, we introduce a new performance metric in the framework of
status updates that we will refer to as the Age of Incorrect Information
(AoII). This new metric deals with the shortcomings of both the Age of
Information (AoI) and the conventional error penalty functions as it neatly
extends the notion of fresh updates to that of fresh "informative" updates. The
word informative in this context refers to updates that bring new and correct
information to the monitor side. After properly motivating the new metric, and
with the aim of minimizing its average, we formulate a Markov Decision Process
(MDP) in a transmitter-receiver pair scenario where packets are sent over an
unreliable channel. We show that a simple "always update" policy minimizes the
aforementioned average penalty along with the average age and prediction error.
We then tackle the general, and more realistic case, where the transmitter
cannot surpass a specific power budget. The problem is formulated as a
Constrained Markov Decision Process (CMDP) for which we provide a Lagrangian
approach to solve. After characterizing the optimal transmission policy of the
Lagrangian problem, we provide a rigorous mathematical proof to showcase that a
mixture of two Lagrange policies is optimal for the CMDP in question. Equipped
with this, we provide a low complexity algorithm that finds the AoII-optimal
operating point of the system in the constrained scenario. Lastly, simulation
results are laid out to showcase the performance of the proposed policy and
highlight the differences with the AoI framework.
