{"id":"918766a9-9d5f-4bef-b46c-0d1702fafb31","arxiv_id":"2509.06147","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An additive allocation procedure for distributionally robust ranking and selection is proven consistent, with only k+m-1 scenarios sampled infinitely often as the budget grows.","lead":"Distributionally robust ranking and selection can be made consistent by a greedy procedure that samples only k+m-1 of the k*m scenarios forever. The paper proves this, and shows the scenario of a losing alternative that gets sampled forever need not be its worst-case scenario.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's proof of additivity relies on a false dominance claim: a lower tail minimum does not prevent re-selection by the greedy max-sampling k-step.","rationale":"The reader's identified weakest assumption is a modeling premise (δ>0) that is explicit and standard in R&S, so it is not a correctness risk. My stress-test found a more serious issue: an internally false proof step in the central additivity theorem. The greedy k-step selects the scenario with the maximum current sample mean; the proof instead reasons with tail minima and asserts that once a scenario reaches its minimum it will never be selected again. That assertion is false, and it is exactly the step that implies the almost-sure bound on the number of scenarios sampled infinitely often. Because Theorem 2 is the paper's strongest and most counterintuitive claim, and because Theorem 4 extends it to the GAA framework, the paper's central contribution is not fully supported by the provided proofs. The numerical experiments are consistent with the claimed behavior, but they cannot settle an almost-sure asymptotic statement. The appropriate disposition is conditional acceptance: the additivity theorems should carry a rigorous proof, or the claims should be weakened accordingly.","tokens_in":55158,"tokens_out":12410,"duration_ms":121457,"concrete_test":"Simulate the pure greedy k-step for one non-best alternative with two scenarios, both N(0.5,1), starting with one observation each; at each step sample the scenario with the larger current sample mean. For each scenario, record the index n* where its sample-mean process attains its running minimum, and the total number of observations allocated to it. After a long horizon (e.g., 10^7 steps), check whether the total allocations exceed n*. The proof's 'key observation' asserts this cannot happen; if any replication shows n_total > n*, that claim is falsified. As a secondary check, run the full AA procedure with k=2, m=2, μ_11=0, μ_21=μ_22=0.5 over the same horizon and see whether both scenarios of alternative 2 receive more than 10^6 observations; Theorem 2 predicts this occurs with probability zero.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The reader's weakest assumption (δ>0) is explicit and standard; my concern is internal to the proof of Theorem 2 in EC.1.5.2. After bounding the m-steps of a non-best alternative i, the proof analyzes the pure greedy k-step, which samples the scenario with the current maximum sample mean. It defines Ω^<_{ijl} = {min_{n≥n_ij(t_i)} X̄_ij(n) < min_{n≥n_il(t_i)} X̄_il(n)} and claims: 'once (i,j) reaches its minimum sample mean, it will be dominated by (i,l) and no longer selected by the greedy k-step.' This is not true for max-selection: a scenario can attain its running minimum at one sample size and later have a current sample mean above the other scenario, so it is selected again. Concretely, if scenario j's sample-mean path is 0.5, -1.0 (minimum), 1.0 at successive sample sizes while scenario l's current mean is 0.4, j is the maximum and is sampled after its minimum. Consequently the inclusion leading to Eq. (EC.1.30) — n^k_ij(t) ≤ argmin_{n≥n_ij(t_i)} X̄_ij(n) — is unsupported, and the conclusion Pr(lim n_ij = lim n_il = ∞) = 0 does not follow. Since Theorem 2 is the paper's headline additivity claim and Theorem 4 inherits it, the central claim currently lacks a valid proof.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies fixed-budget distributionally robust ranking and selection (DRR&S) with k alternatives and m scenarios per alternative. It proposes an additive allocation (AA) procedure that, in each round, samples all m scenarios of the current empirical best alternative and the current empirical worst-case scenario of each other alternative, and finally selects the alternative that has been named best most often. The central theoretical claims are: (i) a finite-time lower bound on PCS via last-exit-time boundary-crossing arguments (Lemma 2); (ii) exponential decay of the probability of incorrect selection (Proposition 1), implying consistency (Theorem 1); (iii) an almost-sure additivity result stating that as the budget grows, exactly k+m-1 scenarios are sampled infinitely often (Theorem 2); and (iv) a result that the true worst-case scenario of a non-best alternative need not be among the infinitely sampled scenarios (Theorem 3). The paper then generalizes AA to a GAA framework allowing modular plug-in sampling rules (e.g., KG, TTTS) and claims consistency and additivity under sufficient exploration conditions (Theorems 4 and 5). Numerical experiments on synthetic and practical problems support the qualitative predictions.","tokens_in":55484,"tokens_out":6333,"duration_ms":58030,"significance":"If the main theorems are correct, the paper delivers a striking and useful message: consistency in DRR&S does not require all km scenarios to be sampled infinitely often, and the identity of the infinitely sampled scenario for each non-best alternative can be random and need not be the true worst case. This challenges a prior belief in the DRR&S literature and gives a theoretical basis for additive allocation. The boundary-crossing derivation is refreshingly parameter-free: no fitted constants enter the PCS bound, and the results yield falsifiable predictions that are directly examined in the numerics. The GAA framework is a constructive design principle. However, the proof of Theorem 2, which underpins the headline additivity claim, contains a false dominance assertion; since Theorem 4 inherits the same argument, the central contribution is currently not rigorously established.","major_comments":[{"comment":"The proof of Theorem 2 contains an unsupported dominance claim. After the event Ω^<_{ijl} = {min_{n≥n_ij(t_i)} X̄_ij(n) < min_{n≥n_il(t_i)} X̄_il(n)} is introduced, the proof states that once (i,j) reaches its minimum sample mean it will be dominated by (i,l) and no longer selected by the greedy k-step. This is false for the k-step, which selects the scenario with the current maximum sample mean, not the one with the smaller tail minimum. A scenario can attain its running minimum and later have a current sample mean above the other scenario: for example, with sample-mean paths X̄_ij = 0.5, -1.0, 1.0 and X̄_il = 0.4, scenario j is selected again after its minimum. Consequently the inclusion n^k_ij(t) ≤ argmin_{n≥n_ij(t_i)} X̄_ij(n) leading to Eq. (EC.1.30) is invalid, and Pr(lim n_ij = lim n_il = ∞) = 0 is not established. Since Theorem 2 is the paper's central additivity claim and Theorem 4 inherits its proof, this gap is load-bearing and must be repaired, or the claims should be weakened accordingly.","section":"EC.1.5.2, Eq. (EC.1.30)"},{"comment":"Lemma 3 and Lemma EC.7 are not proved within this manuscript despite statements that their proofs are included; the derivations invoke Lemma 3 of Li et al. (2025a) and Lemma 2 of Li et al. (2025b) from co-authored prior work. These lemmas directly support Proposition 1/Theorem 1 and Theorems 3/5, so the paper is not self-contained at load-bearing points. The authors should either provide full self-contained proofs of these tail bounds or state the external results verbatim with verifiable references, since the cited papers may not be accessible to readers.","section":"EC.1.1 and EC.1.6"}],"minor_comments":[{"comment":"The figures appear in the manuscript with garbled glyph placeholders (e.g., strings beginning with \"/uni00000014/uni00000013/...\") in place of axis labels and legends, making them unreadable; the figures should be regenerated with properly embedded text and fonts.","section":"Figures 2-5 and EC.1"},{"comment":"The text states that enumerating s ∈ {240,260,280,300,320,340} and S ∈ {350,370,390,410,430,450} yields 18 feasible policies; with six reorder points and six order-up-to levels and the constraint s < S, the number of feasible policies is 15, so the stated count should be checked.","section":"Section 6.3.2, Inventory Management"},{"comment":"Step 4 contains a typo: \"for each alternative i, \\hat b, set r^k_i ← r^k_i + 1\" should read \"for each alternative i ≠ \\hat b\".","section":"Procedure 2, Step 4"},{"comment":"The claim that the ε-greedy modification guarantees Assumptions 1 and 2 is asserted but not proved; since the formal results are conditional on these assumptions, the authors should add a short argument that ε-exploration yields infinite exploration almost surely whenever the relevant counter grows without bound.","section":"Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"The false dominance claim in the proof of Theorem 2 is a genuine technical error, not a presentation issue. The paper's headline contribution depends on this theorem, so the authors need to supply a correct proof or explicitly narrow the claim. I would not recommend rejection because the result may well be salvageable and the overall framework is valuable, but the current manuscript cannot be accepted as is. I also suggest that the editor ask the authors to make the external last-exit-time lemmas self-contained, as the EC currently gives the impression of proof while deferring to co-authored papers."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know the headline before reading: the paper's consistency analysis (Lemmas 1–2, Proposition 1, Theorem 1) appears sound and is a real contribution, but the proof of the main additivity theorem (Theorem 2) has a load-bearing flaw. The stress-test note lands.\n\nWhat is actually new: the paper gives the first rigorous consistency guarantee for an additive DRR&S procedure, proves exponential PICS decay, and shows that the true worst-case scenario of a non-best alternative can be sampled only finitely often. The boundary-crossing framework is clean, and the numerical experiments support the qualitative claims. That is worth taking seriously.\n\nThe soft spot is in EC.1.5.2. The proof claims that once scenario (i,j) reaches its minimum sample mean, it is dominated by (i,l) under greedy max-sampling. That is not true: the k-step samples the scenario with the current maximum sample mean, and after (i,j) hits its tail minimum, its sample mean can climb again and exceed (i,l)'s current mean. The stress-test example (0.5 → -1.0 → 1.0 versus a fixed 0.4) is a valid counterexample to the dominance claim. As a result, the key inclusion n^k_ij(t) ≤ argmin_{n≥n_ij(t_i)} X̄_ij(n) is unsupported, and the conclusion Pr(lim n_ij = lim n_il = ∞) = 0 does not follow from the given argument. Theorem 4 inherits this gap.\n\nThis is not a minor issue: Theorem 2 is the paper's central surprise, and the proof as written does not establish it. The δ > 0 assumption the reader flags is explicit and standard, and I do not see a problem there. The GAA assumptions are clearly stated, though verifying Assumptions 1 and 2 for adaptive rules may be nontrivial. Relying on two co-authored prior papers for tail bounds is acceptable if those lemmas are correct; I would ask the authors to reproduce or pinpoint them.\n\nWho should read this: simulation/OR researchers working on R&S under input uncertainty. The consistency and exponential-decay results are useful even if additivity remains open. My recommendation: send it to peer review, but with a request for a major revision. The authors need to repair Theorem 2's proof or state the additivity claim as a conjecture supported by numerics. A referee who understands greedy allocation and last-exit times should be asked to check the revised argument carefully.","headline":"Consistency and PICS decay are solid, but Theorem 2's additivity proof has a genuine gap: the greedy k-step can re-select a scenario after its running minimum, so the claimed dominance argument and the key inclusion do not hold.","tokens_in":55965,"tokens_out":3137,"would_cite":false,"duration_ms":31093,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F07","62L10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Distributionally robust selection needs infinite samples on only $k+m-1$ scenarios, not all $km$ scenarios.","keywords":["ranking and selection","input uncertainty","distributionally robust optimization","additivity","consistency","budget allocation","boundary crossing","probability of correct selection"],"falsifier":"Simulate the AA procedure on a small instance, say $k=2$, $m=2$, with normal outputs and a chosen gap $\\delta>0$; count, over many replications, how many scenarios have final sample sizes that keep growing with $N$ and whether the true worst-case scenario of the non-best alternative is among them. Theorem 2 predicts the count converges to $k+m-1=3$ and Theorem 3 predicts the worst-case scenario is excluded with positive probability; observing two or more infinitely sampled scenarios per non-best alternative, or zero probability of excluding the worst-case scenario, would refute the claims. A second probe is to set $\\mu_{21}=\\mu_{11}$ and check that the PCS of AA does not tend to one, which would confirm that the positive-gap assumption is load-bearing.","tokens_in":54938,"feed_emoji":"🎯","tokens_out":8985,"duration_ms":72259,"temperature":0.7,"pith_summary":"Distributionally robust ranking and selection (DRR&S) asks which of $k$ simulated alternatives has the smallest worst-case mean when the input distribution is uncertain, with $m$ plausible input distributions forming $km$ scenarios. The paper establishes that consistency—choosing the true best with probability approaching one as the sampling budget grows—does not require eventually sampling all $km$ scenarios. The proof runs through a greedy additive allocation (AA) procedure that each round samples only the current best alternative's $m$ scenarios and the current empirical worst-case scenario of every other alternative. For this procedure the probability of incorrect selection decays exponentially and, almost surely, exactly $k+m-1$ scenarios are sampled infinitely often as the budget tends to infinity. The paper also shows that the infinitely sampled scenario of a non-best alternative need not be its true worst-case scenario, which reframes which scenarios are actually critical.","feed_headline":"Greedy robust selection needs infinite samples on k+m−1 scenarios","feed_subtitle":"Consistency survives while every other scenario of the km gets sampled only finitely often.","key_machinery":"The central object is the last exit time of a scenario's sample-mean process: $U_{1j}(b)=\\sup\\{n\\ge1:\\bar X_{1j}(n)\\ge b\\}$ for scenarios of the best alternative and $L_{ij}(b)=\\sup\\{n\\ge1:\\bar X_{ij}(n)\\le b\\}$ for scenarios of non-best alternatives, with $b$ inside the gap $(\\mu_{11},\\mu_{21})$. These random times are finite almost surely and have exponentially decaying tails, and they bound how often the greedy $m$-step can select a non-best alternative and how often the $k$-step can act while the best's worst-case sample mean is above the threshold. The proof then uses a greedy-switching property: once the finitely many $m$-steps of a non-best alternative are exhausted, its $k$-step sampling tracks the current empirical worst-case scenario, and a convergent sample-mean process cannot switch between two scenarios infinitely often once one attains its tail minimum. This is what forces exactly one scenario per non-best alternative to be sampled forever.","core_discovery":"The central claim is an exact asymptotic identity for the AA procedure: almost surely, as the total budget $N\\to\\infty$, the number of scenarios sampled infinitely often is exactly $k+m-1$—all $m$ scenarios of the true best alternative plus exactly one scenario per non-best alternative—and this is enough for the probability of correct selection to converge to one. The finite-time engine is a lower bound on the PCS expressed through last exit times of sample-mean processes across a threshold $b_\\delta\\in(\\mu_{11},\\mu_{21})$; this bound gives exponential decay of the error probability. The additivity result is stronger than prior conjectures in that the single infinitely sampled scenario of a non-best alternative is random and may, with positive probability, be a non-worst-case scenario, so consistency does not require identifying or even estimating the true worst-case mean of a losing alternative. The same pair of guarantees—consistency and exact additivity—is extended to the general additive allocation (GAA) class whenever the modular $m$-step and $k$-step rules satisfy sufficient-exploration conditions.","pith_inferences":["If exact additivity is a property of the DRR&S problem rather than of the AA procedure, then the asymptotic design goal for robust selection should be keeping each non-best alternative's worst-case sample mean above a guide rail set by the best alternative, not identifying worst-case input distributions; this suggests simpler heuristics than OCBA-style critical-scenario allocation.","A testable extension: take the AA procedure with $k=10$, $m=5$ under the monotone-means configuration, record the label of the infinitely sampled scenario for each non-best alternative, and compare the empirical frequency with which the true worst-case scenario is excluded against the positive lower bound of Theorem 3.","The same boundary-crossing machinery might carry over to ambiguity sets with infinitely many distributions, since the exponential tail bound only needs the separating threshold between the best and second-best worst-case means; the paper leaves that extension open.","For practitioners, the implication is that robustness against input uncertainty does not demand heavy estimation of each worst-case distribution; sampling effort is better spent separating the best alternative from its most dangerous challenger under the worst-case lens."],"forward_implications":["The AA procedure is consistent: as $N\\to\\infty$ the PCS tends to one, with the probability of incorrect selection decaying exponentially, despite the allocation being greedy and restricted to current critical scenarios.","Almost surely only $k+m-1$ scenarios are sampled infinitely often; all other $km-(k+m-1)$ scenarios are sampled finitely many times even though the procedure remains consistent.","For every non-best alternative, the one scenario sampled forever is random and can be a non-worst-case scenario with strictly positive probability, so identifying the worst-case scenario is not a prerequisite for correct selection.","Any GAA procedure whose $m$-step and $k$-step rules satisfy sufficient exploration inherits both consistency and exact additivity, allowing standard R&S rules such as KG and TTTS to be reused without losing guarantees.","The finite-time PCS lower bound in Lemma 2 makes the error probability explicitly exponential in the budget, so larger budgets buy exponentially better confidence for a fixed problem instance."],"supporting_citations":[{"why":"Supplies the additive PICS upper bound and the $k+m-1$ critical-scenario set whose structure the AA procedure tries to realize.","marker":"Fan et al. (2020)"},{"why":"Proposes OCBA for DRR&S and first observes that the budget concentrates on $k+m-1$ scenarios, the heuristic claim AA makes rigorous.","marker":"Gao et al. (2017b)"},{"why":"Gives the AR-OCBA procedure and numerical evidence that concentrated allocation may land on non-critical scenarios, motivating the paper's Questions 2 and 3.","marker":"Wan et al. (2025)"},{"why":"Argues that worst-case mean estimation is central; Theorem 3 of this paper directly challenges that stance.","marker":"Wan et al. (2023)"},{"why":"States the conventional consistency requirement that all alternatives be sampled infinitely often, which Theorem 2 overturns in the DRR&S setting.","marker":"Hong et al. (2021)"},{"why":"Supplies the TTTS sampling rule instantiated as GAA-TTTS, whose exploration behavior is used to verify Assumptions 1 and 2.","marker":"Russo (2020)"},{"why":"Supplies the KG sampling rule instantiated as GAA-KG within the modular GAA framework.","marker":"Frazier and Powell (2008)"},{"why":"Provides the exponential tail bound for last exit times (Lemma 3) that the PICS decay and consistency proof use.","marker":"Li et al. (2025a)"},{"why":"Provides the probability bound for last exit times being zero (Lemma EC.7) used in the positive-probability statement of Theorem 3.","marker":"Li et al. (2025b)"}],"fun_headline_variants":["Robust ranking: infinite samples only on k+m−1 scenarios","Additivity proven: k+m−1 scenarios suffice for robust selection","Surprise: worst-case scenarios may not get infinite samples","Exact additivity: consistency with k+m−1 critical scenarios","Only k+m−1 scenarios sampled infinitely; consistency holds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The theory requires a strictly positive gap $\\delta=\\mu_{21}-\\mu_{11}$ between the worst-case means of the best and the second-best alternative, with the best alternative unique; if the gap is zero or the best is tied, the PCS lower bound and the consistency proof no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["Robust ranking: infinite samples only on k+m−1 scenarios","Additivity proven: k+m−1 scenarios suffice for robust selection","Surprise: worst-case scenarios may not get infinite samples","Exact additivity: consistency with k+m−1 critical scenarios","Only k+m−1 scenarios sampled infinitely; consistency holds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000771,"raw_usage":{"total_tokens":3475,"prompt_tokens":1068,"completion_tokens":2407,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":684,"completion_tokens_details":{"reasoning_tokens":2320}},"tokens_in":684,"tokens_out":2407,"duration_ms":15252,"temperature":1.0,"reasoning_tokens":2320,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:19:55.583002+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the AA procedure on a small instance, say $k=2$, $m=2$, with normal outputs and a chosen gap $\\delta>0$; count, over many replications, how many scenarios have final sample sizes that keep growing with $N$ and whether the true worst-case scenario of the non-best alternative is among them. Theorem 2 predicts the count converges to $k+m-1=3$ and Theorem 3 predicts the worst-case scenario is excluded with positive probability; observing two or more infinitely sampled scenarios per non-best alternative, or zero probability of excluding the worst-case scenario, would refute the claims. A second probe is to set $\\mu_{21}=\\mu_{11}$ and check that the PCS of AA does not tend to one, which would confirm that the positive-gap assumption is load-bearing.","supporting_citations":[{"cited_title":"2023 Winter Simulation Conference (WSC), 3647--3656 (IEEE)","cited_arxiv_id":null,"evidence_quote":"Argues that worst-case mean estimation is central; Theorem 3 of this paper directly challenges that stance."}],"review_version":2}