{"id":"1a994e8a-a2ea-4e1b-8566-cd01c5fb57a7","arxiv_id":"2412.12879","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Optimal deterministic policies for LDST-robust MDPs are NP-hard even in a two-stage, single-deviation reward case, and transition uncertainty is Sigma_2^p-hard, but a 1/(5+epsilon)-approximation exists for the two-stage case.","lead":"This paper shows that finding the best robust deterministic policy for a Markov decision process under budgeted uncertainty is computationally hard, even in a simple two-stage case with just one uncertain reward. It also provides a constant-factor approximation for that simple case and proves the general problem with uncertain transitions is far harder, likely ruling out compact optimization formulas.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 1/(5+ε)-approximation for 2-Stage Reward-DLP relies on an unstated nonnegativity assumption: the WLOG reduction to r'=0 in §5.1 is undefined for negative alternative rewards, which the model in §2.1 permits.","rationale":"I agree with the reader's weakest-assumption diagnosis. The hardness arguments (Theorems 1, 2, 4, 5) are standard reductions and appear internally sound; my reading of the Max-Min Vertex Cover reduction found no flaw beyond minor typos. The single load-bearing weakness is the approximation algorithm's unstated nonnegativity requirement. Because the reader already marked the paper CONDITIONAL on exactly this point, my stress-test does not move the verdict. No additional concern rose to the level of changing the conclusion.","tokens_in":20792,"tokens_out":21801,"duration_ms":198152,"concrete_test":"Run the following check: for the instance above, compute L(π)=R(π)-R̂(π)=1-0=1, and compute the maximum value of UB1(L,t̂) for L=1 and t̂∈{t1,t2}. Since the only policy has v_{s,t1}=v_{s,t2}=1/2, the constraint sum v_{s,t̂} x_s ≥1 is infeasible for both t̂, so Lemma 10 is false for this instance. Repeating the same computation after replacing r'(t2) with 0 gives L(π)=1/2 and feasible UB1(1/2,t2), confirming that the failure is caused exactly by the negative alternative reward. This settles that Theorem 3 requires the missing nonnegativity condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's model in Section 2.1 allows terminal rewards r(s) ∈ R, and Section 2.3 only requires r'(s) ≤ r(s), so alternative rewards may be negative. Theorem 3 is proved in Section 5.1 by first assuming 'without loss of generality' that r'(t)=0 for every terminal state. The prescribed transformation splits each t with r'(t)>0 using h=ceil(r'(t)/(r(t)-r'(t))); when r'(t)<0, h is non-positive and the formulas for the replacement states divide by zero or produce invalid state counts. This is not merely a cosmetic gap. In the two-terminal instance with S1={s}, S2={t1,t2}, the only action giving p(t1)=p(t2)=1/2, rewards r(t1)=r(t2)=1, r'(t1)=0, r'(t2)=-1, and k=1, the true robust value is 0 and L(π)=R(π)-R̂(π)=1. The largest nominal expected reward at a terminal is only 1/2. Lemma 10 then claims that for L=1≤L(π) some UB1(L,t̂) has value at least R̂(π)=0, but both UB1(1,t1) and UB1(1,t2) are infeasible because no policy can put nominal reward ≥1 on a single terminal. The enumeration in Theorems 7 and 8 also uses r_min>0 and r'=0 to bound L(π) by max_t Q_t, so the whole approximation proof collapses once negative rewards are allowed. The hardness reductions use nonnegative rewards and are not affected, but the paper's main positive result needs an explicit assumption such as r'(t)≥0 and r(t)>r'(t).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational complexity of finding optimal deterministic policies in the Lightning Does Not Strike Twice (LDST) robust MDP model under budgeted uncertainty. It proves that 2-Stage Reward-DLP is strongly NP-hard (Theorem 1), that Reward-DLP has no polynomial-time constant-factor approximation unless P=NP (Theorem 2), that Transition-DLP is NP-hard even for budget k=2 (Theorem 4), and that Transition-DLP is Sigma_2^p-hard (Theorem 5). On the positive side, it gives a 1/(5+epsilon)-approximation algorithm for 2-Stage Reward-DLP (Theorem 3), based on a Knapsack Cover relaxation and a Generalized Assignment relaxation. The hardness reductions appear sound and are mostly clean; the main issue is that the positive result relies on an unstated nonnegativity assumption that is not part of the model as defined.","tokens_in":21103,"tokens_out":11505,"duration_ms":106091,"significance":"If the results stand, they are significant: they sharply separate deterministic from randomized policies in the LDST model, complementing Mannor et al.'s polynomial-time result for randomized policies. The Sigma_2^p-hardness of Transition-DLP is a strong statement about the impossibility of compact mixed-integer formulations. The approximation algorithm for the two-stage reward case is a useful positive counterpoint to the hardness results. The paper's reductions are from established hard problems and use external algorithms (FPTAS for Knapsack Cover and the Shmoys-Tardos algorithm for Generalized Assignment), which makes the proofs verifiable. However, the positive result currently depends on an assumption that is absent from the model definition, and one central reduction contains a misstated equation; these issues are fixable but require revision.","major_comments":[{"comment":"The reduction to r'(t)=0 is not without loss of generality for the model defined in Sections 2.1-2.3. The model allows arbitrary real terminal rewards and only requires r'(s) <= r(s). The transformation in Section 5.1 is applied only for r'(t)>0; for r'(t)<0, the formula h = ceil(r'(t)/(r(t)-r'(t))) is non-positive or undefined, and the replacement states and probabilities are not well-defined. This is not a cosmetic gap: in the two-terminal instance with S1={s}, S2={t1,t2}, p(t1)=p(t2)=1/2, r(t1)=r(t2)=1, r'(t1)=0, r'(t2)=-1, and k=1, the true robust value is 0, L(pi)=1, but no policy can achieve nominal reward at least 1 on a single terminal, so Lemma 10 fails. The enumeration in Theorems 7 and 8 also assumes r_min>0 in the definition of L_i, which is not guaranteed by the model. Theorem 3 therefore needs an explicit assumption such as r'(t) >= 0 and r(t) > r'(t) (which implies nonnegative nominal rewards), or the transformation and guarantees must be extended to negative alternative rewards.","section":"Section 5.1, Assumption 2; Theorems 3, 7, 8"},{"comment":"The sentence identifying the choice of epsilon is incorrect as written. The text states that epsilon is 'the unique solution to 1 - |I|*epsilon/|V| = epsilon/(2m)', but the value epsilon = 2m/(2m|I|+|V|) does not satisfy this equation in general; for example, with m=1, |I|=1, |V|=10, the left-hand side is approximately 0.983 while the right-hand side is approximately 0.083. The inequalities later needed (p_e > p_v for e in E_{t_pi} and p_e < p_v otherwise) do hold for the stated epsilon because p_v = 1/(2m|I|+|V|), p_e = 2epsilon/(3m) = 4/(3(2m|I|+|V|)) for e in E_{t_pi}, and p_e <= epsilon/(3m) = 2/(3(2m|I|+|V|)) otherwise. The proof is thus repairable, but the present derivation does not justify the claim and should be corrected.","section":"Section 6, proof of Theorem 5"}],"minor_comments":[{"comment":"In the definition of the state space, 'S3 := {tj}' should be 'S2 := {tj}', since the three stages are S0, S1, and S2.","section":"Section 4, proof of Theorem 1"},{"comment":"The artificial state t* is denoted with the same star symbol used in v_{st}^*, which makes the notation confusing in the definition of v_{st}^* and in Lemmas 12 and 13; please use distinct notation for the artificial state.","section":"Section 5.3, definition of UB2"},{"comment":"In the displayed inequality after invoking the Shmoys-Tardos algorithm, the right-hand side should be the objective value of the fractional solution, not the same expression with y' on both sides. Also, the enumeration in the proof of Theorem 8 loops over every t-hat in S2, but UB2(L) does not depend on t-hat; only the L_i values are needed.","section":"Section 5.3, proof of Theorem 8"},{"comment":"In the definition of A', 'for some i in N' should be 'for some i in M' (the clauses), and the notation 'pi(sCi)' should be 'pi(s_{c_i})' for consistency.","section":"Section 6, proof of Theorem 4"},{"comment":"There are several typographical slips: 'there a is a 1/(5+epsilon)-approximation' in Theorem 3, and the expression 'pv = 1 - epsilon|I| / |V|' in the proof of Theorem 5 should be parenthesized as '(1 - epsilon|I|)/|V|'.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid contribution and the hardness results appear correct. The main concern is the unstated nonnegativity assumption in the approximation algorithm; with an explicit assumption or a fixed reduction, the paper would be acceptable. The misstated epsilon equation in Theorem 5 is also easily corrected. I would recommend major revision rather than rejection because these issues are local and repairable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"One thing you should know: this is a real contribution, and the hardness results should hold up. The paper's main positive result, however, is currently only proved under an unstated nonnegativity assumption, and the proof as written collapses when alternative rewards are negative.\n\nWhat is genuinely new: the contrast between polynomial-time randomized policies and NP-hard deterministic policies in the LDST model, even with two stages and a single deviating reward. The reductions are clean. The 3-Partition construction in Theorem 1 is straightforward and correct; the disjoint-paths reduction for Theorem 2 is a nice use of layered DAGs and the epsilon-weighting trick. Theorem 5's Sigma_2^p-hardness is intricate, and while the proof contains a misstated equation for epsilon, the chosen value does satisfy the inequalities, so that is a minor typo. The approximation algorithm combining a Knapsack Cover relaxation and a Generalized Assignment relaxation is clever, and the two-lemma structure is sound given its assumptions. No circularity: the paper relies on external FPTAS for Knapsack Cover and Shmoys-Tardos, and the hardness targets are established problems.\n\nThe soft spot is load-bearing. In Section 5.1, the paper claims WLOG that r'(t)=0 for every terminal state, but the transformation is only defined when r'(t)>0. The model in Section 2.3 allows r'(s) <= r(s) with no lower bound, so negative alternative rewards are permitted. The stress-test example is the right one: two terminals, both nominal reward 1, alternative rewards 0 and -1, one deviating state, equal probability on the two terminals. The true robust value is 0, L(pi)=1, and Lemma 10 fails because no UB1(L,t) with L=1 can have value at least 0 -- the largest single-terminal nominal reward is 1/2. The enumeration bounds in Theorems 7 and 8 also rely on rmin <= L(pi) <= rmax, which breaks with negative r'. So Theorem 3 as stated is false or at least unproven for the model actually defined. This is fixable by explicitly assuming r'(t) >= 0 (and r(t) > r'(t)) in the theorem, or by extending the transformation, but it changes the scope of the positive result.\n\nVerdict: the hardness half is solid and worth publishing; the approximation half needs a revision. The paper deserves a serious referee. I would send it to review with a clear request to address the nonnegativity issue. For a reading group, it is a maybe -- the gap is a good discussion point, but the main results are narrow.","headline":"Hardness results are solid, but the approximation theorem has an unstated nonnegativity assumption that currently makes it false as written.","tokens_in":21714,"tokens_out":3937,"would_cite":true,"duration_ms":35362,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40","68Q17","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that finding an optimal deterministic policy in the LDST budgeted-uncertainty MDP model is computationally intractable, with NP-hardness already for two stages and a single deviating terminal reward, and…","keywords":["robust Markov decision processes","deterministic policies","budgeted uncertainty","LDST model","NP-hardness","approximation algorithms","Sigma-2 hardness","mixed integer programming"],"falsifier":"For a terminal state $t$ with nominal reward $r(t)=1$, deviating reward $r'(t)=-1$, and a policy reaching $t$ with probability 1, the paper's reduction yields $h=0$ and replaces $t$ by a state with nominal reward 2 and deviating reward 0, changing the worst-case value from $-1$ to $0$; any 2-Stage Reward-DLP instance containing such a negative deviation therefore tests whether Theorem 3's guarantee actually covers the paper's stated domain of arbitrary real rewards, and the described reduction shows it does not.","tokens_in":20518,"feed_emoji":"🎲","tokens_out":10523,"duration_ms":90622,"temperature":0.7,"pith_summary":"The paper asks how hard it is to choose a deterministic policy for a Markov decision process when the parameters (terminal rewards or transition probabilities) may deviate from their nominal values at a bounded number of states, the 'Lightning Does Not Strike Twice' (LDST) uncertainty model. It claims that this task is computationally hard in stark contrast to the randomized-policy case, which earlier work showed can be solved in polynomial time for reward uncertainty. Specifically, the paper establishes that already a two-stage MDP with a single deviating terminal reward is strongly NP-hard to optimize, and that the general reward-uncertainty version has no bounded approximation unless P equals NP. For transition uncertainty, the paper proves the problem is Sigma_2^p-hard, effectively excluding compact mixed-integer linear programming formulations. On the positive side, it gives a constant-factor approximation algorithm for the two-stage reward-uncertainty case.","feed_headline":"Even one deviating reward makes robust MDP policies NP-hard","feed_subtitle":"Randomized robust policies stay tractable; deterministic policies are intractable even with one deviating reward.","key_machinery":"The argument for hardness is carried by reductions from classic problems: 3-Partition for the two-stage NP-hardness, Vertex-Disjoint Paths for the inapproximability of the general reward case, Max-Min Vertex Cover for the Sigma_2^p-hardness of transition uncertainty, and 3-SAT for the fixed-budget decision version. The positive algorithm is organized around the loss of a policy, $L(\\pi) = R(\\pi) - \\hat{R}(\\pi)$, the drop in expected reward under the worst-case deviation. It solves a Knapsack Cover relaxation (with an FPTAS) for instances where the optimal loss is large relative to the optimal worst-case reward, and a Generalized Assignment relaxation (with a standard rounding for assignment problems) for instances where the loss is small; the better of the two resulting policies is returned.","core_discovery":"The central discovery is a separation between randomized and deterministic policies in the LDST model. Whereas optimal randomized policies under reward uncertainty can be computed efficiently, the deterministic version is intractable: the two-stage reward case is strongly NP-hard (Theorem 1), the general reward case admits no constant-factor approximation unless P = NP (Theorem 2), and the version with uncertain transitions is Sigma_2^p-hard (Theorem 5), with a further NP-hardness result for deciding positive robust reward with budget k=2 (Theorem 4). The only general positive result is a 1/(5+epsilon)-approximation for the two-stage reward case (Theorem 3), obtained by running two complementary relaxations and taking the better policy.","pith_inferences":["If the unstated nonnegativity of deviating rewards is genuinely required, the positive approximation result is less general than the problem definition suggests; extending it to negative deviations would need a different rounding or a different relaxation.","The hardness contrast suggests that randomization in robust MDPs is not merely a modelling convenience but a source of tractability, which may matter for applications that require deterministic execution.","The two-relaxation idea—one for large-loss and one for small-loss regimes—could plausibly be adapted to other budgeted-robust optimization problems where a similar loss measure is available."],"forward_implications":["Even the simplest meaningful deviation—a single terminal reward changing in a two-stage MDP—makes the optimal deterministic policy impossible to compute in polynomial time unless P = NP.","For general reward uncertainty, no polynomial-time algorithm can guarantee any fixed fraction of the optimal worst-case reward, so approximation must be restricted to special structures.","For transition uncertainty, the Sigma_2^p-hardness implies that no compact mixed-integer programming formulation can capture the problem unless the polynomial hierarchy collapses.","The 1/(5+epsilon)-approximation for the two-stage reward case shows that this restricted problem is approximable despite being NP-hard, and the approximation factor is independent of the size of the MDP."],"supporting_citations":[{"why":"Introduces the LDST budgeted-uncertainty model and proves the polynomial-time result for randomized policies with reward uncertainty that this paper contrasts.","marker":"[8]"},{"why":"Extends the LDST model to k-rectangular uncertainty and provides the adaptive-policy tractability result that motivates the deterministic-policy question.","marker":"[9]"},{"why":"Supplies the budgeted-uncertainty approach to robustness that LDST adapts to MDPs.","marker":"[1]"},{"why":"Provides the FPTAS for Knapsack Cover used by the first approximation subroutine.","marker":"[11]"},{"why":"Provides the rounding algorithm for Generalized Assignment used by the second approximation subroutine.","marker":"[14]"},{"why":"Establishes Sigma_2^p-completeness of Max-Min Vertex Cover, the source problem for the transition-uncertainty hardness reduction.","marker":"[6]"},{"why":"Establishes NP-hardness of Vertex-Disjoint Paths in DAGs, the source problem for the inapproximability reduction.","marker":"[2]"},{"why":"Explains why Sigma_2^p-hardness rules out compact mixed-integer programming formulations.","marker":"[17]"}],"fun_headline_variants":["Single reward deviation breaks MDP policy tractability","Robust MDP policy: one deviation, NP-hard","Deterministic robust MDP policy: intractable even with one deviation","Budgeted uncertainty: deterministic policies NP-hard","Robust MDP: deterministic policies NP-hard even with one deviation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's positive constant-factor approximation for two-stage reward uncertainty depends on an unstated assumption that every deviating reward is nonnegative and no larger than the nominal reward, since its reduction to zero deviations splits a terminal state into an integer number of copies using $h = \\lceil r'(t)/(r(t)-r'(t)) \\rceil$, a formula that is not value-preserving when $r'(t) < 0$.","fun_headline_variants_meta":{"raw":{"variants":["Single reward deviation breaks MDP policy tractability","Robust MDP policy: one deviation, NP-hard","Deterministic robust MDP policy: intractable even with one deviation","Budgeted uncertainty: deterministic policies NP-hard","Robust MDP: deterministic policies NP-hard even with one deviation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000906,"raw_usage":{"total_tokens":3889,"prompt_tokens":931,"completion_tokens":2958,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":2877}},"tokens_in":547,"tokens_out":2958,"duration_ms":20895,"temperature":1.0,"reasoning_tokens":2877,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:41:12.405555+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a terminal state $t$ with nominal reward $r(t)=1$, deviating reward $r'(t)=-1$, and a policy reaching $t$ with probability 1, the paper's reduction yields $h=0$ and replaces $t$ by a state with nominal reward 2 and deviating reward 0, changing the worst-case value from $-1$ to $0$; any 2-Stage Reward-DLP instance containing such a negative deviation therefore tests whether Theorem 3's guarantee actually covers the paper's stated domain of arbitrary real rewards, and the described reduction shows it does not.","supporting_citations":[{"cited_title":"Lightning does not strike tw ice: robust MDPs with coupled uncertainty","cited_arxiv_id":null,"evidence_quote":"Introduces the LDST budgeted-uncertainty model and proves the polynomial-time result for randomized policies with reward uncertainty that this paper contrasts."},{"cited_title":"Robust MDPs with k-rectangular uncertainty","cited_arxiv_id":null,"evidence_quote":"Extends the LDST model to k-rectangular uncertainty and provides the adaptive-policy tractability result that motivates the deterministic-policy question."},{"cited_title":"The price of robustness","cited_arxiv_id":null,"evidence_quote":"Supplies the budgeted-uncertainty approach to robustness that LDST adapts to MDPs."},{"cited_title":"Approximation schemes fo r a class of subset selection problems","cited_arxiv_id":null,"evidence_quote":"Provides the FPTAS for Knapsack Cover used by the first approximation subroutine."},{"cited_title":"An approximation algorithm for the generalized assignment problem","cited_arxiv_id":null,"evidence_quote":"Provides the rounding algorithm for Generalized Assignment used by the second approximation subroutine."},{"cited_title":"On the complexity of min-max optimizat ion problems and their approximation","cited_arxiv_id":null,"evidence_quote":"Establishes Sigma_2^p-completeness of Max-Min Vertex Cover, the source problem for the transition-uncertainty hardness reduction."},{"cited_title":"On the complexity of timetable and mul- ticommodity flow problems","cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of Vertex-Disjoint Paths in DAGs, the source problem for the inapproximability reduction."},{"cited_title":"The trouble with the second quantifier","cited_arxiv_id":null,"evidence_quote":"Explains why Sigma_2^p-hardness rules out compact mixed-integer programming formulations."}],"review_version":1}