Abstract
The value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there observational strategies that achieve the reachability objective with probability arbitrarily close to 1? This problem was shown undecidable recently. Our contribution is to introduce a class of partially observable Markov decision processes, namely \(\sharp-acyclic\) partially observable Markov decision processes, for which the value 1 problem is decidable. Our algorithm is based on the construction of a two-player perfect information game, called the knowledge game, abstracting the behaviour of a \(\sharp\)-acyclic partially observable Markov decision process \({\mathcal M}\) such that the first player has a winning strategy in the knowledge game if and only if the value of \({\mathcal M}\) is 1.
This work has been supported by the ANR project ECSPER (JC09_472677) and the ARC project Game Theory for the Automatic Synthesis of Computer Systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bertoni, A.: The solution of problems relative to probabilistic automata in the frame of the formal languages theory. In: Siefkes, D. (ed.) GI 1974. LNCS, vol. 26, pp. 107–112. Springer, Heidelberg (1975)
Bertoni, A., Mauri, G., Torelli, M.: Some recursive unsolvable problems relating to isolated cutpoints in probabilistic automata. In: Proceedings of the Fourth Colloquium on Automata, Languages and Programming, pp. 87–94. Springer, London (1977)
Bertrand, N., Genest, B., Gimbert, H.: Qualitative determinacy and decidability of stochastic games with signals. In: LICS, pp. 319–328 (2009)
Chatterjee, K., Doyen, L., Henzinger, T.A., Raskin, J.F.: Algorithms for omega-regular games of incomplete information. LMCS 3(3) (2007)
Chatterjee, K.: Concurrent games with tail objectives. Theor. Comput. Sci. 388(1-3), 181–198 (2007)
Chatterjee, K., Doyen, L., Gimbert, H., Henzinger, T.A.: Randomness for free. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 246–257. Springer, Heidelberg (2010)
Chatterjee, K., Doyen, L., Henzinger, T.A.: Qualitative analysis of partially-observable markov decision processes. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 258–269. Springer, Heidelberg (2010)
Chatterjee, K., Jurdzinski, M., Henzinger, T.A.: Quantitative stochastic parity games. In: SODA, pp. 121–130 (2004)
Chatterjee, K., Tracol, M.: Decidable problems for probabilistic automata on infinite words. In: LICS, pp. 185–194 (2012)
Courcoubetis, C., Yannakakis, M.: The complexity of probabilistic verification. J. ACM 42(4), 857–907 (1995)
Derman, C.: Finite State Markovian Decision Processes. Academic Press, Inc., Orlando (1970)
Fijalkow, N., Gimbert, H., Oualhadj, Y.: Deciding the value 1 problem for probabilistic leaktight automata. In: LICS, pp. 295–304 (2012)
Gimbert, H.: Randomized Strategies are Useless in Markov Decision Processes. Technical report, Laboratoire Bordelais de Recherche en Informatique - LaBRI (July 2009), http://hal.archives-ouvertes.fr/hal-00403463
Gimbert, H., Horn, F.: Solving simple stochastic tail games. In: SODA, pp. 847–862 (2010)
Gimbert, H., Oualhadj, Y.: Probabilistic automata on finite words: Decidable and undecidable problems. In: ICALP (2), pp. 527–538 (2010)
Gimbert, H., Oualhadj, Y.: Deciding the Value 1 Problem for #-acyclic Partially Observable Markov Decision Processes. Technical report, Laboratoire Bordelais de Recherche en Informatique - LaBRI, Laboratoire d’Informatique Fondamentale de Marseille - LIF (July 2013), http://hal.archives-ouvertes.fr/hal-00743137
Putterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, New York (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Gimbert, H., Oualhadj, Y. (2014). Deciding the Value 1 Problem for \(\sharp\)-acyclic Partially Observable Markov Decision Processes. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds) SOFSEM 2014: Theory and Practice of Computer Science. SOFSEM 2014. Lecture Notes in Computer Science, vol 8327. Springer, Cham. https://doi.org/10.1007/978-3-319-04298-5_25
Download citation
DOI: https://doi.org/10.1007/978-3-319-04298-5_25
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04297-8
Online ISBN: 978-3-319-04298-5
eBook Packages: Computer ScienceComputer Science (R0)