# Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning

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

## Key facts

- Cited by 191 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2020.

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

- [LTL2Action: Generalizing LTL Instructions for Multi-Task RL](https://mlsanity.com/paper/2102.06858/) (2021)
- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [Grounding Complex Natural Language Commands for Temporal Tasks in Unseen Environments](https://mlsanity.com/paper/2302.11649/) (2023)
- [Beyond Preferences in AI Alignment](https://mlsanity.com/paper/2408.16984/) (2024)
- [Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2206.09421/) (2022)
- [DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RL](https://mlsanity.com/paper/2410.04631/) (2024)
- [Policy Optimization with Linear Temporal Logic Constraints](https://mlsanity.com/paper/2206.09546/) (2022)
- [Eventual Discounting Temporal Logic Counterfactual Experience Replay](https://mlsanity.com/paper/2303.02135/) (2023)
- [Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2411.00205/) (2024)
- [Sample Efficient Model-free Reinforcement Learning from LTL Specifications with Optimality Guarantees](https://mlsanity.com/paper/2305.01381/) (2023)
- [A Review of Reward Functions for Reinforcement Learning in the context of Autonomous Driving](https://mlsanity.com/paper/2405.01440/) (2024)
- [Learning Reward Machines: A Study in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2112.09477/) (2021)
- [Behavior Alignment via Reward Function Optimization](https://mlsanity.com/paper/2310.19007/) (2023)
- [Goals as Reward-Producing Programs](https://mlsanity.com/paper/2405.13242/) (2024)
- [Three Dogmas of Reinforcement Learning](https://mlsanity.com/paper/2407.10583/) (2024)
- [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)
- [LgTS: Dynamic Task Sampling using LLM-generated sub-goals for Reinforcement Learning Agents](https://mlsanity.com/paper/2310.09454/) (2023)
- [LTL-Constrained Policy Optimization with Cycle Experience Replay](https://mlsanity.com/paper/2404.11578/) (2024)
- [Reward Machines for Deep RL in Noisy and Uncertain Environments](https://mlsanity.com/paper/2406.00120/) (2024)
- [Exploiting Transformer in Sparse Reward Reinforcement Learning for Interpretable Temporal Logic Motion Planning](https://mlsanity.com/paper/2209.13220/) (2022)
- [Noisy Symbolic Abstractions for Deep RL: A case study with Reward Machines](https://mlsanity.com/paper/2211.10902/) (2022)
- [Programmatic Reward Design by Example](https://mlsanity.com/paper/2112.08438/) (2021)
- [A Hierarchical Bayesian Approach to Inverse Reinforcement Learning with Symbolic Reward Machines](https://mlsanity.com/paper/2204.09772/) (2022)
- [Accelerated Reinforcement Learning for Temporal Logic Control Objectives](https://mlsanity.com/paper/2205.04424/) (2022)
- [Skill Machines: Temporal Logic Skill Composition in Reinforcement Learning](https://mlsanity.com/paper/2205.12532/) (2022)
- [On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks](https://mlsanity.com/paper/2401.14811/) (2024)
- [Specification-Guided Learning of Nash Equilibria with High Social Welfare](https://mlsanity.com/paper/2206.03348/) (2022)

## Abstract (arXiv)

Reinforcement learning (RL) methods usually treat reward functions as black boxes. As such, these methods must extensively interact with the environment in order to discover rewards and optimal policies. In most RL applications, however, users have to program the reward function and, hence, there is the opportunity to make the reward function visible -- to show the reward function's code to the RL agent so it can exploit the function's internal structure to learn optimal policies in a more sample efficient manner. In this paper, we show how to accomplish this idea in two steps. First, we propose reward machines, a type of finite state machine that supports the specification of reward functions while exposing reward function structure. We then describe different methodologies to exploit this structure to support learning, including automated reward shaping, task decomposition, and counterfactual reasoning with off-policy learning. Experiments on tabular and continuous domains, across different tasks and RL agents, show the benefits of exploiting reward structure with respect to sample efficiency and the quality of resultant policies. Finally, by virtue of being a form of finite state machine, reward machines have the expressive power of a regular language and as such support loops, sequences and conditionals, as well as the expression of temporally extended properties typical of linear temporal logic and non-Markovian reward specification.