{"id":"e9e5e66d-f76c-460e-a049-515ac54cdfe5","arxiv_id":"2505.02479","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper constructs a layered homogeneous model equivalent to the non-homogeneous semi-Markov reach-avoid model and proposes a value iteration algorithm for the maximal reach-avoid probability and an ε-optimal policy.","lead":"This paper gives an algorithm for the maximum probability of reaching a target before hitting time-varying obstacles in a finite-horizon semi-Markov decision process. It rewrites the model with an extra coordinate that counts decision steps, but the algorithm only optimizes over policies that ignore the elapsed time, a restriction that generally loses optimality.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 2.2's reduction to Markov policies ignores remaining time; a two-state counterexample shows the restricted optimum is below G*, so Algorithm 4.1 solves a weaker problem.","rationale":"The reader identified Proposition 2.2 as the weakest assumption, and my independent analysis confirms that the reduction to randomized Markov policies depending only on current state and decision-epoch count is not valid for finite-horizon reach-avoid criteria. The remaining time is an essential part of the information state, and the paper's equivalent layered model (3.5) does not include elapsed time in its state, so its stationary policies cannot adapt to the remaining horizon. The explicit counterexample shows a strict gap between the sup over all history-dependent policies and the sup over the class used by Algorithm 4.1. The proof of Proposition 2.2 is also incomplete: condition (2.9) matches only one-dimensional marginals, not the joint distribution required for the stopping event. Since the paper's stated goal is to compute G*(x,T) over all history-dependent policies, and the algorithm provably optimizes only over a restricted class, the central claim does not hold as stated. The numerical example contains additional inconsistencies, but they are secondary. I therefore agree with the reader's REJECT verdict.","tokens_in":21907,"tokens_out":6224,"duration_ms":79951,"concrete_test":"Implement the two-state counterexample exactly: E = {0,1,2,3}, C = {2}, B_n = ∅, T = 6; Q({1}, t | 0, go) = 0 for t < 4, = 1/2 for 4 ≤ t < 5, = 1 for t ≥ 5; at state 1, action a has Q({2}, t | 1, a) = 1/2 for t ≥ 1 and Q({3}, t | 1, a) = 1/2 for t ≥ 1, while action b has Q({2}, t | 1, b) = 9/10 for t ≥ 2 and Q({3}, t | 1, b) = 1/10 for t ≥ 2. Run Algorithm 4.1 with a small tolerance ρ (e.g., 10^{-6}) and compare its output to a direct dynamic-programming computation that includes remaining time t − σ_n in the state. If the algorithm returns about 0.5 while the full computation returns 0.7, then Proposition 2.2 fails and the central claim is unsupported; if it returns 0.7, the concern would be refuted.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim depends on Proposition 2.2, which asserts that every history-dependent policy π can be replaced by a randomized Markov policy π′ = {ψ_n} with ψ_n depending only on X_{σ_n} and n, for every horizon t. This is load-bearing because Theorem 3.1 and Lemma 3.1 transfer only such Markov policies to stationary policies of the layered model, and Algorithm 4.1 optimizes over that restricted class. The reduction is invalid for finite-horizon reach-avoid: at decision epoch n the optimal action generally depends on the remaining time T − σ_n, which is not encoded in the pair (X_{σ_n}, n). The proof of Proposition 2.2 only matches marginal distributions of individual states and actions (2.9), not the joint evolution needed to preserve the event {τ_C < τ̄ ∧ t}. A concrete failure is as follows. Let E = {0,1,2,3}, C = {2}, B_n = ∅ for all n, and T = 6. From state 0, the only action 'go' jumps to state 1 with sojourn time 4 with probability 1/2 and 5 with probability 1/2. At state 1, action a reaches C with probability 1/2 after 1 time unit and otherwise goes to absorbing state 3; action b reaches C with probability 9/10 after 2 time units and otherwise goes to state 3. If the process arrives at state 1 at time 4, the remaining time is 2, so b is optimal (success 0.9); if it arrives at time 5, the remaining time is 1, so only a can succeed (0.5). A history-dependent policy observes σ_1 and attains (1/2)·0.9 + (1/2)·0.5 = 0.7. Any randomized Markov policy with fixed ψ_1(·|1) attains at most max(0.5, 0.45, or a mixture value in between) = 0.5. Hence sup over all history-dependent policies strictly exceeds sup over randomized Markov policies, so G*(x,T) is not equal to the value computed over the restricted class. Algorithm 4.1 therefore computes a quantity that can be strictly below the claimed maximal reach-avoid probability for the problem as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies finite-horizon reach-avoid probabilities in semi-Markov decision processes with time-varying obstacle sets B_n. It constructs an equivalent two-dimensional homogeneous model S = E × Z_+ in (3.5), proves an equivalence result in Theorem 3.1, derives a value iteration (4.11), and proposes Algorithm 4.1 for computing the maximal reach-avoid probability and an epsilon-optimal policy, followed by a numerical plane-flight example in Section 5. The intended contribution is to handle non-homogeneous obstacle sets by augmenting the state with the decision-epoch count.","tokens_in":22306,"tokens_out":4020,"duration_ms":45895,"significance":"If the equivalence and the policy-reduction claims were valid, the paper would fill a genuine gap in the reach-avoid literature by extending algorithms from MDPs with fixed obstacles to semi-Markov decision processes with time-varying obstacles. The layered-state construction is a natural idea, and the value-iteration bound in Proposition 4.2 together with the worked example are useful components. However, the central reduction from history-dependent policies to randomized Markov policies is not justified, and this invalidates the claimed equality G*(x,t) = G̃*(x,0,t) and hence the algorithm's guarantee. The paper is therefore not publishable in its current form.","major_comments":[{"comment":"The reduction of arbitrary history-dependent policies to randomized Markov policies π' = {ψ_n} with ψ_n(·|x) depending only on X_{σ_n} and n is not proved. The proof matches only the marginal distributions of individual states and actions in (2.9), but the reach-avoid event {τ_C < τ̄ ∧ t} depends on the joint distribution of states, actions, and sojourn times. In a finite-horizon problem the optimal action at an epoch generally depends on the remaining time T − σ_n, which is not encoded in the pair (X_{σ_n}, n). A concrete failure is as follows: let E = {0,1,2,3}, C = {2}, B_n = ∅ for all n, and T = 6. From state 0 the only action jumps to state 1 with sojourn time 4 or 5, each with probability 1/2. At state 1, action a reaches C with probability 1/2 after 1 time unit and otherwise goes to an absorbing failure state; action b reaches C with probability 9/10 after 2 time units and otherwise fails. A history-dependent policy that observes σ_1 attains (1/2)(0.9) + (1/2)(0.5) = 0.7, while any randomized Markov policy with a fixed ψ_1(·|1) attains at most 0.5. Thus Proposition 2.2 is false as stated, and the restriction to Π_rm is a real loss of performance.","section":"§2, Proposition 2.2 and Eq. (2.9)"},{"comment":"Because Proposition 2.2 is invalid, the equivalence G*(x,t) = G̃*(x,0,t) in Eq. (3.16) is not established. The proof of Theorem 3.1 only transfers randomized Markov policies via (3.6)–(3.7), while the supremum defining G* is taken over all history-dependent policies Π. Since the optimal policy may need to depend on the remaining time, the supremum over Π_rm can be strictly smaller than the supremum over Π. Consequently, the equation G*(x,t) = G̃*(x,0,t) is not justified, and this equality is load-bearing for the entire value-iteration and algorithm construction.","section":"§3, Theorem 3.1 and Eq. (3.16)"},{"comment":"Theorem 4.1(ii) produces a deterministic stationary policy f̃* for the layered model (3.5) for a fixed horizon T, and Step 4 of Algorithm 4.1 converts it to a Markov policy π* = {f*_n} for the original model. This policy depends on time only through the decision-epoch count n, not through the remaining time T − σ_n. In light of the counterexample above, such a policy class is not sufficient for optimality in the original finite-horizon problem. Therefore Algorithm 4.1, as stated, computes the optimum over a restricted class and cannot be said to compute G*(x,T). The numerical example in Section 5 accordingly reports the restricted value rather than the true maximal reach-avoid probability.","section":"§4, Theorem 4.1 and Algorithm 4.1"}],"minor_comments":[{"comment":"In the first displayed equality of (2.9) the probability measure on the right-hand side should be P^{π'}_x rather than P^{π}_x; as written the equality is tautological.","section":"§2, Eq. (2.9)"},{"comment":"The displayed formula for W_0(x,n_Ɩ̃,T) contains a stray closing brace after the maximum; this typo should be corrected.","section":"§4, Algorithm 4.1, Step 1"},{"comment":"The sentence beginning 'when the process is in a state where it is transferred to neither C nor B_k' is unclear and should be rephrased to state precisely which initial state and which layer are being compared.","section":"§4, Remark 4.1"},{"comment":"The paragraph beginning 'Therefore, under the above transition kernel, our purpose is computing...' is repeated verbatim, and one of the two copies should be deleted.","section":"§5, Example 5.1"},{"comment":"The figures appear as raw ASCII plots embedded in the text; they should be provided as properly labeled figure files with readable axes and legends.","section":"§5, Figures 1–3"}],"recommendation":"reject","confidential_remarks":"The central reduction in Proposition 2.2 is not a minor gap: the concrete counterexample shows the restricted Markov class can be strictly suboptimal in a finite-horizon reach-avoid problem. Repairing this would require adding the remaining time to the state or otherwise enlarging the policy class, which would change the algorithm and the main theorem substantially. I therefore recommend rejection rather than major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about arXiv:2505.02479. First, it has a real idea: build a layered model whose state includes the decision-epoch count, and compute finite-horizon reach-avoid probability for semi-Markov decision processes with step-dependent obstacle sets. Second, the central claim as stated is not true: the reduction to randomized Markov policies in Proposition 2.2 is invalid, and the algorithm therefore computes a quantity that can be strictly below the maximal reach-avoid probability over history-dependent policies.\n\nThe layered construction itself is sound. Theorem 3.1 is a correct equivalence between the original process and the layered process when policies are restricted to those that depend only on the current state and the decision-epoch count. The value iteration in Section 4 is a standard application of the Bellman equation, and the convergence arguments in Propositions 4.1 and 4.2 are acceptable, modulo some notational mess.\n\nThe soft spot is load-bearing. Proposition 2.2 claims that any history-dependent policy can be replaced by a policy of the form ψ_n(·|X_{σ_n}), but its proof only matches marginal distributions of the state and action at each jump; it does not preserve the joint distribution of states, actions, and sojourn times, which is exactly what the event {τ_C < τ̄ ∧ t} depends on. The failure is concrete. Suppose from state 0 we reach state 1 at time 4 or 5 with probability 1/2 each; at state 1, action a succeeds with probability 1/2 in one time unit, action b succeeds with probability 9/10 in two time units. With remaining time two, b is better; with remaining time one, only a can succeed. A history-dependent policy observes the arrival time and gets 0.7, while any policy that sees only the state and epoch number gets at most 0.5. The same issue invalidates Theorem 4.1's claim that a stationary policy is optimal for the layered model: the optimal action generally depends on the remaining time. The numerical example's convergence parameters also have internal inconsistencies (e.g., n_tilde_l is declared but the displayed iteration counts do not match), but that is minor next to the main gap.\n\nWho is this for? Someone working on semi-Markov reach-avoid might find the layered-model equivalence useful for the restricted policy class, and the paper is honestly written. But the stated problem is not solved. I would not cite the main theorem as it stands. I would still send it to a serious referee rather than desk-reject: the gap is identifiable and the paper contains a salvageable subproblem. With a major revision that either restricts the problem statement or augments the state with remaining time, it could become a valid contribution.","headline":"The layered-state idea is worthwhile, but the Markov-policy reduction is wrong, so the algorithm solves a weaker problem than the one advertised.","tokens_in":22908,"tokens_out":8753,"would_cite":false,"duration_ms":100708,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A15","91A25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the maximal reach-avoid probability of a semi-Markov decision process with time-varying obstacles equals that of a homogeneous two-dimensional model, and gives an improved value iteration that computes it together…","keywords":["reach-avoid probability","finite horizon semi-Markov decision processes","time-varying obstacles","non-homogeneous model","equivalent two-dimensional model","epsilon-optimal policy","value iteration algorithm"],"falsifier":"Take two states plus a target, choose deterministic sojourn times, and let one action at the first decision epoch be optimal only when the remaining time exceeds a threshold; compute the reach-avoid probability under the best randomized Markov policy depending only on $(X_{\\sigma_n}, n)$ and compare it with the supremum over all policies that may use the exact remaining time $T-\\sigma_n$. If the latter is strictly larger, Proposition 2.2 fails, and with it the equivalence used by Algorithm 4.1.","tokens_in":21663,"feed_emoji":"🎯","tokens_out":7372,"duration_ms":81410,"temperature":0.7,"pith_summary":"This paper tackles a reach-avoid problem for semi-Markov decision processes: a system moves between states after random waiting times with general distributions, and the goal is to maximize the probability of reaching a target set before hitting an obstacle, all within a fixed time horizon. The obstacle set is allowed to change from one decision epoch to the next, which makes the model time-inhomogeneous and rules out the fixed-obstacle techniques used in earlier work. The central contribution is a two-dimensional reformulation in which the state records both the physical state and the number of jumps made so far; in this reformulation the changing obstacles become a fixed layered obstacle set, and the paper proves that the original maximal reach-avoid probability equals the maximal reach-avoid probability of the new model. The paper then gives an improved value-iteration algorithm that computes this value and an $\\epsilon$-optimal policy in a prespecified number of iterations, and transfers the result back to the original model. If correct, this makes time-varying obstacle reach-avoid problems computationally tractable in the same way fixed-obstacle problems already are, with direct applications to aircraft path planning and traffic management.","feed_headline":"Algorithm computes best reach-avoid odds with moving obstacles","feed_subtitle":"A layered state trick turns changing hazard zones into a fixed obstacle set, yielding provable ε-optimal policies.","key_machinery":"The load-bearing object is the two-dimensional (layered) semi-Markov model (3.5), whose state is $(x,n)\\in E\\times\\mathbb{Z}_+$ with $n$ the number of jumps so far. The layered cemetery set is $\\tilde B=\\cup_n(B_n\\times\\{n\\})$, the layered target is $C\\times\\mathbb{Z}_+$, and the transition kernel $\\tilde Q$ sends $(x,k)$ to the next layer $k+1$ under the original kernel $Q$, with a special absorbing action $\\Delta^*$ inside $\\tilde B$. This object does the work of homogenization: the non-homogeneous obstacle sequence $B_n$ becomes a layered homogeneous obstacle $\\tilde B$, so the search over history-dependent policies reduces to a search over stationary policies. The companion machinery is the operator $L_a$ and the monotone value iteration $W_{n+1}(x,k,t)=\\max_a L_a W_n(x,k,t)$, whose limit is $\\tilde G^*(x,k,t)$ by Theorem 4.3; Proposition 4.2 converts the convergence into an explicit iteration count and an $\\epsilon$-optimal stationary policy.","core_discovery":"The paper's central claim is that the finite-horizon maximal reach-avoid probability $G^*(x,T)=\\sup_{\\pi\\in\\Pi}P_x^\\pi(\\tau_C<\\bar\\tau\\wedge T)$ for a semi-Markov decision process with time-varying obstacle sets $B_n$ can be computed by solving a time-homogeneous auxiliary model. The auxiliary model takes state $(x,n)\\in E\\times\\mathbb{Z}_+$, records the decision-epoch count $n$ as part of the state, declares $\\tilde B=\\cup_n(B_n\\times\\{n\\})$ as its cemetery set and $C\\times\\mathbb{Z}_+$ as its target, and uses the same semi-Markov kernel with a forced jump from layer $n$ to layer $n+1$. Theorem 3.1 proves that the reach-avoid probability under any randomized Markov policy in the original model equals that of the corresponding stationary policy in the auxiliary model, so $G^*(x,T)=\\tilde G^*(x,0,T)$. The paper then shows the auxiliary value function satisfies an optimality equation, that a deterministic stationary optimal policy exists, that the monotone value iteration $W_{n+1}=\\max_a L_aW_n$ converges to $\\tilde G^*$, and that a prescribed number of iterations yields an $\\epsilon$-optimal policy. The final step transfers the computed stationary policy back to a Markov policy for the original model via Lemma 3.1 and Theorem 3.1.","pith_inferences":["Inference: the layered construction should extend to random obstacle sets $B_n$ that are revealed online, because the layer index already carries the epoch; the algorithm would then compute the conditional reach-avoid probability given the observed obstacle history.","Inference: one can use the algorithm as an inner oracle to optimize obstacle placement, since the example suggests that altering $B_n$ for finitely many epochs changes the value monotonically; this yields a planner that searches over which obstacles to move.","Inference: in models with deterministic sojourn times, the Markov-policy reduction in Proposition 2.2 may fail when the optimal action depends on residual time, so the algorithm's guarantee should be tested against a residual-time state extension in that special case."],"forward_implications":["The algorithm yields an $\\epsilon$-optimal policy, not merely a value bound, so a user can extract a concrete decision rule for each decision epoch from the auxiliary model's stationary policy.","When obstacle sets are monotone in $n$ ($B_k\\subseteq B_{k-1}$ or the reverse), the maximal reach-avoid probability is monotone in the layer index, giving qualitative predictability before any computation.","The equivalence transfers the reach-avoid problem to a homogeneous model, so the standard optimality-equation and convergence machinery for stationary semi-Markov policies applies directly.","The paper gives an explicit convergence rate: after $\\tilde l=\\tilde K+\\log_\\beta(\\epsilon/2)$ iterations the value error is below $\\epsilon$, so the number of iterations is known in advance from the kernel's holding-time bound.","In the plane-flight example, the computed values show that changing the obstacle set at finitely many decision epochs can strictly increase the maximal reach-avoid probability relative to a fixed obstacle set."],"supporting_citations":[{"why":"Provides the long-run average transformation for fixed-obstacle reach-avoid that the paper shows cannot apply directly to time-varying obstacles, motivating the new value-type algorithm.","marker":"[1]"},{"why":"Gives the existence of optimal reach-avoid policies in discrete-time MDPs that the paper's stationary-policy existence theorem parallels.","marker":"[8]"},{"why":"Supplies the state-space enlargement technique that the transferred method adapts to handle time-varying obstacles.","marker":"[4]"},{"why":"Supplies Assumption 2.1 and the sufficient condition used to prevent infinitely many jumps in a finite horizon.","marker":"[18]"},{"why":"Supplies the convolution bound used to establish the explicit iteration count and epsilon-optimality in Proposition 4.2.","marker":"[21]"},{"why":"Provides a state-classification policy-iteration approach for MDP reach-avoid that this paper contrasts with its improved value-type method.","marker":"[26]"},{"why":"Treats reach-avoid under embedded Markov chains in continuous-time controlled Markov systems, the semi-Markov analogue this paper extends.","marker":"[25]"},{"why":"Supplies the standard reduction argument used in Proposition 2.2 to replace history-dependent policies by Markov policies.","marker":"[28]"}],"fun_headline_variants":["Moving obstacles? Lift time into the state and solve reach-avoid","Adding a time-layer turns moving obstacles into static ones","Provably ε-optimal reach-avoid policies with time-varying obstacles","Reach-avoid under shifting hazards: a state-time lift","Max reach-avoid odds with moving obstacles via a two-state trick"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire reduction rests on the claim that an optimal strategy can be chosen to depend only on the current state and the number of jumps so far, not on the exact amount of time left before the deadline.","fun_headline_variants_meta":{"raw":{"variants":["Moving obstacles? Lift time into the state and solve reach-avoid","Adding a time-layer turns moving obstacles into static ones","Provably ε-optimal reach-avoid policies with time-varying obstacles","Reach-avoid under shifting hazards: a state-time lift","Max reach-avoid odds with moving obstacles via a two-state trick"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000817,"raw_usage":{"total_tokens":3605,"prompt_tokens":995,"completion_tokens":2610,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":611,"completion_tokens_details":{"reasoning_tokens":2523}},"tokens_in":611,"tokens_out":2610,"duration_ms":22094,"temperature":1.0,"reasoning_tokens":2523,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:54:09.222211+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take two states plus a target, choose deterministic sojourn times, and let one action at the first decision epoch be optimal only when the remaining time exceeds a threshold; compute the reach-avoid probability under the best randomized Markov policy depending only on $(X_{\\sigma_n}, n)$ and compare it with the supremum over all policies that may use the exact remaining time $T-\\sigma_n$. If the latter is strictly larger, Proposition 2.2 fails, and with it the equivalence used by Algorithm 4.1.","supporting_citations":[{"cited_title":"& Junca, M","cited_arxiv_id":null,"evidence_quote":"Provides the long-run average transformation for fixed-obstacle reach-avoid that the paper shows cannot apply directly to time-varying obstacles, motivating the new value-type algorithm."},{"cited_title":"& Lygeros, J","cited_arxiv_id":null,"evidence_quote":"Gives the existence of optimal reach-avoid policies in discrete-time MDPs that the paper's stationary-policy existence theorem parallels."},{"cited_title":"& Rieder, U","cited_arxiv_id":null,"evidence_quote":"Supplies the state-space enlargement technique that the transferred method adapts to handle time-varying obstacles."},{"cited_title":"H., Guo, X","cited_arxiv_id":null,"evidence_quote":"Supplies Assumption 2.1 and the sufficient condition used to prevent infinitely many jumps in a finite horizon."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the convolution bound used to establish the explicit iteration count and epsilon-optimality in Proposition 4.2."},{"cited_title":"On reachability of Markov decision processes: a novel state-classification-based PI approach","cited_arxiv_id":"2308.06298","evidence_quote":"Provides a state-classification policy-iteration approach for MDP reach-avoid that this paper contrasts with its improved value-type method."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Treats reach-avoid under embedded Markov chains in continuous-time controlled Markov systems, the semi-Markov analogue this paper extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard reduction argument used in Proposition 2.2 to replace history-dependent policies by Markov policies."}],"review_version":1}