PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimizing Age of Incorrect Information in Pull-Based Remote Estimation of a Markov Source

Ismail Cosandal, Sennur Ulukus, Nail Akar

arXiv:2610.22265v1cs.ITcs.NImath.ITmath.PR

TL;DR

The paper asks how to minimize mean age of incorrect information (MAoII) under a sampling-rate constraint when estimating a Markov source through zero- or unit-delay channels. It uses MAP estimation, an SMDP for zero delay, and belief-based constrained deep reinforcement learning for unit delay. In the reported examples, belief-CDRL outperforms benchmark policies, with larger gains for faster or heterogeneous sources.

  • Problem

    The paper seeks pull policies that minimize MAoII under a long-run sampling-rate constraint for remote estimation of a finite-state Markov source.

    Source: §I · p. 2

  • Method

    For zero delay, the paper uses a constrained SMDP; for unit delay, it evaluates policies numerically and optimizes a belief-dependent policy with constrained deep reinforcement learning.

    Source: §I · p. 2

  • Results

    The proposed belief-CRL method outperforms benchmark policies in all studied examples, with gains more apparent for faster or heterogeneous DTMC sources.

    Source: §VIII · pp. 12–13

  • Takeaways & Limitations

    The authors suggest the belief-dependent control approach may apply to other related information-freshness problems.

    Source: §VIII · p. 13

    Extension to more general channels is left for future work.

    Source: §VIII · p. 13

Abstract

from arXiv · show

In this paper, we consider a discrete-time pull-based remote estimation system involving an information source and a remote monitor where the information source is a finite-state irreducible discrete-time Markov chain (DTMC) process. In this system, the remote monitor sends a pull request towards the source which responds by sampling its process so as to transmit the sampled values towards the monitor through a delay channel, encapsulated in information packets. We consider i) zero delay (ZD) and ii) unit delay (UD) channels, where the packet transmission times are zero and one slot, respectively. For remote estimation, we use the maximum a posteriori (MAP) estimator, and for quantifying its performance, we use the mean age of incorrect information (MAoII) which is a recently proposed freshness and mismatch metric that penalizes an incorrect estimation along with its duration. Our goal is to obtain pull policies so as to minimize MAoII under a long-run sampling rate constraint. For the ZD model, we propose a semi-Markov decision process (SMDP) formulation of the problem, which allows us to find the optimum observation-dependent pull policy. On the other hand, the UD channel prevents the monitor from possessing perfect information on the actual AoII process at any given time, and the SMDP formulation of the ZD channel cannot readily be used for the UD model. For the system with the UD channel, we first provide a numerical algorithm to calculate the MAoII and the average sampling rate for a given observation-dependent pull policy. For the optimization of the underlying remote estimation system, we use the joint distribution of the age and source processes to be obtained from the history of all observations, termed as belief. Subsequently, we propose a belief-dependent policy obtained via the belief-MDP formulation and a constrained deep reinforcement learning (CDRL) algorithm.

I. INTRODUCTION

The paper studies MAoII-minimizing pull policies for MAP estimation of a finite-state Markov source over zero- and unit-delay channels. It motivates the metric and estimator choices, develops separate optimization approaches for the two channel settings, and situates them against prior AoII and belief-MDP work.

I. INTRODUCTION

  • Age of incorrect information (AoII) penalizes source-estimate mismatch over time, addressing cases where packet age alone may misrepresent freshness.AoII can return to zero when the source transitions to the monitor's estimate, even without a new sample.Source: §I · p. 1
  • The objective is to minimize mean AoII under a long-run pull-rate constraint for a finite-state Markov source, using MAP estimation over zero- and unit-delay channels.The channels transmit packets in zero and one slot, respectively.Source: §I · pp. 1–2
  • Martingale estimators are common for their simplicity, but the paper incorporates MAP estimation because martingale estimators are inferior for pull-based remote estimation.Source: §I · p. 2
  • For zero delay, the paper formulates constrained MAoII minimization as an SMDP and obtains optimum deterministic observation-dependent pull policies for a general finite-state DTMC source.The policy iteration and Lagrangian approach enforce the long-run pull-rate constraint.Source: §I · p. 2
  • For unit delay, the paper provides an algorithm to calculate MAoII and sampling rate for a given policy, then uses a belief-MDP and constrained deep reinforcement learning for policy optimization.The unit-delay monitor lacks perfect information on the source and AoII, so the zero-delay SMDP formulation cannot be used directly.Source: §I · p. 2

II. RELATED WORK

  • Earlier AoII work focused mainly on symmetric or binary Markov chains and single-threshold policies; prior work notes such policies are not guaranteed optimal for general asymmetric chains.Related work also covers multi-source pull scheduling, POMDP formulations, and methods for continuous belief spaces.Source: §II · pp. 2–3

III. PRELIMINARIES

The preliminaries specify the discrete-time SMDP representation used in the paper and its policy-iteration solution method. The framework accounts for state-action holding times and evaluates policies by long-run average cost per unit time.

A. Semi-Markov Decision Process (SMDP)

B. Absorbing Markov Chains and Time to Absorption

The section introduces absorbing Markov chains and absorption-time quantities, then specifies a pull-based remote-estimation model with MAP or martingale estimation and a sampling-rate constraint. Its AoII evolution resets on synchronization, while the paper excludes more general AoII evolution rules.

B. Absorbing Markov Chains and Time to Absorption

  • An absorbing Markov chain has transient and absorbing states; eventual absorption with probability one ensures the fundamental matrix (I − A)^−1 exists.A contains transitions among transient states, while B contains transitions from transient to absorbing states.Source: B. Absorbing Markov Chains and Time to… · p. 4
  • The section characterizes absorption probabilities by absorbing state and the absorption-time pmf, identifies the latter as discrete phase-type, and gives its first two factorial moments in closed form.The absorption probabilities and time distribution are described for a chain initialized by a probability vector β.Source: B. Absorbing Markov Chains and Time to… · p. 4

IV. SYSTEM MODEL

  • The source is a finite-state irreducible DTMC with known dynamics; the monitor pulls or idles and estimates from received observations.The considered channel delays are zero or one slot, with the observation received immediately in the ZD model and after one slot in the UD model.Source: §IV · pp. 4–5
  • MAP selects the most likely source state, while the martingale estimator uses the latest observation; AoII increments during mismatch and resets at synchronization.The paper studies the evolution rule in (15), not more general rules in the unifying AoII framework.Source: §IV · p. 5
  • A sampling-rate budget α constrains the optimization, and a Lagrangian coefficient λ converts it to an unconstrained problem.The constrained SMDP solution uses the λ* that solves the Lagrangian problem.Source: §IV · p. 5

V. ZERO DELAY CHANNEL

For the zero-delay channel, the paper models observation-dependent waiting as an SMDP: the observed state determines the inter-pull wait, and the cycle cost accounts for sampling and accumulated AoII.

V. ZERO DELAY CHANNEL

  • After observing state i, the policy chooses a wait k until the next pull, and the SMDP transition probability is the probability of state j after k slots.The finite action set bounds the allowed inter-sampling time.Source: §V · p. 5
  • The cycle cost combines one sample with expected AoII accumulated before the next pull, computed from the transient evolution of (X_t, AoII_t).The martingale estimate stays at the last sampled state during the cycle, while the MAP estimate follows the most likely state.Source: §V · pp. 5–6
  • Policy iteration finds the optimum deterministic policy for a fixed Lagrangian parameter, and bisection selects the parameter satisfying the sampling constraint.The example cycle also shows AoII resetting spontaneously when the source returns to the estimated state, before the next pull.Source: §V · p. 6, Figure 2 · p. 6

VI. UNIT DELAY CHANNEL

For the unit-delay channel, the paper constructs an absorbing-chain model to evaluate observation-dependent policies and their MAoII and sampling rate. It then uses a belief-dependent policy obtained through CDRL for optimization.

VI. UNIT DELAY CHANNEL

  • The analytical model evaluates MAoII and average sampling rate for observation-dependent benchmark policies; the ZD-derived policy is one benchmark but is suboptimal for UD.The proposed belief-dependent CDRL policy is evaluated by simulation.Source: §VI · p. 6

A. Analytical Model for Observation-Dependent Pull Policies

  • Within each synchronization epoch, the AMC state (i, j, k) records source state, last observation, and elapsed time since that observation.Synchronization states satisfy i = f(j, k); other states are transient, and absorption begins a new AoII cycle.Source: A. Analytical Model for… · p. 6
  • Under the waiting rule g(j), a pull can synchronize the monitor, but synchronization can also occur without a pull when the estimate matches the source.When k ≥ g(j), a new observation is received; when k < g(j), the estimate continues to evolve from the last observation.Source: A. Analytical Model for… · p. 6
  • The AMC absorption time determines the cycle's accumulated AoII, and its transitions between synchronization states support a semi-Markov evaluation of MAoII and sampling rate.The expected cycle cost is the sum 1 + 2 + · · · + (W(l) − 1); choosing cost C(l) = 1 yields the sampling-rate calculation.Source: A. Analytical Model for… · p. 7

B. Belief-based CDRL

For unit delay, the monitor cannot know the instantaneous source state or AoII, so the paper uses the observation-history belief in a belief-MDP and proposes CDRL. Belief evolution updates the joint distribution using observations and source dynamics, with AoII truncated for practical reasons.

B. Belief-based CDRL

  • Because delay obscures the actual source state and AoII, the paper uses the belief—their joint distribution conditioned on observations—to formulate a belief-MDP and solve it with CDRL.The belief is constructed from the history of observations received by the monitor.Source: B. Belief-based CDRL · p. 7

1) Belief Evolution:

  • Belief evolution first incorporates a new observation into an updated joint distribution, then propagates it using the source dynamics.The update accounts for whether the preceding action requested a pull, since the arriving observation can concern the prior source state.Source: 1) Belief Evolution · pp. 7–8
  • For practical reasons, AoII values are truncated at Δ and assumed not to increase further, unlike in the ZD SMDP formulation.Source: 1) Belief Evolution · p. 7
  • The belief is a sufficient statistic for decision making: the current belief and next observation determine the next belief.The figure illustrates the updates for a ternary source, including the observation branches and MAP estimate.Source: Figure 4 · p. 7, 1) Belief Evolution · p. 8

2) Belief-MDP Formulation:

The belief-MDP represents the monitor’s information as a belief state and models pulls as actions, with costs combining expected AoII and sampling cost. Its transitions follow possible observations and their resulting belief updates.

2) Belief-MDP Formulation:

  • For any belief and action, only as many next beliefs have nonzero transition probability as there are possible observations.Each observation deterministically maps the current belief to a next belief; its transition probability is the probability of that observation given the current belief and action.Source: 2) Belief-MDP Formulation · p. 8
  • When no pull is made, the next observation is 0 with probability 1; when a pull is made, observation j occurs with probability πt(j).Source: 2) Belief-MDP Formulation · p. 8
  • The belief-MDP is specified by the tuple (B, A, T, c, γ), with γ the discount factor.Its Bellman optimality equation gives the average cost of taking an action first and then following the optimal policy.Source: 2) Belief-MDP Formulation · p. 8
  • The belief space is B = [0, 1]N(∆+1), actions are {0, 1}, and the cost of a belief-action pair combines expected AoII with sampling cost.After an observation, the state distribution and estimate are updated using the transition matrix and the specified update rules.Source: 2) Belief-MDP Formulation · p. 8

3) Constrained Deep Reinforcement Learning:

The section presents constrained deep reinforcement learning for belief-dependent pull decisions and compares policies in zero-delay examples. In those examples, observation-dependent sampling improves MAoII, while MAP uniform substantially outperforms ME uniform.

3) Constrained Deep Reinforcement Learning:

  • The belief space is uncountable, so the value function is approximated with a nonlinear network using fully connected layers and a policy-selection step.Fig. 5 depicts the network architecture used for DRL with parameter θ.Source: 3) Constrained Deep Reinforcement… · p. 8, Figure 5 · p. 9
  • The CDRL state augments the belief with the Lagrangian coefficient λ, which is sampled uniformly during training and dynamically updated during execution.The execution-phase update uses the sampling rate from the last B samples.Source: 3) Constrained Deep Reinforcement… · p. 9
  • Belief-CDRL trains main and target networks, selects actions through an exploration-exploitation rule, and has training and execution phases.The target network is soft-updated from the main network; during exploration, actions may instead be chosen uniformly at random.Source: 3) Constrained Deep Reinforcement… · p. 9

A. ZD Channel Examples

  • For sources A and B, observation-dependent inter-sampling times improve MAoII over uniform timing, and MAP uniform substantially outperforms ME uniform.For source B, MAP uniform slightly outperforms ME optimum; for source A, the two show no apparent performance gap.Source: A. ZD Channel Examples · p. 9

B. UD Channel Examples

The UD examples compare belief-CDRL with benchmark policies across sources and source parameters. Belief-CDRL attains the lowest MAoII in the reported comparisons, while its relative advantage and the performance of ZD-derived policies vary with source characteristics.

B. UD Channel Examples

  • The ZD optimum policy assumes zero channel delay and is therefore sub-optimal for UD; steering mixes deterministic policies to meet the sampling constraint almost surely.The policies being mixed have sampling rates below and above the constraint.Source: B. UD Channel Examples · p. 10
  • Pseudo-uniform spreads pulls as far apart as possible when the budget cannot be written as α = 1/M for integer M, and is evaluated by simulation only.Source: B. UD Channel Examples · p. 10
  • For source C, belief-CDRL and ZD optimum with steering perform similarly and both outperform the other policies for every studied budget M.Analytical and simulation results for ZD optimum without steering and uniform policies match, verifying the analysis; simulations use runtime Tmax = 106 time slots.Source: B. UD Channel Examples · p. 11, Figure 7 · p. 11
  • Belief-CDRL attains the lowest MAoII for sources D and E; ZD optimum with steering performs better for D than E, while other policies perform similarly for E.For source D at M = 14, ZD optimum without steering can perform worse than uniform because the budget constraint is not met with equality.Source: B. UD Channel Examples · p. 11, Figure 8 · p. 11
  • For source F, when heterogeneity is low, belief-CDRL and ZD optimum with steering perform similarly; as heterogeneity rises, both have higher MAoII, but belief-MDP is more robust.The source transition matrix is PF(ρ) = (1−ρ)H+ρR, and the comparison uses budgets α = 0.3 and 0.6.Source: B. UD Channel Examples · p. 12
  • For source G, MAoII increases with κ and β; as the steady-state distribution becomes more symmetric, ZD optimum with steering converges to pseudo-uniform.Belief-CDRL has a consistent performance gain over pseudo-uniform of around 10% in this example.Source: B. UD Channel Examples · p. 12, Figure 10 · p. 12

VIII. CONCLUSIONS

The paper minimizes MAoII under a sampling budget for known DTMC sources, using different policy methods for zero-delay and unit-delay channels. Belief-CRL outperforms benchmark policies in all studied examples, with larger gains for faster or heterogeneous sources.

VIII. CONCLUSIONS

  • Belief-CRL outperforms various benchmark policies in all studied examples, with gains more apparent for faster or heterogeneous DTMC sources.The authors leave extension to more general channels for future work.Source: §VIII · pp. 12–13
  • For zero-delay channels, policy iteration and Lagrangian bisection yield optimum deterministic policies, while steering mixes two policies to better satisfy the sampling budget.The estimation uses martingale and maximum a posteriori estimators.Source: §VIII · p. 12
  • For unit-delay channels, belief-CRL selects belief-dependent pulls because the monitor lacks perfect information about the source state or AoII process.The proposed belief-dependent control approach may also apply to related information-freshness problems.Source: §VIII · pp. 12–13

A. Target Stationary Distribution

The source DTMC is constructed to control stationary-distribution asymmetry and chain speed independently. Its target stationary distribution is linearly spaced, and its transition matrix is built from directed-cycle chains.

A. Target Stationary Distribution

  • The target stationary distribution is linearly spaced; β = 1 gives a uniform distribution, while β → 0 yields maximum asymmetry, with π1 → 0 and πN → 2/N.The minimum stationary probability is πmin = π1.Source: A. Target Stationary Distribution · p. 13

B. Cycle-Based Construction of the Transition Matrix

  • The transition matrix is constructed as a convex combination of directed-cycle chains, avoiding an inverse eigenvector problem for the target stationary vector.The construction uses a cycle slice for each step size, allowing either a forward jump or a self-loop.Source: B. Cycle-Based Construction of the… · p. 13
  • The mixture weights shape the jump-size distribution without changing the stationary vector; the chain is irreducible exactly when gcd(N, {i : wi > 0}) = 1.In particular, irreducibility holds whenever w1 > 0.Source: B. Cycle-Based Construction of the… · p. 13
  • The chain is aperiodic when at least one self-loop probability is positive, except when κ = β = 1 and a single step size is used.Source: B. Cycle-Based Construction of the… · p. 13

C. Speed of the Chain

Chain speed is the long-run expected fraction of slots with an actual state change. The parameter κ scales this speed linearly for fixed asymmetry, independently of N and the mixture weights.

C. Speed of the Chain

Loading 2610.22265v1…