# Maximally Permissive Reward Machines

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 15 Aug 2024.

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

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Reinforcement learning](https://mlsanity.com/paper/2405.10369/) (2024)
- [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)
- [SDRL: Interpretable and Data-efficient Deep Reinforcement Learning Leveraging Symbolic Planning](https://mlsanity.com/paper/1811.00090/) (2018)
- [Joint Inference of Reward Machines and Policies for Reinforcement Learning](https://mlsanity.com/paper/1909.05912/) (2019)
- [PEORL: Integrating Symbolic Planning and Hierarchical Reinforcement Learning for Robust Decision-Making](https://mlsanity.com/paper/1804.07779/) (2018)
- [Reward Machines for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2007.01962/) (2020)
- [Plan To Predict: Learning an Uncertainty-Foreseeing Model for Model-Based Reinforcement Learning](https://mlsanity.com/paper/2301.08502/) (2023)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Decentralized Graph-Based Multi-Agent Reinforcement Learning Using Reward Machines](https://mlsanity.com/paper/2110.00096/) (2021)

## Abstract (arXiv)

Reward machines allow the definition of rewards for temporally extended tasks and behaviors. Specifying "informative" reward machines can be challenging. One way to address this is to generate reward machines from a high-level abstract description of the learning environment, using techniques such as AI planning. However, previous planning-based approaches generate a reward machine based on a single (sequential or partial-order) plan, and do not allow maximum flexibility to the learning agent. In this paper we propose a new approach to synthesising reward machines which is based on the set of partial order plans for a goal. We prove that learning using such "maximally permissive" reward machines results in higher rewards than learning using RMs based on a single plan. We present experimental results which support our theoretical claims by showing that our approach obtains higher rewards than the single-plan approach in practice.