Qualitative Multi-Objective Reachability for Ordered Branching MDPs

Kousha Etessami, Emanuel Martinov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 2O(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.
Original languageEnglish
Title of host publicationReachability Problems (RP 2020)
EditorsSylvain Schmitz, Igor Potapov
PublisherSpringer
Pages67-82
Number of pages16
ISBN (Electronic)978-3-030-61739-4
ISBN (Print)978-3-030-61738-7
DOIs
Publication statusPublished - 15 Oct 2020
Event14th International Conference on Reachability Problems - Paris, France
Duration: 19 Oct 202021 Oct 2020
https://www.irif.fr/~rp2020/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12448
ISSN (Print)1611-3349
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Reachability Problems
Abbreviated titleIRIF 2020
CountryFrance
CityParis
Period19/10/2021/10/20
Internet address

Keywords

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

Fingerprint

Dive into the research topics of 'Qualitative Multi-Objective Reachability for Ordered Branching MDPs'. Together they form a unique fingerprint.

Cite this