In this work we present ISA, a novel approach for learning and exploitingsubgoals in reinforcement learning (RL). Our method relies on inducing anautomaton whose transitions are subgoals expressed as propositional formulasover a set of observable events. A state-of-the-art inductive logic programmingsystem is used to learn the automaton from observation traces perceived by theRL agent. The reinforcement learning and automaton learning processes areinterleaved: a new refined automaton is learned whenever the RL agent generatesa trace not recognized by the current automaton. We evaluate ISA in severalgridworld problems and show that it performs similarly to a method for whichautomata are given in advance. We also show that the learned automata can beexploited to speed up convergence through reward shaping and transfer learningacross multiple tasks. Finally, we analyze the running time and the number oftraces that ISA needs to learn an automata, and the impact that the number ofobservable events has on the learner's performance.