Finding Structure in Reinforcement Learning

Sebastian Thrun and Anton Schwartz

Reinforcement learning addresses the problem of learning to select actions in order to maximize one's performance in unknown environments. To scale reinforcement learning to complex real-world tasks, such as typically studied in AI, one must ultimately be able to discover the structure in the world, in order to abstract away the myriad of details and to operate in more tractable problem spaces.

This paper presents the SKILLS algorithm. SKILLS discovers skills, which are partially defined action policies that arise in the context of multiple, related tasks. Skills collapse whole action sequences into single operators. They are learned by minimizing the compactness of action policies, using a description length argument on their representation. Empirical results in simple grid navigation tasks illustrate the successful discovery of structure in reinforcement learning.

Click here to obtain the full paper (148920 bytes).

@INPROCEEDINGS{Thrun95c,
  AUTHOR         = {S. Thrun and A. Schwartz},
  YEAR           = {1995},
  TITLE          = {Finding Structure in Reinforcement Learning},
  BOOKTITLE      = {Advances in Neural Information Processing Systems 
                    (NIPS) 7},
  EDITOR         = {G. Tesauro and D. Touretzky and T. Leen},
  PUBLISHER      = {MIT Press},
  ADDRESS        = {Cambridge, MA}
}