{"id":"789ac5c9-917f-4497-bf75-a26368de17d4","arxiv_id":"2506.09180","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The infinite-state dynamic program for optimal task offloading with firm deadlines is reduced to a finite lean-state computation, and the optimal policy is characterized by an adjacent-state off-by-one rule.","lead":"This paper finds the optimal way to decide how many computing tasks to offload to a remote cloud when the link is only occasionally available and each task has a firm deadline. It reduces the infinite-state dynamic program to a small finite set of states, which makes the optimal policy computable and reveals a simple structure: neighboring states have decisions that differ by at most one.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"For T < N, the lean-state set is infinite: Definition 2 zeroes γ_i for i > min(N,T), so Algorithm I leaves b_i untouched and each state (0,...,0,b_{T+1},...,b_N) is its own lean state.","rationale":"I read the paper's central claim as the finite-state reduction: for every state s, V_T(s) can be obtained from the DP evaluated only on a finite set of lean states plus the linear adjustment of Eq. (21). The most load-bearing condition for that claim is that the lean-state set is finite and that Eq. (21) correctly accounts for all surplus tasks. The reader's identified weakness—that surplus tasks might interact with lean-state tasks—is plausible, but my own testing of small examples (e.g., s=(0,2,1) with T=2 and s=(1,2) with T=1) did not produce a failure of Eq. (21); the Appendix B case analysis, while terse, appears consistent with the transition order, and the linear correction correctly handles offloading opportunities up to the horizon. The sharper, more decisive problem is the horizon-truncation gap: when T < N, Definition 2 and Algorithm I deliberately stop processing components i > min(N,T), yet Eq. (20) then copies those unbounded components into the lean state. This makes the lean-state set infinite whenever T < N, directly contradicting the paper's finite-state claim, Lemma 1's scope, Algorithm II's bounded memory, and the memory-saving plots in Section VII. The issue is concrete and checkable by enumeration, and it does not rely on subtle queueing interactions. It is fixable by either assuming T ≥ N (which all simulations satisfy, with T=1000 and N≤10) or by truncating the state to the first min(N,T) components; the paper does neither, so the theorem as written is false in an explicitly contemplated regime. I therefore keep the reader's CONDITIONAL verdict: the main approach is promising and likely correct for T ≥ N, but the manuscript must be revised to state the required horizon assumption or fix the truncation, and the proof of Proposition 1 should explicitly establish the non-interaction of surplus tasks rather than asserting it in the case analysis.","tokens_in":48877,"tokens_out":27596,"duration_ms":271409,"concrete_test":"Set N=3, T=1. For k=0,1,2,..., compute the lean state of s_k=(0,0,k) using Definition 2 and Algorithm I. Since γ_2=γ_3=0 and the algorithm's loop stops at i=1, every s_k is its own lean state; the cardinality of the lean-state set grows linearly with k, whereas a finite set requires a bound independent of k. Then run Algorithm II on s_k and record the number of entries in memory M after solving the DP: because each distinct lean state generates a stored quadruplet, the stored count grows without bound, directly contradicting the finite-memory reduction claimed for Proposition 1. If the authors intended T ≥ N, the correct resolution is to state that assumption explicitly before Proposition 1 and in Algorithm I; verifying that all subsequent claims, including the memory comparisons in Section VII, are restricted to that regime would settle the discrepancy.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 1's advertised finite-state reduction fails when the horizon T is shorter than the maximum deadline N. Definition 2 (Eq. 19) sets γ_i = 0 for every i > min(N,T), and Algorithm I loops only up to min(N,T) (line 4). Consequently, for such i, b_i^r = b_i, and Eq. (20) gives b_i^ℓ = max(0, b_i^r) = b_i. Hence every state s = (0,...,0, b_{T+1},...,b_N) is its own lean state, with arbitrary nonnegative trailing components; the set of lean states is infinite. For example, with N=2 and T=1, the states (0,k) for k=0,1,2,... are all lean. Lemma 1's Catalan count applies only to Definition 1 reduced states, but Algorithm I need not produce such states when TT, but the central claim that the DP need only be evaluated on a finite subset is false as stated. The paper either must assume T ≥ N explicitly or truncate the state space to components i ≤ T (which cannot affect the cost) and re-derive the lean-state construction on that truncated space.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a discrete-time mobile edge computing system in which tasks with firm deadlines arrive at a base station and can either be processed locally (at most one task per slot, with probability mu) or offloaded to a remote server whenever an Autonomous Mobile Agent (AMA) is present (probability p_a). The authors formulate a finite-horizon dynamic program for minimizing the expected time-average cost, composed of offloading costs and task-expiration penalties, and derive structural properties of the optimal policy: discrete convexity of the cost as a function of the number of offloaded tasks, a relation between optimal decisions at adjacent states, and a characterization of the optimal decision as the smallest number of offloaded tasks that reaches a non-offloading state. The main computational contribution is Proposition 1, which claims that the minimum cost of any state can be obtained from a finite set of \"lean states\" via a linear correction term (Eq. 22), and Algorithm II uses this reduction to compute the optimal policy. The paper also reports numerical experiments on optimal decision visualization, memory savings, and comparisons with threshold, expiry-driven, random, and on-the-spot baselines.","tokens_in":49171,"tokens_out":11419,"duration_ms":130331,"significance":"If the finite lean-state reduction were established for all T and N, the paper would make a solid, self-contained contribution: it would convert an infinite-state DP into a finite computation plus an algebraic correction, give a structured optimal policy, and provide appendices with proofs of the main theorems. The structural insights, such as adjacent-state inference and the threshold characterization of offloading, are nontrivial and could inform richer MEC models. The paper's self-contained nature is a strength, and the simulations are consistent with the theory in the regime T >= N used in the figures. However, the central finiteness claim is currently false as stated for T < N (see major comment 1), and the proof of the key separation property behind Proposition 1 is asserted rather than demonstrated (see major comment 2). Because these points are load-bearing, the paper is not yet acceptable in its present form, though the issues appear fixable by an explicit assumption or a truncated-state re-derivation.","major_comments":[{"comment":"The claimed finiteness of the lean state space fails when T < N. In Definition 2, gamma_i = 0 for every i > min(N,T), and Algorithm I loops only up to min(N,T) (line 4). Consequently, for such i, b_i^r = b_i and Eq. (20) gives b_i^ell = max(0, b_i^r) = b_i. Hence every state of the form (0, ..., 0, b_{T+1}, ..., b_N) is its own lean state; for example, with N = 2 and T = 1, the states (0,k) for k = 0,1,2,... are all lean, so the set is infinite. This contradicts the statement after Eq. (21) that the lean state space is finite, the memory argument for Algorithm II, and the memory-saving claims in Section VII-C, whose Fig. 7 only covers T >= N. The paper should either add an explicit T >= N assumption or truncate the state representation to min(N,T) components (tasks with deadline greater than T cannot affect the cost in Eq. (11)) and re-derive the lean-state construction and Eq. (21) on that truncated space.","section":"Section IV-B, Definition 2 and Algorithm I"},{"comment":"The proof of Proposition 1 assumes the key separation property it needs to prove. It asserts that the extra tasks d_i = b_i - b_i^ell are \"excessive tasks\" and \"should be offloaded by the optimal policy\" without showing from the transition law that these surplus tasks never change which non-excessive tasks are locally processed or offloaded. The case analysis in Eqs. (41)-(48) postulates that, under every realization, the remaining state of s after serving or expiring the surplus tasks is exactly the corresponding state of s^ell, plus the same arrivals and local service. If surplus tasks can occupy the local server or the offloading budget at a time when s^ell would serve a different task, Eq. (21) would not follow. A formal coupling or monotonicity argument is needed; as written, this is a gap in the central reduction.","section":"Appendix B, Eqs. (41)-(48)"},{"comment":"The domain of F(s,F) in Eq. (24) is inconsistent with the text immediately above it and with the appendix's L1(s) in Eq. (33). The text says that decisions F < b1 are removed because deadline-1 tasks are excessive; for b1 = 0 this set is empty. Yet Eq. (24) removes {0} through the term max(b1 - 1, 0). Consequently, Lemma 2's stated domain excludes the candidate F = 0 for states with b1 = 0, and Lemma 3 cannot hold for non-offloading states with b1 = 0. The correct domain appears to be L(s) \\ {0, ..., b1 - 1}, matching L1(s). The appendix proofs use L1(s), but the formal statement of Lemma 2 must be corrected.","section":"Section V-A, Eq. (24)"}],"minor_comments":[{"comment":"In the pseudocode, the stored quadruplet is written with horizon T rather than T - t; the surrounding text and Fig. 7 use the latter, so the pseudocode should be aligned with the description.","section":"Algorithm II, line 20"},{"comment":"The phrase \"convexity of cost functions proven in Subsec. VIII\" should refer to the relevant appendix section (Appendix C) or the main-text Section V-A, not \"Subsec. VIII.\"","section":"Appendix E"},{"comment":"Line 15 says \"Offloading F_r most imminent tasks from s(r)\"; as written this does not define s* correctly. It should state that s* is obtained by offloading F* = F_r + F_g most imminent tasks from the original state s.","section":"Algorithm II, line 15"},{"comment":"The claim that Eq. (21) extends to bulk task arrivals is stated without proof. If kept, the authors should either provide a proof or state precisely how the arrival process is modified and why the separation property remains valid.","section":"Remark 1"},{"comment":"The memory-saving experiments in Fig. 7 use T = 6, ..., 15 and N = 3, 4, 5, i.e., only the regime T >= N. The paper should state this limitation explicitly, or extend the experiments to T < N if the truncated-state fix is adopted.","section":"Section VII-C"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the T < N gap in the finite lean-state claim; I believe it is fixable by an explicit T >= N assumption or by truncating the state space to min(N,T) dimensions, so major revision rather than reject. The paper self-cites a conference version [24] of the same model and appropriately frames this work as the extended version with proofs. If the authors choose to assume T >= N, that assumption should be stated clearly in the model section and all subsequent claims adjusted. The simulations currently cover only T >= N, which masks the gap."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The paper gives a real structural result for a firm-deadline task offloading DP with an intermittent relay (AMA): the optimal cost satisfies a linear relation with respect to a finite set of 'lean' states, and the optimal decision is the smallest offload count that reaches a non-offloading state. The appendix proofs are mostly coherent and the model is self-contained. The second thing is that the finite lean-state claim is false as stated when the time horizon T is shorter than the maximum deadline N. Definition 2 sets γ_i = 0 for i > min(N,T), Algorithm I never modifies those components, so any state of the form (0,...,0, b_{T+1},...,b_N) is its own lean state. With N=2, T=1, the states (0,k) for all k are lean. Proposition 1's 'finite subset' statement and the Section VII memory-savings numbers therefore rely on an unstated assumption, likely T ≥ N or a truncation of the state space to the first min(N,T) components.\n\nThe fix is easy. Since tasks with deadlines beyond the horizon never affect the cost, one can either assume T ≥ N explicitly or truncate the state vector at min(N,T) and re-derive the lean-state construction on the truncated space. This does not seem to break the adjacent-state theorem or the offloading condition; those are independent of the finiteness claim.\n\nTwo smaller issues. Eq (24) removes F=0 when b1=0, contradicting the appendix's L1(s) and weakening Lemma 3 for states without deadline-1 tasks; the domain should be L(s) without the suboptimal decisions strictly below b1, i.e., keep 0 when b1=0. Eq (14) has a typo in the second expectation term (s'' instead of s'). Neither is fatal.\n\nWhat is genuinely new: the convexity of the cost in the offloading decision (Lemma 2), the off-by-one adjacent-state rule (Theorem 1), and the lean-state reduction (Proposition 1) go beyond the cited literature, including the authors' own conference version [24], which this paper extends with full proofs. The simulation figures are consistent with the structural claims, though no code or data is provided, so independent reproduction means reimplementing the DP.\n\nAudience: people working on MDP/DP methods for MEC offloading with deadlines and on state-space reduction for DP. It deserves a serious referee. I would send it out and ask for a major revision that fixes the T c_o$. The paper claims that the optimal policy has a crisp threshold form: offload the smallest number of most imminent tasks that makes the remaining state non-offloading, where a state is non-offloading exactly when removing the next most imminent task would change the optimal cost by less than $c_o$. The main structural result is that the infinite-state dynamic program collapses: every state's value equals its finite lean-state value plus a closed-form linear term (Proposition 1), so the DP needs to be solved only on finitely many lean states. If correct, this turns a seemingly intractable stochastic control problem into a finite computation plus an algebraic adjustment, with memory savings on the order of 95 to 98 percent in the paper's horizon-15 simulations.","feed_headline":"Optimal edge offloading: stop at the first non-offloading state","feed_subtitle":"Infinite state space shrinks to finitely many lean states plus a linear cost correction.","key_machinery":"The load-bearing objects are the reduced states and lean states. A reduced state is one with no excessive tasks, the tasks guaranteed to expire before local processing can reach them, and the number of reduced states is the Catalan number. A lean state $s^{(\\ell)}$ for a state $s$ is the finite representative that, under any AMA-free sequence of arrivals and local-service outcomes, reaches the same reduced state as $s$; the surplus tasks in $s$ are excessive and therefore act independently of the remaining tasks. The identity $V_T(s)=V_T(s^{(\\ell)})+C_\\ell$ (Proposition 1) carries the computational reduction, while discrete convexity of $F(s,F)=V^A_T(\\bar{s}_F)+F c_o$ and the adjacent-state relation convert the policy into a threshold: offload until the residual state is non-offloading, where non-offloading is checked by the difference condition of Proposition 2.","core_discovery":"On its own terms, the paper establishes that any state $s$ can be reduced to a finite lean state $s^{(\\ell)}$ by deleting tasks that are guaranteed to expire unless offloaded (excessive tasks), and that $V_T(s)=V_T(s^{(\\ell)})+C_\\ell$, with $C_\\ell$ a linear function of the surplus tasks (Eqs. 21–22). It then characterizes optimal decisions: for every state, the optimal number of tasks to offload is the smallest $F$ such that the state obtained by offloading the $F$ most imminent tasks is non-offloading (Theorem 2), and a state is non-offloading exactly when $V_T(s^{(a)})-V_T(s)