Novel Exploration via Orthogonality
Andreas Theophilou, Özgür Şimşek
Discovering novel states or transitions efficiently requires effective policies or optionsthat direct the agent away from well-visited regions of the state space. This paper introducesa method, Novel Exploration via Orthogonality (NEO), that automatically uncoversnot only which state regions are novel but also how to reach them by leveraging Laplacian-basedrepresentations. Specifically, we use the eigenvectors of a modified graph Laplacian toinduce gradient flows from frequently visited (less novel) states to seldom visited (more novel)states. We show that modifying the Laplacian with weighted sinks yieldseigenvectors whose extreme values align with the most novel regions of the state space.We evaluate reinforcement learning agents with our option discovery method against related methods such as eigen-options and cover options in online, incremental settings. In summary we provide three key contributions, we provide bounds for our Laplacian matrices, we show that the smoothest eigenvectors with real eigenvalue below certain bounds provide guaranteed gradients to novel nodes for undirected and directed graphs, and we show that our option method NEO outperforms related state-of-the-art approaches in undirected and directed domains with varying structures.