CS Paper Radar

Age of Incorrect Information for Pull-Based State Estimation of General Markov Sources

Marco Zanni, Mohamad Assaad, Touraj Soleymani

cs.IT cs.NI ·submitted 2026-08-13 13:52 UTC · v1

Abstract

We study pull-based remote state estimation of an arbitrary, multi-state Markov source while accounting for both freshness and correctness attributes of information. To that end, we formulate a discounted optimization problem in terms of the age of incorrect information (AoII), and express it as a joint source-AoII belief Markov decision process (MDP) under maximum a posteriori (MAP) estimation. We then exploit the information structure of the model and prove that every reachable belief is represented by the last successfully observed source state and the number of time slots elapsed since that observation. For numerical computation, we truncate the elapsed no-success duration at a finite level and derive an explicit error bound and a criterion for selecting the truncation parameter. For reliable links, we show that an optimal policy can be represented by a look-up table of waiting times. For unreliable links, we propose a persistent policy and derive computable performance bounds. We also show that the MAP estimate stabilizes after a finite number of time slots. To further reduce memory requirements, we introduce a hybrid estimator with an early stationary switch and derive a computable bound on the resulting difference in performance. Finally, we extend the framework to multiple sources, formulate the scheduling problem as a restless multi-armed bandit, establish a sufficient condition for indexability, and develop an approximate Whittle index policy based on interpolation. Our numerical results illustrate the structure of the optimal single-source policy, evaluate the performance of the multi-source policies, and verify that the proposed heuristic policies closely approach the optimal solution while substantially reducing computational efforts.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT cs.NImath.PR ·2026-10-15 ·Ismail Cosandal, Sennur Ulukus, Nail Akar
similarity 0.79
Abstract

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.

0.11

Elapsed-Service-Time-Aware Preemption for Age of Information Minimization

cs.IT ·2026-11-04 ·Mohammad Moltafet, Nail Akar, Sennur Ulukus, Marian Codreanu, Roy D. Yates
similarity 0.64
Abstract

We study the age of information and peak age of information in status update systems with an arbitrary number of independent sources sharing a single server with generally distributed service times. We consider a general age-dependent self-preemptive policy in which an in-service update from source $c$ is preempted by a new same-source arrival with a probability $p_c(x)$ that depends on the elapsed service time $x$. This formulation subsumes the non-preemptive, fully self-preemptive, and probabilistically preemptive policies as special cases, and also accommodates threshold-based preemption. We develop a unified analytical framework based on non-homogeneous absorbing continuous-time Markov chains and semi-Markov chains to derive explicit expressions for the average age of information and peak age of information of each source under general per-source service-time distributions and age-dependent preemption rules. The framework applies to both single-source and multi-source systems and enables joint tuning of per-source preemption parameters. Numerical results for fifteen service-time distributions in the single-source setting reveal that the benefits of preemption depend strongly on the service-time hazard-rate structure, with threshold-based preemption providing its most notable additional gains over age-independent policies for distributions with unimodal hazard rates. For a dual-source system with lognormal service times, jointly tuned threshold-based preemption achieves lower sum average age of information and peak age of information than the considered age-independent policies, highlighting the importance of cross-source interactions in preemption decisions.

0.09

Resource-Constrained Semantic-Aware Remote Estimation with Overlapping Sensor Coverage

cs.IT ·2026-09-07 ·Bowen Sun, Nikolaos Pappas
published similarity 0.63
Abstract

We study semantic-aware remote estimation of multiple finite-state Markov sources observed by K sensors with overlapping coverage. The sensors share a time-division multiple-access uplink and differ in transmission reliability, delivery delay, and transmission budget. In each slot, the scheduler jointly selects a source and one of its monitoring sensors, or remains idle, to minimize the long-run average cost of actuation error subject to global and per-sensor transmission-frequency constraints. We formulate this problem as a finite average-cost constrained Markov decision process. We show that the transmission resource functions have rank at most K, although the global constraint may still restrict the feasible region. Consequently, the Lagrangian depends only on K effective transmission costs, and an optimal constrained solution can be represented using at most K+1 deterministic policy-recurrent-class components. We further characterize the piecewise-affine concave Lagrangian value function and derive projected dual subgradient ascent over an explicitly bounded multiplier set. Numerical results illustrate the value-function structure, the need for policy randomization in a representative instance, and the interaction between global and per-sensor transmission budgets.

0.25

Finite-Memory Control of POMDPs: Fundamental Limits and Efficient Design

cs.LG cs.IT ·2026-11-02 ·Emrecan Kutay, Atilla Eryilmaz, Ness Shroff
top venuetheory similarity 0.63
Abstract · Accepted at NeurIPS 2026

Optimal control of partially observable Markov decision processes (POMDPs), in general, requires a complete history. The belief state, a distribution over hidden states, summarizes this history and provides the classical sufficient statistic to control POMDPs. However, the continuous nature of the belief space generally prevents a finite-memory controller from maintaining it exactly. This raises the question we address in this work: what must the available finite memory preserve to achieve near-optimal control performance? We study this question through an information-theoretic converse that gives a fundamental lower bound on the loss of any finite-memory controller. The analysis introduces the concept of a decision witness that characterizes belief states whose confusion would lead to unavoidable loss. Motivated by this bound, we propose RECAP, a constructive quantization method for designing representative memory states. We prove an upper bound on the optimality gap of any RECAP codebook and use the components of this bound together with the converse analysis to define the codebook objective. Experiments on 11 POMDP benchmarks demonstrate that RECAP improves over finite-memory representation baselines under the same memory budget.

0.32

On the Optimality of Implicit Feedback in Markov Decision Processes over Imperfect Links

eess.SY ·2026-11-04 ·Romain Planchon, Federico Chiariotti, Federico Mason, Andrea Zanella, Deniz Gunduz
hot direction similarity 0.63
Abstract · Submitted to IEEE INFOCOM 2027

Goal-oriented communication protocols are explicitly designed to support the objectives of target applications, such as the monitoring and control of remote processes, while minimizing data traffic. This study considers a transmitter node that observes the environment state and sends it to a remote agent, which then performs control actions. This problem can be modeled as a remote Partially Observable Markov Decision Process (POMDP), a subclass of decentralized POMDPs. Existing studies limit transmissions through communication costs, but neglect the effect of channel impairments and non-ideal or delayed feedback. In this work, we study the optimal joint transmission and control policies over lossy forward channels without explicit acknowledgments. We introduce \emph{revealing} policies, under which the receiver's action, observed directly by the transmitter, discloses the outcome of the forward transmission, keeping the two agents synchronized without a feedback channel. We derive sufficient conditions for the optimality of time-invariant policies in this implicit feedback regime for general POMDPs, along with strictly weaker sufficient conditions in the special case of contextual bandits. Our simulations over a family of remote POMDPs show that these conditions are conservative, and revealing policies are optimal over a substantially wider parameter range than the conditions warrant.

0.34

Semantic Freshness Optimal Sampling and Transmission for Gossiping Receivers

cs.IT cs.NIeess.SP ·2026-08-31 ·Irtiza Hasan, Ahmed Arafa
publishedtheory similarity 0.63
Abstract · To appear in IEEE ITW 2026

We study the optimal joint sampling and transmission policy for a transmitter communicating with two gossiping receivers that share information with each other, with the objective of tracking a source under the Version Age of Information (VAoI) metric. The transmitter can observe source-version changes, but it has to pay a sampling cost to get the current source information content. Similarly, it can communicate with a receiver by paying a transmission cost. Gossiping enables local information exchange and is able to reduce costly direct transmissions. With imperfect communication links, we formulate an infinite-horizon average-cost Markov Decision Process (MDP) to jointly minimize receiver VAoI, sampling cost, and transmission cost. Using Relative Value Iteration (RVI), we evaluate the optimal policy and establish several properties of its structure. We prove that sampling has a threshold structure in the transmitter VAoI. Among direct transmissions, it is optimal to serve the older receiver. We further characterize the transmit or idle decision through the receiver VAoI difference. Our analysis shows that link reliability and receiver VAoI imbalance have a significant effect on the optimal policy structure. Numerical results verify the structural properties and demonstrate the performance gains of the optimal policy over multiple baselines.

0.47

Fundamental Tradeoffs in Sampling, Transmission and Information Freshness: Instantaneous Feedback

cs.IT cs.NIeess.SY ·2026-11-16 ·Subhankar Banerjee, Sennur Ulukus
theory similarity 0.62
Abstract

We study a time-slotted generate-at-will status-update system over an erasure channel with transmission success probability $q$, subject to average sampling- and transmission-rate constraints $f_s$ and $f_r$, respectively. The sampler-transmitter pair jointly decides whether to idle, retransmit a stale packet, or replace it with a fresh sample. We derive a universal lower bound on the optimal average age of information, analyze a class of stationary randomized policies, and obtain an optimal policy within this class that provides a $4$-approximation guarantee. The joint problem reduces to the sampling-constrained problem when $f_s\leq qf_r$ and the transmission-constrained problem when $f_s\geq f_r$. For $qf_r<f_s<f_r$, we formulate a constrained Markov decision process (CMDP) and introduce the class $\barΠ$ of $(W,R)$ policies, where $W$ specifies a waiting threshold for transmission and $R$ specifies a packet-replacement threshold. We prove that, for every choice of Lagrange multipliers, the corresponding Lagrangian-relaxed Markov decision process admits an optimal policy in $\barΠ$. We then formulate a linear program (LP) over distributions of $(W,R)$ policies and prove that choosing a policy according to an optimal LP solution yields an optimal CMDP policy. Moreover, there exists an optimal LP solution assigning positive probability to at most three $(W,R)$ policies. Since $\barΠ$ is countably infinite, for every $ε>0$ we construct a finite subset $\barΠ_ε\subset\barΠ$ and show that the LP restricted to this set yields an $ε$-optimal policy. Finally, we derive a stronger pair of lower bounds by considering systems with only the sampling-rate or transmission-rate constraint. Using these bounds, we construct a policy randomizing among four $(W,R)$ policies with a $2$-approximation guarantee for $qf_r<f_s<f_r$.

0.12

Online Scheduling for Throughput Maximization of Time-varying Markovian Channels with Unknown Statistics

cs.NI ·2026-08-19 ·Tasmeen Zaman Ornee, Clement Kam, Ness B. Shroff
similarity 0.61
Abstract · 19 pages, 8 figures. This manuscript is currently under review in IEEE/ACM Transactions on Networking

We consider a wireless scheduling problem in downlink wireless networks with unknown channel statistics, where a Base Station (BS) sends data to multiple users. The scheduling performance relies heavily on accurate Channel State Information (CSI), which is often costly to acquire. In this paper, CSI is obtained from ACK/NACK feedback, only after each scheduled transmission. Due to limited wireless channel resources, all users cannot be scheduled for transmission simultaneously. Hence, the most recently observed CSI can be outdated. The traditional approach to solve scheduling problems using outdated CSI is to utilize belief states, which are calculated using the time correlation statistics of channels. However, channel statistics are often unknown; consequently, belief states can be uncountable and this approach becomes infeasible. In this paper, we introduce a new sufficient statistics for the wireless scheduling problem. Towards this effort, we characterize the CSI staleness by the Age of Channel State Information (AoCSI) and show that the latest observed CSI and its AoCSI is a sufficient statistic of the history to make the scheduling decisions. Accordingly, we are able to reduce the state space for online learning. Our goal is to develop an online scheduling algorithm that maximizes the expected sum throughput of all users over a finite time-horizon while satisfying a channel resource constraint. The formulated problem is a Restless Multi-armed Bandit (RMAB). We develop an online Maximum Gain First (Online-MGF) policy, which achieves sub-linear regret on the number of episodes. For a special case of ON/OFF channels, we are able to prove indexability and derive a closed-form expression of the Whittle index. Numerical results demonstrate that the Online-MGF policy converges to MGF and Whittle index policies with known statistics within a very few episodes.

0.25