CS Paper Radar

Quantitative Reachability Properties Beyond Decisiveness

Raphaël Faure, Alain Finkel, Lina Ye

cs.LO cs.FL ·submitted 2026-10-26 12:12 UTC · v1

Abstract

Decisiveness is central to reachability algorithms for infinite Markov chains, but is a qualitative notion: it guarantees that path-enumeration algorithms terminate, without an a priori bound on the horizon. We study decisiveness quantitatively of Markov chains, and apply our results to the approximate quantitative coverability problem for effective probabilistic well-structured transition systems (pWSTS). We introduce truncation sets, which represent the horizons sufficient to approximate the reachability probability within a precision $\varepsilon$. These sets reformulate decisiveness quantitatively, and their elements can be computed when it is decisive. To obtain such horizons, before any exploration, we introduce geometrically reachable sets, for which the probability of not reaching them within n steps decreases exponentially in n, up to a prefactor depending on the initial state. Horizons valid for all initial states exist iff this prefactor can be chosen uniformly for boundedly coarse chains. For such pWSTS, including probabilistic vector addition systems and Galton-Watson processes, we obtain a priori global horizons growing at most logarithmically in $1/\varepsilon$. In the non-uniform case, we give a drift condition ensuring the existence of a finite geometrically reachable set. Under this condition, we derive a priori horizons growing at most logarithmically in $1/\varepsilon$ and in the weight w(x) measuring the size of the initial state x. In both cases, we compute a horizon function whose evaluation on any initial state and precision requires only a constant number of elementary operations $(+, -, \times, / \text{ and } \log)$. For probabilistic lossy channel systems, this yields, to our knowledge, the first explicit a priori horizons from arbitrary initial states, and it extends to $ν$-pLCS, a new infinitely branching variant with probabilistic emissions.

Comment
38 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Quantitative coverability for probabilistic well-structured transition systems

cs.LO cs.FL ·2026-09-22 ·Raphaël Faure, Alain Finkel, Gaspard Fougea, Lina Ye
similarity 0.82
Abstract · 25 pages

Well-structured transition systems (WSTS) provide a classical framework for the verification of infinite-state systems, but their probabilistic extensions lack a unified treatment of quantitative coverability: path-enumeration algorithms assume a finite branching degree, while alternative approximation schemes defer some computations, such as probabilities over a bounded horizon, to the model at hand. We introduce probabilistic well-structured transition systems (pWSTS), Markov chains over countable state sets whose underlying transition systems are WSTS, with no a priori assumption on the branching degree. This class encompasses any WSTS equipped with a Markov kernel, such as probabilistic vector addition systems (pVAS) and probabilistic lossy channel systems (pLCS). For an effective subclass, we solve the approximate quantitative coverability problem over bounded horizons, and over infinite horizons under decisiveness, requiring no probabilistic information beyond individual transition probabilities. We then identify a general source of decisiveness: every stochastically monotone pWSTS is decisive with respect to every upward-closed set. We finally instantiate the framework on multi-type Galton--Watson processes, a classical model of population dynamics whose offspring distributions may have infinite support. Under mild assumptions on the reproduction laws, these processes are effective pWSTS, and they are stochastically monotone, hence decisive. Approximate quantitative coverability is therefore computable for them over both horizons, with a proof that uses none of the traditional tools: neither generating functions nor any case distinction between regimes.

0.41

Converse Barrier Certificates for Set-Based Stochastic Reach-Avoid Verification

eess.SY ·2026-08-31 ·Bai Xue, C. -H. Luke Ong
similarity 0.68
Abstract

Recent work established sufficient and necessary barrier-like conditions for infinite-horizon reach-avoid verification of stochastic discrete-time systems from a single initial state. Whether such a converse characterization extends to a set of initial states, however, remains open. In this paper, we answer this question affirmatively for compact initial sets. We consider a uniform reach-avoid specification requiring the reach-avoid probability to exceed a prescribed threshold for every initial state in a compact set. Under appropriate assumptions, including continuous system transitions, together with a strict uniform probability margin, we extend the pointwise converse characterization to the uniform setting.

0.42

Harmonic-Mean Aggregation of Continuous-Time Markov Chains with Reachability Error Bounds

cs.LO ·2026-11-16 ·Bingqing Hu, Landon Taylor, Zhen Zhang
similarity 0.67
Abstract

Abstracting a continuous-time Markov chain by grouping its states into blocks raises a fundamental question: which rates should the abstract chain use when states within a block have different exit rates and transition probabilities? We study harmonic-mean aggregation, which matches the mean waiting time and next-block distribution of a local experiment that uniformly selects a state within the block and observes its next jump. Equivalently, the abstract transition rates are averages of the concrete rates with inverse-exit-rate weights. Since the aggregation does not preserve reachability probabilities in general, we derive theoretical error bounds for time-bounded reachability. We decompose the error into a blockwise mean and centered-within-block deviations, and show that the rate mismatch has zero weighted mean. Exploiting this cancellation and differences between abstract reachability values, we obtain bounds valid at every time horizon through a linear comparison system with two quantities per block, without computing concrete reachability values. All results are formalized and proven in Lean 4.

0.25

Path Abstraction for Markov Reward Models

cs.FL cs.LO ·2026-08-25 ·Arnd Hartmanns, Robert Modderman
theory similarity 0.64
Abstract

Path abstraction originated as a technique for counterexample refinement in probabilistic model checking. Given a discrete-time Markov chain, it summarises the probabilities passing through a subset of the states onto new transitions of a smaller chain. In earlier work, we proved its correctness and that it is monotonically absorbing. In this paper, we extend path abstraction from reachability probabilities on discrete-time Markov chains to expected rewards on Markov reward models. Working in a novel free monoid view of Markov chains throughout, we prove that path abstraction preserves the Markov reward model structure when abstracting over arbitrary sets of states, and that it remains monotonically absorbing. Finally, we give a numerical recipe, accompanied by a reference implementation in PARI/GP, that computes path abstraction by solving linear equation systems. Its correctness rests on the relationship between expected rewards and expected visiting times of transitions.

0.19

Polynomial VASS MDPs

cs.LO ·2026-11-02 ·Michal Ajdarow
similarity 0.61
Abstract

Markov decision process over vector addition system with states (VASS MDP) is a finite state model combining non-deterministic and probabilistic behavior, augmented with non-negative integer counters that can be incremented or decremented during each state transition. VASS MDPs can serve as abstractions of probabilistic programs, offering many decidable properties. In this paper, we develop techniques for analyzing the polynomiality of asymptotic estimates for VASS MDPs. That is, for every initial configuration of size \(n\), we consider the number of transitions needed to reach a configuration with some counter negative. We show that for any VASS MDP, either for all \(ε>0 \) and all sufficiently large \(n\) the number of transitions is at least \(2^{n^{\frac{1}{2}-ε}} \) with probability at least \(1-ε\), or for any superpolynomial function \(f \), all \(ε>0 \) and all sufficiently large \(n\) the number of transitions is upper bounded by \(f(n) \) with probability at least \(1-ε\). Furthermore, if the VASS MDP is DAG-like then we can replace \(f(n)\) with \(n^{k+ε} \), where \(k=2\cdot 3^{w\cdot d+|T|} \) and \(w,d\) and \(T \) are the number of MECs, counters and transitions of the VASS MDP, respectively. It is decidable in polynomial time which case holds.

0.30

Bridging the Gap Between Plain VASS and Branching VASS

cs.LO cs.FL ·2026-09-14 ·Clotilde Bizière, Jérôme Leroux, Grégoire Sutre
publishedtheory similarity 0.61
Abstract · 25 pages, extended version of the paper with same title and same authors presented at FOSSACS'26

Vectors addition systems with states (VASS), a model equivalent to Petri nets, are finite-state machines with finitely many counters ranging over the natural numbers. The decidable reachability problem for VASS has many applications in logic, automata, and verification. In this paper we study the reachability problem for BVASS, a branching generalization of VASS. We show that BVASS reachability sets are very similar to VASS reachability sets, namely that they are sections of VASS. Our proof relies on a new well-quasi-order (wqo) on BVASS runs that generalizes the well-known wqo on VASS runs. By leveraging an amalgamation property, we prove that every BVASS run can be transformed into an equivalent one of bounded branching complexity. This allows us to derive several results on the geometry of BVASS reachability sets. As an application we obtain that reachability sets of 5-dimensional BVAS are effectively semilinear, as is the case for 5-dimensional VAS.

0.58

Subprocess-Constrained Markov Decision Processes

cs.AI ·2026-11-16 ·Jiarui Gan, Debmalya Mandal
top venuecode/data similarity 0.60
Abstract · To appear at NeurIPS '26. Code available at https://github.com/jrgan/VSI

Constrained Markov decision processes (CMDPs) typically bound expected cumulative cost from an initial state. Such a guarantee can be insufficient when a policy must remain feasible after every history it may encounter. We introduce \emph{subprocess-constrained MDPs} (S-CMDPs), which require the expected discounted cost of each continuation, conditional on any reachable history, to satisfy a bound determined by the current state. This stronger requirement changes the structure and complexity of the problem: we show that stationary policies can be strictly suboptimal, and finding even an approximately optimal stationary policy is NP-hard. We adapt a recently introduced value-set iteration framework to show that history-dependent policies surprisingly overcome both obstacles. Our polynomial-time algorithm represents such a policy implicitly: its expected reward is within $ε$ of the optimal feasible value, it violates each subprocess cost bound by at most $δ$, and its action distribution can be computed in polynomial time for any given history.

0.53

Certifying Almost-Sure Reachability in Unknown MDPs

cs.LO cs.AI ·2026-10-13 ·S Akshay, Suguman Bansal, Gaurav Mahla
theory similarity 0.60
Abstract

{\em Specification-Guided Reinforcement Learning (RL)} has largely concerned itself with \emph{learning} an optimal policy against a formal specification in an unknown {\em Markov Decision Process (MDP)}. We take up the dual question. Given a policy already in hand, can one \emph{verify} that it is correct against a formal specification in an unknown MDP, using sampling access alone? Such a question arises naturally in safety-critical systems. We investigate it for the {\em almost-sure reachability property}, whose correctness is witnessed by a {\em ranking supermartingale (RSM)} certificate. Our first finding is negative. In the absence of any further information about the MDP, one can neither learn such a certificate nor verify a candidate one with probabilistic guarantees. On the positive side, we show that, under a mild restriction, a known lower bound $p_{\min}$ on nonzero transition probabilities, a correct certificate \emph{can} be learned with PAC-style guarantees. To the best of our knowledge, this is the first study of learning and verifying certificates for almost-sure reachability in unknown MDPs from sampling access alone. Finally, our experiments show that the $p_{\min}$-based sufficient condition, while sound, is conservative: the learned certificate often remains valid on the true MDP even when the condition fails.

0.07