The Frontier of Decidability in Partially Observable Recursive Games

David Auger 1 Olivier Teytaud 1, 2, 3, 4
2 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
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.
Type de document :
Article dans une revue
International Journal of Foundations of Computer Science, World Scientific Publishing, 2012, Special Issue on "Frontier between Decidability and Undecidability", 23 (7), pp.1439-1450
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00710073
Contributeur : Olivier Teytaud <>
Soumis le : mercredi 9 juillet 2014 - 14:16:08
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : jeudi 9 octobre 2014 - 10:35:30

Fichier

sparta2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

699

Téléchargements de fichiers

269