CS Paper Radar

Polynomial VASS MDPs

Michal Ajdarow

cs.LO ·submitted 2026-11-02 23:45 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy

cs.LG cs.DSmath.OC ·2026-09-30 ·Han Zhong, Yinyu Ye
highly cited similarity 0.63
Abstract · Added results on average-reward MDPs and extended the discounted lower bounds to constant-bit integer rewards

We establish exponential iteration lower bounds in the number of states for Howard's policy iteration on deterministic discounted and average-reward Markov decision processes (MDPs), with a constant number of actions per state. This rules out strong polynomiality of Howard's policy iteration in both settings. We further prove that a Dantzig counterpart of Howard's policy iteration runs in strongly polynomial time on deterministic average-reward MDPs. Together with the known strongly polynomial bound for Dantzig's rule on deterministic discounted MDPs, these results establish an exponential separation between the two algorithms in both settings. This separation between Howard's decentralized and simultaneous selfish improvements and Dantzig's coordinated selection of a single action with the largest improvement across all states reveals a ``price'' of algorithmic anarchy.

0.42

Polynomial Invariants for Probabilistic Transition Systems with Unbounded Support

cs.LO ·2026-09-02 ·Anne Schreuder, Lorenz Winkler, Laura Kovács, C. -H. Luke Ong
publishedtheory similarity 0.63
Abstract · 16 pages + 19 pages appendix, extended version of submission accepted at LPAR'26

We study the synthesis of polynomial invariants for probabilistic transition systems (PTS) based on martingale theory. We present tractable methods to verify that such polynomials are indeed invariants, in the sense that their expected value upon termination is the same as their value at the start of the computation. We do this by applying the Optional Stopping Theorem (OST) in the form of a specific precondition. This precondition requires the existence of an integrable dominating function for the martingale expression, which implies uniform integrability; we refer to this condition as dui. For linear PTS we simplify the dui property to proving finiteness of the expected value of an expression depending on the update matrix, the degree of the martingale expression, and the stopping time. Specifically, if all random samples have finite moments and we can verify a moment bound on the runtime of a linear loop, then we can automatically synthesise polynomial loop invariants that satisfy the OST. Notably, dui allows for the sampled distributions to have unbounded support, which is a novel contribution to the field.

0.40

Reachability in Five-Dimensional Vector Addition Systems Is PSPACE-Complete

cs.FL cs.CC ·2026-10-29 ·Weijun Chen, Bo Fu, Yuxi Fu
theory similarity 0.63
Abstract · 69 pages,1 figure

Vector addition systems (VAS) are a fundamental model of concurrent computation in which transitions update nonnegative integer counters by adding integer vectors, provided all counters remain nonnegative. Closely related to Petri nets, VAS are the single-state counterpart of vector addition systems with states (VASS), which use finitely many states to restrict the available transitions. A classical simulation of $d$-VASS by $(d+3)$-VAS connects their reachability problems, but the complexity-theoretic picture of fixed-dimensional VAS remains largely unclear. While reachability in $2$-VASS is PSPACE-complete under binary encoding, the best known upper bound for $5$-VAS was only elementary. We prove that every reachable $5$-VAS instance has a reachability witness of length polynomial in its unary size. Consequently, $5$-VAS reachability is NL-complete under unary encoding and PSPACE-complete under binary encoding. We also establish a polynomial factorization of the reachability relation of every $d$-VAS with $d \ge 3$. For $5$-VAS, this strengthens Hopcroft and Pansiot's effective semilinearity of reachability sets to the full reachability relation. For every fixed $d\ge3$, it also yields an $\mathsf F_d$ upper bound for reachability in $(d+3)$-VAS.

0.16

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

Integer reachability in VASS with transfers: a refined complexity analysis

cs.FL cs.CC ·2026-10-01 ·Tymoteusz Kucharek, Piotr Hofman
published similarity 0.63
Abstract · Full version of the paper accepted at FSTTCS 2026

Integer reachability is NP-complete for vector addition systems with states (VASS), but becomes PSPACE-complete in the presence of transfer operations. We refine this complexity gap for single-transfer VASS by identifying structural features of transfers responsible for the increase in complexity. Each system induces a transfer graph whose vertices are counters and whose edges represent possible transfers. We classify its vertices as good or bad, according to the branching and cyclic structure of their reachable subgraphs. Let $b$ be the number of bad vertices. We show that every positive instance admits a polynomially verifiable certificate of size $|I|^{O(b+1)}$, where $|I|$ is the input size. Consequently, integer reachability for single-transfer VASS can be decided in nondeterministic time $|I|^{O(b+1)}$; in particular, it belongs to NP for every class with a bounded number of bad counters. Conversely, we show that bad counters provide sufficient structural power to encode space-bounded computation. For every transfer graph with $b$ bad vertices, we construct a single-transfer VASS that encodes the acceptance of a Turing machine using $b^{O(1)}$ tape cells. This yields PSPACE-hardness for every polynomial-time constructible family of transfer graphs containing linearly many bad vertices. Our results isolate the transfer patterns responsible for the complexity of integer reachability.

0.18

Certifying Almost-Sure Reachability in Unknown MDPs

cs.LO cs.AI ·2026-10-13 ·S Akshay, Suguman Bansal, Gaurav Mahla
theory similarity 0.62
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

Quantitative Reachability Properties Beyond Decisiveness

cs.LO cs.FL ·2026-10-26 ·Raphaël Faure, Alain Finkel, Lina Ye
similarity 0.61
Abstract · 38 pages

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.

0.23

Computation with Backward Feedback: Power, Observation, and Cost

cs.CC ·2026-11-12 ·Saman Farhat, Farzad Didehvar
similarity 0.61
Abstract

How much can a computation gain by passing information back to an earlier stage, and how soon can an observer obtain the answer? We study deterministic programs whose runs are accessed at randomly selected stages. A program keeps a register, a finite block of memory. A random clock selects the current stage; each tick takes a random step, with a law fixed independently of input, program and register. When the clock moves backward, the register contents at the stage it leaves start a new run, and the clock continues where it lands. Equilibrium readout requires a distribution of clock position and register that one tick leaves unchanged, and a correct final answer under every such distribution. For bounded steps in both directions with negative average, we obtain an exact classification at each polynomial scale s. If running time and register length are both O(s), feedback gives exactly nondeterministic space O(s); without transmission the class is deterministic time O(s), which is strictly smaller. An observer that starts at stage zero with an all-zero register, reads sequentially and never accepts a nonmember sees, with fewer ticks than any exponential, only languages fixed by a bounded input prefix. Exponentially many ticks reveal every linear-time language. For a clock moving one step up or down, we bound the wait for useful backward moves and the rate of random erasures a stored counter tolerates. The results separate the power of feedback at equilibrium, observation from a fixed start, and the cost of obtaining and keeping information.

0.21