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

The paper introduces three generalizations of reward machines (RMs) to enhance reinforcement learning for long-horizon unordered tasks: Numeric RMs for compact task representation, agenda RMs for tracking remaining subtasks, and coupled RMs for managing subtask dependencies. It also presents QCoRM, a Q-learning-based algorithm that utilizes coupled RMs, ensuring global optimality in tabular settings. Experimental results indicate that QCoRM outperforms baseline algorithms across various domains, highlighting its potential for improving sample efficiency in complex reinforcement learning scenarios.