Hierarchies of Reward Machines - curriculum-based hierarchical reward machines for reinforcement learning

Aug 4, 2026

Upload by Eden

Reward machines (RMs) provide a finite-state machine formalism to represent reinforcement learning reward functions, where edges encode task subgoals via high-level events and associated rewards. Their structure supports decomposing long-horizon and sparse-reward tasks into simpler, independently solvable subtasks. This work introduces a hierarchy of RMs (HRMs) by enabling an RM to call other RMs, composing complex behavior. Experiments show handcrafted HRMs accelerate convergence versus flat HRMs, and learning HRMs is practical even when equivalent flat representations are infeasible.

LanguageEnglish

CategoryTechnology

FormatPDF

Pages48

Reading Time2 h 1 min

AccessFree to download

Introduction

Background

Reinforcement Learning Setup

Contributions

Hierarchies of RMs

HRL Algorithm for RM Calls

Curriculum-Based HRM Learning

Hierarchies of Reward Machines Daniel Furelos-Blanco 1 Mark Law 1 2 Anders Jonsson 3 Krysia Broda 1 Alessandra Russo 1 Abstract 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 longhorizon 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. 1. Introduction More than a decade ago, Dietterich et al. (2008) argued for the need to “learn at multiple time scales simultaneously, and with a rich structure of events and durations”. Finitestate machines (FSMs) are a simple yet powerful formalism for abstractly representing temporal tasks in a structured manner. One of the most prominent recent types of FSMs used in reinforcement learning (RL; Sutton & Barto, 2018) are reward machines (RMs; Toro Icarte et al., 2018 ; 2022), which compactly represent state-action histories in terms of high-level events; specifically, each edge is labeled with (i) a formula over a set of high-level events that capture a task’s subgoal, and (ii) a reward for satisfying the formula. Hence, RMs fulfill the need for structuring events and durations, and keep track of the achieved and pending subgoals. 1Imperial College London, UK 2ILASP Limited, UK 3Universitat Pompeu Fabra, Spain. Correspondence to: Daniel Furelos-Blanco <[d.furelos-blanco18@imperial.ac.uk](d.furelos-blanco18@imperial.ac.uk)>. Proceedings of the 40 th International Conference on Machine Learning, Honolulu, Hawaii, USA. PMLR 202, 2023 . Copyright 2023 by the author(s) . Hierarchical reinforcement learning (HRL; Barto & Mahadevan, 2003) frameworks, such as options (Sutton et al., 1999), have been used to exploit RMs by learning policies at two levels of abstraction: (i) select a formula (i.e., subgoal) from a given RM state, and (ii) select an action to (eventually) satisfy the chosen formula (Toro Icarte et al., 2018 ; Furelos-Blanco et al., 2021) . The subtask decomposition powered by HRL enables learning at multiple scales simultaneously, and eases the handling of long-horizon and sparse reward tasks. In addition, several works have considered the problem of learning the RMs themselves from interaction (e.g., Toro Icarte et al., 2019 ; Xu et al., 2020 ; Furelos-Blanco et al., 2021 ; Hasanbeig et al., 2021) . A common problem among methods learning minimal RMs is that they scale poorly as the number of states grows. In this work, we make the following contributions: 1. Enhance the abstraction power of RMs by defining hierarchies of RMs (HRMs), where constituent RMs can call other RMs (Section 3) . We prove that any HRM can be transformed into an equivalent flat HRM that behaves exactly like the original RMs. We show that under certain conditions, the equivalent flat HRM can have exponentially more states and edges. 2. Propose an HRL algorithm to exploit HRMs by treating each call as a subtask (Section 4) . Learning policies in HRMs further fulfills the desiderata posed by Dietterich et al. since (i) there is an arbitrary number of time scales to learn across (not only two), and (ii) thereis a richer range of increasingly abstract events and durations. Besides, hierarchies enable modularity and, hence, the reusability of the RMs and policies. Empirically, we

FAQs

What problem do reward machines (RMs) address in reinforcement learning?

RMs represent a task’s reward function using a finite-state machine whose edges encode subgoals as high-level events, enabling structured decomposition of long-horizon and sparse-reward tasks.

How do hierarchical reward machines (HRMs) extend reward machines?

HRMs add the ability for one RM to call other RMs, creating a compositional hierarchy of subtasks rather than a single flat state machine.

How is HRM learning achieved from traces in this work?

The method uses a curriculum-based approach that learns HRMs from traces for a set of composable tasks, leveraging simpler constituent RMs and previously learned components to make learning feasible.

Aug 4, 2026

Upload by Eden