# The Complexity of Reachability in Parametric Markov Decision Processes

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2020.

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

- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Convex Optimization for Parameter Synthesis in MDPs](https://mlsanity.com/paper/2107.00108/) (2021)
- [Fine-Tuning the Odds in Bayesian Networks](https://mlsanity.com/paper/2105.14371/) (2021)
- [Efficient Sensitivity Analysis for Parametric Robust Markov Chains](https://mlsanity.com/paper/2305.01473/) (2023)
- [Graph-Based Reductions for Parametric and Weighted MDPs](https://mlsanity.com/paper/2305.05739/) (2023)
- [Qualitative Analysis of ω-Regular Objectives on Robust MDPs](https://mlsanity.com/paper/2505.04539/) (2025)
- [Adversarial Robustness Verification and Attack Synthesis in Stochastic Systems](https://mlsanity.com/paper/2110.02125/) (2021)
- [Lecture Notes on Partially Known MDPs](https://mlsanity.com/paper/2112.02976/) (2021)
- [Analyzing Value Functions of States in Parametric Markov Chains](https://mlsanity.com/paper/2504.17020/) (2025)
- [PAC Approximation and DIRECT Optimization for Parametric Markov Models](https://mlsanity.com/paper/2608.02184/) (2026)

## Abstract (arXiv)

This article presents the complexity of reachability decision problems for parametric Markov decision processes (pMDPs), an extension to Markov decision processes (MDPs) where transitions probabilities are described by polynomials over a finite set of parameters. In particular, we study the complexity of finding values for these parameters such that the induced MDP satisfies some maximal or minimal reachability probability constraints. We discuss different variants depending on the comparison operator in the constraints and the domain of the parameter values. We improve all known lower bounds for this problem, and notably provide ETR-completeness results for distinct variants of this problem.