Equivalence Relations in Fully and Partially Observable Markov Decision Processes

Pablo Samuel Castro, Prakash Panangaden, Doina PrecupIJCAI 2009 · OpenReview

Abstract

This paper explores state equivalence relations in Markov Decision Processes (MDPs) and Partially Observable Markov Decision Processes (POMDPs). We compare bisimulation, a local notion of equivalence, with trajectory equivalence, a global notion based on observation distributions. We demonstrate that while these concepts diverge in fully observable systems due to state identity, they converge in certain partially observable settings. Furthermore, we provide a novel characterization of bisimulation as a fixed point of a trajectory-based refinement operator.

Introduction

In reinforcement learning, state space reduction is crucial for tractability. Equivalence relations allow us to group states that behave identically regarding long-term outcomes. Two primary notions exist: bisimulation, which focuses on step-by-step local transitions and rewards, and trajectory (or trace) equivalence, which focuses on the probability distributions of future observation sequences given action sequences. This work maps the theoretical boundaries between these definitions across different levels of observability.

State Equivalence in MDPs

In fully observable MDPs, a significant discrepancy arises between bisimulation and trajectory equivalence. This is often termed the "State Identity Trap."

Figure 1: An example where states $s$ and $s'$ are bisimilar but not trajectory equivalent due to distinct state identities in transitions.

As shown in Figure 1, states $s$ and $s'$ may be bisimilar because they transition to equivalent "types" of states with the same total probability and immediate rewards. However, because trajectory equivalence in MDPs typically includes the specific state IDs in the trace, $s$ and $s'$ are considered distinct if they transition to states with different names (e.g., $t$ vs $t'$), even if those states are behaviorally identical.

To bridge this gap, the authors introduce $\Psi$-trajectory equivalence, where states are replaced by their partition labels. They further define a refinement operator $\Gamma$. The fixed point of this operator—iteratively applying trajectory equivalence tests—is proven to be exactly bisimulation (Theorem 3.7).

Bisimulation vs. Trajectory Equivalence

Even when ignoring state names, the branching structure of a process can distinguish bisimulation from trajectory equivalence.

Figure 4: Comparison of two systems that are trajectory equivalent but not bisimilar. The branching timing (at $s$ vs. at $t'$) distinguishes them under bisimulation.

In Figure 4, the system on the left makes a probabilistic choice at the first step ($s$), while the system on the right makes it at the second step ($t'$). While both generate the same probability distributions over reward sequences (traces), they are not bisimilar because the intermediate states ($t_1, t_2$ vs $t'$) do not match in their transition probabilities to future reward-equivalent states.

Partially Observable Systems

In POMDPs, the relationship changes. The authors analyze equivalence in the belief space—the space of probability distributions over hidden states.

  • Strong Belief Bisimulation: Proved to be identical to belief trajectory equivalence (Theorem 4.9). This convergence is due to the deterministic nature of belief updates in a belief MDP.
  • Weak Belief Bisimulation: Shown to be insufficient for trajectory equivalence, highlighting the importance of how observations are handled.

The link between trajectory equivalence and Predictive State Representations (PSRs) suggests that learning algorithms for PSRs could be leveraged to discover state equivalences in POMDPs without requiring a full model.

Conclusion

This theoretical framework clarifies the relationship between local and global state equivalences. By showing that bisimulation can be recovered through iterated trajectory equivalence, the authors open the door for sampling-based algorithms that can identify equivalent states in complex environments where the underlying model is unknown.

Summary updated

Abstract

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.
BibTeX
@inproceedings{castro2009equivalence,
  author = {Pablo Samuel Castro and Prakash Panangaden and Doina Precup},
  title = {{Equivalence Relations in Fully and Partially Observable Markov Decision Processes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=BJNI4EMOWB},
}
Figure