Talk by Joao Messias

You are all cordially invited to the next AMLab colloquium this Tuesday, February 23 at 16:00 in C3.163, where Joao Messias will give a talk titled “Variable-Order Markov Models for Sequence Prediction”. Afterwards there is the ‘borrel’ with drinks and snacks!

Abstract: The problem of learning how to predict future values of discrete stochastic sequences arises in many different domains. (Semi-)Markovian models with latent state representations, such as HMMs, have been widely used for this purpose, but their application can be difficult in domains with complex state or observation spaces. Recently, the first tractable approximations to the AIXI interpretation of Universal Reinforcement Learning have made use of Variable-Order Markov Models (VMMs) to approach this problem from a different perspective, by learning how to predict directly from histories of past observations, without requiring an explicit latent state representation, and in some cases, without knowing a priori how long these histories of observations should be.

In this talk, I will present an introduction to VMM methods for sequence prediction. I will discuss the relationship between VMM prediction and lossless compression; and present a review of the most well-known VMM methods. Finally, I will discuss future directions of research in this topic, in the context of reinforcement learning under partial observability.