Metraipolis › archive › dc_06a044c8c381
Supermartingale Certificates for Parametric MDPs — arXiv:2609.12715
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.12715
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T03:03:35.134Z
- SHA-256 of the archived text
d6551123b95756c9107523536818e91a7f264314362bb2ccab2c11df5d2a70f7- Stable URL of this page
https://metraipolis.com/documento/dc_06a044c8c381
How to cite
Supermartingale Certificates for Parametric MDPs — arXiv:2609.12715 — arXiv (en), https://arxiv.org/abs/2609.12715 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_06a044c8c381 (Metraipolis archive dc_06a044c8c381, sha256 d6551123b95756c9107523536818e91a7f264314362bb2ccab2c11df5d2a70f7)
BibTeX
@misc{dc06a044c8c381,
title = {Supermartingale Certificates for Parametric MDPs — arXiv:2609.12715},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.12715},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_06a044c8c381; sha256 d6551123b95756c9107523536818e91a7f264314362bb2ccab2c11df5d2a70f7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12715. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We consider the problems of formal verification and synthesis in parametric Markov decision processes (MDPs) with general measurable state and action spaces. The heart of our approach is a parameter flattening transformation, which allows us to transform parametric MDPs into semantically equivalent non-parametric MDPs. Building on this transformation, we introduce the novel notion of parametric supermartingale certificates, which generalize the traditional supermartingale certificates---used for non-parametric MDPs---to the parametric setting. We use our parametric supermartingale certificates to design algorithms for verification and approximate synthesis in polynomial arithmetic parametric MDPs. This leads to the first verification and synthesis algorithms for parametric MDPs with general state and action spaces. We implement our algorithms and experimentally evaluate them on several continuous parametric random walk benchmarks. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-14 in cs.AI). Categorie arXiv: Logic in Computer Science (cs.LO) ; Artificial Intelligence (cs.AI); Systems and Control (eess.SY). Pagina del lavoro: https://arxiv.org/abs/2609.12715 — 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-10-16T02:51:27.938Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).