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."
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.
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