Recursive stochastic games with positive rewards

Etessami, Kousha, Wojtczak, Dominik ORCID: 0000-0001-5560-0546 and Yannakakis, Mihalis (2019) Recursive stochastic games with positive rewards. THEORETICAL COMPUTER SCIENCE, 777. pp. 308-328.

Text tcs-revision.pdf - Author Accepted Manuscript Download (471kB) | Preview

Abstract

We first show that in such games both players have optimal deterministic “stackless and memoryless” optimal strategies. We then provide polynomial-time algorithms for computing the exact optimal expected reward (which may be infinite, but is otherwise rational), and optimal strategies, for both the maximizing and minimizing single-player versions of the game, i.e., for (1-exit) Recursive Markov Decision Processes (1-RMDPs). It follows that the quantitative decision problem for positive reward 1-RSSGs is in NP ∩ coNP. We show that Condon's well-known quantitative termination problem for finite-state simple stochastic games (SSGs) which she showed to be in NP ∩ coNP reduces to a special case of the reward problem for 1-RSSGs, namely, deciding whether the value is ∞. By contrast, for finite-state SSGs with strictly positive rewards, deciding if this expected reward value is ∞ is solvable in P-time. We also show that there is a simultaneous strategy improvement algorithm that converges in a finite number of steps to the value and optimal strategies of a 1-RSSG with positive rewards.

Item Type:	Article
Uncontrolled Keywords:	Recursive Markov decision processes, Recursive simple stochastic games, Recursive Markov chains, Total expected reward, Stochastic context-free grammars, Multi-type branching processes, Probabilistic pushdown systems, Linear programming, Policy iteration and strategy improvement algorithms
Depositing User:	Symplectic Admin
Date Deposited:	20 Aug 2019 10:28
Last Modified:	19 Jan 2023 00:28
DOI:	10.1016/j.tcs.2018.12.018
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3052140