{"id":"0a0774c9-7df6-4977-a2d9-dabf89270fa1","arxiv_id":"2412.03860","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A framework based on cost amortization and local approximation gives constant-factor approximation algorithms for combinatorial selection with costly information under matroid constraints.","lead":"This paper introduces a general framework for designing approximation algorithms for stochastic selection problems where learning each option's value is a costly, multi-step process. It yields new approximation guarantees for several Pandora's-box-style problems, including the first efficient policy for matroid-constrained optional-inspection boxes that beats the trivial 0.5 ratio.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.4's lower-bound proof has an unjustified acceptance-weighted step; if it fails, the composition theorem and all application bounds collapse.","rationale":"The reader identified action independence (Lemma 3.5) as the most fragile assumption. I agree that the amortization framework is the critical core, but I locate the concrete gap slightly later: even granting action independence, the proof of Theorem 3.4's lower bound passes from an unconditional inequality E[W*_{Mπ}] ≥ E[W*_M] to an acceptance-weighted inequality E[X·W*_{Mπ}] ≥ E[X·W*_M] without justification. X is a stopping rule on the trajectory and can be correlated with the surrogate costs, so the unconditional dominance does not imply the weighted version. The non-negativity of bπ in Lemma 3.5 is also not established; the construction gives bπ_{στ} = E[ρπ(τ)] − E[ρπ|s(τs)], which can be negative. The paper's main composition theorem and all application results depend on this lower bound. I do not claim the theorem is false — a more careful coupling argument may rescue it — but the proof as written is incomplete. This warrants the paper remaining conditional pending a rigorous derivation or a counterexample. The reader's weakest assumption is related but distinct; hence partial agreement. I credit the paper for the clearly correct Markov-chain theory (Theorem 3.2) and the careful local-approximation composition proof in Appendix E, but the MDP lower bound needs additional scrutiny.","tokens_in":56782,"tokens_out":36638,"duration_ms":402412,"concrete_test":"Re-derive Claim 4 with an explicit coupling between the water-filling surrogate ρ*(τ) of Mπ and the action-independent amortized cost E[ρπ(τ)] from Lemma 3.5. Concretely: for the two-action MDP of Example 1, take commitment π=a1, compute for each terminal t the values ρ*(t) (water-filling surrogate of M1) and E[ρπ(t)] (from the lemma's construction), and test whether any subset A of terminals satisfies E[1_A·ρ*] < E[1_A·E[ρπ|τ]]. If such A exists, the acceptance-weighted inequality in Claim 4 fails and Theorem 3.4 is false. Also check whether any bπ_{στ} is negative; if so, Lemma 3.5's non-negativity claim is false as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central load-bearing step is the proof of Theorem 3.4 via Claim 4 in Appendix D.2. Claim 4 asserts that for any deterministic commitment π, the expected cost of following π on M is at least E[X(π)·W*_M], where X(π) is the indicator of accepting a terminal of M. The proof shows E[W*_{Mπ}] ≥ E[W*_M] using cost dominance, but Claim 4 requires E[X·W*_{Mπ}] ≥ E[X·W*_M] for the algorithm's stopping rule X. The unconditional inequality does not imply the acceptance-weighted inequality when X is correlated with the trajectory; the proof provides no coupling or pathwise argument. Additionally, the construction in Lemma 3.5 defines bπ_{στ} as E[ρπ(τ)] − E[ρπ|s(τs)], which can be negative; only total cost dominance is shown, not the stated non-negativity of every cost share. If Claim 4 fails, the lower bound OPT(I) ≥ E[min_{S∈F} Σ_{i∈S} W*_{Mi}] is unsupported, and therefore Theorem 4.1 and all application ratios (√2, 2, O(κ), 0.582) lose their foundation. This is a correctness risk internal to the framework, not merely a presentation issue.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines Costly Information Combinatorial Selection (CICS), a class of stochastic selection problems in which each variable is inspected through an independent acyclic MDP, and proposes a framework for approximately optimal committing policies under matroid feasibility constraints (with an extension to frugal constraints). The main ingredients are an amortized surrogate-cost construction for MDPs, a Whittle-integral-style lower bound on the optimal adaptive cost, a notion of local approximation that composes into global approximation guarantees, and applications to four problems: Pandora's Box with Partial Inspection (a sqrt(2) commitment gap), Additive Pandora's Box (a 2-approximation), a new Weighing Scale problem (an O(kappa) gap), and matroid PBOI (a 0.582 approximation in the maximization setting). The paper also carries the framework through the maximization setting and to general frugal algorithms.","tokens_in":57046,"tokens_out":11761,"duration_ms":121258,"significance":"If the lower-bound theorem and composition theorem were fully established, this would be a substantive contribution: it offers a unified decomposition for bandit superprocesses beyond indexable settings, gives new approximation bounds for several variants of Pandora's Box, introduces a natural new problem (the Weighing Scale problem), and provides the first efficient policy that beats 0.5 for matroid-PBOI. The appendix contains substantial, mostly self-contained proofs, and the action-independence/water-filling construction is a genuinely novel technical idea. The significance, however, is contingent on repairing the proof of the central Whittle-integral lower bound (Theorem 3.4), because the PBPI, APB, WS, and PBOI results are all derived through it.","major_comments":[{"comment":"The claim that the expected cost of following commitment pi is at least E[X(pi) W*_M] is reduced to proving E[W*_{Mpi}] >= E[W*_M]. The displayed calculation proves only the unconditional expectation comparison. The indicator X(pi) is correlated with the realized trajectory, because the global policy's stopping decision depends on realized terminal values, so E[X W*_{Mpi}] >= E[X W*_M] does not follow. Since inequality (8) in Theorem 3.4 and hence the Whittle-integral lower bound, Theorem 4.1, and the ratios sqrt(2), 2, O(kappa), and 0.582 all depend on this step, the submitted proof is incomplete. A possible repair is to apply Lemma 3.1 directly to the amortization supplied by Lemma 3.5; the paper should supply that argument, or an equivalent coupling, rather than the unconditional comparison given in the current text.","section":"Appendix D.2, proof of Claim 4"},{"comment":"The lemma states that the cost-sharing vector b^pi is non-negative, but the proof defines b^pi_{sigma tau} = E[rho^pi(tau)] - E[rho^{pi|s}(tau_s)]. Lemma 3.6 only guarantees E[m(z)] <= z for each z; it does not imply E[m(g_j vee rho^{pi|s}(tau_s))] >= E[rho^{pi|s}(tau_s)], so individual entries can be negative even though the aggregate over tau is non-negative. The lemma statement and the Markov-chain amortization definition in Definition 4 require b_{s tau} >= 0. This is not merely cosmetic: Lemma 3.1's proof retains terms of the form b_{s tau}(Pr[I(s)]Pr[R(tau)|R(s)] - Pr[A cap R(tau)]), which can change sign if b_{s tau} < 0. The proof should establish entrywise non-negativity, or the subsequent uses of the lemma should be reformulated.","section":"Lemma 3.5 and its proof"},{"comment":"The two claims are stated for all y in R with alpha equal to (c_o/c_p)(1 - c_o/g_p) and 1 + min(c_p/c_o, c_o/g_p), respectively. Neither claim states the regime assumption g_p < g_o < tau that the preceding paragraph introduces, and the first alpha can be less than 1 in general; for a deterministic value X = 0 it becomes c_o/(c_o + c_p) < 1. Because Definition 8 and Theorem 4.1 require alpha >= 1, the claims need to include the regime in their statements or explicitly split off the complementary case in which opening the box is 1-locally optimal. Without this, the derivation of the sqrt(2) bound at the end of Section 5.2 is not complete.","section":"Section 5.2, Claims 1-2"}],"minor_comments":[{"comment":"In several places the proof writes rho^{pi|sigma} and b^{pi|sigma} where the intended objects are rho^{pi|s} and b^{pi|s}, the restrictions of the commitment after transitioning to state s; this should be corrected.","section":"Section 3.3, proof of Lemma 3.5"},{"comment":"The semilocal composition algorithm is numbered Algorithm 2 in the main text and Algorithm 3 in Appendix I; the numbering should be made consistent.","section":"Section 8.3 and Appendix I"},{"comment":"The parameter kappa_i = mu_i/M_i + log(mu_i/g_i) is undefined when M_i = 0 or g_i = 0; the statement should give the quantile convention for the median and the assumptions required for g_i > 0.","section":"Section 7, Theorem 7.1"},{"comment":"The definition says that the terminal accept action 'results in a value v(s)', but in the minimization setting that value is a cost and in the maximization setting it is a reward; the sign convention should be made explicit at the definition.","section":"Definition 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is ambitious and the applications are significant if the framework holds. I would not reject on the basis of the current gaps, because a direct application of Lemma 3.5 to Lemma 3.1 may repair Theorem 3.4, but that repair must be written and checked carefully. The decision should hinge on whether the authors can close the acceptance-weighted step in Claim 4 and the non-negativity issue in Lemma 3.5 without changing the framework's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the good news. The framework is genuinely novel: the amortization-based surrogate costs with action independence (Lemma 3.5) and the composition theorem (Theorem 4.1) are new, and the applications cover several variants people care about. The √2 for partial-inspection PB, the constant for additive PB, the weighing-scale bound, and the 0.582 for matroid-PBOI are all real target results. If the framework holds, this is a significant advance.\n\nThe stress-test note lands. The proof of Theorem 3.4 via Claim 4 in Appendix D.2 has a gap. The claim requires E[X·W*_{Mπ}] ≥ E[X·W*_M] for the algorithm's acceptance indicator X, but the proof only establishes the unconditional inequality E[W*_{Mπ}] ≥ E[W*_M]. Since X is correlated with the trajectory—the algorithm may stop exactly when surrogate costs are low—the weighted inequality does not follow. I don't see a coupling or pathwise argument in the text that would close this. This is load-bearing: without Theorem 3.4, the lower bound on OPT, and hence the composition theorem and every application ratio, are unsupported. It may well be fixable, but it needs a real proof, not a sentence.\n\nThe paper also has some smaller rough edges. Claims 1–2 in Section 5.2 omit the regime assumption used in their proofs (where the stated α can be <1); the APB existence proof (Theorem 6.1, Step 2) is sketched and the argument that the constructed amortization is valid is quick; and the 0.582 constant leans on a numerical verification that would be better as an explicit inequality.\n\nThis is a paper for the stochastic-optimization and Pandora's-box community. A serious referee should engage with it, but the main job is to check whether Theorem 3.4's lower bound can be repaired. I'd be cautious about citing the results until that's resolved.\n\nSend it to review, with a referee who will sit down with Appendix D.2. If the gap is fixable, it's a strong paper; if not, the framework needs a different lower-bound argument.","headline":"Ambitious and likely important framework, but the central lower-bound proof has a gap that needs a real fix.","tokens_in":57591,"tokens_out":5117,"would_cite":false,"duration_ms":50188,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90C27","90C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that local per-alternative approximations compose without loss into global bounds for costly-information combinatorial selection, yielding √2, 2, O(κ), and 0.582 guarantees for Pandora's Box variants.","keywords":["combinatorial selection","costly information acquisition","bandit superprocesses","Pandora's box","commitment gap","local approximation","surrogate costs","matroid constraints"],"falsifier":"Solve, by exhaustive dynamic programming, a small matroid-min-CICS instance (e.g., two finite acyclic MDPs under a rank-1 matroid) for the true optimal cost OPT(I) and compare it with the expected minimum surrogate cost E[min_{S∈F} Σ_{i∈S} W*_{Mi}], where each W*_{Mi} is read off the optimality curve fM(y) = E[min(y, W*_M)] per Definition 7. Theorem 3.4 asserts OPT(I) ≥ E[min_{S∈F} Σ_{i∈S} W*_{Mi}]; one instance where the strict reverse inequality holds would refute the amortization foundation and, with it, all the composition results.","tokens_in":56596,"feed_emoji":"🎁","tokens_out":14605,"duration_ms":128036,"temperature":0.7,"pith_summary":"This paper tries to establish a decomposition principle for combinatorial selection problems in which information about each alternative is acquired through a sequence of costly steps, modeled as a finite-horizon Markov decision process. The key claim is that the global 'commitment gap'—the loss from fixing all local inspection decisions in advance—is governed entirely by per-alternative, local conditions: if each MDP admits an α-local commitment, then the whole matroid-constrained instance has commitment gap at most α. This is made possible by a novel cost amortization that assigns each alternative a surrogate cost whose distribution is independent of the chosen inspection strategy. A sympathetic reader would care because prior solutions existed only for narrow special cases, whereas this framework applies to arbitrary acyclic MDPs under matroid (and frugal) constraints and yields the first approximation guarantees for several Pandora's Box variants: √2 for Partial Inspection, 2 for Additive Pandora's Box, O(κ) for a new Weighing Scale problem, and 0.582 for matroid-constrained Optional Inspection in the maximization setting, the first efficient committing policy provably better than 0.5.","feed_headline":"Local checks now give global guarantees for costly search","feed_subtitle":"Per-item approximations compose into global bounds: √2, 2, and 0.582 for Pandora-box variants.","key_machinery":"The load-bearing object is the water-filling surrogate cost W*_M, a random variable extracted from an MDP's optimality curve fM(y) by the relation fM(y) = E[min(y, W*_M)]; it is the MDP-level generalization of the surrogate costs familiar from Pandora's Box analysis. For Markov chains, W*_M is generated by a bottom-up water-filling amortization that distributes each action's cost onto the cheapest downstream trajectories; the paper's novel step is Lemma 3.5, which extends this to general acyclic MDPs by showing that for every deterministic commitment π there exists an amortized cost function ρπ on trajectories—with cost-sharing and cost-dominance properties—whose induced distribution over surrogate costs is exactly W*_M, independent of π. This action independence is what makes both the global lower bound and the composition theorem work: the interaction between global and local decision-making is severed, so an α-local approximation condition on each MDP alone (f_{Mπ}(αy) ≤ α f_M(y) for all outside options y) suffices to bound the commitment gap of the whole instance by α. Each application then boils down to finding such local commitments: peeking-versus-opening for PBPI, a minimum-index static probing order for APB, One-Sided Halving for WS, and a semilocal (α, β) approximation plus a matroid-greedy composition argument for PBOI.","core_discovery":"On the paper's own terms, the central claim is that the commitment gap of a Costly Information Combinatorial Selection instance can be bounded by local approximation ratios of its constituent information-acquisition MDPs. For each MDP M, Whittle's local game (M, y)—the choice between advancing M and accepting an outside option of cost y—defines an optimality curve fM(y), which in turn defines a water-filling surrogate cost W*_M via fM(y) = E[min(y, W*_M)]. The paper proves a lower bound on the unrestricted optimum, OPT(I) ≥ E[min_{S∈F} Σ_{i∈S} W*_{Mi}] (Theorem 3.4), using a new amortization lemma (Lemma 3.5) showing that for every deterministic commitment, action costs can be shifted onto terminal outcomes so that the induced surrogate-cost distribution equals W*_M regardless of the commitment—action independence. It then proves the composition theorem (Theorem 4.1): if each Mi admits an α-local approximation (f_{Mπ_i}(αy) ≤ α f_{Mi}(y) for all y), the global commitment gap is at most α. The four applications—√2 for matroid-PBPI, 2 for matroid-APB, O(κ) for matroid-WS with the One-Sided Halving commitment, and 0.582 for matroid-max-PBOI via a semilocal approximation—are instantiations of this recipe.","pith_inferences":["Because W*_M is strategy-independent, it functions as a canonical 'price of information' for an alternative; a natural (untested) conjecture is that index policies built from these surrogate costs remain near-optimal for constraints that are 'almost' greedy, such as laminar matroids, losing only a constant or poly-log factor.","The framework assumes known distributions and mutually independent MDPs; an extension the paper leaves implicit would replace true distributions by empirical estimates, with the water-filling construction suggesting that estimation error would propagate additively through the composition bound at an O(1/√n) rate per alternative.","Theorem 7.2 shows pointwise approximation for Weighing Scale cannot be constant, yet the paper leaves open whether the weaker local approximation notion yields a universal constant; the PBOI precedent (where local failed but semilocal succeeded) suggests the better WS bound may need a similarly non-pointwise condition.","The semilocal composition is the one place the framework exploits matroid structure beyond frugality; porting semilocal approximation to other MDP families with a grab-like deterministic-terminal action—flagged by the paper itself—would extend the 0.582-style gains to new domains."],"forward_implications":["For any matroid-CICS instance, constructing an α-approximation reduces to a per-MDP search for α-local commitments; the composed policy inherits the ratio with no dependence on the number of alternatives n.","Mixed instances containing partial-inspection, additive, and optional-inspection boxes together still have commitment gap at most 2, so heterogeneous inspection protocols no longer require bespoke algorithms.","The framework transfers to any feasibility constraint admitting a frugal approximation algorithm, with the global factor becoming the product of the local α and the frugal β (Corollary B.3).","Additive Pandora's Box—equivalently, Pandora's Shortest Path on disjoint s-t paths—has constant commitment gap 2 regardless of the number of components per box, though the achieving commitment in the proof is existential.","Matroid-max-PBOI attains the first efficiently computable committing policy strictly better than the trivial 0.5, namely 0.582, via semilocal approximation."],"supporting_citations":[{"why":"Defines the classical Pandora's Box problem whose inspection variants (partial, optional, additive) are the paper's applications; its index algorithm is the Markov-chain special case.","marker":"Weitzman [1979]"},{"why":"Introduces the local games and optimality curves for bandit superprocesses, and the Whittle integral lower bound that Theorem 3.4 extends to finite-horizon MDPs.","marker":"Whittle [1980]"},{"why":"Proves the Whittle integral as a lower bound in the discounted-reward setting, the prior result whose finite-horizon analog with an algorithmic proof is Theorem 3.4.","marker":"Brown and Smith [2013]"},{"why":"Establishes index-based optimality for finite-horizon Markov-chain bandits, restated here as Theorem 3.2 and used to run the global policy after commitments.","marker":"Dumitriu et al. [2003]"},{"why":"Supplies the surrogate-cost and amortization viewpoint for classical Pandora's Box that the paper extends from Markov chains to general MDPs.","marker":"Kleinberg et al. [2016]"},{"why":"Shows how frugal (greedy-style) combinatorial algorithms lift Pandora's Box to combinatorial feasibility; the template for the matroid and frugal composition results.","marker":"Singla [2017]"},{"why":"Extends index optimality for Markov chains to combinatorial settings; used so that after commitments fix each MDP into a chain, the global index policy is optimal.","marker":"Gupta et al. [2019]"},{"why":"Defines local approximation and proves its composition for optional-inspection Pandora's Box; Definition 8 and the composition idea are generalized here to arbitrary MDPs.","marker":"Scully and Doval [2024]"},{"why":"Characterizes optimal behavior and surrogate costs for optional-inspection boxes in the local game, supplying Definition 11's Gittins and backup indices.","marker":"Doval [2018]"},{"why":"Gives the commitment-gap results for matroid-PBOI (0.63 nonconstructively, 0.5 efficiently) that Theorem 8.1's 0.582 bound improves upon.","marker":"Beyhaghi and Kleinberg [2019]"}],"fun_headline_variants":["Local optimality composes to global bounds for costly search","New framework approximates bandit superprocesses with matroids","Pandora's box variants: √2, 2, and 0.582 approximations","Cost amortization yields tight guarantees for costly information"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire framework rests on the action-independence lemma: for every way of committing to actions inside an alternative's (acyclic) information process, action costs can be shifted onto terminal outcomes so the resulting surrogate-cost distribution is exactly the one read off the MDP's optimality curve; if that fails—say for cyclic processes, which are explicitly excluded—the lower bound and all composition results collapse.","fun_headline_variants_meta":{"raw":{"variants":["Local optimality composes to global bounds for costly search","New framework approximates bandit superprocesses with matroids","Pandora's box variants: √2, 2, and 0.582 approximations","Cost amortization yields tight guarantees for costly information"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000569,"raw_usage":{"total_tokens":2763,"prompt_tokens":1084,"completion_tokens":1679,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":700,"completion_tokens_details":{"reasoning_tokens":1605}},"tokens_in":700,"tokens_out":1679,"duration_ms":12599,"temperature":1.0,"reasoning_tokens":1605,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T22:00:26.021316+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve, by exhaustive dynamic programming, a small matroid-min-CICS instance (e.g., two finite acyclic MDPs under a rank-1 matroid) for the true optimal cost OPT(I) and compare it with the expected minimum surrogate cost E[min_{S∈F} Σ_{i∈S} W*_{Mi}], where each W*_{Mi} is read off the optimality curve fM(y) = E[min(y, W*_M)] per Definition 7. Theorem 3.4 asserts OPT(I) ≥ E[min_{S∈F} Σ_{i∈S} W*_{Mi}]; one instance where the strict reverse inequality holds would refute the amortization foundation and, with it, all the composition results.","supporting_citations":[{"cited_title":"Multi-Armed Bandits and the Gittins Index","cited_arxiv_id":null,"evidence_quote":"Introduces the local games and optimality curves for bandit superprocesses, and the Whittle integral lower bound that Theorem 3.4 extends to finite-horizon MDPs."},{"cited_title":"Optimal sequential exploration: Bandits, clairvoyants, and wildcats","cited_arxiv_id":null,"evidence_quote":"Proves the Whittle integral as a lower bound in the discounted-reward setting, the prior result whose finite-horizon analog with an algorithmic proof is Theorem 3.4."},{"cited_title":"On playing golf with two balls","cited_arxiv_id":null,"evidence_quote":"Establishes index-based optimality for finite-horizon Markov-chain bandits, restated here as Theorem 3.2 and used to run the global policy after commitments."},{"cited_title":"Glen Weyl","cited_arxiv_id":null,"evidence_quote":"Supplies the surrogate-cost and amortization viewpoint for classical Pandora's Box that the paper extends from Markov chains to general MDPs."},{"cited_title":"The price of information in combinatorial optimization","cited_arxiv_id":null,"evidence_quote":"Shows how frugal (greedy-style) combinatorial algorithms lift Pandora's Box to combinatorial feasibility; the template for the matroid and frugal composition results."},{"cited_title":"The Markovian Price of Information","cited_arxiv_id":null,"evidence_quote":"Extends index optimality for Markov chains to combinatorial settings; used so that after commitments fix each MDP into a chain, the global index policy is optimal."}],"review_version":1}