Understanding Problem Difficulty in Reinforcement Learning: A Study of Goal-Oriented MDPs and Solution Methods

Abstract

Due to the rise of optimal control problems in modern life and their increasing complexity, this thesis analyzes various properties of these problems and how they relate to the difficulty of the problem itself to help increase understanding of the space. Through the lenses of learning theory and topology, it discusses how concepts like sample complexity, topological complexity, and path homotopy contribute to characterizing problem difficulty. Through graphical and topologically equivalent representations, methods are presented for bounding sample complexity for various goal-oriented MDPs, with a strong focus on separated-path MDPs.

Using various model environments as specific examples of interest, three different methods of solving these types of problems are presented along with discussions on why the above properties affect those solutions. These environments serve as playgrounds for analyses based on partial observability, topologically complex navigation, and hierarchical frameworks.