Earlier Version

Partial-observation stochastic reachability and parity games

Chatterjee K. 2014. Partial-observation stochastic reachability and parity games. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 8634, 1–4.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English

Scopus indexed
Department
Series Title
LNCS
Abstract
We consider two-player zero-sum partial-observation stochastic games on graphs. Based on the information available to the players these games can be classified as follows: (a) general partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) perfect-observation (both players have complete view of the game). The one-sided partial-observation games subsumes the important special case of one-player partial-observation stochastic games (or partial-observation Markov decision processes (POMDPs)). Based on the randomization available for the strategies, (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. We consider all these classes of games with reachability, and parity objectives that can express all ω-regular objectives. The analysis problems are classified into the qualitative analysis that asks for the existence of a strategy that ensures the objective with probability 1; and the quantitative analysis that asks for the existence of a strategy that ensures the objective with probability at least λ (0,1). In this talk we will cover a wide range of results: for perfect-observation games; for POMDPs; for one-sided partial-observation games; and for general partial-observation games.
Publishing Year
Date Published
2014-01-01
Publisher
Springer
Volume
8634
Issue
PART 1
Page
1 - 4
Conference
MFCS: Mathematical Foundations of Computer Science
Conference Location
Budapest, Hungary
Conference Date
2014-08-25 – 2014-08-29
IST-REx-ID

Cite this

Chatterjee K. Partial-observation stochastic reachability and parity games. In: Vol 8634. Springer; 2014:1-4. doi:10.1007/978-3-662-44522-8_1
Chatterjee, K. (2014). Partial-observation stochastic reachability and parity games (Vol. 8634, pp. 1–4). Presented at the MFCS: Mathematical Foundations of Computer Science, Budapest, Hungary: Springer. https://doi.org/10.1007/978-3-662-44522-8_1
Chatterjee, Krishnendu. “Partial-Observation Stochastic Reachability and Parity Games,” 8634:1–4. Springer, 2014. https://doi.org/10.1007/978-3-662-44522-8_1.
K. Chatterjee, “Partial-observation stochastic reachability and parity games,” presented at the MFCS: Mathematical Foundations of Computer Science, Budapest, Hungary, 2014, vol. 8634, no. PART 1, pp. 1–4.
Chatterjee K. 2014. Partial-observation stochastic reachability and parity games. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 8634, 1–4.
Chatterjee, Krishnendu. Partial-Observation Stochastic Reachability and Parity Games. Vol. 8634, no. PART 1, Springer, 2014, pp. 1–4, doi:10.1007/978-3-662-44522-8_1.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar