Synchronizing Objectives for Markov Decision Processes

Laurent Doyen
(LSV, ENS Cachan & CNRS, France)
Thierry Massart
(Université Libre de Bruxelles, Belgium)
Mahsa Shirmohammadi
(Université Libre de Bruxelles, Belgium)

We introduce synchronizing objectives for Markov decision processes (MDP). Intuitively, a synchronizing objective requires that eventually, at every step there is a state which concentrates almost all the probability mass. In particular, it implies that the probabilistic system behaves in the long run like a deterministic system: eventually, the current state of the MDP can be identified with almost certainty.

We study the problem of deciding the existence of a strategy to enforce a synchronizing objective in MDPs. We show that the problem is decidable for general strategies, as well as for blind strategies where the player cannot observe the current state of the MDP. We also show that pure strategies are sufficient, but memory may be necessary.

In Johannes Reich and Bernd Finkbeiner: Proceedings International Workshop on Interactions, Games and Protocols (iWIGP 2011), Saarbrücken, Germany, 27th March 2011, Electronic Proceedings in Theoretical Computer Science 50, pp. 61–75.
Published: 18th February 2011.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: