Answers.Body: <p>The belief state in a POMDP is a distribution over the hidden state given all past actions and observations, i.e., at time <span class="math-container">$k$</span>, the belief state is <span class="math-container">$b_k(s_k) \triangleq P(s_k \mid a_{0:k-1}, z_{1:k})$</span>, where <span class="math-container">$a$</span> and <span class="math-container">$z$</span> are the actions and observations, respectively.</p>
  <p>What you are asking about and calling &quot;backtracking&quot; boils down to the question: &quot;given that at time <span class="math-container">$k$</span>, I know the history of actions <span class="math-container">$a_{0:k-1}$</span> and observations <span class="math-container">$z_{1:k}$</span>, what is the distribution over states at some past time step <span class="math-container">$t&lt;k$</span>, that is, <span class="math-container">$P(s_t\mid a_{0:k-1},z_{1:k})$</span>&quot;?</p>
  <p>This is commonly known as <em>Bayesian smoothing</em>. You might be familiar with Bayesian <em>filtering</em>, which aims to recover the belief state as defined in the first paragraph - an estimate of the current state given actions and observations up to the current time. Smoothing also uses information gained after time <span class="math-container">$t$</span> to estimate the state at time <span class="math-container">$t$</span>, and hence it is only possible after those actions and observations become known. There is also prediction, where you estimate the distribution over the state in the future.</p>
  <p>Smoothing is too broad of a topic to go into detail here, but below is a picture from the book <a href="https://users.aalto.fi/%7Essarkka/pub/cup_book_online_20131111.pdf" rel="nofollow noreferrer">&quot;Bayesian Filtering and Smoothing&quot;</a> by Simo Särkkä that illustrates the concepts. You could start there for further information on the topic.
  <a href="https://i.sstatic.net/FKlwP.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FKlwP.png" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T10:56:04.877Z
Answers.LastActivityDate: 2021-03-25T10:56:04.877Z
Answers.UserDisplayName: mikkola
Body: <p>Given a history of belief states, is there a common method that backtracks the most likely path of ending up in the current belief state?</p>
  <p>I have a Markov model which calculates belief states after every step. The belief state is a representation of the most likely states one could be in. A belief state may look like this:</p>
  <p><span class="math-container">$$b=[1,0,0,0,0],$$</span> where I am in the state <span class="math-container">$s_0$</span> with 100% certainty.</p>
  <p>I can store the belief state history like <span class="math-container">$b_0, b_1, b_2,\dots, b_n$</span>.</p>
  <p>Is there a common way to represent and estimate the most likely states one has been in?</p>
  <p>A naive approach could be to just look for the state with the highest value per belief state and take that as the node along the reverse path. But I am not confident enough, if that is a common and a good practice, as it is not considering the fuzziness, which comes with a belief state. But then again, if I would take all states that are bigger than 0, I might not know which state leads to which state and if that transition is even possible.</p>
  
Tags: <markov-decision-process><pomdp>
Title: Is there a way of path reconstruction using only the history of belief states?
UserDisplayName: MScott
ThreadText: # Is there a way of path reconstruction using only the history of belief states?
  
  (Asked by: username_0 on 2021-03-25)
  
  Given a history of belief states, is there a common method that backtracks the most likely path of ending up in the current belief state?
  
  I have a Markov model which calculates belief states after every step. The belief state is a representation of the most likely states one could be in. A belief state may look like this:
  
  $$b=[1,0,0,0,0],$$ where I am in the state $s\_0$ with 100% certainty.
  
  I can store the belief state history like $b\_0, b\_1, b\_2,\dots, b\_n$.
  
  Is there a common way to represent and estimate the most likely states one has been in?
  
  A naive approach could be to just look for the state with the highest value per belief state and take that as the node along the reverse path. But I am not confident enough, if that is a common and a good practice, as it is not considering the fuzziness, which comes with a belief state. But then again, if I would take all states that are bigger than 0, I might not know which state leads to which state and if that transition is even possible.
  
  **Tags:** markov-decision-process, pomdp
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-03-25. Score: 1
  
  The belief state in a POMDP is a distribution over the hidden state given all past actions and observations, i.e., at time $k$, the belief state is $b\_k(s\_k) \triangleq P(s\_k \mid a\_{0:k-1}, z\_{1:k})$, where $a$ and $z$ are the actions and observations, respectively.
  
  What you are asking about and calling "backtracking" boils down to the question: "given that at time $k$, I know the history of actions $a\_{0:k-1}$ and observations $z\_{1:k}$, what is the distribution over states at some past time step $t, that is, $P(s\_t\mid a\_{0:k-1},z\_{1:k})$"?
  
  This is commonly known as *Bayesian smoothing*. You might be familiar with Bayesian *filtering*, which aims to recover the belief state as defined in the first paragraph - an estimate of the current state given actions and observations up to the current time. Smoothing also uses information gained after time $t$ to estimate the state at time $t$, and hence it is only possible after those actions and observations become known. There is also prediction, where you estimate the distribution over the state in the future.
  
  Smoothing is too broad of a topic to go into detail here, but below is a picture from the book ["Bayesian Filtering and Smoothing"](https://users.aalto.fi/%7Essarkka/pub/cup_book_online_20131111.pdf) by Simo Särkkä that illustrates the concepts. You could start there for further information on the topic.
  [![enter image description here](https://i.sstatic.net/FKlwP.png)](https://i.sstatic.net/FKlwP.png)
  
  
  ---
  
  