Automatic Discovery and Transfer of MAXQ Hierarchies in a Complex System

Reinforcement learning has been an important category of machine learning approaches exhibiting self-learning and online learning characteristics. Using reinforcement learning, an agent can learn its behaviors through trial-and-error interactions with a dynamic environment and finally come up with an optimal strategy. Reinforcement learning suffers the curse of dimensionality, though there has been significant progress to overcome this issue in recent years. MAXQ is one of the most common approaches for reinforcement learning. To function properly, MAXQ requires a decomposition of the agent´s task into a task hierarchy. Previously, the decomposition can only be done manually. In this paper, we propose a mechanism for automatic subtask discovery. The mechanism applies clustering to automatically construct task hierarchy required by MAXQ, such that MAXQ can be fully automated. We present the design of our mechanism, and demonstrate its effectiveness through theoretical analysis and an extensive experimental evaluation.