Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machines

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

Abstract

Reinforcement Learning (RL) agents often utilize symbolic abstractions like Reward Machines (RMs) to solve long-horizon tasks. However, these methods are vulnerable to the "symbol grounding problem," where noisy sensor data leads to incorrect state transitions within the RM. This paper introduces Reward Machine State Modelling (RMSM), a method that directly predicts a belief distribution over RM states using a recurrent neural network. By bypassing individual symbol grounding and accounting for temporal correlations, RMSM demonstrates significant robustness to sensor noise and partial observability across multiple domains, including complex gridworlds and simulated household tasks.

Introduction

Long-horizon tasks in Reinforcement Learning (RL) are often decomposed using Reward Machines (RMs)—automata that track progress through logical stages of a goal. While effective, RMs typically rely on a "labelling function" to map raw sensor data to discrete symbols. In real-world scenarios, sensors are inherently noisy, leading to incorrect symbol detection. This "symbol grounding problem" can cause an agent's internal representation of the task to diverge from reality, resulting in failure. Existing solutions often assume symbols are independent or rely on simple probability thresholds, which fail in partially observable environments where symbols are temporally correlated.

Reward Machine State Modelling (RMSM)

To address these limitations, the authors propose Reward Machine State Modelling (RMSM). Instead of grounding individual symbols and then updating the RM state, RMSM uses a Recurrent Neural Network (RNN) to maintain a belief distribution over all possible states in the Reward Machine based on the history of observations and actions.

Figure 2: A Reward Machine automaton representing a task. Transitions are triggered by logical propositions (symbols) derived from the environment.

The architecture optimizes two concurrent objectives: a supervised learning loss to minimize the negative log-likelihood of the true RM state (using ground-truth labels available during training) and a reinforcement learning objective to maximize expected return. The policy is conditioned on both the environment state and the predicted RM state belief, allowing the agent to act cautiously when uncertainty is high.

Experimental Evaluation

The approach was tested in three distinct environments designed to challenge symbolic grounding:

  1. Toy Mining Domain: A gridworld testing robustness to uniform sensor noise and false positives in gold detection.
  2. MiniGrid Traffic Light: A task requiring memory of a traffic light state when the sensor is occluded (e.g., when the agent is facing away from the light).
  3. MiniGrid Kitchen: A household chore task with partially observable requirements and temporal dependencies, where chores remain "undone" until explicitly addressed.

Results and Discussion

RMSM significantly outperformed traditional baselines like Thresholding and Independent Belief Updating. In the Traffic Light and Kitchen domains, these baselines failed due to their inability to handle sensor gaps or temporal correlations. Quantitative analysis showed that the RM state beliefs generated by RMSM were significantly closer to the ground truth than any other approximate method.

Figure 6: (Top) Visualization of RM state beliefs in a gridworld. (Bottom) Performance comparison showing RMSM (Belief Updating+) maintaining near-optimal performance across varying noise levels compared to brittle baselines.

Key findings include:

  • Bypassing the Noisy Middleman: Predicting high-level task states directly is more robust than predicting individual symbols.
  • Temporal Consistency: RMSM correctly models that environment properties (like "dirty dishes") persist over time, preventing the "hallucinated progress" seen in independent models.
  • Sample Efficiency: By leveraging the structured logic of the RM, RMSM is more sample-efficient than standard recurrent policies that ignore task structure.

Conclusion

RMSM provides a robust framework for RL in noisy, symbolic environments. While it currently requires ground-truth RM states during training, future work could involve learning the RM structure and state modeller simultaneously. This approach paves the way for integrating high-level symbolic reasoning with deep RL in complex, real-world settings where sensors are imperfect.

Summary updated

BibTeX
@inproceedings{li2022noisy,
  author = {Andrew C. Li and Zizhao Chen and Pashootan Vaezipoor and Toryn Q. Klassen and Rodrigo Toro Icarte and Sheila A. McIlraith},
  title = {{Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machines}},
  booktitle = {DeepRL @ NeurIPS},
  year = {2022},
  url = {https://openreview.net/forum?id=LYYhPFpcv95},
}
Figure