REVIEW 4 major objections 5 minor 1 cited by
Adaptive Reward Design for Reinforcement Learning
T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper claims that adaptively updated task-progression rewards make an RL agent's optimal policy both maximize expected return and attain the best possible task progression for a co-safe LTL specification, within finitely many updates.
desk verdict Adaptive distance-based reward shaping is a genuinely useful practical contribution, but the formal correctness proof has a real gap that should be fixed before publication. 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 product MDP $M^\otimes = M \otimes A_\varphi$ formed from the environment MDP and the deterministic finite automaton for the co-safe LTL task. On its states the paper defines a distance-to-acceptance function $d_\varphi(q)$, zero on accepting states, and a task-progression function $\rho_\varphi(q,q') = \max\{0, d_\varphi(q)-d_\varphi(q')\}$ for non-cyclic DFA transitions. The adaptive update in Eq. 5 adds a constant $\theta$ to $d_\varphi(q)$ for every DFA state in partitions indexed at least the current policy's task progression $b_k$, which makes the transition that finally lowers the partition index carry extra reward $\theta$ in the next round; the adaptive hybrid variant pairs this with a self-loop penalty whose weight decays as $\eta_k = \eta_{k-1}/\theta$. The proof mechanism is the threshold condition $\theta > \sigma/(p\gamma^{H-1})$, which forces the better-progression policy's expected return to surpass the current optimum and yields strict descent in $b(\pi^*_k)$ until $b^*$ is reached.
What would settle it
Run the adaptive update on a two-stage product MDP in which the policy that reaches the accepting state has lower expected return than a policy that stops one stage earlier, and set the update size $\theta$ below $\sigma/(p\gamma^{H-1})$ with the initial distance-to-acceptance rewards; if the updated reward's optimal policy still stops early, the finite-update improvement claimed by Theorem 1 has been falsified in that instance.
Extended reading notes
Core claim
The central claim is Theorem 1: given an episodic MDP and a DFA for a co-safe LTL formula, there exists an update round $k$ such that an optimal policy of the product MDP $M^\otimes = M \otimes A_\varphi$ under the adaptive progression reward $R^\otimes_{ap,k}$ or the adaptive hybrid reward $R^\otimes_{ah,k}$ maximizes expected return while attaining the best possible task progression $b^*$. The adaptive step adds a positive offset $\theta$ to the distance-to-acceptance values of every DFA state whose partition index is at least the current policy's progression level, so the specific transition that carries the agent into a strictly better partition gains an extra $\theta$ of reward in the next round. Repeating this makes the best-progression policy overtake the current optimum once $\theta > \sigma/(p\gamma^{H-1})$, where $\sigma$ is the return gap and $p$ the probability of the breakthrough path; since progression values are bounded, only finitely many updates are needed.
Load-bearing premise
The proof treats the current learned policy as truly optimal for the current reward and assumes its task-progression level $b_k$ is known exactly, and it requires the update size $\theta$ to exceed a threshold $\sigma/(p\gamma^{H-1})$ that depends on the unknown MDP; when the RL policy is approximate and evaluation is short, these conditions need not hold and the guarantee can stop applying.
Editorial extensions
If this is right
- For any co-safe LTL task, an agent that maximizes expected return under the adaptively updated reward should also reach the best reachable task stage within finitely many updates, rather than only maximizing a shaped proxy.
- Because the reward is Markovian on the product MDP, it can wrap around standard deep RL agents without changing the learning rule; the paper demonstrates this with value-based, actor-critic, and policy-gradient algorithms across discrete and continuous environments.
- In environments where some sub-goals are impossible, the adaptive reward still distinguishes useful sub-task progress from failure, so the agent learns meaningful partial behavior where sparse or potential-based baselines fail.
- The update interval $N$ and scale $\theta$ control a practical trade-off: the ablation suggests feasible tasks prefer longer intervals and larger $\theta$, while infeasible tasks benefit from smaller $\theta$ and more frequent updates.
Reading between the lines
- A natural extension is to apply the same update rule to any finite-state task monitor with a well-founded distance-to-acceptance, such as LTLf or general reward machines, since only the automaton's state partition and reachability are used.
- In practice one could estimate $b_k$ from rollouts instead of assuming an exact optimal policy; the update would then be approximate, and the finite-update guarantee would become probabilistic or conditional on estimation accuracy.
- The reported outlier in the noisy office world offers a direct stress test: if the adaptive reward's optimal policy there does not attain $b^*$, the gap is either in the approximate RL step or in the reward design itself, and the theorem's conditions identify which assumption to inspect.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an adaptive reward-shaping framework for reinforcement learning with co-safe LTL specifications. It defines rewards based on a DFA distance-to-acceptance progression function and periodically updates the distance values by adding a scaling factor theta to states whose partition index is at least the current task progression. Two reward families are introduced, adaptive progression and adaptive hybrid, and Theorem 1 claims that after finitely many updates an optimal policy of the shaped product MDP maximizes expected return while also achieving the best possible task progression. The empirical section compares the method with reward-machine baselines in office, taxi, water, and HalfCheetah domains under deterministic, noisy, and infeasible variants, reporting generally improved success rates and normalized returns.
Significance. If the formal guarantee were correct, this would be a useful contribution: it directly addresses the sparse-reward problem for LTL-specified tasks, is compatible with several deep RL algorithms, is evaluated across diverse domains, and ships code. The experimental study also includes an infeasible-task setting that is relevant for real deployments. However, the central correctness claim is not established by the current proof, and the theorem does not match the implemented algorithm. The contribution is therefore currently best viewed as an empirical reward-shaping heuristic with an unproven convergence certificate; the formal part needs substantial repair.
major comments (4)
- [Appendix A, proof of Theorem 1] The key inequality in the proof is not established. The proof asserts that for the final transition into B_{b*} one has R^⊗_{ap,k+1} = R^⊗_{ap,k} + θ. By Eq. (5), only states in B_i with i ≥ b_k receive the increment θ. If b* < b_k, the source of the transition into B_{b*} can have partition index i with b* < i < b_k (e.g., B_1 when b*=0 and b_k=2), in which case neither the source nor the destination is updated and the reward is unchanged. Even if the source is updated, Eq. (7) takes the maximum of ρ^0 and ρ^k, so the reward gain is θ only when ρ^k + θ exceeds ρ^0; otherwise the gain is smaller or zero. Consequently, the claimed lower bound V^π_{ap,k+1} ≥ V^π_{ap,k} + pγ^{H-1}θ is not guaranteed, and the threshold θ > σ/(pγ^{H-1}) is insufficient.
- [Section 4.2, Theorem 1 statement] The theorem statement omits the 'sufficiently large θ' condition that the proof requires. The proof in Appendix A introduces the condition θ > σ/(pγ^{H-1}), where σ, p, and γ depend on the unknown MDP and on the policies under consideration. This condition is load-bearing, and without it the theorem as stated is not supported. The condition must appear in the theorem statement or the claim must be weakened accordingly.
- [Section 4.2 vs. Appendix A] There is a mismatch between the idealized assumptions of the proof and the algorithm actually evaluated. Eq. (5) uses b_k, the task progression of the exact optimal policy of the current reward, and Appendix A assumes that π*_k is the exact optimal policy and that b_k is known. The algorithm in Section 4.2 instead runs N episodes of approximate RL and triggers an update when the average success rate falls below a threshold λ, without measuring b_k exactly. If the learned policy is suboptimal or the success-rate proxy misestimates the task progression, Eq. (5) can update rewards for the wrong stages, and Theorem 1 provides no guarantee for the implemented procedure.
- [Appendix A, proof for R^⊗_{ah,k}] The proof for the adaptive hybrid reward function does not go through. Lemma 1 only shows that lim_{k→∞} R^⊗_{ah,k} = R^⊗_{ap,k}, while Theorem 1 claims existence of a finite k for which the optimal policy of R^⊗_{ah,k} achieves b*. Convergence in the limit does not imply equality at any finite index, so the 'without loss of generality' reduction to the adaptive progression case is invalid without an additional argument bounding the finite-k discrepancy and its effect on the optimal policy.
minor comments (5)
- [Eq. (1)] The formula for h(q,q') uses an undefined symbol 'n'; it should be clarified (likely 2^{|AP|} or a similar normalizing constant).
- [Example 8] The text says 'θ1 = 100' where the intended expression appears to be 'θ = 100'.
- [Section 4.2] The statement 'requiring that θ > 1' is much weaker than the threshold θ > σ/(pγ^{H-1}) used in the proof; the relationship between these two conditions should be stated explicitly.
- [Section 5.1] In the HalfCheetah description, 'reaching the farthest location' and 'each of the five locations along the way' would benefit from a precise definition of the locations and the episode horizon, since the distance-based reward may otherwise be ambiguous.
- [Figures 5 and 6] The ablation plots would be easier to read if the legend identified which curves correspond to which θ and N values; several curves appear to overlap substantially.
Circularity Check
No significant circularity: the adaptive update is a designed feedback loop, and the empirical evaluation is self-contained against external baselines.
full rationale
The paper's derivation chain is self-contained. Theorem 1 is a mathematical guarantee about the reward-update process, not an empirical prediction fitted to data. The reward functions in Equations 7 and 8 are built from the distance-to-acceptance function d_phi, and the task-progression metric b(pi) in Section 3 is defined from the same DFA partition; this overlap is by design, because the reward is intended to incentivize progression. It is not a circular reduction: Examples 4 and 5 show that maximizing the static progression or hybrid reward does not by itself yield the best progression, and the adaptive rule in Equation 5 feeds the current progression b_k back into the distance values precisely to close that gap. The proof of Theorem 1 argues by contradiction and bounded descent over partition indices, which is a legitimate convergence argument rather than an equivalence of inputs and outputs. There are no load-bearing self-citations: the only imported notion, the distance-to-acceptance function of Lacerda et al. (2019), is an external, parameter-free definition. The experimental section compares against external baselines (QRM, CRM, HRM, naive) on standard benchmark environments, so the empirical claims are not forced by the construction. A caveat, noted for correctness rather than circularity, is that the proof in Appendix A asserts the reward increment R_ap,k+1 = R_ap,k + theta for the transition into B_{b*} without verifying that the source state has index at least b_k, and the theorem statement omits the 'sufficiently large theta' condition used in the proof. These are soundness gaps in the formal guarantee, not circular dependencies.
Assumptions & free parameters
free parameters (4)
- θ (reward scaling factor) =
2000, 5000, 10000 in ablation
- N (update interval) =
Not fixed; varies per environment
- λ (success-rate threshold) =
Not specified numerically
- η_0 (hybrid weight) =
0.1 in examples; 10^-3 or 10^-4 recommended
assumptions (4)
- domain assumption The distance-to-acceptance function d_φ (Eq. 1) from Lacerda et al. 2019 is a valid measure of task progression.
- domain assumption The agent observes the DFA state q_{t+1} = δ(q_t, L(s_{t+1})) at every step, so the labeling function L is known.
- ad hoc to paper After each N-episode round the learning process has identified the exact optimal policy of the current reward, and its task progression b_k is known exactly.
- ad hoc to paper The update size θ exceeds σ/(p·γ^(H-1)) for every round, with σ the return gap and p the probability of the completing path.
Cite this review
Pith. "Pith review of Adaptive Reward Design for Reinforcement Learning." pith.science (2026). https://pith.science/paper/ZQUQXRKQ
@misc{pith2026241210917,
author = {Pith},
title = {Pith review of: Adaptive Reward Design for Reinforcement Learning},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZQUQXRKQ}},
note = {Machine review of arXiv:2412.10917}
}
read the original abstract
There is a surge of interest in using formal languages such as Linear Temporal Logic (LTL) to precisely and succinctly specify complex tasks and derive reward functions for Reinforcement Learning (RL). However, existing methods often assign sparse rewards (e.g., giving a reward of 1 only if a task is completed and 0 otherwise). By providing feedback solely upon task completion, these methods fail to encourage successful subtask completion. This is particularly problematic in environments with inherent uncertainty, where task completion may be unreliable despite progress on intermediate goals. To address this limitation, we propose a suite of reward functions that incentivize an RL agent to complete a task specified by an LTL formula as much as possible, and develop an adaptive reward shaping approach that dynamically updates reward functions during the learning process. Experimental results on a range of benchmark RL environments demonstrate that the proposed approach generally outperforms baselines, achieving earlier convergence to a better policy with higher expected return and task completion rate.
Figures
Figures from the paper (5 more)
Forward citations
Cited by 1 Pith paper
-
A Unified Framework for Dynamic Reward Shaping in Reinforcement Learning
A unified framework and review of dynamic reward shaping, with a new taxonomy over twelve method families and a gap analysis of optimality guarantees.
Reference graph
Works this paper leans on
-
[1]
Control synthesis from linear temporal logic specifications using model-free reinforcement learning
Alper Kamil Bozkurt, Yu Wang, Michael M Zavlanos, and Miroslav Pajic. Control synthesis from linear temporal logic specifications using model-free reinforcement learning. In IEEE International Conference on Robotics and Automation, pages 10349--10355. IEEE, 2020
work page 2020
-
[2]
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606.01540, 2016
arXiv 2016
-
[3]
Mingyu Cai, Erfan Aasi, Calin Belta, and Cristian-Ioan Vasile. Overcoming exploration: Deep reinforcement learning for continuous control in cluttered environments from temporal logic specifications. IEEE Robotics and Automation Letters, 8 0 (4): 0 2158--2165, 2023 a
work page 2023
-
[4]
Learning minimally-violating continuous control for infeasible linear temporal logic specifications
Mingyu Cai, Makai Mann, Zachary Serlin, Kevin Leahy, and Cristian-Ioan Vasile. Learning minimally-violating continuous control for infeasible linear temporal logic specifications. In American Control Conference, pages 1446--1452. IEEE, 2023 b
work page 2023
-
[5]
Ltl and beyond: Formal languages for reward function specification in reinforcement learning
Alberto Camacho, Rodrigo Toro Icarte, Toryn Q Klassen, Richard Anthony Valenzano, and Sheila A McIlraith. Ltl and beyond: Formal languages for reward function specification in reinforcement learning. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, volume 19, pages 6065--6073, 2019
work page 2019
-
[6]
Foundations for restraining bolts: Reinforcement learning with ltlf/ldlf restraining specifications
Giuseppe De Giacomo, Luca Iocchi, Marco Favorito, and Fabio Patrizi. Foundations for restraining bolts: Reinforcement learning with ltlf/ldlf restraining specifications. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 29, pages 128--136, 2019
work page 2019
-
[7]
From language to goals: Inverse reinforcement learning for vision-based instruction following
Justin Fu, Anoop Korattikara, Sergey Levine, and Sergio Guadarrama. From language to goals: Inverse reinforcement learning for vision-based instruction following. In International Conference on Learning Representations, 2018
work page 2018
-
[8]
Mohammadhosein Hasanbeig, Yiannis Kantaros, Alessandro Abate, Daniel Kroening, George J Pappas, and Insup Lee. Reinforcement learning for temporal logic control synthesis with probabilistic satisfaction guarantees. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5338--5343. IEEE, 2019
work page 2019
Show all 26 references
-
[9]
Deep reinforcement learning with temporal logics
Mohammadhosein Hasanbeig, Daniel Kroening, and Alessandro Abate. Deep reinforcement learning with temporal logics. In International Confernece on Formal Modeling and Analysis of Timed Systems, pages 1--22. Springer, 2020
2020
-
[10]
Reward machines: Exploiting reward function structure in reinforcement learning
Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A McIlraith. Reward machines: Exploiting reward function structure in reinforcement learning. Journal of Artificial Intelligence Research, 73: 0 173--208, 2022
2022
-
[11]
Temporal-logic-based reward shaping for continuing reinforcement learning tasks
Yuqian Jiang, Suda Bharadwaj, Bo Wu, Rishi Shah, Ufuk Topcu, and Peter Stone. Temporal-logic-based reward shaping for continuing reinforcement learning tasks. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 7995--8003, 2021
2021
-
[12]
A composable specification language for reinforcement learning tasks
Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A composable specification language for reinforcement learning tasks. Advances in Neural Information Processing Systems, 32, 2019
2019
-
[13]
Compositional reinforcement learning from logical specifications
Kishor Jothimurugan, Suguman Bansal, Osbert Bastani, and Rajeev Alur. Compositional reinforcement learning from logical specifications. Advances in Neural Information Processing Systems, 34: 0 10026--10039, 2021
2021
-
[14]
Model checking of safety properties
Orna Kupferman and Moshe Y Vardi. Model checking of safety properties. Formal Methods in System Design, 19: 0 291--314, 2001
2001
-
[15]
Probabilistic planning with formal performance guarantees for mobile service robots
Bruno Lacerda, Fatma Faruq, David Parker, and Nick Hawes. Probabilistic planning with formal performance guarantees for mobile service robots. The International Journal of Robotics Research, 38 0 (9): 0 1098--1123, 2019
2019
-
[16]
Reinforcement learning with temporal logic rewards
Xiao Li, Cristian-Ioan Vasile, and Calin Belta. Reinforcement learning with temporal logic rewards. In IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3834--3839. IEEE, 2017
2017
-
[17]
Continuous control with deep reinforcement learning
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In International Conference on Learning Representations, 2016
2016
-
[18]
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518 0 (7540): 0 529--533, 2015
2015
-
[19]
Asynchronous methods for deep reinforcement learning
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning, pages 1928--1937. PMLR, 2016
1928
-
[20]
Algorithms for inverse reinforcement learning
Andrew Y Ng and Stuart J Russell. Algorithms for inverse reinforcement learning. In International Conference on Machine Learning, pages 663--670, 2000
2000
-
[21]
Policy invariance under reward transformations: Theory and application to reward shaping
Andrew Y Ng, Daishi Harada, and Stuart J Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In International Conference on Machine Learning, pages 278--287, 1999
1999
-
[22]
The temporal semantics of concurrent programs
Amir Pnueli. The temporal semantics of concurrent programs. Theoretical Computer Science, 13 0 (1): 0 45--60, 1981
1981
-
[23]
Stable-baselines3: Reliable reinforcement learning implementations
Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22: 0 1--8, 2021
2021
-
[24]
Proximal policy optimization algorithms
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017
2017 arXiv
-
[25]
Deep reinforcement learning with double q-learning
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q-learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2016
2016
-
[26]
A survey of preference-based reinforcement learning methods
Christian Wirth, Riad Akrour, Gerhard Neumann, Johannes F \"u rnkranz, et al. A survey of preference-based reinforcement learning methods. Journal of Machine Learning Research, 18 0 (136): 0 1--46, 2017
2017
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.