Reinforcement Learning with Option Machines

Floris den Hengst, Vincent François-Lavet, Mark Hoogendoorn, Frank van Harmelen

Abstract

Reinforcement Learning (RL) agents often struggle with sample efficiency and generalizing to new tasks. This paper introduces Option Machines (OMs), a framework that leverages Finite State Transducers (FSTs) to guide agents using high-level, potentially underspecified instructions. By treating instructions as a flexible controller over reusable "options," OMs significantly improve learning speed and enable zero-shot performance on unseen tasks.

Introduction

Standard RL is notoriously data-hungry, often requiring millions of interactions to master simple behaviors. While symbolic instructions (e.g., "Go to A, then B") can accelerate learning, existing methods typically assume these instructions are perfect and complete. However, real-world guidance is frequently underspecified. For instance, a GPS might instruct a driver to "turn left" without accounting for dynamic obstacles or ensuring the final destination is reached if the map is outdated.

The authors address this gap by proposing a method to utilize high-level hints that guide an agent while still allowing it to optimize for the actual environment reward, even when instructions are incomplete or slightly inaccurate.

Methods: The Option Machine Framework

The core innovation is the Option Machine (OM), a high-level supervisor that sits atop a standard RL agent. It consists of several key components:

  1. Finite State Transducers (FSTs): Instead of a linear task list, OMs utilize FSTs to model complex logic, including loops, branches, and partial orderings. The FST processes environment "events" (e.g., "dough is smooth") and outputs a set of "permissible options" (e.g., "fill the pie plate").
An example Finite State Transducer (FST) representing a high-level recipe for baking a pie.
  1. Named Options: Behaviors are modularized and named (e.g., mix, bake). This allows the agent to learn a policy for a specific skill in one task and immediately reuse it in another, facilitating zero-shot transfer.
  2. Flexible Control: The framework explores three strategies for selecting an option when multiple are permissible:
  3. Fixed: Uses a pre-set priority.
  4. Greedy: Selects the option with the highest predicted reward.
  5. Sticky: Prefers the current option to maintain behavioral consistency and prevent "jittering."
  6. Reward Attribution: A specialized learning rule ensures that credit for a high-level state transition is attributed to the specific option that triggered it.

Evaluation and Results

The framework was evaluated on two benchmark environments: Craft (a resource-gathering and crafting world) and Maze (a navigation task with underspecified event detectors).

Learning curves across Maze and Craft environments comparing Option Machines (OM) variants against baselines.

Key Findings

  • Zero-Shot Success: In the Craft environment, OMs achieved a total reward of 0.90 in isolation settings, vastly outperforming the "Sketch" baseline (0.03).
  • Multi-Task Efficiency: In the Maze environment, OMs reached high reward levels significantly faster than baselines. Notably, Reward Machines (RMs) failed in this setting because they could not handle the underspecified nature of the maze events.
  • Robustness: OMs demonstrated consistent performance across both fully specified (Craft) and underspecified (Maze) environments.
  • Stability vs. Flexibility: Interestingly, the "Fixed" selection method often outperformed "Greedy" in difficult holdout tasks, suggesting that a stable high-level strategy is preferable when learning is challenging.

Discussion and Future Work

Option Machines treat instructions as a "curriculum" rather than a rigid constraint, allowing the agent to prioritize the environment's actual reward. The modularity of named options creates a library of skills that can be repurposed across tasks. Furthermore, the FST's ability to track event history allows the agent to handle non-Markovian conditions that standard RL struggles with.

Despite these strengths, current OMs rely on hand-crafted FSTs. Future research should explore methods for agents to automatically derive or learn these machines through interaction or observation. Additionally, scaling OMs to continuous, high-dimensional spaces like robotics remains a significant open challenge.

Summary updated

Abstract

Reinforcement learning (RL) is a powerful framework for learning complex behaviors, but lacks adoption in many settings due to sample size requirements. We introduce a framework for increasing sample efficiency of RL algorithms. Our approach focuses on optimizing environment rewards with high-level instructions. These are modeled as a high-level controller over temporally extended actions known as options. These options can be looped, interleaved and partially ordered with a rich language for high-level instructions. Crucially, the instructions may be underspecified in the sense that following them does not guarantee high reward in the environment. We present an algorithm for control with these so-called option machines (OMs), discuss option selection for the partially ordered case and describe an algorithm for learning with OMs. We compare our approach in zero-shot, single- and multi-task settings in an environment with fully specified and underspecified instructions. We find that OMs perform significantly better than or comparable to the state-of-art in all environments and learning settings.
BibTeX
@inproceedings{hengst2022reinforcement,
  author = {Floris den Hengst and Vincent François-Lavet and Mark Hoogendoorn and Frank van Harmelen},
  title = {{Reinforcement Learning with Option Machines}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/403},
}
Figure