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

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 51 references that are in the map.
- First posted on arXiv 20 Nov 2022.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [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)
- [A Survey of Reinforcement Learning Informed by Natural Language](https://mlsanity.com/paper/1906.03926/) (2019)
- [Language as an Abstraction for Hierarchical Deep Reinforcement Learning](https://mlsanity.com/paper/1906.07343/) (2019)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Zero-Shot Task Generalization with Multi-Task Deep Reinforcement Learning](https://mlsanity.com/paper/1706.05064/) (2017)
- [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)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [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)
- [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)
- [Systematic Generalisation through Task Temporal Logic and Deep Reinforcement Learning](https://mlsanity.com/paper/2006.08767/) (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)
- [Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics](https://mlsanity.com/paper/2204.11833/) (2022)
- [Learning to Follow Instructions in Text-Based Games](https://mlsanity.com/paper/2211.04591/) (2022)
- [Planning With Uncertain Specifications (PUnS)](https://mlsanity.com/paper/1906.03218/) (2019)

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

- [Reward Machines for Deep RL in Noisy and Uncertain Environments](https://mlsanity.com/paper/2406.00120/) (2024)
- [DeepDFA: Automata Learning through Neural Probabilistic Relaxations](https://mlsanity.com/paper/2408.08622/) (2024)
- [Neural Reward Machines](https://mlsanity.com/paper/2408.08677/) (2024)
- [Learning Robust Reward Machines from Noisy Labels](https://mlsanity.com/paper/2408.14871/) (2024)
- [Ground-Compose-Reinforce: Grounding Language in Agentic Behaviours using Limited Data](https://mlsanity.com/paper/2507.10741/) (2025)
- [Learning Hidden Subgoals under Temporal Ordering Constraints in Reinforcement Learning](https://mlsanity.com/paper/2411.01425/) (2024)
- [Fully Learnable Neural Reward Machines](https://mlsanity.com/paper/2509.19017/) (2025)
- [Grounding LTL Tasks in Sub-Symbolic RL Environments for Zero-Shot Generalization](https://mlsanity.com/paper/2602.09761/) (2026)
- [DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applications](https://mlsanity.com/paper/2602.03486/) (2026)
- [Safe Reinforcement Learning of Autonomous Highway Driving: A Unified Framework for Safety and Efficiency](https://mlsanity.com/paper/2606.14609/) (2026)

## Abstract (arXiv)

Natural and formal languages provide an effective mechanism for humans to specify instructions and reward functions. We investigate how to generate policies via RL when reward functions are specified in a symbolic language captured by Reward Machines, an increasingly popular automaton-inspired structure. We are interested in the case where the mapping of environment state to a symbolic (here, Reward Machine) vocabulary -- commonly known as the labelling function -- is uncertain from the perspective of the agent. We formulate the problem of policy learning in Reward Machines with noisy symbolic abstractions as a special class of POMDP optimization problem, and investigate several methods to address the problem, building on existing and new techniques, the latter focused on predicting Reward Machine state, rather than on grounding of individual symbols. We analyze these methods and evaluate them experimentally under varying degrees of uncertainty in the correct interpretation of the symbolic vocabulary. We verify the strength of our approach and the limitation of existing methods via an empirical investigation on both illustrative, toy domains and partially observable, deep RL domains.