# Graph-Based Reductions for Parametric and Weighted MDPs

arXiv: https://arxiv.org/abs/2305.05739 · HTML: https://mlsanity.com/paper/2305.05739/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 9 May 2023.

## Builds on (most cited first, 7 of 7)

- [The Probabilistic Model Checker Storm](https://mlsanity.com/paper/2002.07080/) (2020)
- [Verification of Markov Decision Processes using Learning Algorithms](https://mlsanity.com/paper/1402.2967/) (2014)
- [The Complexity of Reachability in Parametric Markov Decision Processes](https://mlsanity.com/paper/2009.13128/) (2020)
- [A Practitioner's Guide to MDP Model Checking Algorithms](https://mlsanity.com/paper/2301.10197/) (2023)
- [Are Parametric Markov Chains Monotonic?](https://mlsanity.com/paper/1907.08491/) (2019)
- [The Complexity of Graph-Based Reductions for Reachability in Markov Decision Processes](https://mlsanity.com/paper/1710.07903/) (2017)
- [Out of Control: Reducing Probabilistic Models by Control-State Elimination](https://mlsanity.com/paper/2011.00983/) (2020)

## Built on by (most cited first, 2 of 2)

- [What Are the Odds? Improving the foundations of Statistical Model Checking](https://mlsanity.com/paper/2404.05424/) (2024)
- [Analyzing Value Functions of States in Parametric Markov Chains](https://mlsanity.com/paper/2504.17020/) (2025)

## Abstract (arXiv)

We study the complexity of reductions for weighted reachability in parametric Markov decision processes. That is, we say a state p is never worse than q if for all valuations of the polynomial indeterminates it is the case that the maximal expected weight that can be reached from p is greater than the same value from q. In terms of computational complexity, we establish that determining whether p is never worse than q is coETR-complete. On the positive side, we give a polynomial-time algorithm to compute the equivalence classes of the order we study for Markov chains. Additionally, we describe and implement two inference rules to under-approximate the never-worse relation and empirically show that it can be used as an efficient preprocessing step for the analysis of large Markov decision processes.