# Reward Machines for Deep RL in Noisy and Uncertain Environments

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods.
- Builds on 43 of its 68 references that are in the map.
- First posted on arXiv 31 May 2024.

## Placed in

- Deep reinforcement learning methods / [Interpretable and logic-guided RL](https://mlsanity.com/deeprl/interpretable-and-logic-guided-rl/)

## Builds on (most cited first, 30 of 43)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [Video PreTraining (VPT): Learning to Act by Watching Unlabeled Online Videos](https://mlsanity.com/paper/2206.11795/) (2022)
- [Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks](https://mlsanity.com/paper/2306.13831/) (2023)
- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Vision-Language Models as Success Detectors](https://mlsanity.com/paper/2303.07280/) (2023)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Using Natural Language for Reward Shaping in Reinforcement Learning](https://mlsanity.com/paper/1903.02020/) (2019)
- [Zero-Shot Task Generalization with Multi-Task Deep Reinforcement Learning](https://mlsanity.com/paper/1706.05064/) (2017)
- [STEVE-1: A Generative Model for Text-to-Behavior in Minecraft](https://mlsanity.com/paper/2306.00937/) (2023)
- [LTL2Action: Generalizing LTL Instructions for Multi-Task RL](https://mlsanity.com/paper/2102.06858/) (2021)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications](https://mlsanity.com/paper/1609.07409/) (2016)
- [Environment-Independent Task Specifications via GLTL](https://mlsanity.com/paper/1704.04341/) (2017)
- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [Joint Inference of Reward Machines and Policies for Reinforcement Learning](https://mlsanity.com/paper/1909.05912/) (2019)
- [Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/1801.08099/) (2018)
- [Encoding formulas as deep networks: Reinforcement learning for zero-shot execution of LTL formulas](https://mlsanity.com/paper/2006.01110/) (2020)
- [Reward Machines for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2007.01962/) (2020)
- [Transfer of Temporal Logic Formulas in Reinforcement Learning](https://mlsanity.com/paper/1909.04256/) (2019)
- [Reinforcement Learning with Probabilistic Guarantees for Autonomous Driving](https://mlsanity.com/paper/1904.07189/) (2019)
- [Temporal-Logic-Based Reward Shaping for Continuing Reinforcement Learning Tasks](https://mlsanity.com/paper/2007.01498/) (2020)
- [Modular Deep Reinforcement Learning with Temporal Logic Specifications](https://mlsanity.com/paper/1909.11591/) (2019)
- [Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamples](https://mlsanity.com/paper/2006.15714/) (2020)
- [Reinforcement Learning Based Temporal Logic Control with Maximum Probabilistic Satisfaction](https://mlsanity.com/paper/2010.06797/) (2020)
- [A Policy Search Method For Temporal Logic Specified Reinforcement Learning Tasks](https://mlsanity.com/paper/1709.09611/) (2017)
- [Induction of Subgoal Automata for Reinforcement Learning](https://mlsanity.com/paper/1911.13152/) (2019)
- [In a Nutshell, the Human Asked for This: Latent Goals for Following Temporal Specifications](https://mlsanity.com/paper/2110.09461/) (2021)

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

- [DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RL](https://mlsanity.com/paper/2410.04631/) (2024)
- [Learning Robust Reward Machines from Noisy Labels](https://mlsanity.com/paper/2408.14871/) (2024)
- [Modeling Others' Minds as Code](https://mlsanity.com/paper/2510.01272/) (2025)
- [Ground-Compose-Reinforce: Grounding Language in Agentic Behaviours using Limited Data](https://mlsanity.com/paper/2507.10741/) (2025)
- [ARM-FM: Automated Reward Machines via Foundation Models for Compositional Reinforcement Learning](https://mlsanity.com/paper/2510.14176/) (2025)
- [FORM: Learning Expressive and Transferable First-Order Logic Reward Machines](https://mlsanity.com/paper/2501.00364/) (2024)
- [PlatoLTL: Scaling LTL-Guided Multi-Task RL](https://mlsanity.com/paper/2601.22891/) (2026)
- [DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applications](https://mlsanity.com/paper/2602.03486/) (2026)
- [Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version)](https://mlsanity.com/paper/2602.06227/) (2026)
- [Active Reward Machine Inference From Raw State Trajectories](https://mlsanity.com/paper/2604.07480/) (2026)
- [Safe Reinforcement Learning of Autonomous Highway Driving: A Unified Framework for Safety and Efficiency](https://mlsanity.com/paper/2606.14609/) (2026)

## Abstract (arXiv)

Reward Machines provide an automaton-inspired structure for specifying instructions, safety constraints, and other temporally extended reward-worthy behaviour. By exposing the underlying structure of a reward function, they enable the decomposition of an RL task, leading to impressive gains in sample efficiency. Although Reward Machines and similar formal specifications have a rich history of application towards sequential decision-making problems, they critically rely on a ground-truth interpretation of the domain-specific vocabulary that forms the building blocks of the reward function--such ground-truth interpretations are elusive in the real world due in part to partial observability and noisy sensing. In this work, we explore the use of Reward Machines for Deep RL in noisy and uncertain environments. We characterize this problem as a POMDP and propose a suite of RL algorithms that exploit task structure under uncertain interpretation of the domain-specific vocabulary. Through theory and experiments, we expose pitfalls in naive approaches to this problem while simultaneously demonstrating how task structure can be successfully leveraged under noisy interpretations of the vocabulary.