The Frontier of Decidability in Partially Observable Recursive Games

David Auger 1 Olivier Teytaud 1, 2, 3, 4
2 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : The classical decision problem associated with a game is whether a given player has a winning strategy, i.e. some strategy that leads almost surely to a victory, regardless of the other players' strategies. While this problem is relevant for deterministic fully observable games, for a partially observable game the requirement of winning with probability 1 is too strong. In fact, as shown in this paper, a game might be decidable for the simple criterion of almost sure victory, whereas optimal play (even in an approximate sense) is not computable. We therefore propose another criterion, the decidability of which is equivalent to the computability of approximately optimal play. Then, we show that (i) this criterion is undecidable in the general case, even with deterministic games (no random part in the game), (ii) that it is in the jump 0', and that, even in the stochastic case, (iii) it becomes decidable if we add the requirement that the game halts almost surely whatever maybe the strategies of the players.
Document type :
Journal articles
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-00710073
Contributor : Olivier Teytaud <>
Submitted on : Wednesday, July 9, 2014 - 2:16:08 PM
Last modification on : Thursday, April 5, 2018 - 12:30:12 PM
Long-term archiving on : Thursday, October 9, 2014 - 10:35:30 AM

File

sparta2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00710073, version 1

Collections

Citation

David Auger, Olivier Teytaud. The Frontier of Decidability in Partially Observable Recursive Games. International Journal of Foundations of Computer Science, World Scientific Publishing, 2012, Special Issue on "Frontier between Decidability and Undecidability", 23 (7), pp.1439-1450. ⟨hal-00710073⟩

Share

Metrics

Record views

751

Files downloads

422