Equivalence Relations in Fully and Partially Observable Markov Decision Processes

1 Introduction

Probabilistic systems are very useful modeling tools in many fields of science and engineering. In order to understand the behavior of existing models, or to provide compact models, notions of equivalence between states in such systems are necessary. Equivalence relations have to be defined in such a way that important properties are preserved, i.e., the long-term behavior of equivalent states should be the same. However, there are different ways in which "long-term behavior" could be defined, leading to different equivalence notions. In this paper, we focus on two equivalence relations which have been explored in depth in the process algebra literature: bisimulation [Milner, 1980; Larsen and Skou, 1991] and trace equivalence [Hoare, 1980]. Roughly speaking, two states are bisimilar if they have the same immediate behavior, and they transition with the same probabilities to equivalence classes of states. Two states are trace equivalent if they generate the same (conditional) probability distribution over observable system trajectories. At first glance, these notions are quite similar; however, they are not the same, and in particular bisimulation has stronger theoretical guarantees for certain classes of processes.

In this paper, we focus on bisimulation and trace equivalence in the context of Markov Decision Processes (MDPs) [Puterman, 1994] and Partially Observable Markov Decision Processes [Kaelbling et al., 1998]. Bisimulation has been defined for MDPs by Givan et al [2003] and has generated several pieces of follow-up work and extensions (e.g. Dean & Givan [1997], Ferns et al. [2004], Taylor et al. [2009]). Comparatively little work has focused on bisimulation for POMDPs, except for a basic definition of a bisimulation notion for POMDP states [Pineau, 2004] (though the terminology of "bisimulation" is not used there). To our knowledge, trace equivalence has not really been explored in either MDPs or POMDPs. However, using traces holds the potential of offering a more efficient and natural way of computing and approximating state equivalence through sampling methods (rather than the global, model-based process used typically to compute bisimulation). Moreover, in POMDPs, trace equivalence is intimately related to predictive state representations (PSRs) [Litman et al., 2002] as well as lossless compression [Poupart and Boutilier, 2003]. As we will discuss in more detail later, this link opens up other potential avenues for checking trace equivalence efficiently.

In this paper we investigate the relationship between bisimulation and trace equivalence, focusing on partially observable systems. We show that these two notions are not equivalent in MDPs, but they can be equivalent in POMDPs. We also present a different characterization of bisimulation in MDPs based on trace equivalence, which could potentially yield new algorithms for computing or approximating bisimulation.

The paper is organized as follows. In Sec. 2, we present the definitions and theoretical analysis of the relationship between bisimulation and trajectory (or trace) equivalence in MDPs. The analysis reveals the surprising fact that trajectory equivalence makes unnecessary distinctions in MDPs. In Sec. 3 we present a weaker version of trajectory equivalence that does not suffer from this problem. In Sec. 4, we consider these equivalence relations in the context of POMDPs, under two reasonable definitions of bisimulation. Finally, in Sec. 5, we discuss our findings and present ideas for future work.

2 Fully Observable States

Definition 2.1. A Markov Decision Process (MDP) is a 4tuple M = 〈S,A,P,R〉, where S is the set of states; A is the set of actions; P : S×A→Dist(S) is the next state transition dynamics; R : S×A→Dist(R) is the reward function.

Since R and P are defined as functions, we will denote P(s,a)(s′ ) = Pr(s′ |s,a) and R(s,a)(r) = Pr(r|s,a). We note that most often in the MDP literature, the reward function is defined as a deterministic function of the current state and action. The reward distribution is not explicitly considered because, for the purpose of computing value functions, only the expected value of the reward matters. However, in order to analyze state equivalences, we need to consider the entire distribution, because its higher-order moments (e.g. the variance) may be important. In what follows, we will assume for simplicity that the rewards only take values in a finite subset of R, denoted R. This is done for simplicity of exposition, and all results can be extended beyond this case.

Bisimulation for MDPs is defined in [Givan et al., 2003] for the case in which rewards are deterministic; here, we give the corresponding definition for reward distributions.

Definition 2.2. Given an MDP M = 〈S,A,P,R〉, an equivalence relation E : S×S→{0,1} is defined to be a bisimulation relation if whenever sEt the following properties hold:

where S/E denotes the partition of S into E-equivalence classes. Two states s and t are bisimilar, denoted s ∼ t, if there exists a bisimulation relation E such that sEt.

We will now define the notion of trajectory equivalence for MDP states, in a similar vein to the notion of trace equivalence for labelled transition systems [Hoare, 1980]. Intuitively, two states are trace equivalent if they produce the same trajectories. In MDPs, in order to define an analogous notion, we will need to give a similar, probabilistic definition conditional on action sequences (since actions can be independently determined by a controller or policy).

Definition 2.3. An action sequence is a function θ : N+ ↦→A mapping a time step to an action. Let Θ be the set of all action sequences. Let N : Θ ↦→Θ be a function which returns the tail of any sequence of actions: ∀i ∈ N+.θ(i+1) = N(θ)(i).

Consider any finite reward-state trajectory α ∈ (R×S)∗ and let Pr(α|s,θ) be the probability of observing α when starting in state s ∈ S and choosing the actions specified by θ .

Definition 2.4. Given an MDP, the states s,t ∈ S are trajectory equivalent if and only if ∀θ ∈ Θ and for any finite reward-state trajectory α,

We note that conditioning on state-independent (openloop) sequences of actions may be considered non-standard for MDPs, where most behavior is generated by stateconditional policies (in which the choice of action depends on the state). We focus here on open-loop sequences because this is the closest match to trace equivalence. We conjecture that a very similar analysis can be performed for closed-loop policies, but we leave this for future work.

We are now ready to present our main results relating trajectory equivalence and bisimulation in MDPs.

Lemma 2.5. If two states are trajectory equivalent, they have the same model for all actions.

The proof is immediate by considering one-step trajectories. The following theorem is a direct consequence of Lemma 2.5.

Theorem2.6. If two states are trajectory equivalent, they are also bisimilar.

Theorem 2.7. If two states are bisimilar, they need not be trajectory equivalent.

Proof. Consider the MDP depicted in Figure 1, with 4 states and only one action. In this, as well as in all subsequent examples, the annotations on the links represent the rewards received (in brackets) and the transition probabilities. In this MDP, t and t ′ are bisimilar, and thus, s and s′ are also bisimilar. Note that there is only one possible infinite action sequence θ, since there is only one action. Let α = 〈(1,t)〉. Then Pr(α|s, θ ) = 0.5 ̸= 0 = Pr(α|s′ ,θ). Thus, s and s′ are not trajectory equivalent.

These results show that trajectory equivalence is a sufficient but not necessary condition for bisimulation. This result seems counterintuitive, as bisimulation is considered perhaps the strongest equivalence notion in the process algebra literature. Upon closer inspection, one can notice that this result is due to the full state observability in an MDP. More precisely, because the identity of the state is fully observable, and is included in the trajectory, very fine distinctions are made between trajectories. This is undesirable if one wants an equivalence notion that is useful, for example, in reducing the state space of an MDP. With the current definition of trajectory equivalence, even completely disjoint but otherwise identical subsets of the MDP would be considered distinct, as long as their states are numbered differently. Hence, we will now consider a weaker version of trajectory equivalence, which is closer in spirit to bisimulation, and has more desirable properties.

3 ADifferent Notion of Trajectory Equivalence

In order to define a more appropriate notion of trajectory equivalence, we need to allow the exact state identity to not appear in the trajectory. In bisimulation, the equivalence relation E is used to partition the state space. Afterwards, the identity of a state is essentially replaced by the partition to which it belongs (as follows from the second condition in Def. 2.2). To exploit this idea, we will consider now a notion of trajectory equivalence when the state space is partitioned, and the identity of a state is replaced by the identity of the partition to which it belongs.

Let Ψ(S) be a partitioning of the state space into disjoint subsets and ψ : S → Ψ(S) be the function mapping each state to its corresponding partition in Ψ(S). Consider any finite reward-partition trajectory κ ∈ (R×Ψ(S))∗ and let Pr(κ|s,θ) be the probability of observing κ when starting in state s ∈ S and choosing the actions specified by θ .

Definition 3.1. Given an MDP M = 〈S, A, P, R〉 and a decomposition Ψ(S), two states s,t ∈ S are Ψ-trajectory equivalent if and only if ψ(s) = ψ(t) and ∀θ ∈ Θ and for any finite reward-partition trajectory κ , Pr(κ |s, θ ) = Pr(κ |t , θ ).

If Ψ(S) = S and ψ is the identity function, we have trajectory equivalence as defined in Sec. 2. Note, however, that if Ψ is defined in an arbitrary way, this notion of equivalence may not be useful at all.

Given that bisimulation distinguishes states with different rewards, it is natural to define a clustering ΨR(S) such that ψR(s) = ψR(s′ ) if and only if ∀a ∈ A.∀r.R(s,a)(r) = R(s′ ,a)(r). We will now establish the relationship between ΨR-equivalence and bisimulation.

Theorem 3.2. Two states that are ΨR-trajectory equivalent need not be bisimilar.

Proof. Consider the MDP in Figure 2, in which there is again only one action. Here, ΨR(S) = {c0,c1,c2}, where c0 = {s,s′ }, c1 = {t1,t2,t ′ ,u1,u′1 } and c2 = {u2,u′2}. Both s and s′ observe c1 w.p.1 in the first step. For any trajectories of length n > 1, 〈0,c1〉〈1,c1〉n-1 and 〈0,c1〉〈1,c1〉〈2,c2〉n-2 are observed w.p. 0.5 each. Thus, s and s′ are ΨR-trajectory equivalent. However, they are not bisimilar since neither t1 nor t2 is bisimilar to t ′ .

Lemma 3.3. For all bisimulation-equivalence classes c ∈ S/∼ and for all ΨR-trajectory equivalence classes d ∈ ΨR(S), either c ⊆ d or c∩d = /0.

Proof. Without loss of generality assume c∩d ̸= /0. If c contains only one state s, then c ⊆ψ(s). Now suppose that c has at least two states. For any two states s,s′ ∈ c, fromDef. 2.2, we have that ∀a ∈ A, r ∈ R.R(s, a)(r) = R(s′ , a)(r) ⇒ ψR(s) = ψR(s′ ), so s, s′ ∈ d.

Lemma 3.4. For all d ∈ ΨR(S) there exists a set C ⊆ S/∼ such that ⋃c∈C c = d.

Proof. Immediate from Lemma 3.3 and the fact that ⋃c∈S/∼ c = ⋃d∈ΨR(S) d = S.

Theorem 3.5. If two states are bisimilar, they are also ΨRtrajectory equivalent.

Proof. Assume s0 ∼ t0. Take any θ ∈ Θ and any finite trajectory κ. The proof is by induction on the length of κ.

Base case: |κ| = 1. Say κ = 〈d〉. Let a = θ(0). By Lemma 3.4 there exists C ⊆ S/∼ such that ⋃c∈C c = d. Therefore:

Induction step: Assume that the claim holds up to |κ| = n-1. Let κ = 〈d1, · · · ,dn〉 and κ ′ = 〈d2, · · · ,dn〉. As before, let a = θ(0). Again, by Lemma 3.4, there exists C such that ⋃c∈C c = d. We have:

From the induction hypothesis, Pr(κ ′ |s1,N(θ)) is the same ∀s1 ∈ c, so we can denote this by Pr(κ ′ |c,N(θ)), Hence, continuing from above, we have:

which concludes the proof.

Theorems 3.2 and 3.5 are closer to what we would normally expect for these notions. The fact that trajectory equivalence is weaker is not surprising, since bisimulation has a "recursive" nature that is lacking in ΨR-trajectory equivalence. We now proceed by iteratively strengthening ΨRtrajectory equivalence to bring it closer to bisimulation.

Let Γ be an operator that takes a partitioning Ψ(S) and returns a more refined decomposition as follows. For any subset d ∈ S, d ∈ Γ(Ψ(S)) if and only if, for any two states s,t ∈ d, we have:

1. For any a ∈ A and r ∈ R, R(s, a)(r) = R(t, a)(r);

2. s and t and Ψ-trajectory equivalent.

Let Γ(n) denote the n-th iterate of Γ. It is clear that Γ(ΨR(S)) equivalence is ΨR-trajectory equivalence. Using Theorem 3.5, it is easy to prove that bisimulation implies Γ(n) (ΨR(S)) equivalence by induction. Similarly, it can be shown that for every n, Γ(n) (ΨR(S)) does not imply bisimulation. The counterexamples are similar in spirit to the one from Theorem 3.2, but they grow linearly in height and exponentially in width with n.

Theorem 3.6. The iterates Γ n have a fixed point, Γ∗ .

Proof. Define a binary relation ⊒ on the set of partitionings of S, where for any D1(S) and D2(S), D1(S) ⊒D2(S) if and only if for any d1 ∈ D1(S) and d2 ∈ D2(S), either d1 ∩d2 = /0

d86d86

or d2 ⊆ d1. It is easy to see that the set of all possible partitions of S along with ⊒ constitute a complete partial order with bottom, where bottom is simply ΨR(S). It then follows from Theorem 5.11 in [Winskel, 1993] that Γ∗ exists and is well defined.

From the results so far, it is easy to see that bisimulation implies Γ∗ equivalence. We now show that the reverse is also true.

Theorem 3.7. If two states are Γ∗ -equivalent, they are also bisimilar.

Proof. Let E be the Γ∗ -equivalence relation. Given s and t with sEt, we will show s ∼ t by checking the conditions of Def 2.2. The first condition follows from the definition of Γ. The second condition follows from the definition of Γ and the fact that Γ∗ is a fixed point.

Hence, we have obtained a new fixed-point characterization of bisimulation in terms of this new notion of trajectory equivalence.

4 Equivalences in Partially Observable Markov Decision Processes

We now turn our attention to the case of partial observability.

Definition 4.1. A Partially Observable Markov Decision Process (POMDP) is a 6-tuple M = 〈S,A,P,R,Ω,O〉, where 〈S,A,P,R〉 define an MDP; Ω is a finite set of observations; and O : S×A ↦→Dist(Ω) is the observation distribution function, with O(s, a)(ω) = Pr(ot+1 = ω|st+1 = s, at = a).

A belief state b is a distribution over S, quantifying the uncertainty in the system's internal state. Let B be the set of all belief states over S. After performing an action a ∈ A and witnessing observation ω ∈ Ω from belief state b, the function τ : B×A×Ω ↦→ B computes the new belief state b′ = τ(b,a,ω) as follows, ∀s′ ∈ S:

Many standard approaches replace the POMDP with a corresponding, continuous-state belief MDP 〈B,A,T,ρ〉, where B

is the (continuous) state space; A is the action set; the transition probability function T : B×A ↦→Dist(B) is defined as T (b, a)(b′ ) = ∑ω∈Ω Pr(b′ |b, a, ω)Pr(ω|a, b), with Pr(ω|a, b) defined above, and Pr(b′ |b,a,ω) = 1 1b′=τ(b,a,ω); and the reward function ρ : B×A ↦→Dist(R) is defined as: ρ(b, a)(r) = ∑s∈S b(s)R(s, a)(r).

Consider any finite reward-observation trajectory β ∈ (R× Ω)∗ and let Pr(β |b, θ ) be the probability of observing β when starting in belief state b and choosing the actions dictated by θ .

Definition 4.2. Given a POMDP, two belief states b,c are belief trajectory equivalent if and only if ∀θ ∈ Θ and for any finite reward-observation trajectory β, Pr(β|b,θ) = Pr(β |c, θ ).

Unlike in MDPs, where open-loop sequences of actions are rarely used, in partially observable environments, such sequences have been explored extensively in the work on predictive state representations (PSRs), where trajectories are called tests. Litman et al. [2002] show that in a POMDP, the outcomes of all tests can be computed from a set of core tests no larger than the number of states in S. Noting that belief states correspond one-to-one to histories (once an initial belief has been fixed), it becomes apparent that one could check trajectory equivalence by looking at the PSR model. Lossless belief compression [Poupart and Boutilier, 2003] is also quite related to our trajectory equivalence notion, though they are not identical: losless compression allows for a change of basis for the belief state space, whereas trajectory equivalence does not explicitly do so. This relationship deserves further study in the future.

Lemma 4.3. If two belief states are trajectory equivalent, they also have the same immediate transitions and rewards for all actions (i.e., their models are equivalent).

Proof. Assume that b,c ∈ B are belief trajectory equivalent. Take any a ∈ A and r ∈ R. Take any θ ∈ Θ with θ(0) = a. From Def. 4.2, we have:

Lemma 4.4. If b,c ∈ B are belief trajectory equivalent, then for any a ∈ A and ω ∈ Ω, τ(b,a,ω) and τ(c,a,ω) are belief trajectory equivalent.

Proof. We need to show that for any finite rewardobservation trajectory α, θ ∈ Θ, a ∈ A and ω ∈ Ω we have that Pr(α |τ (b, a, ω), θ ) = Pr(α |τ (c, a, ω), θ ).

Let θ ′ be a new action sequence s.t. θ ′ (0) = a and N(θ ′ ) = θ. Taking an arbitrary reward r, construct a new rewardobservation trajectory α ′ where α ′ = 〈(r,ω),α〉. We know Pr(α ′ |b,θ ′ ) = Pr(α ′ |c,θ ′ ) since b and c are belief trajectory equivalent. We also know that:

From Lemma 4.3, ρ(b,a)(r) = ρ(c,a)(r) and Pr(ω|b,a) = Pr(ω|c,a). So Pr(α|τ(b,a,ω),θ)=Pr(α|τ(c,a,ω),θ), and since α,a,θ,ω were all chosen arbitrarily, the proof concludes.

Previous work on POMDPs defines bisimulation between internal POMDP states. Instead, we focus on bisimulation between belief states. However, there are two possible definitions that one could adopt, which we present below.

Definition 4.5. A relation E ⊆ B×B is defined to be a weak belief bisimulation relation 1 if whenever bEc, the following properties hold:

1. ∀a ∈A.∀r ∈R.ρ(b,a)(r) =ρ(c,a)(r)
2. ∀a ∈A.∀ω ∈Ω.Pr(ω|b,a) =Pr(ω|c,a)
3. For any a ∈ A and d ∈ B/E, Pr(d|b,a) = Pr(d|c,a), where

Two belief states b,c are weakly belief bisimilar, denoted b ≈w c, if there exists a weak belief bisimulation relation E such that bEc.

Definition 4.6. A relation E ⊆ B×B is a strong belief bisimulation relation if it respects the first two conditions of Def. 4.5, and the following third condition:

1. ∀a ∈ A.∀ω ∈ Ω, τ(b,a,ω) and τ(c,a,ω) are strongly belief bisimilar.

1 We do not use 'weak' and 'strong' here in the same sense as [Milner, 1980].

Two belief states b,c are strongly belief bisimilar, denoted s ≈ t, if there exists a strong belief bisimulation relation E such that bEc.

We emphasize that strong belief bisimulation has a recursive definition.

Since both bisimulation definitions are quite similar in spirit, one would expect them to be equivalent. However, as we will now show, this is not the case.

Lemma 4.7. If two belief states are strongly bisimilar, they are also weakly bisimilar.

Proof. Let E be a strong belief bisimulation. Take any two belief states b and c such that bEc. The first two conditions in Def. 4.5 and Def. 4.6 are identical, so we only need to prove that the third condition in Def. 4.5 holds. Consider an arbitrary d ∈ B/E and a ∈ A. We have:

The last step follows because τ(b,a,ω)Eτ(c,a,ω) implies that ∀d ∈ B/E, τ(b, a, ω) ∈ B if and only if τ(c, a, ω) ∈ B.

Lemmas 4.3 and 4.4 are sufficient conditions for strong belief bisimilarity. This observation, combined with Lemma 4.7 yields the following corollary.

Corollary 4.8. Two belief states that are trajectory equivalent are both strongly and weakly bisimilar as well.

Theorem 4.9. If two belief states are strongly bisimilar, they are also trajectory equivalent.

The proof uses the definition of strong belief bisimilarity and induction on the length of the trajectory. It is very similar to previous proofs, and we omit it for succinctness.

Theorem 4.10. Two belief states that are weakly bisimilar need not be trajectory equivalent.

Proof. Consider the POMDP in Figure 3. There is only one available action and we assume all transitions yield the same reward. The observation received upon entering a state is indicated in parentheses next to the state name.

Let θ be the only available action sequence, and denote by δs the belief state concentrated at state s. We have: Pr(ω1|δs, θ ) = Pr(ω1|δs′ , θ ) = 0.5 and Pr(ω2|δs, θ ) = Pr(ω2|δs′ ,θ) = 0.5. Furthermore, δu1 ≈w δu′1 , δu2 ≈w δu′2 , implying that δt1 ≈w δt ′1 and δt2 ≈w δt ′2 , and hence δs ≈w δs′ . However, δs and δs′ are not belief trajectory equivalent since Pr(〈ω1, ω3〉|δs, θ ) = 0.5 ̸= 0 = Pr(〈ω1, ω3〉|δs′ , θ )

Note that this result is due mainly to the fact that the observation is obtained upon entering a state, and past observations are in some sense not taken into account.

5 Discussion and FutureWork

We analyzed the relationship between bisimulation and trajectory equivalence in MDPs and POMDPs. When the state is fully observable, trajectory equivalence is stronger than bisimulation, because it distinguishes between differences in transition probabilities to individual states. Bisimulation, on the other hand, can only distinguish between differences in transition probabilities to classes of bisimilar states.

By considering partitions over states, we obtained a new trajectory equivalence notion. We showed that bisimulation can be characterized as the fixed point of a sequence of iterates in which states are initially aggregated according to their immediate reward. K-moment equivalence [Zhioua, 2008], is somewhat similar to our method, as bisimulation is only reached in the limit. However, the equivalence computation is more straightforward in our case.

The Γ iterative operator provides an alternative way of computing bisimulation classes. It would be interesting to analyze the number of iterations required to reach the fixed point Γ∗ . This approach could yield an alternative algorithm for computing bisimulation classes, and could potentially be extended to a metric, in the spirit of [Ferns et al., 2004]. The advantage of our method compared to other bisimulation constructions is that one can accumulate a set of trajectories from action sequences and then approximate ΨR-trajectory equivalence, and further Γ(n) (ΨR(S))-equivalence. This would not require knowing the system model, and performance should improve as the number of trajectories gathered increases. We plan to study this idea, as well as algorithms for efficiently gathering trajectories, in future work.

We gave two definitions of bisimulation over belief states for POMDPs, which at first sight seem very similar, but they are not. The fact that strong belief bisimulation is equivalent to belief trajectory equivalence is not surprising, because the belief MDP is deterministic: from a belief state b, for a given action a and observation ω, there is exactly one reachable belief state. It is well known in the process algebra literature that trace equivalence and bisimulation are identical for deterministic automata. The strong relationship between belief trajectory equivalence, on one hand, and PSRs and lossless compression, on the other hand, opens up the possibility of efficient algorithms for computing and approximating this equivalence, which we will explore in the future.

Acknowledgments

This work was funded by NSERC. We thank the reviewers for their helpful comments and for suggesting the relationship between belief trajectory equivalence and linear PSR tests.