Reward Machines for Deep RL in Noisy and Uncertain Environments

Andrew C. Li, Zizhao Chen, Toryn Q. Klassen, Pashootan Vaezipoor, Rodrigo Toro Icarte, Sheila A. McIlraith

Abstract: While Reward Machines (RMs) are powerful tools for teaching agents complex, multi-step tasks, they typically rely on perfect state observations. In real-world applications, sensors are often noisy and environments are partially observable, causing standard RM-based agents to fail. This paper, presented at NeurIPS 2024, introduces a framework to decouple task-state inference from decision-making. By accounting for temporally correlated sensor noise through Temporal Dependency Modelling (TDM), the authors demonstrate that agents can maintain robust performance even with highly uncertain observations.

Introduction

In structured Reinforcement Learning (RL), Reward Machines use automata to define rewards by breaking tasks into logical stages (e.g., "pick up the key," then "open the door"). This structure significantly accelerates learning. However, RMs traditionally depend on a "labelling function"—an oracle that provides perfect ground-truth signals for sub-goal completion. In practice, robots rely on noisy sensors like cameras or LiDAR. If a sensor glitch leads an agent to believe a sub-goal is met when it is not, the RM state desynchronizes from reality, leading to task failure. This research addresses how to maintain RM utility when the agent must "guess" the world state through noisy abstraction models.

The Noisy Reward Machine Framework

The authors propose treating this challenge as a Partially Observable Markov Decision Process (POMDP). The core architecture decouples the system into two distinct modules:

  1. Inference Module: This module utilizes an "abstraction model" (such as a pretrained neural network) to maintain a belief—a probability distribution—over the current state of the Reward Machine.
  2. Decision-Making Module: A policy that consumes both the raw observation and the inferred belief to determine the optimal next action.
The Noisy Reward Machine framework decouples noisy sensory features from the ground-truth logic required for task progression.

Inference Strategies

The study evaluates three primary methods for handling state inference:

  • Naive: The agent assumes the most likely label at each discrete time step is correct.
  • Independent Belief Updating (IBU): The agent maintains a probability distribution but assumes sensor noise at time $t$ is independent of noise at time $t+1$.
  • Temporal Dependency Modelling (TDM): The proposed superior method. TDM models the belief based on the history of observations using a recurrent model (e.g., a GRU). This allows the system to recognize that sensor errors are often temporally correlated—if a sensor is wrong now, it is likely to remain wrong for a short duration.

Experimental Evaluation

The framework was tested across four diverse environments designed to simulate different types of uncertainty:

  • Gold Mining: A grid-world where some "gold" is actually worthless iron pyrite, requiring the agent to handle false positives.
  • Traffic Light (MiniGrid): Navigating a road with a stochastic traffic light that is hidden when the agent moves in reverse.
  • Kitchen (MiniGrid): A cleaning task where the agent must enter rooms to verify if chores are completed.
  • Colour Matching (MuJoCo): A high-dimensional robotics task requiring the identification of pillars based on text instructions and RGB values.
The Gold Mining environment illustrates the challenge: the agent must navigate to gold while dealing with noisy observations (probabilities) and the logical transitions of the Reward Machine.

Key Insights and Results

A critical finding is the Overconfidence Trap inherent in standard Bayesian updating (IBU). If a noisy classifier reports a 60% confidence in a label and the agent remains stationary for several frames, IBU aggregates these "independent" sightings, quickly reaching near 100% certainty. In reality, the sensor is simply repeating the same error. TDM avoids this trap by learning to account for these correlations.

Key Results include: * Performance: TDM achieved sample efficiency and total rewards nearly identical to an Oracle agent with perfect knowledge. * Robustness: Standard Deep RL methods, such as Recurrent PPO, failed to solve these tasks as they could not effectively exploit the logical structure of the RM under uncertainty. * Foundation Models: The authors demonstrated that GPT-4o can serve as a "zero-shot" abstraction model, evaluating task propositions from environment images well enough to guide RL agents without task-specific training.

Conclusion

TDM provides a robust path for deploying structured RL in the real world by bridging the gap between high-level logic and low-level sensor noise. While TDM requires training on historical data, future work aims to integrate large-scale foundation models as general-purpose "logical sensors," potentially removing the need for ground-truth rewards during training.

Summary updated

BibTeX
@inproceedings{li2024reward,
  author = {Andrew C. Li and Zizhao Chen and Toryn Q. Klassen and Pashootan Vaezipoor and Rodrigo Toro Icarte and Sheila A. McIlraith},
  title = {{Reward Machines for Deep RL in Noisy and Uncertain Environments}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=Cc0ckJlJF2},
}
Figure