Equivalence Relations in Fully and Partially Observable Markov Decision Processes

Dean & Givan [1997], Ferns et al. [2004], Taylor et We explore equivalence relations between states in al. [2009]). Comparatively little work has focused on bisimulation Markov Decision Processes and Partially Observable for POMDPs, except for a basic definition of a bisimulation Markov Decision Processes. We focus on two notion for POMDP states [Pineau, 2004] (though the different equivalence notions: bisimulation [Givan terminology of "bisimulation" is not used there). To our et al., 2003] and a notion of trace equivalence, under knowledge, trace equivalence has not really been explored in which states are considered equivalent if they either MDPs or POMDPs. However, using traces holds the generate the same conditional probability distributions potential of offering a more efficient and natural way of computing over observation sequences (where the conditioning and approximating state equivalence through sampling is on action sequences). We show that the methods (rather than the global, model-based process used relationship between these two equivalence notions typically to compute bisimulation). Moreover, in POMDPs, changes depending on the amount and nature of the trace equivalence is intimately related to predictive state representations partial observability.