文章基本信息

标题：Synchronizing Objectives for Markov Decision Processes
本地全文：下载
作者：Laurent Doyen ; Thierry Massart ; Mahsa Shirmohammadi 等
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2011
卷号：50
页码：61-75
DOI：10.4204/EPTCS.50.5
出版社：Open Publishing Association
摘要：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.