{"id":"db597095-099c-4f39-8135-0d1a9d366971","arxiv_id":"1908.01334","paper_version":6,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A truncated scheduling policy built on single-user constrained-MDP solutions is shown to be asymptotically optimal for minimizing average Age of Information in multi-state fading networks with per-user power constraints.","lead":"This paper designs a scheduling algorithm to keep collected information fresh in wireless networks where each user has limited power and only a few users can transmit at once. It shows that decoupling the problem into single-user decisions and then truncating the schedule yields near-optimal freshness as the network grows.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix C's O(1/sqrt(N)) bound depends on Theorem 2's threshold structure for the randomized single-user policy, but that theorem is unproven in the tight-power case; monotonicity alone does not imply a single randomized threshold.","rationale":"The paper's central claim is the asymptotic optimality of the truncated policy in Theorem 3. The proof reduces this to two ingredients: a concentration argument for the number of eager users (which is sound, since the decoupled users are independent) and a bounded-age/threshold-structure argument for each user's relaxed policy (Appendix C). The second ingredient is where the argument is least secure. Theorem 2's tight-power case is not proved in the paper; it is asserted to follow from [21], and Corollary 2's monotonicity does not by itself yield the one-randomized-state threshold structure. Without that structure, the bound x_n(t) <= tau_{n,Q}, the geometric miss probability z, and the uniform O(1) bound on thresholds have no foundation, so the advertised O(1/sqrt(N)) gap is not established. The reader's overall rationale already lists the [21] deferral, but the reader's designated weakest assumption is the i.i.d. channel model, which is an explicit modeling choice rather than an internal gap; I therefore regard the threshold proof as the load-bearing concern. The numerical simulations in Section V are consistent with the claimed behavior up to N=50 but do not test the asymptotic rate or the structural theorem. Because the issue is an unverified but plausibly repairable proof step rather than a demonstrated counterexample, the appropriate disposition remains CONDITIONAL, so I do not change the reader's verdict.","tokens_in":17181,"tokens_out":21618,"duration_ms":244421,"concrete_test":"Solve LP (20) for Q=2, Xmax=10, eta=(0.7,0.3), omega=(1,4), W=0, and an E that makes the power constraint active; enumerate all vertices of the feasible polytope and count states with 0 < y_{x,q}/(mu_x eta_q) < 1. If any optimal vertex has two or more fractional scheduling probabilities, Theorem 2's at-most-one-randomized-state assertion is false and the bounded-age step of Appendix C collapses. Independently, complete the tight-power proof of Theorem 2 from the KKT conditions of (20) without importing side conditions from [21, Theorem 5]; if it cannot be completed, the conditional verdict remains necessary.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Appendix C's use of a threshold structure for the optimal stationary randomized policy of the decoupled CMDP. Theorem 3 bounds the AoI of every user under the relaxed policy by tau_{n,Q} (Eq. (44c)) and assumes the probability that an eager, truncated user remains unscheduled decays geometrically with exponent governed by Gamma_n = tau_{n,Q} - tau_{n,1}. Both require Theorem 2: for each channel state q, xi*_{x,q}=0 for x<tau_q, xi*_{x,q}=1 for x>tau_q, and randomization only at tau_q, with tau_1 <= ... <= tau_Q. The proof of Theorem 2 establishes only Corollary 2, a monotonicity statement; monotone xi matrices may have many fractional entries and do not imply a single randomized threshold. The tight-power case is deferred to [21, Theorem 5] without verifying that its assumptions (a queueing model with Bernoulli arrivals, boundedness or strict-convexity structure) transfer to the AoI CMDP (11)-(12). The bounded-age step and the uniform-threshold claim in Eq. (46) also require tau_{n,Q} not to grow with N, which is asserted for the W sequence from the dual search but not proved. The i.i.d. channel assumption is explicit in Eq. (2), so it is a scope condition rather than the critical internal weak point.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers a slotted wireless network in which a central controller collects status updates from N users over multi-state fading channels. Each user has an average power constraint, and at most M users can be scheduled per slot. The objective is to minimize the long-term average Age of Information per user. The authors relax the hard per-slot bandwidth constraint to a time-average constraint, form a Lagrangian with multiplier W, and decouple the problem into N single-user constrained Markov decision processes. They claim a dual threshold structure for the optimal single-user policy, reformulate each single-user CMDP as a linear program, and then construct a truncated scheduling policy that respects the hard bandwidth constraint. The main theoretical result is Theorem 3: with M/N = θ held constant, the per-user AoI gap between the truncated policy and the relaxed lower bound is O(1/√N), so the truncated policy is asymptotically optimal. Simulation results compare the proposed policy with a greedy baseline and illustrate threshold-type scheduling behavior.","tokens_in":17451,"tokens_out":18366,"duration_ms":192235,"significance":"If the main claims are correct, the paper offers a tractable LP-based solution to a meaningful cross-layer AoI problem and an asymptotically optimal scheduling rule under a hard bandwidth constraint. The LP reformulation in Theorem 1 and the steady-state balance equations appear sound, and the asymptotic optimality statement is concrete and falsifiable. The simulations support the qualitative claims about channel-aware scheduling for power-limited users. The main weakness is the incomplete proof of the threshold structure used in the asymptotic argument: Theorem 2 is not established for the tight-power case, and Appendix C relies on that structure in several places. The paper also contains a repairable algebraic error in the proof of Lemma 1. The central idea is promising, but the current version is not self-contained enough for the claimed Theorem 3.","major_comments":[{"comment":"The displayed inequality chain in Eq. (37) is algebraically inconsistent. From Eq. (36) the correct implication for x′ > x is α Σ η_{q′} V_α(x′+1,q′) ≥ α Σ η_{q′} V_α(x+1,q′) ≥ α(λω(q)+W)+α Σ η_{q′} V_α(1,q′). The printed line omits the discount factor from parts of the right-hand side and asserts α Σ η_{q′} V_α(x′+1,q′) > Σ η_{q′} V_α(x+1,q′), which is not a consequence of monotonicity because α<1. Since Lemma 1 is the basis for the threshold-structure claims, this step must be corrected.","section":"Appendix A, Eq. (37)"},{"comment":"The proof of Theorem 2 does not establish the claimed single-threshold structure. Corollary 2 supplies only monotonicity of ξ*_{x,q} in x and q. By Corollary 1, the optimal stationary randomized policy is a mixture of two deterministic threshold policies; if those two policies have different threshold vectors, then ξ*_{x,q} takes a constant fractional value on an interval of x, so the assertion that randomization occurs only at a single x per channel state does not follow. The tight-power case is deferred to [21, Theorem 5] without verifying that the queueing and arrival assumptions of [21] transfer to the AoI CMDP in Eqs. (11)-(12). This matters because Appendix C uses the threshold structure both to bound x_n(t) ≤ τ_{n,Q} and to control the probability that an eager user remains eager in subsequent slots.","section":"Section III-D, Theorem 2"},{"comment":"The O(1/√N) bound contains several unproved assertions that are load-bearing for Theorem 3. First, the quantity p in the paragraph before Eq. (42) is never defined, and the subsequent construction of z = (N-M)/N + (M/N)(1-η_{n,1}) is not derived from a precise conditional probability over the event that the relaxed policy would schedule the user. Second, Eq. (46) asserts that τ_{n,Q} and Γ_n do not grow with N for users with fixed power constraints; this is not proved and depends on the behavior of the Lagrange multiplier W as N grows. Third, the concentration bound [31] is applied to ||Ω(t)|−Ω|, but the independence assumptions underlying that bound should be stated explicitly. The asymptotic optimality claim therefore needs a more rigorous proof or clearly stated extra conditions.","section":"Appendix C, Eqs. (44)-(46)"}],"minor_comments":[{"comment":"The subgradient formula d_W g(W(k)) should contain the factor 1/N if g(W) is defined as in Eq. (25); the printed formula (1/N)Σ A_n(W(k)) - M is missing the 1/N. This does not change the zero set but it affects the step-size interpretation in the subgradient update.","section":"Eq. (27)"},{"comment":"The definition of β_x should be Σ_{q=1}^Q η_q ξ_{x,q}; the subscript x on ξ is missing in the displayed equation.","section":"Eq. (16b)"},{"comment":"The notation WMN in Eq. (9) should be written as W M/N, and in Fig. 4 the caption appears to have a typo: “ρ = {0.2, 0.4.1.4, 1.6}” should be “ρ = {0.2, 0.4, 1.4, 1.6}”.","section":"Eq. (9) and Fig. 4"},{"comment":"The expressions for z and 1/(1-z) should be reconciled: from the displayed z one obtains z = 1 - θ η_{n,1}, whereas the text writes 1/(1-z) = 1/(min_n η_{n,q}(1-(N-M)/N)). The current notation is confusing and should be cleaned up.","section":"Eq. (44c)"},{"comment":"The concentration step in Eq. (45) would be clearer if it used a standard Berry-Esseen or Lyapunov CLT statement for sums of independent bounded variables, and if the independence of the indicators s_n(t) across users were stated explicitly.","section":"Reference [31]"}],"recommendation":"major_revision","confidential_remarks":"The paper has a useful and plausible approach, but the proof of the central asymptotic optimality theorem is not yet self-contained. The dependence on [21, Theorem 5] and the imprecise probabilistic argument in Appendix C should be addressed carefully before acceptance. The LP formulation and the simulation study are solid parts of the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does something real: it takes AoI scheduling out of the two-state, identical-user world and gives a tractable LP reformulation for Q-state i.i.d. fading with per-user average power budgets and a hard bandwidth limit. The decoupling into single-user CMDPs and the linear programming in Theorem 1 are clean and, as far as I can tell, correct. The dual search and the truncated policy are natural. Simulations are consistent with the theory. If those were the whole story, this would be a solid journal paper.\n\nThe soft spots are in the proofs, and they are not cosmetic. Lemma 1 has a typo in inequality (37): the discount factors are misplaced. The intended inequality is true, so that one is repairable. The bigger issue is Theorem 2. The tight-power case is dismissed with a pointer to [21, Theorem 5] without checking that its queueing-model assumptions transfer to this AoI CMDP. Corollary 2 gives monotonicity of the randomized scheduling probabilities, but monotonicity alone does not imply a single threshold per channel state; there could be many fractional entries. That matters because Appendix C leans directly on the single-threshold structure to bound the probability that an eager user stays unscheduled and to define Γ_n. The claim that τ_{n,Q} stays bounded as N grows is also asserted rather than proved. And the round-robin lower bound in (48) is simply wrong as stated—round robin isn't feasible under power constraints—though you can replace it with the trivial bound J≥1 and the asymptotic argument still goes through.\n\nNone of this makes me think the central idea is wrong. The framework is plausible and likely fixable. But the current version overstates what has been proved: the O(1/sqrt(N)) gap is not yet supported, and the threshold structure in the tight-power case is an unverified borrowing. The i.i.d. channel assumption is a scope condition rather than a flaw; it should just be stated more prominently.\n\nWho gets value from this: people working on AoI scheduling, CMDP-based cross-layer design, and asymptotic analysis of constrained schedulers. It advances an active subfield rather than opening a new one. I would send it to peer review, but with a request for major revisions, specifically a self-contained proof of Theorem 2 (or a verified reduction to [21]) and a corrected Appendix C. The LP framework alone justifies refereeing it.","headline":"A genuinely useful LP-based framework for AoI scheduling with power constraints, but the advertised O(1/sqrt(N)) optimality is not yet rigorously backed because the threshold-structure theorem is deferred and the proof gaps are non-trivial.","tokens_in":18004,"tokens_out":5409,"would_cite":true,"duration_ms":56150,"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":"This paper proves that a simple truncated scheduling policy — transmit when a user's age exceeds a per-channel threshold, and cap simultaneous transmissions at M — achieves average Age of Information within O(1/√N) of the optimal value as…","keywords":["Age of Information","constrained Markov decision process","threshold structure","opportunistic scheduling","power constraint","bandwidth constraint","asymptotic optimality","time-varying channels"],"falsifier":"Simulate the truncated policy with M/N = 1/5 on the paper's four-state i.i.d. channel model for N = 100, 400, and 1600, measuring (J(π̃) − AoI_LB)/AoI_LB; Theorem 3 predicts this normalized gap decays like 1/√N, so a plateau or growth in the gap would refute asymptotic optimality.","tokens_in":16947,"feed_emoji":"⏱️","tokens_out":9638,"duration_ms":89801,"temperature":0.7,"pith_summary":"This paper asks how a central controller should schedule updates from many battery- and bandwidth-limited users over wireless channels that vary randomly from slot to slot, so that the average age of the freshest information stays small. The paper proves that the problem can be broken into per-user subproblems once the hard bandwidth limit is relaxed, that each subproblem's optimal policy has a simple threshold form (transmit only when the information is old enough or the channel is good enough, with thresholds ordered by channel quality), and that a truncated multi-user rule that simply caps the number of simultaneous transmissions is asymptotically optimal: as the number of users grows with the bandwidth fraction held fixed, the average age it achieves approaches the relaxed-problem lower bound at rate O(1/√N). The practical consequence is a computationally tractable way to design near-optimal freshness-aware schedules in large networks, with the scheduler using good channels for power-starved users and keeping well-powered users updated often enough to fill the bandwidth.","feed_headline":"Cutoff scheduler nears the freshness optimum as networks grow","feed_subtitle":"Collected data ages approach the freshness lower bound within O(1/√N) under power and bandwidth limits.","key_machinery":"The load-bearing object is the threshold-structured stationary randomized policy for the decoupled single-user CMDP, together with the truncated multi-user policy built from it. In the single-user problem the state is (x, q), the current age and channel state; the threshold property says transmission is optimal exactly when age x is at least τ_q, with τ_1 ≤ ⋯ ≤ τ_Q, and at most one state randomizes. This structure turns the Markov decision process into a finite linear program whose variables y_{x,q} = μ_x η_q ξ_{x,q} are the stationary probabilities of being in each state and transmitting. The multi-user policy then schedules all eager users when at most M qualify and otherwise selects M eager users uniformly; the proof of asymptotic optimality bounds the AoI loss from these truncation events by a concentration bound on the number of eager users, giving the O(1/√N) gap.","core_discovery":"The central claim is Theorem 3: for a network of N users with M = θN schedulable slots per time step, the expected average Age of Information under the proposed truncated policy — schedule every user whose individual policy says 'transmit', and if too many qualify, pick M of them uniformly at random — differs from the optimal value of the original bandwidth- and power-constrained problem by at most O(1/√N). Hence, as N grows, the truncated policy is asymptotically optimal. The path to this result is a chain of reductions: relax the hard bandwidth constraint to a time-average constraint, decouple the users through a Lagrange multiplier W, show the single-user constrained Markov decision process has an optimal stationary randomized policy with threshold structure (for each channel state q there is a threshold τ_q such that the user transmits whenever its age is at least τ_q, and τ_q is smaller for better channels), solve the single-user problem exactly as a linear program, and then use concentration of the number of 'eager' users to control the loss from truncation.","pith_inferences":["Beyond the paper: if the channel process is Markovian rather than i.i.d., the same decomposition could in principle be carried out with the age augmented by channel memory, but the thresholds would become functions of the channel-state history and the O(1/√N) concentration argument would need a new bound; the paper's result does not cover this case.","Beyond the paper: the proof of Theorem 3 bounds the gap using the worst-case threshold span and the worst-case channel probability; a tighter bound is likely available by exploiting the actual distribution of the eager set, which would shrink the constant while preserving the 1/√N rate.","Beyond the paper: the threshold-based policy suggests a natural online-learning extension when channel distributions are unknown — estimate η and adapt the LP thresholds periodically; this paper assumes known distributions.","Beyond the paper: the same LP-with-truncation construction should apply to other freshness metrics, such as peak age, as long as the single-user Bellman equation retains monotonic structure; the paper only treats average AoI."],"forward_implications":["For large N with fixed bandwidth fraction θ, network operators can implement the truncated policy and be guaranteed average AoI within O(1/√N) of the relaxed-problem lower bound.","Per-user thresholds can be computed offline by solving a small linear program for each distinct channel-distribution and power-budget type, so the online scheduler is simple: compare current age to a precomputed threshold and pick a subset of eager users.","The scheduler automatically differentiates users: power-limited users transmit mainly in good channel states, while power-rich users transmit often and at low age, filling the bandwidth.","The asymptotic-optimality result holds for heterogeneous users because the decoupling is per-user; the proof does not require identical channel distributions or power budgets across users."],"supporting_citations":[{"why":"Defines Age of Information, the metric the whole paper minimizes.","marker":"[1]"},{"why":"Supplies the greedy-policy baseline and the round-robin lower bound used to normalize the asymptotic gap in Theorem 3.","marker":"[10]"},{"why":"Provides the threshold-structure proof technique (Lemma 2 and Theorem 5 analogues) used to establish the form of the optimal single-user policy.","marker":"[21]"},{"why":"Supplies the relaxation-and-truncation template for constructing a policy that satisfies the hard constraint from a relaxed solution.","marker":"[25]"},{"why":"A standard CMDP reference guaranteeing existence of an optimal stationary randomized policy as a mixture of two deterministic policies, grounding the decoupling and LP solution.","marker":"[28]"},{"why":"Gives the subgradient algorithm and its convergence properties used to search for the Lagrange multiplier W.","marker":"[29]"},{"why":"Provides the average-cost optimality result that lifts the threshold structure from discounted to average-cost MDPs.","marker":"[30]"},{"why":"Delivers the closed-form concentration bound on the deviation of the eager-user count from its mean, which yields the O(1/√N) gap.","marker":"[31]"}],"fun_headline_variants":["Tiny freshness gap: scheduler approaches AoI optimum as N grows","Randomly drop eager senders: still near freshness bound","LP threshold policy: near-optimal Age of Information for many users","Asymptotic optimality: simple scheduler for fresh data","Age of Information near-optimal with threshold scheduling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire chain — decoupling, threshold structure, and the O(1/√N) concentration bound — assumes each user's channel state is independent and identically distributed from slot to slot with a known distribution; if channels are temporally correlated, the age-and-channel state no longer summarizes the user and the theorem's scope ends.","fun_headline_variants_meta":{"raw":{"variants":["Tiny freshness gap: scheduler approaches AoI optimum as N grows","Randomly drop eager senders: still near freshness bound","LP threshold policy: near-optimal Age of Information for many users","Asymptotic optimality: simple scheduler for fresh data","Age of Information near-optimal with threshold scheduling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001364,"raw_usage":{"total_tokens":5545,"prompt_tokens":968,"completion_tokens":4577,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":584,"completion_tokens_details":{"reasoning_tokens":4494}},"tokens_in":584,"tokens_out":4577,"duration_ms":33805,"temperature":1.0,"reasoning_tokens":4494,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:17:01.504128+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the truncated policy with M/N = 1/5 on the paper's four-state i.i.d. channel model for N = 100, 400, and 1600, measuring (J(π̃) − AoI_LB)/AoI_LB; Theorem 3 predicts this normalized gap decays like 1/√N, so a plateau or growth in the gap would refute asymptotic optimality.","supporting_citations":[{"cited_title":"Real-time status: How often should one update?","cited_arxiv_id":null,"evidence_quote":"Defines Age of Information, the metric the whole paper minimizes."},{"cited_title":"Scheduling policies for minimizing age of information in broadcast wireless networks,","cited_arxiv_id":null,"evidence_quote":"Supplies the greedy-policy baseline and the round-robin lower bound used to normalize the asymptotic gap in Theorem 3."},{"cited_title":"Joint queue-aware and channel-aware delay optimal scheduling of arbitrarily bursty traffic over multi-state time-varying channels,","cited_arxiv_id":null,"evidence_quote":"Provides the threshold-structure proof technique (Lemma 2 and Theorem 5 analogues) used to establish the form of the optimal single-user policy."},{"cited_title":"Throughput optimal decentralized schedul- ing of multihop networks with end-to-end deadline constraints: Unreli- able links,","cited_arxiv_id":null,"evidence_quote":"Supplies the relaxation-and-truncation template for constructing a policy that satisfies the hard constraint from a relaxed solution."},{"cited_title":"Altman, Constrained Markov decision processes","cited_arxiv_id":null,"evidence_quote":"A standard CMDP reference guaranteeing existence of an optimal stationary randomized policy as a mixture of two deterministic policies, grounding the decoupling and LP solution."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the subgradient algorithm and its convergence properties used to search for the Lagrange multiplier W."},{"cited_title":"Average cost optimal stationary policies in infinite state markov decision processes with unbounded costs,","cited_arxiv_id":null,"evidence_quote":"Provides the average-cost optimality result that lifts the threshold structure from discounted to average-cost MDPs."},{"cited_title":"Closed form summation for classical distributions: variations on a theme of de moivre,","cited_arxiv_id":null,"evidence_quote":"Delivers the closed-form concentration bound on the deviation of the eager-user count from its mean, which yields the O(1/√N) gap."}],"review_version":1}