Fast Computation of Conditional Probabilities in MDPs and Markov Chain Families
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910215334526976 |
|---|---|
| author | Češka, Milan Junges, Sebastian van der Maas, Luko Macák, Filip Quatmann, Tim |
| author_facet | Češka, Milan Junges, Sebastian van der Maas, Luko Macák, Filip Quatmann, Tim |
| contents | Computing optimal conditional reachability probabilities in Markov decision processes (MDPs) is tractable by a reduction to reachability probabilities. Yet, this reduction yields cyclic, challenging MDPs that are often notoriously hard to solve. We present an alternative, practically efficient method to compute optimal conditional reachabilities. This new method is numerically stable, can decide the threshold problem in linear time on acyclic MDPs, and yields performance comparable to standard reachability queries. We also integrate the method in an abstraction-refinement framework to analyse millions of Markov chains at once. We demonstrate the efficacy of the new methods on benchmarks from Bayesian network analysis, probabilistic programs, and runtime monitoring and show speed-ups up to multiple orders of magnitude. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_11897 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fast Computation of Conditional Probabilities in MDPs and Markov Chain Families Češka, Milan Junges, Sebastian van der Maas, Luko Macák, Filip Quatmann, Tim Logic in Computer Science Computing optimal conditional reachability probabilities in Markov decision processes (MDPs) is tractable by a reduction to reachability probabilities. Yet, this reduction yields cyclic, challenging MDPs that are often notoriously hard to solve. We present an alternative, practically efficient method to compute optimal conditional reachabilities. This new method is numerically stable, can decide the threshold problem in linear time on acyclic MDPs, and yields performance comparable to standard reachability queries. We also integrate the method in an abstraction-refinement framework to analyse millions of Markov chains at once. We demonstrate the efficacy of the new methods on benchmarks from Bayesian network analysis, probabilistic programs, and runtime monitoring and show speed-ups up to multiple orders of magnitude. |
| title | Fast Computation of Conditional Probabilities in MDPs and Markov Chain Families |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2605.11897 |