# Hierarchies of Reward Machines

arXiv: https://arxiv.org/abs/2205.15752 · HTML: https://mlsanity.com/paper/2205.15752/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 77 references that are in the map.
- First posted on arXiv 31 May 2022.

## Builds on (most cited first, 24 of 24)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [The Option-Critic Architecture](https://mlsanity.com/paper/1609.05140/) (2016)
- [Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation](https://mlsanity.com/paper/1604.06057/) (2016)
- [BabyAI: A Platform to Study the Sample Efficiency of Grounded Language Learning](https://mlsanity.com/paper/1810.08272/) (2018)
- [Teacher-Student Curriculum Learning](https://mlsanity.com/paper/1707.00183/) (2017)
- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [Prioritized Level Replay](https://mlsanity.com/paper/2010.03934/) (2020)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [A Laplacian Framework for Option Discovery in Reinforcement Learning](https://mlsanity.com/paper/1703.00956/) (2017)
- [Generalization in Reinforcement Learning with Selective Noise Injection and Information Bottleneck](https://mlsanity.com/paper/1910.12911/) (2019)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Joint Inference of Reward Machines and Policies for Reinforcement Learning](https://mlsanity.com/paper/1909.05912/) (2019)
- [A Boolean Task Algebra for Reinforcement Learning](https://mlsanity.com/paper/2001.01394/) (2020)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [Reward Machines for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2007.01962/) (2020)
- [Discovering Options for Exploration by Minimizing Cover Time](https://mlsanity.com/paper/1903.00606/) (2019)
- [Induction and Exploitation of Subgoal Automata for Reinforcement Learning](https://mlsanity.com/paper/2009.03855/) (2020)
- [The Logical Options Framework](https://mlsanity.com/paper/2102.12571/) (2021)
- [Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamples](https://mlsanity.com/paper/2006.15714/) (2020)
- [Systematic Generalisation through Task Temporal Logic and Deep Reinforcement Learning](https://mlsanity.com/paper/2006.08767/) (2020)
- [Learning Compositional Neural Programs with Recursive Tree Search and Planning](https://mlsanity.com/paper/1905.12941/) (2019)
- [Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics](https://mlsanity.com/paper/2204.11833/) (2022)
- [A Hierarchical Bayesian Approach to Inverse Reinforcement Learning with Symbolic Reward Machines](https://mlsanity.com/paper/2204.09772/) (2022)

## Built on by (most cited first, 4 of 4)

- [Reward Machines for Deep RL in Noisy and Uncertain Environments](https://mlsanity.com/paper/2406.00120/) (2024)
- [Learning Reward Machines in Cooperative Multi-Agent Tasks](https://mlsanity.com/paper/2303.14061/) (2023)
- [Program Machine Policy: Addressing Long-Horizon Tasks by Integrating Program Synthesis and State Machines](https://mlsanity.com/paper/2311.15960/) (2023)
- [Reward Shaping and Action Masking for Compositional Tasks using Behavior Trees and LLMs](https://mlsanity.com/paper/2605.05795/) (2026)

## Abstract (arXiv)

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 subgoals 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 learn HRMs from 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 feasible in cases where its equivalent flat representation is not.