# Reinforcement Learning for Long-Horizon Unordered Tasks: From Boolean to Coupled Reward Machines

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods.
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 31 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, 18 of 18)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Data-Efficient Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1805.08296/) (2018)
- [The Option-Critic Architecture](https://mlsanity.com/paper/1609.05140/) (2016)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [Modular Lifelong Reinforcement Learning via Neural Composition](https://mlsanity.com/paper/2207.00429/) (2022)
- [Reward Machines for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2007.01962/) (2020)
- [Provably Safe Reinforcement Learning: Conceptual Analysis, Survey, and Benchmarking](https://mlsanity.com/paper/2205.06750/) (2022)
- [Deep Laplacian-based Options for Temporally-Extended Exploration](https://mlsanity.com/paper/2301.11181/) (2023)
- [Induction and Exploitation of Subgoal Automata for Reinforcement Learning](https://mlsanity.com/paper/2009.03855/) (2020)
- [Abstract Value Iteration for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2010.15638/) (2020)
- [On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Tasks](https://mlsanity.com/paper/2401.14811/) (2024)
- [Reinforcement Learning with Non-Cumulative Objective](https://mlsanity.com/paper/2307.04957/) (2023)
- [FORM: Learning Expressive and Transferable First-Order Logic Reward Machines](https://mlsanity.com/paper/2501.00364/) (2024)

## Abstract (arXiv)

Reward machines (RMs) inform reinforcement learning agents about the reward structure of the environment, enabling support for non-Markovian tasks and improving sample efficiency. However, learning with RMs is ill-suited for long-horizon problems where subtasks can be completed in any order. In such cases, the amount of information to learn increases exponentially with the number of unordered subtasks. We address this issue by introducing three generalisations of RMs: (1) Numeric RMs allow users to express complex tasks in a compact form. (2) In agenda RMs, states are associated with an agenda that tracks the remaining subtasks to complete. (3) Coupled RMs have coupled states associated with each subtask in the agenda. In addition, we introduce QCoRM, a new task-decomposition Q-learning-based algorithm that leverages coupled RMs and preserves global optimality guarantees in tabular settings. Our experiments across four domains -- featuring both discrete and continuous action and state spaces -- demonstrate that QCoRM scales better than baseline algorithms for long-horizon problems with unordered subtasks.