Xavier Boyen (PhD student)
Raya Fratkina (Masters student)
(Professor Daphne Koller)
When dealing with a dynamic process, we are typically interested in keeping track of where we are, and in predicting where we will be in the future. When the dynamic process is stochastic and partially observable, as it invariably is, the best we can hope for is to have accurate beliefs about the state of the system. Thus, we want to maintain a belief state: a probability distribution over the possible states the system can be in. When the state space is large (or infinite), it is typically impossible to maintain a completely accurate representation of the belief state. In this paper, we investigate the possibility of maintaining a more compact belief state, i.e., we maintain a distribution over states using a more compact representation than a full joint distribution. A more compact representation is more limited, and is therefore typically incapable of representing the correct belief state. Thus, the distribution that we maintain is necessarily only an approximation to the true belief state.
One risk of maintaining an approximate belief state is that the errors accumulate over time, eventually resulting in a distribution which is very far away from the true distribution. We have recently shown that, in many processes, this problem does not arise. If at each phase, the error introduced by the restricted representation is bounded, the overall error remains bounded over time indefinitely. Empirical results strongly support this theoretical conclusion.
In parallel, we are exploring compact representations of the belief state which are suited to the structure arising in real-world domains. We are experimenting with various representations, and comparing the resulting error. Our aim is to construct a representation which is suited to dealing with processes which are almost decomposable, i.e., processes composed of weakly interacting entities.