Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games

Kousha Etessami, Mihalis Yannakakis

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

Abstract

Recursive Markov Decision Processes (RMDPs) and Recursive Simple Stochastic Games (RSSGs) are natural models for recursive systems involving both probabilistic and non-probabilistic actions. As shown recently [10], fundamental problems about such models, e.g., termination, are undecidable in general, but decidable for the important class of 1-exit RMDPs and RSSGs. These capture controlled and game versions of multi-type Branching Processes, an important and well-studied class of stochastic processes. In this paper we provide efficient algorithms for the qualitative termination problem for these models: does the process terminate almost surely when the players use their optimal strategies? Polynomial time algorithms are given for both maximizing and minimizing 1-exit RMDPs (the two cases are not symmetric). For 1-exit RSSGs the problem is in NP∩coNP, and furthermore, it is at least as hard as other well-known NP∩coNP problems on games, e.g., Condon’s quantitative termination problem for finite SSGs ([3]). For the class of linearly-recursive 1-exit RSSGs, we show that the problem can be solved in polynomial time.
Original languageEnglish
Title of host publicationSTACS
PublisherSpringer-Verlag GmbH
Pages634-645
Number of pages12
Publication statusPublished - 2006

Fingerprint

Dive into the research topics of 'Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games'. Together they form a unique fingerprint.

Cite this