REVIEW 4 major objections 5 minor 31 references
Reinforcement Learning for Long-Horizon Unordered Tasks: From Boolean to Coupled Reward Machines
T0 review · 4 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash
Pith's one-line read By splitting a reward machine into coupled per-subtask copies and ordering them with a shortest-observed-steps heuristic, CoRM learns unordered long-horizon tasks with a linear amount of Q-learning information instead of an exponential amou
desk verdict Coupled reward machines are a real step forward, but the reward in Eq. 11 has a sign error that breaks the paper's main optimality guarantee. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the coupled reward machine with labels ⟨d, T, x⟩: d is RM depth, T is the agenda of remaining subtasks, and x is the single current objective. It splits a state into as many coupled sub-states as there are remaining subtasks, so the agent is 'in' all of them at once. The escalation mechanism is the episode-length-dependent final reward of Eq. 11: R(K) = 1 for the shortest observed episode, γ^{ΔK+1}+R(K^x) for longer ones, with a window ΔK_w capping the penalty. This reward makes locally optimal but globally sub-optimal subtask policies less attractive, and the η table provides the greedy high-level ordering.
What would settle it
On a small deterministic Delivery instance (say 3 boxes), run CoRM to convergence and compare its return with an exhaustive Q-learner over the full reward-machine state space; any gap in the converged return would falsify the paper's optimality-preservation claim.
Extended reading notes
Core claim
The paper's central claim is that a task with N unordered subtasks can be learnt through one Q-function per subtask rather than one Q-function per reward-machine state. This is made possible by coupled reward machines: the RM state is split into coupled copies, one per remaining subtask, each labelled with the same agenda, and the agent treats all copies as concurrent. Low-level Q-updates run in parallel on environment states augmented with the single subtask objective; a high-level controller stores η_u = minimum steps observed from each RM state to a goal and picks the coupled state with the smallest η. To bind the two levels, subtask completions receive a final reward R(K) that equals 1 w
Load-bearing premise
The global-optimality claim assumes a deterministic environment and assumes the agent can actually compute the episode-length final reward from Eq. 11, which depends on a local subtask length that the paper never shows how to measure.
Editorial extensions
If this is right
- For a task with N unordered subtasks, the agent learns O(N) low-level policies instead of O(N!) RM-state policies.
- The same decomposition works for sequential tasks too: CoRM reuses one policy per distinct objective rather than one per RM state.
- In deterministic environments, the final-episode-length reward lets CoRM retain tabular Q-learning's optimality guarantees, unlike hierarchical methods that relax them.
- The approach ports to deep RL through a replay buffer that stores RM transitions, so continuous state and action domains benefit as well.
- Standard RM baselines exhaust memory on 8-box Delivery, while CoRM solves it within the same step budget; runtime grows linearly in the number of subtasks.
Reading between the lines
- Inference — If η is replaced by an expected-length estimator, the same architecture would apply to stochastic MDPs; the paper notes this as future work, and the current proof would need to change.
- Inference — The agenda representation could be extended to partially ordered tasks, where the agenda is a DAG of available subtasks; then low-level policies would still number O(N), and ordering decisions would be made among the currently available set.
- Inference — Because the final reward depends only on total episode length, tasks where time is not the real cost (e.g., energy or safety) would need a different scalar signal to get the same global-optimality argument.
- Inference — The explicit exploration over RM transitions during learning suggests that the method's theoretical efficiency depends on the agent trying every completion order early, so in very large task sets exploration itself could become the bottleneck.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces three generalizations of reward machines—numeric, agenda, and coupled RMs—to handle long-horizon tasks with unordered subtasks. The main algorithmic contribution is CoRM (Q-learning with coupled RMs), which learns one low-level Q-function per subtask and uses a high-level controller that selects the next subtask according to the minimum experienced number of steps ηu. A final reward R(K) in Eq. (11) is intended to couple low-level choices with global episode length, and the authors claim that this preserves Q-learning optimality in deterministic tabular settings. Experiments compare CoRM with QRM/CRM baselines in Delivery, Office, and Water domains and report faster convergence and better scaling.
Significance. If the central theoretical claim were correct, CoRM would be a valuable contribution: it replaces an exponentially sized RM state space with a number of subtask-specific Q-functions linear in the number of subtasks, and the runtime results in Figs. 3g–3i indeed show linear scaling for CoRM versus exponential scaling for CRM baselines. The paper also provides a clear taxonomy of numeric/agenda/coupled RMs and a useful ablation separating the decomposition benefit from the length-dependent reward. However, the optimality guarantee rests on an invalid bound and an uncomputable reward, so the headline claim is not established. The empirical scaling results are interesting, but they do not compensate for the false theoretical statement.
major comments (4)
- [§4, Eqs. (9)–(11)] Invalid derivation of R(K). Substituting the bounded immediate rewards into Eq. (9) yields R(K1) < γ^{Kx2−Kx1} − C·B, with C=γ^{1−Kx1}/(1−γ) and B=rmax−rmin−γ^{Kx1−1}(rmax−γ^{Kx2−Kx1}rmin). Since the subtracted quantity in B is nonnegative, B ≤ rmax−rmin, so replacing B by rmax−rmin makes the upper bound looser, not tighter; Eq. (10) does not follow. The reward in Eq. (11) can then violate the required inequality. Example: γ=0.9, rmax=1, rmin=0, Kx1=2, Kx2=3, Kmin=4, K1=5 gives R(5)=11.92, Q1=10.73, and Q2=0.81, so Q1>Q2. Thus the claim that optimality guarantees are preserved is false for the stated reward.
- [§4, Eq. (11)] The reward is not implementable. R(Kx)=γ^{1−Kx1}/(1−γ)(rmax−rmin) requires the length Kx1 of the locally optimal policy for subtask x, but Kx1 is precisely the unknown quantity being learned. The paper gives no procedure for computing or estimating Kx1 online, and rmax/rmin are merely assumed known. Since Eq. (4) uses R(K) in the Q-learning target, the agent cannot execute the update it is supposed to perform. This is separate from the derivation error above: even with oracle access to Kx1, the formula fails.
- [§4 and §6, high-level selection] The high-level controller chooses the next subtask by the minimum experienced ηu, and §6 asserts convergence to an optimal solution in deterministic environments without a proof or theorem. In stochastic environments the minimum observed length is not a sufficient statistic, a point the paper itself defers to future work. Moreover, the low-level derivation compares returns only up to completion of subtask x (Eqs. 7–8) and ignores rewards obtained after that completion, although R(K) is assigned per subtask and later subtasks also contribute to the return. A formal convergence argument is needed for the claimed guarantee.
- [§5, experimental protocol] The optimality-preserving reward is never tested in a setting where Q-learning guarantees could apply. In the tabular domains the authors set ΔKw=−1, which disables the length-dependent term and gives a constant reward of 1 upon every subtask completion (Eq. 11). The only domain using ΔKw>0 is Water, which is solved with DDQN, where no optimality guarantees exist. Thus the experiments do not provide evidence for the theoretical claim; the ablation in Fig. 3e–f shows only that the length-dependent reward changes Water's behavior, not that it preserves optimality.
minor comments (5)
- [Abstract vs. §4] The name QCoRM appears in the abstract but the body consistently uses CoRM; please standardize.
- [§2.1, Eq. (2)] The notation x \xleftarrow[\alpha]{}-y is confusing; use the standard form x ← x + α(y − x) or state it explicitly.
- [§4, Eq. (11)] The text says that when K ≠ Kmin the reward decreases from 1 to γ^{ΔKw+1}, but the formula includes the additive term R(Kx), so the reward can exceed 1. The prose should match the equation.
- [§5.3] Typo: 'join optimisation' should be 'joint optimisation.'
- [Figure 2(c)] The notation 0{1,2}1, 0{1,2}2 is used before labels ⟨d,T,x⟩ are fully explained; the caption should define d, T, and x.
Circularity Check
No material circularity; the Eq. 11 reward gap is a soundness issue, not a by-construction reduction.
full rationale
CoRM's central derivation is not circular. The low-level Q-update (Eq. 3), the final-reward construction (Eqs. 5-10), and the η-based high-level ordering are stated mechanisms rather than quantities fitted to the experimental outputs. The optimality claim is justified by an inequality argument whose premises (reward bounds, K2^x > K1^x) are independent of the experimental results, so the claim does not reduce to the conclusion by definition. The only author-overlapping citation (Drexler, Seipp, and Geffner 2023, where Seipp is a coauthor) appears as related work and is not load-bearing; the load-bearing citations (Watkins and Dayan 1992; Icarte et al. 2022, etc.) are external. Theorem 2 is close to a definitional tautology--the proof says 'the task progression is completely defined by d, T, and x' and then concludes the labels are unique--but it only motivates state merging and does not carry the paper's main scalability or optimality claims. I do flag a serious non-circular weakness: the step from Eq. 9 to Eq. 10 loosens the exact bound, so Eq. 11's R(K) can satisfy Eq. 10 while violating the required inequality (e.g., γ=0.9, rmax=1, rmin=0, K1^x=2, K2^x=3, K1=5 gives the globally sub-optimal policy a higher Q-value). Additionally, R(K) depends on the unobservable local length K1^x, and the paper never states how the agent computes it. These are soundness/completeness gaps, not equivalence-by-construction, so they do not raise the circularity score.
Assumptions & free parameters
free parameters (2)
- ΔKw (episode-length window) =
−1 for tabular domains; 80 for Water
- rmax, rmin, and local policy length Kx1 in R(Kx) =
not specified
assumptions (6)
- standard math Standard tabular Q-learning convergence requires infinite visits to all state-action pairs
- domain assumption Assumption 1: numeric variables in numeric RMs are discrete and bounded
- domain assumption Assumption 4: collections of tasks encapsulated in numeric variables can be completed in any order
- domain assumption Environment is deterministic
- ad hoc to paper Agent exists concurrently in all coupled RM states
- ad hoc to paper The final reward R(K) in Eq. 11 is implementable despite unobservable Kx1 and reward bounds
Cite this review
Pith. "Pith review of Reinforcement Learning for Long-Horizon Unordered Tasks: From Boolean to Coupled Reward Machines." pith.science (2026). https://pith.science/paper/JYNJBFPI
@misc{pith2026251027329,
author = {Pith},
title = {Pith review of: Reinforcement Learning for Long-Horizon Unordered Tasks: From Boolean to Coupled Reward Machines},
year = {2026},
howpublished = {\url{https://pith.science/paper/JYNJBFPI}},
note = {Machine review of arXiv:2510.27329}
}
read the original abstract
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.
Figures
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
Andreas, J.; Klein, D.; and Levine, S. 2017. Modular Multitask Reinforcement Learning with Policy Sketches. In International conference on machine learning, 166--175. PMLR
2017
-
[4]
Balakrishnan, A.; and Deshmukh, J. V. 2019. Structured Reward Shaping using Signal Temporal Logic Specifications. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 3481--3486. IEEE
2019
-
[5]
T.; Klassen, T
Camacho, A.; Icarte, R. T.; Klassen, T. Q.; Valenzano, R. A.; and McIlraith, S. A. 2019. LTL and Beyond: Formal Languages for Reward Function Specification in Reinforcement Learning. In IJCAI, volume 19, 6065--6073
2019
-
[6]
C.; Di Nunzio, L.; Fazzolari, R.; Giardino, D.; Re, M.; and Span \`o , S
Canese, L.; Cardarilli, G. C.; Di Nunzio, L.; Fazzolari, R.; Giardino, D.; Re, M.; and Span \`o , S. 2021. Multi-agent Reinforcement Learning: A Review of Challenges and Applications. Applied Sciences, 11(11): 4948
2021
-
[7]
Cui, W.; and Yu, W. 2023. Reinforcement Learning with Non-cumulative Objective. IEEE Transactions on Machine Learning in Communications and Networking, 1: 124--137
2023
-
[8]
Drexler, D.; Seipp, J.; and Geffner, H. 2023. Learning Hierarchical Policies by Iteratively Reducing the Width of Sketch Rules. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 19, 208--218
2023
Show all 31 references
-
[9]
Eschmann, J. 2021. Reward Function Design in Reinforcement Learning. Reinforcement Learning Algorithms: Analysis and Applications, 25--33
2021
-
[10]
Hu, W.; Wang, H.; He, M.; and Wang, N. 2023. Uncertainty-aware Hierarchical Reinforcement Learning for Long-horizon Tasks. Applied Intelligence, 53: 28555--28569
2023
-
[11]
T.; Klassen, T
Icarte, R. T.; Klassen, T. Q.; Valenzano, R.; and McIlraith, S. A. 2022. Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning. Journal of Artificial Intelligence Research, 73: 173--208
2022
-
[12]
T.; and McIlraith, S
Illanes, L.; Yan, X.; Icarte, R. T.; and McIlraith, S. A. 2020. Symbolic plans as High-level Instructions for Reinforcement Learning. In Proceedings of the international conference on automated planning and scheduling, volume 30, 540--550
2020
-
[13]
Jothimurugan, K. 2023. Specification-Guided Reinforcement Learning. Ph.D. thesis, University of Pennsylvania
2023
-
[14]
Jothimurugan, K.; Alur, R.; and Bastani, O. 2019. A Composable Specification Language for Reinforcement Learning Tasks. Advances in Neural Information Processing Systems, 32
2019
-
[15]
Jothimurugan, K.; Bansal, S.; Bastani, O.; and Alur, R. 2021. Compositional Reinforcement Learning from Logical Specifications. Advances in Neural Information Processing Systems, 34: 10026--10039
2021
-
[16]
Karpathy, A. 2015. REINFORCEjs: WaterWorld demo. https://cs.stanford.edu/people/karpathy/reinforcejs/waterworld.html. Accessed: 2025-10-31
2015
-
[17]
u ller, M.; Sch \
Krasowski, H.; Thumm, J.; M \"u ller, M.; Sch \"a fer, L.; Wang, X.; and Althoff, M. 2023. Provably Safe Reinforcement Learning: Conceptual Analysis, Survey, and Benchmarking. Transactions on Machine Learning Research
2023
-
[18]
Li, X.; Vasile, C.-I.; and Belta, C. 2017. Reinforcement Learning with Temporal Logic Rewards. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 3834--3839. IEEE
2017
-
[19]
P.; Hunt, J
Lillicrap, T. P.; Hunt, J. J.; Pritzel, A.; Heess, N.; Erez, T.; Tassa, Y.; Silver, D.; and Wierstra, D. 2015. Continuous Control with Deep Reinforcement Learning. arXiv preprint arXiv:1509.02971
2015 arXiv
-
[20]
A.; van Seijen, H.; and Eaton, E
Mendez, J. A.; van Seijen, H.; and Eaton, E. 2022. Modular Lifelong Reinforcement Learning via Neural Composition. arXiv preprint arXiv:2207.00429
2022 arXiv
-
[21]
A.; Veness, J.; Bellemare, M
Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M.; Fidjeland, A. K.; Ostrovski, G.; et al. 2015. Human-level Control through Deep Reinforcement Learning. nature, 518(7540): 529--533
2015
-
[22]
Mohan, A.; Zhang, A.; and Lindauer, M. 2024. Structure in Deep Reinforcement Learning: A Survey and Open Problems. Journal of Artificial Intelligence Research, 79: 1167--1236
2024
-
[23]
Y.; Harada, D.; and Russell, S
Ng, A. Y.; Harada, D.; and Russell, S. 1999. Policy Invariance under Reward Transformations: Theory and Application to Reward Shaping. In Icml, volume 99, 278--287. Citeseer
1999
-
[24]
Raffin, A.; Hill, A.; Gleave, A.; Kanervisto, A.; Ernestus, M.; and Dormann, N. 2021. Stable-baselines3: Reliable Reinforcement Learning Implementations. Journal of machine learning research, 22(268): 1--8
2021
-
[25]
N.; Wright, R.; Velasquez, A.; and Sinapov, J
Shukla, Y.; Burman, T.; Kulkarni, A. N.; Wright, R.; Velasquez, A.; and Sinapov, J. 2024. Logical Specifications-guided Dynamic Task Sampling for Reinforcement Learning Agents. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 34, 532--540
2024
-
[26]
Srivastava, S.; Zilberstein, S.; Immerman, N.; and Geffner, H. 2011. Qualitative Numeric Planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 25, 1010--1016
2011
-
[27]
B.; Talbert, D
Stone, G. B.; Talbert, D. A.; and Eberle, W. 2022. A Survey of Scalable Reinforcement Learning. Int. J. Intell. Comput. Res, 13: 1118--1124
2022
-
[28]
S.; and Barto, A
Sutton, R. S.; and Barto, A. G. 2018. Reinforcement Learning: An Introduction. MIT press
2018
-
[29]
Unniyankal, H.; Belardinelli, F.; Ferrando, A.; and Malvone, V. 2023. RMLGym: a Formal Reward Machine Framework for Reinforcement Learning. In WOA 2023: 24th Workshop From Objects to Agents
2023
-
[30]
Van Hasselt, H.; Guez, A.; and Silver, D. 2016. Deep Reinforcement Learning with Double Q-learning. In Proceedings of the AAAI conference on artificial intelligence, volume 30
2016
-
[31]
J.; and Dayan, P
Watkins, C. J.; and Dayan, P. 1992. Q-learning. Machine learning, 8: 279--292
1992
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.