HDCS: Hierarchy Discovery and Critic Shaping for Reinforcement Learning with Automaton Specification
Authors: Duo XU
Faramarz Fekri
Venue: Accepted by TMLR ()

Abstract: Training reinforcement learning (RL) agents by scalar reward signals is often infeasible when an environment has sparse and non-Markovian rewards. Deterministic finite-state automaton (DFA) provides a streamlined method for specifying tasks in reinforcement learning (RL) that surpass the limitations of traditional discounted return formulations. However, existing RL algorithms designed to address DFA tasks face unresolved challenges, hindering their practical application. One key issue is that subgoals in the DFA may exhibit hidden hierarchical structures, with some macro-subgoals comprising multiple micro-subgoals in certain orders. Without understanding this hierarchy, RL algorithms may struggle to efficiently solve tasks involving such macro-subgoals. Additionally, the sparse reward problem remains inadequately addressed. Previous approaches, such as potential-based reward shaping, often encounter inefficiencies or result in suboptimal solutions.
To address these challenges, we propose a novel RL framework designed to uncover the hierarchical structure of subgoals and accelerating the solving of DFA tasks without changing the original optimal policies, short as HDCS. The framework operates in two phases: first, a hierarchical RL method is used to identify the prerequisites of subgoals and build the hierarchy; second, given any task specification (DFA), the subgoal hierarchy is incorporated into task DFA to make a product DFA, and then a simple and novel critic shaping approach is proposed to accelerate the satisfaction of product DFA, which does not change optimal policies of the original problem. The effectiveness of HDCS is demonstrated through experiments conducted across various domains. Especially, compared with representative baselines, the critic shaping can have 2X or 3X acceleration on task solving.

Published in Transactions on Machine Learning Research (08/2025)
HDCS: Hierarchy Discovery and Critic Shaping for Reinforce- ment Learning with Automaton Specification
Duo Xu
dr3301 @gotech edu
School of Electrical and Computer Engineering Georyia Institute of Technology
Faramarz Fekri
Jamumarr.fdrriiecce.goeck. edu
School of Electricol and Computer Engineering Georgia Institute of Technology
Reviewed on 20ConsoleX
OpenReview:
https: oppenreveee...... net/ peet/foumm? id= Bidee
Abstract
Training reinforcement learning (RL) agents by scalar reward signals is often infeasible when an environment has sparse and non-Markovian rewards. Deterministic finite-stale automaton (DFA) provides a streamlined method for specifying tasks in reinforcement learning (RL) that surpass the limitations of traditional discounted return formulations. However, existing RL algorithms designed to address DFA tasks face unresolved challenges, hindering their practical application. One key issue is that subgoals in the DFA may exhibit hidden hierarchical structures, with some macro-subgoals comprising multiple micro-subgoals in certain orders. Without understanding this hierarchy, RL algorithms may struggle to efficiently solve tasks involving such macro-subgoals. Additionally, the sparse reward problem remains inadequately addressed. Previous approaches, such as potential-base reward shaping, often encounter inefficiencies or result in suboptimal solutions. To address these challenges, we propose a novel RL framework designed uncover the hierarchical structure of subgoals and accelerating the solving of DFA tasks without changing the original optimal policies, short HDCS. The framework operates in two phases: first, hierarchical RL method is used to identify the prerequisites of subgoals and build the hierarchy; second, given any task specification (DFA), the subgoal hierarchy is incorporated into task DFA to make a product DFA for the agent to satisfy, and then a simple and novel critic shaping approach is proposed to accelerate the satisfaction of the product DFA without changing optimal policies of the original problem. In addition, the convergence of the critic shaping method is theoretically proved. The effectiveness of HDCS is demonstrated through experiments conducted across various domains. Especially, compared with representative baselines, the critic shaping can have 2X or 3X acceleration on task solving.
1 Introduction
In the classical reinforcement lcarning (RL) framework, the primary objective is to develop a strategy that maximizes a reward function within an unfamiliar environment. Typically, practitioners design a scalar reward function guide the agent toward desirable behaviors during the learning process. However, scalar rewards often fail to effectively capture the complexity of real-world task specifications (Toromanoff al. While some rescarchers have posited the hypothesis that 'the reward function is enough" (Sutton
2019h.
2018
Silver el. al. 2021). certain tasks remain inherently unrepresentable by scalar rewards alone AAel el al.
2021
This work supported by ARO grant under Award #991 1NF-333---3111111 1-0146 and gift by Open Philanthropy.

---

Published in Transactions on Machine Learning Research (08/2025)
scroll
necromancer
fountain
exorcism
stone
tool workshop
stone
stone
water
pickaxe
Figure 1: Example of subgoal hierarchy. Every icon represents subgoal or final goal. The final goal is get exorcism. The prerequisite of that goal is to first get scroll, second visit necromancer, and then build fountain. Here, building fountain has its own prerequisites under ordering constraint, including making stone pickaxe, collecting stone and going to place with water. In addition, the prerequisites of making a stone pickaxe consist of first collecting a stone and then visiting a tool workshop. In addition to the fact that stone pickaxe, fountain and exorcism are in level 1 (blue), 2 (green) and 3 (red), all the other subgoals are in level 0 and do not have any prerequisites.
To address these limitations, recent rescarch has incrcasingly turned to deterministic finitc-state automaton (DFA), which subsumes many previous attempls to define specifications that canmot be reduced to scalar Markovian rewards (Abel et al., 2021). These works include Linear Temporal Logic (LTL) (Camacho et al.
2019: Fu & Topcu, 2014 Hasanbeig et al. 2018
Sadigh et al.
2014
Wang et al.,
2020 Vaczipoor et al. 2021
Alur et al.) 2022 De Giacomo et al.) 2020 Voloshin et al.) 2023
SPECTRL (Jothimurugan et al. 2019
2021 and reward machine (Icarte et al.
2021). DFA consists of temporally extended subgoals and can express desired characteristics of future behavior a system, allowing for precise and fiexible task specification (Fersman et al., 2007]. Tasks specified using DFA are provalent
2022
Corazza et al.
2022
Neider et al.
in various real-world applications, including robotics, soflware verification (Bauer al. 2011), and system control (Tabuada & Pappas 2003). However, previous works of RL for solving DFA tasks still have two issues remaining unsolved, which could prevent RL algorithms from being deployed into real-world applications.
First, the hierarchical structures of subgoals have been largely overlooked in previous research. In many real-world applications, completing macro subgoals often comprise achieving micro subgoals under ordering constraints. This can form hierarchies of subgoals, where achieving lower-level (micro) subgoals acts as a prerequisite for achieving higher-level (macro) goals. For instance, in the NetHack game (Küttler al. 2020); which can be regarded as variant of Minecraft game (Duncan 2011), subgoals exhibit layered structure with ordered dependencies. For the example shown in Figure 1 subgoals can be categorized into 4 levels and the prerequisites of every subgoal are under temporal ordering constraints. Before completing the desired goal, the agent has to achieve every subgoal in the prerequisite following the right order. This subgoal hierarchy describing ordering dependencies is typically unknown to the agent at the outsct. Without uncovering and leveraging this hierarchy, RL algorithms may struggle to achieve satisfactory learning efficiency.
Second, the issue of sparse rewards in the context of DFA tasks remains insufficiently addressed. Potential- based reward shaping (PBRS) has been employed in previous studies to densify the reward signal (Ng et al. Grzeš 2017 Jiang et al. 2021 Devidze et al. 2022 Icarte et al. 2022). wherein auxiliary rewards derived from potential function are added onto the original reward function. However, these reward shaping methods still exhibit certain drawbacks. First, the presence of temporal dependencies in DFA tasks can render the computation of the potential function both difficult and cumbersome, particularly when subgoal prerequisites are incorporated. Second, because DFA tasks typically encompass multiple subgoals over extended temporal stages, incorporating subgoal-speciffc auxiliary rewards risks diverting the agent's 's attention to other redundant subgoals, thus destabilizing the agent's learning. Moreover, given that the policy learning is guided by the critic function, the auxiliary rewards must first be assimilated by the critic to subsequently facilitate policy learning-4 process that can be inefficient, especially in tasks with lengthy time horizons. Some studies have attempted to decompose DFA tasks into subtasks and address them via hierarchical reinforcement. learning (HRT.) (Araki et al. 2021 Camacho et. al., 2019 Tcarte et al. 2022 However, in many practical settings, independently solving each subtask may yield suboptimal solutions.
1999
In this work, we address the aforementioned challenges by introducing a novel framework, referred as HDCS, that discovers hierarchical subgoal structures and expedites DFA task resolution without modifying the
2

---

Published in Transactions on Machine Learning Research (08/2025)
- A b
b
1
g
b
F
9 A m
b
(a) Environment
(b) Task DEA
(c) Prerequisite DFA
Figure 2: (a): the map of environment. (b): the DFA of LTT. task formula [ A Og A ((b))) A ( (c): The DFAs representing the prerequisites of visiting green ("g") zone and blue ("b") zone. States with double circles are accepting states. State 'F' indicates the sink state which can make the task fail. "[" denotes the empty output of the labeling function. In (c), the left DFA shows that the prerequisite of "g" is to first visit 'o', and the right DFA shows that the preroquisite of "b" is to fist visit "p" and then 'c'. In this work, the task formula is known to the agent while the prerequisites of subgoals are unknown initially.
original optimal policy. The framework proceods in two stages. First, we proposc a hicrarchical reinforcement learning (HRL) approach to learn subgoal prerequisttes and construct a corresponding subgoal hierarchy. These learned prerequisites of product automaton. Second, unlike existing reward shaping methods, propose shaping the critic function directly to enhance learning efficiency and mitigate the sparse reward problem.
then integrated into the task specification (DFA) through the construction
More specifically, we design an auxiliary reward function based on task progress, measured by a reduction in the distance to an accepting state within the task automaton. Whenever the agent progresses to a new stage-iee. reduces the minimal distance to an accepting state the agent has ever achieved by one hop-thi the corresponding auxiliary reward integrated into the critic function via a maximun operator. We term this mechanism critic shaping, since it fixes and stabilizes critic values of the target states in all stages. Because this approach bypasses the reward function, it substantially accelerates policy learning, thus alleviating the sparse reward issue in temporal logic tasks. The convergence of the critic shaping method is theoretically proved in Appendix D
In experiments, we comprehensively evaluate the HDCS framework in terms of subgoal hierarchy discovery and acceleration in solving DFA tasks. The experiments are conducted in 2D-Minerraft, AssemblyZone and Button domains, covering both discrete and continuous action spaces. DFA tasks without and with subgoal hierarchy are both evaluated. The results show that HDCS can learn subgoal hierarchy accurately and expedite the efficiency of solving the DFA task for 2 or 3 times, compared to the state-of-the-art baselines.
2
Problem Setting
2.1
Definitions
First, present some basic definitions. An atomic proposition is variable that takes Boolean truth value. The alphabet of symbols is defined as a subset of all possible combinations over a finite set of atomic propositions (denoted as P), i.e., 2P, In every working environment, we assume a set of subgoals G which is a subset of the alphabet, i.e., G C 2". The subgoals in G have hierarchical structures which are unknown to the agent initially.
Detorministic Finitc-state Automata (DFA). In this work, we consider solving tasks specified by DFAs. Specifically, a DFA is defined as tuple B - (B, T B" ,,,,,)),, where B is the set of automaton states, the alphabet Σ c 2n denotes the alphabet of propositions, driving deterministic transitions in the automaton, the function T : B x Σ + B denotes the deterministic transitions of automaton states, 8 is the set of accepting states, and ag is the initial state. A path & = (bu, b,....) .) is a sequence of automaton states in B reached through sequential transitions governed by T In addition, we assume that DFAs for task specification are only composed by subgoals in G, i.e., Σ = G.
Remark. We focus on DFAs rather than LTL for two main reasons. First, with finite traces, LTL is strictly less expressive than DFAs an example being that LTL cannot capture tasks such as "the light switch is
3

---

Published in Transactions on Machine Learning Research (08/2025)
toggled an odd number of times." Second, both DFAs and LTL tasks form countably infinite sets, so any distribution over L,TL, inherently lavors certain subclasses. By contrast, the syntactic structure of DFAs allows these subclasses to be easily distinguished.
We show an example of DFA task in Figure 2 A robot is navigating in the environment with multiple colored zones, as shown in Figure [[a] where subgoals in 9 = (r, g, b, o. P: C, y) correspond to whether the agent steps into the red, green, blue, orange, purple, or cyan zones. As shown in Figure 2(b) the task DFA specification in this example asks the agent to oscillate among the red, yellow, and green zones with fixed temporal order while always avoiding the yellow zone.
Definition 3.1 (Satisfaction) A path & = (bu. b,,...) satisfies a DFA B if an accepting state of B is visited infinitely often by 5.
Labeled MDP. In this work, the environment where the agent is working is formulated as a labeled Markov Decision Process (MDP) M = (S. A. T.M A(so), y, r, L-M), with the state space S, the action space A, the state transition TM : 8 A - (SS) mapping from input state-action pair into distribution of next states, distribution of initial states (sso), discount factor y E (0, 1), reward function S x A + [Rmin Rmax], and a labeling function L-M; S - Σ. The labeling function produces atomic propositions in P which are true in the input state. If no propositions are true, it produces an empty ]. Note that the transition function T'M is unknown to the agent. In this work, we assume that the agent is working in a goal-oriented MDP, where the labeling function produces propositions which represent subgoals, ie., Σ ==6 G. We assumne that the set G is known to the agent, but the hierarchy of subgoals in 9 is unknown initially. The environments used in this work are determinislic and the output of TM is a distribution whose the support is on single point only.
2.2 Subgoal Prerequisites and Hierarchy
Hierarchy Formulation. In this work, assumee that subgoals follow layered structure, where the prerequisites of visiting subgoal only depend on lower-level subgoals, under some ordering constraints, Specifically, subgoals in level 0, denoted as Go. can be achieved without any prerequisites. In level k, subgoals (denoted as Gk) have prerequisites comprising subgoals from levels O through k - 1. We further assume that subgoals in the level 0 are directly visible in the environment, so that the set Go is known to the agent initially. Note that subgoal prerequisites cannot contain higher-level subgoals. Otherwise, circular dependencies can be created, making the involved subgoals unreachable. For example, if the prerequisite of subgoal 'a" depends "b," and prerequisite of 'b' includes 'a,' neither 'a' or 'b' can be achieved.
This kind of subgoal hierarchy exists in many real-world problems. For instance, Figure 1 illustrates a simplified example from the NetHack game, which is a variant of MineCraft. The goal in the highest level (level 3) is to get "exorcism', and its preroquisites are to first get a scroll, second visit the necromancer, then build a fountain. The subgoal of building a fountain is a level-2 subgoal whose prerequisiles are to first make a stone pickaxe, then get stone and then go to a place with water. In addition, the subgoal of "stone pickaxe" is in level I which requires the agent first get a stone and visit the tool workshop. So, every subgoal in level 1, 2 and 3 has prerequisites under temporal ordering constraints. Except 'exorcism', "fountain" and 'stone pickaxe", all the other subgoals are in level O.
However, except level-0 subgoals, this hierarchical structure of subgoals is often unknown prior to interacting with the environment. To address this, before tackling the DFA task, we propose to use HRL to first learn subgoal prerequisites to build the subgoal hierarchy. Subsequently, we need to incorporate the learned subgoal prerequisites into the DFA task for the agent to follow. Hence, we represent subgoal prerequisites in the form of DFAs, referred to prerequisile DFAs, which are incorporated into the task specification by making a product of task DFA and prerequisite DFAs.
Specifically, a prerequisite DFA is a tuple C- (C. (C.G,T cu),, where C is the finite set of automaton states, G is the input alphabet. driving the stale transition (same as the set of subgoals), T C x g - C is the deterministic transition function, C* C C is the set of accepting states, and co is the initial state. Some example prerequisite DFAs are shown in Figure 2(c) The left DFA illustrates that visiting any green zone requires visiting an orange zone first, while the right DFA shows that, before visiting a blue zone, the sequence of visiting a purple zone followed by cyan zone must be adhered to.
4

---

Published in Transactions on Machine Learning Research (08/2025)
2.3 Problem Formulation
In this work, we aim to uncover the hierarchical structures of subgoals and subsequently learn policy efficiently that generates trajectories meeting the constraints of the task DFA specification B and subgoal prerequisites represented by prerequisite DFAs C. These two sets of constraints can be integrated with environmental MDP by formulating a product MDP defined as below.
Definition 3.2 (Product MDP) A product MDP synchronizes the environmental MDP with the task DFA and the prerequisite DFAs. Denote the task DFA as B and the prerequisite DEAs as C1 C2,..., Cx. Let M represent the product MDP with a state space defined as & = B C₁ x Cx. Policies over this product MDP are given by II: S A ( 1]). The probabilistic transition function for this product MDP is then defined as:
(s'sss), a (+))
ck, Cx.
(1)
0,
otherwise
where the condition (x) refer to equations 6' = (
...,kk CK T (cx lex. L(s'),, reprosenting state transitions over task DFA and preroquisite DFAs. Denote the trajectory of state-action pairs in product MDP as = ((00, ao, .1, cx.,,......,))....))
Definition 3.3 (Trajectory acceptance) trajectory T is defined to accepted by task DFA B and prerequisite DFAs C, i.c., T Fc B, if there exist some (b, (o.,,....c.)) E B Ci x... x Cx that are visited by infinitely often.
Definition 3.4 (Constraint satisfaction) We say policy 1l satisfies constraints of task DFA B and prerequisite DFAs C with the probability P( Fc B] := B, B.r.gglLrpaa) where 1 indicates whether the trajectory accepted by В and C not, and M is the distribution of trajectories induced by the policy in product MDP M In addition, producing trajectories accepted by both B and C, iee, II" == { E [| Fc BJ = max PP(r' Fc BJ}. The ultimate goal of this work is to learn policy in II accurately and efficiently.
define II as the set of policies which maximize the probability of
3 Methodology
This work introduces the HDCS framework to address the issues of unknown subgoal structure and sparse reward, including two phases. The diagram is shown in Figure 3 In the first phase (introduced in Section 3.1), hierarchical reinforcement learning (HRL) is employed to uncover a hierarchical structure of subgoals. The first phase is a process of pre-training which makes the agent understand the hidden structure of subgoals in the environment.
In the second phase (introduced in Section 3.2 agent adheres the subgoal prerequisites in the discovered hi- crarchy, whenever the task specification (DFA) is given, these learned prerequisites are first integrated into the task DFA via prerequisite DFAs. Then, to address the sparse reward issue in satisfying the LTL specification, the critic shaping method is proposed. This approach effectively mitigates the sparse reward challenge a simple way, particularly in tasks where the hier- archy of subgoal prerequisites significantly complicates the task formula.
ensure the
Task DFA
Subgoal
Hierarchy Discovery
Product DFA
Subgoal Prerequisites
RL with Critic Shaping
Phase
Phase
3.1 Phase 1: Subgoal Hierarchy Discovery
In this soction, we will first present the HRI-based algorithm for hierarchy discovery, and then discuss how incorporate learned subgoal prerequisites into the task specification.
Figure 3: Diagram of the HDCS frame-
work
5

---

Published in Transactions on Machine Learning Research (08/2025)
3.1.1 Discovering Subgoal Hierarchy
We propose to use hierarchical reinforcement learning (HRL.) DDetteriich et al., 1998 Nachum et al. 2018 to learn prerequisites of subgoals, which are pre-conditions of visiting subgoals, and use them to build the subgoal hierarchy.
Model Architecture. The high-level part is responsible for exploring and learning prerequisites of subgoals. It is realized by an RNN-based RL agent Th which selects next subgoal from lower levels to explore or achieve a designated subgoal in the current level. The high-level action space is the set of lower-level subgoals. The low-level part is a goal-conditioned RL agent Tg which is trained to achieve any level-0 subgoal (i.e. Go) selected by the high-lovel part. The low-lcvel action space is the primitive action space of the environment.
Discovery Method. The HRL method discovers subgoal prerequisites level- by-eel.. The discovery starts from level 0, and proceeds to higher levels incrementally. In level 0, every subgoal g E Go does not have any prerequisites and the low-level policy xg(-11) is trained to achieve g by using goal-conditioned RL algorithm (Nachum et al. 2018). In level 1 2 1, the operations are divided into exploration phase and learning phase. The exploration phase aims to explore and discover subgoals of the current level, while the learning phase is to learn prerequisites of discovered subgoals. The discovery continues until the prerequisites of all the subgoals in G of the environment are learned and the subgoal hierarchy is well established. The exploration and learning phases in level & are introduced with details as below. Both ma and v are trained with PPO algorithm (Schulman et al. 2017]. The detailed algorithm is shown in Appendix C
Exploration Phase. In each level k the HRL model first works in the exploration phase to explore subgoals of level k. The high-level part of the HRL model uses a stochastic policy to select next lower-level subgoal to achieve, and the low-level agent uses its policy to achieve the selected subgoal. In the beginning of exploration phase, the high-level policy T is re-initialized while the low-level part T keeps the same. In each episode, whenever a new subgoal not in lower levels is achieved, the episode ends and this new subgoal is recorded as a newly discovered subgoal in the level k. Then na is trainod with the reward signal of discovering a new subgoal. The agent will start a new episode until no new subgoals have been discovered for number of episodes. Then, these new subgoals form the subgoal set of level k, ie., Gg, and the algorithm will proceed to the learning phase.
Remark. Note that in level k, whenever any subgoal already in Ge is accidentally visited in exploration phase, this episode ends and this trajectory data is discarded. This is to avoid visiting any subgoals in levels higher than k.
Learning Phase. In this phase, the agent will learn the prerequisites for subgoals in GA one- one For learning each g E GR, the high-level part x² is first re-initialized. Then, being conditioned on g; the RNN-based high-level policy (-19) is used to collect trajectories and trained with the reward signal of achieving 9, where Tg is fixed and used to achieve the subgoal produced by Tb (-19). After (-19) is well trained, the prerequisites of achieving g can be obtained as the output of 7 (-1g), which are sequences of subgoals in levels lower than k.
Whenever the prerequisites of subgoals in G& are all well learned, the algorithm will proceed to level k: + 1. If the prerequisites of every subgoal in g are discovered, the algorithm terminates and the subgoal hierarchy is built.
Remark. The correctness of learned subgoal sequences for prerequisite can be verified easily via interacting with the environment. After the prerequisite of target subgoal is learned, the obtained subgoal sequences can be applied into the environment to check whether the target subgoal can be achieved or not. If not, the agent needs to learn the sequences for prerequisite again. However, the empirical experience is that it is very unlikely that the learned subgoal sequences are not correct, since in the learning phase, the high-level policy is trained with the reward of achieving target subgoal only.
3.2 Phase 2: Policy Learning for Automaton Satisfaction
In the second stage of HDCS framework, when the task specification (DFA) is given, the agent first incorporates the learned subgoal prerequisites into the task DFA, producing a product DFA Ax, then the agent learns
6

---

Published in Transactions on Machine Learning Research (08/2025)
d
d
g
g
(a)
g
F
4
g
g
d
1
0
3
D
A -d
b
Figure 4: Example of building the prerequisite DFA for subgoal a, b, c, d are lower-level subgoals. (a): prerequisite sequences of g learned by the HRL method. (b): intermediate DFA. (c): prerequisite DFA. State "F" denotes sink state. The condition (*) over state 1 is g -a A -b.
optimal policy to satisly Ax; i.e., to achieve an accepting state in Ax as often as possible. A thorough discussion on the motivation of critic shaping is presented in Appendix F
3.2.1 Incorporating Subgoal Prerequisites
In the subgoal hierarchy, the prerequisites of subgoals are composed by sequences of lower-level subgoals, which are learned by the HRL method in Section 3.1.1 These prerequisites are incorporated into the task specification via prerequisite DFAs, which consists of two steps.
First, for each larget subgoal we construct an intermediate DFA Ć (De la Higuera 2010 Watanabe el al. 2021) by using its prerequisite sequences of lower-level subgoals. This C represents all the possible paths for achieving g. In C, there is one initial state and one accepting state denoting the achievement of g. An example is shown in Figure g For the target subgoal g, its learned prerequisite sequences - + denoting two allernative paths to achieve g. Then, these sequences are converted into an
and b + intermediate DFA.
Second, we convert the intermediate DEA C into the prerequisite DEA C. Specifically, this process consists of three steps:
First, one sink (rejecting) state is added into C avoid selecting the target subgoal y before its prerequisites are satisfied, which is the state 'F" in Figure 4(c..
Then, in order to consider the situation that the agent does not need to satisfy g in task completion, except the sink state, all the other states in C become accepting states, where the prerequisite of g are partially satisfied.
Finally, one more accepting state is added to represent the situation that y is achieved with its prerequisites satisfied, which is the state 5 in Figure [ as an example. This state is also connected back to the initial state with an edge label of emply (I), meaning that after is achieved, the agent wants to achieve again, its prerequisites have to be satisfied again from the scratch.
Product DFA. After prerequisite DFAs of all the subgoals are obtained, we propose to build a product DFA to incorporate the subgoal prerequisite into the task specification. By multiplying the task DEA (B) and all the prerequisite DFAs (CI,..., Ck) together, the product DEA is tuple Ax AS, S s where the product automaton state space is Sx := B x C₁ X x CK. the input alphabet driving the state transition over Ax is Ax = Σ X G x .... x G, the state transition is 7 Sx x Ax + Sx, the set of accepting states is S = B x G x x Ck. and s is the initial state over Ax. An accepting state in Ax is a vector of accepting states in task DFA and all the prerequisite DFAs, making the RL agent learn to complete the task and obey subgoal prerequisites at the same time. An example of product automaton is shown in A Appendix
7

---

Published in Transactions on Machine Learning Research (08/2025)
5
b
d
C
C
0
1
6
Figure 5: Example of level, stage and round. The number labeled over every state is its index. Yellow state: level O. Purple state: level 1. Green state: level Red line: stage 2. Blue line: stage 1. Dotted line: round 1. Dashed line: round 2. Self-loops are omiteed.
3.2.2 Auxiliary Rewards
Due to the complexity of product DFA Ax as constraint, the RT. agent may suffer from the issue of sparse reward. To overcome this issue, we propose a critic shaping method to accelerate the policy learning under the constraint of an automaton. Different from previous reward shaping methods which add auxiliary rewards onto the reward function, the proposed method directly shapes the critie function by using an max operator, encouraging the agent to reach an accepting state in Ax more efficiently. We will first introduce the auxiliary rewards, details of critic shaping operations and finally present its motivation and intuition.
We design auxiliary rewards as intermediate rewards assigned to agent as it makes progress towards the satisfaction of product automaton Ax. Then, we first define concepts of level, stage and round which are used to formulate the auxiliary rewards Ra for critic shaping.
Level. First, we divide the states of Ax into different levels according to their shortest distances to the nearest accepting state in Ax. The level k only contains states with distance k. An example of state levels is shown in Figure where the states in the same level have the same color.
Stage. Then, the stage is defined as the segment of agent's trajectory between the first visit to level I and first visit to level I. L- 1. The slage essentially divides the trajectory according lo the shortes! distance to an accepting state in Ax the agent has ever had in this episode. As shown in Figure 5 before visiting state 4, the stage and 2 are shown in blue and red lines, respectively, Although state 2 is in level 2, the visit to state is already in stage 1, since the state 1 in level 1 was previously visited and the agent already entered stage 1 at that time.
Round. In addition, the satisfaction of Ax means infinitely many visits to an accepting state in Ax- Hence, we define round as the segment of a trajectory from (i - 1)-th to i-th visit to an accepting state or the end of episode (i.e., time limit is exceeded).
Now we introduce auxiliary rewards RA defined terms of stage and round indices. In any round i, whenever the agent enters stage k, there will be auxiliary reward RA k) 0 to shape the critic function, encouraging the agent making progress towards visiting accepting state. Whenever the agent visits any accepting state in Ax for the i-th time (i.e., the round i ends), it will receive an auxiliary reward (A 0) > 0 and then start the next round ++1 1. These auxiliary rewards must satisfy an condition as below, for any i, k integers such that > 0 and 1: > 0,
RA(i,K) <
RA(i,k- ( 1), RA(L.0) < < RA
(2)
where y is the discount factor of environmental MDP. Note that H is the max length of each stage, rather than the whole episode, which allows the agent to visit accepting states in fa infinitely often. The intuition behind the condition equation 2 will be introduced in Appendix
3.2.3 Critic Shaping
In order model the multi-stage nature of satisfying DFA constraint, we extend the state representation tuple of four elements, including (environmental state), 8x (state in DFA constraint), i (round index),
8

---

Published in Transactions on Machine Learning Research (08/2025)
and & (stage index), which are inputs to policy (Tτ) and the critic function (V The auxiliary rewards R,A are used only at the boundaries of stages and rounds. Inspired by the max-reward RI. (Veviurko et al. 2024);
the target for updating critic function V is written as below based on Bellman-like equations: whenever the agent steps into stage k from stage k - 1 in round i
V ( 8 i, k) = B - Ra 1) i i,k - 1)/s = s1+1]
(3)
where 1 is the next state of the transition driven by symbol ((s++1) over Ax, and a v is max(a, b). If the agent steps into a new round i + 1, the larget for updating Va is computed as below
VVVa (st, st 0) = Eey [R ( i k,)ss=== = s++1]
(4)
where K is the stage index of next state săt over Ax. Otherwise, whenever săt1 and oe are in the same stage and round over Ax, , it is
(5, 5f s7, i, = Ee [7V k,)lss = s441]
In implementation, the policy To and critic V are trained with auxiliary rewards by using PPO (Schulman et al. 2017) or DDPG algorithm (Lilicrap et al. 2015).. The motivation of critic shaping is introduced in
Appendix F and the convergence proof is presented in Appendix D
3.2.4 Adaptive Design of Auxiliary Reward
Since the agent has little knowledge about the environment initially, any pre-designed auxiliary rewards R& may not precisely reflect the difficulty of activating desired DFA transitions, leading to sub-optimal policies. In order to address this issue, we propose an adaptive design for RA which first sets RA to some initial values in the beginning, and then updates every value of RA adaptively according to the difficulty of achieving the corresponding stage, which is determined by the empirical performance of achieving that stage in previous episodes.
We first set every ki, to its initial value, which is selected empirically for each environment and satisfies the condition equation 2 For example, in Minecraft, we choose RA = [5, 10, 20, 40....J, -I, while in the AssemblyZone environment, we set initial values of RA to be 10, 100, 1000....
Denote Be, as a binary label indicating whether the stage i in round is achieved in the last episode or not. If yes, 3L, 0. If not, Be 1. Then, the end of 1-th episode, Ra k) is updated
(1, - '
(1, k) + KISLN
(6)
(ne (e
where K2 is a hhper--paatt parameter controlling the update rate of RA, and H(,s) is the operator clipping a value into the interval (a, b). In experiments, we select K2 1. Besides, we set Rain k) == - R2, (i, "i, 1) and Rmax(i (i, k) := 7 1t'- (i, k - 1), which is to make sure that the condition equation still holds after I-th update of RA- This dynamic and adaptive update can make RA have higher values in difficult stage, giving the agent more encouragement to achieve this kind of stages.
4 Experiments
The experiments will try to examine two questions as below:
1. Can the proposed framework accurately learn the prerequisites and build the hierarchy of subgoals?
2. Can the critic shaping method accclerate the solving of LTL task with and without subgoal hicrarchy?
In this section, we will use experimental results and analysis to answer these two questions in 4.1 and 4.2 respectively. The environments are introduced in Appendix [ The tasks used in experiments are described in Appendix H The evaluation of critic shaping in Button domain is in Section 4.3 Ablation study for the whole framework is presented in Appendix K
9

---

Published in Transactions on Machine Learning Research (08/2025)
Propused WHRL
1.0
Proposed
0.8
0.8
HAC
VHRL
1,00
Proposed HACC a MEGA
1.00
Proposed BAAC MEGA
0.6
MEGA
0.8
MEGA
0.75
04
04
0.90
0.50
02
0.2
0.25
0.00
2
5x1e5
10x1e8
iron Ioo fountain
sword
exordsm
Hil zombie
0.00
P1
P2
P4
(a) Minecraft
(b) ZssemblyZone
(c) Minecraft.
(d) A AssemblyZone
Figure 6: Comparison of exploration. The x-axis is the number of samples drawn from the environment. The y-axis are success rates of reaching target subgoals (a, b) and intermediate subgoals (c, d).
4.1 Hierarchy Discovery Evaluation
The baselines used in the evaluation of subgoal hierarchy discovery are presented in Appendix [.1
In environments with hard-to-explore hicrarchical structures, we first conduct experiments to compare the exploration capability of HDCS and state-of-the-art baselines. Then, we compare the accuracy of subgoal hicrarchies Icarned by HDCS and basclines. In addition, more detailed results are presented in Appendix J
Exploration. In 2D-Minecraft and AssemblyZone, evaluated the learning efficiency of the HDCS framework against baseline methods for attaining the highest-level subgoals (specifically, "exorcism" and "kill zombic" in Minecraft, and p4 and p5 in AssemblyZone), whose success rates are compared in Figure G (a,b). In addition, some selected intermediate subgoals which are used as selected exploration milestones. The success rates of achieving intermediate subgoals are shown in Figure t (c,d), where the performances are evaluated after training with 3e5 and 6e6 environmental steps. As illustrated in Figure D the proposod
framework exhibits accelerated learning and surpasses all baselines in both efficiency and success rate. This improvement is primarily due to its level-by-level acquísition of subgoal prerequisites, in accordance with the underlying hidden hierarchy. Although the VHRL approach eventually achieves stable attainment of the target subgoals, it expends an excessive number of samples on intermediate subgoals because it directly targets the highest-level subgoals, thereby neglecting the hierarchical structure. Moreover, both HAC and MEGA implement goal-conditioned high-level policies to directly reach various subgoals without considering the subgoal hierarchy, which ultimately leads to suboptimal performance in achieving the target subgoals with satisfactory sample efficiency.
Hierarchical Structure Discovery. In experiments, the accuracy of subgoal hicrarchy discovery is evaluated by computing the Hamming distance between the learned subgoal prerequisites and the true ones. Figure 7 illustrates a comparative analysis between the proposed framework and baseline methods, revealing that our approach significantly outperforms both HAC and MEGA. This superior performance is attributed to the framework's mothod of soquentially discovering subgoals, thereby progressively constructing a subgoal hierarchy that more accurately reflects the inherent structure of the environment. In contrast, conventional HRL methods like HAC and MEGA rely on exploration-drite subgoal discovery, which overlooks the hicrarchical organization of subgoals.
Note that the targets of experiments in Figure 5 and are different. In Figure f the experiments are designed to evaluate only the exploration capability of the agent trained by the proposed method. In Figure 7 we compare the proposed and baseline mothods for the accuracy of learning prerequisites of all the subgoals. Therefore, the experiments in Figure 7 need more samples than those in Figure
4.2 Task Completion Evaluation
The baselines used in task completion evaluation are presented in Appendix I.2
In addition to the subgoal hierarchy discovery, this work proposes the critic shaping method to accelerate the resolution of the given DFA task, which the stage 2 of the proposed framework. In this scetion, we compare the critic shaping method against some state-of the-art baselines on the sample efficiency of solving DFA tasks. The first set of experiments uses regular tasks without subgoal hierarchy, while the second part of
10

---

Published in Transactions on Machine Learning Research (08/2025)
Proposes MEGA
Proposed e HAC MEGA
60
40
30
30
20
10
0.2M
0.4M
0.5M
D.8M
1M
2M
4M
6M
BM
10M
(a) Minocraft
(b) AssemblyZone
Figure: 7: Comparison of accuracy in subgoal hierarchy discovery. The y-axis is the Hamming distance between learned and real subgoal prerequisites.
1.0
1.0
Proposed
1,0
Proposed
088
9.6
0.8
FBRS
0,8
Naive-RB
havve
0.6
0.8
0.6
AdeptveiRS
08
AdsptiveRS
0.4
Proposed
0.4
Proposed
0.4
0.4
02
Naire-RS
Na
022
022
Adagtie-RS
Adsptie-RS
0.0
Scte5
Gx1c6
10xte6
6
10xtes
(a) Minocraft Task
(b) Minecraft Task 2
(c) Zose Task
(d) AasemblyZone Task 2
Figure 8: Performance comparison on tasks without subgoal hicrarchy. The y-axis is the success rate.
experiments evaluate tasks integrated with subgoal hierarchy, which the overall evaluation of the proposed framework. The details of evaluated tasks are presented in Appendix H The evaluation of critic shaping in more challenging domain is shown in Section 4.3 The ablation study specific to critic shaping is presented in Appendix K
We evaluate the performance using the metric of success rate of task completion, calculated by counting the frequency of successful episodes where the task is completed. We pause the learning process every 10K training steps in every domain, then evaluate the current policy in the test environment over 20 episodes. We ran independent trials for each method. In cach plot, the solid curve represents the mean performance whose standard deviation is shown by the shaded area.
The comparison on tasks without subgoal hierarchy is shown in Figure S where only subgoals in the level 0 are used to compose the tasks. The automata of evaluated tasks are presented in Appendix H Figure g presents the performance comparison on tasks with subgoal hierarchy, where subgoals from every level are used and the subgoal prerequisites learned in the stage of HDCS are incorporated into the task automata via prerequisite DFAs.
As shown in Figures Figure and Figure g the proposed framework significantly outperforms baselines, demonstrating the effectiveness of the critic shaping method. Every baseline assign intermediate rewards to the reward function, dependent on the agent's 's distance towards task completion on the automaton Ax- Compared with baselines, the critic shaping directly modifies the critic values via a max operator, bypassing
1.0
1.0
1.0
Proposed
1.0
Proposed
0.8
9.8
FBRS
PBRS
Adoptive RS
Adapive-R8 RS
Proposed PBRS
Proposed
PORS
02
Adoptive RS
Adsplive-R
00
00
10xte5
(a) Minecraft Task
(b) Minecraft Task
(c) AssemblyZone Task
(d) AssemblyZone Task 4
Figure Performance comparison on tasks with subgoal hierarchy. The y-axis the success rate.
11

---

Published in Transactions on Machine Learning Research (08/2025)
Proposed
Proposed
0.8
PBRS
PBRS
Acaptive RS
Adaptive RS
0.4
02
0.2
0.0
0.0
10x1e6
10xte6
(a) Screenshot
(b) Task
(c) Task
Figure 10: Performance comparison Button domain.
the process of the critic function that assimilates auxiliary rewards. Besides, the rewards in critic shaping set stable targets for updating the critic function, improving the efficiency of critic training and facilitating the reward propagation across the state space.
The advantage of the HDCS framework is magnified in Figure g This is because the DFA constraints there are product automata which incorporated prerequisite DFAs of subgoals, and have more complex structures. Since the agent needs to go through more stages to satisfy more complex DFA constraints, the critic shaping can have larger margin over baselincs based on conventional reward shaping. We can see that the PBRS method performs almost worst. This is because the auxiliary rewards on loo many automaton stales can distract the agent from reaching the real target. Both Naive-RS and Adaptive perform much worse than the proposed framework, and the performance gap is larger in AssemblyZone environment which has much longer horizon. This shows that the effect of shaping the critic is significant and increase in proportion with the task horizon.
4.3 Evaluation of Critic Shaping in Button Domain
In addition, we evaluate the critic shaping accelerating the resolution of L.TL tasks in the Button domain which is more challenging than Zone. This environment is from Safety-gymnasium (Ji et al. 2023), where agent must press a number of small buttons in a larger space while avoiding cube-shaped 'gremlins' that move in a fixed circular path. A screenshot of this domain is shown in Figure 10(a) The agent simulated car (Ji et al. 2023). The task specification (DFA) instructs the agent to press some specific buttons in the right orders, while avoiding making contact with gremlins. The symbols in this domain include indices of buttons (i.e., '1", 22", *3" and "4') and 'g' for gremlins. The task DFAs are shown in Appendix H
We use two basclincs, i.c. PBRS and Adaptive-RS, introduced in Appendix 1.2 In the proposed method, the critic shaping method is adopted and RA are chosen as [10, 100, 1000, The horizon for every stage is 1000 and the discount 7 0.998, so that RA satisfies the condition in equation 2 The proposed method and basclincs adopt PPO algorithm, where the clipping c should be small, c.g., 0.1.
As shown Figure 10 critic shaping still shows advantages over PBRS and Adaptive-RS the high- dimensional domain. Compared with comparisons in Minecraft and AssemblyZone domains, the advantage of the proposed method (critic shaping) enlarges here. This is because the agent here is more difficult to control and the gremlin is moving around. In this case, the stabilization of critic targets brought by the critic shaping can accelerate the agent's 's learning more significantly.
5 Conclusion
In this work, attempt to solve two important issues of completing temporal logic tasks, i.e. unknown subgoal hierarchy and sparse rewards, which are largely ignored or inadequately solved in previous works. First, we propose an HRL-based framework to learn subgoal prerequisites and build a subgoal hierarchy, significantly facilitating the agent's learning process. Second, we propose a simple and novel critic shaping method which can densify the rewards and efficiently accelerate the resolving of the given task. Each component of the proposed framework is evaluated in various domains, verifying its advantages over baselines. In the future, will consider using large language model (LLM) to extract the subgoal hierarchy from text. descriptions of collected trajectories and incorporate it into task DFA.
12

---

Published in Transactions on Machine Learning Research (08/2025)
References
David Abel, Will Dabney, Anna Harutyunyan, Mark K Ho, Michael Littman, Doina Precup, and Satinder Singh. On the expressivity of markov reward. Advances in Neural Information Processing Systems, 34: 7799- 7812, 2021.
Rajeev Alur, Suguman Bansal, Osbert Bastani, and Kishor Jothimurugan. A framework for transforming specifications in reinforcement learning, In Principles of Systems Design: Essays Dedicated to Thomas A. Henzinger on the Occasion of His 60th Birthday, pp. 604-624. Springer, 2022.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAT Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. Advances in newral information processing systems, 30, 2017.
Dana Angluin. Learning regular sets from queries and countercxamples. Information and computation, 75(2):
87 106, 1987.
Brandon Araki, Xiao Li, Kiran Vodrahalli, Jonathan DeCastro, Micah Fry, and Daniela Rus. The logical options framework. In International Conference Machine Leorning, pp. 307-317. PMLR, 2021.
Dzmitry Bahdanau, Felix Hill, Jan Leike, Edward Hughes, Arian Hosseini, Pushmeet Kohli, and Edward Grefenstette. Learning to understand goal specifications by modelling reward. In International Conference Learning Representations, 2018.
Andreas Bauer, Martin Leucker, and Christian Schallhart. Runtime verification for Itl and tltl. ACM Transactions on Software Engineering and Methodology (TOSEM), 20(4):1-64, 2011.
Mingyu Cai, Shaoping Xiao, Zhijun Li, and Zhen Kan. Optimal probabilistic motion planning with potential infeasible constraints. IEEE Transactions on Automatic Control, 68(1):301 316, 2021.
Alberto Camacho, Rodrigo Toro Iearte, Toryn Q Klassen, Richard Anthony Valenzano, and Sheila A Mcllraith. Ltl and beyond: Formal languages for reward function specification in reinforcement learning, In IJCAI, volume 19, pp. 6063-6073, 2019.
Jan Corazza, Ivan Gavran, and Daniel Neider. Reinforcement learning with stochastic reward machines. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 14296 2022.
Giuseppe De Giacomo, Marco Favorito, Luca locchi, Fabio Patrizi, and Alessandro Ronca. Temporal logic monitoring rewards via transducers. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 17, pp. 860-870, 2020.
Colin De la Higuera. Grammatical inference: learning automata and grammars. Cambridge University Press, 2010.
Rati Devidze, Parameswaran Kamalaruban, and Adish Singla. Exploration-guided reward shaping for reinforcement learning under sparse rewards. Advances in Newral Information Processing Systems, 35: 5829 -849, 2022.
Thomas G Dietterich et al. The maxq method for hicrarchical reinforcement learning. In ICML, volume 98, pp. 118- 118-126,110 1998.
Xuchu Ding, Stephen L Smith, Calin Belta, and Daniela Rus. Optimal control markov decision processes with linear temporal logic constraints. IEFE Transactions on Aulomatic Control, 59(5):1244-1255 2014.
Sean C Duncan. Minecraft, beyond construction and survival. Carnegie Mellon University, 2011.
Elena Fersman, Pavel Kreal, Paul Pettersson, and Wang Yi. Task automata: Schedulability, decidability and undecidability. Information and Compulation, 205(8):1149-11 1172, 2007.
Jie Fu and Ufuk Topeu. Probably approximately correct mdp learning and control with temporal logic constraints. Xrxie preprint 144. 2014.
13

---

Published in Transactions on Machine Learning Research (08/2025)
E Mark Gold. Language identification in the limit. Information and control, 10(5):447-474, 1967.
Sai Krishna Gottipati, Yashaswi Pathak, Rohan Nuttall, Raviteja Chunduru, Ahmed Touati, Sriram Ganapathi Subramanian, Matthew Taylor, Sarath Chandar, al. Maximum reward formulation in reinforcement learning. arXiv preprint arXi::2010003744, 2020.
Marek Grześ. Reward shaping in episodic reinforcement learning. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pp. 565-573, 2017.
William H Guss, Brandon Houghton, Nicholay Topin, Phillip Wang, Cayden Codel, Manuela Veloso, and Ruslan Salakhutdinov. Minerl: a large-scale datasct of minceraft demonstrations. In Proceedings of the 28th International Joinl Conference on Artificial Intelligence, pp. 2442 2448, 2019.
Mohammadhoscin Hasanbeig, Alessandro Abate, and Danicl Kroening. Logically reinforcement learning. Xiv preprint arXiv: 111::880.08000 801.08099, 2018.
Marijn JH Heule and Sicco Verwer. Exact dfa identification using sat solvers. In Grammatical Inference: Theorelical Results and Applicalions: 10th International Colloquium, ICGI 2010, Valencia, Spain, Seplember 13-16, 2010. Proceedings 10, pp. 66 79. Springer, 2010.
Xing Hu, Rui Zhang, Ke Tang, Jiaming Guo, Qi Yi, Ruishi Chen, Zidong Du, Ling Li, Qi Guo, Yunji Chen, et al. Causality-driven hierarchical structure discovery for reinforcement learning, Advances in Newral Information Processing Systems, 35:20064-20076, 2022.
Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A Mcllraith. Reward machines: Exploiting reward function structure in reinforcement learning. Journal of Artificial Intelligence Research, 73:173-2086 2022.
Jiaming Ji, Borong Zhang, Jiayi Zhou, Xuehai Pan, Weidong Huang, Ruiyang Su,, Yiran Geng, Yifan Zhong, Josef Dai, and Yaodong Yang. Safety gymnasium: A unified safe reinforcement learning benchmark. Advances in Neural Information Processing Systems, 36:18964 18993, 2023.
Yiding Jiang, Shixiang Shane Gu, Kevin Murphy, and Chelsea Finn. Language as an abstraction for hierarchical deep reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Yuqian Jiang, Suda Bharadwaj, Bo Wu, Rishi Shah, Ufuk Topcu, and Peter Stone. Temporal-logic-aase reward shaping for continuing reinforcement learning tasks. In Proceedings of the AAAI Conference on artificial Intelligence, volume 35, pp. 7995 7995-8003, 2021.
Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A composable specification language for reinforcement. learning tasks. Advances in Newral Information Processing Systems, 32, 2019.
Kishor Jothimurugan, Suguman Bansal, Osbert Bastani, and Rajeev Alur. Compositional reinforcement learning from logical specifications. Advances in Neural Information Processing Systems, 34:10026 -00099,
2021.
Heinrich Küttler, Nantas Nardelli, Alexander Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel. The nethack learning environment. Advances in Neural Information Processing Systems, 33:7671-7688 7687117684, 2020.
Niklas Lauffer, Beyazit Yalcinkaya, Marcell Vazquez- Chanlatte,,, Ameesh Shah, and Sanjit A Seshia. Learning deterministic finite automata decompositions from examples and demonstrations. In 2022 Formal Methods in Computer-Aided Design (FMCAD), pp. 1-6. IEEE, 2022.
Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierarchies with hindsight. In International Conference Learning Representations, 2019.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Hoess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint ar 2015.
14

---

Published in Transactions on Machine Learning Research (08/2025)
J Luketina, N Nardelli, G Farquhar, Foerster, J Andreas, E Grefenstette, S Whiteson, and T Rocktäschel. A survey of reinforcement learning informed by natural language. In Proceedings of the twenly-Fight International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence, 2019.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hicrarchical reinforcement learning. Advances in neural information processing systems, 31, 2018.
Daniel Neider, Jean-Raphael Gaglione, Ivan Gavran, Ufuk Topcu, Bo Wu, and Zhe Xu. Advice-guided reinforcement learning in a non-markovian environment. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 9073 90800 2021.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Ieml, volume 99, pp. 278-287, 287, 1999.
José Oncina, Pedro Garcia, et al. Inferring regular languages in polynomial update time. Pattern recognition and image analysis, 1(49-61):10-114,, 1992.
Rajesh Parekh and Vasant Honavar. Learning dfa from simple examples. Machine Learning, 44:9 35, 2001.
Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba. Maximum entropy gain exploration for long horizon multi-goal reinforcement learning. In International Conference on Machine Learning, pp- 7750 7761. PMLR, 2020.
Kian Hong Quah and Chai Quek. Maximum reward reinforcement learning: A non-cumulative reward critcrion. Expert Systems with Applications, 31(2):351339, 2006.
Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep reinforcement learning. arXiv preprint arxiv: 1ate:1910011100 7(1):2, 2019.
Dorsa Sadigh, Eric S Kim, Samuel Coogan, S Shankar Sastry, and Sanjit A Seshia. A learning based approach to control synthesis of markov decision processes for linear temporal logic specifications. In 53rd IEEE Conference on Decision and Control, pp. 1091-1096. IEEE, 2014.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International conference on machine learning, pp. 1312 1320. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. Xiv preprint arXio:1707.0634 2017.
Ameesh Shah, Cameron Voloshin, Chenxi Yang, Abhinav Verma, Swarat. Chaudhuri, and Sanjit Seshia. Deep policy optimization with temporal logic constraints. arXie preprint orXiv:244,.11578, 2024.
David Silver, Satinder Singh, Doina Precup, and Richard S Sutton. Reward is enough. Artificial Intelligence, 299:103535, 2021.
Sungryull Sohn, Junhyuk Oh, and Honglak Lee. Hierarchical reinforcement reiiforrmeer learning for zero-shot generalization with subtask dependencies. Advances in neural information processing systems, 31, 2018.
Sumedh Sontakke, Jesse Zhang, Séb Arnold, Karl Pertsch, Frdem Biyik, Dorsa Sadigh, Chelsea Finn, and Laurent Itti. Roboclip: One demonstration is enough to learn robot policies. Advances in Newral Information Processing Systems, 36:55681 55693, 2023.
Richard S Sutton. Reinforcement learning: An introduction. A Bradford Book, 2018.
Paulo Tabuada and George J Pappas. Model checking Itl over controllable linear systems is decidable, In International workshop hybrid systems: Computation and control, pp. 498-513. Springer, 2003.
Marin Toromanoff, Emilie Wirbel, and Fabicn Moutarde. Is deep reinforcement learning really superhuman on atari? In Deep Reinforcement Learning Workshop of 39th Conference on Neural Information Processing Systems (Neurips' 2019), 2019.
15

---

Published in Transactions on Machine Learning Research (08/2025)
Pashootan Vaczipoor, Andrew C Li, Rodrigo A Toro Icarte, and Sheila A Mcilraith. Lt12action: Generalizing Itl instructions for multi-task rl. In Internalional Conference on Machine Learning, pp. 10497-10508. PMLR, 2021.
Marcell Yazquez-Chanlatte, Karim Elmaaroufi, Stefan Witwicki, and Sanjit A Seshia. Imm: Learning automata from eramples using natural language oracles. arXiv preprint arXiv:2402.07051, 2024.
Marcell Jose Vazquez- Chanlltte. Specifications from Demonstrations: Learning, Teaching, and Control.
University of California, Berkeley, 2022.
Grigorii Veviurko, Wendelin Böhmer, and Mathijs de Weerdt. To the max: Reinventing reward in reinforcement learning. Xiv preprint 4rXi:22022.01361, 2024.
Cameron Voloshin, Abhinav Verma, and Yisong Yuc. Eventual discounting temporal logic counterfactual PMLR, 2023.
experience replay. In International Conference Machine Learning, pp.
Chuanzheng Wang, Yinan Li, Stephen Smith, and Jun Liu. Continuous motion planning with temporal logic specifications using deep neural networks. arXiv preprint arXiv:2004. 002600,04400000, 2020.
Kandai Watanabe, Nicholas Renninger, Sriram Sankaranarayanan, and Morteza Lahijanian. Probabilistic specification learning for planning with safety constraints. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 6558 6565. IEEE, 2021.
Wojeiech Wicczorck. Grammatical Inference. Springer, 2017.
16

---

Published in Transactions on Machine Learning Research (08/2025)
A
Source Code
The source codes in the following link:
B
Related Work
We invostigate temporal extension of goal-conditioned reinforcement lcarning (RL) (Schaul et al. 2015 in which objectives are encoded as automata. Although early work emphasized goals defined solely as prospective target states, subsequent research has broadened the scope to encompass objectives expressed in
natural language (Bahdanau et al. 2018 Jiang et al. 2019 Luketina et al. 2019 Sontakke et al. 2023 and temporal logic formulas (Vaczipoor et al., 2021). Conditional deterministic finite automata (cDFAs), while less expressive than free-form language, strike useful compromise: they retain much of language's ' user-friendly character yet preserve the precise, unambiguous semantics essential for the growing deployment of Al agents in safety-critical contexts. In addition, the problem of inferring DFAs has been extensively studied (Angluin
1987: Gold 1967 Heule & Verwer 2010 Lauffer et al., 2022 Oncina et al.,
1992 Parekh & Honavar 2001
Wieczorek 2017). and recent advances demonstrate that both DFAs and cDFAs can be learned directly from
natural-language descriptions and expert demonstrations, further narrowing the gap between language-based
and automata- based goal specifications (Yazquez-Chanlattee Chanlatte
2022 Vazquez-Chanlatte Chanlatte et al.) 2024).
On the LTL-constrained policy optimization side, several works have tackled the problem in varying settings
(Cai et al..
2021 Ding et al., 2014 Shah et al.
2024 Voloshin et al. 2023 Adjacent to these efforts, there is
surge of recent works which have explored LTL specifications and automalon-like models as objectives in
RL Camacho et al. 2019
Fu & Topcu. 2014 Hasanbeig et al. 2018 Sadigh et al. 2014 Wang et al. 2020
Vaczipoor et al.
2021: Alur et al.) 2002 De Giacomo et al. 2020; Voloshin et al.] 2023 Jothimurugan et al,
2019
2021 However, none of them lackled the issue of unknown subgoal hierarchy.
Several previous works have tried address the issue of sparse reward in solving the LTL task. Some of them applied potential-basod reward shaping (PBRS) (Ng et al. 1999) to derive auxiliary rewards for
intermediale progress towards lask completion (Grzes 2017: liang al. 2021 Devidze et al. 2022 learte
ct al.
2022). However, this method still does not resolve the sparse reward issue adequately. Another method
is to decomposing LTL task and solve it by hierarchical RL (HRL) approaches (Araki et al. 2021 Camacho
et al. issues.
2019 Icarte et al. 2022 However, these HRL-based methods may suffer from the sub-optimality
C Subgoal Hierarchy Discovery Algorithm
The algorithm for discovering subgoal hierarchy and prerequisites shown Algorithm
Remark. The low-level policy T/f (+lg) is pre-trained to achieve every subgoal g in level 0 (Go). In pre-training, conditioned every g E Go, Tg is trained by the PPO algorithm to reach g. Since every Go can be visited without prerequisites and the set Go is known to the agent initially, the agent could use mq to achieve every 9 directly. For any subgoal in higher levels (i.c., 9), the agent could leverage the subgoal hicrarchy to decompose it into a sequence of subgoals in level 0, and then apply Th to achieve these decomposed subgoals one-by-onee meeting the prerequisites.
Convergence Proof of Critic Shaping
In this section, we provide the convergence proof of the critic shaping method. We will first formulate the DFA satisfaction based on critic shaping as reward maximization in an extended MDP, and then prove the convergence of max-Ban Bellman operators used in this extended MDP, implying the convergence of critic shaping method.
17

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm Subgoal Hierarchy Discovery
Require: subgoal set G; goal-conditioned low-level policy Tg(-1)); empty subgoal hierarchy H: 1: 9 := 9 Gui l= 0; =
while G not empty do
I 1+1:
initialize high-level policy mp; # exploration phase slarls
G
6: while true do
7: explore until new subgoal is discovered;
8: if no more new subgoal has been discovered for many episodes then
break; 10: end if
11: store the new subgoal into 9G
12:
train high-level policy; end while
13:
14:
# exploitation phase starts
15:
for each E 9i do
16:
initialize high-level policy mh:
17:
train =/ to reach fi
18:
obtain prerequisites of g from the trained; T (+19) and store them into H. 19: remove g from 5;
20: end for
21:
end while
D.1 Extended MDP
In the formulation in Section 3.2.3 the state representation is extended tuple of four elements, including (environmental state), 8x (state of product DFA Ax), i (round index) and (stage index). To formalize this extension, we define the extended state space S == S Sx Z Z, where S is the environmental state space, Sx is the set of aulomaton states the product DFA Ax and & denoles the set of integers. Besides, we also define the level function [ Sx + Z mapping automaton state on Ax to its level. As defined in Scction 3.2.2 the level of a state mcans the minimal number of hops to an accepting state over Ax).
For any exlended state 8 = (s, 8x, kx, v) E S, the initial distribution of extended states defined as fo( == po(s)6(sx)0(C ((sx)))(())) where po is the initial state distribution of environmental MDP, 8(sx) ensures that the agent starts from the initial state 0 of Ax, and other terms ensure that the first stage index the level of automaton state 0 and the round index starts from 0.
Then, for any extended state & E S and for an action E A, the extended transition function i, is PDF over (s',8x, K,) E S, defined as
P(s Kls k, = P())s: T (sx. (1 ((
E Sx))) (7)
where P the transition function of the environmental MDP, T is the state transition function of Ax denotes min(a,)) b), and Sx the of accepting states of Ax. The first two terms in equation denote the state transitions in environmental MDP and Ax. The third term means that the stage index k is the minimal level the agent has reached in the current round. The last term denotes that the round index i is the number of accepting visits the agent has made in the current episode. Since we only consider deterministic environment. in this work, P becomes a delta function and hence the distribution produced by P concentrates on a single point.
In addition, the auxiliary reward function RA is defined in Section 3.2.2 and is used to train the policy S ((A) to visit accepting states of Ax (accepling visit) as often possible in one episode. Based
18

---

In order to show the convergence, we first define the max- Bellman evaluation operator and the max- Bellman Veviurko al. 2024). Based on a critic function Q S A Published in Transactions on Machine Learning Research (08/2025)
RA, we can define the reward function for extended state transition (5, a,) and action below
('), a(), = RA(K'dd),
if 1(55)))
if x E 8% otherwise
(8)
In the definition of R, the first line denotes the situation where new stage is achieved by 3' and the second line represents the case when an accepting state is visited in 8.. Combining all the discussions above, have the following definition.
Extended MDP. The extended MDP is an MDP M defined by the tuple (S,ARR, PR Po 7). Here A and y are action space and discount factor of the environmental MDP M.
D.2 Convergence Proof
As introduced in Section 3.2.3 in the proposed critic shaping method, auxiliary rewards RA are used directly shape the critic function via the max operator V. So, for any time step t and any extended state & (8t, 8x,1, he, it,, we can define the critic function Q as below,
max (R(s,, (R((t, 8111), S6+2 P(-1a+11; aet1) (max(A(())1) at11 8122), ....))
R Se+1 P(-)a)
ac+1 x (8(+1)
a+t2 (81+2)
E 8 a()
(10)
a++1 ~ x (8++1)
According to the condition oquation 2 of RA values and the definitions of the reward R and the Q function equation [ and equation g the objective of visiting accepting states in the DFA Ax as often possible in finite episode is equivalent to maximizing the Q value in this extended MDP. So, the optimal policy of satisfying the product DFA Ax can be obtained by training stationary policy to maximize the Q function defined in equation g Therefore, the convergence of policy optimization based on this Q function implics the convergence of the critic shaping method.
optimality operator (Quah & Quek 2006 and for any state-action pair (5,a) 8 A,
( (ft(( 8'), (lE (38,, P(-a,)))))))
(M)))(&,
(g [maxx a, 8'), 7 max (
(11)
a'EA
Specifically, M= and M (S A R) + (S AA R) are operators that take in a Q function and returns another modified Q function by assigning the Q value of the input state-action pair (s,a), to the maximum of the reward obtained at (s, a) and the discounted future expected Q value. In the following, we are going to show that these two Bellman operators converge to a fixed point, and this fixed point is the optimal policy which maximizes the Q values. The proofs are variants of convergence proofs in max-reward RI. (Quah &
Quek 2006 Gottipati et al. 2020
Theorem D.I. The operator M defined in equation 11 have the following properlies.
1. Monotonicity: Assume that have two Q functions Q1, for any state-action pair (8.a), Then
R such that Qi 2 Q2(5,a)
M' 2 M0Q²
(12)
Contraction: both operators are conntraccton in the supremum norm (ll-loo), iee, for any Q functions Q1. Q2 : S A R, we have
I| -M*22l <11111 Q211x
(13)
19

---

Published in Transactions on Machine Learning Research (08/2025)
Proof. We first prove the monotonicity and contraction for M Monotonicity. Assume Qi and Q2 are two Q functions such that Qi(8, 2 Q2(8, for any (8,4) E A. Then, we have
max Q1(3,a') 2 a'EAA
E
which yields
Q1 a') z max a2( a'EAA
max
a Vs V
a'EA
Based on the definition of operator M in equation
we have
2 2 ((11aa)
max (((,
d'EA
Then, it obvious that
M²Q2(8, 7 -R8 2 max Q2(
(14)
d'EA
The definition of M also implies that
M²QI(B,0) 2 Bg P(18,a) [R(S, a, 8)]
(15)
Since only consider deterministic enviromment in this work (stated in Section 2.1 based on equation 14
and equation 15 we have
(),i(S,a) ((1 max [2(3, a, 8'), max Q2(8", = M2Q2(8, -M
(16)
Contraction. Denote Ji(8, a, 8*) = 7 maxa'eA ( Based the fact that max(x; v) 0.5(% + x v)), Vx,y R, have
max fi) max (t f2)
0.5(ft + f1 + f1)- 0.5(ft 11 (2
0.5(f1 f2 -
S 0.5(f: f2 I8 fR--f-(R-- -f((fffa)
0.5(fi f2 + +I1 +111-f - fal)
S If1 - f2l
(17)
Then, we can have
-
1 maxx R. fi) max(R, f2)ll
| M fi fell
| ((-1,a)))
mmx Q1 a'E.A
max a'EAA
||Q Q21
which proves the y-contraction of M in equation 13 largest difference between the two Q-functions. Since in the range [0, 1), all the differences are guaranteed to converge to zero in the limit. Based on the Banach fixed point theorem, the operator M admits fixed point.
The left-hand side of this equation represents the
Theorem D.2. The operator R defined in equation 11 have the following properties.
1. Monotonicity: Assume that have two Q functions Q2, Q2 Sxx - R such that (3 2 Q2(5,a) for any stale-action pair (8.a). Then
M 2 M
(18)
20

---

Published in Transactions on Machine Learning Research (08/2025)
2. Contraction: both operators are "ycontraction in the supremum norm (ll-1lo), i.e,, for any functions Q1,Q2: x A + R, we have
|IM' - Q2 S <1lQ1 -MQ2ll
Q21lo
(19)
Proof. Now we prove the monotonicity and contraction for M Monotonicity. Assume Qi and Q2 are two Q functions such that Q1 2 Q2(8. for any (8,0) $ A. Then, we have
(('''''')) d')) P(jaa) Q2(('' V(S,a) M1. 7B g P(18a))) QQ1 (8',
Based on the definition of operator M TM in equation we have
MTQI($,a) 2 (
Then, it is obvious that
(,,i(B,a) 2 P
(20)
The definition of M also implies that
M²Q1($,a) 2 ( (
(21)
Since we only consider deterministic environment in this work (stated in Section 2.1 based on equation
20
and equation 21 we have
() Eg - max ( (105
M((2(8,
(22)
which shows the monotonicity of M" Contraction. Denote [i, a, 8') = 7Baa (-1))/21( Based on the fact that max(x, y) = 0.5(x +
+
J vl), Va,ye y R, have
max R. f1) max (2)
0.5(ft + /1 + R2 fil) 0.5(f + f2 1 12)-22)
= 0.5(f1 fa + 1R - f1l f
s 0.5(f1 - fe + j f1 -(R-f2))
0.5(f - -2 1S1 - f2l)
S I/i f2l
(23)
Then, we can have
- MMPQl-MQQ2lle
(1 [maxx( (ft, fi) max max f2)
ff felloo
|| [Ba Q1(8', a') (18)
< ||Q: - Q21loo
which proves the 7-contraction of M in equation largest difference between the two Q-functions. Since in the range [0, 1), all the differences are guaranteed to converge to zero in the limit. Based on the Banach fixed point theorem, the operator M admits fixed point.
19
The left-hand side of this equation represents the
According to equation 11 and equation 10 the fixed point of M is Q". Denote the fixed point of M operator as Q- In the following, we will show that Q" corresponds to the optimal action-value function which maximizes the reward ft obtained in one episode, ie., Q" max, Q
Thcorem D.3. Define the deterministic policy n" as n²" (*)) arg max,eA (*, VS S. Then, n' is the optimal policy and for any stationary policy and any state-action pair (8, a) $ A, we have Q" (8, (*( a) 2 ())
21

---

Published in Transactions on Machine Learning Research (08/2025)
b
[
[]
Task DFA
Prerequisite DFA
Example of task DFA B and prerequisite DFA C for building the product automatton AK. 'x' denotes the product of two DFAs. Self-loops are omitted.
Figure 11:
Proof. Based the definition of x² and Q", have Q"=0"=='QQ"" Q" Tt shows that Q" is the fixed point of M= which implics that Q" is the value function of n²"
For any Q function Q $ x A + R and any stationary policy n, we have M 2 MMQ. Based on the monotonicity of operators, we have
(M' (2 Z (M*PQ
Then, by using induction, can show that for any we have (M*)QQ 2 (M Based the contracting properties of M and M both (M*)"Q and (M")PQ converge to Q" and Q" when n - 00, respectively. Then, we show that Q' 2 Q" element-wisely.
According to theorems above, show that both the optimality M and evaluation M operators, defined based the max-Bellman operator used in the critic shaping, converge to their fixed points, and the fixed point of M is the optimal policy. Therefore, we show that policy optimization based on the critic shaping method can converge to the optimal policy which maximizes the number of visits to accepting states of Ax in a finite episode.
Levels
States in A
(4,0), (4. 1), (4, 2), (4,
(3,0), (3, 1), (3, 2), (3.3)
(2
3
(1,2), (2, 1)
4
(2, 0), (1, 1), (0,
(1,0), (0, 1), (1,3)
(0, 0), (0,3)
Table 1: Dividing states in product automaton A into levels.
E Example of Product Automaton and Levels
give another example for the levels in product automaton AX The prerequisite DFA states that the pre-condition of visiting subgoal "e" is visiting "c" first and then 'f' The state of product automaton (8), is a tuple of state sg in task DFA B and state se in prerequisite DFA C. Then, the states in product automaton are divided into different levels as shown in Table [
Additionally, shown in Figure 11
States in level are accepting states Ax States in level k are è hops away from any accepting state following the shortest path over A Note that the state (2, can never be reached from initial state (0, since the conditions of transiting from state to 3 coincide in both B and C, which is visiting 'e". States (0,3)
22

---

Published in Transactions on Machine Learning Research (08/2025)
and (1,3) are in level 6 and 5 respectively, since the agent goes to these states by visiting "c" redundantly and has to visit 'e" by satisfying its causal constraint again.
F
Discussion: Reward vs Critic Shaping
In comparison to previous reward shaping approaches Ng ct al. 1999 Grzeš 2017 Jiang et al. 2021 Devidze
et al.
2022
Icarte et al. 2022 the critic shaping proposed in HDCS offers three primary advantages.
First, the auxiliary rewards in critic shaping depend solely on the stages and rounds, making them simpler to compute than those in PBRS (Ng et al. 1999) which need potential function (sce Figure
12
Second, because the policy is trained using critics rather than rewards, critic shaping directly modifies the critic function, thereby expediting policy learning more effectively than previous reward shaping methods. In prior techniques, auxiliary rewards are first added to the original reward function and then incorporated into the critic function, which can lead to inefficient sample usage and slower policy learning.
Third, critic shaping provides stable targets for learning the critic function, preventing the agent from being influenced by other subgoals and thus stabilizing the overall policy learning process. This aspect is particularly important for satisfying DFA constraints, as DFAs consist of multiple subgoals, many of which do not have progress toward the DFA satisfaction and can destabilize the agent's 's learning process. As illustrated in Figure 12 in reward shaping the second visit to state 1 yields an auxiliary reward of 11.02 that affects the target for updating critic function at state 2. However, in critic shaping, since the second visit to state 1 there is no progression to new stage, this visit receives an auxiliary reward of 0, which does not influence the critic target at state 2 and thereby maintains greater stability in the critic and policy learning processes.
Remark. Another example of the benefit of critic shaping about stability is shown in Figure 13 When the agent is not well trained, especially in early training period, the critic values in every stage are almost small, as shown by the blue curve in Figure 13 In this case, the high value of (a and the max operator in equation and equation can prevent the agent's learning in stage k from being inffuenced by the poorly-learned critic values in stage k (blue curve). It essentially inserts a barrier at the boundary between stages k and h - 1, and fixes the critic value of target states in stage i at Ra(i,)) This barrier can make the agent's learning of stage k focus on going to stage k - 1, stabilizing its learning behavior.
If we simply use "+' in equation 3 and equation q RA(i, k:) cannot work like a barrier and the small values in stage & will be added to critic targets stage k, destabilizing and slowing down the agent's learning stage k. Therefore, Ri k) can stabilize the critic's learning in stage A and accelerate the policy learning. This effect can be extended to other stages with other RA.
Intuition of equation 2 Due to the discount factor y of the MDP, the auxiliary reward Rx k) can be attemuated exponentially when the critic function is updated according to equation 3 and equation 5 If the trajectory is long, RA may become small at earlier stages, say stage k + 1. If the condition equation 2 is violated, i.e., ( k) < Ra + 1) (T denotes the number of time steps from stage 1 to k), the reward information in stage I cannot back-propagate to stage k ++1 and carlier stages, which makes the agent's policy learning in stage k + 1 be unaware of rewards in stage k and lose optimality. Therefore, we have to make sure that the condition of RA in equation 2 holds. This condition guarantees that the reward information in every stage and round can back-propagate till the beginning of the trajectory (initial state), which can make the agent's policy learning reach optimality.
The examples of RA and their discounted values are shown in Figure 13 The solid lines show that values of RA satisfy the condition equation 2 The red dashod line shows the case where equation [ violated, where the red line can block the back-propagation of reward information and make the return estimation at stage k inaccurate, deviating the policy learning from its optimal solution.
23

---

Published in Transactions on Machine Learning Research (08/2025)
g
y
g A m.
0.94
y
g
y
b
b 10
3
2
0.96
b A y
b A
(a) Reward Shaping
(b) Critic Shaping
Figure 12: Comparison of reward and critic shaping. A task DEA in the example environment (Figure 2(a) is shown in (a) and (b). The red line denotes the agent's path (r, y) on the DFA, where state 2 is visited twice by mistake. (a): Assume that the potential function of states are ((0) = -3 o(1) = -2, 6(2) = 1,, 9 = 0 and discount. factor = 0.98. Based on PBRS, the auxiliary rewards are computed as Φ(s') 7 Φ(s) and denoted as red and blue numbers. (b): state 1, and are in stage 3, and 1, respectively. The auxiliary
rewards in terms of stage are denoted as red and blue numbers. Note that in (a) the critic value of state 2 will be influenced by the second visit. to state 1. But in (b), it will be fixed 10, no matter where the agent. goes after visiting state 2 (except state in better stage).
V
Ra k -2)
RA k - 1)
RA M
12 k time 6
Figure 13: Examples of auxiliary rewards RA- Each RA is shown as a solid line, which is discounted over one stage in back-propagation, and its discounted value is shown as dotted line. The dashed arrow denotes the direction of reward back-propagation process. h; a round. The vertical axis is the value of critic function. The red line denotes a wrong choice of RA value which blocks the pook-propngttion of reward information. The blue dashed line denote the situation that the critic values are small in stage k- --1 when the critic function is not well trained. In this case, the max operator can make the high value of RA (i, k) barrier and prevent the agent from being influenced by the critic values in stage A 1, stabilizing the agent's 's learning in stage k.
and
denote stage indices. is the index of
24

---

Published in Transactions on Machine Learning Research (08/2025)
Figure 14: Map of Minecraft. Only subgoals in the level 0 are shown. Higher-level subgoals become visible after their prerequisites are satisfied.
G Environments
We evaluate the proposed framework two domains, including 2D-Minecraft and AssemblyZone. These domains all have complex hierarchical structures of subgoals with very sparse rewards, covering both discrete and contimuus state-action spaces. The task is specified by the user in the form of LTL specification. Different from previous papers (Sohn et al. 2018 Hu et al. 2022), we consider the hierarchical subgoal structures containing prerequisites under temporal ordering constraints, which are common in many real-world scenarios. Note that every subgoal has multiple copies in the map, requiring the agent to decide which copy is the optimal to visit.
G.1 2D- -D-Minecraft
MiMeecaaaftt is modified 2D version of the famous Minecraft (Guss et al. 2019 In one episode with limited number of steps, the agent must navigate the map, pick up various materials, and craft tools to complete the task. Compared with original Minecraft game (Guss et al. 2019 Hu et al. 2022), we add some more objects to complicate their relationships. As shown in Figure 14 in a 12 x 12 grid-world there are 11 objects corresponding to the subgoals of level 0, including wood, stone, water, scroll, tool workshop, iron workshop, wizard, neeromancer, iron ore, coal and zombie (verbs are omitted). There are other subgoals in the higher levels, including stone pickaxe, iron, stone sword, fountain, iron pickaxe, iron sword, exorcism and killing zombic. Visiting some lower-level subgoals in certain orders can unlock and enable subgoals in higher levels.
The subgoal hierarchical structures are shown Figure 15 which are unknown to the agent initially. For example, when the agent first visits the stone and then tool workshop, the subgoal of making stone pickaxe becomes feasible at the workshop, which can produce a stone pickaxe if selected. In order to make iron, coal and iron ore can be collected any order and then fed into the iron workshop to produce iron. The prerequisites of both stone and iron swords contain wizard, since adding some magic the raw materials can make the swords more effective. Asking the necromancer to process the stone sword can make it strong enough to kill the zombie. As shown in the highest level, the ultimate goal of this game is to use the sword to kill zombie or produce exorcism to drive away zombie. The LTT. task in this domain is compased by all the subgoals from level 0 to level 3.
G.2 AssemblyZone
This domain is modified from the Zone domain Vaezipoor al. 2021 where the subgoal hicrarchy is added. Tt is simulated robotic environment where the robot dynamics is implemented by the Safety Gym (Ray et al.
25

---

Published in Transactions on Machine Learning Research (08/2025)
Level
scroll
stone pickaxe
Iron workshop
tool workshop
wizard
necromancer
iron
coal
zombie
sword
Level
Level
fountain
exorcism
Iron pickaxe
WIN
zomble
iron sword
Figure 15: The subgoal hierarchy in Minecraft. Prerequisite sequences of subgoals connected by arrows whose directions show the ordering constraints.
(a) Screenshot
(b) Map
Figure 16: Screenshot (left) and Map (right) of AssemblyZone.
2019). Specifically, the agent is the point robot with actions for steering and forward/backwar acceleration.
It observes lidar information towards the zones and other sensory data (e.g,, accelerometer, velocimeter), where the observation a real-valued vector with 92 dimensions. The zones and the robot are randomly positioned on the plane at the start. of each episode. The agent is navigating the map to visit zones different colors in an order specified the LTL task, including rod ('R'), blue ("B"), yellow ("Y"), green ('G*)
and white ('W"), shown in Figure 16
This domain is created to simulate the warehouse robot in practice. Zones in the same color contain same kind of parts. Whenever the agent visits a zone, it collects the corresponding part and gets a letter a symbol. Collecting and assembling different parts in certain orders, which form sequences of symbols, can create new products. In addition, some products can be combined to produce more complex products. Therefore, parts in zones and products can form hicrarchical structures of subgoals, as shown in Figure [7 (short for 'p1' to 'p5') are categorized into two levels. The prerequisites
The products numbered from of product only contain products in lower levels. For example, after visiting the red, blue and green zones
26

---

Published in Transactions on Machine Learning Research (08/2025)
Level
Level
Level 2
p1
red
blue
yellow
p3
p1
p4
r
p2
p1
p5
green
white
p2
p3
Figure 17: Hierarchical structures of subgoals in AssemblyZone.
The subgoal prerequisites are connected by
WO
st
ne
0
wood
wa
wa
wa
wa
WO
st
1
coal
E.W.
t.W.
t.W.
t.w.
coal
stone
WO
st
ne
9
11
SC
scroll
WO
st
3
2
12
13
14
15
(a) Minceraft Task
(b)
Minecraft Task 2
R
0
1
G
0
1
1
Y
B
B
W
W
F
G
2
W
B
B
R
3
2
3
(c) AsscmblyZone Task
(d) AssemblyZone Task
Figure 18: Task automaton compose by primitive subgoals. 'wo', 'st", 'ne", "wa", 't.w.", and "sc" represent wood, stone, necromancer, water, tool workshop, and scroll, respectively. 'R", "G', 'B', "W" and 'Y" are short for red, green, blue, white and yellow zones, respectively.
sequentially, the subgoal of producing product 1 ('pl") is unlocked and the agent can produce 'pl' directly without taking any other actions. The prerequisites of products in level 2 contain products in level 1. For instance, in order to produce 'p4', the agent noeds to first produce 'p3' and then "p2'. The LTL task in this domain is composed by letters of both parts ('r', "b", 'y", "g", "w") and products ('pl",.. 'p5').
Evaluation Tasks
The tasks composed by primitive subgoals are shown in Figure 18] where subgoals can be visited without satisfying any prerequisites. In the 2D-Minecraft environment, the task for evaluation to keep collecting wood, stone and scroll in a fixed order and collect collect coal can go back a previous automaton state. The task 2 is to first collect wood, second collect stone, then visit necromancer, and first. collect.
27

---

Published in Transactions on Machine Learning Research (08/2025)
WO
s.p.
0
2
3
iron
wa
wa
wa
wa
WO
ir
s.p.
water
fountain
i.p.
i.p.
i.p.
i.p.
water
Wo
ir
s.p.
9
10
11
SC
6
Sc
Sc
stone
sword
WO
ir
s.p.
3
12
13
14
15
(a) Minecraft Task
(b) Minecraft Task 4
p3
0
0
p2
R
1
p5
P4
3
4
3
(c) AssemblyZone Task
(d) AssemblyZone Task
Figure 19: Task automaton compose by higher-level subgoals. In addition to Figure are short for iron, stone pickaxe and iron pickaxe, respectively.
18 'ir' "s.p." and "i.p.'
1
0
0
2
2
1
2
1
g
g
g
2
F
F
2
g
1
3
g
g
4
4
4
3
3
(a) Task
(b) Task 2
Figure 20: Task DFA in Button domain. Here numbers are indices of buttons and "g" represents the moving gremlin.
28

---

Published in Transactions on Machine Learning Research (08/2025)
water, second visit tool workshop, then collect scroll, where these 6 items can be done in any orders long the ordering constraints are satisfied. Specifically, the task 2 of Minecraft can be represented as (wwo/ A 0(st A Qne)) A Q(wa A (t..w, A (se)) in the form of LTL formula. The task 1 in AssemblyZone environment is to keep visiting red, then green, then yellow zoncs in a fixed order without visiting blue zone at any time. It can be written as ( A OG A QY)) A ((-B). The lask 2 in AssemblyZone is to visit green, then yellow, then blue and finally red zone for only once, and visiting white zone can go back to a previous automaton state.
The tasks with subgoal hierarchy are shown in Figure 19 where visiting some subgoals needs to satisfy prerequisites first. The agent needs to form a product automaton to complete the task, which multiplies the task automaton and prerequisite automaton together, as an example shown in Figure 4 In Minecraft environment, task 3 and 4 are formed by replacing some subgoals in task 1 and 2 with higher-level subgoals. In AssemblyZone, task and are formed in similar ways.
The tasks in Button domain are shown in Figure 20
Baselines
1.1 Baselines for Hierarchy Discovery
In order to evaluate the performance on the exploration and discovery of subgoal hierarchy, we compare the stage 1 of HDCS with three baselines. Every method is evaluated in the same subgoal set G. Subgoals in level 0, stored in the set Go, do not have any prerequisites to visit and are visible in the map, while visiting subgoals in higher levels has prerequisites in the form of subgoal sequences. The first baseline is used to evaluate the capability of exploration only, while other baselines are designed for both exploration and discovery of subgoal hierarchy.
Vanilla HRL (VHRL). This is implemented as a two-level HRL agent. Specifically, in the low level, there is a goal-conditioned policy trained to achieve subgoals in Go selected by the high-level part. The low-level action is the primitive environmental action. In the high level, an RNN-based policy is trained to learn sequences of subgoals in Go to reach the final target of the environment (i.e., subgoals in the highest level), where the action space is Go and the observation is the symbolic observation denoting the subgoal achieved by the agent.
HAC (Levy et al., 2019). This method is a two-layer HRL similar as VHRL. The low-level part is same as that of VHRL. In contrast to VHRL, the high-level part is an goal-conditioned based policy trained to achieve a subgoal in g \ Go by using sequences of subgoals in Go- Besides, HAC discovers subgoal hicrarchy with vandomness-driven exploration paradigm (Levy et al. 2019). We also use HER (Andrychowicz el al. 2017) to augmeett the training of the high-level part.
MEGA (Pitis et al., 2020). This bascline designed to use curriculum learning to improve HAC. MEGA train subgoals in 9 Go in the order of their training progress, where the subgoal in every episode is selected according to the principle of minimum density approximation. Other parts are same as HAC.
In every method evaluated in experiments, there is pre-training phase which trains the low-level part to achieve subgoals in Go in a fixed number of time steps. In HAC and MEGA, whenever well trained, the prerequisites of every subgoal can be obtained as the output sequences of the high-level policy conditioned on that subgoal, building the subgoal hierarchy.
1.2 Baselines for Task Completion Evaluation
In every baseline, auxiliary reward is added to the original reward function of the environment, and the backbone is the PPO algorithm (Schulman et al.) (017)) whose hyper-parameters are set same as the proposod franework. In Appendix 4.3] we compare critic shaping with these baselines in the Button domain, where the backbone is DDPG (Lillicrap et al. 2015).
29

---

Published in Transactions on Machine Learning Research (08/2025)
1.0
Proposed
1.0
Proposed
Proposed
Proposest
VHRL
VHRL
VHRL
VIRRL
HAG
HAC
VEGA
0.6
MEGA
0.4
0.2
0.2
0.0
0.0
0.0
Sxie5
2
Exfe5
10xte6
10x1e6
(a) Minecraft Exorciam
(b) Minecraft Kill Zombie
(c) AssemblyZone pd
(d) AssemblyZone p5
Figure 21: Performance comparison on the exploration capability reaching a single final target of each domain. The success rate (y-axis) about reaching one specific target denoted in the caption.
PPospood HAG MEDA
Proposed HÁG MEDA
0.70
6.70
0.00
0.00
Icentai
esc4cam
22
25
P2
15
(a) Minecraft 1.5e5
(b) Minecraft 4e5
(c) Assembly Zone 3e6
(d)
Zone 8e6
Figure 22: Performance comparison on reaching intermediate subgoals given fixed number of training samples. The number of training samples is denoted in the caption.
PBRS. The first baseline is the PPO augmented with auxiliary rewards computed by using PBRS method (Ng et al., 1999 Jiang et al. 2021b. The potential function is defined in teriss of the automaton state, ie., ((s). Specifically, ((s) is equal to the negative distance from s to its closest accepting state, multiplied by a scaling parameter k = 10. An example with a. 1 is shown Figure a).
Naive-RS. Moreover, we adopt naive baseline which rewards transitions over task automaton that reduce the distance to the accepting state, short as Naive-RS. For any state u in task automaton Ag, the distance to its closest accepting state over Ag is represented by the potential function Φ(u). For any transition ((s, u), o, (s', u')), the auxiliary reward is 10 if (u) ((u') is otherwise 0.
The third baseline we use is an adaptive variation of Naive-RS. It works in the same way as Naive-RS, but it adaptively adjusts auxiliary rewards of cach stage by using the method introduced in Section 3.2.4. making every auxiliary reward adaptive to the difficulty of its corresponding stage.
Adaptive-RS.
J Subgoal Hierarchy Discovery
In this section, as a supplement to Section we present more detailed results on the performance comparison about the discovery of subgoal hicrarchy.
As shown in Figure 21 the proposed HRL-based method outperforms baselines in every highest-level subgoal of each domain, reaching every subgoal faster than baselines. Besides, given different number of training samples from the environment, we also evaluate the efficiency of the proposed and bascline methods on reaching some intermediate subgoals, as shown Figure 22 We can see that the proposed method still reaches intermediate subgoals faster than baselines. Note that baselines can reach highest-level subgoals with some probability the carly learning stago. This because those basclines select the target subgoals train the high-level agent with some randomness, ignoring the hierarchical nature of the subgoal space. However, this ignorance makes these baselines be outperformed by the proposed method finally.
30

---

Published in Transactions on Machine Learning Research (08/2025)
1.0
Proposed
0.8
0.8
No Discovery
0.6
0.4
0.4
0.2
Proposed
0.2
Discovery
0.0
0.0
10xte5
2
10x1c6
(a) Minecraft
(b) AssemblyZone
Figure 23: Ablation study on subgoal hierarchy discovery. Minecraft and AssemblyZone domains.
The lasks for evaluation are both task 4 in
Baseline
HDCS
Baselire HDCS
Minecreft-1
Minecroft-2
Zone-1
Zone-2
(a) Minecraft.
(b) AssemblyZone
Figure 24: Optimality comparison. y-axis is the return (discounted accumulated rewards).
K
Ablation Study
In this section, will conduct. some ablation studies the HDCS framework. We first investigate the performance of task completion without subgoal hierarchy discovery, and then compare different choices of auxiliary rewards which may violate the condition equation 2 showing the importance of various components of the algorithm design.
K.1 Effect of Hierarchy Discovery
In order to study the effect of hierarchy discovery, we design baseline "No Discovery' which directly uses the second part of HDCS framework, i.e, critic shaping and PPO, to solve the task 4 of Minecraft and AssemblyZone. These two tasks contain subgoals which have prerequisites to satisfy. The performance comparison is shown in Figure 23 We can see that the baseline almost cannot solve the given task, showing the significance of subgoal hierarchy discovery.
K.2 Ablation Study for Optimality
A simple idea. is use the low-level policies trained in phase directly solve the given DFA task in phase 2, without using critic shaping to train any new policies. However, this mothod can have the sub-optimality issue in the found solutions. We term this method as 'baseline", and compare its optimality with the proposed HDCS framework. The comparison is shown in Figure 24
we first compare the bascline and HDCS in task and 2 in 2D-Minerraft domain, short Minecraft-1 and Minecraft-2. We also compare the optimality in task 1 and 2 in Zose domain, short. as Zone-1 and Zone-2. The DFA of these tasks are presented in H The final reward Rp, is given at the last visit an accepting state in task DFA, where RF rewards are not counted when computing the return. The higher the return is, the less time steps are used in task completion.
In Figure 24
Minceraft and 100 AssemblyZone. Auxiliary
31

---

Published in Transactions on Machine Learning Research (08/2025)
1.0
Proposed
0.8
Choice-1
Choico-2
0.6
0.4
0.2
0.0
0
4
8
8
10x1e5
(a)
(b)
Figure 25: Ablation study on different auxiliary rewards in AssemblyZone domain. (a): The red path shows the optimal solution of the task. (b): performance comparison for abalation study.
In baseline, no policies are trained in the phase 2. In HDCS, the return is evaluated when the agent is trained with 5e5 and 10e6 environmental samples in Minecraft and AssemblyZone domains, respectively. We can see that the HDCS outperform the baseline in every evaluated task. This is because every symbol has multiple copies in both domains and the policies in HDCS are trained from scratch to select the optimal symbol to visit.
K.3 Effect of Auxiliary Reward Condition
In this section, study the importance of the auxiliary reward condition equation 2 We design a task in the AssemblyZone domain by introducing some causal relationship. As shown in Figure 25(a) the task is to first visit the red, then green, and finally blue zones, where each zone has fixed position in every episode. There is a yellow key (relized by a yellow zone) fixed at the upper left corner of the map. The sizes of map and zones are choson smaller than previous experiments in AssemblyZone domain.
However, we assume that the agent can only visit. blue zone with a yellow key which can be picked up by visiting the yellow zone. The agent does not know this causal relationship initially, and it has to learn this by interacting with the environment. The horizon of every stage is 300 and discount factor is 0.998. In this case, apply critic shaping and PPO, which is the stage 2 of HDCS, to solve the given task and evaluate different choices of auxiliary rewards RA. The proposed framework chooses RA = [10, 20, 40) for three stages in task DFA. Additionally, we have [10, 10, 10] as choice-1, and [10,30, 10] as choice-2.
The performance comparison is shown in Figure 25(b] We can see that these two choices perform poorly and cannot solve the task at all. The reason is that the auxiliary rewards of stage 2 and 3 do not satisfy condition equation
2 and prevent the reward information of stage 3 (i.e., reaching the blue zone) from back-propagating to stage 2. This can make the agent only focuses on reaching green zone in stage 2 and ignore picking up the key, so that the blue zone can never be reached in stage 3. If the reward cannot back-propagate across every stage smoothly, the optimal solution cannot be learned.
K.4 Effect of Max Operator
In addition, we further conduct ablation studies on the max operators in critic shaping. The bascline
method replaces the max operator in equation X and equation 4 The environment is the AssemblyZone domain and the tasks are task 1 and 2 without subgoal hierarchy (introduced in Appendix Hp. We choose
RA [10, 20, 40,...]. The performance comparison is shown in Figure 26
We can see that if the proposed method replaces the max operator with the addition used in conventional reward shaping methods, the performance degrades. The reason is that, although auxiliary rewards RA are large enough to satisfy equation 2 the values produced by the critic function are usually small in the early learning stage. Using the max operator can prevent the learning in one stage from being influenced by the values of next stage. Hence, it stabilizes the targets of the learning of critic function and improves the
32

---

Published in Transactions on Machine Learning Research (08/2025)
1.0
1.0
Proposed
Proposed
0.8
Baselline
0.8
Baseline
0.6
0.6
0.4
0.4
0.2
0.0
0.0
2
4
10xte5
2
4
8
10x1e5
(a) Task
(b) Task 2
Figure 26: Ablation study the max operator of critic shaping in the AssemblyZone domain.
learning efficiency of both critic and policy. This is visualized and demonstrated by the blue curve in Figure
B
Section F+
33


Reviews:
[{"review_id": "qrNVcsCTfi", "reviewer": "Reviewer_1PEB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n- As far as I know, unknown hierarchies & sparse rewards are rarely handled together in existing \n- The method, bypassing slow reward-to-critic propagation and yielding stable learning targets, seems interesting\n- Composite ablation studies look good, including (i) omitting hierarchy discovery, (ii) illegal auxiliary-reward schedules, and (iii) removing the max, each of which degrades performance\n- Code link is provided; hyper-parameters and task DFAs are spelled out in appendices.\n\nWeakness: \n- The main concern is that the experiment platform is oversimple, Minecraft and AssemblyZone are handcrafted, and the Button tasks have $\\leq$ 4 buttons. It is unclear how does HCDS scales to larger DFAs ($\\gg$ 20 states) or real robotics.\n- The auxiliary-reward schedule $R_A(i,k)$ is hand-tuned per domain (Appendix D). How robust is HDCS if these values are mis-specified, especially in unseen environments?\n- Phase 1 pre-training seems sample-hungry (millions of steps, Fig. 6). A wall-clock or GPU cost comparison is missing.\n- The critic-shaping idea resembles “max-reward RL” (Veviurko et al., 2024) and the hierarchy discovery phase borrows heavily from HAC/MEGA but with a level-wise schedule.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper tackles two long-standing obstacles in automaton-specified reinforcement learning (RL), including hidden sub-goal hierarchies and extreme reward sparsity. \nThe authors propose HDCS, a two-phase framework with sub-goal hierarchy discovery and critic shaping. Experiments on three domains (2D-Minecraft, AssemblyZone, Safety-Gym Button) show 2–3 × faster convergence versus PBRS, Naive-RS, Adaptive-RS and several HRL baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- provide O(#states, #sub-goals) bounds for Phase 1 exploration and Phase 2 convergence.\n- please add a table to map prior methods with the addressed challenges, and highlight what HDCS uniquely contributes.\n- It will be helpful to add experiments to show the real scaling, e.g. MiniGrid-SkillWorld or StarCraftII mission", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3keKmUXdXR", "reviewer": "Reviewer_ZGCC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper offers a clear and innovative approach by coupling automated hierarchy discovery with critic shaping, significantly improving sample efficiency on sparse-reward tasks. Its major strength is the careful empirical validation: multiple domains, strong baselines, detailed ablations, and openly available code support reproducibility and thoroughness. The introduced critic-shaping technique is conceptually simple yet notably effective, enhancing practicality.\n\nHowever, several concerns exist. The theoretical justification for why the critic-shaping technique preserves optimality remains informal, lacking explicit proofs or rigorous conditions. Evaluation tasks are limited to custom-made simulations, leaving open questions about the approach’s generalization to widely-used benchmarks or real-world applications. Additionally, the scalability of the method with respect to computational resources and state-space complexity is not clearly addressed. Important recent baselines relevant to DFA-based reinforcement learning are also absent from comparisons.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents **HDCS (Hierarchy Discovery and Critic Shaping)**, a reinforcement learning framework that automatically discovers sub-goal hierarchies and improves learning efficiency in tasks specified by deterministic finite-state automata (DFA). HDCS first learns prerequisite DFA structures through hierarchical policy interactions, effectively capturing intermediate sub-goals without manual specification. Next, the paper introduces a critic-shaping approach that mitigates sparse reward issues by providing more stable and dense training signals without altering optimal policies. Empirical evaluations conducted across three simulation domains—2D-Minecraft, AssemblyZone, and Safety-Gymnasium—demonstrate HDCS’s superiority over existing hierarchical RL and reward-shaping baselines in terms of both accuracy of hierarchy discovery and overall sample efficiency. Extensive ablations reinforce the significance of each component of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Provide a formal theoretical analysis or proof clarifying under what conditions the critic-shaping method preserves optimal policies.\n2. Conduct a hyperparameter robustness analysis, focusing on parameters like stage horizon and auxiliary reward scale, to assess the sensitivity of HDCS's performance.\n3. Evaluate HDCS on more public benchmarks (e.g., MiniGrid-LTL, CraftWorld or ZoneENV...) to demonstrate broader applicability.", "broader_impact_concerns": "The work aims to improve interpretability and effectiveness in specifying complex, temporally-extended tasks, potentially benefiting safety-critical and robotics domains. Nevertheless, incorrect hierarchy discovery could inadvertently introduce unsafe constraints. The authors should explicitly discuss strategies to mitigate such risks, including human validation or automated verification processes. Otherwise, no significant ethical or societal issues are apparent.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TmI95tRQBN", "reviewer": "Reviewer_LooW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\n- The problem studied seems to be relevant for complicated problems in RL.\n- The general idea behind the method sounds reasonable.\n\n## Weakness\n\nThe biggest issue for this paper is that the presentation is very confusing, which makes it hard to evaluate the value of the proposed method. Here are some questions of mine:\n- For the first phase, the exploration, the authors seem to assume the availability of a low-level policy $\\pi^l(a|g)$ which can reach all the goals already. How is this policy obtained in the experiments? More importantly, how would such a policy be acquired in real-world applications?\n- After the exploration phase, we obtain a hierarchical policy that can reach any goal given the correct prerequisites. Given a task DFA, wouldn't executing the appropriate sub-policies in sequence suffice to solve the task? It's unclear what is being learned in the second phase.\n- Figure 5 is very confusing. Can you explain what does the different colour means for the arrows?\n- I am not sure if I understand the product DFA correctly. There are drawings for task DFA and prerequisite DFA, but not for product DFA. Can I understand it as a flattened and merged version of the task DFA and prerequisite DFA? For instance, for the example in Figure 11, should I understand the product DFA as a sequence of a → b → c → f → e → c that the agent need to visit in the correct order?\n- The difference between the proposed method and the relevant baselines is not clear to me. For the first phase, from Appendix G.1, it seems like the only difference is that the proposed method can build arbitrary layers of hierarchy while all the baselines are constrained to build only 2 layers. \n- Why is VHRL not in Figure 6 (c, d) and Figure 7? \n- Why is the number of environment interactions different between figures? For Minecraft, Figure 6 (a) shows up to $5e5$, Figure 6 (c) shows the point at $3e5$ while Figure 7 (a) shows up to $1e6$; For AssemblyZone, Figure 6 (b) and Figure 7 (b) show up to $1e7$ while Figure 6 (d) shows at the point of $6e6$. How are these numbers selected?\n\nMinor issues:\n\n- Citation Format issue: I would like to remind the author to take care of the difference between \\citep and \\citet, the majority of the citations in this paper should in \\citep format but they are currently all in \\citet format.\n- I think the SC2 example in Figure 1 is a bit misleading. First, the hierarchy there is very subjective. For example, to scout the enemy defence one can do a radar-scan instead sending a small group of units. Minecraft can be a better example since the hierarchy is objective. For example, one cannot build a stone pickaxe without stone, which is a hard constraint of the environment. Second, it feels like an overstatement since the algorithm in this paper feel far away for solving SC2 and you are not conducting experiments on that task.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studied the problem of using deterministic finite-state automaton (DFA) to define complicate tasks which are not easy to defined by a single scalar reward. The authors identified two problems within the current framework: (1) There can be hidden temporal structure about the fulfillment of goals and (2) the sparse reward problem when the DFA is complicated. For the first problem, the authors propose an exploration method to build the hierarchical structure of the hidden DFA iteratively; While for the second problem, the authors propose a critic-shaping method based on heuristic. Experiments on three toy examples demonstrate the proposed method is better than some baselines.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the Weakness section.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)