Pith. sign in

REVIEW 3 major objections 5 minor 30 references

Reach-avoid semi-Markov decision processes with time-varying obstacles

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict The layered-state idea is worthwhile, but the Markov-policy reduction is wrong, so the algorithm solves a weaker problem than the one advertised. read the letter →

arxiv 2505.02479 v1 pith:MUJZQO6H submitted 2025-05-05 math.PR

Yanyun Li , Xianping Guo This is my paper · ORCID
classification math.PR MSC 91A1591A25
keywords reach-avoidprobabilityfinitehorizonsemi-Markovdecisionprocessestime-varyingobstaclesnon-homogeneousmodelequivalenttwo-dimensionalepsilon-optimalpolicyvalueiterationalgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [§2, Proposition 2.2 and Eq. (2.9)] 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.
  2. [§3, Theorem 3.1 and Eq. (3.16)] 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.
  3. [§4, Theorem 4.1 and Algorithm 4.1] 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.
minor comments (5)
  1. [§2, Eq. (2.9)] 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.
  2. [§4, Algorithm 4.1, Step 1] The displayed formula for W_0(x,n_Ɩ̃,T) contains a stray closing brace after the maximum; this typo should be corrected.
  3. [§4, Remark 4.1] 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.
  4. [§5, Example 5.1] 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.
  5. [§5, Figures 1–3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the reach-avoid value is obtained by standard dynamic programming on an equivalent layered model; no fitted parameter or self-citation chain forces the result.

full rationale

The paper's derivation chain is self-contained. G*(x,t) is defined as a supremum over all history-dependent policies, and Proposition 2.2 proposes a reduction to randomized Markov policies by matching one-step and marginal distributions; whether that reduction is valid is a correctness question, not a circularity. Theorem 3.1 embeds these policies into stationary policies of the layered model (3.5) and proves equality of reach-avoid probabilities by explicitly matching the finite-dimensional transition distributions F_n and tilde-F_n. Theorem 4.1 proves the optimality equation and the existence of a deterministic stationary optimal policy using Assumption 2.1, finite action sets, and the successive-approximation argument of Proposition 4.1, which is proved in the paper from the renewal bound in [21]. Theorem 4.3 and Proposition 4.2 give the monotone convergence of W_n to tilde-G* and a quantitative error bound; neither involves fitting any parameter to the target value. The numerical example takes model data from Table 1 as fixed inputs and reports the algorithm's output; no constant is calibrated against G*(x,T), so the computed values are not predictions forced by construction. The few self-citations, such as [17] and [18] for Assumption 2.1 and its sufficient condition, support ancillary assumptions and are not load-bearing for the main equivalence or algorithm. Any concern about Proposition 2.2 failing for finite horizons would be a mathematical-correctness risk, not a circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The central derivation rests on standard measure-theoretic dynamic programming and the stated semi-Markov assumptions. The critical unproven premise is the sufficiency of Markov policies that ignore the residual time (Proposition 2.2), which is false in general; this is why the computed value can be a lower bound rather than G*. No free parameters are fitted to support the theory; the numerical example uses tabulated model inputs.

assumptions (4)
  • domain assumption Assumption 2.1: P_x^π(lim_n σ_n = ∞) = 1 for all x and π.
    Ensures only finitely many decision epochs occur within the finite horizon [0,T]; standard for semi-Markov decision processes and stated explicitly in Section 2.
  • domain assumption The target set C is uniformly absorbing: Q(C, ∞ | x, a) = 1 for all x ∈ C, a ∈ A(x).
    Makes the reach-avoid problem well-defined and lets the layered model treat C̃ as absorbing; stated in Section 2 before Definition 2.3.
  • ad hoc to paper Randomized Markov policies depending only on (X_{σ_n}, n) are sufficient for the finite-horizon reach-avoid optimality.
    Proposition 2.2 asserts this reduction, but it is not valid for time-horizon criteria because the optimal action at decision epoch n generally depends on the residual time T - σ_n; this is the load-bearing flaw.
  • ad hoc to paper A deterministic stationary policy f̃* can achieve the maximum in the optimality equation for every remaining time t simultaneously.
    Theorem 4.1 applies Proposition 4.1(a) at t = T only; the argument requires the inequality H ≤ L_{f̃*} H to hold for all t, which assumes a t-independent argmax that is not generally guaranteed.
invented entities (1)
  • Layered state space S = E × Z_+ with layer index n recording the decision-epoch count
    purpose: Converts the non-homogeneous obstacle sequence into a homogeneous model with transitions from layer k to k+1 only.
    This is a mathematical construction, not a physical entity; it is introduced to carry the obstacle index, but it does not carry the elapsed time, which is why the restriction to Markov policies is insufficient.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Reach-avoid semi-Markov decision processes with time-varying obstacles." pith.science (2026). https://pith.science/paper/MUJZQO6H

@misc{pith2026250502479,
  author       = {Pith},
  title        = {Pith review of: Reach-avoid semi-Markov decision processes with time-varying obstacles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MUJZQO6H}},
  note         = {Machine review of arXiv:2505.02479}
}
abstract

We consider the maximal reach-avoid probability to a target in finite horizon for semi-Markov decision processes with time-varying obstacles. Since the variance of the obstacle set, the model \eqref{Model} is non-homogeneous. To overcome such difficulty, we construct a related two-dimensional model \eqref{newModel}, and then prove the equivalence between such reach-avoid probability of the original model and that of the related two-dimensional one. For the related two-dimensional model, we analyze some special characteristics of the equivalent reach-avoid probability. On this basis, we provide a special improved value-type algorithm to obtain the equivalent maximal reach-avoid probability and its $\epsilon$-optimal policy. Then, at the last step of the algorithm, by the equivalence between these two models, we obtain the original maximal reach-avoid probability and its $\epsilon$-optimal policy for the original model.

Figures

Figures reproduced from arXiv: 2505.02479 by the authors.

Figure 1
Figure 1. The values of W1 8 (i, 0, t) with respect to t ∈ [0, 18] [PITH_FULL_IMAGE:figures/full_fig_p023_1.png] view at source ↗
Figure 3
Figure 3. The values of W3 8 (i, 0, t) with respect to t ∈ [0, 18]. Remark 5.1. By Figures 1-2, we see that in the fixed obstacle set case, when the transition probability from regular states (that is, states in E \ (B0 ∪ C)) to the obstacle set is smaller, the maximal reach-avoid probability bigger. However, based on situation (5.2), we change the obstacle state 1 to 0 at decision epochs 3, 4, 5, 6 and obtain situation (5.3)… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    & Junca, M

    ´Avila, D. & Junca, M. (2022). On reachability of Markov chains: a long- run average approach. IEEE Trans. Automat. Control. 67(4), 1996-2003

    work page 2022

  2. [2]

    & Gupta, V

    Af`eche, P., Caldentey, R. & Gupta, V. (2002). On the optimal design of a bipartite matching queueing system. Oper. Res. 70(1), 363-401

    work page 2002

  3. [3]

    & Rieder, U

    B¨auerle, N. & Rieder, U. (2014). More risk-sensitive Markov decision p rocesses. Math. Oper. Res. 39(1), 105-120

    work page 2014

  4. [4]

    & Rieder, U

    B¨auerle, N. & Rieder, U. (2017). Partially observable risk-sensitive Ma rkov decision processes. Math. Oper. Res. 42(4), 1180-1196

    work page 2017

  5. [5]

    & Spanjers, L

    Boda, K., Filar, J., Lin, Y. & Spanjers, L. (2004). Stochastic tar get hitting time and the problem of early retirement. IEEE Trans. Automat. Control. 49(3), 409-419

    work page 2004

  6. [6]

    & Hern´ andez-Hern´andez, D

    Cavazos-Cadena, R. & Hern´ andez-Hern´andez, D. (2011). Discounted approximations for risk-sensitive average criteria in Markov decision chains with finit e state space. Oper. Res. 36(1), 133-146. 24

    work page 2011

  7. [7]

    & Ozekici, S

    Cekyay, B. & Ozekici, S. (2010). Mean time to failure and availability of semi-Markov missions with maximal repair. European J. Oper. Res. 207, 1442-1454

    work page 2010

  8. [8]

    & Lygeros, J

    Chatterjee, D., Cinquemani, E. & Lygeros, J. (2011). Maximizing the probability of attaining a target prior to extinction. Nonlinear Anal. Hybrid Syst. 5(2), 367-381

    work page 2011

Show all 30 references
  1. [9]

    & Krogh, B

    Chutinan, A. & Krogh, B. (2003). Computational techniques fo r hybrid system verifi- cation. IEEE Trans. Automat. Control. 48(1), 64-75

    2003

  2. [10]

    Guo X. P. & Hern´ andez-Lerma, O. (2007). Zero-sum games f or continuous-time jump Markov processes in Polish spaces: discounted payoffs. Adv. in Appl. Probab. 39, 645- 668

    2007

  3. [11]

    P., Liu J

    Guo X. P., Liu J. Y. & Liu, K. (2000). Nonstationary Markov decis ion processes with Borel state space: the average criterion with non-uniformly boun ded rewards. Math. Oper. Res. 24, 667-678

    2000

  4. [12]

    Ghosh, M. K. & Bagchi, A. (1998). Stochastic games with avera ge payoff criterion. Appl. Math. Optim. 38(3), 283-301

    1998

  5. [13]

    Guo X. P. & Shi P. (2001). Limiting average criteria for nonstat ionary Markov decision processes. SIAM J. Optim. 11(4), 1037-1053

    2001

  6. [14]

    & Lasserre, J

    Hern´ andez-Lerma, O. & Lasserre, J. (1996). Discrete-Tim e Markov Control Processes. Springer

    1996

  7. [15]

    Huo, H. F. & Guo, X. P. (2020). Risk probability minimization proble ms for continuous- time Markov decision processes on finite horizon. IEEE Trans. Automat. Control. 65(7), 3199-3206

    2020

  8. [16]

    Huang, X., Guo, X. P. & Wen, X. (2023). Zero-sum games for fin ite-horizon semi-Markov processes under the probability criterion. IEEE Trans. Automat. Control. 68(9), 5560- 5567

    2023

  9. [17]

    Huang, Y. H. & Guo, X. P. (2011). Finite horizon semi-Markov de cision processes with application to maintenance systems. European J. Oper. Res. 212(1), 131-140

    2011

  10. [18]

    H., Guo, X

    Huang, Y. H., Guo, X. P. & Song, X. Y. (2011). Performance an alysis for controlled semi-Markov systems with application to maintenance. J. Optim. Theory Appl. 150(2), 395-415. 25

    2011

  11. [19]

    Mitchell, Alexandre M

    Ian M. Mitchell, Alexandre M. Bayen & Claire J. Tomlin. (2005). A Tim e-Dependent Hamilton–Jacobi Formulation of Reachable Sets for Continuous Dyn amic Games. IEEE Trans. Automat. Control. 50(7), 947-957

    2005

  12. [20]

    & John, L

    Kostas, M. & John, L. (2011). Hamilton-Jacobi formulation fo r reach-avoid differential games. IEEE Trans. Automat. Control. 56(8), 1849-1861

    2011

  13. [21]

    John, W. M. (1986). Successive approximations for finite horiz on, semi-Markov decision processes with application to asset liquidation. Oper. Res. 34(4), 638-644

    1986

  14. [22]

    Lygeros, J. (2004). On reachability and minimum cost optimal co ntrol. Automatica. 40(6), 917-927

    2004

  15. [23]

    E., Zhang

    Love, C. E., Zhang. Z. G., Zitron. M. A. & Guo, R. (2000). A discr ete semi-Markov de- cision model to determine the optimal repair/replacement policy und er general repairs. European J. Oper. Res. 125, 398-409

    2000

  16. [24]

    Liao, W., Liang, T., Wei, X. H. & Yin, Q. Z. (2022). Probabilistic reac h-avoid prob- lems in nondeterministic systems with time-varying targets and obst acles. Appl. Math. Comput. 425, 127-054

    2022

  17. [25]

    Li, Y. Y. & Li, J. P. (2025). The minimal reaching probability of con tinuous-time controlled Markov systems with countable states. System & Control Letters. 196:106002

    2025

  18. [26]

    Y., Guo, X

    Li, Y. Y., Guo, X. & Guo, X. P. (2023). On reachability of Markov d ecision processes: a novel state-classification-based PI approach. https://arxiv.org/pdf/2308.06298

    2023 arXiv

  19. [27]

    & Zhao, H

    Ma, C. & Zhao, H. (2023). Optimal control of probability on a ta rget set for continuous- time Markov chains. IEEE Trans. Automat. Control. 69(2), 1202-1209

    2023

  20. [28]

    Puterman M. L. (1994). Decision processes: discrete stocha stic dynamic programming. John Wiley & Sons Inc., New York,

    1994

  21. [29]

    Singh. S. S., Tadic. V. B. & Doucet. A. (2007). A policy gradient m ethod of semi-Markov decision processes with application to call admission control. European J. Oper. Res. 178, 862-869

    2007

  22. [30]

    & Yang, Y

    Zhang, L., Feng, Z., Jiang, Z., Zhao, N. & Yang, Y. (2020). Impr oved results on reachable set estimation of singular systems. Appl. Math. Comput. 385, 125-419. 26

    2020

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.