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.


1 Answer 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<k$, 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" by Simo Särkkä that illustrates the concepts. You could start there for further information on the topic. enter image description here


You must log in to answer this question.

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