Reinforcement learning (RL) with non-Markovian rewards requires agents to learn history-dependent policies, which is particularly challenging in long-horizon or sparse reward settings. Reward machines (RMs) are finite-state machines that represent non-Markovian reward functions in terms of high-level events. By compactly encoding high-level event histories, RMs thereby constitute an external memory that makes rewards Markovian and enables the applicability of standard RL algorithms in non-Markovian reward settings. The structure elucidated by RMs facilitates task decomposition, allowing policy learning to become more efficient when rewards are sparse. Nevertheless, the potential of RMs is limited by the complexity of handcrafting them and the lack of reusability within larger RMs. In this thesis, we address these problems.

In the first part of the thesis, we devise a method for learning minimal RMs from traces of high-level events observed by an RL agent. The learning is powered by an inductive logic programming system and is launched when the current RM does not correctly recognize a trace. To make RM learning more efficient, we conceive a symmetry breaking mechanism to shrink the search space whilst remaining complete. We empirically demonstrate that exploiting a learned RM leads to performance on par with a handcrafted one.

In the second part of the thesis, we build hierarchies of RMs (HRMs) by endowing RMs with the ability to call each other, enabling the reusability of the RMs' structures and policies. In particular, the HRMs are exploited by treating each call as an independently solvable subtask, and learned through a curriculum-based method extending our RM learning approach. Our experiments reveal that (i) exploiting a handcrafted HRM leads to faster convergence than with a flat HRM, and (ii) learning an HRM is feasible in cases where its equivalent flat representation is not.