Metraipolis › archive › dc_51f2e864342c

Polynomial VASS MDPs — arXiv:2611.04082

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.04082
License (as archived): CC0-1.0
Archived: 2026-11-04T19:07:49.594Z
SHA-256 of the archived text: be7e148acc2c629bd18fe3401037d3b8fc61dc6cb40cad1803db782e6eece54e
Stable URL of this page: https://metraipolis.com/documento/dc_51f2e864342c

How to cite

Polynomial VASS MDPs — arXiv:2611.04082 — arXiv (en), https://arxiv.org/abs/2611.04082 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_51f2e864342c (Metraipolis archive dc_51f2e864342c, sha256 be7e148acc2c629bd18fe3401037d3b8fc61dc6cb40cad1803db782e6eece54e)

BibTeX

@misc{dc51f2e864342c,
  title = {Polynomial VASS MDPs — arXiv:2611.04082},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04082},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_51f2e864342c; sha256 be7e148acc2c629bd18fe3401037d3b8fc61dc6cb40cad1803db782e6eece54e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04082. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 \(\epsilon>0 \) and all sufficiently large \(n\) the number of transitions is at least \(2^{n^{\frac{1}{2}-\epsilon}} \) with probability at least \(1-\epsilon \), or for any superpolynomial function \(f \), all \(\epsilon>0 \) and all sufficiently large \(n\) the number of transitions is upper bounded by \(f(n) \) with probability at least \(1-\epsilon \). Furthermore, if the VASS MDP is DAG-like then we can replace \(f(n)\) with \(n^{k+\epsilon} \), 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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.LO, nuovi lavori del giorno).
Categorie arXiv: Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2611.04082 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:41:07.426Z dalla pagina https://arxiv.org/list/cs.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).