Qualitative Multi-Objective Reachability for Ordered Branching MDPs

We study qualitative multi-objective reachability problems for Ordered Branching Markov Decision Processes (OBMDPs), or equivalently context-free MDPs, building on prior results for single-target reachability on Branching Markov Decision Processes (BMDPs). We provide two separate algorithms for “almost-sure” and “limit-sure” multi-target reachability for OBMDPs. Specifically, given an OBMDP, A, given a starting non-terminal, and given a set of target non-terminals K of size k = |K|, our first algorithm decides whether the supremum probability, of generating a tree that contains every target non-terminal inset K, is 1. Our second algorithm decides whether there is a strategy for the player to almost-surely (with probability 1) generate a tree that contains every target non-terminal in set K. The two separate algorithms are needed: we give examples showing that indeed “almost-sure” ≠ “limit-sure” for multi-target reachability in OBMDPs. Both algorithms run intime 2^O(k)·|A|^O(1), where |A| is the bit encoding length of A. Hence they run in P-time when k is fixed, and are fixed-parameter tractable with respect to k. Moreover, we show that the qualitative almost-sure (and limit-sure) multi-target reachability decision problem is in general NP-hard, when k is not fixed.