Reinforcement learning is the problem faced by an agent that must learn behavior through trial-and-error interactions with a dynamic environment. Usually, the problem to be solved contains subtasks that repeat at different regions of the state space. Without any guidance an agent has to learn the solutions of all subtask instances independently, which in turn degrades the performance of the learning process. In this work, we propose two novel approaches for building the connections between different regions of the search space. The first approach efficiently discovers abstractions in the form...