Bayesian variable order Markov models: Towards Bayesian predictive state representations

We present a Bayesian variable order Markov model that shares many similarities with predictive state representations. The resulting models are compact and much easier to specify and learn than classical predictive state representations. Moreover, we show that they significantly outperform a more straightforward Bayesian hierarchical Markov chain model and approach the performance of an oracle hidden Markov model. The simplicity of the approach makes it attractive for applications where the actual hidden state of the system does not need to be explicitly tracked, such as sequential prediction and decision making, while its fully Bayesian nature allows us to take into account the model uncertainty in decision making.