# Reinforcement Learning with Stochastic Reward Machines

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

## Key facts

- Cited by 7 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 10 of its 25 references that are in the map.
- First posted on arXiv 16 Oct 2025.

## Placed in

- Deep reinforcement learning methods / [Interpretable and logic-guided RL](https://mlsanity.com/deeprl/interpretable-and-logic-guided-rl/)

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

- [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)
- [Reinforcement Learning with Perturbed Rewards](https://mlsanity.com/paper/1810.01032/) (2018)
- [Reinforcement Learning with a Corrupted Reward Channel](https://mlsanity.com/paper/1705.08417/) (2017)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [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)
- [Reward Machines for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2007.01962/) (2020)
- [Reward Estimation for Variance Reduction in Deep Reinforcement Learning](https://mlsanity.com/paper/1805.03359/) (2018)
- [Induction of Subgoal Automata for Reinforcement Learning](https://mlsanity.com/paper/1911.13152/) (2019)

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

- [Expediting Reinforcement Learning by Incorporating Knowledge About Temporal Causality in the Environment](https://mlsanity.com/paper/2510.15456/) (2025)
- [Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes](https://mlsanity.com/paper/2512.14617/) (2025)
- [Active Learning of Symbolic Automata Over Rational Numbers](https://mlsanity.com/paper/2511.12315/) (2025)
- [About Time: Model-free Reinforcement Learning with Timed Reward Machines](https://mlsanity.com/paper/2512.17637/) (2025)
- [DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applications](https://mlsanity.com/paper/2602.03486/) (2026)
- [Reinforcement Learning with Symbolic Reward Machines](https://mlsanity.com/paper/2603.03068/) (2026)
- [Expert Behavior Prior Reinforcement Learning](https://mlsanity.com/paper/2607.21302/) (2026)

## Abstract (arXiv)

Reward machines are an established tool for dealing with reinforcement learning problems in which rewards are sparse and depend on complex sequences of actions. However, existing algorithms for learning reward machines assume an overly idealized setting where rewards have to be free of noise. To overcome this practical limitation, we introduce a novel type of reward machines, called stochastic reward machines, and an algorithm for learning them. Our algorithm, based on constraint solving, learns minimal stochastic reward machines from the explorations of a reinforcement learning agent. This algorithm can easily be paired with existing reinforcement learning algorithms for reward machines and guarantees to converge to an optimal policy in the limit. We demonstrate the effectiveness of our algorithm in two case studies and show that it outperforms both existing methods and a naive approach for handling noisy reward functions.