mlsanityData to 14 Oct 2026

Reward Machines for Deep RL in Noisy and Uncertain Environments

arXiv 2406.00120 ↗First posted 31 May 2024cs.LG cs.AI cs.FLcited by 11

On the map: Deep reinforcement learning methods → Interpretable and logic-guided RL

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.

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.

Builds on

43 of 68 references.

References · 43

  1. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,744
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2015Deep Recurrent Q-Learning for Partially Observable MDPscited by 465
  4. 2022Video PreTraining (VPT): Learning to Act by Watching Unlabeled Online Videoscited by 345
  5. 2023Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Taskscited by 327
  6. 2016Modular Multitask Reinforcement Learning with Policy Sketchescited by 203
  7. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 191
  8. 2023Vision-Language Models as Success Detectorscited by 142
  9. 2016Reinforcement Learning With Temporal Logic Rewardscited by 117
  10. 2019Using Natural Language for Reward Shaping in Reinforcement Learningcited by 114
  11. 2017Zero-Shot Task Generalization with Multi-Task Deep Reinforcement Learningcited by 98
  12. 2023STEVE-1: A Generative Model for Text-to-Behavior in Minecraftcited by 97
31 more
  1. 2021LTL2Action: Generalizing LTL Instructions for Multi-Task RLcited by 74
  2. 2020A Composable Specification Language for Reinforcement Learning Taskscited by 69
  3. 2016Q-Learning for Robust Satisfaction of Signal Temporal Logic Specificationscited by 67
  4. 2017Environment-Independent Task Specifications via GLTLcited by 67
  5. 2021Compositional Reinforcement Learning from Logical Specificationscited by 67
  6. 2019Joint Inference of Reward Machines and Policies for Reinforcement Learningcited by 56
  7. 2018Logically-Constrained Reinforcement Learningcited by 51
  8. 2020Encoding formulas as deep networks: Reinforcement learning for zero-shot execution of LTL formulascited by 36
  9. 2020Reward Machines for Cooperative Multi-Agent Reinforcement Learningcited by 35
  10. 2019Transfer of Temporal Logic Formulas in Reinforcement Learningcited by 31
  11. 2019Reinforcement Learning with Probabilistic Guarantees for Autonomous Drivingcited by 28
  12. 2020Temporal-Logic-Based Reward Shaping for Continuing Reinforcement Learning Taskscited by 28
  13. 2019Modular Deep Reinforcement Learning with Temporal Logic Specificationscited by 25
  14. 2020Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamplescited by 23
  15. 2020Reinforcement Learning Based Temporal Logic Control with Maximum Probabilistic Satisfactioncited by 22
  16. 2017A Policy Search Method For Temporal Logic Specified Reinforcement Learning Taskscited by 20
  17. 2019Induction of Subgoal Automata for Reinforcement Learningcited by 17
  18. 2021In a Nutshell, the Human Asked for This: Latent Goals for Following Temporal Specificationscited by 17
  19. 2021Learning Reward Machines: A Study in Partially Observable Reinforcement Learningcited by 16
  20. 2022Joint Learning of Reward Machines and Policies in Environments with Partially Known Semanticscited by 12
  21. 2022Learning to Follow Instructions in Text-Based Gamescited by 12
  22. 2019Planning With Uncertain Specifications (PUnS)cited by 11
  23. 2020Learning Non-Markovian Reward Models in MDPscited by 11
  24. 2022Exploiting Transformer in Sparse Reward Reinforcement Learning for Interpretable Temporal Logic Motion Planningcited by 10
  25. 2022Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machinescited by 10
  26. 2022Neurosymbolic Motion and Task Planning for Linear Temporal Logic Taskscited by 6
  27. 2021Lifelong Reinforcement Learning with Temporal Logic Formulas and Reward Machinescited by 5
  28. 2023Reinforcement Learning of Action and Query Policies with LTL Instructions under Uncertain Event Detectorcited by 5
  29. 2022Hierarchies of Reward Machinescited by 4
  30. 2021Collaborative rover-copter path planning and exploration with temporal logic specifications based on Bayesian update under uncertain environmentscited by 2
  31. 2023Assessing the Robustness of Intelligence-Driven Reinforcement Learningcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 3; 2026: 5.

11 papers.

  1. 2024DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RLcited by 21
  2. 2024Learning Robust Reward Machines from Noisy Labelscited by 7
  3. 2025Modeling Others' Minds as Codecited by 7
  4. 2025Ground-Compose-Reinforce: Grounding Language in Agentic Behaviours using Limited Datacited by 5
  5. 2025ARM-FM: Automated Reward Machines via Foundation Models for Compositional Reinforcement Learningcited by 5
  6. 2024FORM: Learning Expressive and Transferable First-Order Logic Reward Machinescited by 4
  7. 2026PlatoLTL: Scaling LTL-Guided Multi-Task RLcited by 2
  8. 2026DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applicationscited by 0
  9. 2026Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version)cited by 0
  10. 2026Active Reward Machine Inference From Raw State Trajectoriescited by 0
  11. 2026Safe Reinforcement Learning of Autonomous Highway Driving: A Unified Framework for Safety and Efficiencycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Physics-Informed Reward Machines
  2. 2025Expressive Reward Synthesis with the Runtime Monitoring Language
  3. 2025Fully Learnable Neural Reward Machines
  4. 2026Reward Models Are Secretly Value Functions: Temporally Coherent Reward Modeling
  5. 2024Neural Reward Machines
  6. 2024On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks
  7. 2026Reward Granularity in RLVR: Comparing Process and Outcome Reward Structures for Mathematical Reasoning in Small Language Models
  8. 2025Circuit-Aware Reward Training: A Mechanistic Framework for Longtail Robustness in RLHF