Consider a Markov decision process $M$ with an initial state $s_0$ and a set of goal states $S_G$. We can view $M$ as a graph with two types of edges (nondeterministic and probabilistic ones). Now consider the set $E_G$ of all edges that lie on a path from $s_0$ to some state in $S_G$ (i.e., every edge in $E_G$ lies on such a path, and for every such path, all its edges are in $E_G$). Now let $M_G$ be the subgraph of $M$ induced by $E_G$. If necessary, we add a sink state to $M_G$ with probabilistic edges going into it, to ensure that the probabilities in each distribution sum to 1.
Two questions:
- It should be straightforward to show that $M$ and $M_G$ agree on all
minimum andmaximum reachability probabilities for all states in $S_G$. Is anybody aware of such a result having been published? - Is there a name for such a subgraph? Path-covering subgraph or something like that?
