{"id":"4131fbce-31d8-4fb6-946a-408069c1ab7a","arxiv_id":"2502.05537","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"WS-option jointly learns budget allocation and node selection for sequential stochastic combinatorial optimization, outperforming fixed-allocation baselines on adaptive influence maximization and route planning and generalizing to larger graphs.","lead":"This paper introduces WS-option, a two-layer hierarchical reinforcement learning system that allocates a limited budget across time steps and then selects nodes at each step, for sequential stochastic combinatorial optimization. It is the kind of method that could make adaptive influence campaigns or epidemic interventions more efficient, and it reports strong results plus generalization to larger graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reported improvement over the strongest score-based baseline is small (best margins 0.43–1.19 in Table 1; 0.35 at n=1000 in Table 4), so the central 'significantly improved' claim cannot be assessed without the omitted per-run statistics.","rationale":"The reader's headline weakness is the wake-sleep similarity assumption. That is a real soft spot, but it attacks the theoretical convergence story, not the empirical claim that is the paper's main acceptance criterion: even if the assumption fails, wake-stage co-training could still produce a good policy, as the ablation in D.5 suggests. I therefore route my objection through statistical verifiability rather than through the convergence proof. The reader did note the missing error bars and code in the rationale, so my agreement is partial rather than complete. I considered the non-Markovian lower-layer reward in Eq. 4 as an alternative concern; it undermines Theorem 1 and the 'coherent MDP' claim, but it also does not directly falsify the empirical comparison. If the raw-data check above passes, the paper should still soften Theorem 2 or reclassify the convergence analysis as heuristic, keeping the verdict CONDITIONAL. My recommendation is UNCHANGED relative to the reader's CONDITIONAL verdict.","tokens_in":22881,"tokens_out":15019,"duration_ms":152356,"concrete_test":"Obtain the raw per-run rewards (or the code) behind Table 1 and Table 4, n=1000, and compute paired 95% confidence intervals and paired Wilcoxon tests for WS-option vs the best score-based baseline in each setting, reporting the number of seeds/runs per cell. If any CI includes 0, or the n=1000 effect size is <0.5 reward units with overlapping intervals, the 'significantly improved generalizability' claim at that size is not established. This single check settles whether the empirical headline survives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is empirical: WS-option 'exhibits significantly improved effectiveness and generalizability' compared with traditional methods. The strongest baselines are the score-based heuristics, yet the margins over the best baseline in each column are tiny: Table 1 gives 76.00 vs 74.81/74.36, 118.56 vs 118.13, 129.06 vs 128.29, and 80.95 vs 80.31 (best score-based baseline), i.e. 0.4%–1.7% relative differences. The generalization headline is even thinner at the largest tested size: Table 4, n=1000, shows WS-option at 221.16 vs average-score and normal-score both at 220.81, a 0.16% difference. Section 4.1 explicitly replaces standard deviations with t-tests, and Appendix C.5 describes the t-test rationale, but the paper never reports the number of seeds/runs, the actual p-values, or the standard errors behind 'p-values ≤ 0.05'. Because the effect sizes are so small, the significance claim — and hence the abstract's 'significantly improved' — is unverifiable as written. This is load-bearing: if the n=1000 difference is within noise, the paper's most striking generalization result collapses; if it is significant, the practical magnitude is under half a node, which does not support the advertised strength.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines sequential stochastic combinatorial optimization (SSCO) as a two-level problem in which a budget is allocated over time steps and a set of nodes is selected at each step. It proposes WS-option, a two-layer option-based hierarchical RL framework, with a wake-sleep training procedure, MC learning for the higher layer, TD learning for the lower layer, and brief convergence theorems. The method is evaluated on adaptive influence maximization and route planning, with ablation studies and tests on larger graphs and a real-world network. The central claim is that WS-option exhibits significantly improved effectiveness and generalizability over traditional methods.","tokens_in":23166,"tokens_out":6852,"duration_ms":71721,"significance":"The problem formulation is a useful and reasonably general way to expose the budget-allocation and node-selection coupling in SSCO, and the option-based hierarchical decomposition is a sensible design. The wake-sleep idea, the use of different learning updates per layer, and the ablations for sleep length and simplified options are worthwhile contributions. If the empirical claim were fully supported, the generalization to larger graphs would be a practical benefit. However, the current evidence for 'significantly improved' is incomplete: the reported margins over the strongest baselines are small, and the paper never gives the run counts, variances, test statistics, or actual p-values behind the blanket 'p-values ≤ 0.05' statements. The theoretical guarantees are also narrower and more assumption-dependent than the text suggests.","major_comments":[{"comment":"The central empirical claim is not verifiable from the reported numbers. The paper states 'All cases have p-values ≤ 0.05' but never reports the number of independent runs/seeds, standard errors, confidence intervals, test statistics, or the p-values themselves. This matters because the effect sizes are small: in Table 1 the largest advantage over the best score-based baseline is 1.19 out of 74.81 (about 1.6%), and in Table 4 at n=1000 the difference is 221.16 vs 220.81 (about 0.16%). Without per-run statistics, the reader cannot tell whether these differences are within stochastic noise, so the abstract's 'significantly improved effectiveness and generalizability' claim is unsupported as written. The authors should report the number of independent trials, the variance, and the p-values or confidence intervals for at least all headline tables.","section":"§4.1 and Tables 1–4, 7–8"},{"comment":"The lower-layer reward defined in Eq. (4) is not a well-posed per-action reward for the sequential decision process. The reward r^II_{t,v} = m_{t,v} / (Σ_{u∈a^II_t} m_{t,u}) · (r^I_t − r^II_{t,∅}) depends on the full lower-layer action set a^II_t and on the realized total reward r^I_t, both of which are known only after the complete node sequence for time step t has been executed. When Algorithm 2 selects nodes one by one (lines 8–13), the reward retrospectively assigned to an earlier node therefore depends on future choices and on the stochastic outcome of the whole step. The lower-layer transition is then not a Markov transition of the sort assumed in Theorem 1, and the contraction proof in Appendix A.5.1 does not apply to the algorithm as implemented. The sentence in §3.3 that scaling 'does not affect the relative Q value of the actions' is also not justified, because the normalizer varies with the action set and can change the ordering of Q-targets. The authors should either define a causal reward, or explicitly treat Eq. (4) as heuristic reward shaping and remove the convergence guarantee that relies on it.","section":"§3.2.2, Eq. (4)"},{"comment":"The joint convergence claim is not established. Theorem 2 assumes that for every higher-layer policy the lower-layer policy provides the conditionally optimal response, which is precisely the property that the wake-sleep procedure is supposed to deliver. Appendix A.2 adds a further assertion, 'the conditionally optimal lower-layer policy remains similar across different higher-layer policies πI', with no proof and no direct test. The wake-sleep design is load-bearing on this assumption: during the sleep stage the lower layer is trained under the average budget allocation, and during the wake stage it is co-trained with a learned higher-layer policy. If the conditionally optimal lower-layer policies are not similar across high-layer policies, the sleep-stage solution may be a poor initialization and the joint training may not converge. Table 9 only varies sleep duration; it does not test the similarity assumption. The framing of Figure 3 as a Stackelberg game is an analogy, not a proof. I recommend either proving the assumption under explicit conditions, testing it by training the lower layer to convergence under several fixed high-layer policies and comparing the resulting policies, or substantially weakening the convergence claim to match what is actually shown.","section":"§3.3.3, Theorem 2, and Appendix A.2"},{"comment":"The policy-assessment and ablation tables are reported as single point estimates. Table 9 explicitly says 'we use the same random seed as in 4.2', which suggests that at least some results come from a single seed. If that is true, the t-test language in Section 4.1 is internally inconsistent: a two-sample t-test requires a sample of runs, not a single trajectory. The authors should clarify how many seeds underlie each table and, if the ablations are single-seed, label them as illustrative rather than as significance-tested results.","section":"§4.3, Table 3 and Tables 9–10"}],"minor_comments":[{"comment":"The title contains a spelling error: 'Hierarchal' should be 'Hierarchical'; the abstract also has 'opitmization' instead of 'optimization' in one place.","section":"Title and abstract"},{"comment":"In the row 'normal-degree', the entry for (T,K=10,20) reads '101.50.34', which appears to be a typo for either 101.50 or 101.34; please correct it.","section":"Table 1"},{"comment":"There are several typographical errors, including 'transistions' in §3.3, 'repreat' in Appendix A.4.1, 'effiency' in Appendix A.1, and 'Vonference' in reference [22]. A careful proofreading pass is needed.","section":"Throughout"},{"comment":"The t-test rationale states that standard deviation mainly reflects aleatoric uncertainty, but a t-test still requires multiple independent runs to estimate the sampling distribution. The appendix should state the number of runs, the type of t-test (paired or unpaired), and how the stochastic environment is sampled across runs.","section":"Appendix C.5"},{"comment":"The two panels in Figure 2(b) are hard to interpret because the MC and TD plots are shown as separate small curves with no shared axis labels or legend; please provide full axis labels and a single linked figure or a table of the Q-value trajectories.","section":"Figure 2"}],"recommendation":"major_revision","confidential_remarks":"The paper has already appeared at ICLR 2025, but for a journal version the burden of evidence should be higher. The most serious issue is the gap between the strong 'significantly improved' claim and the absence of run-level statistics; the margins are small enough that even a directed reviewer cannot independently verify significance. The non-Markovian reward in Eq. (4) and the assumption-laden convergence theorems are also load-bearing and need to be repaired or explicitly reframed. I do not think the core idea is unsalvageable, but the revision must supply reproducible statistics and address the reward formulation and the convergence assumptions before the claims can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, what you should know: WS-option is a real, working combination of established ideas—two-layer option-based HRL for SSCO, with wake-sleep training and layer-wise MC/TD updates—and it consistently beats its baselines on adaptive IM and route planning, including a useful generalization result to larger graphs. But the headline claim that it \"significantly\" outperforms is not quite established as written, and the theory is thinner than the rest.\n\nWhat's genuinely new: adaptive budget allocation over time, rather than the uniform budget used in earlier work by Chen et al. and Ou et al. The two-layer MDP formulation is clean, the null action is a sensible piece of engineering, and the wake-sleep design—train the lower layer under a fixed average policy, then fine-tune jointly—is well motivated. The ablations (sleep duration, simplified option) support the core design choices. I believe the empirical wins are probably real in the sense that the framework learns something useful.\n\nThe first problem is statistical reporting. Every table says \"p-values ≤ 0.05,\" but we never get the number of seeds, standard deviations, or actual p-values. The margins over the best baseline are small: in Table 1, 76.00 vs. 74.81 (about 1.6%) and 118.56 vs. 118.13 (0.4%); in Table 4 at n=1000, 221.16 vs. 220.81 (0.16%). Without variance, \"significantly improved\" is unverifiable, and at the largest graph size the advantage is under half a node. That is load-bearing because the generalization headline depends on it. The result could still be significant; the paper simply does not show it.\n\nThe second problem is theory. Theorem 2 assumes the lower layer is conditionally optimal to get higher-layer convergence, and joint convergence is argued via a Stackelberg analogy plus an untested similarity claim in Appendix A.2. The lower-layer reward in Eq. 4 is also troublesome: the reward for selecting node v depends on all nodes selected in that time step through the normalization sum, so when the first node is chosen its reward is not known until the full set is picked. That is non-causal and potentially non-Markovian, and the paper does not address it.\n\nThe \"first to define SSCO\" claim overstates the departure from the earlier works; the real novelty is the adaptive budget allocation, not the problem class itself.\n\nWho this is for: anyone working on RL for combinatorial optimization, especially adaptive influence maximization or budget allocation. It deserves a serious referee, though it needs substantial revision—code, seeds, error bars or real p-values, and a more honest discussion of the theory's limits. I would bring it to a reading group to debate these issues, but I would not cite it in its current form.","headline":"WS-option is a genuine and sensible combination of HRL ideas for non-uniform budget allocation in sequential stochastic CO, but its 'significantly improved' claim rests on thin margins with unreported variance, and the theory section is mostly assertion.","tokens_in":23712,"tokens_out":3074,"would_cite":false,"duration_ms":29799,"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":"WS-option jointly learns budget allocation and node selection for sequential stochastic combinatorial optimization, beating uniform-allocation baselines and transferring from 50-node training graphs to 1000-node graphs.","keywords":["hierarchical reinforcement learning","option framework","sequential stochastic combinatorial optimization","budget allocation","node selection","adaptive influence maximization","route planning","wake-sleep training"],"falsifier":"Train the lower-layer node-selection policy to convergence under several deliberately different budget-allocation policies—all budget on the first day, uniform across days, all budget on the last day—and measure how often the resulting policies choose different nodes in the same state. If they disagree substantially, the similarity assumption behind wake-sleep training is violated; conversely, if joint training from scratch reaches the same final reward as wake-sleep training on a hard instance, the schedule's claimed stabilising role is not essential to the result.","tokens_in":22635,"feed_emoji":"🧠","tokens_out":14644,"duration_ms":138489,"temperature":0.7,"pith_summary":"The paper takes on a class of optimization problems it calls sequential stochastic combinatorial optimization: a fixed budget must be spread over a time horizon, and at each step a set of nodes or cities is chosen, with rewards that are random and partly revealed only as decisions unfold. It claims that the few existing reinforcement-learning treatments of these problems settle for a uniform budget split, which is suboptimal, and that the right structure is a two-layer hierarchy. The proposed WS-option framework learns a budget-allocation policy on the higher layer and a node-selection policy on the lower layer, with the two layers coupled through a shared time-step reward and stabilized by a wake-sleep training schedule. The payoff, if the claims hold, is that one agent trained cheaply on small graphs supplies both levels of the decision for large problem instances: the paper reports better cumulative rewards than hand-designed baselines on adaptive influence maximization and route planning, and successful use of a model trained on 50–100 node graphs at sizes up to 1000 nodes.","feed_headline":"Two-layer RL beats uniform-budget planners on sequential optimization","feed_subtitle":"Joint budget-and-node learning wins on influence spread and route planning, scaling to 1000-node graphs.","key_machinery":"The load-bearing object is the two-layer Markov decision process pair connected by a reward-alignment identity: at each time step the higher layer chooses a budget option $o^I_t = K_t$ and the lower layer selects nodes one at a time, and the lower-layer rewards are scaled marginal rewards $r^{II}_{t,v} = \\frac{m_{t,v}}{\\sum_{u \\in a^{II}_t} m_{t,u}}(r^I_t - r^{II}_{t,\\emptyset})$ so that $\\sum_u r^{II}_{t,u} + r^{II}_{t,\\emptyset} = r^I_t$; the layers therefore optimize exactly the same objective. Around this identity the paper builds three stabilising devices: a wake-sleep training schedule (sleep: freeze the higher layer at an average budget allocation and train the lower layer, then pre-train the higher layer offline on those trajectories; wake: train both layers jointly), a layer-wise learning-method split (Monte Carlo returns for the unbiased higher-layer Q-function, TD/Q-learning for the faster-converging lower layer), and a binary continuation option $o^{II}_t \\in \\{0,1\\}$ with a null action, so the lower layer only needs to know whether to keep selecting nodes rather than the exact budget value. The network also uses an action-in structure for the higher layer so that budget size is an input, not an output layer, which is what lets a model trained on small graphs be evaluated on arbitrarily larger ones.","core_discovery":"On the paper's own terms, the central discovery is that the SSCO problem—maximize $\\sum_{t=1}^T r_t(S_t)$ subject to $\\sum_t K_t \\leq K$ and $|S_t| \\leq K_t$—is a bi-level optimization, and that a hierarchical value-based agent can solve it stably instead of flattening it into one giant Markov decision process. WS-option treats the per-time-step budget $K_t$ as a higher-layer option and the per-step node set $S_t$ as a sequence of lower-layer actions, and the two layers are trained so that the lower layer's rewards at each time step sum exactly to the higher layer's reward, keeping both levels optimizing the same objective. The paper further claims that its wake-sleep schedule—first training the lower layer under a frozen average budget policy, then fine-tuning both layers together—avoids the divergent Q-value estimates it observes when the layers are trained jointly from scratch, and its two convergence theorems establish Q-learning convergence for each layer in the tabular case assuming the other layer is fixed or optimally responsive. The reported empirical result is that this agent outperforms the average, static, and normal budget policies with degree- or score-based node selection on adaptive influence maximization, and greedy and genetic-algorithm planners on route planning, with all reported differences at $p \\leq 0.05$; it also reports that the learned policies generalize to graphs up to 1000 nodes and to a 2500-node real-world power-grid network.","pith_inferences":["Editorial inference — the reward-alignment identity is a generic credit-assignment recipe: any hierarchical agent that must distribute one aggregate time-step reward across many primitive actions could reuse it, with the marginal contribution of each action estimated by simulation, not just in the two problem instances studied here.","Editorial inference — the paper's convergence proof is explicitly limited to tabular Q-learning, so an untested question is whether the wake-sleep schedule keeps the function-approximation case stable in regimes beyond the reported $T \\le 20$, $K \\le 30$ settings, such as very long horizons or budgets large relative to the graph.","Editorial inference — the comparison set does not include a flat RL baseline that learns budget allocation and node selection as a single joint MDP; testing whether the hierarchy is genuinely necessary rather than merely convenient is an open comparison the paper does not run.","Editorial inference — the paper's own stated limitation is that each new problem class needs its own graph embedding technique; a testable consequence of its design is that the wake-sleep schedule and the reward-alignment identity, rather than the specific embedding, are what carry the performance gains."],"forward_implications":["Uniform budget allocation over the time horizon is suboptimal for sequential stochastic combinatorial optimization; an adaptive budget policy learned jointly with node selection yields higher cumulative reward on adaptive influence maximization and route planning in the reported experiments ($p \\leq 0.05$).","A model trained on graphs of 50–100 nodes transfers to unseen graphs of 200–1000 nodes and to a 2500-node power-grid network without retraining, because the learned networks contain no graph-size-dependent parameters.","The lower layer's node-selection policy and the higher layer's budget-allocation policy each contribute independently to the gain: holding one layer fixed at its learned policy while swapping the other for a baseline still favors the learned policy.","The wake-sleep schedule matters: an ablation shows that shortening the sleep stage so the lower layer has not converged (one third of the epochs) degrades final performance, while half and two thirds of the epochs give nearly identical results.","Using Monte Carlo returns for the higher layer instead of TD bootstrapping prevents the monotone Q-value inflation the paper observes for TD in this coupled setting."],"supporting_citations":[{"why":"Supplies the option framework (temporally extended actions) that the two-layer budget/node hierarchy is built on.","marker":"[47]"},{"why":"Defines the time-constrained adaptive influence maximization problem and the average/static/normal budget baselines used in the experiments.","marker":"[48]"},{"why":"Provides the stochastic-approximation convergence theorem used to prove both layers' Q-functions converge.","marker":"[21]"},{"why":"Supplies the graph-embedding and value-based RL approach that the lower layer and the adaptive influence maximization network follow.","marker":"[24]"},{"why":"Earlier RL solution to adaptive influence maximization that assumes a uniform budget allocation, the limitation the paper targets.","marker":"[10]"},{"why":"Earlier RL solution to medical resource allocation that also assumes uniform budgets, the other existing SSCO-RL work.","marker":"[41]"},{"why":"Formalizes the influence-maximization model that the adaptive influence maximization instance extends.","marker":"[23]"}],"fun_headline_variants":["Two-layer RL allocates budgets and picks nodes jointly, beating fixed plans","Wake-sleep RL tunes budget and node choices, beating uniform-budget baselines","Two-layer agent learns budget and node selection for sequential stochastic CO","RL that jointly decides budget and nodes surpasses static planners","Wake-sleep hierarchical RL tunes budgets and nodes, beating uniform-budget"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole wake-sleep design rests on the claim, stated explicitly in Appendix A.2, that the best node-selection policy is roughly the same no matter how the budget is spread across time steps: if that similarity fails, the lower-layer policy learned in the sleep stage is a poor starting point and nothing guarantees the two layers converge jointly.","fun_headline_variants_meta":{"raw":{"variants":["Two-layer RL allocates budgets and picks nodes jointly, beating fixed plans","Wake-sleep RL tunes budget and node choices, beating uniform-budget baselines","Two-layer agent learns budget and node selection for sequential stochastic CO","RL that jointly decides budget and nodes surpasses static planners","Wake-sleep hierarchical RL tunes budgets and nodes, beating uniform-budget"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000747,"raw_usage":{"total_tokens":3417,"prompt_tokens":1125,"completion_tokens":2292,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":741,"completion_tokens_details":{"reasoning_tokens":2199}},"tokens_in":741,"tokens_out":2292,"duration_ms":14761,"temperature":1.0,"reasoning_tokens":2199,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T18:55:24.883557+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train the lower-layer node-selection policy to convergence under several deliberately different budget-allocation policies—all budget on the first day, uniform across days, all budget on the last day—and measure how often the resulting policies choose different nodes in the same state. If they disagree substantially, the similarity assumption behind wake-sleep training is violated; conversely, if joint training from scratch reaches the same final reward as wake-sleep training on a hard instance, the schedule's claimed stabilising role is not essential to the result.","supporting_citations":[{"cited_title":"Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning","cited_arxiv_id":null,"evidence_quote":"Supplies the option framework (temporally extended actions) that the two-layer budget/node hierarchy is built on."},{"cited_title":"Time-constrained adaptive influence maximization","cited_arxiv_id":null,"evidence_quote":"Defines the time-constrained adaptive influence maximization problem and the average/static/normal budget baselines used in the experiments."},{"cited_title":"Convergence of stochastic iterative dynamic programming algorithms","cited_arxiv_id":null,"evidence_quote":"Provides the stochastic-approximation convergence theorem used to prove both layers' Q-functions converge."},{"cited_title":"Learning combinatorial optimization algorithms over graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the graph-embedding and value-based RL approach that the lower layer and the adaptive influence maximization network follow."},{"cited_title":"Contingency-aware influence maximization: A reinforcement learning approach","cited_arxiv_id":null,"evidence_quote":"Earlier RL solution to adaptive influence maximization that assumes a uniform budget allocation, the limitation the paper targets."},{"cited_title":"Active screening for recurrent diseases: A reinforcement learning approach","cited_arxiv_id":null,"evidence_quote":"Earlier RL solution to medical resource allocation that also assumes uniform budgets, the other existing SSCO-RL work."},{"cited_title":"Maximizing the spread of influence through a social network","cited_arxiv_id":null,"evidence_quote":"Formalizes the influence-maximization model that the adaptive influence maximization instance extends."}],"review_version":1}