Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Olivier Teytaud <>
Submitted on : Wednesday, July 9, 2014 - 2:16:08 PM
Last modification on : Tuesday, June 15, 2021 - 4:18:13 PM
Long-term archiving on: : Thursday, October 9, 2014 - 10:35:30 AM


Files produced by the author(s)


  • HAL Id : hal-00710073, version 1



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⟩



Record views


Files downloads