nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Qualitative Multi-objective Reachability for Ordered Branching MDPs

verfasst von : Kousha Etessami, Emanuel Martinov

Erschienen in: Reachability Problems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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, \(\mathcal {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 in set 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” \(\not =\) “limit-sure” for multi-target reachability in OBMDPs. Both algorithms run in time \(2^{O(k)} \cdot |\mathcal {A}|^{O(1)}\), where \(|\mathcal {A}|\) is the bit encoding length of \(\mathcal {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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Case Study: Reachability and Scalability in a Unified Combat-Command-and-Control Model

Nächstes Kapitel Quantum-over-Classical Advantage in Solving Multiplayer Games

The notion of general “strategy” employed for BMDPs in [8] is somewhat different than what we define in this paper for OBMDPs: it allows the controller to not only base its choice at a tree node on the ancestor chain of that node, but on the entire tree up to that “generation”. This is needed for BMDPs because there is no ordering available on “siblings” in the tree generated by a BMDP. However, a careful look shows that the results of [8] imply that, for OBMDPs, for single-target reachability, almost-sure and limit-sure reachability also coincide under the notion of “strategy” we have defined in this paper, where choices are based only on the “ancestor history” (with ordering information) of each node in the ordered tree. In particular the key"queen/workers" strategy employed for almost-sure (=limit-sure) reachability in [8] can be mimicked using the ordering with respect to siblings that is available in ancestor histories of OBMDPs.

This strategy is, however, necessarily not “static”, meaning it must actually use the ancestor history: the action distribution cannot be defined solely based on which non-terminal is being expanded.

Equivalent w.r.t. all (multi-objective) reachability objectives we consider.

We assume, without loss of generality, that for \(0 \le t < t' \le m_i\), \(T_{j_t} \ne T_{j_{t'}}\).

Here ‘l’, ‘r’, and ‘u’, stand for ‘left’, ‘right’, and ‘unique’ child, respectively.

To avoid confusion, note that subderivation and subplay have very different meanings. Saying derivation X is a “subderivation” of \(X'\), means that in a sense X is a “prefix” of \(X'\), as an ordered tree. Saying play X is a subplay of play \(X'\), means X is a “suffix” of \(X'\), more specifically X is a subtree rooted at a specific node of \(X'\).

The fact that these statements are equivalent is easy to prove; see the full version.

Technically, as given, this OBMDP in not in simple normal form; but this can easily be rectified by using an auxiliary branching non-terminal, Q, adding the rule \(Q \xrightarrow {1} M \; A\) and changing the rule \(M \xrightarrow {a} M \; A\) to \(M \xrightarrow {a} Q\).

In [4], maximal end-components are referred to as closed components.

Note that this differs crucially from the situation in the limit-sure algorithm, where the other spawned children of these branching nodes in C were only able to reach a non-empty subset \(P_C\) of \(K'\) with a positive probability (bounded away from zero), not necessarily the entire set \(K'\).

A helpful observation here is this: in the limit-sure algorithm we were identifying MECs, where the choice of when to “exit” the MEC is entirely controlled by the player. In the almost-sure algorithm we instead identify SCCs. Even though there may also be purely probabilistic (i.e., not controlled) opportunities of “exiting” such a “good” SCC, C (specifically, an SCC C that is identified and used in step II.8.), due to the way the set \(F_{K'} = X - S_{K'}\) is constructed (and due to properties of its associated witness strategy \(\sigma _{K'}^*\), which is described in the full proof), we can show that even when C is “exited” we still stay inside the set \(F_{K'}\), and eventually hit a SCC, \(C'\), which can only be “exited” probabilistically to \(D_{K'}\), and where, moreover, for each target in \(K'\) there is a branching (Q-Form) node in the SCC, \(C'\), whose “extra” child can hit that target with positive probability (bounded away from zero).

Bozic, I., et al.: Evolutionary dynamics of cancer in response to targeted combination therapy. eLife 2, e00747 (2013) CrossRef

Chatterjee, K., Henzinger, M.: Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition. J. ACM 61(3), 15:1–15:40 (2014)MATHCrossRef

Chen, T., Dräger, K., Kiefer, S.: Model checking stochastic branching processes. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 271–282. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32589-2_26CrossRef

Courcoubetis, C., Yannakakis, M.: Markov decision processes and regular events. IEEE Trans. Autom. Control 43(10), 1399–1418 (1998)MathSciNetMATHCrossRef

Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998)MATHCrossRef

Etessami, K., Stewart, A., Yannakakis, M.: A Polynomial-time algorithm for computing extinction probabilities of multi-type branching processes. SIAM J. Computing 46(5), 1515–1553 (2017). (Incorporates part of the work of a conference paper in STOC 2012.)MathSciNetMATHCrossRef

Etessami, K., Stewart, A., Yannakakis, M.: Polynomial time algorithms for branching Markov decision processes and probabilistic min(max) polynomial Bellman equations. Math. Oper. Res. 45(1), 34–62 (2020). (Conference version in ICALP’12.)MathSciNetMATHCrossRef

Etessami, K., Stewart, A., Yannakakis, M.: Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes. Inf. Comput. 261(2), 355–382 (2018). (Conference version in ICALP 2015.)MathSciNetMATHCrossRef

Etessami, K., Martinov, E., Stewart, A., Yannakakis, M.: Reachability for branching concurrent stochastic games. In: Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP) (2019). (All references are to the full preprint arXiv:1806.03907.)

10.

Etessami, K., Martinov, E.: Qualitative multi-objective reachability for ordered branching MDPs. Full preprint arXiv:2008.10591 (2020)

11.

Etessami, K., Kwiatkowska, M., Vardi, M.Y., Yannakakis, M.: Multi-objective model checking of Markov decision processes. LMCS 4(4), (2008)

12.

Etessami, K., Yannakakis, M.: Recursive concurrent stochastic games. LMCS 4(4), (2008)

13.

Etessami, K., Yannakakis, M.: Recursive Markov decision processes and recursive stochastic games. J. ACM 62(2), 1–69 (2015)MathSciNetMATHCrossRef

14.

Etessami, K., Yannakakis, M.: Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. J. ACM 56(1), 1–66 (2009)MathSciNetMATHCrossRef

15.

Haccou, P., Jagers, P., Vatutin, V.A.: Branching Processes: Variation, Growth, and Extinction of Populations. Cambridge University Press, Cambridge (2005)MATHCrossRef

16.

Kimmel, M., Axelrod, D.E.: Branching Processes in Biology. IAM, vol. 19. Springer, New York (2002). https://doi.org/10.1007/b97371MATHCrossRef

17.

Michalewski, H., Mio, M.: On the problem of computing the probability of regular sets of trees. In: Proceedings of FSTTCS 2015, pp. 489–502 (2015)

18.

Przybyłko, M., Skrzypczak, M.: On the complexity of branching games with regular conditions. In: Proceedings of MFCS 2016, LIPICS, vol. 78 (2016)

19.

Reiter, J.G., Bozic, I., Chatterjee, K., Nowak, M.A.: TTP: tool for tumor progression. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 101–106. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39799-8_6CrossRef

Titel: Qualitative Multi-objective Reachability for Ordered Branching MDPs
verfasst von: Kousha Etessami
Emanuel Martinov
Verlag: Springer International Publishing
Buch: Reachability Problems
Print ISBN: 978-3-030-61738-7

Electronic ISBN: 978-3-030-61739-4

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-61739-4_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"