Hierarchies of Reward Machines

Summary

This partial ingest is based on the extracted full PDF text. The paper extends Reward Machines by letting one reward machine call another, producing a hierarchy of reward machines (HRM) for Non-Markovian Reinforcement Learning tasks whose reward and termination depend on event traces. The authors define HRM semantics with hierarchy states, contexts, exit conditions, and call stacks; prove that every HRM has an equivalent flat HRM; show that the flat equivalent can be exponentially larger in the root height; and introduce LHRM, a curriculum method that learns HRMs from traces using ILASP while reusing lower-level machines and options.

Key Claims

• Flat reward machines expose temporal reward structure, but complex long-horizon tasks can still require large flat automata.
• HRMs add compositional structure: constituent RMs can call other RMs, so reusable subtasks such as “make paper” or “collect colors in sequence” can be shared across higher-level tasks.
• Every HRM can be flattened into an equivalent flat HRM, but the number of flat states and edges can grow exponentially in the height of the root RM.
• The hierarchy can be exploited by treating calls as options: formula options pursue primitive label formulas, while call options invoke lower-level RMs.
• LHRM learns task HRMs from goal, dead-end, and incomplete label traces, reusing previously learned lower-height RMs and policies through a curriculum.
• Empirically, non-flat HRMs improve feasibility and sample efficiency in the reported CraftWorld and WaterWorld tasks, especially when tasks are sparse, hierarchical, and contain dead-end conditions.

Methods / Formalism

• The environment is an episodic labeled MDP with Markovian dynamics but potentially history-dependent reward and termination. A label trace

$${\lambda }_t=⟨l(s_0),\dots ,l(s_t)⟩\in (2^P{)}^{+}$$

summarizes the high-level events seen so far.

• A simple RM is written

$$M=⟨U,P,\varphi ,r,u_0,U^A,U^R⟩,$$

where U is the finite RM state set, P is the proposition set, phi(u,u') is a DNF formula over P, r(u,u') is the transition reward, u_0 is initial, and U^A, U^R are accepting and rejecting states.

• HRMs extend the transition function to

$$\varphi :U\times U\times \mathcal{M}\to DN{F}_P,$$

so an edge can call another RM under a propositional context.

• An HRM is

$$H=⟨\mathcal{M},M_r,P⟩,$$

where M_r is the root and M_top is a leaf RM that immediately returns control. The paper assumes no circular dependencies, global rejecting states, terminal accepting/rejecting states, and root rewards matching the underlying task reward.

• A hierarchy state is a tuple <M_i,u,Phi,Gamma> containing the current RM, current RM state, accumulated context, and call stack.
• The formal details of hierarchy traversal, exit conditions, flat equivalence, exponential blow-up, and option construction are summarized in Hierarchical Reward Machine Semantics.
• LHRM interleaves policy learning and HRM induction. When a trace is misclassified by the current HRM, the trace is added as a counterexample and ILASP learns an updated root transition function consistent with goal, dead-end, and incomplete traces.

Evidence / Experiments

• Domains: CraftWorld grid tasks with recipes, room layouts, and lava dead-ends; and WaterWorld continuous-control tasks with colored moving balls.
• Policy-learning comparison: handcrafted non-flat HRMs are compared with minimal flat equivalents under the authors’ HRL algorithm and with counterfactual reward-machine learning (CRM).
• Learning comparison: LHRM learns non-flat HRMs and is compared against flat HRM/RM learners including LHRM-flat, DeepSynth, JIRP, and LRM.
• Reported results support the theoretical scalability claim: non-flat HRMs are learned in cases where flat equivalents time out or require much larger edge sets.
• Options help collect goal traces for higher-level tasks; in the harder CraftWorld FRL setting, primitive-action exploration required far more episodes than option-guided exploration for the level-2 Milk Bucket task.
• The paper reports that restricting the callable RM set speeds up induction, which also exposes a utility problem: too many reusable machines can enlarge the search space for the learner.

Connections

• Extends Reward Machines from flat finite-state reward specifications to compositional machines with calls and call stacks.
• Strengthens Non-Markovian Reinforcement Learning by making history-dependent reward structure reusable across tasks rather than merely Markovianizing a single trace automaton.
• Connects to Automata Learning because LHRM uses ILASP to infer transition rules from counterexample traces.
• Connects to Continual Learning because the curriculum reuses lower-level learned HRMs and policies while moving to harder task levels.
• Complements Alinejad2026 - Dynamic Automaton Refinement and Planning for Non-Markovian RL: both learn or revise automata during interaction, but this paper emphasizes hierarchical reuse and compositional compression.
• The formal semantics and equivalence result are captured in Hierarchical Reward Machine Semantics.

Open Questions

• LHRM assumes a known proposition set, fixed task family, known task levels/root heights, and shared action/proposition interfaces across task instances.
• The policy-learning scheme is recursively optimal for the decomposed subtasks rather than a proof of global optimality over all possible HRM-consistent policies.
• The reported experiments support feasibility in structured benchmark domains; the paper leaves open how robust HRM learning is under noisy labels, partial observability, learned propositions, or non-episodic tasks.
• Callable-RM selection matters: making many lower-level machines available improves reuse in principle but can slow induction by enlarging the hypothesis space.

Citation

Furelos-Blanco, D., Law, M., Jonsson, A., Broda, K., and Russo, A. (2023). Hierarchies of Reward Machines. In Proceedings of the 40th International Conference on Machine Learning, PMLR 202.