# Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 64 references that are in the map.
- First posted on arXiv 20 Apr 2022.

## Builds on (most cited first, 24 of 24)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation](https://mlsanity.com/paper/1604.06057/) (2016)
- [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)
- [Flipout: Efficient Pseudo-Independent Weight Perturbations on Mini-Batches](https://mlsanity.com/paper/1803.04386/) (2018)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Omega-Regular Objectives in Model-Free Reinforcement Learning](https://mlsanity.com/paper/1810.00950/) (2018)
- [Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning](https://mlsanity.com/paper/1909.07299/) (2019)
- [Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications](https://mlsanity.com/paper/1609.07409/) (2016)
- [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)
- [A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications](https://mlsanity.com/paper/1409.5486/) (2014)
- [HouseExpo: A Large-scale 2D Indoor Layout Dataset for Learning-based Algorithms on Mobile Robots](https://mlsanity.com/paper/1903.09845/) (2019)
- [Induction of Subgoal Automata for Reinforcement Learning](https://mlsanity.com/paper/1911.13152/) (2019)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Correct-by-synthesis reinforcement learning with temporal logic constraints](https://mlsanity.com/paper/1503.01793/) (2015)
- [Stochastic Finite State Control of POMDPs with LTL Specifications](https://mlsanity.com/paper/2001.07679/) (2020)
- [Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications](https://mlsanity.com/paper/1409.3360/) (2014)
- [Online Learning of Non-Markovian Reward Models](https://mlsanity.com/paper/2009.12600/) (2020)
- [Active Perception and Control from Temporal Logic Specifications](https://mlsanity.com/paper/1905.03662/) (2019)
- [Reinforcement Learning with Temporal Logic Constraints for Partially-Observable Markov Decision Processes](https://mlsanity.com/paper/2104.01612/) (2021)
- [Optimal Temporal Logic Planning in Probabilistic Semantic Maps](https://mlsanity.com/paper/1510.06469/) (2015)
- [Barrier Functions for Multiagent-POMDPs with DTL Specifications](https://mlsanity.com/paper/2003.09267/) (2020)
- [Secure Control under Partial Observability with Temporal Logic Constraints](https://mlsanity.com/paper/1903.06873/) (2019)

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

- [Reward Machines for Deep RL in Noisy and Uncertain Environments](https://mlsanity.com/paper/2406.00120/) (2024)
- [Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machines](https://mlsanity.com/paper/2211.10902/) (2022)
- [Learning Task Automata for Reinforcement Learning using Hidden Markov Models](https://mlsanity.com/paper/2208.11838/) (2022)
- [Neural Reward Machines](https://mlsanity.com/paper/2408.08677/) (2024)
- [Learning Robust Reward Machines from Noisy Labels](https://mlsanity.com/paper/2408.14871/) (2024)
- [Hierarchies of Reward Machines](https://mlsanity.com/paper/2205.15752/) (2022)
- [Provably Efficient Exploration in Reward Machines with Low Regret](https://mlsanity.com/paper/2412.19194/) (2024)
- [Accelerated Learning with Linear Temporal Logic using Differentiable Simulation](https://mlsanity.com/paper/2506.01167/) (2025)
- [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)
- [Active Reward Machine Inference From Raw State Trajectories](https://mlsanity.com/paper/2604.07480/) (2026)

## Abstract (arXiv)

We study the problem of reinforcement learning for a task encoded by a reward machine. The task is defined over a set of properties in the environment, called atomic propositions, and represented by Boolean variables. One unrealistic assumption commonly used in the literature is that the truth values of these propositions are accurately known. In real situations, however, these truth values are uncertain since they come from sensors that suffer from imperfections. At the same time, reward machines can be difficult to model explicitly, especially when they encode complicated tasks. We develop a reinforcement-learning algorithm that infers a reward machine that encodes the underlying task while learning how to execute it, despite the uncertainties of the propositions' truth values. In order to address such uncertainties, the algorithm maintains a probabilistic estimate about the truth value of the atomic propositions; it updates this estimate according to new sensory measurements that arrive from the exploration of the environment. Additionally, the algorithm maintains a hypothesis reward machine, which acts as an estimate of the reward machine that encodes the task to be learned. As the agent explores the environment, the algorithm updates the hypothesis reward machine according to the obtained rewards and the estimate of the atomic propositions' truth value. Finally, the algorithm uses a Q-learning procedure for the states of the hypothesis reward machine to determine the policy that accomplishes the task. We prove that the algorithm successfully infers the reward machine and asymptotically learns a policy that accomplishes the respective task.