{"id":"79477699-ffd1-4674-9e4d-583535159063","arxiv_id":"2608.13248","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"In pull-based AoII monitoring of general Markov sources, every reachable belief is exactly parameterized by the last observed state and the elapsed time since it, enabling reduced-state MDPs, finite truncation bounds, and Whittle-index scheduling.","lead":"This paper proves that a monitor deciding when to pull updates from a Markov source only needs to remember the last successfully observed source state and the time since that observation, despite never seeing the source or its estimation error directly. This exact reduction turns a partially observed control problem into a discrete Markov decision process with finite approximations, performance bounds, and index-based multi-source scheduling.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is sound given the synchronized exact-revelation reset; the load-bearing limitation is that the (i,n) reduction collapses if that reset is relaxed.","rationale":"The formal reduction is proved carefully and I found no algebraic error in Theorems 1-6 or the appendices. The reader's weakest_assumption points to the synchronized initial condition, which I agree is the key scope condition. However, the reader's statement that countability of the reachable belief space would fail without it is not quite right: for any fixed initial belief, the number of finite observation histories is finite at each depth, so the reachable set is countable; what fails is the parameterization by (i,n) and the exact equivalence to the reduced MDP. Because the paper states Eq. (9) explicitly and all subsequent claims are conditional on it, this does not undermine the internal correctness of the central claim. The remaining package-level issues (no code artifacts, unspecified selection of m in Table II) justify the reader's CONDITIONAL verdict, and my scope concern does not move the verdict. I therefore recommend UNCHANGED.","tokens_in":28706,"tokens_out":40389,"duration_ms":396038,"concrete_test":"For a two-state Markov source (e.g., P=[[0.8,0.2],[0.3,0.7]], gamma=0.9, s=0.8, lambda=1), compute the optimal value by value iteration on the exact reachable-belief tree truncated at depth H=20 under three initial conditions: (i) the synchronized point mass of Eq. (9); (ii) the stationary-distribution belief with Delta=0; (iii) a noisy-success variant where a successful update reveals the correct state with probability p=0.9. Compare each value with the reduced-MDP value from Eq. (41). If cases (ii) and (iii) deviate from the reduced-MDP prediction, the synchronized exact-revelation reset is confirmed as load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reduction in Theorem 1 is built on the point-mass reset in Eq. (9) and the analogous reset after every successful transmission. Starting from b0(i,Delta)=1{i=i0,Delta=0}, a success reveals the full state and returns the posterior to b_k, so the null-observation recursion b_{i,n+1}=F(b_{i,n},empty) is deterministic and the belief is parameterized by the pair (i,n). This is what turns the POMDP into the fully observed countable MDP of Section IV-A. If the initial belief is non-degenerate, or if a successful packet reveals the state only through noise, the posterior after the reset is not a point mass; the reachable belief is then a full distribution evolving deterministically under null observations, and it is not of the form b_{i,n} for any single i. The reduced-state MDP, the waiting-time table of Section V, and the persistent-policy analysis of Section VI all inherit this assumption. This is a scoping condition explicitly stated in Eq. (9), not an internal inconsistency, but it is the least secure point of the central claim. I note that if the initial belief is relaxed, the reachable belief set remains countable for a fixed initial belief (the observation tree has finite branching); what fails is the two-parameter representation and the resulting equivalence to a fully observed MDP on Y=X x N_{>=1}.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers pull-based remote state estimation of a general finite-state Markov source under an age-of-incorrect-information (AoII) cost, where the monitor observes the source only through (possibly failed) pull requests and uses MAP estimation. It formulates the problem as a belief-MDP, proves that every prior belief reachable from a synchronized initial condition is parameterized by the last successfully observed state and the elapsed no-success duration, and thus obtains an exact countable-state MDP on X × N≥1. On this basis it develops a finite truncation with an explicit error bound and a rule for selecting the truncation level; for reliable links it shows that an optimal policy is a waiting-time table; for unreliable links it proposes a persistent policy with regenerative performance bounds; it proves finite-time MAP stabilization and introduces a hybrid estimator with a computable value-difference bound; and it extends the framework to multiple sources as a restless multi-armed bandit with a sufficient indexability condition and an approximate Whittle-index policy. Numerical experiments compare the persistent policy, Whittle index policy, approximate Whittle index policy, and random scheduling baselines.","tokens_in":28950,"tokens_out":30590,"duration_ms":318633,"significance":"If the results hold, this is a substantial contribution: it turns a POMDP over a belief simplex into a fully observed countable MDP with a finite, error-controlled approximation, for arbitrary asymmetric multi-state Markov sources rather than only binary or symmetric ones. The paper is strong in several specifics: Theorem 1's closure argument is clean and the resulting reduction is genuinely exact under the stated model; Theorem 2 gives a usable, parameter-based truncation bound; Theorem 3 is a correct contraction argument for the reliable-link case; Lemma 1 and Theorem 6 are internally consistent; and the paper does not fit parameters to data or calibrate predictions to targets. The main qualifications are the scope of the synchronized exact-revelation reset and the correctness of the lower-bound part of the persistent-policy certificate in Theorem 4; these are the subjects of my major comments.","major_comments":[{"comment":"The central reduction that every reachable belief has the form b_{i,n} is proved only for the synchronized point-mass initial belief in Eq. (9) and for successful transmissions that reveal the complete source state in Eq. (3). If the initial belief is non-degenerate, or if a successful packet reveals only a noisy or partial observation of the source, the null-observation recursion is no longer deterministic on a two-parameter family and the countable reduced-state MDP, the truncation bound of Theorem 2, the waiting-time table of Theorem 3, the persistent policy of Theorem 4, and the multi-source index policies all lose their exact foundation. This is a scoping condition rather than an internal inconsistency, but it is the load-bearing boundary of the model. I recommend adding a prominent scope paragraph and making the abstract and conclusions carry the same qualifier, so that 'every reachable belief' is not read as a statement about arbitrary initial beliefs.","section":"§IV-A, Eq. (9) and Eq. (3)"},{"comment":"The lower bound L_{ν,T} for the optimal policy is obtained by replacing the continuation cost after T unsuccessful slots by V_min. This replacement is a valid relaxation only if the true continuation value from every state (i,T+1) is at least V_min. If V_min is interpreted as min_i V_i(1), the minimum over post-regeneration states, the needed inequality V_i(T+1) ≥ min_j V_j(1) is not proved and is not obviously true in general; if V_min is instead interpreted as a global minimum over all reduced states, then the subsequent vertex-reduction step at the minimizing state i_0 is not covered, because C_{i,T}(u) assumes a cycle starting at n=1. As written, therefore, the proof does not establish that L_{ν,T} is a lower bound on the optimal cost, and the certificate B_{ν,K,T}(m) in Eq. (56) may not be a guaranteed suboptimality gap. Please either prove the needed monotonicity of the value function or modify the relaxation so that the lower bound is valid under the stated assumptions.","section":"Appendix D-B, Eqs. (105)–(108) and Eq. (54)"}],"minor_comments":[{"comment":"The abstract and Section X state that 'every reachable belief' is represented by the last observed state and elapsed time, omitting the qualifier 'from the synchronized initial condition' that appears in Theorem 1; please align the wording.","section":"Abstract and Conclusions"},{"comment":"The text first says the approximate Whittle table is built using 10 anchor beliefs and that the exact table contains 122 beliefs, but later says the AWIP uses 30 anchor beliefs instead of computing indices for all 366 reachable belief states; these numbers should be reconciled.","section":"§IX-B"},{"comment":"There are small editing issues: 'let the timeline' should be 'Let the timeline', and 'N 0' should be typeset as N_{\\ge 1} (or N_{\\ge 0}, depending on the intended set).","section":"§IV-A and §IV-B"},{"comment":"The header 'PolicyJ ¯J95% CI half-width forJ' is missing column separators and should be reformatted, e.g., as 'Policy | J | J̄ | 95% CI half-width'.","section":"Table II"},{"comment":"The pseudocode contains typos such as 'forally' in lines 3 and 12; please correct them.","section":"Algorithm 2"},{"comment":"Lemma 2 and the bound in Theorem 5 use λ/s and therefore assume s>0, while the model in Eq. (3) allows s=0; please either state s>0 in Section VII or handle the degenerate case separately.","section":"Lemma 2 and Theorem 5"},{"comment":"Theorem 4 is stated for post-regeneration initial distributions ν, but the original problem starts from the synchronized belief b_0, where V^λ(b_0)=γV_{i_0}(1). The γ factor that scales the gap for b_0 should be stated explicitly so that the theorem is directly applicable to the optimization problem of Section III.","section":"Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"This is a strong paper with a clean and useful main reduction, and most derivations are internally consistent. The main risk is the lower-bound proof in Appendix D for Theorem 4; if the authors can close that gap, or alternatively weaken the claim to an upper bound on the persistent policy plus a separate lower-bound argument, the paper should be publishable. The inconsistency in anchor/state counts in Section IX-B is minor but should be fixed in revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The key thing to know: Theorem 1 is sound under the model's stated reset, and it is a genuine advance. The reachable-belief parameterization (last observed state plus elapsed no-success duration) turns the pull-based AoII POMDP into a countable fully observed MDP, and Theorem 2 gives an explicit truncation bound with a usable selection rule. I checked the logic in Section IV and the appendices well enough: no load-bearing error. The cost recursion in Eq. (36) correctly counts consecutive mismatches, and the always-transmit continuation argument for the truncation bound checks out.\n\nThe paper also has real secondary contributions: reliable-link waiting-time look-up tables, regenerative suboptimality bounds for a persistent policy, finite stabilization of the MAP estimate with a hybrid estimator change bound, and an RMAB formulation with a sufficient indexability condition and an interpolation heuristic. Those are more incremental, but they are honest and formally derived.\n\nNow the soft spots, in proportion. The main one is the scoping condition in Eq. (9). The reduction uses a point-mass posterior after every successful transmission and starts from a synchronized initial belief. If you relax that—non-degenerate prior, noisy partial state revelation—beliefs are no longer of the form b_{i,n} and the reduced-state MDP, the truncation theory, and the Whittle construction all fall apart. This is explicitly stated, not hidden, and it is a reasonable model for pull-based status updates with perfect packet payloads, but it is the least secure point of the central claim. The stress-test note is right about that. Also, the channel model lumps failures with idle slots; again an explicit assumption, but structural.\n\nThe numerical validation is weaker. No code or artifacts are shipped. Table II does not say how the persistent-policy waiting-time vector m was chosen. If m was produced by solving the optimal MDP and then the same policy class was evaluated, the near-zero loss is partly baked in. The theorem bounds do not depend on Table II, so this is a package problem, not a math problem. Minor: the indexability condition gamma <= 1/(1+s) restricts the multi-source theory, and beyond it they only offer a heuristic.\n\nBottom line: the paper deserves serious refereeing. The central reduction is correct within its stated scope, and the supported formal bounds are a real contribution. The scope limitation should be prominent in the final version, and the numerical section needs transparency about m and preferably released code. I would bring it to reading group and cite it if I worked in this area.","headline":"Theorem 1 is the real thing: under the synchronized exact-revelation reset, every reachable belief reduces to (last observed state, elapsed no-success duration), and the paper turns the pull-based AoII POMDP into a countable fully observed MDP with explicit truncation control.","tokens_in":29482,"tokens_out":2206,"would_cite":true,"duration_ms":24613,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"In pull-based estimation of a Markov source, every reachable belief is determined by the last observed state and the elapsed no-success duration, reducing a POMDP to an exactly equivalent countable-state MDP.","keywords":["age of incorrect information","pull-based remote state estimation","Markov source","belief Markov decision process","partially observable Markov decision process","no-success cycle reduction","restless multi-armed bandit","AoII truncation error bound"],"falsifier":"Run the belief recursion from the paper's Eq. (9) for a fixed, explicitly given transition matrix and enumerate all histories up to a finite depth; if any reachable belief is not of the form $b_{i,n}$, Theorem 1 is false. A structurally different test: replace the perfect-revelation observation in Eq. (3) by a noisy or partial observation and check whether the reachable belief set becomes uncountable, which would confirm the reduction's dependence on exact state revelation.","tokens_in":28498,"feed_emoji":"📡","tokens_out":14281,"duration_ms":131450,"temperature":0.7,"pith_summary":"This paper studies when a remote monitor should pull updates from a Markov source it cannot see, when the cost is the age of incorrect information (AoII) plus a charge per request. Its central claim is that, under the paper's assumptions, the monitor's full belief state is always determined by two observable numbers: the last source state successfully received and how many time slots have passed without a success. Because those two numbers are enough, the problem becomes an exactly equivalent countable-state Markov decision process rather than a decision process over an uncountable belief space. The paper then proves that truncating the elapsed time at a finite threshold $H$ gives a finite dynamic program with an explicit error bound, and it derives structured near-optimal policies for reliable and unreliable links, as well as a multi-source scheduling extension.","feed_headline":"Pull-based tracking: two numbers replace a full belief state","feed_subtitle":"Optimal pull-based estimation becomes a finite optimization problem with controlled error.","key_machinery":"The load-bearing object is the no-success cycle parameterization $b_{i,n}$, a belief indexed by the last observed source state and the elapsed no-success duration. The parameterization carries the proof because a successful update reveals the exact state and resets the belief to a point mass, while a failed or idle slot is a null observation that leaves the source distribution unchanged; the null-observation recursion sends $b_{i,n}$ to $b_{i,n+1}$, and a successful observation of state $k$ sends it to $b_{k,1}$, keeping the family closed. The reduced MDP's costs and transitions are expressed through the expected posterior AoII $g_i(n)$ and the transition matrix $P$, and the truncation error of Theorem 2 is bounded by explicitly computable quantities $C_n$ and $M_H$.","core_discovery":"The central claim is Theorem 1: every prior belief reachable from the synchronized initial condition is either $b_0$ or a belief $b_{i,n}$, where $i$ is the last successfully observed source state and $n$ is the number of time slots elapsed without a success. The proof shows that the family $\\{b_{i,n}\\}$ is closed under both possible observations: a successful transmission revealing state $k$ sends the belief to $b_{k,1}$, and a null observation, an idle slot or a failed pull, sends it to $b_{i,n+1}$. Along the way the paper derives the source marginal $p_i(n)=e_i P^n$ and the expected posterior AoII $g_i(n)$, and it proves $0 \\leq g_i(n) \\leq n$. Because the observable pair $(i,n)$ is a sufficient state, the pull-based AoII problem is exactly equivalent to a fully observed countable-state MDP on $Y = \\mathcal{X} \\times \\mathbb{N}_{\\ge 1}$.","pith_inferences":["Inference: if the channel is changed so that transmission success depends on the source state, no-success cycles no longer collapse to $(i,n)$; the paper's own reasoning suggests the countable reduction would need a new closure property and would generally fail.","Inference: the same two-parameter state should apply to any freshness or correctness metric that is a deterministic function of the joint distribution of source state and elapsed error duration, not only to AoII.","Inference: the numerical projections suggest that for stable, persistent sources the optimal policy is nearly threshold in the expected AoII; a direct test would be to compute the optimal policy for a family of stable chains and check whether a threshold description holds exactly.","Inference: the paper gives separate computable bounds for truncation, persistent-policy suboptimality, and early stationary switch; combining them into a single end-to-end memory-versus-performance certificate for a given set of parameters is a natural next step the paper does not take."],"forward_implications":["A pull-based scheduler can be implemented with a table indexed by $(i,n)$ rather than by a continuous belief; only the latest observed state and the elapsed no-success time need to be stored and updated online.","For any prescribed tolerance, truncating the elapsed time at $H$ yields a finite MDP whose optimal value differs from the exact value by at most $\\gamma^{H+1}M_H$, so the approximation is controlled by a one-dimensional search over $H$.","For reliable links, the optimal policy is a look-up table of waiting times $m_i^*$: after observing state $i$, the monitor stays idle for $m_i^*-1$ slots and then transmits.","For unreliable links, persistent transmit-until-success policies come with closed-form regenerative bounds on the suboptimality gap, and the MAP estimate stabilizes to the stationary mode after a finite number of slots, enabling an exact finite-memory estimator table.","For multiple independent sources, the reduced state makes each source a countable arm of a restless multi-armed bandit; under a simple condition on the discount factor and success probability the arm is indexable, and an approximate index policy computed from a small number of anchor states matches the exact index policy in the numerical experiments."],"supporting_citations":[{"why":"Introduces the age of incorrect information metric and the threshold results for binary or symmetric Markov sources that this paper generalizes to arbitrary transition matrices.","marker":"[13]"},{"why":"Sets up the pull-based AoII problem with the joint source-AoII belief as a sufficient statistic; this paper's Theorem 1 reduces that formulation.","marker":"[32]"},{"why":"Supplies the standard POMDP framework in which the belief is the information state, motivating the belief-MDP formulation of Section II.","marker":"[28]"},{"why":"Provides the restless multi-armed bandit index method used in the multi-source scheduling construction.","marker":"[36]"},{"why":"Shows that a partial-state-revelation model yields continuous beliefs, the contrast that makes the countable reduction under full-state revelation distinctive.","marker":"[33]"}],"fun_headline_variants":["Belief state collapses to last state and elapsed slots","Pull-based AoII: just two numbers for the belief","Remote estimation: belief is last state plus age","Two variables replace full belief in pull-based tracking","AoII optimization shrinks state to (i,n) pair"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reduction depends on the monitor starting with exact knowledge of the source, on every successful update revealing the complete source state, and on failed pulls carrying no information beyond an idle slot; if any of these breaks, the closed belief family $b_{i,n}$ need not exist and the countable-state reduction can fail.","fun_headline_variants_meta":{"raw":{"variants":["Belief state collapses to last state and elapsed slots","Pull-based AoII: just two numbers for the belief","Remote estimation: belief is last state plus age","Two variables replace full belief in pull-based tracking","AoII optimization shrinks state to (i,n) pair"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000194,"raw_usage":{"total_tokens":1396,"prompt_tokens":1032,"completion_tokens":364,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":648,"completion_tokens_details":{"reasoning_tokens":287}},"tokens_in":648,"tokens_out":364,"duration_ms":3886,"temperature":1.0,"reasoning_tokens":287,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:24:07.747075+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the belief recursion from the paper's Eq. (9) for a fixed, explicitly given transition matrix and enumerate all histories up to a finite depth; if any reachable belief is not of the form $b_{i,n}$, Theorem 1 is false. A structurally different test: replace the perfect-revelation observation in Eq. (3) by a noisy or partial observation and check whether the reachable belief set becomes uncountable, which would confirm the reduction's dependence on exact state revelation.","supporting_citations":[{"cited_title":"The age of incorrect information: A new performance metric for status updates,","cited_arxiv_id":null,"evidence_quote":"Introduces the age of incorrect information metric and the threshold results for binary or symmetric Markov sources that this paper generalizes to arbitrary transition matrices."},{"cited_title":"Joint age-state belief is all you need: Minimizing AoII via pull-based remote estimation,","cited_arxiv_id":null,"evidence_quote":"Sets up the pull-based AoII problem with the joint source-AoII belief as a sufficient statistic; this paper's Theorem 1 reduces that formulation."},{"cited_title":"Planning and acting in partially observable stochastic domains,","cited_arxiv_id":null,"evidence_quote":"Supplies the standard POMDP framework in which the belief is the information state, motivating the belief-MDP formulation of Section II."},{"cited_title":"Restless bandits: Activity allocation in a changing world,","cited_arxiv_id":null,"evidence_quote":"Provides the restless multi-armed bandit index method used in the multi-source scheduling construction."},{"cited_title":"Which sensor to observe? timely tracking of a joint Markov source with model predictive control,","cited_arxiv_id":null,"evidence_quote":"Shows that a partial-state-revelation model yields continuous beliefs, the contrast that makes the countable reduction under full-state revelation distinctive."}],"review_version":1}