{"id":"48e7803f-6a42-4fdd-a3d3-f66b9742ee0d","arxiv_id":"2502.00228","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For Pandora's box with Markovian reward correlations and order constraints, the paper claims optimal fully adaptive strategies for forest precedence graphs and fast static-transition approximations.","lead":"This paper introduces Markovian Pandora's Box, where box rewards are correlated along a directed graph and later boxes can only be opened after earlier ones. It claims polynomial-time optimal strategies for forest-shaped graphs and fast near-optimal approximations when correlations are static.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 3's stale-max recurrence (line 16) does not compute the Bellman value, so the exact line/forest optimality claim is unsupported.","rationale":"The reader's weakest assumption identifies the same load-bearing defect: Algorithm 3's recurrence uses the old maximum x instead of max{x,y} after opening a box. My concrete three-box deterministic instance confirms that this is not a harmless typo but an actual numerical error: the printed recurrence returns 2 where the Bellman value is 4. Because the single-line DP is the building block for the multi-line and forest algorithms, the main theorem (Theorem 1.1) loses its correctness proof. The paper contains no formal verification or executable implementation that could independently validate the table, and the forest optimality proof in Appendix E is a brief assertion; however, the DP indexing error is the most direct and decisive problem. The reader's REJECT verdict is therefore appropriate, and no verdict adjustment is needed.","tokens_in":26659,"tokens_out":8152,"duration_ms":82727,"concrete_test":"Run Algorithm 3 exactly as printed on the three-box line with deterministic rewards R = (5, 0, 10), costs c = (1, 6, 1). Correct Bellman recursion gives Phi(0, ., 1) = 4: open box 1, observe 5, then stop, since opening box 2 from max=5 yields 3 < 5. The algorithm as written calls RFRM(0, 5, 2) and cFR(0, 5, 2), producing z = max{0, 5, 10} - 1 - 7 = 2 and hence Phi(0, s, 1) = 2. The discrepancy is exactly the stale x in line 16; replacing the recursive arguments with max{x,y} yields the correct value 4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 3 (Appendix C.2) is the engine for every exact result, including Theorem 1.1 via Algorithm 2. Its recurrence at line 16 evaluates, after opening box i and observing reward y, the continuation using RFRM(x, s_y, i+1) and cFR(x, s_y, i+1), i.e., with the pre-opening maximum x. But the actual next state has maximum max{x,y}, and Definition 3.2 requires the continuation value Phi(max{x,y}, y, i+1), whose stopping decisions depend on that updated threshold. When y > x, the stored RFRM(x, . , i+1) and cFR(x, . , i+1) may prescribe opening boxes that are suboptimal from max{x,y}, or stopping prematurely, so the table does not compute Phi(x,s,i). Since every GRV lookup and every forest contraction (Algorithm 2) uses this table, the claimed polynomial-time optimality of the fully adaptive strategy is unsupported. The same stale argument appears in line 22 when RFRM(x, s, i) is built from max{y, RFRM(x, s_y, i+1)} rather than RFRM(max{x,y}, s_y, i+1). This is not a minor notational issue: it changes the objective value on small instances.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Markovian Pandora's Box problem, where boxes have known probing costs and Markovianly correlated rewards governed by the same directed acyclic graph that encodes precedence constraints. It proposes a generalized reservation value (GRV) and claims an exact polynomial-time fully adaptive algorithm for forest-structured precedence graphs (Theorem 1.1), building from a single-line dynamic program (Algorithm 3), then extending to multi-line settings and forests via contraction. It also gives faster near-optimal and 1/2-approximation algorithms under a static-transition assumption. The central claims are that the GRV rule is optimal and that all components can be computed in polynomial time and space.","tokens_in":26935,"tokens_out":5716,"duration_ms":53053,"significance":"If the central claims held, the paper would be a significant contribution: it would identify a structured correlation setting in which the fully adaptive optimum is exactly computable in polynomial time, contrasting with the NP-hardness of the general DAG case, and it would introduce a natural new model connecting Markovian reward dependencies with precedence constraints. The paper also proposes concrete approximation algorithms under static transitions. However, the manuscript as written does not establish these claims: the main dynamic programming recurrence contains a load-bearing indexing error, and several supporting lemmas are asserted with inadequate or flawed proof. The contribution therefore currently remains at the level of a promising framework rather than a verified set of results.","major_comments":[{"comment":"The recurrence in Algorithm 3 uses the pre-opening maximum x to index the continuation tables after observing reward y, but the actual next state has current maximum max{x,y}. Specifically, line 16 evaluates max{x, y, RFRM(x, s_y, i+1)} and line 22 builds RFRM(x,s,i) as max{y, RFRM(x, s_y, i+1)}, always with first argument x. This contradicts the Bellman equation in Section 3.2, which requires the continuation value Φ^{τ*}(max{x,s_i}, s_i, i+1), and Definition 3.2, whose stopping rule depends on the updated threshold. When y > x, the table applies stopping decisions appropriate for the lower threshold x, so the computed entries are not the Bellman values of the stated problem. Since every GRV lookup and every forest contraction uses this table, Theorems 3.7, 4.5, E.5, and 1.1 are unsupported as written.","section":"Appendix C.2, Algorithm 3, lines 16 and 22"},{"comment":"The generalized reservation value is defined in terms of the optimal stopping time τ*, and Theorem 3.5 then asserts that comparing the current maximum to the GRV recovers an optimal strategy. The only independent validation of this characterization is the dynamic programming table that computes Φ and the GRV. Because Algorithm 3 does not in fact compute the Bellman value (see previous comment), the non-circularity of the GRV definition is not established. The argument needs a correct DP table or an alternative fixed-point characterization before the optimality claim can be accepted.","section":"Sections 3.2 and 3.3, Definition 3.3 and Theorem 3.5"},{"comment":"The proof of Lemma D.4, which is the key exchange argument underlying multi-line optimality, relies on the assertion that E[A|A ≥ X] > X; this inequality is not true in general when equality can hold with positive probability. The proof also uses the notation π_A, λ_A, ρ_A (and their B counterparts) as both events and probabilities without a formal definition, and the displayed table-based calculation contains multiple ambiguous terms. Since Theorem 4.4 (the multi-line GRV optimality theorem) and the forest contraction argument depend on this lemma, the exact optimality proof is incomplete even setting aside the Algorithm 3 issue.","section":"Appendix D.2, Lemma D.4 and Theorem 4.4"},{"comment":"Lemma 6.9 asserts a 1/2 adaptivity gap for forest-structured Markovian precedence graphs, citing BFLL20 and stating that the proof 'generalizes easily' from the independent-box setting. No proof is provided, and the generalization to Markovian correlations is not immediate because the forest structure interacts with the reward dependencies. This lemma is load-bearing for Theorem 6.10 (the 1/2 approximation for forests under static transition); the claim needs a complete proof or a precise citation of a result that covers this setting.","section":"Section 6.3, Lemma 6.9"}],"minor_comments":[{"comment":"The manuscript contains numerous typos and duplicated words (for example, 'irreducible, irreducible' in Theorem F.15 and 'in put' in Theorem F.13). The paper would benefit from a careful proofreading pass.","section":"Throughout"},{"comment":"The variable j is initialized to 1 and never updated, yet the algorithm returns 'box bj that is opened and with the max reward.' This should either be updated during the loop or the return statement should be clarified.","section":"Algorithm 1, line 8"},{"comment":"A directed tree is defined as a connected DAG where removing any edge disconnects the graph, and a directed forest as a DAG whose components are trees. Standard arborescence terminology would be clearer, and the definition should specify whether edges are directed away from roots or in some other orientation.","section":"Definition 5.1"},{"comment":"The proof begins by analyzing space, then says 'Next, we analyze the space complexity' before discussing runtime. The second paragraph appears to conflate runtime and space; it should be reorganized into separate time and space complexity arguments.","section":"Section 4, Theorem 4.5 proof"},{"comment":"The variable t is set to 1 but never used, and the loop condition references 'minimal trees in graph G0' while the graph is named bG. These inconsistencies should be fixed.","section":"Algorithm 2, line 1"},{"comment":"The displayed equation for the forest case has unbalanced brackets and the expression E[max_{i∈G} R_i − Σ_{i∈G} c_i] is not well-formed. The statement should be rewritten with precise notation.","section":"Theorem 1.2"}],"recommendation":"reject","confidential_remarks":"The manuscript is not ready for publication in its current form. The central exact-optimality claim rests on a dynamic programming recurrence that is erroneous as written, and the proof of the multi-line exchange lemma contains a false inequality. These are load-bearing issues, not merely presentation problems. If the authors correct the recurrence, provide a complete proof of the adaptivity-gap lemma, and substantially revise the exposition, a resubmission could be considered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Markovian Pandora's Box is a good idea: it combines order constraints with correlated rewards in a way I haven't seen before, and the GRV contraction is a genuinely nice way to handle trees. If the main theorem were right, it would be a real result. But as written, the exact optimality claim doesn't hold up.\n\nThe problem is Algorithm 3. The recurrence at line 16, after opening box i and observing reward y, looks up continuation values RFRM(x, s_y, i+1) and cFR(x, s_y, i+1) using the pre-opening maximum x. The actual state should have max{x,y}. That matters: if y > x, the stored continuation may stop early or open boxes that are suboptimal from the updated threshold. So the DP table doesn't compute Phi(x,s,i). The same stale-max issue is in line 22 when building RFRM. This is load-bearing: every GRV lookup, and the forest contraction, uses this table. The paper does not flag it as a typo, and the proof of Lemma C.4 just asserts the algorithm works. On small instances this changes the objective, so it's not cosmetic.\n\nThe forest proof is also thin. Theorem E.5 says contraction preserves the value, but that's a brief assertion; it needs a careful induction. And the 1/2 approximation for static transitions leans on an 'adaptivity gap' from BFLL20 that the paper says generalizes easily but doesn't prove. That may be true, but it's another unverified step.\n\nWhat's good: the problem definition is sensible, the GRV idea is interesting, and the paper is honest about the PA-vs-FA gap. The citation pattern seems fair.\n\nWho is this for: someone working on Pandora's Box variants. If the DP bug is fixed, this could be solid. But as submitted, the main theorem is unsupported. I'd send it to peer review? Yes — serious work, but it needs major revision and a correct numerical DP before it's publishable. If I were an editor, I'd let the authors revise.","headline":"A natural new model with a clever contraction idea, but the central exact algorithm has a load-bearing indexing bug in its DP.","tokens_in":27442,"tokens_out":1867,"would_cite":false,"duration_ms":17804,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"For forest precedence graphs, the Markovian Pandora's box problem has a polynomial-time fully adaptive optimal strategy.","keywords":["Markovian Pandora's box","generalized reservation value","fully adaptive strategies","order constraints","forest precedence graphs","static transition","subgraph optimization","sequential decision making"],"falsifier":"Construct a two-box line in which the first box has positive probability of yielding a reward $y$ above the starting threshold $x$, and compare the continuation value returned by the table lookup $RFRM(x, s_y, i+1)$ in Algorithm 3 with the value computed by dynamic programming from the state $\\max\\{x,y\\}$. Any instance where the two values imply different opening decisions settles whether the table index is a typo; if the table value is wrong, the polynomial-time optimality claim fails.","tokens_in":26452,"feed_emoji":"📦","tokens_out":8369,"duration_ms":81467,"temperature":0.7,"pith_summary":"The paper introduces Markovian Pandora's box, a costly-search model in which one directed acyclic graph simultaneously states which boxes must be opened before which others and how each box's reward depends, Markovianly, on the reward of its predecessor. It claims that when this graph is a forest, the fully adaptive optimum—the best strategy whose stopping time and next box to open may both depend on all rewards seen so far—can be computed exactly in polynomial time and space. That matters because the fully adaptive optimum is NP-hard to approximate on general DAGs, so the forest case is a rare exactly solvable class. The decision is governed by a generalized reservation value per box, and in a forest the optimal strategy is to follow the available branch with the highest current value after minimal subtrees are contracted into single boxes with random costs. Under static transition, where every edge in a component shares one transition matrix, the paper gives faster algorithms that truncate each line to a short prefix, near-optimal on lines and multi-lines and a $\\frac{1}{2}$-approximation on forests.","feed_headline":"Forest-shaped Pandora's boxes solved exactly in poly time","feed_subtitle":"A generalized reservation value governs when to stop and which box to open next, beating general-DAG NP-hardness","key_machinery":"The machinery is the generalized reservation value (GRV), a per-box threshold defined as the smallest current maximum reward at which the expected utility of optimally continuing equals the utility of stopping. The paper computes it from a dynamic-programming table of continuation values $\\phi(x,s,i)$, storing the expected future max reward minus cost for every possible current best reward $x$, predecessor reward $s$, and next-box index $i$. In the forest algorithm, the same table is reused after contracting the descendants of a branch vertex into an equivalent single box with random cost and reward, so every contraction step preserves the GRV rule. Under static transition, the table becomes index-free and is solved by fixed-point iteration, and Markov-chain mixing bounds justify truncating lines to their first few boxes.","core_discovery":"The central claim is that a threshold rule based on a generalized reservation value is exactly optimal for the fully adaptive Markovian Pandora's box on forests. For each box and each observed predecessor state, the generalized reservation value is the current best reward $x$ at which the decision maker is indifferent between stopping and paying the cost to open that box with optimal continuation; if the threshold exceeds $x$ the strategy proceeds, otherwise it stops. In a single line this reduces the problem to an optimal stopping time, and the paper proves the threshold can be precomputed in a polynomial-size equivalent-reward table. For multiple lines the optimal strategy probes the line whose next available box has the highest current generalized reservation value, and this remains true even though the choice is now fully adaptive. For a forest, the paper contracts each minimal tree below its root into one box with a correlated random reward and cost, reducing the graph to a multi-line instance and preserving the payoff table and thresholds through every contraction; iterating gives the polynomial-time exact optimum of Theorem 1.1.","pith_inferences":["Inference: The GRV-based contraction may extend to graphs of bounded treewidth, since forest contraction is a special case of repeatedly eliminating branch vertices; the paper does not claim this.","Inference: The static-transition truncation result suggests an online or learning version of the problem where transition matrices are estimated from data could keep regret bounded by mixing time; the paper does not study learning.","Inference: A natural testable extension is to replace the single best-line search in the forest approximation by a search over a constant number of lines, which might improve the $\\frac{1}{2}$ constant while keeping the polylogarithmic runtime."],"forward_implications":["If Theorem 1.1 is correct, every Markovian Pandora's box instance whose precedence and correlation graph is a forest can be solved exactly rather than approximated, in time polynomial in the number of boxes and reward values.","The exact forest algorithm gives a concrete benchmark for measuring approximation loss on the NP-hard general-DAG problem, since any DAG algorithm can be compared against its optimal forest sub-instances.","Under static transition, near-optimal play on a line needs only a bounded mixing-time prefix, so exploration cost stays controlled as the graph grows; the speedup over the exact algorithm grows with graph size.","For forest-structured static-transition instances, restricting attention to the best directed line already guarantees half the expected payoff of any adaptive strategy, up to an additive $\\delta$.","The adaptivity-gap result means fully adaptive strategies strictly beat partially adaptive ones in this model, so the paper's focus on fully adaptive optimality addresses a real loss in simpler strategy classes."],"supporting_citations":[{"why":"defines the original Pandora's box problem and the reservation-value stopping rule that this paper generalizes.","marker":"[Wei79]"},{"why":"establishes the NP-hardness of the order-constrained problem and the $\\frac{1}{2}$ adaptivity gap between adaptive and non-adaptive strategies used in the forest approximation.","marker":"[BFLL20]"},{"why":"shows that approximating the fully adaptive optimum in correlated Pandora's box is NP-hard, motivating the structured forest assumption.","marker":"[CGMT21]"},{"why":"supplies the Markov-chain mixing-time convergence theorem used to bound how many boxes are needed in the static-transition near-optimal algorithms.","marker":"[LP17]"},{"why":"provides the data-driven algorithm design motivation for sequential inspection with costs.","marker":"[GR16]"}],"fun_headline_variants":["Forest Pandora's boxes solved exactly in polynomial time","Exact optimal probing for Markovian Pandora's box on forests","Poly-time exact strategy for Markovian Pandora's box on forests","Forests yield exact Pandora's box strategies in poly time","Generalized reservation value leads to exact forest Pandora's box"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the dynamic-programming table in Algorithm 3 correctly uses the old maximum reward $x$ as the state index after a newly opened box reveals a larger reward $y$; if the correct index is the updated maximum $\\max\\{x,y\\}$, then the stopping thresholds computed from the table are wrong on every continuation state where $y$ exceeds $x$.","fun_headline_variants_meta":{"raw":{"variants":["Forest Pandora's boxes solved exactly in polynomial time","Exact optimal probing for Markovian Pandora's box on forests","Poly-time exact strategy for Markovian Pandora's box on forests","Forests yield exact Pandora's box strategies in poly time","Generalized reservation value leads to exact forest Pandora's box"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000362,"raw_usage":{"total_tokens":1926,"prompt_tokens":891,"completion_tokens":1035,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":949}},"tokens_in":507,"tokens_out":1035,"duration_ms":9066,"temperature":1.0,"reasoning_tokens":949,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T19:45:34.593007+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a two-box line in which the first box has positive probability of yielding a reward $y$ above the starting threshold $x$, and compare the continuation value returned by the table lookup $RFRM(x, s_y, i+1)$ in Algorithm 3 with the value computed by dynamic programming from the state $\\max\\{x,y\\}$. Any instance where the two values imply different opening decisions settles whether the table index is a typo; if the table value is wrong, the polynomial-time optimality claim fails.","supporting_citations":[],"review_version":1}