Hierarchies of Reward Machines
Reward machines (RMs) are a recent formalism for representing the reward
function of a reinforcement learning task through a finite-state machine whose
edges encode landmarks of the task using high-level events. The structure of
RMs enables the decomposition of a task into simpler and independently solvable
subtasks that help tackle long-horizon and/or sparse reward tasks. We propose a
formalism for further abstracting the subtask structure by endowing an RM with
the ability to call other RMs, thus composing a hierarchy of RMs (HRM). We
exploit HRMs by treating each call to an RM as an independently solvable
subtask using the options framework, and describe a curriculum-based method to
induce HRMs from example traces observed by the agent. Our experiments reveal
that exploiting a handcrafted HRM leads to faster convergence than with a flat
HRM, and that learning an HRM is more scalable than learning an equivalent flat
HRM.