Hierarchical Reinforcement Learning with Targeted Causal Interventions
Authors: Mohammadsadegh Khorasani
Saber Salehkaleybar
Negar Kiyavash
Matthias Grossglauser
Venue: ICML 2025 poster (2025)
Keywords: Structural Causal Models
Causal Discovery
Hierarchical Reinforcement Learning
Intervention
Subgoal Discovery
Primary area: general_machine_learning->causality

Abstract: Hierarchical reinforcement learning (HRL) improves the efficiency of long-horizon reinforcement-learning tasks with sparse rewards by decomposing the task into a hierarchy of subgoals. The main challenge of HRL is efficient discovery of the hierarchical structure among subgoals and utilizing this structure to achieve the final goal. We address this challenge by modeling the subgoal structure as a causal graph and propose a causal discovery algorithm to learn it. Additionally, rather than intervening on the subgoals at random during exploration, we harness the discovered causal model to prioritize subgoal interventions based on their importance in attaining the final goal. These targeted interventions result in a significantly more efficient policy in terms of the training cost. Unlike previous work on causal HRL, which lacked theoretical analysis, we provide a formal analysis of the problem. Specifically, for tree structures and, for a variant of Erdős-Rényi random graphs, our approach results in remarkable improvements. Our experimental results on HRL tasks also illustrate that our proposed framework outperforms existing work in terms of training cost.

Hierarchical Reinforcement Learning with Targeted Causal Interventions
Sadegh Khorasani
Saber Salehkaleybar
Negar Kiyavash 3 Matthias Grossglauser'
Abstract
many real-world applications, the agent faces tasks where rewards are sparse and delayed. This poses significant challenge to traditional RL since the agent must take many actions without receiving an immediate reward. For in- stance, in maze-solving tasks, the agent might only receive reward once it finds a path to a specific exit or loca- tion within the maze. Hierarchical reinforcement learning (HRL) allows the agent to break down the problem into subtasks, which is helpful in environments where achieving goals requires long horizon (Bacon et al., 2017; Barto & Mahadevan, 2003; Eysenbach et al.. 2019; Le et al., 2018).
Hierarchical reinforcement learning (HRL) improves the efficiency of long-horizon reinforeement-leariing tasks with sparse rewards by decomposing the task into a hierarchy of subgoals. The main challenge of HRL efficient discovery of the hierarchical structure among subgoals and utilizing this structure achieve the final goal. We address this challenge by modeling the subgoal structure as a causal graph and propose a causal discovery algorithm to learn it. Additionally, rather than intervening on the subgoals at random during exploration. we harness the discovered causal model to prioritize subgoal interventions based on their importance in attaining the final goal. These targeted interventions result in significantly more efficient policy in terms of the training cost. Unlike previous work on causal HRL, which lacked theoretical analysis, we provide a formal analysis of the problem. Specifically, for tree structures and, for variant of Erdös-Rényl ran- dom graphs, our approach results in remarkable improvements. Our experimental results HRL tasks also illustrate that our proposed framework outperforms existing work in terms of training cost.
Hierarchical policies are widely used in HRL to manage the complexity long-horizon and sparse-reward tasks. How- ever, learning hierarchical policies introduces significant challenges. To address these issues, many methods are pro- posed to improve learning efficiency (Kulkarni et al., 2016; Levy et al., 2017: Vezhnevets et al., 2017). The high-level policy does not deal with primitive actions but instead sets subgoals or options (Sutton et al., 1999) that the lower-level policies must achieve. Lower-level policies are trained to achieve subgoals assigned by the high-level policy. In or- der to discover meaningful subgoals and their relationships, it is essential to ensure that both high-level and low-level policies explore the environment efficiently. However, naive exploration of the entire goal space is not sample efficient in high-dimensional goal spaces. Some studies in the liter- ature aim to improve sample efficiency and scalability by employing off off-policy techniques (Nachum al., 201 (0),,,, utilizing representation learning (Nachum al., 2018a), or restricting the high-level policy explore only subset of the goal space (Zhang et al., 2020).
1. Introduction
In traditional reinforcement learning (RL), agent is typi- cally required to solve specific task based on immediate feedback from the environment (Sutton, 2018). However, in
In order to improve exploration efficiency, recently, Hu et al. (2022); Nguyen et al. (2024) proposed using an off- the-shelf causal discovery algorithm (Ke et al., 2019) to infer the causal structure among subgoals. This learned causal structure subsequently used select a subset of subgoals, from which one is chosen uniformly at random for exploration. In Nguyen et al. (2024), the agent initially takes random actions until it serendipitously achieves the final goal a few times-a scenario that is highly unlikely in long-horizon tasks with a huge state space. After that, the agent infers the causal structure among state-action pairs which more challenging than recovering the causal struc- ture among subgoals when the state space is very large.
'School of Computer and Communication Sciences, EPFI., Lausanne, Switzerland PLedden Institute of Advanced Computer Science (LIACSS) Leiden University, Leiden, The Netherlands *College of Management of Technol- ogy, EPFL. Lausanne, Switzerland. Correspondence to: Sadegh Khorasani <sadegh. khorasani @eauun@@epll.h.... Saber Salehkaleybar <s.salehkaley bar leddenuiivvn Negar Kiyavash <negar kiyavashe @ww.sshheepppphheccoccecccc eptl.ch>, Matthias Grossglauser imatthias.grossghhan certuusssr@@epfflhe @p....ch>.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

HRL with Targeted Causal Interventions
is noteworthy that the causal discovery algorithm used in both works was applied without any adaptation to the HRL setting, and no theoretical guarantee was provided regarding the quality of its output. Additionally, they did not include theoretical analysis for their proposed framework.
the defined subgoals. However, in the exploration phase, the subgoals chosen uniformly at random without w exploiting the causal relationships among subgoals. Recent work Hu et al. (2022): Nguyen et al. (2024) used the causal discov- ery algorithm in Ke et al. (2019) to infer causal structures among subgoals. In Hu et al. (2022), this learned causal structure is subsequently used to select subset of subgoals, from which one chosen uniformly at random (without any prioritization among the selected subgoals) for exploration. As result, it made limited use of the causal structure during exploration. In Nguyen et al. (2024), the agent initially takes random actions until it accidently achieves the final subgoal a few times (which is highly improbable in tasks with a large state space). Following this, the agent infers the causal structure among state-action pairs, which more challenging than inferring the causal structure among subgoals when the state space is large. Moreover, both work directly applied the causal discovery algorithm in Ke et al. (2019) without providing any theoretical guarantee on its performance.
In this paper, we introduce the Hierarchical Reinforcement Learning via Causality (HRC) framework where achieving subgoal by a multi-level policy formulated as an interven- tion in the environment. The HRC framework enables to discover the causal relationships among subgoals (so-called subgoal structure) through targeted interventions. The agent is fully guided by the recovered subgoal structure in the sense that the acquired causal knowledge is utilized in both designing targeted interventions and also in training the multi-level policy. Our main contributions are as follows:
We introduce a general framework called HRC (Section 4) that enables the agent to exploit the subgoal structure of the problem to achieve the final goal more efficiently. In particular, we design three causally-guided rules (sections 6 and F.9) to prioritize the subgoals in order to explore those with higher causal impact on achieving the final goal (see Section 6).
3. Problem Statement and Notations
Although subgoal discovery in the HRC framework could be carried out using off-the-shelf causal discov- ery algorithms, we propose a new causal discovery algorithm (Section 8) specifically tailored to subgoal discovery in the HRL setting, and we provide theoreti- cal guarantees for it.
In this section, we review the concepts and define the no- tations necessary to formulate our proposed work on HRL. In many real-world applications, an agent must perform a sequence of actions before receiving any reward signal from the environment. We focus on this specific setting, where the agent must achieve intermediate objectives before receiving a reward. Figure 1 shows a simple example where a crafts- man must obtain wood and stone to build pickaxe. The craftsman receives a reward only if he builds a pickaxe; oth- erwise, he receives no reward. That is, while obtaining both wood and stone are intermediate subgoals that the crafts- man needs to plan for, it does not result in a reward. The action space (denoted by A) for this game includes moving "right", "left", "up", and "down". "pick" and "craft", which enables the craftsman to interact with the environment.
Our HRC framework allows us to formulate the cost of training for any choice of exploration strategy (Section 5). In particular, we theoretically bound the training cost for our proposed causally-guided rules, which are derived harnessing the subgoal structure, compared to an agent that performs random subgoal exploration (Section 7).
The experimental results in Section 9 demonstrate the clear advantage of the proposed approach compared to the state of the art both in synthetic datasets and in a real-world scenario (the Minecraft environment).
In our setup, the agent per- ceives the environment in the form of "disentangled factors" (Hu et al., 2022). For instance, in a visual observation of robotic environment, the dis- entangled factors may include elements such as object quan- tity, object position, and veloc- ity. We define Environment Variables (EVs) as the disentan- gled factors of the environment observations. We assume that the agent has access all EVs. We denote the set of EVs by XgV (X,,'.. Xi]. The vector of these EVs
2. Related Work
Hierarchical policies enable multilevel decision-making (see Appendix A for related work). Moreover, causal relation- ships can be utilized to improve exploration, generalization, and explanation (see Appendix A). In the following, we review the related work at the intersection of HRL and causality.
Figure 1. Craftsman in the mini-craft game.
Causal hierarchical reinforcement learning: In Corcoll & Vicente (2020), a notion of subgoal is defined based on the causal effect of an action on the changes in the state of the environment. A bigh-level policy is trained to select from
2

---

HRL with Targeted Causal Interventions
at time step I, denoted by X = (Xi..... X)), is the state the system. In the craftsman game of Figure 1, the craftsman observes his position the map and the quantity of each object (wood or stone) in his backpack. Therefore, in this game, Agv = (X1, X2, X3, Xa}= = ("number of wood". " number of stone". " numbeer of pickaxe", "crafts- man position").
contains intermediary objectives that guide the learning of the policy, A is the set of actions available the agent, T S x A x S + [0, is the transition proba- bility function that denotes the probability of the transi- tion from state 8 to state s' after taking an action a, and R : S x A x & + IR is the reward indicator function of the agent pertaining to whether a subgoal g was achieved in state s after taking action a. More specifically, R(s, a. 1, if the subgoal g is achieved, otherwise it is zero. y is the discount factor that quantifies the diminishing value of future rewards. Given a state E S and a subgoal g E D, the objective in a subgoal-based MDP is to learn a subgoal-based policy a{a]s, g) S x &b + A that maximizes value function defined as (* = E, 1E>= ? R(se, de:g) sg = s].
We define a subset X' S Ngv. where each variable X; E X' represents resource environment variable. Resource environment variables refer to items, tools, or abilities that the agent attains throughout the game and are key factors in achieving the final objective. Without loss of generality, we assume that the first n EVs are resource EVs, hence X' (X1,- ........ ). where n S I. We denote the vector of X at time step t by X (Xf, , .x)). In our example, the objects wood, stone, and pickaxe are resource EVs. Therefore, X' = (X1, X3).
We the term system probes to refer to the observed state-action pairs. For a given time horizon H, the agent observes a sequence of state-action pairs (80, 00, ..... , - -I- called a trajectory. The action variable at time step t is denoted by A' E .A. We assume that the process (A', gg hezz can be described by a structural causal model (SCM) (see the definition of SCM C.1) in the following form:
Furthermore, we define a set of subgoals o = (gi,- .9. associated with a set of values e = fer,--. ,nn), where cach gi corresponds to resource EV X,. We say subgoal gi is achieved at time if and only if X; = ez- Without loss of generality, we consider In as the only desired main goal that the agent is supposed to achieve and refer to it as the "final subgoal" or "final goal". In our example, for instance, the subgoals 91. 92, and Is with the corresponding values e = 1, e2 = 1, and e3- = 1 correspond to obtaining one wood, one stone, and one pickaxe, respectively !.
In
X = f((pa(x++)), ), c s+1),
)
Vt 2 1 and 1 isish
A = fo(X :0 (11,,
Vt V220 0,
(1)
where pa(X; represents the parent of X in X X and ft is the causal mechanism showing how pa(X:+) influences X, at time / 1. Furthermore, e/41 and c represent the corresponding exogenous noises of X, and A at time t + 1, respectively.
In many woaldworld applications, resource variables (such as skill, tool, access to certain objects) only need to be attained once. For instance, once a skill is attained by agent in an environment, it remains permanently available. Motivated by this observation but mainly for ease of presen- tation, we suppose that the domain of each resource EV is {0, 13. and a subgoal X; is achieved when e; = 1
The summary graph G is used to graphically represent the causal relationships in the SCM where there is a node for each variable in XgV U {A]. Furthermore, an edge from X, to X₃ is drawn in Gf XJ E pa(X;*') for any Addi- tionally, there exist directed edges from the action variable A to each environment variable X; and from X; back to A.
We model the HRL problem of our interest through a subgoal-based Markov decision process. The subgoal- based MDP is formalized as tuple (8, A,T, R, 7), where S is the set of all possible states (in our setup, all possible values of xv 4 is the subgoal space, which
Definition 3.1 (Subgoal Structure).
'Our framework assumes discretized resource EVs, which is a reasonable assumption in domains where acquiring specific re- sources is required. For environments with continuous variables, one can apply disentangled representation lcarning methods to high-dimensional continuous observations in order to extract cate- gorical latent variables-suce such as using categorical VAEs. We view this as a natural extension of our current work.
The subgoal structure, denoted as F, is a directed graph (not necessarily acyclic), where the nodes represent subgoals in the set o. In $, a di- rected edge from subgoal gj to sub- goal gi exists if and only if there is at least one path in the summary graph G from X, to X; such that all inter- mediate nodes along this path belong to the set (K'v \ X²). These edges in & represent a one-step causal relationship from one subgoal to another by ignoring intermediate envi- ronmental variables not designated as subgoals.
Figure 2. Subgoal structure of the mini-craft game.
"Our proposed solutions can be extended to the settings with non-binary domains for EVs the cost of more cumbersome notation. The assumption of binary variables for resource EVs is made solely to facilitate the cost analysis in Section 7 and to provide theoretical guarantees for our causal discovery method in Section& 8. Indeed, in our experiments, we evaluate our proposed methods in the non- binary settings.
3

---

HRL with Targeted Causal Interventions
The subgoal structure of the above mini-craft game is de- pieted in Figure 2. We use the terms 'subgoal' and 'node' interchangeably. In I, the parent and children sets of subgoal 9: are denoted by pAg. and CH respectively.
4. Hierarchical Reinforcement Learning via Causality (HRC)
In this section, we introduce Hierarchical Reinforcement Learning via Causality (HRC) framework which guides the learning policy by incorporating information pertaining to hierarchical subgoal structure (see Definition 3.2). In order to describe the HRC framework, we first define the notion of "controllable subgoal."
In our setup, the subgoals are further categorized into two types, based on their corresponding causal mechanisms, gi an "AND" subgoal if it can be achieved at time step if and only if all its parents in the set P'g. have been achieved prior to time step f, indicating strict conjunctive require- ment for the achievement of gi- Pi is an "OR" subgoal if it can be achieved at time step t if at least one of its parents in the set PAg, has been achieved before time step t. This indicates a disjunctive requirement for the activation of 9:, where the achievement of any single parent is sufficient to achieve gi- In the rest of the paper, we represent an AND subgoal with a square and an OR subgoal with cirele in the figures.
Definition 4.1. For a given > O, a subgoal gi is (1 ()- controllable by the subgoal-based policy T(a | s, if there exists time step t" < H such that 9a is achieved with probability at least - (i.e., P(X = 1) 2 1 - -), when actions are taken according to π.
Assumption 4.2. We assume that if a subgoal 9s is achieved at a time step tx (i.e., X;" = 1). it will remain achieved for all future time steps. Formally, if X = 1, then X = 1 for all 2 L*.
We denote the estimate of o by 9. Additionally, the parent and children sets of a subgoal 9; in the graph & are denoted by PAY and CH1 g. respectively, For given set of subgoals
Remark 4.3. Suppose a subgoal gi is (1 - e) controllab.e In this case, based on Definition 4.1 and Assumption 4.2, X = 1 for all L 2 6", According to Definition 3.3. this is equivalent to intervention do do =) with probability at least 1 e, where the intervention can be performed by taking actions based on the subgoal- -bssd policy x 8, 9s). For the sake of brevity, from hereon we say a subgoal is controllable and drop (1 c).
L. CH2 Ug.EL CH
Definition 3.2 (Hierarchical Structure). The hierarchical structure is denoted by 7 = (H, C). where H is a directed acyclic graph (DAG) which is a subgraph of 9 and C 4 + N is a level assignment function, where L(g:) denotes the hierarchy level of subgoal gs. In H. each node is assigned to hierarchy level such that for each subgoal gi, L(g,)= 2 max S.EAA [(g)) +1 (See an example in C.I).
Before introducing the algorithm, we give a high-level overview using the example 1, explained in Section 3. The craftsman has no knowledge of the subgoal structure (i.e., Figure 2) but he knows which objects exist on the map (call them resources). Initially, he considers obtaining each re- source as a subgoal and divides subgoals into two sets: con- trollable (CS) and intervention (IS) shown in the figures with blue and green, respectively. Controllable Subgoals set are those that he has learnt how to achieve (see Defini- tion 4. 4)... Initially, both sets are empty (Figure 3()). The craftsman plays the game several times and learns how to gather "stone" and "wood". Thus, he can add "obtaining stone" and "obtaining wood" (call them root subgoals) to the controllable set, meaning he can from now on acquire them whenever needed (Figure 3(b)). At this stage, he can still be unsure how to craft pickaxe. Now, the craftsman starts loop and at each iteration of this loop, he chooses one of the items in the controllable set and adds it to the intervention set to explore whether it a requirement for obtaining other resources (i.e., subgoals). Let us assume he chooses "obtaining stone" (denote it as gse)) and adds it to the intervention set (Figure 3(c)). Then he plays the game multiple times, and observes all the trajectories (so- called interventional data) with the goal of discovering all reachable subgoals, which are the direct children of the sub- do = do, = 0)] goals in the intervention set. This is done using a causal ECEA (A, B, = EAX +A
Definition 3.3 (Intervention, Explorational Data). An in- tervention on a subgoal 9i at time t* is considered as re- placing the structural assignment (1) of the corresponding environment variable X, with X = a for t 2 t", where E {0, 13. This intervention is denoted by dx!" = a). Moreover, the explorational data of the subgoal gi is shown by D =1) and consists of the state-action pairs that the agent collects (the actions are taken randomly) from the time step t" until min H, t" + A), where A is a positive integer and H is the horizon.
Furthermore, for a given set of subgoals B and any time step X²= a implies that X! = a for all gi E B.
Definition 3.4. Let A and B be two subsets of subgoals क such that yn & (AU B). The expected causal effect (ECE) of A on the final goal 9n at some time step t" + A (where A is a positive integer) conditioned on do B = 0) is defined as:
-EXX do(X = do = 0)}. discovery subroutine in HRC algorithm (will be discussed
4

---

HRL with Targeted Causal Interventions
in Algorithm 1). In the example in Figure 1, "obtaining pickaxe" is an AND subgoal (see Figure 2), therefore it is highly likely that the causal discovery algorithm would not detect it as the child of "obtaining stone" alone. However, in the next iteration of the loop, when the craftsman also adds the subgoal "obtaining wood" to the intervention set (Figure 3(d)), he will discover that the subgoal "obtaining pickaxe" is the child of "obtaining stone" and "obtaining wood". He can now play the game multiple times to hone in on how to efficiently obtain a pickaxe (Figure 3(e)). Note that the main phases of the algorithm are learning the sub- goal structure and then exploiting it to train the policy. To learn the subgoal structure, the algorithm can benefit from purposeful "interventions" on the resources instead of naive random play (see Section 6 for details).
routine). Controllable set (CS)), is populated with root subgoals using SubgoalTrraniig subroutine.
3. Expand intervention set: In this step, a subgoal from CS is selected and added to the current intervention set 1S to form the new intervention set is, and then removed from the controllable set (lines 4-5).
4. Intervention Sampling: InterventionSampling sub- routine collects T trajectories. In each trajectory, randomly intervenes on the subgoals in IS, until the horizon H is reached or all the subgoals in IS, are achieved. We call the entire data collected in this sub- routine "interventional data" and denote it as Dr (see Appendix D.1 for more details).
Causal Discovery: After collecting interventional data (D1). the algorithm estimates the causal model and 9 using causal discovery method. We propose our causal discovery method in Section 8.
6. Candidate Controllabe Set: From Si we identify the set of subgoals that are not in IS, U CS,, but are children of subgoals in IS,, and all their parents are in IS, We call this set the candidate controllable set CCS, and its elements reachable subgoals.
(a)
(b)
7. Update-H:: To update the graph H. for each subgoal 96 CCS,, we add an edge from each parent g PA to gr. Additionally, the level of gi is updated to:
(c)
(d)
(e)
((g.) = { max
0,
if PA = 0, 9:
Figure 3. Discovering the subgoal structure in the mini-craft (Fig- ure 1). S. W, and P represent stone, wood, and pickaxe. The sets IS, and CS, are illustrated with green, and blue respectively.
((gz) + 1, otherwise.
9, SPEPA
8. Subgoal Training: Subgoal subroutine trains the subgoal- -based policy for achieving the subgoals in CCS; 3 (see Appendix D.4 for more details).
4.1. HRC Framework
The pseudocode of HRC is given in Algorithm 1. HRC algorithm at each iteration, chooses a subgoal from the controllable set (line 4) and adds it to the intervention set (line 5), then it collects interventional data (line 6) and uses causal discovery (line 7) to identify the reachable subgoals (line 8) from the current intervention set. These reachable subgoals are added to the hierarchy, assigned levels (line 9), and trained (line 10). Successfully trained subgoals are added to the controllable set (line 11), and the process repeats until the final subgoal is added to the intervention set or no further controllable subgoals remain. In particular, HRC is comprised of the following key steps:
9. Update Controllable Set: This step adds the trained subgoals to the controllable set CS..
Steps 3 to 6, aim of which is to find the reachable subgoals, form Stage 1, and steps 7 to 9, which train the reachable subgoals to make them controllable, form Stage 2. HRC can use different strategies to select a controllable subgoal from CS in line 4. If HRC randomly selects a controllable subgoal from CS,-1, we call it "random strategy"
Figure 4 illustrates a simple example of how strategically se- lecting controllable subgoals can enhance the performance of HRC. Figure 4 shows different stages of the underlying subgoal structure. In this example, we assume that every subgoal is of OR type. The final subgoal is node F. Reach- able subgoals are depicted in gray. Assume we have reached the stage where S and W are controllable (Figure 4(a)).
1. Initialization: We initialize intervention (ISp) and con- trollable sets (CS,) with empty sets. The hierarchical structure, H. = (H,, C). initially contains a graph H with the subgoals as nodes, but with no edges between them, and all the entries in L are set to O. 2. Pre-train: In line 2, we call JubgoalTraining on all the subgoals (b) to train the ones with no parent in T These subgoals are called root subgoals (see Appendix D.4 for more details about the SubgoalTraine sub-
"If a subgoal becomes reachable, becomes controllable after Subgoal Training step. However, in practice, this may not always be the case. Therefore, we consider a threshold and remove the ones that are trained well both from the CCS, and hierar- chical structure H (see Appendix D.4 for more details).
5

---

HRL with Targeted Causal Interventions
Algorithm 1 Hierarchical Reinforcement Learning via Causality (HRC)
Initialize subgoal-based policy x; intervention set ISg 0: controllable set CSo
0 hierarchical structure
H (H, L); iteration counter = 1.
2: CS f SubgoalTraining(T, H. ISg, Φ) {Train the root subgoals}
3: while In 1 and - * 0 do
Expand the intervention set by adding a potentially required subgoal
4: 9scl. f Choose a controllable subgoal from CS,-1
}
5: IS; f - U 1) CS; < CS \ (sset.))
Stage 1 (line 8)
6: Dt f InterventionSSampiingrr..
7:
G. < CausalDiscoovery(D), IS,)
Find reachable subgoals
8:
CCS, + {g:1 St $ (IS, U CS,) and gi E CHIS and PA c
9:
Update-Hd( S., IS,, CCS,)
Train reachable subgoals and add them the controllable set
10: CCS, - Surnoallraiiningt,,,, H. IS, CCS,)
Stage (line to 13)
11: CS2 4 CS, CCC,
1 1+1
13: end while
HRC will terminate earlier if selects subgoal S gsel. (Figure 4(c)), rather than W (Figure 4(b)). Therefore, strate- gic selection of controllable variables from CS in line 4 of Algorithm 1 can significantly improve the performance. In Section 6, we propose causally-guided selection mech- anisms to pick I in order to improve the performance. Before introducing these mechanisms, we formulate the cost of HRC algorithm in the next section.
action space is 4, and the action is determined by Jsel If are in state I and choose Isel, then transit to state I U {Ase) with a probability determined by the strategy in line 4 of Algorithm 1. Let Cg,, (I) be the expected cost of adding the final subgoal In to the intervention set when the current state I. Then, we have:
Cg. (I)
Σ PI, Ctrana(I, (9wl))
Sse E
+ Cg.. (IU (0mil)
where the transition cost Ctrans I U {9sa)) is the cost of transition from the current intervention set I to set by adding Isel to it (I U ).. Moreover, the cost-to-go, Cg.. (I U {g accounts for the future costs from the new state onwards. Both terms are weighted by the transition probability PI,zu(aa) the probability of transition from state I to {gse)) in M. This transition probability determined by the strategy in line 4 of Algorithm Based on the above definitions, the total expected cost is equal to Cg. (f)). ). See the detailed derivation of Cirans (I, (UU((a)) }) and Cg., (O) in Appendix E.
(a)
(b)
(c)
Figure 4. A showcase of HRC performing more efficiently under better selection of controllable subgoal. The sets IS, CS, and CCS are illustrated with green, blue, and gray colors, respectively.
6. Subgoal Discovery with Targeted Strategy
5. Formulating the Cost
In this section, we propose two causally-guide ranking rules (a third rule, which is a combination of these two rules is discussed in Appendix F.9) that utilize & and the estimated causal model to prioritize among controllable subgoals candidates for picking Isel, i at iteration in line 4 of Algorithm
In order to measure the effectiveness of any strategy used for selecting Isc. in line of Algorithm we need to formalize the training cost of the HRC algorithm, which is the expected system probes during Intervention Sampling and Subgoal Training accumulated in all iterations. To compute the expected total cost of Algorithm 1, we model its execution as an MDP, denoted as M. The state space of M is the power set of 4. state in this MDP, denoted by I, represents the intervention set IS in Algorithm 1. The
Causal Effect Ranking Rule An intuitive rule to es- timate the expected causal effect every 9s E CS,-1 on the final subgoal 9n. and select the subgoal with the largest
6

---

HRL with Targeted Causal Interventions
effect. Specifically,
Table I. Comparison of the cost hetween HRC; and HRC, in tree and Semi-Erdbe Rényi graphs.
EC ((9b), 0.9n))
1 arg max -CE,
TREE G(n,b)
SEMI-ERDÓS-RéNVI C(n.p)
HRCa HRC.
Olog"(n)) 1)(((b)
O 3(n3+3+log(n)
where ECE,, is the estimate of the expected causal effect defined in 3.4 (See Appendix H.3 for details on how to esti- mate the expected causal effect from the recovered causal model and also a discussion on the values of A and t*). When all subgoals are of AND type, under the conditions explained in Appendix F.I, this rule yields the minimum training cost as only subgoals with path to final subgoal are added to IS.
(2(x))
its parents has been added IS in the case of OR subgoal), For the ease of analysis, we exclude this error event by making the next assumption and add two more assumptions.
Assumption 7.1. In the Causal Discovery part, we assume that for every g E IS, and g, E CHg. 9i is also in CH² iff 9i is an OR subgoal or all PAge E IS. Moreover, we assume if a subgoal becomes reachable in line 8, it will become controllable after Subgoal Training step in line 10.
g
In this section, we utilize A A*-based search approach in designing a shortest path rank- ing rule. A algorithm finds a weighted shortest path in a graph by using a heuristic function h(g:) to estimate the cost from node Oi to the final subgoal (Hart al., 1968). Additionally, A uses cost function g(gi) that determines the actual cost from the start or the root node to g:. At each iteration, it selects the node with the lowest combined cost f(g)) = E(9:) + h(g;) until it reaches the final subgoal (see Appendix F.2 for details of A algorithm).
Shortest Path Ranking Rule
Assumption 7.2. We assume that the estimated causal effect of a subgoal 9i on the final subgoal In is not zero if g is an ancestor of 9n in G.
Assumption 7.3. We assume that the expected system probes between achieving any two consecutive subgoals in IS, are equal (see the exact statement in E.
Theorem 7.4. Let G(n, b) be tree structure with branch- ing factor b >>> 1, and G(n.,) p) a AymiiErrössRRén gruph < 1 and n > 4. Under Assump- fions 7.1, 7.2, and 7.3, the cost complexities of the HRC, and HRC, are given in Table 1.5
Inspired by A search, at each iteration of Algorithm I, we choose I as the subgoal with the lowest combined cost f(g:), that is, I arg min s.cs_ f(g:)-
where p n-1
elog(n) 0
In Appendix F.7, we explain how to calculate functions and h in our setting. When the subgoal structure is a DAG and every subgoal is of the OR type 4, this rule adds precisely the subgoals that are on the shortest path to the final subgoal to IS and hence incurs a minimum training cost. In Appendix F.9, we also propose Hybrid ranking rule that is combination of the two ranking rules presented here.
Thus, the worst-case cost of targeted strategy HRC,, is sig- nificantly lower than the lower bound the cost of random strategy HRC, In fact, in semi-Erdo Erdrs--éroe- Rényi graphs, the gap widens for sparser subgoal structures.
8. Causal Subgoal Structure Discovery (SSD)
In this section, focus on the Causal Discovery part of Algorithm by proposing new causal discovery algorithm that improves the efficiency of learning the subgoal structure. First, we need the following definitions below:
7. Cost Analysis
In this section, we analyze the cost of Algorithm 1 for a random strategy, denoted by HRC, (baseline), and targeted strategy, denoted by HRC,, which uses any of the ranking rules in Section 6. We consider two subgoal structures: tree graph G(n, b). where b is the branching factor; and a Semi-Erdös-Rénys graph G(n, p). with p = n-1 and 0 < 1 (see definition in Appendix E.3).
Definition 8.1 (One-sided valid assignment). Let X E {0, 13". We say X is a one-sided valid assignment if it satisfies the following conditions for every subgoal indexed by i: (1) For an OR subgoal gi. (X, = 1) - 3g, e
clog(n)
PAg. X, 1; (2) For an AND subgoal gi. (X: = 1) =
Vgj E PAg X, =1. 1.
Recall that subgoal becomes reachable once it is added to the candidate controllable set CCS, which is defined based on 3 (see line 8 of Algorithm 1). If there is an estimation error in the causal discovery part, it is possible that a subgoal gi is not added to CCS despite all its parents being in the intervention set IS for an AND subgoal (resp. at least one of
In general, the algorithm cannot discover all parents of a goal, but only the so-called discoverable parents as defined below.
Definition 8.2 (Discoverable Parent). For any subgoal g:, parent 9j E PAg, is called discoverable if the following
Thhre are some further mild conditions given in Appendix F.1
'All proofs are provided in the Appendix.
7

---

HRL with Targeted Causal Interventions
30300
HRC.
40000
HRC,
HRC.
HRCc
3000
Average
13330
3000
300C
Nodia Size
Node Sice
(a) Erdos-Rényi
semi-Erd8s with
50005
10"
40006
HRC,
10"
HRC,
HRC,
30062
102
Average
16"
107
167
10
Node
Node Stoe
10200
(c) semi-Erdöee ReineErrdd--Réyii with c 1.5
(d) tree with (Y-axis is in log scale)
Figure 5. Training cost in semi-Erdös Rényi and tree graphs.
holds: (1) For an OR subgoal, there exist one-sided valid assignments X, X' {0, 1 such that X, and X O, and Vga. E PAg. Dj: X X O, implying X; changes from 0 to due to Xj; (2) For an AND subgoal, there exist one-sided valid assignments X, X' E 13" such that X, = and x 0, and Vgg E PAg. \ 9) Xx = X = 1, indicating X; becomes only when X, and all other parents are equal to one.
Theorem 8.4. Given the A-SCM defined in (3), for a vector B E R", consider
S(X* = Σ B3X} + 30.
Let - ,B) 0} be an estimate of X
Define the loss function:
((B) = - +|1B1o...
(4)
Proposition 8.3. Under Assumption 4.2, the subgoal struc- ture identifiable up to discoverable parents.
There exists À O such that for any optimal solution 3 minimizing the loss function in (4), the positive coefficients in 3 correspond to the parents of X
In Appendix G.2, give example where all the parents of subgoal cannot be recovered from the interventional data collected in Algorithm 1.
Remark 8.5. In our experiments, for the causal discovery
algorithm, we use the norm instead of the norm the above loss function.
To recover the relationship between subgoals, we model the changes the EVs corresponding to subgoals by an abstracted structural causal model (A-SCM) between the variables in X. This abstraction enables to focus on the relationships between subgoals while skipping intermediate environment variables (Agv \ 1)), operating different time scale compared to the original SCM. In A-SCM, the value of X! x++ is determined as follows:
9. Experimental Results
In this section, we compare our proposed methods with previous work First, we compare our proposed ranking rules with random strategy using synthetic data, Herein, HRC, and HRC, represent the versions of HRC algorithm using the causal effect ranking rule and the shortest path ranking rule, respectively. When HRC algorithm uses the random strategy, it is denoted as baseline or HRC,
x 0
1sisn,
(3)
where
AgJEPA, X5 if gi is AND subgoal, (VaePA,, Xj if gi is OR subgoal,
The cost depicted in Figures 5(a), 5(b), 5(c), and 5(d) repre- sents the training cost of the HRC algorithm, as formulated
(x²)
"I [A} = 1 if A is true, and 1 {A} = 0 otherwise.
and + denotes the XOR operation. Moreover, the error term (+1 is Bernoulli with parameter p < 1/2.
TThe code for all experiments is available https:// gi thub. com sadegh 6/ HRC.
8

---

HRL with Targeted Causal Interventions
HIS (eptroer))))
1.0
1.0
MAC
COMRL
0.8
0.8
Vanilla PPO
Success Ratio
0.6
Success rate
0.6
0.4
0.2
0.2
0.0
0.0
HRC_
(SC_
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
System probes
System protes
(a)
(b)
Figure 6. Comparison of versions of HRC algorithm (ours) with other methods in a complex enviromment of 2D- 2D-Minecraft.
in (11), function of the number of nodes. Specifically, Figures 5()), 5(b), and 5(c) illustrate the costs for semi- Erdōs-Rényi graph ((n. p) for different values of c (see Section 7 for the definition of c). Figure 5(d) illustrates the cost of HRC, for tree Gmn, b) with the branching factor 3. In tree structures, there no difference between using the shortest path versus the causal effect rule, there is only path the final subgoal. In all the cases, the proposed ranking rules outperform the baseline, especially in sparse graphs (See Appendix H for more details).
Table 2. Comparison of SHD for causal discovery methods
METHOD
SHD
MISSING
EXTRA
SSD (OURS) SDI (KE BT AL., 2019)
12.3
6.0
6.3
19.8
4.2
15.6
success ratio, indicating the percentage of trajectories in which the final subgoal was achieved, and the x-axis shows system probes. As can be seen, all versions of our HRC algorithm learn faster than the previous methods. This in- dicates that both our causal discovery method and targeted strategies provide remarkable improvements in achieving the final subgoal (see sensitivity analysis in Appendix H.4).
To evaluate the effectiveness of our proposed methods in a realistic setting, we conducted experiments using a com- plex long-horizon game called 2D-Minecraft (Sohn al., 2018). This environment adaptation of the well-known game Minecraft (Guss al., 2019), where the agent must accomplish various hierar- chical subgoals (such as collecting resources and crafting items) to reach the final objective. Note that in this game the agent receives a positive reward only upon achieving the final subgoal 8, We compared our algorithm with several HRL algorithms, namely CDHRL, HAC, HER, OHRL, and Vanilla PPO. See Appendix H for more details about these algorithms.
simplified two-dimensional
In Figure 6(b) we compare the success ratio two versions of the HRC algorithm which are only different in the causal discovery part. In both versions, we use random strategy. In particular, HRC, (SSD) uses our proposed causal discovery method while HRC, (SDI) uses the one in Ke et al. (2019), which was used in Hu et al. (2022). This figure shows that our proposed causal discovery method is more effective in having faster learning by providing more accurate causal knowledge.
We compare the recovered causal graphs in both methods and show their accuracy in Table 2, measured in terms of SHD (Tsamardinos al., 2006). As can be seen in Table 2, our causal discovery algorithm results in much fewer extra edges, while having a few more missing edges on average.
Figure 6(a) compares three versions of HRC algorithm with previous work. In Figure 6(a), HRC, (SSD) denotes the version of HRC algorithm that uses the causal effect rank- ing rule as the targeted strategy, and the proposed causal discovery method (SSD). HRC, (SSD) represents the ver- sion of HRC algorithm which uses the same causal dis- covery method (SSD) but with random strategy instead. HRC(optimal) denotes the HRC algorithm where both the causal discovery algorithm and the ranking rules operate without error, representing an upper bound on the perfor- mance that cannot surpassed. The y-axis represents the
10. Conclusion
We studied the problem of discovering and utilizing hierar- chical structures among subgoals in HRL. By utilizing causal discovery algorithm, the framework enables targeted interventions that prioritize impactful subgoals for achieving the final goal. Experimental results validate its superiority over existing methods in training cost.
For implementation details, see Section H in the Appendix.

---

HRL with Targeted Causal Interventions
Acknowledgements
Guss, W. H., Houghton, B., Topin, N., Wang, P., Codel, C., Veloso, M., and Salakhutdinov, R. Minerl: A large- scale dataset of minecraft demonstrations, arXiv preprint arXiv: 19X7.v1907.1. 1344, 2019.
This research was supported by the Swiss National Science Foundation through the NCCR Automation program under grant agreement no. 5INF40.180545.
Hart, P. E., Nilsson, N. J., and Raphael, formal basis for the heuristic determination of minimum cost paths. IEEE transactions Systems Science and Cybernetics, 4(2):100-177, 1968.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Heess, N., Wayne, G., Tassa, Y., Lillicrap. T., Riedmiller, M., and Silver, D. Learning and transfer of modulated locomotor controllers, arXiv preprint arXiv: 2016.
References
Hu, X., Zhang, R., Tang. K., Guo, J., Yi, Q., Chen, R., Du, Z., Li, L., Guo, Q., Chen, Y., et al. Causality-driven hi- erarchical structure discovery for reinforcement learning. Advances in Neural Information Processing Systems, 35: 20064-20076, 2022.
Andrychowiez, M., Wolski, F., Ray, A., Schneider, J., Fong, R., Welinder, P., McGrew, B., Tobin, J., Pieter Abbeel, O., and Zaremba, W. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
Bacon, P.-L., Harb, J., and Precup, D. The ortion-critic architecture. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
Icarte, R. T., Klassen, T. Q.. Valenzano, R., and Mcllraith, S. A. Reward machines: Exploiting reward function structure in reinforcement learning. Journal of Artificial Intelligence Research, 73:173-208, 2022.
Barto, A. G. and Mahadevan, S. Recent advances in hier- archical reinforcement learning. Discrete event dynamic systems, 13:341-379, 2003.
Jiang. Z. and Luo, S. Neural logic reinforcement learning. In International conference on machine learning, pp. 3110- 3119. PMLR, 2019.
Corcoll, O. and Vicente, R. Disentangling causal effects for hierarchical reinforeement learning. arXiv preprint arXiv:2010.01351, 2020.
Ke, N. R., Bilaniuk, O., Goyal, A., Bauer, S., Larochelle, H., Schölkopf, B., Mozer, M. C., Pal, C., and Bengio, Y. Learning neural causal models from unknown interven- tions. arXiv preprint arXiv:1910.0107. 2019.
Dietterich, T. G. Hierarchical reinforcement learning with the maxq value function decomposition. Journal of artifi- cial intelligence research, 13:227-303, 2000.
Kimura, D., Ono, M., Chaudhury, S., Kohita, R., Wachi,
Ding, W., Lin, H., Li, B., and Zhao, D. Generalizing goal-conditioned reinforcement learning with variational causal reasoning. Advances in Neural Information Pro- cessing Systems, 35:26532 26548, 2022.
A., Agravante, D. J., Tatsubori, M., Munawar, A., and Gray, A. Neuro-symbolic reinforcement learning with first-order logic. arXiv preprint 10. 2021.
Kulkarni, T. D., Narasimhan, K., Saeedi, A., and Tenen- baum, J. Hierarchical deep reinforcement learning: In- tegrating temporal abstraction and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
Eysenbach, B., Salakhutdinov, R. R., and Levine, S. Search on the replay buffer: Bridging planning and reinforce- ment learning. Advances in neural information process- ing systems, 32, 2019.
Florensa, C., Duan, Y., and Abbeel, P. Stochastic neural networks for hierarchical reinforcement learning. arXiv preprint arXiv:1704 030112, 2017.
Le, H., Jiang, N., Agarwal, A., Dudík, M., Yue, Y., and Daumé IIII H. Hierarchical imitation and reinforcement learning. In International conference on machine learn- ing, pp. 2917-2926. PMLR, 2018
Florensa, C., Held, D., Geng, X., and Abbeel, P. Automatic goal generation for reinforcement learning agents. In International conference machine learning, pp. 1515- 1528. PMLR, 2018
Levy, A., Konidaris, G., Platt, R., and Saenko, K. Learning multi-level hierarchies with hindsight. arXiv preprint 1712v 2017.
Forestier, S., Portelas, R., Mollard, Y., and Oudeyer, P.- Y. Intrinsically motivated goal exploration processes with automatic curriculum learning. Journal of Machine Learning Research, 23(152):1 2022.
Li, M., Zhang. J., and Bareinboim, E. Causally aligned curriculum learning. In The Twelfth International Confer- ence on Learning Representations, 2024.
10

---

HRL with Targeted Causal Interventions
McGovem, A. and Barto, A. G. Automatic discovery of subgoals in reinforcement learning using diverse density. 2001.
Sorg, J. and Singh, S. Linear options. In Proceedings of the 9th International Conference Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pp. 31-38, 2010.
Méndez-Molina, A.
Reinforcement learning and causal discovery: A synergistic integration. 2024.
Stone, P., Sutton, R. S., and Kuhlmann, G. Reinforcement learning for robocup soccer keepaway. Adaptive Behav- ior, 13(3):165-188, 2005.
Méndez-Moline A., Feliciano-Aveling, I., Morales, E. F., and Sucar, L. E. Causal based q-learning. Res. Comput. Sci., 149(3):95-10))) 104, 2020.
Sutton, R. S. Reinforcement learning: An introduction.
Bradford Book, 2018.
Mitzenmacher, M. and Upfal, E. Probability and computing: Randomization and probabilistic techniques algorithms and data analysis. Cambridge university press, 2017.
Sutton, R. S., Precup, D., and Singh, S. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):
Nachum, O., Gu, S., Lee, H., and Levine, S. Near-optimal representation learning for hierarchical reinforcement learning. arXiv preprint arXiv:1810.01255/ 2018: 8a.
181-211, 1999.
Tsamardinos, I., Brown, L. E., and Aliferis, C. F. The max- min hill-climbing bayesian network structure learning algorithm. Machine learning, 65:31-78, 2006.
Nachum, O., Gu, S. Lee, H., and Levine, S. Data-efficient hierarchical reinforcement learning. Advances in neural information processing systems, 31, 2018b.
Vezhnevets, A. S., Osindero, S., Schaul, T., Heess, N., Jader- berg, M., Silver, D., and Kavukcuoglu, K. Feudal net- works for hierarchical reinforcement learning. In Interna- tional conference on machine learning, pp. 3540-3549, PMLR, 2017.
Nguyen, M. H., Le, H., and Venkatesh, S. Variable-agnostic causal exploration for reinforcement learning. In Joint Eu- ropean Conference on Machine Learning and Knowledge Discovery in Databases, pp. 216-232. Springer, 2024.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. Grandmaster level in starcraft using multi-agent reinforcement learning. nature, 575 (7782)350-3544 2019.
Pearl, J. Heuristics:
intelligent search strategies for com- puter problem solving. Addison-Wesley Longman Pub- lishing Co., Inc., 1984.
Peters, J., Janzing, D., and Schölkopf, B. Elements of causal inference: foundations and learning algorithms. The MIT Press, 2017.
Wang, Z., Xiao, X., Xu, Z., Zhu, Y., and Stone, P. Causal dynamics learning for task task- bess-independent state abstraction. arXiv preprint arXiv:2206. /..6....44 13452, 2022.
Pitis, S., Creager, E., and Garg, A. Counterfactual data aug- mentation using locally factored dynamics. Advances in Neural Information Processing Systems, 33:3976-3990, 2020.
Wang, Z., Hu, J., Chuck, C., Chen, S., Martin-Martin, R., Zhang, A., Niekum, S., and Stone, P. Skild: Unsuper- vised skill discovery guided by factor interactions. arXiv preprint arXiv:2410. 18416, 2024.
Schaul, T., Horgan, D., Gregor, K., and Silver, D. Universal value function approximators. In International conference on machine learning, pp. 1312-132.. PMLR, 2015.
Yang, Y., Huang, B., Tu, S., and Xu, L.. Boosting efficiency in task-agnostic exploration through causal knowledge. arXiv preprint arXiv:2407.200 20506. 2024.
Seitzer, M., Schölkopf, B., and Martius, G. Causal influence detection for improving efficiency in reinforcement leam- ing. Advances in Neural Information Processing Systems, 34:22905-22918, 2021.
Yu, Z., Ruan, J., and Xing. D. Explainable reinforce- ment learning via causal world model. arXiv preprint arXiv:2305.02749, 2023.
Zhang, T., Guo, S., Tan, T., Hu, X., and Chen, F. Gen- erating ceaucency--costrrinne subgoals in hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 33:21579 2215900, 2020.
Sigaud, O. and Stulp, F. Policy search in continuous action domains: an overview. Neural Networks, 113:28-40, 2019.
Sohn. S., Oh, J., and Lee, H. Hierarchical reinforcement learning for zero-shot generalization with subtask de- pendencies. Advances in neural information processing systems, 31, 2018.
Zhu, Z.-.., Chen, X.-H., Tian, H.-L., Zhang, K., and Yu, Y. Offline reinforcement learning with causal structured world models. arXiv preprint arXiv:2206.01474, 2022.

---

HRL with Targeted Causal Interventions
A. Additional Related Work
Temporal abstractions and hierarchical policy: In many applications, such as strategy games Vinyals et al. (2019) or robot locomotion Stone al. (2005), poocisioo-maaiing involves operating across different time scales. Temporal abstraction in RL addresses this by considering abstract actions that represent sequences of primitive actions. One way to implement temporal abstraction is through options, where each option defines a policy that the agent follows until a specific termination condition is met. The option framework allows agents to choose between executing primitive action or an option. Further studies have been made to generalize the standard reward function or the value function for this framework (Schaul et al., 2015; Sorg & Singh, 2010). Upon the concept of temporal abstractions, researchers have developed several frameworks to learn hierarchical policies (Dietterich, 2000; Kulkami et al., 2016; Levy et al., 2017; McGovern & Barto, 2001; Nachum et al., 201 (b). A recent work by (Kulkarni et al., 2016) proposed a framework that takes decisions in two levels of hierarchy: a higher-level policy that picks a goal, and a lower-level policy that selects primitive actions to achieve that goal. Despite these advancements, training hierarchical policies remains challenging. as changes in policy at one level of the hierarchy can alter the transition and reward functions at higher levels. This interdependence makes it difficult to learn policies at different levels jointly. Previous work has attempted to solve this issue but they mostly lack generality or require expensive on-policy training (Florensa et al., 2017: Heess et al., 2016; Sigaud & Stulp, 2019; Vezhnevets et al., 2017). To address these challenges, techniques such as Hierarchical Reinforcement Learning with Off-Policy Correction (HIRO) (Nachum et al., 201 20) and Hierarchical Actor-Critic (HAC) (Levy et al., 2017) have been proposed. For instance, HAC accelerates learning by enabling agents to learn multiple levels of policies simultaneously.
Causal reinforcement learning: Recently, many studies have focused on exploiting causal relationships in the environment to address some of the main challenges in RL (Ding et al., 2022; Florensa et al., 2018; Forestier et al., 2022; Li et al., 2024; Méndez-Molina, 2024; Méndez-Molina et al., 2020; Pitis et al., 2020; Seitzer et al., 2021; Wang et al., 2022; Yang et al., 2024; Yu et al., 2023; Zhu et al., 2022). For instance, Seitzer et al. (2021) proposes a mutual information measure to detect the causal influence of an action on the subsequent state, given the current state. This measure can be leveraged to enhance exploration and training. Many model- based RL methods learn a world model that generalizes poorly to unseen states. Wang et al. (2022) aims to address this challenge by learning a causal world model that removes unnecessary dependencies between state variables and the action. Ding et al. (2022) leverage causal reasoning address the challenge of goal-conditioned generalization, where the goal for the training and testing stages will be sampled from different distributions. Recent work Yu et al. (2023) utilized causal discovery to capture the influence of actions on environmental variables and explain the agent's 's decisions. Zhu et al. (2022) shows theoretically that an agent equipped with causal world model outperforms the one with a conventional world model in offline RL.
B. Connections to Related Literature
Skill Discovery: The goal of skill discovery (Wang et al., 2024) is to learn diverse set of skills, which are later used to train a higher-level policy for a downstream task. In that context, a skill is conceptually similar to subgoal in our work. However, there are key methodological differences in subgoal vs. skill discovery: 1- In skill discovery, the process of learning the skill set is often decoupled from the downstream task. In contrast, our work-framed within the context of HRL-conditions the learning process on a target goal. By leveraging the learned subgoal structure, our approach guides exploration toward only the relevant subgoals that contribute to achieving the target goal. In contrast, skill discovery methods often aim to learn as many diverse skills as possible, regardless of their relevance to the target goal in the downstream task. 2- In our framework. the lower-level policy is itself hierarchical and is trained according to defined hierarchical structure (where defined it formally based on the discovered subgoal structure). This results in a significant reduction in sample complexity compared to standard policy training, which typically does not utilize such a structure. Beyond these methodological distinctions in subgoal discovery and training policies, to the best of our knowledge, our work is the first to rigorously study HRL within a causal framework. We formally defined the cost formulation, proposed subgoal discovery strategies (with our key Definition ECE 3.4) with performance guarantees (Theorem 7.4), and provided theoretical bounds on the extent to which the subgoal structure can be learned in an HRL setting (Prop. 8.3). Furthermore, we introduce causal discovery algorithm tailored to this setting, with provable guarantees on its correctness (Theorem 8.4).
Inductive Logic Programming (ILP): RL has also been studied in other areas. Inductive Logic Programming (ILP)-based methods (Jiang& & Luo, 2019; Kimura et al., 2021) represent policies as logical rules to enhance interpretability. Our work considers a multi-level policy, with a focus on recovering the hierarchy among subgoals (with our explicit hierarchical structure definition) for training the multi-level policy more efficiently. Herein, we do not impose any structural limitations
12

---

HRL with Targeted Causal Interventions
on our policy. For our theoretical analysis, we assumed that the causal mechanism of each subgoal follows AND/OR structure. This assumption pertains to the environment rather than for representing the policy using logical rules.
Reward Machines: Reward machine (Icarte et al., 2022) can be viewed as an alternative way to represent hierarchical structures in HRL and can be effectively used for training policies.
C. Additional Preliminaries and Definitions
We model the HRL problem of our interest through subgoal-based Markov decision process. The subgoal-based MDP is formalized tuple (S, $ A. T, 7,), where S is the set of all possible states (in setup, all possible values of g 4 is the subgoal space, which contains intermediary objectives that guide the learning of the policy, A is the set of actions available to the agent, T" S x A x S - [0, 1] is the transition probability function that denotes the probability of the transition from state to state s' after taking an action a and R S x A x Φb + R is the reward indicator function of the agent pertaining to whether a subgoal was achieved in state s after taking action a. More specifically, R(s, s, a, 9) if the subgoal g is achieved, otherwise is zero. ? is the discount factor that quantifies the diminishing value of future rewards. Given state E S and subgoal g 4, the objective in subgoal-basee MDP learn a subgoal-based policy क (als,g)
4 A that maximizes value function defined V (s(ss g) EE, IEt= 7 R(st, ats (t.g) 80 - 8).
C.1. Introductory Example
For the example provided in Section based on Definition 3.2, we present two hierarchical structures of the subgoal structure in Figure 2 in the following.
(a) ((S) = L(W) 0, C(P)= =1
(b) C(S) = 1(W) = C(P) = =2
Figure 7. Two hierarchical structures of subgoal structure given in Figure 2. S, W, P denote stone, wood, and pickaxe, respectively.
In Figure 7, S, W. and P denote stone, wood, and pickaxe, respectively. Figure 7a represents hierarchical structure
H. = (xH, L) where A graph is the same as the real subgoal structure I and level of S and W are zero and the level of P is
1. Figure 7b shows another H = (H, L) where H is not an exact estimate of S.. The level of W is zero, S is I and P is 2.
C.2. More Definitions
Definition C.1 (Structural Causal Model (SCM)(Peters et al., 2017)). A Structural Causal Model is defined as tuple
M = (U, V, F, P(U)), where:
U is a of exogenous variables whose values are determined by factors outside the model.
V is a set of endogenous variables whose values are determined by variables within the model.
F is a set of structural functions } one for each v e V. such that v = fo (pa(v). u.), where pa(v) S V {f} is
the set of parents of v and u, is the exogenous variable affecting v.
P(U)) is a probability distribution over the exogenous variables U which are required to be jointly independent.
D. HRC Algorithm
D.1. Intevention Sampling
Algorithm 2 collects interventional data D, for the subgoals in IS in T trajectories. During each trajectory, it randomly
intervenes on the subgoals in IS until the horizon H is reached or all the subgoals in IS are achieved. In line 1, it initializes an empty dataset to store the interventional data. Then at each iteration in the "For" loop, it records a trajectory Tj. The "While" loop in line 4 iterates until the horizon H is reached or all the subgoals in IS are achieved. In line 5, it randomly selects not already achieved subgoal 9: from the set IS and in line 6 it performs intervention on it. This intervention can be accomplished by taking actions based on the subgoal- based policy π (a 8, 9:) until the subgoal gi achieved some
13

---

HRL with Targeted Causal Interventions
time 1* (see Remark 4.3) or predefined maz_sleps (the maximum number of steps that the policy interacts with the environment) is reached. Since all the subgoals in set IS are already controllable, with high probability, the subgoal 9i will be achieved. Next, in line 7, we append all the observed state-action pairs the Tj (along with explorational data if gi is achieved).
Algorithm 2 Intervention Sampling
Require: Subgoal-based policy म, set of subgoals IS, number of trajectories T, maximum horizon H
Ensure: Collected interventional data D,
1: D₁ t O (Initialize empty interventional dataset)
2: for =1 to to do
3: Initialize empty trajectory = (
4: while (len(T;) < H) or (there exists an unachieved subgoal in IS) do
5: In IS, randomly select subgoal that is not already achieved, denoted as 9t-
6: Perform intervention on 9i (This can be accomplished by taking actions based the subgoal-based policy
Ta s, 9;) until the subgoal 9, is achieved some time t* 4.3}
7: Add the observed state-action pairs and explorational data (Dooxx;==1) (if any) to Tj
8: end while
9: Append trajectory to Dj: D1 t D1
10:
end for
return D
D.2. How to use hierarchical structure and policy?
The hierarchical structure H determines which subgoals need to be achieved before achieving specific subgoal g.. These prerequisite subgoals are the ancestors gs. and they must be achieved by following a valid causal order. This causal order can be obtained using Algorithm 3, which identifies the ancestors of g: and then sorts them by their level in the hierarchical structure. However, multiple valid causal orderings may exist, and it is the policy's role to choose proper order in a given state. This policy can be modeled as multi-level policy, which is defined in the following subsection.
Algorithm 3 Find Causal Order of Ancestors
Require: Hierarchical structure = (HH44 L). node 9i
Ensure: List of ancestors of 9: sorted by causal order
1: Initialize empty list A [ [List of ancestors)
2: Initialize stack S + [9.] (DFS stack to traverse ancestors)
3: while S is not empty do
4: f pop element from stack 5
5: if gj is not already in then
6: Add 9j to A
7: Push all parents of gj from H into S
8: end if
9: end while
10: Sort A by increasing L(g,) for all gj E A
11: return A [List of ancestors in causal order)
D.3. Multi-level Policy
A multi-level policy Fy is collection of le policies: ny { -i,..., Tk-1), where n; is the policy at level i. The lowest-level policy is mo (ola,, (,l,,,, 9) S x + - A which returns a primitive action given the current state and some subgoal g. Moreover, a policy n, (gg g) S +- + t at a higher level (1 < < k), returns subgoal g given the current state and conditioned subgoal. Please note that the level of a policy is different than the level of subgoal in the hierarchical structure (Refer to Definition 3.2 for the definition of levels of subgoals in a hierarchical structure).
Algorithm gives a pseudo-code of executing the lueei-levyyyolicy recursively for given state E S and subgoal g E
14

---

HRL with Targeted Causal Interventions
The input the multi-level policy is tuple of state, conditioned subgoal, and the recovered hierarchical structure H. Initially, in line 2, the algorithm determines the level of the subgoal (denoted by i) in the hierarchical structure, L(g). In line 3, it identifies the parents of this subgoal in the recovered subgoal structure and stores them in the action_mask. The output of policy is forced to be taken from the subgoals in action_mask in line 5. The maximum number of actions that the policy at each level is allowed to take is equal to mor marractioos. the subgoal is a root in the subgoal structure (i.e., > 0), the action и; is a subgoal, and the algorithm recursively calls the EXECUTE_T,, function for this subgoal (line 7). Otherwise, subgoal is root, and the agent takes the primitive actions directly the environment (line 9). After taking each action, the algorithm checks whether the goal has been achieved or if the trajectory terminated. either condition is met, the loop terminated, and the algorithm returns the new state to the upper level of the multi-level policy.
Algorithm 4 Executing Hierarchical Policy
Require: state s, subgoal 9, hierarchical structure H.
1: Function EXECUTE_TA (s, g. H):
2: < level of the g in the hierarchical structure
3: action_mask - parents of the g from hierarchical structure
4: for each step in max maa__actions do
5: Select action based the action_mask: a <=(aa 8,9)
6: if > 0 then
7: next-ssale done, goal _uchieved <- EXECUTE (s a, H)
8: else
9: Execute action in environment: nextlstale, reward, done + env.step(a)
end if
goaleecheeved Check if goal achieved
12:
+ nezt_state
13:
if done or y is achieved then
14: break
15:
end if
16:
end for
17:
return next state, done, goal achieved
D.4. Subgoal Training
In Algorithm 5, in line 1, we first determine the maximum level of the reachable subgoals from the set CCS. If the level number of these subgoals exceeds the current number of levels, k, in the multi-level policy Th, we add new level to тa- For each reachable subgoal 9; in the set CCS, we collect 7" trajectories. In each trajectory т, we iteratively generate a random number between 0 and I and randomly pick a subgoal in the set IS if the chosen number less than Otherwise, we select 9: for intervention. This ensures that the policy learns how to achieve Ji not only from the initial state but also after having some interventions. In practice, set p = 0.1. Note that if the final subgoal belongs to the reachable CCS, only train the final subgoal 9n- Additionally, for each subgoal g. define parameter called the success ratio, which measures the proportion of times the subgoal g is successfully achieved after interventions on it during Algorithm 5. We consider the subgoals that have a success ratio greater than threshold @casaal as controllable.
E. Subgoal Discovery
E.1. Cost formulation proof
We start by formulating the cost each iteration
T
T Σ
To iin.g'
+
wosp)
+
Σ
W int.g"
+ 2 T5
"rainng"
(5)
9
EI;
EcCS, j=1 Is
InterventionSaanping
SubguulTTraiiigg
15

---

HRL with Targeted Causal Interventions
Algorithm 5 Subgoal Training with Probabilistic Subgoal Selection
Require: subgoal-based policy my with &: levels, hierarchical structure H. intervention set IS, reachable subgoals in CCS,
verification threshold Ocansal
1: if final subgoal In belongs to the reachable set CCS then
2: Train only on the final subgoal On : CCS <- {gn}
3: end if
4: Add a new level to Ty if maxx C(g.) >
5: for 9: in CCS do
6: for
7" do 7: Initialize empty trajectory Tj {}}
8: while len(T,) < H or subgoal 9; is not achieved do Select 7 randomly from [0, 1]
9:
10:
if r S p then
11:
In IS, randomly select a not already achieved subgoal (denoted as gj)
else
13:
Set 03 = 9: end if
14:
15:
Call EXECUTE.TA(Slate Uj. H)
16:
Add the observed state-action pairs to Ty
17:
end while
18:
Append trajectory T, to Dv: Du + Du UT
19:
end for
Train Th using Du
21: end for
where T and T' are the number of trajectories collected in Intervention Samping and Subgoal Training steps at iteration t, respectively. Furthermore, Tj represents trajectory and - g' Wedp- and w " ""min.g" represent system probes corresponding to the different steps of the algorithm in trajectory Ty. which are further explained below. In Intervention Sampling (Algorithm 2), in each trajectory Tj. randomly select a subgoal 9i E IS, and perform an intervention on it. After each intervention, explorational data is gathered as specified in Definition 3.3. A trajectory is terminated when all subgoals in IS, have been achieved or when the horizon is reached. Note that, during an intervention on randomly chosen subgoal Jr. it may be necessary to first achieve other subgoals g' E IS, Therefore, for each Tj. we consider the system probes obtained toward achieving each subgoal g' E IS, regardless of whether it was selected as the intervention subgoal (g:) or not. We denote this cost by w. whi and is equal to the system probes between achieving two consecutive subgoals, with g', being the second one. Additionally, we need to consider collected explorational data during the trajectory T, to explore the environment and discover reachable subgoals. The number of system probes for exploration in trajectory Tj is denoted by waáp.
In Subgoal Training, for each reachable subgoal in CCS,, which is denoted by g". we gather T" trajectories to train the policy for achieving it. For each trajectory Ty, similar to the reasoning above, we consider the system probes obtained toward achieving each subgoal in IS, Note that "irain.g" represents the portion of system probes towards achieving the subgoal g", during the intervention on g" by taking actions based on the subgoal-basee policy x(a s, s,g").
As we mentioned in section we define recursive formula denoted by Cg,, (I) that represents the expected cost of achieving the final subgoal In when the set I is intervened on:
Cg. (I)
Σ PI. Cirano {gbal)) + Ogn UIU {owll)
(6)
Bhat
where it has two terms: 1-the transition cost and 2-the cost-to-go. Specifically, the transition cost CI, J (ghel) is the cost of transition from the current interventions set I to new set by adding Jsel to it (I U (gwa)) The cost-to-go Cp.. (I U (0wl) shows the future costs from the new state onwards. Both components are weighted by the transition probability Pr, which shows the probability of transition from state I to I U {g which is determined by the strategy. Ctrans (I, I (9val) is indeed the expected of the cost formulated (5):
16

---

HRL with Targeted Causal Interventions
E
Σ
Σ
Ty Weep
+ + Σ
Σ
T3 Wint,g
w uaangn""
I, 9scl
n'EZU(aa)
("EN(IU(Oa)) j=1
g'EZU(ma
where (II (fee)) contains reachable subgoals having interventions on the subgoals in the set I (gsel) This set equal CCS, in Algorithm 1. We assume E be simplified to:
Elwim.g/ E [
E E[w (r = w. Therefore, Ctrans (Z, I (geel) will
T(I + 2 +
Σ g" (2
T( + 2)vc.
(8)
Equation (6) can be represented in matrix form:
Cgn (P Ciran)) + PC 'n.
(9)
where Cg., is 2 column vector, P and Cirans are 2n x 2n matrices, and is column vector of ones.
We define R (P 1 where R is 2" column vector:
RI,
RT.
Rige
the elements of which are defined by:
Σ
PI, [(Lan)
T(ZII + 2)w +
Σ
T(II 2)w
$ Iz
RI,-
(10)
gaEDiI
('EN(I,U(Bal)
0,
In EI
If we expand (9):
Cg. = R. + PC 8n
R P(R PCg.) = R PR P'C
which further expands to (T+ P + ........ R. Since P²R = 0 for 2 n, we can truncate the series at Pn-1 R. This truncation is justified because, beyond this point, all subgoals have been added to the set I, including Ins and the algorithm terminates and results no additional transition costs. Therefore,
C
II+P+N p2 +
))-
0
912
(1)
913
(1)
0
412
(n-1)
413
(n-1)
RI. RI.
0
0
0
923
0
423
(n 1)
0
0
+
0
0
0
+
0
0
Ri
4i The expected cost of training is equal to the first entry in Cz.,. where we start from primitive actions and I (}. Therefore.
Lij denote the ij-th entry of the k-tth power of the transition probability matrix P. In other words, (Pk)
)aj
Cg. HM RI,
(1) RI, + Σ RI, Σ0
RI,
Σ
(3) 91
R1,
Σ (n-1)
9
RI,
(11)
Remark E. The condition PA C IS, in line of Algorithm 1, added because we assume that for a given gi E CH all of its recovered parents (i.e., PA%.). ) are needed to be achieved before achieving 9s. Hence, this condition ensures that all of them are in set IS, However, under Assumption 7.1, we can remove this condition, as all necessary parents of g, E CH (i.e., for AND subgoal all of its parents in @ and for OR subgoal least one of its parents in ( are already in IS,
gi
17

---

HRL with Targeted Causal Interventions
E.2. Analysis for the Tree
In this section, we analyze the cost associated with subgoal structure modeled tree G(n, b), where represents the number of nodes and b the branching factor. First rewrite equation (10):
Σ
PT, TT,
T( + 2) +
Σ
T((I)++2))
In $ I
RI,
g ((E((I)
0,
On E
In the tree structure, each subgoal has only one parent and only becomes reachable by that. Hence:
[ { E0 PI, Pll [T(ZZ) + 2)w + ([z)+ 2)w], In $ Ij-
RI,
0.
In E Iz.
Note that Σ E
1. Therefore,
([Z)I+2) + 2) + + DT") In $ Ij. 0,
RI,
In Iz.
We assume that the final subgoal is positioned at the depth D. Consequently, Algorithm is expected to perform at most D & (1) interventions before termination, where n is the total number of nodes and is the branching factor.
In the (11), RI, is zero if gn. EI, This implies that for any k the term o RT, should not be included in the cost calculation if In is in Zy. Additionally, of, represents the probability of transition from the initial subgoal to the subset I, where |z,l = k. Please note that the values of Rz, are the same for each term in the expression E3 11 RI, for every j where On E I as [Iy] = Thus:
Σ dig RT, =
Σ
Pig
(R) RT,
+
Σ
RT. 9ij
(k)
(12)
where gn EZ;
where EITy
= (Ie + (T + bT")
Σ
Pi
(k)
Q (k + 2) + DT"),
(13)
j where Iu $I,
(e) is the probability of reaching a state such as Z, where [Z,| = k and In & I, after where 2 = En where øI, 915 transitions from the initial state (} in M (we call this sequence of transitions in M as a path). Note that for k < D, Q(i since the final subgoal cannot be intervened before all of its ancestors have been intervened.
Now, for k > D, we derive the probability that the final subgoal is in such as Ij where |Z,l k. In tree structure, each node has only parent and children. Thus, after adding each node to the intervention set, all of its children become controllable. Let f() represent the number of controllable subgoals having intervened on h subgoals in the tree. It can be easily shown that:
f(h) = hb h + 1- h(b 1) + 1,
as hb is the total number of controllable subgoals after intervening on h subgoals, h accounts for the subgoals that have already been added to the intervention set, and +1 represents the root subgoal.
In order to calculate O(A), since ( 1 ( first upper bound on O(*h We know that there is only one path in the subgoal structure that leads from the root to the final subgoal. To add the final subgoal to the intervention set, we must select exactly one controllable node from the controllable set, at each iteration. The probability of making the correct
selection is 7 On the other hand, for A: > D, the final subgoal might be added to the intervention set in any position (iteration). Hence, the probability that the final subgoal is in set I, where [I, k is follows:
k d
d
Σ
II
(14)
f(h)
d= D Am
18

---

HRL with Targeted Causal Interventions
Note that the outer sum in the (14), is because Ih プ:y is the probability that the final subgoal is added set Z, at last (iteration d). Therefore, the sum considers all possible positions(iterations)) where the final goal can be added to I, (from D to k). Based on this, we show that there exist constant where 2 (1 2 2 a 0 for 2 D:
2
Σ
(15)
h(b +1
h(b 1)
D=
k=1
d=
1
Σ
(16)
d!(b - 1)d
D=
(17)
d!
D=D
(6)
1
(18)
2(d-1)
d=D
(19)
20-1
2k-D4I D4I
2
(20)
20-1
(a) (6-1)²21 1. Because for any d 1: d! S 26-1
(c) Sum of geometric series with a first term g and ratio 2'
Therefore for k 2 D.
(k)
(1 0 (1
2
(21)
NG
20-1
Now, we calculate the total cost using the (11):
Cg. [0] = RI, + Σ di RI, +...+
Ea b 10
RI,
+
Σ
(D) (D)R,, hi
RI, + Σ oi RI,
(22)
"paths M final subgoul cannot he reached"
"paths A final subgoal can reached"
D-1
=
2T + bT") +
Σ
Q Ald (k 2T + bTT)+
+
bT")
(23)
k=1
"paths in A where the final subgoal cannot reached"
"paths in M where the final subgral can he reached
D-1
n-1
(T + bT) +
Σ 2) bT") + k=1
Σ a(k + (T + DT")
(24)
"paths in A where the final subgoal cannot be reached"
"paths in M where the final subgoal can be reached"
n-1
2 (w + +8T) +
Σ a(k + (T
(25)
a n(n + 3) (T)
= 2
(26)
where in (a), we used (21). Therefore for HRC,, the complexity is Q(n?t), while for the targeted strategies in Section 6, the sum ends on k < D < (n) since they add only the ancestors of the final subgoal to the intervention set in the worst-case scenario (based on Assumption 7.2). Therefore, the complexity of our targeted strategies is O (l))).m)bb.
19

---

HRL with Targeted Causal Interventions
E.3. Analysis for Random Graph
In this section, we analyze the cost of training in subgoal structures modeled by random graph which we call semi- Erdös Erdös-Rényi graph. In particular, semi-Erdoe Rényi the directed edge set E. Each node i V. corresponds with subgoal 9r. The edges in the graph are generated follows: For each node i E (1,2....p with probability p, where is the edge probability. Formally, for each pair of nodes (i,j) such that i <
Rényi G(n, p) is directed graph with the vertex set V = ... n) and
1}. iterate over each node such that i < j and add directed edge from node to node j
Pr((i.j) E =
where the existence of an edge (i.5) in E is determined independently from other edges. our analysis, we consider clog(n) where is positive constant > 0.
n-1
Lower bound for semi-Erdós-Rényi G(n,p) p) for HRC, algorithm
From (11), the total expected of cost is:
B[Cmn. (.n
RTi
+
E
Pi
RT.
Σ
RT.
... + E
Σ
(n-
RT.
(27)
Based on the definition of Rz,, we know:
0
(R) Σ
RI,
Σ
9ia
(b)
RI,
Σ
4r RI
(k)
(28)
j where HI,
wheee In EI₃
Hence, we can rewrite (27) as follows:
C HO
=
RI.
Σ
(k) 91
RI,
=
E
RI,
91
RI,
(29)
where gn IT,
k= j where o
We drive a lower bound for RI, for j that In & Zy. Note that since we are looking for the lower bound for the cost, we consider particular subgoal structures where subgoals are all of "OR" type:
RI,
Σ
PT,T,,Laa))
wT([I,1+ +
Σ
wT + -2)
(30)
I))
("EN(Z,U(am))
Σ
PI,Iz,(
WT([I +2)
(31)
In)(()I,))
w +2)
(32)
where the last equality is because the sum of the probabilities should equal 1.
Now for each A:
Σ
E
Ti
(k)
RT,
where Dee TTy
Σ
Elgis
(k)
2)
where gm II,
wT (k: 2)
(33)
where on ZTy
20

---

HRL with Targeted Causal Interventions
which means that we only need to compute Ej where gn, E Bio which the sum of the expected probability of the paths (in MDP M) that start from the state { and reach to a state 2, that does not include the final subgoal after & transitions (In $ I and Izy = k). We know that,
(8)
(4) Big
Σ
Elgiy
(R)
1.
(34)
where ow ET3
where 9h, E
Now consider each I, where In. $ I and Σyl
k. We can create new set Ij, by replacing 9, Iy with In (see Figure 8). Let us denote this new set with Zy. (the index of this new set is denoted by j:).
1
2
3
n
1
2
3
n
Figure 8. Left: The gray nodes represent elements of the set with size k. where subgoal go & Iz. Right: A transformation of the Ij to a new set Zj., where one element (in this case, node = 3) in Zy is replaced by gn. as shown by the gray node gn on the right.
Based on Lemma E.3 have Eig Eigna Blgi Summing all of these inequalities gives:
(k)
Hence, for each such I, there exist k number of Zj.S, where Elg =
(k) E Eluig < kB[41
(R)
(35)
9:E2,
Note that each Ij, be created from (n k-) different Iys. Hence, summing all the inequalities from 35 for different js, (k)] (or the corresponding |l(u))) each Bldiy]]
[k)] where Ij ) will be counted (n - k) times:
(n k)
Σ
E Blyi
S k
Σ
Elgij
E
(k)
(36)
where EZ,
where on $I,
By adding Ej where on EI,
Elgig to the both sides and rearranging the terms:
(K))
Elghy
k El
(K)
Elqis
(1)
(37)
K
where gn, ETT
on HZ,
Therefore,
Σ
Elgiy
(K)
Σ
(K) Eluig!
<
Elyi,
(A6)
k
Σ
Eluly
(8)
(38)
K
j where Sh
where EI,
where ove TTy
where an TTy
The left-hand side is and the right hand side is
n Ej where gmn I
E Elqi
(1:)
hence:
1
Σ
Blai
(k)) J-
(39)
ni
where In IT,
Thus,
Σ
E
E
(k)
k
(40)
n
where gu II,
Now we compute the total cost using (29) as follows:
21

---

HRL with Targeted Causal Interventions
B Cg. [0]
=R [B(
Rz.
B
Pii
(k)
RI,
k= j where Ii I.Iyg
(0) TwT + weT log(n) +
IMi IMM
PIIM
wT + +2 x
Σ
Bluig
(40)
where on T.y
(0)
2 2wT + weT' log(n)
wf(k +2) -
k=1
wT n(n 1)(3n + +5)
2wT + weT" log(n) +
(a) We used inequality in 33 in the third term.
(b) We used inequality in 40 in the third term.
Therefore, the complexity of HRC, algorithm is S((2).. In following, we analyze the complexity of our suggested targeted strategies for this type of random graph.
Upper bound for semi-Erdos- G(n, p) where = clog(n) for HRC, Due to the assumptions made in Section (n-1)
our ranking rules in Section 6 intervene on all ancestors the final subgoal in the worst-case scenario. Hence, we first
obtain an upper bound on the expected number of nodes that are ancestors of the final subgoal.
For given node we define the event A, as the probability that is the ancestor of node n. The probability of A, is as follows:
P(A.) P(i connected to n) + P(i not connected to n) P
U j=++1
(j a child of i) n nA))
(41)
(n)
(c)
sp+ (1-p)
Σ
x P(Aj)
(42)
i=
(d)
n-
= =p + p)
P(A,),
(43)
j=1+1
where (a), represents the probability that node is directly connected node (which is p), and (b) is the probability that node is not connected node n (which is - p). If i directly connected n, it must be connected to at least one node (j > i + 1) that is itself an ancestor of This probability is represented in (c) and upper-bounded by union bound in term (d). We define 9: = Σド= P(A,). The goal to find an upper bound on Q1 ΣE P(A,) which is an upper bound of the expected number of ancestors of Therefore, we can rewrite the above equation in recurrence form follows:
qs 9++ Sp+ (1-p))001
(44)
Let p- p² + 1. The recurrence then becomes:
9i S p + aqb+1
To solve the recurrence, let begin with For this case, we have:
22

---

HRL with Targeted Causal Interventions
9n-1
Σ
P(A))
P(An-1)
j=-
where the last equality holds because node n - 1 an ancestor node n if and only if is the direct child of n In general, for any dz i S n 1, we can derive:
4:
S
a
km0
To find 9t, we sum the series from to k
2:
a1 S a
Finally, substitute p²
and p
clogn into the above equation:
n-1
clogn 1--1
clog n--
+
clog n-1
7-1
clog n
n-
Φ1
S
(45)
log it
c clog n
clog n
where the last two inequalities because the terms bounded as follows:
cllog n-1
and -1 are negative, The term
<llggn n-1
+ +1) n-
upper
clog + 1
n-1
< c logn = n
1
Substituting back into the (45):
n1
91 5
clog n-
For n > 4, c < 1, we have: clogn
2. Hence:
n-1
Q 2n
As we mentioned earlier, QI the upper bound on the expected number of the nodes that are ancestors of the node n. Hence:
E|ANC, (G)) & Σ P(A,) q1 S 2n
(46)
where G' is the generated random graph and ANC,, (G) represents the number of ancestors of the node in the graph G.
The total cost is then computed as the expected sum of the transition costs:
ANC, (G)
E
E
T(k 2)w No (k: + 2)w
G
(47)
A=
23

---

HRL with Targeted Causal Interventions
where the inner expectation is because of the orders of adding ancestors the interventions. Let NY represent the set of reachable subgoals when the k-th ancestor is added to the intervention We define N(G) the maximum degree of the graph G. Hence, for every k. Ng S (G). With further simplification:
(G)
ANC,, (G)
E
E
Σ
T(k+ 2) + No x ( + 2)
S E
Σ
[Tk N(G)T ( 2)
(48)
We can partition the last expectation into two terms:
(N),.G)
ANC..())
ANC.
E
T(k 2)w 2 (KG) NKG)) + 2)wl
E
Σ
T(k: + 2)w
+E N(G)
Σ
T' + 2)w
(49)
k=1
k=
We now analyze the second term the dominant term. We partition it into two expectations based on the following
24

---

HRL with Targeted Causal Interventions
event N(G) (1 + 8) log())))
(G)
E
N()
(k + 2)w
(50)
(G)
=E
((G)
Σ
(kk + 2)w [NCC)c(400)))))()))
km
ANC..G)
+E
(N())
Σ
T 2)w0 IN(G)2(44000000))))
(51)
(G)..
(a)
(1 + ()clog(n)
T" + 2)w) (N(C)
(G)
+ nB
Σ
T'k 2)w
(N(G)2((00)))bg())
(52)
(NC.,(G)
(1 + d)clog(n)E
(Σ
Σ
T'(k
+ + 2)w)
(G)..G)
+ nE
Σ
T'KK+ + 2)w 1 ((C)2((400)))
(53)
k=1
T'(k AGC..G)
(c)
(1 + d)clog(n)B
T + 2)w)
ANC, (G)
P ((NGG) 2 (1+ + log(())
+ nE
Σ k=1
( + 2)
N(G) 2 (1 5) log(m))
(54)
(G)
(d)
wI' (1+ + log(n)E
Σ
(k: + 2)
ANC.(G)
+ nK
Σ
(k+2)
N(G) 2 (1 (1+ 5)c log(n)) P (NNGG) 2 2 ++))loog())
(55)
ANC., (G) Σ
(e)
( (1 6))elog(n)
(k + 2)
+ "TT' m n² + 5n
P N(G) 2 (1 (1+b) 8)clog(n)
(56)
2
(a) We move the max of (G)) outside of the expectations.
(b) Because LANC. (k [k + 2) [N(C) S E (NC T' + +2) )
(c) Expanding the second expectation based on the law of total expectation.
Moving constants out of the expectations.
Replacing ANC,(G) (G) with its max value (n) and computing the expectation.
Now we should compute an upper bound on E EANC
ANC. (k + 2)] and P (N(G) 2 (1 ((+))coo(nn) ).
First, we obtain an
upper bound on the term E
(G)..(G) A=
(k +) 2)
25

---

HRL with Targeted Causal Interventions
ANC, (G)
ANC (G) + 5ANC.
BJANC (G)
E
Σ
(k+ 2)
E
2
2
We derived an upper bound on [A (G)) in (46). Hence we only need to find an upper bound on [[)]
E
(G)
ANC ANC.(G) 2 MEJANC.. P ANC...G) ABJANC..CG)
+ (G) ANC.(G) ABJANC..
P (ANC.(G) < <MEIANG,
E
(G) (N). 2 ME|ANC, (G)]
h
+ E
ANC, (G). < AB]ANC,,
n ("]
h
n22
$ 22
(a) Using Markov's inequality (G) KEJANC, 3
(b) For each expectation replace (GC with its maximum value and take it outside the expectation.
The critical point for n² %/ n is h = 11 2-
1/3
By substituting this into the above inequality we obtain:
n²
2
2/3
E[ANC
+
4
11 2c
1/3
n2
Thus, E (O + 2)] can upper bounded by:
ANC, (G)
LIANC (G)] 5
E
Σ
(kc 2)
+ B[ANC,, (G)]
2
k=1
z mn++3
+3+ + 5m
(57)
Now, we only need find the upper bound on the probability P [ 2 (1+5)clog(n) in the (56). obtain an upper bound, we analyze the case in which each node i can have edges to all other nodes. Let Dj denote the out-degree of node i. Therefore, each D, follows Binomial nn 1,p) with expected value:
#4 E[D.] = 1)p clog(n).
Using Chernoff bound in Lemma E.2:
p D, 2 (1+ c)gg(g)))
( 8ec (oolog(n)
= exp (- [8'clog(n)
sexp
< exp
2 + 8
2 +
2+5
26

---

HRL with Targeted Causal Interventions
The event that the maximum out-degree exceeds (1 8)c log(n) is:
[N(G) 2 (1 6)clog(n)) = U [D, (1 8)clog(n))
Thus using union bound:
P N(G) 2 (1 8)clog()) = UtD 2 2 (1+) -
Σ 1=1
P D 2 (1 (L+)clog(m)
n
(58)
22
==1
We substitute equations (57) and (58) into equation (56):
3 (1 + 6))log(()
n² +5 )
2 n nn 5n
+ wT'n(
N(G) 2 (1 d)clog(n)
(59)
3 n + 5n + wT'n
[n + 5m
$ wT (1 5))cllgo)))
(60)
2
For any 0 < c < 1, the first term in the above equation above is of order n $e log(n) and remains less than n². For the second term, the exponent of is 4 2+8 which we desire to be less than 4 + 3e. For this purpose, should satisfy the following equation:
6²
82
2c
C
+
2+0
8
3 3
which holds when
8 2c +
2 + 160c + 64
2
6c
Note that for < < 1, the expression under the square root, -4c² + 160c + 64, is positive. This ensures that å has real solutions. Consequently, the dominant term in the above equation will be + Therefore, the complexity of our ranking rules will (n + log(n)).
E.4. Auxiliary Lemma
Lemma E.2 (Chernoff Bound, see (Mitzenmacher & Upfal, 2017)). Let X x Ei= be the sum of n independent Bernoulli random variables, where each X, takes value with probability and O otherwise. Ler μ = E = np. Then, for any 8 > 0,
21+ s exp (- 5211
(-2+3)
Lemma E.3. Under the setting outlined in Section E.1 and E.3, let G(n, p) be semi-EErös-Réng graph where p = clog(n) and 0 < c 1. For each I where 9n. & I, and I k, we create new set I, by replacing 9: E I, with In (see Figure 8). Let us denote this new set with Lz, Then:
n-
E((1)) (8)
(k) Proof. We define Isco as new set by replacing 9i E I, with the node 9.-1. If 9:+1 E Iy, Elg = Elg Otherwise, prove that
E E[g S E[g (10
(8)
(61)
27

---

HRL with Targeted Causal Interventions
Let denote the that the edge (i, i + 1) exists in the graph (i.e., there is an edge from 9: to 9t+1), which oceurs with probability p. and let me denote the event that it does not exist, which occurs with probability 1 p. Then, can write:
(k) 1900
= (1 - p) x B
11900 --
+ + x
P1300
(k)
For the first term, under the event me from the perspective of other nodes, Ii and gi+1 are the same. Therefore:
(k)
(R)
E
E
41
-
(62)
For the second term, under the event e, we consider additional events. Let e be the event that there at least one edge from the set I, {gi} to gis and ei+1 be the event that there is at least one edge from the set Zz {gi gi+1- Moreover, consider that k' = -Kgrlg+ E I and r < i]}-
We can partition E
(k) into four cases based on e, and e,+1
Using the law of total expectation, rewrite E
(1900 |el
(k)
as follows:
E
(k) 1130
le
= P( P(-ei+1; 6z) x E
(k)
+ P(el+1, -e;) x (izte)
(k)
E, e,+1 76p
+ P(-e:+1, -e;) ) x E Pijs
(k)
e, Eit11 76
+ P(e++1,e;) x E
(1300
(k)
e, (..41.cc) e.]
(63)
For each of the above cases, we show that the expectation is less than or equal to the corresponding expectation for Iz. Case I: e, occurs and 1 does not occur. In this case, there is at least one edge from Ií \ { to gi. but there are no edges
from I \ {g.} to 9i+1- In this case, P(-e++1,c;) = [1 [1- (1 - ->0* (1 - p)* To add the node J++1 to the intervention
set, 9i must first be added. Hence, E
11000 e, 7e,t1,,, es
= 0. Therefore,
(k) e, e
(k) 9ij le, e3
E
1100
= 0 < E
Case 2: e, does not occur and e1+1 occurs. Here, there is at least one edge from I, {oi} to 9++1. but no edges from
Ij \ {9:) to gi- In this case, P(ec+1, m); = p) [ - (1 p)*² If we merge nodes di and g++1 into a dummy node, from the perspective of the other nodes, the dummy node in cases I and can be treated similarly except that in case 1. paths in M that go to 1 must include 9t. (thus E(g 16,1,, e:] = 0) while in case 2, the opposite does not hold
e, 6,41, me,] # O. Therefore, the expectation of visiting the set I, in case bigger than the expectation of visiting Iym in case 2.
for 9i and Eiqi;) (k)
E
Pifta
(k)
e, 6,41, mes < 9i5 e, es
(k)
Note that this comparison is possible because P es) = P(e++1, ne,)
Case 3: Neither 6; nor 6:+1 occur. In this case, there are no edges from I, {gi} to either 9i or 9-+1- In this case,
P(-es+1, e)) = (1 p)
As in Case 1, to add gi+1 to the intervention set, must first be added. Hence,
E
(R) 91300
e, -6411 -e, 0.
Therefore,
E
(R) 12900
le, -i41, mei
=05E Si
(R) l,, -6441 76
28

---

HRL with Targeted Causal Interventions
Case 4: Both 6, and 6441 occur. Here, there is at least one edge from Zj { both 9, and 9+11 In this case, P(e411))) 1 - (1 r)** and both Di and li+1 have incoming edges from other nodes. Similar to case 2 we merge nodes yi and gc+1 into a single dummy node.
However, some paths in MM with length k that include Ii+1. include too, thus will not be counted in Elq e, 6+11,
) while the paths leading to Zy do not rely gi+1. Hence,
E
1130o e, e,,,
S (is le, e,ee41
we use all the inequality achieved in all the above cases,
E
9100
(k)
c = P(-e(+1, e,) x x P(e++1, -,,) x (9309 e,+11 Tee
(8)
case
case 2
P(-e1+1, e. x x0+ P(e++1,)) x E
11(0) e, es+1.0
cuse
(R) +P(eit,, x
< P( E( x
T1j e, ei
ei4i, -s
and
P(-ei41, ei)
E
Tij e,
(k)
(k) P(e X
Ti
E
9i
(k)
case
case
Hence, the expectations in (63) are less than or equal to the corresponding expectations for I,. This, along with the (62),
results in:
(k)
(R) 9i
915033
E
To construct the set Ij:- we perform sequence of successive single swaps. We begin with the set I,0>,, where r = max
9: ] represents the maximum index among nodes in set I,. The construction process is as follows:
1. First, we replace node Dr with gr+1 and construct Iy(r)
2. Then replace 9-+1 in Iy(e) by 9r+2-
3. Continue this process until In. is in the set.
At this point, we have constructed Ij.. If r. the process is complete. Otherwise, we continue a similar replacement process starting from set I,.. In Ij.,, replace the node gr where r' is the second maximum index among nodes in set I, (r' max(= 9= E Z {o+})) with its successive node 9++11 until reach the node If = r' the process is complete, otherwise we repeat the process similarly.
Through this sequence of single node replacements, we can successfully construct the desired set Z,,- Since each replacement operation results in a set with lower expectation, when we construct I,,, the following inequality holds:
(K)
(K)
E
11
F. Ranking Rules
F.. Graph search algorithm
In the following, we describe the graph search algorithm (Algorithm 6) and also refer to the corresponding parts in HRC algorithm. The graph search algorithm initiates with empty sets CS and IS, along with root subgoals, which are the
29

---

HRL with Targeted Causal Interventions
subgoals with no parents in the subgoal structure G. Sets IS and CS represent intervention and controllable sets, respectively. In line (corresponding to line 2 of Algorithm 1), we add the root subgoals to the controllable set CS. At each iteration, subgoal Gsel, is selected from CS (corresponding to line 4 of Algorithm 1). Then, in line 4, Isel will be added to IS and removed from CS (corresponding to line 5 of Algorithm 1). Once the children of the selected subgoal Isel are determined using the estimated subgoal structure i (corresponding to lines 5 to 8 of Algorithm 1), set CS is updated in line 7 to include these reachable subgoals (corresponding to lines to 11 of Algorithm 1).
Algorithm 6 Graph Search Algorithm
Require: Final subgoal Iu: empty set IS (} and CS 0, rool_subgouls.
I: CS <- --ott_ssoe subgosus
2: while 9n. $ IS do
3: Select subgoal gsel from CS
4: Remove gsel from CS and add it to IS
5: for all subgoals y' E (CH&
gie (IS U CS)) do 6: {reachable subgoals become controllable}
7: Add g' to list CS
8: end for
9: end while
10: return 2 (IS) + (ength(CS)
We define the cost of the graph search algorithm to be proportional the training cost of Algorithm 1. In Section E. TE] [F [lluianng") w. In this equation, if we assume [Z] 0 (i.e., there is no cost to intervene subgoals in 1), T = T", and U 22wT, the equation will be as follows:
equation (8) shows the expected transition cost if [u int.g"
T3
U+
E
U.
(64)
9" ((UUUD()))))
If we consider U unit of cost, during each transition, the above equation counts 1 unit for Intervention Sampling and N (I J gsel)) units for Subgoal Training steps. In other words, this shows the number of additions to the intervention set and controllable set, during the run of the algorithm 1, hence we define the cost of running the graph search algorithm after the termination as follows:
(65) The cost is calculated as the total number of additions to sets IS and CS, during executing the graph search algorithm, which is equal to twice the number of nodes in the intervention set IS plus the number of nodes in the controllable set CS, at the time of termination. To guarantee the validity of our ranking rules in sections 6, we assume that Assumption 7.1 holds and that there are no errors in estimating ECEA (in Section 6) and h is perfect heuristic according to (Pearl, 1984) (in Section 6). It is important to note that while these assumptions are necessary to provide formal guarantees, the ranking rules can still function without them.
c = 2 x IS| + CSI,
F.2.A. A Search for Weighted Shortest Path
The A search algorithm finds the shortest path from a start node to a goal node in a weighted graph. The description of A search as follows:
1. Initialize two node sets: a closed set (already evaluated nodes) and an open set (yet to be evaluated, starting with the initial node). We define a function parent pointer + + Φ, which assigns the corresponding parent of node ge. Nodes are evaluated based on three key functions:
g(g:): ): the cost from the start node to node gi.
h(g:): an admissible heuristic estimating the cost to the goal from 9i.
f(g.) = g(g.) + hgg)): the total estimated cost through node 9s.
2. While the open set is not empty:
Select node yi with the lowest f(g:) from the open set.
g: is the goal, backtrack to construct the path.
30

---

HRL with Targeted Causal Interventions
Move 9; the closed set and evaluate its neighbors:
For each neighbor 9m of 9s. if 9m not the closed set, add it to the open if not already present.
Calculate tentative g(gm) = g(g:) + weight(9::99n) 9m).
If tentative 8(9m) improves upon the known g(9m), update g(9m), set the parent porent.pointer(g.)) = 9t. and recalculate f(gm).
3. If no path to the goal is found and the open set is empty, conclude no path exists.
E.3. Backtrack function
We define the function back_tres fack_track(gs) that backtracks through the parent pointers of the node di and returns the set of ancestors of 9; during the backtracking process:
{ggt back baack.rrckkparenttpponteeer U {gc otherwise.
if parent.pointers = Ø
back_track(g.))
F.4. Admissible Heuristic
A heuristic is admissible if, for every node 9s, the heuristic estimate h(g:) is less than or equal to the minimum cost from gi to the goal. Mathematically, this is expressed as:
h(g)) S (g.),
where h" (g:) is the actual minimum cost from gi to the goal.
F.5. Consistent Heuristic
This is stronger condition than admissibility. A heuristic is consistent if, for every node and each of its children g', the following condition holds:
h(2) S w(g,, gf) + h(g)),
where w(gi, g.) is the weight from gi to g(-
F66 Conditions for Optimality Guarantee
If a heuristic is admissible (and we allow revisiting closed nodes) consistent, A search is guaranteed to find the optimal path to the goal. Using admissible heuristic ensures that A prioritizes paths that are potentially closer to the goal, and explores them first. If the heuristic is also consistent, it preserves the order of the nodes as they are expanded, and ensures that the first time a node i is expanded (moved to closed set), it is guaranteed to have the shortest possible cost g(i).
F.7. Shortest Path Ranking Rule
After the Causal Discovery step, we define the set E of the children of Isel, in & as follows:
E =
gg gi & IS,, Ii
CH 9vt.1
Then, for each gs E E, we update the cost of getting from the start node (root subgoal) to it, i.c., g(g:). as follows:
g(g.) + min (g(g.).g(os g(ovel.)) + CH th
\ back track( w) + +1)
get.t
where back track(gset.) the set of subgoals the path from root subgoals fsel, (see the exact definition in Appendix taakkkrrck((aaaa .) 1, shows the expansion cost of the node gj in the context back_track(gua, .) represents the number of new subgoals needed to be trained in Subgoal Training step and 1 denotes the number subgoals added to the intervention set (i.c., intervening on it in Intervention Sampling).
F.2). the above equation, the term ICH',
fielt
of A algorithm. Specifically, the term |CH 9ual:
31

---

HRL with Targeted Causal Interventions
To update (gs),, for each 91 E, propose dynamic version of Dijkstra's algorithm that computes the weighted shortest path from g; to In within 9. In our approach, the edge weights in Gg are determined during the algorithm's execution. For each 9i E E, perform the following:
1. Initialization: Set the tentative distance dist(g;) and dist(g) = oo (the distance of to g) for all g E E' (as). We define a function parent. pointer: Φ + 4, which assigns the corresponding parent of a node Jt.
2. Priority Queue: Insert all nodes into priority queue Q based on their tentative distances.
3. Algorithm Execution:
While Q is not empty:
Extract the node with the smallest dist(gw) from Q.
For each neighbor gr of gu in By:
Set w(Ju, Po) = ICH gx back_trackkg.)) +1
*
If dist(ge) & dist(g.) wGu: 9v), then: update dist(gw) dist(gu) + w(Bu, and parent.pointer(g.))
Iu-
4. Heuristic Update: After computing the shortest path, set
h(g)) = dist(gn).
F8. Intuitive Examples
In Figure 9a, to achieve the final subgoal fs. the green subgoals must achieved and these are precisely the subgoals with non-zero causal effect on gs. Similarly in Figure 9b, we achieve the final subgoal Ia if we only achieve the green subgoals during the execution of the algorithm. Under the conditions explained in Section F.1, Causal Effect and Shortest Path ranking rules will yield the minimum training cost in scenarios of Figure 9a and Figure 9b, respectively.
(a) AND subgoals
(b) OR subgoals
Figure 9. The causal effect and shortest path ranking rules aim to include only the green nodes to the intervention set, as shown in Figures (a) and (b), respectively.
F.9. Hybrid Ranking Rule
In this rule, we integrate the two ranking rules described in Section 6. In Initialization step of Algorithm 1, we initialize list selected. subgoals that keeps the subgoal to be selected Isel, : top of it. At each iteration, if selected subgools is not empty we pop the top of selected steps before popping the top of salected_subgoode
and choose the returned subgoal as Isel, otherwise, we do the following
(i) For each subset S C CS,-1, we calculate the ECE,- (5, CS \ S, gm). This measures the impact of S on the final
subgoal In. We keep subsets, where the corresponding ECE,, is not zero, and put them into collection S. iii Next, for every S E S, we define the function F(S) as follows:
F(S) = G(S) + H(S),
where:
32

---

HRL with Targeted Causal Interventions
G(S) represents the cumulative of the costs of all subgoals in to be added CS. It is defined follows:
G(S)
Σ
((و;)
CH 1 [S 1,
9, erer
where,
9 PAS
U PA BLES
l denotes the of parents of the nodes in S in the graph S:-1-
(S) the estimated cost from S to the final subgoal In- The heuristic function (S) is computed as the number of distinct nodes that appear on the paths from each gi E the final subgoal Ins based on the adjacency matrix of 9111 i.e,
H(S) = Σ 3. Epaths, (5-+9n)>
where path.g (S - 9n) represents all the paths from any subgoal gi E S to In including Ji and In. based on ---1-
We select the subset S that minimizes F(S). Then, we add all the subgoals in S to the selected subggoll in an arbitrary order.
Figure 10. A stage of the algorithm where O1 is in the intervention and 92: 9s. 94 Is. controllable. Our Hybrid heuristic aims select S4 and go as Geel for the next stops.
For instance, in Figure 10, consider that in line 4 of Algorithm 1 at iteration t where IS,- {9i} } and CS,-1 (92, (3, 94 are the intervention set (represented by green nodes) and controllable set (represented by blue nodes) at the end of the iteration & 1, respectively. Suppose that FCF,, is accurate in this example, meaning that if ECF,,- is zero, the corresponding ECEA is also zero, and vice versa. Now apply the steps of Hybrid heuristic: (i) We compute the estimate of A
A
the expected causal effect (ECE,) for every subset of CS. Subsets with non-zero ECE,- will be added the collection S. For instance, if we select subset {,2,, } from CS.-1, ECE, (192.9a) (g4.95) will be non-zero. Furthermore, if we select g4), ECE,- (103, ) (12, 915 ), 98) will be zero. With further evaluations, we identify three candidate sets with non-zero E.E,, S = (J2, 03 S2 [94, 95), and S3 {92. f3, 94, }. resulting in the collection S = (Si. S2, Sa}. (ii) In this simple example, G(Si) G(S,) G(5)) = 4 1 5. Now, we compute the H function for each of these sets: H(S,) Kg2. 9a. I6. Io |10] 5, 5, = [g4, 95. g 1 = and (Sa)) = {92, 93. Io. 99 910- 94. 96. 9s = 8. Therefore, F(S2) < F(Si) and F(S2) < F(Sa), and we choose S₂ = {91. ga } for the next selections of gsel. Therefore, we add all the subgoals S2 to the selected subgoals.
33

---

HRL with Targeted Causal Interventions
F.10. Key differences with CDHRL
If HRC uses the random strategy in line 4 and applies the causal discovery method described in Ke et al. (2019) in line it becomes similar to CDHRL framework in Hu al. (2022). CDHRL does not consider the concept of Iel and simply appends the entire controllable set to the intervention set (IS, CS,-1 u - In contrast, prioritize the controllable subgoals (explained in the next sections) to guide the exploration of the subgoal structure. Another difference is that CDHRL treats the action variable as a subgoal and initializes the intervention set with the action variable. In contrast, we make no such assumption and allow the intervention set to start by any root subgoal. Moreover, we design a new causal discovery algorithm with theoretical guarantees while CDHRL applies the causal discovery in Ke al. (2019) where there is no guarantee on what it can learn.
G. Causal Discovery
G.1. Proof of the proposition 8.3
The SCM that satisfies Assumption 4.2 can be written as follows:
1,
if X = 1,
X XX
X A',
0
if X 0 and (x(X)) 0,
isism n
h: EV X At,+t))
if X and 0x(X*) = 1,
where,
X). if gi is an AND subgoal,
0x(X*)
9y ErEA
V
X), if di is OR subgoal,
9. PA
h; is the causal mechanism of X; when (X,)) = 1, and gv X represents the vector of all the variables in Xgv \ X at time t. Now, we show that we can identify the subgoal structure up to the discoverable parents.
OR Subgoal:
Suppose is an OR subgoal, and 9j E PAg. is an undiscoverable parent. If 9j is not discoverable one of the following occurs:
1. There is no valid assignment X E {0, 13" such that
g E PAge
X 0.
This implies that in all possible assignments, at least one parent of g, is always 1, Therefore, the OR operation can be replaced by I:
0,(X))
V
x/=1.
PAEP
Thus, the SCM simplifies to:
x
X X', = h, h2,
X A",
A (4 x.-
Now consider an alternative SCM where has no parents and is only dependent on initial state and causal mechanism ha
X - h2 BY X A ( X
Therefore, the original SCM the same as the alternative one, making them indistinguishable.
34

---

HRL with Targeted Causal Interventions
2. If there is valid assignment X {0, 13" such that
X, 1, gg PAg. {99},
X
This means that in the collected data, X is one, least some other parent Xx also one. Now consider alternative SCM where 9j is not parent of 9::
(x
V
X
ILEPAR, Ma.
Both the original SCM and the alternative have the structural assignments X given the condition that Xj and at least some other parent of X; are one all time t. Therefore, from the collected data, cannot distinguish between these two models and 9j is not discoverable.
AND Subgoal:
Suppose 9i is an AND subgoal, and gj is an undiscoverable parent. This means that one of the following situations occurs:
1. There is no valid assignment X {0, 13" such that
Vgg PAge
X₃ 1.
Thus, the AND operator equals to O:
0,(x') =
X =.
grEPAgc
The SCM simplifies to:
x: x X
Now consider an alternative SCM where is isolated and only dependent on its initial state, thus it has no parents and no dependency to X XX', , A", and ef through mechanism h4 (i.e., 1; (X Ev X A [+1 0). Hence:
X =xP
Again, both SCMs have the same structural assignment on X Lv given the condition that the parents of gi are not achieved at all time t. 2. There is no valid assignment where
X, 0,
Vgkk E PAg. \ {93),
X₁ =.
This means that if X, is zero, at least of some other parent Xş is one. Now consider an alternative SCM where gj is not parent of g::
(x'))
A
X
SLEPA Mo.
Both the original SCM and the alternative one have the same structural assignments on X gv given the condition that at least some parent (other than 9;) is one at all time t.
This shows that when a parent is undiscoverable, alternative SCMs without that parent produce the same observable behavior, making them indistinguishable. This justifies the claim in Proposition 8.3 that the subgoal structure is identifiable up to discoverable parents.
G.2. Example of Undiscoverable Parents
In this section, we provide an example to illustrate how certain edges in the subgoal structure may not be detectable.
Consider the subgoal structure depicted in Figure 1lb corresponding to the time series with the one-step causal relationships shown in Figure 11a. X, and X2 are OR subgoals, and X3 an AND subgoal. Both X, and X, are parents of X3, and
35

---

HRL with Targeted Causal Interventions
additionally, X1 a parent of X2. Subgoal X3 cannot be achieved achieved at prior time step E' t. Moreover, achieve X2, X1 must be achieved earlier time step. Now, if Assumption 4.2 holds, X1 is always one when X₂ is equal one. Therefore, could not find two valid assignments in the observed time series satisfying the condition in Definition 8.2.
time step unless both X₁ and X₂ have been
In this simple example, the following conditional independence holds in distribution P over the time series data X7:
(X3+)
x
1).
Therefore, constraint baase causal discovery methods cannot detect the edge from X to X3² in 1la
X1
X
X++1
X2
X
X
X
X3
3
(a) The one-step causal relationships time se- ries.
(b) subgoal structure.
Figure An example of undiscoverable parent (X1). The subgoal structure the time series shows the red edge cannot be detected.
G.3. Proof of Theorem 8.4
Theorem G.1. (Formal Statement of Theorem 8.4)
Consider an SCM where the value of X!+1 determined as a function of the variables in the system at time t and an error term + 1+1,
X = 0(x') 3 +et !+1
where 9i is either AND or an OR operation defined as
0x(x)) AxxEPAx, X AND operation,
VXxEPAX, X OR operation,
and denotes the XOR operation. Moreover, the error term d++1 has Bernoulli distribution with parameter p < 1/2.
For variable X and R.,, consider S as:
S(X Σ 3,X 8n-
(66)
Let x (SS ,)) 0} be an estimate of X For any vector B, consider the following loss function:
((3) [[ x All
(67)
There exists a X > 0 such that for any optimal solution 3 minimizing the loss function in (67), the positive coefficients in 3 correspond the parents of x!+1 X
Proof of Theorem G.I: In the proof, for ease of representation, denote x! by y and drop superseript in X and + 1 in d. Also, might use the notation of environment variable and its associated subgoal interchangeably. Moreover, for any given B. we also denote X! by úp-.
36

---

HRL with Targeted Causal Interventions
Let PAy be the parent of y. We define py Xj PAg]-
Proof for OR subgoal: We show that any optimal solution 3 should satisfy the following conditions:
1. For j $ Py. 5 0,
2. For j E Py. $9 >
Let us rewrite the loss function in (67) for any B satisfying the above conditions as follows:
((3) = [ - }1) + A|l,3loo
(68)
Σ
P(X) ú3)) X
X|Py1
(69)
Σ
p
(70)
(=(1,
p+ X|pyl.
(71)
(a) We marginalize over the set of all possible Xs. P.,) denotes the cardinality of the Py-
ùel is equal to one if e; 1 which occurs with probability p. Otherwise, there is error in prediction.
Now, we show that if any vector 3 fails to satisfy either of the aforementioned conditions, it will result in an increase in loss compared to 71. To prove this, we consider the following three cases: 1- 3 does not satisfy condition 1 but satisfies condition 2- 3 satisfies condition 1 but does not condition 2. 3- /3 does not satisfy both conditions and 2.
Case 1: As 33 does not satisfy condition 1, the non-parent variables might also have non con-zero coefficients in B. We form the vector 3 (13) by setting to the entries of B3 corresponding to the non- non-parent variables. Moreover, define A, set of indices of non-parent variables that have non-zero coefficients in G, i.e., Ay Lilj & Py B3 + 0}.
Now we compute the difference in the losses for /3 and 3a (3)):
((B) - (B) = B[(y - 0 - E2 - (33(())) + AcllBllo - 11.3 (B)llo),
(72)
[E((y " - p] + A(113110 (.y),
(73)
X(1 PPy))
(74)
A(IPy) -1411 - PP,))
(75)
(c) 0.
(76)
(a) It is due to the fact that for any 3 E R", B[(
1 2 p.
(b) As condition 2 holds ||,31| = 1P, + |Ayl-
(c) We assume that |Ay 0.
This indicates that / has higher cost compared with 3 (3) and it cannot be an optimal solution.
Case 2: Now consider B fails satisfy condition 2 (but it satisfies condition 1). This implies that there exists j belonging to the parent node set P,, such that its corresponding coefficient is less than or equal to O. In particular, we define the set M, {ilí E Py, B3 < 0). Please note that we also suppose that [M,] > O. We form the vector 33 (B) by setting the entries of B corresponding to the set M, to a value greater than zero. Moreover, we define Zy, DM,,- and Dz, as follows:
Z, زازاا Pa 83 =3
DM, XX (0,1)" F My. X, 1 and X; 0 for all E Py s.t. j}.
where DM, corresponds to the samples, where only one parent in My is equal to one and other parents in the system are zero. Let us compare the loss function for B and (B):
37

---

HRL with Targeted Causal Interventions
((B) - (G) = Bl(v- 03)² - El(y - Uو 0 (8)
+ lo || (3)1lo):
(77)
Σ P(X)
Bi(v - 1s(x ))
El(v 1 (0xx
(78)
XeDafy
+
Σ P(X)
BI((y -1x(x,)))) BI(v (0))
(79)
X4DM,
+ X(11 0 - (B)1lo),
(80)
(
Σ (1X) - 2p) + A(11311o 11,3 (3)1lo)
(81)
XEDM,
Σ (L 2p) 1|1y1 0,
(82)
XEDM
(a) For X DM,, S(X, 3) S(X, and و/3 is set to 0 while ū)-(3) is set to 1 since we assigned values greater than zero for the coefficients in (B) corresponding to parent nodes. Thus, for any X E DM, the model with coefficient vectors 33rme and 3a (3) predicts y correctly with probability 1 p and p. respectively. Consequently,
Σ XEDM,
P(X)
Elyy 1)( | B[(y ((x.,>(())))
(83)
Σ
[( (()1-p) p) pl
(84)
XeDMy
Σ ((X)(1-2p))
(85)
XEDMy
Moreover, the term
Σ P(X)
B[(y ) B((y (s)) ) 0,
X&PaN
since El(y- - 1 (1))))(88)) | p and for any B E IR",, E( 1 ) 2 p.
(b) There are 1zyl more nonzero terms in 3 (²33) compared with B. Moreover, EXEDa, P(X) - 2p) 2 |Das, minxe Dr, (1 2p)] 2 IZyl x minxe [P(X) 2p). Therefore, for À < minxe (1 the loss of @ is greater than (B).
Case 3: In this case, ,3 fails to satisfy both conditions I and 2. This implies that some non-paren variables have non-zero coefficients in B. Moreover, So is not necessarily equal to zero, and for any belonging to the parent node set Pg. their corresponding coefficient can be less than or equal to O. In particular, first, we form the vector 3 (3) by setting the entries of 3 corresponding to the set M, to a value bigger than zero, and second, we form (33 by setting zero the entries of / (333) corresponding to the non-parent variables. The reasoning about the loss change L(B) - (3)) is the same as case 2. except that for X & DM,,, one can claim that having S(X, 3) S(X. 3 (3)) might lead to a decrease in the [((y- ú X). This means that for given X, (3) is wrongly set to I while 0j3 is correctly set zero resulting in a lower squared loss in (vv 9 X compared to EE[ ()) )² X]. Since the actual class of y is zero, then all X, E PAy must be equal to O. Hence, changing the corresponding coefficients of the parents would not affect the value of S. This implies that for this specific X. S(X, B) = S(X,3((3)) (3)), which contradicts the given assumption that S(X, 3) < S(X, (B)). Therefore,
Σ P(X)
Bl(y- - 9 | El(y - (0)) pIx) 20.
X&DM,
38

---

HRL with Targeted Causal Interventions
The reasoning about the change in loss, ((3) - L(3" (3)), is the same as 1. Therefore, the total loss change would be follows:
((8)))(3((3))
BB(y
0)a)²
El(y U (0))
+o ||3 (3)]lo):
(86)
Σ P(X)
[((y 19) |
E[(y 1=(xx
(87)
XeDMy
+ Σ P(X)
B[(y 11((x.9))
El(y 1 (00)
(88)
X&DM,
+ X(1131 0 - (3)1()))))),
(89)
Σ
2p) P1 - + +(1p)) - 1 + +1A11 (Pg))
(90)
XcDMy
E
P(X)(1 - 2p) + + |Zyl |Ay|)-
(91)
XeDMy
Similar case 2, we select À minxeDM, (1 - 2p}] ensure that the calculated difference remains positive. It is important to note that the term P(X)(1- 2p) may not be applicable to all X in DMr, Specifically, for those X where Ejgr, P, X, is positive within the score 3). However, the cost P(X')( - 2p) applies to the sample X', which is identical to X except that the corresponding parent value is O. Therefore, we can conclude that any optimal solution to the loss function given in (67) must satisfy both conditions I and 2, thereby completing the proof.
Proof for AND subgoal: We show that any optimal solution 3 should satisfy the following conditions (we consider that 30 < 0):
1. For j & Py, 83 = O.
2. VU Ç Py:
Σ 33 1 -Bo JEU
(92)
Σ
83 > -Bp
(93)
jEP,
The value of the loss function in (67) for any f3 satisfying the above conditions is equal to 71. Now, we show that if some B fails to satisfy either of the aforementioned conditions, it will result in an increase in loss compared to 71. To prove this, we consider the following three cases: 1- 3 does not satisfy condition but it satisfies condition 2. 2- /3 satisfies condition I but does not condition 2. 3- ,3 does not satisfy both conditions and
This part is similar to OR subgoal, case
2- Consider ( satisfies condition 1 but fails to satisfy condition 2. In this case, we first show that if there exists some j belonging to the parent node set Py such that its corresponding coefficient is less than or equal to 0, at least one of the conditions in (92) or (93) will be violated which in turn results in a higher loss. To prove this, we define the set M, = {ilj E Pys Bj S 0} and Zy = (ilj E Py. 33 = 0} and form the vector (3) by setting the entries of B corresponding to the set My to a value greater than zero such that both (92) and (93) are satisfied. Note that this operation is feasible since we can adjust the coefficients corresponding to non- parear nodes and parent nodes independently. Now we show that the L(B3) is greater than equal to L(B (ß)). We can define the following sample set:
DM, (X,,0 j My),
(1 if and i + We also define the vector X, where {1); for E Py- We can compute 0 if
where [x,
the difference in the losses for B and fe (3)) as follows:
39

---

HRL with Targeted Causal Interventions
[(3) - (3))
BB((y ú/))² - Bl(y ( x(11131 (3)lo)))
(94)
E
P(X)
B1(y 1s( El( (3)) |
KEDM,U(X))
E
P(X)
B((y (1s(xx)))) El(y - 1((
X4DM,
+ 3(11311o - (3)1lo)-
(95)
Now, we derive a lower bound on (95). It is clear that 1(, S S( 3). We show that at least one of the terms
corresponding jo or X2 results in an increase the loss compared to the one of 3 (3). In particular, if 5 jo 3) s then ,, .) < and as a result, j/ is set O which yields the expected loss of 1 p given observing the sample X Moreover, if S (X ju (3) 0, then 93 is set to which also yields the expected loss of 1 P given the sample X Thus, have an increase of either (1 2p) or P(X,) 2p) in the loss compared with _(3 (3)). Therefore there exists
sample in DM, U {X1} for which
B[(y ss(x,))) )
E[ Ls(x,8 (91)) is (1 - 2p) and we denote it by X.
Note that
Σ
P(X) Bi(y 1 El(y 1s(x, 2 0,
X u
since El(y- 1 (((x,a-(0)) and (1y - [( cannot be less than p. Hence, (95) can be lower bounded as follows:
((B) - (3 = [B(yy - ú1) - B(y - ( + x(1181% - (3)))o),
(96)
Σ
P(X)
Fl(yy- 1 s(xx)))
B((y (8))
(97)
XEDM,
Σ P(X)
B((y 10-_ssxx,,)) B[(y - [xx)
(98)
((DM,
A(118110 (B))lo),
(99)
P(X) 2p) >([1B110 -1 (3)
(100)
P( 2p) -|Zz 0,
(101)
where (i) is due to the fact that there are |Zyl additional nonzero entries in (B) compared to B. To ensure that the last inequality holds, we need to choose a value for À such that it is less than |2, P(X) 2p). We observe that:
min (P(X, (1(X))(111 2p)), P(X,) 2p) < P(X) 2p)) jEP,
min
and
1zyl <
Which result in:
min min (P(X;,,) P(X,)(1 2p)] - |zyl n JEP,
P(X) - -2p).
Therefore, if we choose À such that X < min(minnee,, (P(X (1 - 2p)), (1 2p)]. we guarantee that the loss of (3 is greater than (B))
Now we study the cases where 33 > 0 for all j E Py, yet (92) or (93) are not satisfied. the following, we will cover these cases and show that there is an increase in loss. It is noteworthy that in these cases, there is no change in the regularization term || loo
40

---

HRL with Targeted Causal Interventions
(a) Consider the case,
3U P.y Σ
B3
-
(102)
jEU
Σ JEPy
B3 > - B0-
(103)
{
if U
In this case, if we have positivity assumption, there exists a sample such as X where [X]:
which
0
if i U
wrongly be classified as and the loss will increase at least P(X)(1 2p) compared to the (3).
(b) Consider the case,
VU & PsJ. Σ 33 -Bo
(104)
JEU
Σ jEN
B, $ - 30-
(105)
1 if E Py
In this case, if we have positivity assumption, there exists a sample such as X where [X]:
which
0 if & P
will wrongly be classified as 0 and the loss will increase at least P(X)(1 2p) compared to the (B))
(c) Consider the case,
EU
& Py, Σ
Bj
-0
(106)
JEU
Σ
B3 < -Bo-
(107)
jEP,
In this case, both arguments made in (a) and (b) can used to show that there is an increase in loss (at least (X 2p)) compared to the (3))
3- In this case, ,3 fails to satisfy both conditions and 2. Similar to the OR subgoals, we form the vector (3) by setting the entries of /3 corresponding to the set M, to a value bigger than zero such that condition is satisfied. Moreover, we set the entries corresponding to the non-parent variables to zero. The difference the loss for B and 3 (.3) is as follows:
C(B) - C(B = Elyy - 93) - E((y - 033((1)) )8] + A(11B)l - (18((()))))))
(108)
Σ P(X)
[[( - L () [[(y (())
(109)
XEDM,
+
Σ
P(X)
BI(y 1s(x,
El(y - L (a)xxxxx-())))1 (91) |
(110)
U(D,)
A(118110 11 (B))lu))
(111)
> P(X)(1 - 2p) A(11/310 (3)1o)
(112)
= ((X) - 2p) A(I 12 0.
(113)
with similar argument, |Ayl appears in cases and X and are chosen based on the arguments made in case Therefore, the last inequality is greater than zero, implying that any optimal solution of the loss function (67) should satisfy both conditions and and the proof is complete.

---

HRL with Targeted Causal Interventions
H. Details of Experiments
H.1. Experiments setup for synthetic dataset
Figures 5(a), 5(b), and 5(c) illustrate the costs for semi-Erdös- -éndi graph G(n, p) for different values of c. For cach semi-Erdós- Rényi graph, we randomly choose node (subgoal) to be either AND or OR. For each node size illustrated, we generated 100 graphs, and for each graph, we conducted 10 trials of the methods. Each point in the plots represents the mean cost of these runs. Figure 5(d) illustrates the cost of HRC. for tree Gin, b) where the branching factor is set 3. Each point in the plot of Figure 5(d) shows the logarithm of the mean cost over 100 runs on the generated graph. In our experiments with synthetic data, we considered a relaxed version of Assumption 7.1 with a specific form of error (1+z) in recovering new edges where is the iteration number. We considered a 95% confidence interval for all the experiments.
H.2. Experiments setup for Minecraft
CDHRL is the most relevant method, proposed by Hu et al. (2022), which utilizes the causal discovery method introduced in Ke et al. (2019). Hierarchical Actor-Critic (HAC) is a well-known hierarchical reinforcement learning (HRL) framework (Levy et al., 2017) that enables hierarchical agents to jointly Iearn a hierarchy of policies, thereby significantly accelerating learning. However, compared to our targeted strategy, HAC exhibits poorer performance. Similar to the setup in Hu et al. (2022), Oracle HRL (OHRL) implemented as a two-level Deep Q-Network (DQN) with Hindsight Experience Replay (HER) introduced in Andrychowicz et al. (2017) and an "oracle goal space". In order to imitate the oracle goal space, manually remove subset of & that is useless in achieving the final subgoal. We conducted experiments in Minecraft using two-level Deep Q-Network (DQN) with Hindsight Experience Replay (HER) (Andrychowicz et al., 2017). HER allows sample-efficient learning by reusing the unsuccessful trajectories to achieve the goal by relabeling goals in the previous trajectory with different goals. Additionally, we experimented in Minecraft using VACERL, introduced in Nguyen et al. (2024), by using their publicly available code. However, in our experiments, we were unable to train this method successfully, The success rate and reward remained consistently at zero, similar to the PPO curve in Figure even after 4 million system probes. Due its poor performance, we excluded it from Figure 6. There are other methods in the literature that showed poorer performance compared to those we included (see CDHRL in Hu al. (2022)) in our comparison; therefore, we did not include them in our experiments.
H.3. Expected causal effect
Consider estimate of the causal model. This model takes the input X and returns X at the next time step. In practice, to calculate an estimate of E[X do(X a),, do = 0)] in Definition 3.4, we set t* 0 and A = 20. We start by initializing X where the X,s associated with the subgoals in A are set to a and those in B to O as the input to the causal model. All the other EVs are initialized with zero, except those associated with the subgoals in the intervention set IS. Then we take the output and use as the next input. Each time we feed the causal model with X, we ensure that the X,s associated with the subgoals in A are set a and those in B O. We repeat this process A times and then record the outcome for the final subgoal (X,)). We do this procedure multiple times to estimate the average of X
H.4. Sensitivity Analysis
In Figure 12 we show the performance of HRC algorithm under missing ratio of 20% of EVs. As you can see, the performance of HRC, (SSD) slightly affected by the missing EV' but still shows relatively robust and stable performance. HRC, (SSD) is more affected by missing EVs. This result indicates that targeted strategy was able to adapt to missing information very well.
H.S. Hyperparameters
We utilized Linux server with Intel Xeon CPU E5-2680 v3 (24 cores) operating at 2.50GHz with 377 GB DDR4 of memory and Nvidia Titan X Pascal GPU. The computation distributed over 48 threads to ensure relatively efficient run time. In the following table, we provide the fine-tuned parameters for each algorithm. Batch sizes are considered the same for all algorithms. For hyperparameter tuning, we performed a grid search, systematically exploring a predefined range of values for each parameter. To ensure robustness, we repeated the process multiple times with different random seeds. Table shows the key hyperparameters used our setup. Additional hyperparameter values can be found in the supplementary materials.
42

---

HRL with Targeted Causal Interventions
HRCD)SSD)
1.0
HRC_,1SDD
HRS_j(55)200%
HRS_s(5002
HAC
0.8
Success Ratio
0.6
0.4
0.2
0.0
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
System probes
1eb
Figure 12. Sensitivity analysis under missing ratio of 20% of EVs.
Table 3. More hyperparameters of different methods used in the experiment.
SUCCESS RATIO THRESHOLD
INTERVENTION SAMPLING BATCH SIZE
TRAINING BATCH SIZE
LASSO
METHOD
HRL LR
LI-RATIO
JOTHERS
HRC, (SSD)
0.5
32
0.0001
128
0.0001
HRC, (SSD)
0.5
32
0.0001
128
0.0001
HAC
0.0001
CDHRL
0.5
32
0.0001
128
func-Ir=Se-3
struct-Ir=5e-2
OHRL/ HER
0.0001
128
PPO
3E-4
128
ENTROPY
COEF=0.005
43

---

HRL with Targeted Causal Interventions
H.6. Computational Complexity
Regarding computational complexity, our experiments indicate that although our method introduces some additional computation compared to HRL baselines, this is offset by significant reduction in the number of system probes and overall training cost. Below, we provide runtime comparison between various methods to reach success rate of 0.5 in Figure 6(a):
Table 4. Runtime comparison (minutes) required to reach success rate of 0.5.
Method
Average Time (min)
HER
249.1
HАC
185.5
OHRL
133.8
CDHRL
352.3
HRC, (ours)
33.7
HRC, (ours)
38.1
H.7. More Experimental Comparisons
For more empirical comparison, we conducted experiments on the CraftWorld environment (non-binary) provided by (Wang et al., 2024) (SkiLD). Figure of their paper, they report achieving a maximum success rate of approximately 0.6 after training the downstream task (note that they need pretraining in their method, and environment steps for pretraining are unable
plotted in this Figure). However, when we attempted reproduce their results using the provided code, to match their reported performance. Additionally, the code ran extremely slowly on GPU server, requiring about 10 hours to complete just 100k environment steps. Due to time constraints, we contacted the authors to clarify the number of pretraining steps. We received two responses million and 20 million steps-but without a definitive confirmation. Based on Figure their paper, it appears that at least 12 million environment steps are needed to reach a success rate of 0.5. In contrast, the performance of our method on this environment is shown in Figure 13. Each unit on the x-axis represents 10 million environment steps. As illustrated, our method surpasses 0.5 success rate with just million environment steps, whereas SkiLD requires at least 12 million environment steps reach the same level. Furthermore, our approach achieves maximum success rate of approximately 0.8 compared about 0.6 for SkiLD.
Success Rate
Environment Steps
Figure 13, The performance of HRC on CraldWorld environment
44


Reviews:
[{"review_id": "rqBArKMUss", "reviewer": "Reviewer_T49j", "summary": "The paper presents a novel approach to Hierarchical Reinforcement Learning by leveraging causal discovery to identify hierarchical structures among subgoals. The key contribution is a causal discovery algorithm that learns the subgoal structure, which is then used to guide interventions during exploration. This targeted intervention strategy improves training efficiency compared to random exploration. The paper provides a formal analysis of the method and demonstrates empirical improvements on synthetic datasets and a gridworld environment (2D-Minecraft). Results show that the proposed method outperforms existing HRL approaches.\n\n## update after rebuttal\nI am happy with the rebuttal content. I'm raising my score to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and address the concerns under the following headings.\n___\n## 1- Reviewer:  In particular, I’m worried about two assumptions... \nRegarding controllability, our current framework assumes discretized subgoals, which is a reasonable assumption in domains where acquiring specific resources is required. For environments with continuous variables, one can apply disentangled representation learning methods to high-dimensional continuous observations in order to extract categorical latent variables—such as using categorical VAEs. We view this as a natural extension of our current work. The assumption of binary variables for resource EVs is made solely to facilitate the cost analysis in Section 7 and to provide theoretical guarantees for our causal discovery method in Section 8. To the best of our knowledge, this is the first work to rigorously model the HRL problem in SCM framework with a formal associated cost, and provide theoretical guarantees on the performance of the proposed methods. We will clarify this further in the revised version. \n\nAs for the exponential growth of preconditions, we agree that in the worst case, the number of potential combinations can be large. However, in practice, many environment variables (EVs) exhibit sparse dependencies, i.e., the parent set is small. As shown in Theorem 7.4, our method leverages the sparsity in the subgoal structure to guide exploration more efficiently toward the target goal. For example, in a tree-structures, our method achieves a logarithmic cost with respect to the number of EVs, whereas a random strategy incurs a quadratic cost. This efficiency enables our approach to scale effectively to environments with a large number of EVs in such structures.\n___\n## 2- Clarity and organization of the paper\nWe will include a table in the appendix listing all notations along with references to their definitions in the text. Additionally, we will add a brief paragraph at the end of Section 1 to clarify the overall structure of the paper, particularly the methodology section. It would be helpful if the reviewer could refer any notation that they believe was not explicitly or adequately defined in the text.\n___\n## 3- Comparison with skill discovery\n\nThe goal of skill discovery is to learn a diverse set of skills, which are later used to train a higher-level policy for a downstream task. In that context, a skill is conceptually similar to a subgoal in our work. However, there are key methodological differences in subgoal vs. skill discovery: 1- In skill discovery, the process of learning the skill set is often decoupled from the downstream task. In contrast, our work—framed within the context of HRL—conditions the learning process on a target goal. By leveraging the learned subgoal structure, our approach guides exploration toward only the relevant subgoals that contribute to achieving the target goal. In contrast, skill discovery methods often aim to learn as many diverse skills as possible, regardless of their relevance to the target goal in the downstream task. 2- In our framework, the lower-level policy is itself hierarchical and is trained according to defined hierarchical structure (where we defined it formally based on the discovered subgoal structure). This results in a significant reduction in sample complexity compared to standard policy training, which typically does not utilize such a structure. Beyond these methodological distinctions in subgoal discovery and training policies, to the best of our knowledge, our work is the first to rigorously study HRL within a causal framework. We formally defined the cost formulation, proposed subgoal discovery strategies (with our key measure ECE) with performance guarantees (Theorem 7.4), and provided theoretical bounds on the extent to which the subgoal structure can be learned in an HRL setting (Prop. 8.3). Furthermore, we introduce a causal discovery algorithm tailored to this setting, with provable guarantees on its correctness (Theorem 8.4).\n### Empirical comparison\nFor empirical comparison, we consider [2] as it showed superior performance to [1]. [2] conducted a similar experiment on a simplified Minecraft version with only 8 EVs and a 500-step horizon, achieving a 0.5 success rate after 2 million system probes. Our environment is much more complex with 21 EVs and a 100-step horizon, yet our method achieves a success rate approaching 1 (Figure 6). When testing [2]'s code on our Minecraft version, it consumed over 450 GB of memory before crashing. Therefore, we couldn't complete further testing of their approach, but we're currently evaluating our method on their Minecraft version for direct comparison.", "claims_and_evidence": "Most of the claims are well-supported. The paper provides a formal analysis for its proposed method, which strengthens its theoretical grounding.\n\nMore ablation studies, particularly on the impact of different causal discovery techniques, would strengthen the claims regarding the proposed algorithm's effectiveness. In addition, the writing of this paper is not super clear, with complicated and sometimes unexplained notations scattered over a total of 9 different sections. It would be beneficial to organize the method sections with a clearer intuition of what each subsection is doing.", "methods_and_evaluation_criteria": "The authors conduct experiments on both synthetic datasets and a real-world inspired HRL environment (2D-Minecraft), demonstrating the effectiveness of the approach.\n\nWhile the method performs well on the relatively toy 2D-Minecraft domain, it is unclear how well it scales to more complex real-world tasks with high-dimensional state spaces. In particular, I’m worried about two assumptions. First, the proposed method relies on being able to detect whether a environment variable is controllable. While this may be relatievly easy when the variable is discrete (especially when binary), but seems to be more problematic when the variable is continuous. Second, the possible “preconditions” for achieving a subgoal can grow exponentially w.r.t the total number of environment variables. It’s unclear whether this method will still work with a large number of environment variables.", "theoretical_claims": "The proofs look correct to me.", "experimental_designs_or_analyses": "Please see the \"Evaluation Criteria\" section above.", "relation_to_broader_scientific_literature": "This paper fits nicely into the causality-inspired skill discovery literature, and introduces a principled way to incorporate causal discovery into HRL. In particular, the causally-guided ranking system seems quite novel. However, the addition of some missing references (as detailed in the next section) would help assess the novelty of this work.", "essential_references_not_discussed": "The overall idea of this paper seems to resemble previous works [1][2], in terms of using causal dependency as a way to guide skill learning. Can the author discuss the connection/difference between this work and the aforementioned ones, and possibly compare their performance?\n\n[1] Chuck, Caleb, et al. \"Granger-causal hierarchical skill discovery.\" TMLR 2023\n[2] Wang, Zizhao, et al. \"SkiLD: Unsupervised Skill Discovery Guided by Factor Interactions.\" NeurIPS 2024.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See the questions above.", "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": "", "extra_scores": {}}, {"review_id": "S01HWVENw9", "reviewer": "Reviewer_q4Ho", "summary": "This paper tackles the long-horizon RL tasks with hierarchical abstractions. Specifically, the authors propose Hierarcahical RL via Causality (HRC) which enables the agents to prioritize some causally impactful subgoals over the others. Among the HRC framework, the authors also develop a new subgoal-based causal discovery approach and derive the theoretical guarantees for it. Compared to the existing hierarchical causal RL baselines, HRC empirically outperforms them in both synthetic data and MineCraft tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and address the concerns under the following headings.\n___\n## 1- Reviewer: The ablation study...\nWe already conducted several ablation studies (Figure 6) to evaluate our approach. To assess the impact of our targeted strategy, we compared three HRC algorithm variants: HRCh (SSD), HRCb (SSD), and HRC (optimal). As shown in Figure 6(a), HRCh (SSD) outperforms HRCb (SSD), highlighting the ranking rule's effectiveness.\nTo examine the causal discovery component, we also compared two HRC versions: one using our SSD method and another using a standard method (SDI). Results show SSD significantly outperforms SDI, demonstrating the benefits of our tailored causal discovery. \nLastly, a sensitivity analysis (Figure 12, Appendix G.4) shows HRCh (SSD) remains robust even with up to 20% of EVs missing.\n\n___\n## 2- Reviewer: However, in general deep RL applications...\n\n***Regarding the comment \"Generality to more practical applications\" please see number \"4\" of our response to Reviewer 5Zcn***\n\nRegarding interventions, as noted in Remark 4.3, in environments where EVs correspond to specific resources or skills, we assume that once a resource or skill is acquired at some time step, it remains accessible in subsequent time steps (Assumption 4.2). Under this assumption, a subgoal being controllable by a policy $\\pi$ (as defined in Definition 4.1) is equivalent to performing an intervention on the corresponding EV with policy $\\pi$. This interpretation is applicable in both simulated and real-world environments.\n\n___\n## 3- Reviewer: I'm not sure whether OR, AND...\nAs noted in lines 161–164, our proposed solutions can be readily extended to settings with non-binary domains for EVs, albeit at the cost of heavier notation. In fact, our experiments already evaluated the proposed methods in non-binary settings. The assumption of binary variables for resource EVs with AND/OR subgoals is made solely to facilitate the cost analysis in Section 7 and to provide theoretical guarantees for our causal discovery method in Section 8. We will clarify this further in the revised version.\n\n___\n## 4- Other references\n\nThank you for pointing out these references. In Related Work section, we will add references [1, 2] regarding neuro-symbolic RL; [3–5] for the use of interventional data in learning causal structures; [6, 8] for subgoal/skill discovery; and [7, 9, 10] for causal representation learning/causal abstraction in RL. We will also discuss about connection with stochastic control methods.  References [3–5] pertain to learning causal structures among random variables in structural causal models while our causal discovery method is specifically tailored to the HRL setting, working with sequenced data. In our experiments (Figure 6(b)), we have already compared our method with SDI, a representative method from this class that has been used in prior HRL work as a subroutine to learn the causal structure.\n\nRegarding [9], this line of research on causal representation learning is more geared towards recovering EVs, which is not the focus of our paper. Similar to prior work, we assume that either the EVs are already available or that the environment provides state vector–based observations. As for prior work on skill discovery (e.g., [6,8]), please refer to our response \"Comparison with skill discovery\" to the reviewer T49j for more details. \n\n\nRegarding [1–2], ILP-based methods represent policies as logical rules to enhance interpretability.  Our work considers a multi-level policy, with a focus on recovering the hierarchy among subgoals (with our explicit hierarchical structure definition) for training the multi-level policy more efficiently. Herein, we do not impose any structural limitations on our policy. For our theoretical analysis, we assumed that the causal mechanism of each subgoal follows an AND/OR structure. This assumption pertains to the environment rather than for representing the policy using logical rules. We will clarify this in the related work.\n___\n## 5- Reviewer: If the cost complexity bound...\nTo the best of our knowledge, this is the first work to rigorously model the HRL problem in SCM framework with a formal associated cost, and provide theoretical guarantees on the performance of the proposed methods. Analytical comparison with other related HRL approaches is challenging, as most existing methods are experimental in nature and lack a rigorous formalism. Nevertheless, in our analysis, we compared our approach with a baseline that uses random exploration for subgoal discovery, and our method outperforms it in both considered subgoal structures (tree and Erdős–Rényi graphs).  \nRegarding  limitations, due to space constraints in the main text, we were unable to include a detailed discussion. However, in the revised version, we will add a section to discuss the limitations and the future work.", "claims_and_evidence": "The major claim about the theoretical property (training cost bound in interventional causal discovery) and empirical performance of HRC are generally supported by Theorem 7.4, as well as Figure 5, 6 and Table 2, respectively.", "methods_and_evaluation_criteria": "**Method**: The paper’s method involves a hierarchical reinforcement learning framework that leverages causal discovery to learn the subgoal structure underlying long-horizon, sparse-reward tasks. Specifically, it introduces a new causal discovery algorithm tailored for HRL, and then uses targeted causal interventions—prioritizing subgoals via ranking rules (such as causal effect and shortest path ranking)—to guide exploration and improve training efficiency. \n\n**Criteria**: The evaluation criteria include cost complexities for theoretical cost analysis. For the empirical performance on benchmark environment, the authors use metrics like success ratio for the task reward and structural Hamming distance (SHD), missing edges, and extra edges for causal graph accuracy.\n\nThe proposed methods and evaluation criteria make sense to me. They directly address the challenges of sparse rewards and inefficient exploration in HRL by exploiting causal relationships to guide subgoal selection, and the combination of theoretical and practical evaluation provides a well-rounded assessment of the framework’s efficacy in complex, long-horizon tasks.", "theoretical_claims": "The paper's main theoretical claims are that by exploiting the causal structure among subgoals using a novel, HRL-tailored causal discovery algorithm, the proposed HRC framework can significantly lower the training cost compared to random exploration. In particular, \n\n1. Undet the assumption 4.2, the authors provide formal guarantees under certain assumptions, the subgoal structure is identifiable up to discoverable parents in Proposition 8.3 and Theorem 8.4. \n\n2. Under the assumption 7.1, 7.2, 7.3, the targeted causal interventions based on ranking rulesyield lower cost complexities—in tree and semi‐Erdős–Rényi graph models—compared to naive exploration strategies in Theorem 7.4.\n\nI reviewed the proofs provided for Theorem 7.4 (the cost complexity analysis) and Theorem 8.4 (the identifiability of the causal subgoal structure). The derivations appear logically sound and make appropriate use of standard techniques. While I did not perform a line‐by‐line verification, I did not find any obvious mathematical errors. However, in general deep RL applications, the assumptions may limit their generality in more practical tasks, e.g. the subgoal is not explicitly defined and is hard to abstract from pure observation, or the direct intervention is not practical in the simulator.", "experimental_designs_or_analyses": "The experiments compare different variants of the proposed algorithm (using various ranking rules and causal discovery methods) against several state-of-the-art HRL baselines using metrics like training cost (system probes), success ratio, and structural Hamming distance for recovered causal graphs under the synthetic experiments and 2D-MineCraft evaluation.\n\n1. The evaluation protocol is comprehensive in evaluating both the success ratio and causal discovery quality. \n2. The ablation study is not explicitly mentioned. Since the pipeline in Algorithm 1 is pretty long, it might be helpful to conduct throrough ablation studies and discuss how important each module is and how likely some assumptions would hold in practice, such as the assumption 7.1. \n3. I'm not sure whether OR, AND could cover all the possible subgoal relationship in all the long-horizon decision making problems. The authors may include this in the limitation discussions. \n4. It might be helpful if the authors could compare the HRC with other causal RL approaches listed in some of the essential references [5, 6, 7].", "relation_to_broader_scientific_literature": "Beyond the hierarchical RL and causality community, the Definition 4.1 and Assumption 7.1 remind me of the controllability of the subgoal seems to be quite similar to the reachability analysis [1] in stochastic control domain. It might be interesting to reveal the inner connection between HRC and the stochastic control methods. \n\n\n\n> [1] Amin, Saurabh, et al. \"Reachability analysis for controlled discrete time stochastic hybrid systems.\" Hybrid Systems: Computation and Control: 9th International Workshop, HSCC 2006, Santa Barbara, CA, USA, March 29-31, 2006. Proceedings 9. Springer Berlin Heidelberg, 2006.", "essential_references_not_discussed": "In the Neuro-Symbolic Reinforcement learning, there are some related works that also use similar formulations of target tasks [1, 2]. \n\nThere are also some works on causal discovery from interventional data, and also derive theoretical bounds over them [3, 4]. \n\nThere are some some causal RL works [5, 6, 7, 8] that use either causal discovery or explicit hierarchical structure in the policy, and other causal RL works that use controllability-related state abstraction [9, 10], which is relevant to the task domain that the authors are tackling with. \n\n> [1] Jiang, Zhengyao, and Shan Luo. \"Neural logic reinforcement learning.\" ICML 2019\n>\n> [2] Kimura, Daiki, et al. \"Neuro-symbolic reinforcement learning with first-order logic.\" ACL 2021\n>\n> [3] Yang, Karren, Abigail Katcoff, and Caroline Uhler. \"Characterizing and learning equivalence classes of causal dags under interventions.\" ICML 2018. \n>\n> [4] Brouillard, Philippe, et al. \"Differentiable causal discovery from interventional data.\" NeurIPS 2020\n>\n> [5] Scherrer, Nino, et al. \"Learning neural causal models with active interventions.\" NeurIPS workshop on Causal Inference & Machine Learning, 2021\n>\n> [6] Wang, Zizhao, et al. \"SkiLD: Unsupervised Skill Discovery Guided by Factor Interactions.\" NeurIPS 2024\n>\n> [7] Lin, Haohong, et al. \"BECAUSE: Bilinear Causal Representation for Generalizable Offline Model-based Reinforcement Learning.\" NeurIPS 2024\n>\n> [8] Hu, Jiaheng, et al. \"Disentangled unsupervised skill discovery for efficient hierarchical reinforcement learning.\" NeurIPS 2024\n>\n> [9] Zhang, Amy, et al. \"Learning invariant representations for reinforcement learning without reconstruction.\" ICLR 2021\n>\n> [10] Wang, Tongzhou, et al. \"Denoised mdps: Learning world models better than the world itself.\" ICML 2022", "other_strengths_and_weaknesses": "**Strengths**\n\n1. The paper is generally well-written and easy to follow, the paper is well-structured and well-motivated.  \n2. The baseline comparison is comprehensive, and it considers both the task success ratio and causal discovery quality. \n3. The theoretical derivation is generally sound and solid, which makes the results potential more generalizable in broader subgoal-based causal discovery applications. Moreover, the authors verify the theoretical results with empirical causal discovery performance in Figure 5. \n4. The empirical performance demonstrate a superior performance than SDI in Structured Hamming Distance, and a better assymptotic performance and convergence speed compared to other HRL baselines. \n\n**Weaknesses**\n\n1. Additional causal RL baselines such as the ones in [5, 6, 7, 8] in additional references, would be helpful. Comparison to other HRL approaches with implicit causal abstraction (e.g. the causal abstraciton based on controllability and/or reward relevance [9, 10]  in additional references) could also be interesting. \n2. If the cost complexity bound can be comparable with other literatures, please provide for a better reference. \n3. The authors do not include any limitation discussions or future works in the main text. \n4. The assumption of AND, OR subgoal abstraction may not be expressive enough for all the scalable applications in long-horizon real-world decision-making tasks, such as robot manipulation or autonomous driving tasks which require complex reasoning.", "other_comments_or_suggestions": "The paper structure can be merged into a few major sections and some subsections. Now it has 10 sections, which may be too much for the audience to keep up with the authors stories.", "questions_for_authors": "See the above sections for more details.", "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": "", "extra_scores": {}}, {"review_id": "JKrhMUSyc1", "reviewer": "Reviewer_5Zcn", "summary": "This paper considers Hierarchical Reinforcement Learning (HRL) by leveraging causal discovery to improve training efficiency in long-horizon tasks with sparse rewards. In particular, the subgoal structure is modeled as a causal graph and an algorithm to learn this hierarchy is introduced. Instead of random subgoal interventions during exploration, the proposed method prioritizes interventions based on their causal importance in achieving the final goal. This targeted intervention strategy significantly reduces training costs. The paper provides theoretical analysis, showing improvements for tree-structured and Erdős-Rényi random graphs. Experiments show that the proposed framework outperforms existing HRL methods in terms of training efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback and address the concerns under the following headings.\n___\n## 1- Reviewer: The evaluation seems reasonable, but still...\nAs the reviewer mentioned, grid-world environments are widely used in HRL research, as they capture key challenges such as subgoal discovery and hierarchical planning. In our work, we primarily focus on the 2D Minecraft environment as other environments (such as Mini-Behavior environments) are relatively simple and do not adequately showcase the strengths of our method.\n___\n## 2- Reviewer: It could be better explained how the hyper-parameter...\nDue to the space limitations in the main text, we have provided a detailed description of the experiments and hyper‑parameter tuning in Appendix G.\n___\n## 3- Reviewer: It seems that prior work on reward machines...\nWe agree with the reviewer that the reward machine can be viewed as an alternative way to represent hierarchical structures in HRL and can be effectively used for training policies. As the reviewer noted, our work takes a causal approach, representing subgoal structures within the framework of structural causal models. In the revised version, we will include a discussion on the line of research about reward machines in the related work.\n\n___\n## 4- Applicability of the framework to realistic settings\nWe acknowledge that our framework currently assumes an explicit definition of EVs, which may seem restrictive in some deep RL applications. However, in practice, many environments provide state vector–based observations that are inherently disentangled—meaning that each state dimension corresponds to an independent feature. This makes it significantly easier to extract EVs. Common benchmarks such as Atari, MuJoCo, and 2D‑Minecraft, all naturally possess this property. Moreover, many hierarchical RL methods—such as LESSON, DSC, and SkilD (mentioned by the reviewer)— already rely on such structured representations. In scenarios where EVs are not directly provided, one can leverage disentangled representation learning, which aims to reconstruct a latent, disentangled state representation from observations. Methods such as CausalVAE, DEAR, and  the reference [9] suggested by the reviewer q4Ho specifically focus on learning disentangled representations from raw visual input. Therefore, they enable our framework to be applied in such settings too. Note that, in the submitted version, we conducted a sensitivity analysis to evaluate the impact of missing EVs on performance. As shown in Figure 12 (Appendix G.4), HRCh (SSD) remains fairly robust even with up to 20\\% of EVs missing. \nWe would like to emphasize that one of the main messages of the current work is that learning the causal structure among subgoals enables more efficient training of hierarchical policies. By leveraging this structure to guide exploration, our approach can be adapted to a wide range of applications where hierarchical decision-making is required.\n___\n## 5- Reviewer: Also, compared to the baseline algorithms, the considered algorithms are clearly more simple efficient, but there seem to be high computational burden...\nRegarding computational complexity, our experiments indicate that although our method introduces some additional computation compared to some HRL baselines, this is offset by a significant reduction in the number of system probes and overall training cost. Below, we provide a runtime comparison between various methods to reach a success rate of 0.5 in Figure 6(a) of the paper:\n| **Metric**       | **Average Time (mins)** |\n|-------------------|-------------------------|\n| HER              | 249.1                   |\n| HAC              | 185.5                   |\n| OHRL             | 133.8                   |\n| CDHRL            | 352.3                   |\n| HRC_h (ours)     | 33.7                    |\n| HRC_b (ours)     | 38.1                    |\n\n**Table**: Runtime Comparison of HRL Algorithms", "claims_and_evidence": "There is reasonable evidence for the main claims, both in terms of theory and experiments.", "methods_and_evaluation_criteria": "The evaluation seems reasonable, but still limited to only one test environment. The consider grid world setup with subgoals is quite standard test environment for hierarchical RL.", "theoretical_claims": "The theoretical claims seem reasonable. Did not manage to read the proofs in the appendix in much detail, only skim through some main steps, and I did not see any issues.", "experimental_designs_or_analyses": "The consider grid world setup with subgoals is quite standard test environment for hierarchical RL. It could be better explained how the hyper-parameter tuning is done, especially for the baseline algorithms. More description is need in the plots, e.g., there seem to be some confidence bounds that are not explained.", "relation_to_broader_scientific_literature": "Mostly seems reasonable. It seems that prior work on reward machines could be relevant, they also formalize subgoal structures and use them to guide reinforcement learning by providing a structured decomposition of tasks. Reward machines leverage automata-based representations to define subgoals and shape rewards, which could complement the proposed causal discovery approach by offering an alternative way to encode and utilize hierarchical structures in HRL.\n\nIcarte, Rodrigo Toro, et al. \"Reward machines: Exploiting reward function structure in reinforcement learning.\" Journal of Artificial Intelligence Research 73 (2022): 173-208.", "essential_references_not_discussed": "not that I am aware of.", "other_strengths_and_weaknesses": "Strengths: The paper reads very well, and based on the results, the suggested approach significantly improves reasonably selected base line algorithms. The approach intuitively makes sense.\n\nWeaknesses: The problem formulation is quite limiting, it seems to cover mostly these type of grid-world examples with subgroups. I cannot see this used in any type of realistic setting, or maybe I am wrong, but it would then be interesting if some more meaningful application than simple grid-world toy environments. Also, compared to the baseline algorithms, the considered algorithms are clearly more simple efficient, but there seem to be high computational burden in the sub-goal structure discovery, it would be useful to contrast this what is done in the baseline algorithms, and maybe compare, not only in number of system probes, but also considered other dimensions.", "other_comments_or_suggestions": "none", "questions_for_authors": "none", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper explores a novel approach to Hierarchical Reinforcement Learning (HRL) by incorporating causal discovery to enhance learning efficiency in environments with sparse rewards and long-horizon tasks. The key idea is to represent the subgoal hierarchy as a causal graph and introduce an algorithm that learns this structure. Rather than relying on random subgoal exploration, the method strategically selects interventions based on their causal relevance to the final objective, reducing training time. Empirical evaluations further confirm that the proposed framework consistently outperforms existing HRL techniques regarding training efficiency. Reviewers agreed on the interesting and valuable contributions of the work.
Decision: Accept (poster)