0
$\begingroup$

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?

$\endgroup$

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.