## Abstract

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*·|A|*^{O(k)}*, where |A| is the bit encoding length of*^{O(1)}*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.Original language | English |
---|---|

Title of host publication | Reachability Problems (RP 2020) |

Editors | Sylvain Schmitz, Igor Potapov |

Publisher | Springer |

Pages | 67-82 |

Number of pages | 16 |

ISBN (Electronic) | 978-3-030-61739-4 |

ISBN (Print) | 978-3-030-61738-7 |

DOIs | |

Publication status | Published - 15 Oct 2020 |

Event | 14th International Conference on Reachability Problems - Paris, France Duration: 19 Oct 2020 → 21 Oct 2020 https://www.irif.fr/~rp2020/ |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 12448 |

ISSN (Print) | 1611-3349 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 14th International Conference on Reachability Problems |
---|---|

Abbreviated title | IRIF 2020 |

Country | France |

City | Paris |

Period | 19/10/20 → 21/10/20 |

Internet address |

## Keywords

- markov decision processes
- branching processes
- stochastic context-free grammars
- multi-objective
- reachability
- almost-sure
- limit-sure