(With: Balaraman Ravindran, Prateek Gaur)

Understanding how we are able to perform a diverse set of complex tasks has been a central question for the Artificial Intelligence community. One popular approach is to use temporal abstraction as a framework to capture the notion of subtasks. However, this transfers the problem to finding the right subtasks, which is still an open problem. Existing approaches for subtask generation require too much knowledge of the environment, and the abstractions they create can overwhelm the agent. We propose a simple algorithm inspired by small world networks to learn subtasks while solving a task that requires virtually no information of the environment. Additionally, we show that the subtasks we learn can be easily composed by the agent to solve any other task; more formally, we prove that any task can be solved using only a logarithmic combination of these subtasks and primitive actions. Experimental results show that the subtasks we generate outperform other popular subtask generation schemes on standard domains.

• Accepted as a full paper (pdf) at at Autonomous Agents and Multi-Agent Systems (AAMAS 2012)!
• Poster (pdf) at the European Workshop for Reinforcement Learning (EWRL 2011).