# Joint Inference of Reward Machines and Policies for Reinforcement Learning

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2019.

## Built on by (most cited first, 30 of 56)

- [A Survey on Interpretable Reinforcement Learning](https://mlsanity.com/paper/2112.13112/) (2021)
- [Knowledge Enhanced Machine Learning Pipeline against Diverse Adversarial Attacks](https://mlsanity.com/paper/2106.06235/) (2021)
- [Active Task-Inference-Guided Deep Inverse Reinforcement Learning](https://mlsanity.com/paper/2001.09227/) (2020)
- [In a Nutshell, the Human Asked for This: Latent Goals for Following Temporal Specifications](https://mlsanity.com/paper/2110.09461/) (2021)
- [Learning Reward Machines: A Study in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2112.09477/) (2021)
- [Verifiable and Compositional Reinforcement Learning Systems](https://mlsanity.com/paper/2106.05864/) (2021)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Overcoming Exploration: Deep Reinforcement Learning for Continuous Control in Cluttered Environments from Temporal Logic Specifications](https://mlsanity.com/paper/2201.12231/) (2022)
- [Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics](https://mlsanity.com/paper/2204.11833/) (2022)
- [Automaton-Based Representations of Task Knowledge from Generative Language Models](https://mlsanity.com/paper/2212.01944/) (2022)
- [Reward Machines for Deep RL in Noisy and Uncertain Environments](https://mlsanity.com/paper/2406.00120/) (2024)
- [Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes](https://mlsanity.com/paper/2205.01053/) (2022)
- [Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machines](https://mlsanity.com/paper/2211.10902/) (2022)
- [Automata Learning meets Shielding](https://mlsanity.com/paper/2212.01838/) (2022)
- [Using Large Language Models to Automate and Expedite Reinforcement Learning with Reward Machine](https://mlsanity.com/paper/2402.07069/) (2024)
- [Decentralized Graph-Based Multi-Agent Reinforcement Learning Using Reward Machines](https://mlsanity.com/paper/2110.00096/) (2021)
- [Learning Task Automata for Reinforcement Learning using Hidden Markov Models](https://mlsanity.com/paper/2208.11838/) (2022)
- [Learning Robust Reward Machines from Noisy Labels](https://mlsanity.com/paper/2408.14871/) (2024)
- [Reinforcement Learning with Stochastic Reward Machines](https://mlsanity.com/paper/2510.14837/) (2025)
- [Learning Quadruped Locomotion Policies using Logical Rules](https://mlsanity.com/paper/2107.10969/) (2021)
- [Learning Minimally-Violating Continuous Control for Infeasible Linear Temporal Logic Specifications](https://mlsanity.com/paper/2210.01162/) (2022)
- [Reinforcement Learning with Knowledge Representation and Reasoning: A Brief Survey](https://mlsanity.com/paper/2304.12090/) (2023)
- [Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov](https://mlsanity.com/paper/2401.11325/) (2024)
- [ARM-FM: Automated Reward Machines via Foundation Models for Compositional Reinforcement Learning](https://mlsanity.com/paper/2510.14176/) (2025)
- [Hierarchies of Reward Machines](https://mlsanity.com/paper/2205.15752/) (2022)
- [Reinforcement Learning under Partial Observability Guided by Learned Environment Models](https://mlsanity.com/paper/2206.11708/) (2022)
- [Learning Symbolic Representations for Reinforcement Learning of Non-Markovian Behavior](https://mlsanity.com/paper/2301.02952/) (2023)
- [FORM: Learning Expressive and Transferable First-Order Logic Reward Machines](https://mlsanity.com/paper/2501.00364/) (2024)
- [Uncertainty-Aware Signal Temporal Logic Inference](https://mlsanity.com/paper/2105.11545/) (2021)
- [Verifiable Reinforcement Learning Systems via Compositionality](https://mlsanity.com/paper/2309.06420/) (2023)

## Abstract (arXiv)

Incorporating high-level knowledge is an effective way to expedite reinforcement learning (RL), especially for complex tasks with sparse rewards. We investigate an RL problem where the high-level knowledge is in the form of reward machines, i.e., a type of Mealy machine that encodes the reward functions. We focus on a setting in which this knowledge is a priori not available to the learning agent. We develop an iterative algorithm that performs joint inference of reward machines and policies for RL (more specifically, q-learning). In each iteration, the algorithm maintains a hypothesis reward machine and a sample of RL episodes. It derives q-functions from the current hypothesis reward machine, and performs RL to update the q-functions. While performing RL, the algorithm updates the sample by adding RL episodes along which the obtained rewards are inconsistent with the rewards based on the current hypothesis reward machine. In the next iteration, the algorithm infers a new hypothesis reward machine from the updated sample. Based on an equivalence relationship we defined between states of reward machines, we transfer the q-functions between the hypothesis reward machines in consecutive iterations. We prove that the proposed algorithm converges almost surely to an optimal policy in the limit if a minimal reward machine can be inferred and the maximal length of each RL episode is sufficiently long. The experiments show that learning high-level knowledge in the form of reward machines can lead to fast convergence to optimal policies in RL, while standard RL methods such as q-learning and hierarchical RL methods fail to converge to optimal policies after a substantial number of training steps in many tasks.