On page 4 of this pdf in a theoretical RL course, we have a proof of the uniquness of the coarsest bisimulation.

A bisimulation $\phi$ is a mapping from states $s \in\mathcal{S}$ to abstract states $\phi(S)$ such that the following property holds: $\forall s_1, s_2 \in \mathcal{S}, \forall a \in \mathcal{A}, \forall x' \in \phi(\mathcal{S})$, $\phi(s_1)=\phi(s_2) \implies R(s_1,a)=R(s_2,a) \land P(x'|s_1,a) = P(x'|s_2,a)$.

In other words, a bisimulation groups states together such that the grouping preserves the reward and transition probabilities in the fashion above.

The definition of a common coarsening is given as follows:

$\phi_{12}(s_1) = \phi_{12}(s_2)$ if and only if the two states are equivalent under $\phi_1$ or $\phi_2$.

This definition does not make sense to me. Does anyone know how to interpret it correctly?

For example, suppose I have five states $s_1, s_2, s_3, s_4, s_5$. If $\phi_1$ groups $s_1, s_2, s_3$ as $g_1$, and $s_4, s_5$ as $g_2$, while $\phi_2$ groups $s_1,s_2$ as $g_3$ and $s_3, s_4, s_5$ as $g_4$, then it's unclear to me what the common coarsening does.

It seems like the definition invokes a contradiction. $s_3$ and $s_4$ should be in one group under $\phi_{12}$ due to $\phi_2$, and $s_2$ and $s_3$ should be in the same group under $\phi_{12}$ due to $\phi_1$. Then $s_2, s_3, s_4$ should be in the same group under $\phi_{12}$ by transitivity. But if we examine $s_2$ and $s_4$, neither $\phi_1$ nor $\phi_2$ sees them as equivalent, so by the under the definition quoted above, they should not be in the same group.

Can someone clarify how this definition works?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.