PaperlayerView exact revision on arXiv

Source-linked AI summary

The Age of Incorrect Information: A New Performance Metric for Status Updates

Ali Maatouk, Saad Kriouile, Mohamad Assaad, Anthony Ephremides

arXiv:1907.06604v2cs.IT

TL;DR

The paper addresses limitations of AoI and conventional error penalties for remote process estimation by introducing AoII, which measures fresh informative updates. It analyzes transmission over an unreliable channel using MDP and CMDP formulations, showing that always updating is optimal without a power constraint and that a mixture of two deterministic Lagrange policies solves the constrained case.

  • Problem

    AoI does not capture transmitted information content or the monitor’s current knowledge, while conventional error penalties do not increase with the duration of incorrect information.

  • Method

    The paper defines AoII by combining information and time penalties, then uses MDP and Lagrangian CMDP formulations to characterize transmission policies over an unreliable channel.

  • Results

    An always-update policy minimizes average AoII, age, and prediction error without power constraints, while a power-constrained optimum is achieved by mixing two deterministic Lagrange policies.

  • Takeaways & Limitations

    AoII provides a status-update framework that accounts for whether information is new and correct and how long incorrect information persists.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper motivates Age of Incorrect Information (AoII) as a metric for remote estimation that combines update informativeness with increasing dissatisfaction over time. It formulates unconstrained and power-constrained transmission problems and derives policies for minimizing average AoII.

  • Motivation: AoI research has focused heavily on average age, although AoI does not capture packet information content or the monitor’s current knowledge.The paper notes that AoI can penalize elapsed time even when the monitor already has perfect process knowledge.
  • II. PROPOSED METRIC: AoII extends fresh updates to fresh informative updates by combining information content, monitor knowledge, and a time-increasing penalty while incorrect.Informative updates bring new and correct information to the monitor, and the framework allows choices of time and information penalty functions.
  • System model: For an unreliable channel and an N-state Markovian source, the transmitter sends status updates so the receiver can estimate the source accurately.The source model and transmission-policy objective are introduced for a transmitter-receiver pair communicating over an unreliable channel.
  • Policy analysis: Without a power constraint, an always-update policy minimizes average age, prediction error, and AoII.The result is obtained by casting the transmission problem as a Markov Decision Process.
  • Policy analysis: Under a power budget, the problem becomes a Constrained Markov Decision Process solved through Lagrangian policies, whose optimal operating point is a mixture of two deterministic policies.The paper provides a rigorous proof of the mixture result and a logarithmic-complexity algorithm for the constrained AoII-optimal policy.
  • Motivation: The error penalty treats all erroneous states equally, even when incorrect information persists for substantially different durations.The paper contrasts one-slot and 100-slot errors and notes that burst and isolated errors can receive the same long-time average penalty.

III. SYSTEM OVERVIEW

The paper models a transmitter-receiver pair exchanging status updates about an N-state Markov process over an unreliable channel. The transmitter may generate updates at will, and the objective is to minimize the time-average AoII penalty.

  • The system contains a transmitter observing an N-state discrete Markov process and a receiver estimating it from status updates.
  • The process remains in its current state with probability pR and transitions to another state with probability pt, satisfying pR + (N −1)pt = 1.
  • Channel realizations are i.i.d. Bernoulli, with successful decoding probability ps and failure probability pf = 1 −ps.
  • When the transmitter chooses to send, it samples the current process state and transmits the resulting status update.
  • The transmission policy is selected to minimize the time average of the proposed AoII penalty.

B. Penalty Function Dynamics

AoII tracks the time since the monitor was last correct, with dynamics determined by the process evolution, transmission decision, and channel outcome. The resulting optimization is an infinite-horizon average-cost MDP whose optimal policy has explicit regime-dependent structure.

  • The system penalty S(t) uses V(t), the last time instant when the monitor was in a correct state.
  • When S(t) = 0, idling keeps the penalty at zero if the process stays unchanged and raises it to one if the process changes.
  • When a transmission succeeds, the next penalty is zero if the process remains unchanged; otherwise it increases by one.
  • The MDP state is S(t), the action indicates transmission or idling, and the instantaneous cost equals S(t).
  • The value function V(S) is increasing in S, supporting structural characterization of the optimal transmission policy.
  • When pt < pR, transmitting every slot or transmitting whenever the receiver is erroneous is optimal; when pt ≥pR, never transmitting is optimal.
  • In the unconstrained power case, an always-update policy minimizes average AoII, average age, and prediction error.

V. POWER CONSTRAINED SCENARIO

With a transmission power budget, each attempted update incurs cost and scheduling must satisfy a long-run average constraint. The paper converts this CMDP into Lagrangian MDPs and analyzes their optimal policies.

  • Each attempted transmission incurs power cost δ, while the transmitter must respect the average budget δbudget.
  • The transmission policy is a sequence of actions, with ψφ(t) = 1 indicating that a transmission starts at time t.
  • A Lagrange multiplier λ ∈R+ transforms the constrained minimization into optimization of a Lagrangian function.
  • The Lagrangian optimum provides a lower bound on the original constrained optimum, with their difference identified as the duality gap.
  • The unconstrained Lagrangian problem is cast as an MDP with a modified cost function and analyzed through its Bellman equation.

C. Structural Results

The Lagrangian problem has an increasing threshold optimal policy: the transmitter idles below a threshold and transmits at or above it. Threshold policies can be analyzed through a countable-state Markov chain and their average costs.

  • Threshold-policy structure: An increasing threshold policy idles when S < n and transmits when S ≥n, so it is fully characterized by n.
  • Threshold-policy structure: The optimal policy of the Lagrangian problem is an increasing threshold policy.
  • Threshold-policy analysis: The threshold formulation reduces the Lagrangian MDP analysis to studying the threshold value n and its infinite-horizon average cost.
  • Threshold-policy structure: Under a threshold policy, states are penalty values, with idle dynamics below n and transmission dynamics at or above n.
  • Threshold-policy analysis: For each fixed threshold n ∈N∗, the induced DTMC is irreducible and admits a stationary distribution πk(n).
  • Threshold-policy analysis: The average cost of a threshold policy is expressed as C(n, λ) = C(n) + C1(n, λ).

D. Optimality of the Lagrange Approach

The Lagrangian analysis establishes structural properties of threshold policies and proves how they yield an optimal solution to the constrained problem.

  • The standard optimality proof for resource-constrained AoI cannot be directly adopted because the average cost function C(n, λ) is not necessarily convex in n.This nonconvexity motivates the paper’s alternative Lagrangian analysis.
  • The approach proves that C(n) increases with n, defines intersection points, and shows that λ(n) increases with n.
  • When the discrete threshold set does not contain a threshold satisfying the power constraint exactly, mixing φ_n0 and φ_n0+1 achieves the constrained optimum.The mixture uses probabilities ρ = [α − A(n0 + 1)]/[A(n0) − A(n0 + 1)] and 1 − ρ, respectively.
  • For every n ∈ N, there exists λ_n ∈ R+ such that C(n, λ_n) = C(n + 1, λ_n).
  • For the corresponding λ_n0, n0 minimizes the average cost function C(n, λ_n0).

E. Algorithm Implementation

The implementation finds the optimal threshold through exponential upper-bound expansion followed by binary search, then uses a two-threshold mixture to attain the constrained objective.

  • The optimal transmission policy is a mixture of two deterministic threshold policies, φ_n0 and φ_n0+1.
  • A finite n′ exists for every 0 < α ≤ 1, enabling a two-step algorithm to locate the relevant threshold interval.
  • The algorithm first exponentially increases the upper bound NUB until n′ lies within [NLB, NUB].
  • The algorithm then uses binary search to find n′, with logarithmic overall complexity.The first phase takes N1 = log2(n′) iterations, and the second has worst-case complexity N1 − 1.
  • After finding n0 = n′ − 1, transmissions occur at penalties n0 and n0 + 1 with probabilities ρ and 1 − ρ to achieve the constrained optimum.
  • The numerical section examines source-dynamics effects and compares the AoII-optimal policy with AoI and error-function minimization frameworks.

1) Effect of pR:

As pR increases, the optimal policy’s average AoII decreases because the source becomes more predictable and successful updates remain informative longer. Compared with age-based and error-based alternatives, the proposed policy improves AoII, while its age advantage depends on the power budget.

  • 1) Effect of pR:: As pR increases, the optimal policy’s average AoII decreases because transmissions are less likely to become obsolete during delivery.The source becomes more predictable when pR is high.
  • 1) Effect of pR:: Higher pR keeps AoII at zero longer after successful transmissions, allowing a lower threshold without exceeding the power budget.The corresponding threshold n0 decreases as pR increases, reducing the average AoII.
  • 2) Effect of N:: As N grows, average AoII increases because pt = 1−pR N−1 decreases, reducing the chance of recovering the previous state without transmission.The comparison fixes pR = 0.5, α = 0.1, and ps = 0.8.
  • Comparison with the AoI Framework: The proposed policy always outperforms the age-optimal policy in average AoII across the tested power budgets.The curves converge as α increases; for α = 0.02, their AoII gap is 1.1.
  • Comparison with the AoI Framework: The age-optimal policy achieves lower average age, with the gap reaching 190 at α = 0.02, although the gap vanishes for high α.The proposed policy can have AoII equal to 0 while age equals 100 because it uses information content rather than age alone.
  • Comparison in Function of pR: As pR increases from 0.2 to 0.9, the AoII gap between the AoII-optimal and AoI-optimal policies grows from 0.7 to 2.2.The AoI-optimal policy may transmit obsolete packets because AoI increases even when the source retains its value.

APPENDIX A PROOF OF PROPOSITION 3

The proof establishes that the intersection points of the cost curves move monotonically with the threshold, allowing the threshold selected at a given multiplier to be shown optimal.

  • Intersection analysis: C(n) is increasing with the threshold n.This follows by interpreting C(n) as the average penalty of the corresponding unconstrained threshold policy.
  • Intersection analysis: The sequence of intersection points λ(n) is increasing with n.The proof combines the upward movement of C(n,0) with decreasing slopes as n increases.
  • Case n > n0: For n > n0, the intersection with C(n0, λ) occurs after λn0, implying C(n, λn0) > C(n0, λn0).The argument uses the curve properties established in Lemma 3 and the intersection ordering.
  • Conclusion: Therefore, the threshold n0 minimizes C(n, λn0) among the considered thresholds.The two cases establish the required inequalities on either side of n0.
  • Case n < n0: For n < n0, the intersection with C(n0, λ) occurs before λn0, implying C(n0, λn0) ≤ C(n, λn0).The proof uses two lemmas and the increasing behavior of λ(n).

APPENDIX C PROOF OF LEMMA 1

The appendix proves that the value function is increasing in the system state by applying value iteration and showing monotonicity for both transmission decisions.

  • Value iteration: Value iteration converges to the Bellman-equation value function, so monotonicity can be proved inductively across iterations.The proof initializes V0(S)=0 and examines the Bellman update for ordered states.
  • Decision comparison: For an idle transmitter, the Bellman-update expression is ordered consistently for S2 ≥ S1.The proof compares the update expressions x and y for the two states.
  • Decision comparison: For a transmitting transmitter, the Bellman-update expression is likewise ordered consistently for S2 ≥ S1.The corresponding expressions z and w preserve the same inequality.
  • Conclusion: V(S) is increasing in S for all S ∈ N.The result follows because both action-specific updates preserve ordering and the minimum of the updates does as well.

APPENDIX D PROOF OF THEOREM 1

The proof analyzes the always-update policy through its induced Markov chain and derives its stationary behavior and average cost using balance equations.

  • Optimal policy: The always-update policy is optimal when the system state is nonzero in the case pt < pR.At state zero, transmitting and remaining idle produce the same next value function.
  • Markov-chain analysis: The always-update policy induces an irreducible DTMC with stationary distribution πk.The transition dynamics are those associated with transmitting at every time slot.
  • Stationary distribution: The stationary distribution is obtained from πk = aπk−1, with π1 = (N −1)ptπ0 and normalization determining π0.The balance equations are solved by forward induction.
  • Average cost: The average cost is computed by weighting each state k by its state penalty under the stationary distribution.For the alternative case, the analysis substitutes b = pR + (N −2)pt into the corresponding expression.

APPENDIX E PROOF OF PROPOSITION 1

The proof characterizes the Lagrangian policy by comparing the value of transmitting with remaining idle, showing that the optimal action changes monotonically with the state.

  • Action comparison: The action-value difference for nonzero states is ΔVt+1(S) = λ + ps(pt −pR)(Vt(S + 1) −Vt(0)).This expression compares transmitting and idling under the Lagrangian formulation.
  • State-zero decision: At state S = 0, remaining idle is always optimal because λ ≥ 0.The transmission and idling comparison at zero yields the stated preference.
  • Threshold structure: For S ≠ 0, the optimal action increases with S from idling to transmitting.The action-value difference decreases with S, so transmission becomes more beneficial beyond a threshold.

APPENDIX F PROOF OF PROPOSITION 2

The proof derives balance equations for the threshold policy across successive state ranges, then uses induction and series identities to obtain the stationary probability and average-cost expressions.

  • The proof begins with the balance equation at state 1, yielding π1(n) = (N −1)ptπ0(n).
  • Forward induction extends the balance-equation results from states 2 ≤ k ≤ n to states k ≥ n + 1.
  • Substituting the derived πk(n) values and applying series results determines π0(n), completing the stationary-probability proof.
  • For the threshold policy, the state S = k incurs cost k, while transmission is attempted only when S ≥ n, giving C(n, λ) = C(n) + C1(n, λ).
  • Replacing stationary probabilities from Proposition 2, changing variables with k′ = k − n, and applying series analysis yields the expressions in (29) and (30).
Loading 1907.06604v2…