# Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 23 references that are in the map.
- First posted on arXiv 9 Jul 2021.

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

- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Omega-Regular Objectives in Model-Free Reinforcement Learning](https://mlsanity.com/paper/1810.00950/) (2018)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [Joint Inference of Reward Machines and Policies for Reinforcement Learning](https://mlsanity.com/paper/1909.05912/) (2019)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [Active Finite Reward Automaton Inference and Reinforcement Learning Using Queries and Counterexamples](https://mlsanity.com/paper/2006.15714/) (2020)
- [Learning Deterministic Weighted Automata with Queries and Counterexamples](https://mlsanity.com/paper/1910.13895/) (2019)
- [Learning and Solving Regular Decision Processes](https://mlsanity.com/paper/2003.01008/) (2020)
- [Online Learning of Non-Markovian Reward Models](https://mlsanity.com/paper/2009.12600/) (2020)
- [L*-Based Learning of Markov Decision Processes (Extended Version)](https://mlsanity.com/paper/1906.12239/) (2019)

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

- [Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics](https://mlsanity.com/paper/2204.11833/) (2022)
- [Learning Task Automata for Reinforcement Learning using Hidden Markov Models](https://mlsanity.com/paper/2208.11838/) (2022)
- [Learning Quadruped Locomotion Policies using Logical Rules](https://mlsanity.com/paper/2107.10969/) (2021)
- [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)
- [Efficient Reinforcement Learning in Probabilistic Reward Machines](https://mlsanity.com/paper/2408.10381/) (2024)
- [From monoliths to modules: Decomposing transducers for efficient world modelling](https://mlsanity.com/paper/2512.02193/) (2025)
- [Constructing Non-Markovian Decision Process via History Aggregator](https://mlsanity.com/paper/2506.24026/) (2025)
- [Learning Environment Models with Continuous Stochastic Dynamics](https://mlsanity.com/paper/2306.17204/) (2023)
- [Maximally Permissive Reward Machines](https://mlsanity.com/paper/2408.08059/) (2024)
- [Learning Quantitative Automata Modulo Theories](https://mlsanity.com/paper/2411.10601/) (2024)
- [Physics-Informed Reward Machines](https://mlsanity.com/paper/2508.14093/) (2025)
- [Exact Distinguishability in Non-Markovian Decision Processes](https://mlsanity.com/paper/2610.01527/) (2026)

## Abstract (arXiv)

The success of reinforcement learning in typical settings is predicated on Markovian assumptions on the reward signal by which an agent learns optimal policies. In recent years, the use of reward machines has relaxed this assumption by enabling a structured representation of non-Markovian rewards. In particular, such representations can be used to augment the state space of the underlying decision process, thereby facilitating non-Markovian reinforcement learning. However, these reward machines cannot capture the semantics of stochastic reward signals. In this paper, we make progress on this front by introducing probabilistic reward machines (PRMs) as a representation of non-Markovian stochastic rewards. We present an algorithm to learn PRMs from the underlying decision process and prove results around its correctness and convergence.