# Can the normalization factor for the belief state update be zero?

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?

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$$).