NDLI: Partial-Observation Stochastic Games: How to Win when Belief Fails

Please wait, while we are loading the content...

Partial-Observation Stochastic Games: How to Win when Belief Fails

Content Provider	ACM Digital Library
Author	Chatterjee, Krishnendu Doyen, Laurent
Copyright Year	2014
Abstract	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 $\textit{one-sided}$ with either $(\textit{a})$ player 1, or $(\textit{b})$ player 2 having partial observation (and the other player has perfect observation), or $\textit{two-sided}$ with $(\textit{c})$ both players having partial observation. On the basis of randomization, $(\textit{a})$ the players may not be allowed to use randomization (pure strategies), or $(\textit{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 $(\textit{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) $\textit{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 nonelementary memory 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.
Starting Page	1
Ending Page	44
Page Count	44
File Format	PDF
ISSN	15293785
e-ISSN	1557945X
DOI	10.1145/2579821
Volume Number	15
Issue Number	2
Journal	ACM Transactions on Computational Logic (TOCL)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-05-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Partial-observation games Memory bounds Positive and almost-sure winning Reachability and Büchi objectives Stochastic games Strategy complexity
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Logic Computational Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Partial-Observation Stochastic Games: How to Win When Belief Fails

Partial-Observation Stochastic Games: How to Win When Belief Fails

Partial-observation stochastic games: How to win when belief fails (2012)

Partial-observation stochastic games: How to win when belief fails (2011)

Partial-Observation Stochastic Games: How to Win when Belief Fails (2011)

Partial-Observation Stochastic Games: How to Win when Belief Fails

Partial-observation stochastic games: how to win when belief fails (2013).

Apartial-observation stochastic games: how to win when belief fails.

A survey of partial-observation stochastic parity games.

Partial-Observation Stochastic Games: How to Win when Belief Fails

Similar Documents

Partial-Observation Stochastic Games: How to Win When Belief Fails

Partial-Observation Stochastic Games: How to Win When Belief Fails

Partial-observation stochastic games: How to win when belief fails (2012)

Partial-observation stochastic games: How to win when belief fails (2011)

Partial-Observation Stochastic Games: How to Win when Belief Fails (2011)

Partial-Observation Stochastic Games: How to Win when Belief Fails

Partial-observation stochastic games: how to win when belief fails (2013).

Apartial-observation stochastic games: how to win when belief fails.

A survey of partial-observation stochastic parity games.

Partial-Observation Stochastic Games: How to Win when Belief Fails