Compressed predictive state representation: an efficient moment-method for sequence prediction and sequential decision-making

Abstract

The construction of accurate predictive models over sequence data is of fundamental importance in the pursuit of developing artificial agents that are capable of (near)-optimal sequential decision-making in disparate environments.If such predictive models are available, they can be exploited by decision-making agents, allowing them to reason about the future dynamics of a system. Constructing models with sufficient predictive capacity, however, is a difficult task. Under the standard maximum likelihood criterion, these models tend to have non-convex learning objectives, and heuristics such as expectation-maximization suffer from high computational overhead. In contrast, an alternative statistical objective, the so-called method of moments, leads to convex optimizations that are often efficiently solvable via spectral decompositions.This work further improves upon the scalability, efficiency, and accuracy of this moment-based framework by employing techniques from the field of compressed sensing. Specifically, random projections of high-dimensional data are used during learning to (1) provide computational efficiency and (2) regularize the learned predictive models. Both theoretical analyses, outlining an explicit bias-variance trade-off, and experiments, demonstrating the superior empirical performance of the novel algorithm (e.g., compared to uncompressed moment-methods), are provided. Going further, this work introduces a sequential decision-making framework which exploits these compressed learned models. Experiments demonstrate that the combination of the compressed model learning algorithm and this decision-making framework allows for agents to successfully plan in massive, complex environments without prior knowledge.

Pour pouvoir agir optimalement, il est important de pouvoir prédire les séquences d'observations a venir. Ceci est une tache difficile puisque le problème d'estimation du maximum de vraisemblance est non-convexe. Les méthodes standard, tel que l'algorithme d'espérance-maximisation, sont très coûteuses et inefficaces. Une application récente de la méthode des moments offre une interprétation différente du problème qui est convexe et efficace.La méthode présentée améliore l'efficacité et la précision de la méthode des moments dans le contexte de prédiction de séquences d'observations. Ceci est fait grâce à des projections aléatoires qui augmentent l'efficacité de l'algorithme. Une analyse théorique de notre méthode démontre que notre algorithme réduit la variance au dépend d'un peu plus de biais. Nos résultats empiriques démontret une meilleure performance comparativement aux méthodes précédentes. De plus, nous offrons un moyen d'exploiter les prédictions de notre algorithme de façon à agir optimalement. Ceci nous permet de produire des agents capable de raisonner dans des environnements complexes et partiellement observables.