Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Olivier Teytaud Connect in order to contact the contributor
Submitted on : Wednesday, July 9, 2014 - 2:16:08 PM
Last modification on : Sunday, June 26, 2022 - 11:56:25 AM
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