A Theory of State Abstraction for Reinforcement Learning

A Theory of State Abstraction for Reinforcement Learning 

David Abel Department of Computer Science Brown University david_abel@brown.edu

Abstract 

Reinforcement learning presents a challenging problem: agents must generalize experiences, efficiently explore the world, and learn from feedback that is delayed and often sparse, all while making use of a limited computational budget. Abstraction is essential to all of these endeavors. Through abstraction, agents can form concise models of both their surroundings and behavior, supporting effective decision making in diverse and complex environments. To this end, the goal of my doctoral research is to characterize the role abstraction plays in reinforcement learning, with a focus on state abstraction. I offer three desiderata articulating what it means for a state abstraction to be useful, and introduce classes of state abstractions that provide a partial path toward satisfying these desiderata. Collectively, I develop theory for state abstractions that can 1) preserve near-optimal behavior, 2) be learned and computed efficiently, and 3) can lower the time or data needed to make effective decisions. I close by discussing extensions of these results to an information theoretic paradigm of abstraction, and an extension to hierarchical abstraction that enjoys the same desirable properties. 

1 Introduction 

The focus of my doctoral research is on clarifying the representational practices that underlie effective Reinforcement Learning (RL), drawing on Information Theory, Computational Complexity, and Computational Learning Theory. The guiding question of my research is: “How do intelligent agents come up with the right abstract understanding of the worlds they inhabit?”, as pictured in Figure 1. I study this question by isolating and addressing its simplest unanswered forms through a mixture of theoretical analysis and experimentation. 

My interest in this question stems from its foundational role in many aspects of learning and decision making: agents can’t model everything in their environment, but must necessarily pick up on something about their surroundings in order to explore, plan far into the future, generalize, solve credit assignment, communicate, and efficiently solve problems. Abstraction is essential to all of these endeavors: through abstraction, agents can construct models of both their surroundings and behavior that are compressed and useful. The