# Learning Reward Machines: A Study in Partially Observable Reinforcement Learning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 55 references that are in the map.
- First posted on arXiv 17 Dec 2021.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Learning Dexterous In-Hand Manipulation](https://mlsanity.com/paper/1808.00177/) (2018)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [Reinforcement Learning with Unsupervised Auxiliary Tasks](https://mlsanity.com/paper/1611.05397/) (2016)
- [Challenges of Real-World Reinforcement Learning](https://mlsanity.com/paper/1904.12901/) (2019)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Sample Efficient Actor-Critic with Experience Replay](https://mlsanity.com/paper/1611.01224/) (2016)
- [Control of Memory, Active Perception, and Action in Minecraft](https://mlsanity.com/paper/1605.09128/) (2016)
- [Optimizing Agent Behavior over Long Time Scales by Transporting Value](https://mlsanity.com/paper/1810.06721/) (2018)
- [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 Finite-State Controllers for Partially Observable Environments](https://mlsanity.com/paper/1301.6721/) (2013)
- [Interpretable Sequence Classification via Discrete Optimization](https://mlsanity.com/paper/2010.02819/) (2020)
- [Induction of Subgoal Automata for Reinforcement Learning](https://mlsanity.com/paper/1911.13152/) (2019)
- [Active Task-Inference-Guided Deep Inverse Reinforcement Learning](https://mlsanity.com/paper/2001.09227/) (2020)
- [Memory Augmented Control Networks](https://mlsanity.com/paper/1709.05706/) (2017)
- [The act of remembering: a study in partially observable reinforcement learning](https://mlsanity.com/paper/2010.01753/) (2020)
- [Online Learning of Non-Markovian Reward Models](https://mlsanity.com/paper/2009.12600/) (2020)
- [Learning Moore Machines from Input-Output Traces](https://mlsanity.com/paper/1605.07805/) (2016)

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

- [f-Policy Gradients: A General Framework for Goal Conditioned RL using f-Divergences](https://mlsanity.com/paper/2310.06794/) (2023)
- [Adaptive Layer Splitting for Wireless LLM Inference in Edge Computing: A Model-Based Reinforcement Learning Approach](https://mlsanity.com/paper/2406.02616/) (2024)
- [Reward Machines for Deep RL in Noisy and Uncertain Environments](https://mlsanity.com/paper/2406.00120/) (2024)
- [Learning Robust Reward Machines from Noisy Labels](https://mlsanity.com/paper/2408.14871/) (2024)
- [Reinforcement Learning with Knowledge Representation and Reasoning: A Brief Survey](https://mlsanity.com/paper/2304.12090/) (2023)
- [Pushdown Reward Machines for Reinforcement Learning](https://mlsanity.com/paper/2508.06894/) (2025)
- [Knowledge-Informed Auto-Penetration Testing Based on Reinforcement Learning with Reward Machine](https://mlsanity.com/paper/2405.15908/) (2024)
- [Learning Reward Machines from Partially Observed Policies](https://mlsanity.com/paper/2502.03762/) (2025)
- [Bayesian Inverse Reinforcement Learning for Non-Markovian Rewards](https://mlsanity.com/paper/2406.13991/) (2024)
- [Toward Learning POMDPs Beyond Full-Rank Actions and State Observability](https://mlsanity.com/paper/2601.18930/) (2026)
- [A Method for Fast Autonomy Transfer in Reinforcement Learning](https://mlsanity.com/paper/2407.20466/) (2024)
- [Active Learning of Symbolic Automata Over Rational Numbers](https://mlsanity.com/paper/2511.12315/) (2025)
- [Active Reward Machine Inference From Raw State Trajectories](https://mlsanity.com/paper/2604.07480/) (2026)
- [The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2606.03048/) (2026)
- [When Does Reward Teach State? A Hidden-Automaton Instrument and a Group-Language Warning Signal](https://mlsanity.com/paper/2607.11953/) (2026)
- [Reward Structure Shapes the Interaction Between Episodic Exploration and Neural Memory in Reinforcement Learning](https://mlsanity.com/paper/2608.05111/) (2026)

## Abstract (arXiv)

Reinforcement learning (RL) is a central problem in artificial intelligence. This problem consists of defining artificial agents that can learn optimal behaviour by interacting with an environment -- where the optimal behaviour is defined with respect to a reward signal that the agent seeks to maximize. Reward machines (RMs) provide a structured, automata-based representation of a reward function that enables an RL agent to decompose an RL problem into structured subproblems that can be efficiently learned via off-policy learning. Here we show that RMs can be learned from experience, instead of being specified by the user, and that the resulting problem decomposition can be used to effectively solve partially observable RL problems. We pose the task of learning RMs as a discrete optimization problem where the objective is to find an RM that decomposes the problem into a set of subproblems such that the combination of their optimal memoryless policies is an optimal policy for the original problem. We show the effectiveness of this approach on three partially observable domains, where it significantly outperforms A3C, PPO, and ACER, and discuss its advantages, limitations, and broader potential.