Sparse Reinforcement Learning in High Dimensions 1

With the explosive growth and ever increasing complexity of data, developing theory and algorithms for learning with high-dimensional data has become an important challenge in statistical machine learning. Although significant advances have been made in recent years, most of the research efforts have been focused on supervised learning problems. This project designed, analysed, and implemented reinforcement learning algorithms for high-dimensional domains. We investigated the possibility of using the recent results in l1-regularization and compressive sensing in reinforcement learning. Humans learn and act using complex and high-dimensional observations and are extremely good in knowing how to dispense of most of the observed data with almost no perceptual loss. Thus, we hope that the generated results can shed some light on understanding of human decision-making. Our main goal was to find appropriate representations for value function approximation in high-dimensional spaces, and to use them to develop efficient reinforcement learning algorithms. By appropriate we mean representations that facilitate fast and robust learning, and by efficient we mean algorithms whose sample and computational complexities do not grow too rapidly with the dimension of the observations. We further intend to provide theoretical analysis for these algorithms as we believe that such results will help us refine the performance of such algorithms. Finally, we intend to empirically evaluate the performance of the developed algorithms in real-world applications such as a complex network management domain and a dogfight flight simulator.