2
$\begingroup$

In order to update the belief state in a POMDP, the following formula is used: $$b'(s')=\frac{O(a, s', z) \sum_{s\in S} b(s)T(s, a, s')}{\mathbb{P}(z \mid b, a)}$$ where

  • $s$ is a specific state in the set of states $S$
  • $b'(s')$ is the updated belief state of being in the next state $s'$
  • $T(s, a, s') = \mathbb{P}(s' \mid s, a)$ is the propability (function) of having been in $s$ and ending up in $s'$ by taking action $a$;
  • $O(a, s', z) = \mathbb{P}(z \mid s', a)$ the probability (function) of observing $z$, performing action $a$ and ending up in $s'$

  • $\mathbb{P}(z \mid b, a)$ is defined as follows $\sum_{s \in S}b(s)\sum_{s' \in S} T(s, a, s')O(a, s', z)$

Looking at $\mathbb{P}(z \mid b, a)$ it is possible that the result is $0$. This would be the case if the agent is in a state where no further actions are possible. But, in that case, there is a problem with updating $b'(s')$, since this causes a zero division. Is this a common problem and is the only possibility to avoid that a programming solution like an if-statement? Or is $\mathbb{P}(z \mid b, a)$ always non-zero?

$\endgroup$
2
$\begingroup$

I think that the normalisation factor is assumed to be non-zero. So, in practice, I guess, you must eventually check that $P(z \mid b, a)$ is non-zero (even though, I guess, it will likely never be zero because of round-off errors in computers).

The formula to calculate $b'(s')$ comes from its definition, which is based on Bayes' theorem, where the denominator is assumed to be non-zero (in general).

The definition of $b'(s')$ is $P(s' \mid z, a, b)$, that is, the new belief $b'$ of being in state $s'$ is defined as the probability of landing in the next state $s'$, given that we have observed $z$, have taken action $a$ from the previous state $s$ and we had the previous belief $b$. We will expand this definition, but first let us recall a few probability definitions.

Recall that $P(A, B) = P(A \mid B) P(B) = P(B \mid A) P(A)$, where $A$ and $B$ can actually be multiple events (that is, $A$ could actually be the intersection of multiple events). In other words, suppose we want to calculate $P(A, B, C)$, we can actually consider e.g. $B$ and $C$ as one event. Let $(B \cap C) = (A, B) = D$ (note that the notation $(A, B)$ means the "intersection" of events $A$ and $B$, in the case $A$ and $B$ are events). Then

\begin{align} P(A, B, C) & = P(A, (B, C)) \\ &= P(A, D) \\ &= P(A|D)P(D) \\ &= P(A|B, C)P(B, C) \\ &= P(A|B, C)P(B|C)P(C) \\ \end{align}

In general, this idea generalises to more variables/events.

Note also that $\frac{P(A, B)}{P(B)} = P(A \mid B)$.

At this point, we are prepared to expand $P(s' \mid z, a, b)$ and understand its expansion.

We can expand $P(s' \mid z, a, b)$ as follows

\begin{align} P(s' \mid z, a, b) &= \frac{P(s', z, a, b)}{P(z, a, b)}\\[0.7em] &= \frac{P(s', z, a, b)}{P(z \mid b, a)P(a|b)P(b)}\\[0.7em] &= \frac{P(z \mid s', a, b) P(s' \mid a, b) P(a | b) P(b)}{P(z \mid b, a)P(a|b)P(b)} \\[0.7em] &= \frac{P(z \mid s', a, b) P(s' \mid a, b)}{P(z \mid b, a)} \end{align}

It then turns out that (I will maybe explain this more in detail later)

\begin{align} P(s' \mid z, a, b) &= \frac{P(z \mid s', a, b) P(s' \mid a, b)}{P(z \mid b, a)} \\[0.7em] &=\frac{O(a, s', z) \sum_{s\in S} b(s)T(s, a, s')}{\sum_{s \in S}b(s)\sum_{s' \in S} T(s, a, s')O(a, s', z)} \\[0.7em] &=b'(s') \end{align}

So, by assumption, $P(z \mid b, a) = \sum_{s \in S}b(s)\sum_{s' \in S} T(s, a, s')O(a, s', z)$ must be different from zero for the equality above to hold.

You can see this from a very simply example of the Bayes' theorem. Let $P(A \mid B) = \frac{P(B \mid A) P(A)}{P(B)}$. Now, intuitively, $P(A \mid B)$ (which is what we want to calculate using Bayes' theorem) means the probability of $A$ occurring given that $B$ has occurred, which means that $B$ couldn't have had a probability of $0$ of happening if we wanted to calculate $P(A \mid B)$, so $P(B)$ couldn't have been zero if we wanted to calculate $P(A \mid B)$ using Bayes' theorem. We can also apply this reasoning to the definition of $b'(s')$ above.

For completeness, note also that, in the normalisation factor $$\sum_{s \in S}b(s)\sum_{s' \in S} T(s, a, s')O(a, s', z),$$ $b(s)$, $T(s, a, s')$ and $O(a, s', z)$ are probability distributions, which means that not all terms of $b(s)$, $T(s, a, s')$ and $O(a, s', z)$ can be zero, for all $s$, $s'$ and $a$ (given they must sum up to $1$).

Note also that $\sum_{s' \in S} T(s, a, s')O(a, s', z)$ is a convex combination of all $O(a, s', z)$ (for all $s'$), where the coefficients are $T(s, a, s')$. The normalisation factor is also a convex combination where the coefficients are $b(s)$ (for all $s$).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.