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$

1 Answer 1

3
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .