Pith. sign in

REVIEW 3 major objections 5 minor 25 references

Optimal Information Updating based on Value of Information

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For a remote constant-gain estimator of a stable Gauss-Markov process, the paper proves that scheduling the queued packet with the smallest age-and-precision index $W_\psi^2(t)$ minimizes expected cumulative squared estimation error.

desk verdict A clean, likely-correct value-of-information index for remote estimation with heterogeneous source quality, but the proof has a genuine finite-horizon gap and an unstated non-idling assumption. read the letter →

arxiv 1908.01119 v1 pith:OUZQPECY submitted 2019-08-03 cs.IT cs.NImath.IT

Rahul Singh , Gopal Krishna Kamath , P. R. Kumar This is my paper · ORCID
classification cs.ITcs.NImath.IT
keywords ageofinformationvalueremoteestimationGauss-Markovprocessconstant-gainKalmanfilterindexpolicypacketschedulingunreliablechannel
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how a network node sharing one unreliable channel should choose which queued sensor packet to transmit when a remote linear filter with a constant gain uses the packets to estimate a scalar Gauss-Markov process. It claims that the optimal rule is an index policy: compute for each packet a closed-form number that grows with both the packet's age and its source's observation-noise variance, and transmit the packet with the smallest number. This matters because freshness alone can be the wrong objective, since a very fresh but very noisy packet can carry less estimation value than an older, more precise one. Under a stability assumption on the process and filter gain, the paper proves the index policy minimizes the expected cumulative squared estimation error and extends the result to several independent processes sharing a network. A reader should care because the result turns an apparently intractable dynamic scheduling problem into a sorted-queue rule and separates the question of how old the data is from how useful the data is in real-time estimation.

What carries the argument

The central object is the packet index $W_\psi^2(t)$, defined as the closed-form contribution of packet $\psi$ to the one-step expected squared estimation error if it is delivered. Because the term depending on the current error $e(t)$ is common to every choice, minimizing $W^2$ at the last time step is optimal, and an exchange argument shows that swapping packet order never helps at earlier steps either. The time-invariance of the pairwise ordering (Lemma 2) is what makes the policy implementable as a single sorted queue, with a new packet inserted in $O(\log|Q(t)|)$ time, and it is the property that lets the backward-induction proof go through.

What would settle it

Brute-force dynamic programming over all non-idling policies on a small instance, say two sources, $T=10$, $a=0.9$, $K=0.05$, and $p=0.5$, should reproduce the index policy's expected cost; if any non-idling policy yields strictly smaller expected cumulative squared error, the paper's optimality claim is false.

Watch

Extended reading notes

Core claim

The paper's central claim is that the single-queue scheduling problem admits an index policy: at each time $t$, assign to each queued packet $\psi$ the index $$W_\$psi^{2}$(t) = $a^{2}$$K^{2}$\left($a^{{2\tau_\psi(t)}}$\sigma_{s,\psi}^2 + \$sigma^{2}$\frac{$a^{{2\tau_\psi(t)}}$-1}{$a^{2}$-1}\right) + \$sigma^{2}$,$$ where $\tau_\psi(t)$ is the packet's age and $\sigma_{s,\psi}^2$ is the variance of its source's observation noise, and transmit the packet with the smallest $W_\psi^2(t)$. Under the stated stability condition on the process $a$, the filter gain $K$, and a non-idling scheduler, this policy minimizes $\mathbb{E}\sum_{t=1}^T e^2(t)$ over all scheduling policies. Priority is therefore governed jointly by freshness and source precision, so it is not optimal to order packets by age alone.

Load-bearing premise

The proof assumes the scheduler is non-idling, meaning whenever the queue is nonempty it must transmit some packet; if deliberate idling were allowed, sending a very old and noisy packet could increase expected error and the index policy would not necessarily remain optimal.

Editorial extensions

If this is right

  • A system that minimizes age of information alone does not in general minimize expected squared estimation error for a constant-gain filter; both the age and the precision of the source must enter the packet-priority rule.
  • The optimal scheduler is implementable as a single sorted queue: because the relative order of any two packets is fixed over time, inserting a new packet requires only $O(\log|Q(t)|)$ comparisons and no re-sorting is ever needed.
  • For $N$ independent processes sharing a common network node with i.i.d. channel-access probabilities, the joint problem decomposes into $N$ single-process problems, and composing the per-process index policies is optimal with total cost $\sum_{i=1}^N J_i^*(e_i(0);p p_i;T)$.
  • The optimal expected cost depends only on the initial error and queue contents, the horizon $T$, and the channel reliability $p$, so the same index rule works unchanged across different arrival processes and time horizons.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One extension the paper leaves open is allowing the scheduler to idle: because the optimality proof compares only non-idling policies, a threshold rule that skips transmission when every queued packet's $W_\psi^2(t)$ exceeds some function of the current error is a natural candidate for the idle-armed problem.
  • Because the index ordering is time-invariant, the policy may be learnable online: if source precisions or channel reliability are unknown, the scheduler could estimate $\sigma_{s,\psi}^2$ from delivered packet innovations and still maintain a sorted queue, though the paper does not address parameter uncertainty.
  • Since the filter gain $K$ is fixed, the index separates cleanly into sensing-noise and process-noise terms; a plausible next step is to co-optimize $K$ and the scheduling rule, in which case the index would become a function of the chosen gain, but the paper's optimality proof does not cover that joint problem.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies a discrete-time remote estimation system in which a network node receives noisy observations of a scalar Gauss-Markov process from multiple sources with different sensor precisions, queues the resulting packets, and transmits one packet per slot over an unreliable channel to a remote estimator running a constant-gain linear filter. The objective is to minimize the expected cumulative squared estimation error over a finite horizon T. The authors define an index W^2_psi(t) that combines a packet's age and its source's noise variance, propose the Index Policy that transmits the packet with the smallest index, and claim in Corollary 1 that this policy is optimal under Assumption 1. They also extend the result to N processes whose channel access is chosen i.i.d., showing that the optimal scheduler is a product of single-process index policies (Theorem 2).

Significance. If the optimality proof can be made rigorous, the paper would provide a clean, index-based scheduling rule for remote estimation and would establish the important qualitative point that age-optimal scheduling is not necessarily estimation-optimal when sensor precisions vary. The derivation is principled: the index is computed from the model's error covariance rather than fitted, and the ordering-invariance property in Lemma 2 makes implementation efficient. The significance is conditional, however, because the proof of Theorem 1 as written does not yet establish the finite-horizon claim; the infinite-horizon tail and undefined stopping times are load-bearing issues rather than cosmetic ones.

major comments (3)
  1. [Section VI, Theorem 1 and Eq. (25)] The proof of Theorem 1 does not establish the finite-horizon claim in Corollary 1. The objective (4) is E(sum_{t=1}^T e^2(t)), but the cost difference in Eq. (25) contains the term (Delta(psi2,psi1,T2)+Delta(psi1,psi2,1)alpha_{1,T2}) sum_{t>=T2} alpha_{T2,t} with no upper limit. Lemma 5 proves positivity of the infinite-tail expression, not of the truncated expression. If T1>T, so that psi2 is never delivered within the horizon, T1 and T2 in Eq. (16) are not even defined on that sample path. Even when T1<=T, the tail t>T does not vanish because the two packets' noise terms enter the error process at different times with different closed-loop coefficients. The proof therefore needs a finite-horizon truncation argument that shows the sign of the cost difference restricted to t<=T, or a reformulation of the theorem as an infinite-horizon result.
  2. [Section VI, Theorem 1 proof (non-idling assumption)] The exchange argument assumes that all compared policies are non-idling: the proof states 'since they are non-idling, the a(t) are the same under all policies.' This restriction is not stated in the problem formulation in Section IV, where the action is only 'which packet to transmit' and there is no explicit idle action. If a policy were allowed to remain idle or transmit a dummy packet while Q(t) is nonempty, the closed-loop gain process a(t) would differ across policies, and the comparison in Eq. (25) would not apply. The authors should either state non-idling as an explicit assumption or extend the argument to allow idling.
  3. [Eq. (16), Lemma 3] The stopping times T1 and T2 defined in (16) are not guaranteed to exist within the finite horizon. For a sample path on which psi2 is never transmitted successfully under pi_idx by time T, the set {t: psi(t;pi_idx)=psi2} is empty. Lemma 3 and Lemma 4 rely on T1 and T2 being finite and on T2<=T1, but no conditioning on these events is given, and the complement is not analyzed. The proof should define T1 and T2 as hitting times truncated at T (or as infinity) and handle the cases where they exceed T separately.
minor comments (5)
  1. [Eq. (21)] The definition alpha_{s,t} := product_{m=s}^t a^2(t) appears to have a typo: the product index and the variable inside the product should be m, so that alpha_{s,t} depends on a^2(m) for m=s,...,t.
  2. [Eq. (25)] In the first equality of Eq. (25), the text says 'we used Lemma 2 in order to deduce Delta(psi2,psi1,1) = (a^2)^{T2} Delta(psi2,psi1,1)', but the correct statement is Delta(psi2,psi1,T2) = (a^2)^{T2} Delta(psi2,psi1,1).
  3. [Lemma 5 proof] In the chain of inequalities in Lemma 5, the step that drops the term -(a_c^2)^T/(1-a^2) reverses the direction of the inequality, because that term is negative; the proof should be corrected or clarified.
  4. [Section IV and Section VII] The paper says sigma_psi is the variance of the observation noise, but the model y_psi = x(t_psi) + sigma_psi w_psi with w_psi of unit variance makes sigma_psi a standard deviation; the notation sigma^2_{s,psi} in Eq. (9) should be aligned with this. There is also a typo in Section VII: 'distribted according to vec p' should be 'distributed according to vec p'.
  5. [References] Reference [12] refers to the 'Weiner process'; the correct spelling is 'Wiener process'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the index policy is derived from the model's error dynamics and justified by an exchange argument, not from fitting or self-referential assumptions.

full rationale

The claimed result is the optimality of the Index Policy for the cumulative squared estimation error objective. The index W_psi^2(t) is derived, not postulated: Eq. (9) is obtained from the one-step-ahead cost expression (7)-(8), which itself follows from the filter error recursion (6). Lemma 1 is simply the one-step optimality of choosing the packet with smallest W_psi^2. Theorem 1 then attempts to establish optimality for all times via an exchange argument relative to an arbitrary one-step deviation, and Corollary 1 invokes standard dynamic-programming backward induction. No data are fitted and no fitted parameter is renamed as a prediction; the result is self-contained given the model assumptions. The authors cite their own prior work in the related-literature discussion, but those citations concern age-of-information, throughput, and inter-delivery-time problems and are not load-bearing for the optimality proof. No uniqueness theorem from prior work is imported, and no ansatz is smuggled in via citation: the constant-gain filter is standard and cited to an external source [24]. The skeptical observation that the proof of Theorem 1 uses infinite-horizon sums in Eq. (25) while the claim is finite-horizon is a correctness concern about a missing truncation or tail argument, not a circularity. Nothing in the derivation reduces to its own inputs by construction, so the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters were fitted; the index is derived from the model. The paper introduces no new physical entities. The load-bearing assumptions are the stable Gauss-Markov model, the constant-gain filter with the K bound, the mandatory-transmission action space, and the i.i.d. channel model.

assumptions (4)
  • domain assumption The process x(t) is scalar Gauss-Markov with |a|<1 and the filter uses a constant gain K satisfying K <= (1-a^2)/a^2.
    Invoked in Assumption 1 and used in Lemma 5 to prove the key inequality that makes the exchange argument work.
  • domain assumption The scheduler must transmit a packet whenever the queue is nonempty (non-idling).
    The model's action space is 'which packet to transmit'; the proof compares only non-idling policies. If idling were allowed, transmitting old noisy packets could be suboptimal when the current error is small.
  • domain assumption Channel successes are i.i.d. with probability p and ACK is available after each transmission.
    Standard in the model; used in the cost recursion (7) and in the coupling argument comparing policies.
  • domain assumption Gaussian noises and linear filtering imply that only the second moments of the error matter for the scheduling objective.
    The index W^2 is derived from error covariance evolution; higher moments do not affect the optimality proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Information Updating based on Value of Information." pith.science (2026). https://pith.science/paper/OUZQPECY

@misc{pith2026190801119,
  author       = {Pith},
  title        = {Pith review of: Optimal Information Updating based on Value of Information},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OUZQPECY}},
  note         = {Machine review of arXiv:1908.01119}
}
read the original abstract

We address the problem of how to optimally schedule data packets over an unreliable channel in order to minimize the estimation error of a simple-to-implement remote linear estimator using a constant "Kalman'' gain to track the state of a Gauss Markov process. The remote estimator receives time-stamped data packets which contain noisy observations of the process. Additionally, they also contain the information about the "quality'' of the sensor\ source, i.e., the variance of the observation noise that was used to generate the packet. In order to minimize the estimation error, the scheduler needs to use both while prioritizing packet transmissions. It is shown that a simple index rule that calculates the value of information (VoI) of each packet, and then schedules the packet with the largest current value of VoI, is optimal. The VoI of a packet decreases with its age, and increases with the precision of the source. Thus, we conclude that, for constant filter gains, a policy which minimizes the age of information does not necessarily maximize the estimator performance.

Figures

Figures reproduced from arXiv: 1908.01119 by the authors.

Figure 1
Figure 1. N sources generate data packets which contain information about the process to the network node. The packets at the network node are queued in a single queue, and wait to be transmitted to the destination. The sources differ in the precision of their measurements of the process x(t). choice in order to encapsulate the notion of freshness of data. The age at a given time is equal to the time elapsed since the freshes… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 19 canonical work pages

  1. [1]

    Real-time status: How often should one update?

    S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” inINFOCOM, 2012 Proceedings IEEE. IEEE, 2012, pp. 2731–2735

    work page 2012

  2. [2]

    Minimizing the age of information in broadcast wireless net- works,

    I. Kadota, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Minimizing the age of information in broadcast wireless net- works,” in 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016, Monticello, IL, USA, September 27-30, 2016, 2016, pp. 844–851. [Online]. Available: https://doi.org/10.1109/ALLERTON.2016.7852321

    arXiv 2016

  3. [3]

    Scheduling policies for minimizing age of information in broadcast wireless networks,

    I. Kadota, A. Sinha, E. Uysal-Biyikoglu, R. Singh, and E. Modiano, “Scheduling policies for minimizing age of information in broadcast wireless networks,” IEEE/ACM Trans. Netw., vol. 26, no. 6, pp. 2637–2650, 2018. [Online]. Available: https://doi.org/10.1109/TNET.2018.2873606

    arXiv 2018

  4. [5]

    Applying update streams in a soft real-time database system,

    B. Adelberg, H. Garcia-Molina, and B. Kao, “Applying update streams in a soft real-time database system,” in ACM SIGMOD Record, vol. 24, no. 2, 1995, pp. 245–256

    work page 1995

  5. [6]

    Synchronizing a database to improve freshness,

    J. Cho and H. Garcia-molina, “Synchronizing a database to improve freshness,” 2000, pp. 117–128

    work page 2000

  6. [7]

    Scheduling updates in a real-time stream warehouse,

    L. Golab, T. Johnson, and V. Shkapenyuk, “Scheduling updates in a real-time stream warehouse,” in Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, March 29 2009 - April 2 2009, Shanghai, China , 2009, pp. 1207–1210. [Online]. Available: https://doi.org/10.1109/ICDE.2009.202

    work page doi:10.1109/icde.2009.202 2009

  7. [8]

    Real-time status updating: Multiple sources,

    R. D. Yates and S. Kaul, “Real-time status updating: Multiple sources,” in Proc. IEEE ISIT , July 2012, pp. 2666–2670

    work page 2012

  8. [9]

    Lazy is timely: Status updates by an energy harvesting source,

    R. D. Yates, “Lazy is timely: Status updates by an energy harvesting source,” in IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, China, June 14-19, 2015 , 2015, pp. 3008–3012. [Online]. Available: https://doi.org/10.1109/ISIT.2015.7283009

    work page arXiv 2015

Show all 25 references
  1. [10]

    Timely status update in wireless uplinks: Analytical solutions with asymptotic optimality ,

    Z. Jiang, B. Krishnamachari, X. Zheng, S. Zhou, and Z. Niu, “Timely status update in wireless uplinks: Analytical solutions with asymptotic optimality ,” IEEE Internet of Things Journal , vol. 6, no. 2, pp. 3885–3898, 2019. [Online]. Available: https://doi.org/10.1109/JIOT.201...

    2019

  2. [11]

    A unified sampling and scheduling approach for status update in multiaccess wireless networks,

    Z. Jiang, S. Zhou, Z. Niu, and Y. Cheng, “A unified sampling and scheduling approach for status update in multiaccess wireless networks,” in 2019 IEEE Conference on Computer Communications, INFOCOM 2019, Paris, France, April 29 - May 2, 2019 , 2019, pp. 208–216. [Online]. Avail...

    2019

  3. [12]

    Remote estimation of the wiener process over a channel with random delay ,

    Y. Sun, Y. Polyanskiy , and E. Uysal-Biyikoglu, “Remote estimation of the wiener process over a channel with random delay ,” in 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, June 25- 30, 2017 , 2017, pp. 321–325. [Online]. Available: http...

    2017

  4. [13]

    Decentralized throughput maxi- mizing policies for deadline-constrained wireless networks,

    Rahul Singh and P. R. Kumar, “Decentralized throughput maxi- mizing policies for deadline-constrained wireless networks,”IEEE Conference on Decision and Control , 2015

    2015

  5. [14]

    Throughput optimal decentralized scheduling of multihop networks with end-to-end deadline constraints: Unreliable links,

    R. Singh and P. R. Kumar, “Throughput optimal decentralized scheduling of multihop networks with end-to-end deadline constraints: Unreliable links,” IEEE Trans. Automat. Contr. , vol. 64, no. 1, pp. 127–142, 2019. [Online]. Available: https://doi.org/10.1109/TAC.2018.2874671

    2019

  6. [15]

    A risk-sensitive approach for packet inter-delivery time optimization in networked cyber- physical systems,

    X. Guo, R. Singh, P. Kumar, and Z. Niu, “A risk-sensitive approach for packet inter-delivery time optimization in networked cyber- physical systems,” IEEE/ACM Transactions on Networking (TON), vol. 26, no. 4, pp. 1976–1989, 2018

    1976

  7. [16]

    A high reliability asymptotic approach for packet inter-delivery time optimization in cyber-physical systems,

    ——, “A high reliability asymptotic approach for packet inter-delivery time optimization in cyber-physical systems,” in Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing , ser. MobiHoc ’15. New York, NY, USA: ACM, 2015, pp. 197–206. [...

    2015

  8. [17]

    Index policies for optimal mean-variance trade-off of inter-delivery times in real-time sen- sor networks,

    R. Singh, X. Guo, and P. R. Kumar, “Index policies for optimal mean-variance trade-off of inter-delivery times in real-time sen- sor networks,” in Computer Communications (INFOCOM), 2015 IEEE Conference on . IEEE, 2015, pp. 505–512

    2015

  9. [18]

    Optimizing quality of experience of dynamic video streaming over fading wireless networks,

    R. Singh and P. Kumar, “Optimizing quality of experience of dynamic video streaming over fading wireless networks,” in Decision and Control (CDC), 2015 IEEE 54th Annual Conference on. IEEE, 2015, pp. 7195–7200

    2015

  10. [19]

    Maxweight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic,

    R. Singh and A. Stolyar, “Maxweight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic,” in ACM SIGMETRICS Performance Evaluation Review, vol. 43, no. 1. ACM, 2015, pp. 431–432

    2015

  11. [20]

    Maxweight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic,

    ——, “Maxweight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic,” in Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, ser. SIGMETRICS ’15. New York, NY, USA: ACM, 2015, pp. 431–432

    2015

  12. [21]

    Throughput-optimal wireless scheduling with regulated inter-service times,

    R. Li, A. Eryilmaz, and B. Li, “Throughput-optimal wireless scheduling with regulated inter-service times,” in INFOCOM, 2013 Proceedings IEEE , April 2013, pp. 2616–2624

    2013

  13. [22]

    Heavy-traffic-optimal scheduling with regular service guarantees in wireless networks,

    B. Li, R. Li, and A. Eryilmaz, “Heavy-traffic-optimal scheduling with regular service guarantees in wireless networks,” inProceed- ings of the Fourteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing , ser. MobiHoc ’13. ACM, 2013, pp. 79–88

    2013

  14. [23]

    P. R. Kumar and P. Varaiya, Stochastic systems: Estimation, iden- tification and adaptive control . Prentice Hall Inc., Englewood Cliffs, 1986

    1986

  15. [24]

    Kalman filtering over a packet-delaying network: A probabilistic approach,

    L. Shi, L. Xie, and R. M. Murray , “Kalman filtering over a packet-delaying network: A probabilistic approach,” Automatica, vol. 45, no. 9, pp. 2134–2140, 2009. [Online]. Available: https://doi.org/10.1016/j.automatica.2009.05.018

    2009 doi

  16. [25]

    M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1st ed. New York, NY, USA: John Wiley & Sons, Inc., 1994

    1994

  17. [26]

    Multivariate stochastic approximation using a simul- taneous perturbation gradient approximation,

    J. C. Spall, “Multivariate stochastic approximation using a simul- taneous perturbation gradient approximation,” IEEE transactions on automatic control , vol. 37, no. 3, pp. 332–341, 1992

    1992

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.