# FORM: Learning Expressive and Transferable First-Order Logic Reward Machines

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

## Key facts

- Cited by 4 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 13 of its 40 references that are in the map.
- First posted on arXiv 31 Dec 2024.

## 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, 13 of 13)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Learning to Drive in a Day](https://mlsanity.com/paper/1807.00412/) (2018)
- [Reinforcement learning](https://mlsanity.com/paper/2405.10369/) (2024)
- [Joint Inference of Reward Machines and Policies for Reinforcement Learning](https://mlsanity.com/paper/1909.05912/) (2019)
- [Market Making via Reinforcement Learning](https://mlsanity.com/paper/1804.04216/) (2018)
- [Reinforcement Learning with Non-Markovian Rewards](https://mlsanity.com/paper/1912.02552/) (2019)
- [Induction and Exploitation of Subgoal Automata for Reinforcement Learning](https://mlsanity.com/paper/2009.03855/) (2020)
- [The Logical Options Framework](https://mlsanity.com/paper/2102.12571/) (2021)
- [Reward Machines for Deep RL in Noisy and Uncertain Environments](https://mlsanity.com/paper/2406.00120/) (2024)
- [Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach](https://mlsanity.com/paper/2402.19265/) (2024)
- [Learning Robust Reward Machines from Noisy Labels](https://mlsanity.com/paper/2408.14871/) (2024)
- [Counting Reward Automata: Sample Efficient Reinforcement Learning Through the Exploitation of Reward Function Structure](https://mlsanity.com/paper/2312.11364/) (2023)

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

- [Pushdown Reward Machines for Reinforcement Learning](https://mlsanity.com/paper/2508.06894/) (2025)
- [Reinforcement Learning for Long-Horizon Unordered Tasks: From Boolean to Coupled Reward Machines](https://mlsanity.com/paper/2510.27329/) (2025)
- [Expressive Temporal Specifications for Reward Monitoring](https://mlsanity.com/paper/2511.12808/) (2025)
- [Reinforcement Learning with Symbolic Reward Machines](https://mlsanity.com/paper/2603.03068/) (2026)

## Abstract (arXiv)

Reward machines (RMs) are an effective approach for addressing non-Markovian rewards in reinforcement learning (RL) through finite-state machines. Traditional RMs, which label edges with propositional logic formulae, inherit the limited expressivity of propositional logic. This limitation hinders the learnability and transferability of RMs since complex tasks will require numerous states and edges. To overcome these challenges, we propose First-Order Reward Machines (textttFORMs), which use first-order logic to label edges, resulting in more compact and transferable RMs. We introduce a novel method for learning textttFORMs and a multi-agent formulation for exploiting them and facilitate their transferability, where multiple agents collaboratively learn policies for a shared textttFORM. Our experimental results demonstrate the scalability of textttFORMs with respect to traditional RMs. Specifically, we show that textttFORMs can be effectively learnt for tasks where traditional RM learning approaches fail. We also show significant improvements in learning speed and task transferability thanks to the multi-agent learning framework and the abstraction provided by the first-order language.