--- _id: '2211' abstract: - lang: eng text: 'In two-player finite-state stochastic games of partial observation on graphs, in every state of the graph, the players simultaneously choose an action, and their joint actions determine a probability distribution over the successor states. The game is played for infinitely many rounds and thus the players construct an infinite path in the graph. We consider reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1) or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and to the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two-sided with (c) both players having partial observation. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Our main results for pure strategies are as follows: (1) For one-sided games with player 2 having perfect observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almost-sure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete and present symbolic algorithms that avoid the explicit exponential construction. (2) For one-sided games with player 1 having perfect observation we show that nonelementarymemory is both necessary and sufficient for both almost-sure and positive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least nonelementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibit serious flaws in previous results of the literature: we show a nonelementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed.' article_number: '16' author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Laurent full_name: Doyen, Laurent last_name: Doyen citation: ama: 'Chatterjee K, Doyen L. Partial-observation stochastic games: How to win when belief fails. ACM Transactions on Computational Logic (TOCL). 2014;15(2). doi:10.1145/2579821' apa: 'Chatterjee, K., & Doyen, L. (2014). Partial-observation stochastic games: How to win when belief fails. ACM Transactions on Computational Logic (TOCL). ACM. https://doi.org/10.1145/2579821' chicago: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” ACM Transactions on Computational Logic (TOCL). ACM, 2014. https://doi.org/10.1145/2579821.' ieee: 'K. Chatterjee and L. Doyen, “Partial-observation stochastic games: How to win when belief fails,” ACM Transactions on Computational Logic (TOCL), vol. 15, no. 2. ACM, 2014.' ista: 'Chatterjee K, Doyen L. 2014. Partial-observation stochastic games: How to win when belief fails. ACM Transactions on Computational Logic (TOCL). 15(2), 16.' mla: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic Games: How to Win When Belief Fails.” ACM Transactions on Computational Logic (TOCL), vol. 15, no. 2, 16, ACM, 2014, doi:10.1145/2579821.' short: K. Chatterjee, L. Doyen, ACM Transactions on Computational Logic (TOCL) 15 (2014). date_created: 2018-12-11T11:56:21Z date_published: 2014-04-01T00:00:00Z date_updated: 2023-02-23T12:23:43Z day: '01' department: - _id: KrCh doi: 10.1145/2579821 external_id: arxiv: - '1107.2141' intvolume: ' 15' issue: '2' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1107.2141 month: '04' oa: 1 oa_version: Preprint publication: ACM Transactions on Computational Logic (TOCL) publication_status: published publisher: ACM publist_id: '4759' quality_controlled: '1' related_material: record: - id: '1903' relation: earlier_version status: public - id: '2955' relation: earlier_version status: public - id: '5381' relation: earlier_version status: public scopus_import: 1 status: public title: 'Partial-observation stochastic games: How to win when belief fails' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 15 year: '2014' ...