mlsanityData to 7 Oct 2026

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

arXiv 2510.27329 ↗First posted 31 Oct 2025cs.AIcited by 0

Not on the map. Why?

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 18 of its 36 references that are in the map. First posted on arXiv 31 Oct 2025.

Builds on

18 of 36 references.

References · 18

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,302
  3. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  4. 2018Data-Efficient Hierarchical Reinforcement Learningcited by 436
  5. 2016The Option-Critic Architecturecited by 433
  6. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 183
  7. 2016Reinforcement Learning With Temporal Logic Rewardscited by 114
  8. 2020A Composable Specification Language for Reinforcement Learning Taskscited by 68
  9. 2021Compositional Reinforcement Learning from Logical Specificationscited by 65
  10. 2022Modular Lifelong Reinforcement Learning via Neural Compositioncited by 39
  11. 2020Reward Machines for Cooperative Multi-Agent Reinforcement Learningcited by 35
  12. 2022Provably Safe Reinforcement Learning: Conceptual Analysis, Survey, and Benchmarkingcited by 31
6 more
  1. 2023Deep Laplacian-based Options for Temporally-Extended Explorationcited by 28
  2. 2020Induction and Exploitation of Subgoal Automata for Reinforcement Learningcited by 26
  3. 2020Abstract Value Iteration for Hierarchical Reinforcement Learningcited by 12
  4. 2024On the Limitations of Markovian Rewards to Express Multi-Objective, Risk-Sensitive, and Modal Taskscited by 9
  5. 2023Reinforcement Learning with Non-Cumulative Objectivecited by 4
  6. 2024FORM: Learning Expressive and Transferable First-Order Logic Reward Machinescited by 4

Built on by

Not cited yet.