Answers.Body: <p>I think that the normalisation factor is <em>assumed</em> to be non-zero. So, in practice, I guess, you must eventually check that <span class="math-container">$P(z \mid b, a)$</span> is non-zero (even though, I guess, it will likely never be zero because of round-off errors in computers).</p>
  
  <p>The formula to calculate <span class="math-container">$b'(s')$</span> comes from its definition, which is based on Bayes' theorem, where the denominator is assumed to be non-zero (in general).</p>
  
  <p>The definition of <span class="math-container">$b'(s')$</span> is <span class="math-container">$P(s' \mid z, a, b)$</span>, that is, the new belief <span class="math-container">$b'$</span> of being in state <span class="math-container">$s'$</span> is defined as the probability of landing in the next state <span class="math-container">$s'$</span>, given that we have observed <span class="math-container">$z$</span>, have taken action <span class="math-container">$a$</span> from the previous state <span class="math-container">$s$</span> and we had the previous belief <span class="math-container">$b$</span>. We will expand this definition, but first let us recall a few <a href="https://github.com/nbro/probability_cheatsheet/blob/master/probability_cheatsheet.pdf" rel="nofollow noreferrer">probability definitions</a>.</p>
  
  <p>Recall that <span class="math-container">$P(A, B) = P(A \mid B) P(B) = P(B \mid A) P(A)$</span>, where <span class="math-container">$A$</span> and <span class="math-container">$B$</span> can actually be multiple events (that is, <span class="math-container">$A$</span> could actually be the intersection of multiple events). In other words, suppose we want to calculate <span class="math-container">$P(A, B, C)$</span>, we can actually consider e.g. <span class="math-container">$B$</span> and <span class="math-container">$C$</span> as one event. Let <span class="math-container">$(B \cap C) = (A, B) = D$</span> (note that the notation <span class="math-container">$(A, B)$</span> means the "intersection" of events <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, in the case <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are events). Then</p>
  
  <p><span class="math-container">\begin{align}
  P(A, B, C) 
  &amp; = P(A, (B, C)) \\
  &amp;= P(A, D) \\
  &amp;= P(A|D)P(D) \\ 
  &amp;= P(A|B, C)P(B, C) \\
  &amp;= P(A|B, C)P(B|C)P(C) \\
  \end{align}</span></p>
  
  <p>In general, this idea generalises to more variables/events.</p>
  
  <p>Note also that <span class="math-container">$\frac{P(A, B)}{P(B)} = P(A \mid B)$</span>. </p>
  
  <p>At this point, we are prepared to expand <span class="math-container">$P(s' \mid z, a, b)$</span> and understand its expansion.</p>
  
  <p>We can expand <span class="math-container">$P(s' \mid z, a, b)$</span> as follows</p>
  
  <p><span class="math-container">\begin{align}
  P(s' \mid z, a, b)
  &amp;= \frac{P(s', z, a, b)}{P(z, a, b)}\\[0.7em]
  &amp;= \frac{P(s', z, a, b)}{P(z \mid b, a)P(a|b)P(b)}\\[0.7em]
  &amp;= \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]
  &amp;= \frac{P(z \mid s', a, b) P(s' \mid a, b)}{P(z \mid b, a)}
  \end{align}</span></p>
  
  <p>It then turns out that (I will maybe explain this more in detail later) </p>
  
  <p><span class="math-container">\begin{align}
  P(s' \mid z, a, b)
  &amp;= \frac{P(z \mid s', a, b) P(s' \mid a, b)}{P(z \mid b, a)} \\[0.7em]
  &amp;=\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]
  &amp;=b'(s')
  \end{align}</span></p>
  
  <p>So, by assumption, <span class="math-container">$P(z \mid b, a) = \sum_{s \in S}b(s)\sum_{s' \in S} T(s, a, s')O(a, s', z)$</span> must be different from zero for the equality above to hold.</p>
  
  <p>You can see this from a very simply example of the Bayes' theorem. Let <span class="math-container">$P(A \mid B) = \frac{P(B \mid A) P(A)}{P(B)}$</span>. Now, intuitively, <span class="math-container">$P(A \mid B)$</span> (which is what we want to calculate using Bayes' theorem) means the probability of <span class="math-container">$A$</span> occurring given that <span class="math-container">$B$</span> has occurred, which means that <span class="math-container">$B$</span> couldn't have had a probability of <span class="math-container">$0$</span> of happening if we wanted to calculate <span class="math-container">$P(A \mid B)$</span>, so <span class="math-container">$P(B)$</span> couldn't have been zero if we wanted to calculate <span class="math-container">$P(A \mid B)$</span> using Bayes' theorem. We can also apply this reasoning to the definition of <span class="math-container">$b'(s')$</span> above.</p>
  
  <p>For completeness, note also that, in the normalisation factor <span class="math-container">$$\sum_{s \in S}b(s)\sum_{s' \in S} T(s, a, s')O(a, s', z),$$</span> <span class="math-container">$b(s)$</span>, <span class="math-container">$T(s, a, s')$</span> and <span class="math-container">$O(a, s', z)$</span> are probability distributions, which means that not all terms of <span class="math-container">$b(s)$</span>, <span class="math-container">$T(s, a, s')$</span> and <span class="math-container">$O(a, s', z)$</span> can be zero, for all <span class="math-container">$s$</span>, <span class="math-container">$s'$</span> and <span class="math-container">$a$</span> (given they must sum up to <span class="math-container">$1$</span>).</p>
  
  <p>Note also that <span class="math-container">$\sum_{s' \in S} T(s, a, s')O(a, s', z)$</span> is a <a href="https://en.wikipedia.org/wiki/Convex_combination" rel="nofollow noreferrer">convex combination</a> of all <span class="math-container">$O(a, s', z)$</span> (for all <span class="math-container">$s'$</span>), where the coefficients are <span class="math-container">$T(s, a, s')$</span>. The normalisation factor is also a convex combination where the coefficients are <span class="math-container">$b(s)$</span> (for all <span class="math-container">$s$</span>). </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-28T18:44:39.777Z
Answers.LastActivityDate: 2019-03-28T21:11:41.690Z
Answers.LastEditDate: 2019-03-28T21:11:41.690Z
Answers.UserDisplayName: nbro
Body: <p>In order to update the belief state in a POMDP, the following formula is used:
  <span class="math-container">$$b'(s')=\frac{O(a, s', z) \sum_{s\in S} b(s)T(s, a, s')}{\mathbb{P}(z \mid b, a)}$$</span>
  where </p>
  
  <ul>
  <li><span class="math-container">$s$</span> is a specific state in the set of states <span class="math-container">$S$</span></li>
  <li><span class="math-container">$b'(s')$</span> is the updated belief state of being in the next state <span class="math-container">$s'$</span></li>
  <li><span class="math-container">$T(s, a, s') = \mathbb{P}(s' \mid s, a)$</span> is the propability (function) of having been in <span class="math-container">$s$</span> and ending up in <span class="math-container">$s'$</span> by taking action <span class="math-container">$a$</span>;</li>
  <li><p><span class="math-container">$O(a, s', z) = \mathbb{P}(z \mid s', a)$</span> the probability (function) of observing <span class="math-container">$z$</span>, performing action <span class="math-container">$a$</span> and ending up in <span class="math-container">$s'$</span></p></li>
  <li><p><span class="math-container">$\mathbb{P}(z \mid b, a)$</span> is defined as follows <span class="math-container">$\sum_{s \in S}b(s)\sum_{s' \in S} T(s, a, s')O(a, s', z)$</span></p></li>
  </ul>
  
  <p>Looking at <span class="math-container">$\mathbb{P}(z \mid b, a)$</span> it is possible that the result is <span class="math-container">$0$</span>. 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 <span class="math-container">$b'(s')$</span>, 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 <span class="math-container">$\mathbb{P}(z \mid b, a)$</span> always non-zero?</p>
  
Tags: <reinforcement-learning><pomdp><probability-distribution>
Title: Can the normalization factor for the belief state update be zero?
UserDisplayName: Bryan McGill
ThreadText: # Can the normalization factor for the belief state update be zero?
  
  (Asked by: username_0 on 2019-03-27)
  
  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?
  
  **Tags:** reinforcement-learning, pomdp, probability-distribution
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-03-28. Score: 3
  
  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](https://github.com/username_1/probability_cheatsheet/blob/master/probability_cheatsheet.pdf).
  
  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](https://en.wikipedia.org/wiki/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$).
  
  
  ---
  
  