Graph-Based Reductions for Parametric and Weighted MDPs

Kasper Engelen, Guillermo A. Pérez, Shrisha Rao

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 th…