Universal Reinforcement Learning Algorithms: Survey and Experiments
This work addresses the gap between theoretical optimality and practical understanding of URL algorithms for researchers in reinforcement learning, though it is incremental as it focuses on empirical validation rather than new algorithmic development.
The paper tackles the lack of empirical investigation of universal reinforcement learning (URL) algorithms, which assume minimal environment assumptions, by providing a survey and conducting experiments on partially-observable gridworld environments to illustrate policy properties and relative performance.
Many state-of-the-art reinforcement learning (RL) algorithms typically assume that the environment is an ergodic Markov Decision Process (MDP). In contrast, the field of universal reinforcement learning (URL) is concerned with algorithms that make as few assumptions as possible about the environment. The universal Bayesian agent AIXI and a family of related URL algorithms have been developed in this setting. While numerous theoretical optimality results have been proven for these agents, there has been no empirical investigation of their behavior to date. We present a short and accessible survey of these URL algorithms under a unified notation and framework, along with results of some experiments that qualitatively illustrate some properties of the resulting policies, and their relative performance on partially-observable gridworld environments. We also present an open-source reference implementation of the algorithms which we hope will facilitate further understanding of, and experimentation with, these ideas.