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: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3052140 |
Dimensions
Dimensions
