A novel graphical approach to automatic abstraction in reinforcement learning

• A framework for automatic skill acquisition.
• Two algorithms for subgoal detection: the first algorithm incorporates k′k′-means algorithm with spectral graph clustering, and the second algorithm utilizes eigenvector centrality measure.
• An algorithm for elimination redundant options.

Recent researches on automatic skill acquisition in reinforcement learning have focused on subgoal discovery methods. Among them, algorithms based on graph partitioning have achieved higher performance. In this paper, we propose a new automatic skill acquisition framework based on graph partitioning approach. The main steps of this framework are identifying subgoals and discovering useful skills. We propose two subgoal discovery algorithms, which use spectral analysis on the transition graph of the learning agent. The first proposed algorithm, incorporates k′k′-means algorithm with spectral clustering. In the second algorithm, eigenvector centrality measure is utilized and options are discovered. Moreover, we propose an algorithm for pruning useless options, which cause additional costs for the learning agent. The experimental results on various problems show significant improvement in the learning performance of the agent.