AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Equivalence Relations in Fully and Partially Observable Markov Decision Processes
Pablo Samuel Castro, Prakash Panangaden, Doina Precup

Last modified: 2009-06-26


We explore equivalence relations between states in Markov Decision Processes and Partially Observable Markov Decision Processes. We focus on two different equivalence notions: bisimulation (Givan et al., 2003) and a notion of trace equivalence, under which states are considered equivalent if they generate the same conditional probability distributions over observation sequences (where the conditioning is on action sequences).  We show that the relationship between these two equivalence notions changes depending on the amount and nature of the partial observability. We also present an alternate characterization of bisimulation based on trajectory equivalence.


Markov Decision Processes, Partially Observable Markov Decision Processes, state equivalence, bisimulation

Full Text: PDF