Synchronizing Objectives for Markov Decision Processes

Details Synchronizing Objectives for Markov Decision Processes Synchronizing Objectives for Markov Decision Processes

2011-02-21

arxiv.org/abs/1102.4121v1

EPTCS 50, 2011, pp. 61-75

Computer Science

Logic in Computer Science

In Proceedings iWIGP 2011, arXiv:1102.3741

Scientific paper

10.4204/EPTCS.50.5

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.

Affiliated with

Also associated with

No associations

Rating

Synchronizing Objectives for Markov Decision Processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Synchronizing Objectives for Markov Decision Processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Synchronizing Objectives for Markov Decision Processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-519865