Hierarchical Reinforcement Learning with Timed Subgoals
Authors: Nico Gürtler
Dieter Büchler
Georg Martius
Venue: NeurIPS 2021 Poster (2021)
Keywords: hierarchical reinforcement learning
reinforcement learning
subgoals
dynamic environments
long-horizon task
sparse reward
non-stationary SMDP

Abstract: Hierarchical reinforcement learning (HRL) holds great potential for sample-efficient learning on challenging long-horizon tasks. In particular, letting a higher level assign subgoals to a lower level has been shown to enable fast learning on difficult problems. However, such subgoal-based methods have been designed with static reinforcement learning environments in mind and consequently struggle with dynamic elements beyond the immediate control of the agent even though they are ubiquitous in real-world problems. In this paper, we introduce Hierarchical reinforcement learning with Timed Subgoals (HiTS), an HRL algorithm that enables the agent to adapt its timing to a dynamic environment by not only specifying what goal state is to be reached but also when. We discuss how communicating with a lower level in terms of such timed subgoals results in a more stable learning problem for the higher level. Our experiments on a range of standard benchmarks and three new challenging dynamic reinforcement learning environments show that our method is capable of sample-efficient learning where an existing state-of-the-art subgoal-based HRL method fails to learn stable solutions.

Hierarchical Reinforcement Learning With Timed Subgoals
Nico Gürtler
Dieter Büchler
Georg Martius
Max Planck Institute for Intelligent Systems Tübingen, Germany
Inguertler, dbuechler, gmartius)@tue mpg.u.ee.ppp..oo..
Abstract
Hierarchical reinforcement learning (HRL. holds great potential for sample- efficient learning challenging long-horizon tasks. In particular, letting higher level assign subgoals to a lower level has been shown to enable fast learning on difficuult problems. However, such subgoal-basce methods have been designed with static reinforcement learning environments in mind and consequently struggle with dynamic elements beyond the immediate control of the agent even though they are ubiquitous in real-world problems. In this paper, we introduce Hierarchical reinforcement learning with Timed Subgoals (HiTS), an HRL algorithm that en- ables the agent to adapt its timing to a dynamic environment by not only specifying what goal state is to be reached but also when. We discuss how communicating with a lower level terms of such timed subgoals results problem for the higher level. Our experiments on range of standard benchmarks and three new challenging dynamic reinforcement learning environments show that our method is capable of sample-efficient learning where existing state-of-the-art subgoal- based HRL method fails to learn stable solutions
more stable learning
Introduction
Hierarchical reinforcement learning (HRL) has recently begun to live up to its promise of sample- efficient learning difficult long-horizon tasks. The idea behind HRL is to break down complex problem into a hierarchy more tractable subtasks. A particularly successful approach to defining such hierarchy is to let a high-level policy choose a subgoal which low-level policy is then tasked with achieving g Due to the resulting temporal abstraction such subgoal- HRL methods have
been shown to be able to learn demanding tasks with unprecedented efficiency [1 23 19].
In order realize the full potential HRL is necessary to design algorithms that enable concurrent learning all levels of the hierarchy. However, the changing behavior of the lower level during training introduces a major difficulty. From the perspective of the higher level, the reinforcement learning environment and the policy the lower level constitute effective environment which determines what consequences its actions will have. During training, the learning progress on the lower level renders this effective environment non-stationary. If this issue is not addressed, the higher level will usually not start to learn efficiently before the lower level fully converged. This situation is similar to a manager and worker trying to solve task together while the meaning of the vocabulary they use for communication is continuously changing. Clearly, a stable solution can then only be found once the worker reacts reliably to instructions. Hence, to enable true concurrent learning, all
Videos and code, including our algorithm and the proposed dynamic environments, can be found at https///githhb.comm/marrtliiiiih
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

levels in a hierarchy should see transitions that look like they were generated by interacting with a stationary effective environment.
Existing algorithms partially mask the non-stationarity of the effective environment by replacing the subgoal chosen by the higher level appropriately in hindsight. Combined with the subtask of achieving or progressing towards the assigned subgoal as fast as possible, this approach was shown to enable fast learning on a range of challenging sparse-reward. long-horizon tasks [23 [9] What these methods do not take into account, however, is that, if adaptive temporal abstraction is used, the higher level in the hierarchy is effectively interacting with a semi-Marker decision process (SMDP), i.., transition times vary. If the objective of the lower level is to reach subgoal as fast as possible, then the amount of time that elapses until it reaches given subgoal and returns control to the higher level will decrease during training. Hence, the distribution of the transition times the higher level sees will shift to lower values which introduces an additional source of non-stationarity. When trying to quickly traverse a static environment, such as maze, this shift is in line with the overall task and will contribute to the learning progress.
Yet, as soon as dynamic elements that are beyond the immediate control of the agent are present, the situation changes radically. Consider, for example, the task of returning a tennis ball specified point on the ground by hitting it with a racket. This clearly requires the agent to time its actions so as to intercept the ball trajectory with the racket while has the right orientation and velocity. Even the higher level found a sequence of subgoals (specifying the state of the racket) that brought about the right timing, this solution would stop working as soon as the lower level learns reach them faster. This would require the higher level to choose a different and possibly longer sequence of subgoals, a process that would continue until the lower level was fully converged. Hence, exposing the higher level to a non-stationary distribution of transition times will lead to training instability and slow learning. As it is the rule rather than the exception for real-world environments to contain dynamic elements beyond the immediate control of the agent think of humans collaborating with robot or an autonomous car navigating traffic- this problem can be expected to hinder the application of HRL to real-world tasks.
In order to solve the non- stationarity issue in dynamic environments, we propose to let the higher level choose not only what subgoal is to be reached but also when. By emitting such timed subgoals, consisting of a desired subgoal and a time interval that is supposed to elapse before it is reached, the higher level has explicit control over the transition times of the SMDP it interacts with. This completely removes the non-stationn -tattottionarity of transition times and allows for stable concurrent learning in dynamic environments when combined with a technique for hiding the non-stationarity of transitions in the subgoal space. It furthermore gives the higher level explicit control over the degree of temporal abstraction, giving it more direct access to the trade off between small effective problem horizon and exercising tight control over the agent.
The main contribution of this work is to distill these insights into the formulation of a sample-efficient HRL algorithm based on timed subgoals (Section (3) which we term Hierarchical reinforcement learning with Timed Subgoals (HiTS). We demonstrate that HiTS is competitive on four standard benehmark tasks and propose three novel tasks that exemplify the challenges introduced by dynamic elements in the environment. While HiTS succeeds in solving them, prior methods fail to learn a stable solution (Section 4. In theoretical analysis, we show that the use of timed subgoals in combination with hindsight action relabeling [19] removes the non-stationarity of the SMDP generating the data the higher level is trained on (Section 3).
2 Background
2.1 Reinforcement learning and subgoal-basee hierarchical reinforcement learning
We assume the reinforcement learning problem is formulated as a Markov decision process (MDP) defined by tuple
p. Po: 7) consisting of state space S, action space A, transition probabili- ties p(s' 8, a), reward function r88, a), initial state distribution po and discount factor 7 E [0, 1). At each time step, the agent is provided with a state E S and samples an action dt E A from the distribution TT( 8x) defined by its policy æ. The environment then provides feedback in the form of reward r(se, az) E R and transitions to the next state 8:+1 S. The objective is to find an optimal

---

policy x² that maximizes the expected discounted return
(T) = E 80 -op
(rr(s ar)
(I)
In this section, we consider the subgoal-bases HRL approach to solving this problem where a lower level is tasked with achieving subgoal provided by a higher level [8] [3 19]. The lower level (index 0) acts directly on the environment by outputting a primitive action in A. whereas the higher level (index 1) proposes subgoals for level O. Hence, the action of level 1 is the subgoal for level 0, i... g" := a. Since level performs a variable number of steps T in the environment before "finishing" its subtask, level effectively interacts with a semi-Markov decision process (SMDP) [16] 17]. Its transition probabilities p( ((t++r: T St, a.) determine the distribution not only of the next state 8t+T level 1 observes but also of the time that elapses beforehand.
Existing subgoal-based algorithms reward the lower level either for being close to the subgoal 23 or for progressing in a given direction in subgoal space [31] or penalize every action that does not lead to the immediate achievement of the subgoal [1]. In this section, we consider the latter case of shortest path objective with reward
0 {
(fs (0)
( -
otherwise
for transitioning to new state s'. The function o's'.g") g²) evaluates to 1 only if s' is sufficiently close to the subgoal go in some metric (e.g. Euclidean distance). The higher level is queried for new subgoal either if the lower level achieved state sufficiently close to the subgoal or if the lower level has used up a fixed budget of actions.
2.2 Non-stationarity of the induced SMDP and hindsight action relabeling
The higher level of the hierarchy interacts with an SMDP that induced by the environment dynamics and the behaviour of the lower level. Changes to the low-level policy during training render this SMDP non-stationary which prevents the higher level from learning stable solution. Applying the recently proposed hindsight action relabeling technique can alleviate this problem for static environments [9]. We show that for dynamic environments the non-stationarity reappears.
For reasons of cumple-efficeenyy data should be reused after a policy update instead of being discarded. We therefore consider training with off off-policy algorithm that uses replay buffer. On level 1 transitions of the form (s, a ,,'', s') are being stored, containing the state s, the action a the reward r' and the state s' at the end of the subtask execution. For now, assume that the action space of level (which is equal to the goal space of level 0) is the full state space.
Due to the changing low-level policy T², the distribution of the next state s' and the reward r given fixed state action pair (s, a²) will change in the course of training. Hence, the SMDP level interacts with is non-stationary and learning stable high-level policy becomes feasible only after the lower level is fully converged. Hindsight action relabeling, as proposed in [19], addresses this problem by "pretending" that the low-level policy is already optimal, i.e., is able to reach assigned subgoals. This achieved by replacing the high-level action (corresponding to the assigned subgoal) with the state the lower level actually achieved before storing transitions in the replay buffer. If the reward depends on the action, has to be adapted as well:
(s, (s,a), r1 ,/) = (s, àl = 8 et = (s,a)),
(hindsight action relabeling).
(3)
In Fig. LA we illustrate this relabeling procedure.
Proposition 1 Applying hindsight action relabeling (Eq. 3 at level generates transitions that follow stationary state transition and reward distribution, i.e. (s,a), ,',))
pt (s,a²) ) p (s', | s,,t) where p ( 1,, s,a²) is time-independent provided that the subgoal space is equal to the full state space.
The proof is given in Suppl. A The remaining caveat is that the higher level should learn to restrict itself to subgoals which are feasible for the lower level. By conducting testing transitions [19, which
3

---

(a)
(b)
environment dynamics
hindsight action relabeling
slow reaching
unsuccessful original transition
pretend lower level has achieved essigned goal
fast reaching
Figure I: Relabeling results in stationary traeetrranittion distribution in static environments, but not in dynamic ones. (a) Action relabeling replaces the high-level action a with the achieved state s' as if the lower level was already optimal. (b) In dynamic environments with state that factorizes into a directly controllable part s and remaining part sf with dynamics, action relabeling does not prevent different environment outcomes for slow and fast low-level policies the subgoal determines only s In this example, the agent tries to reach moving platform.
are exempt from hindsight action relabeling and penalize infeasible subgoals, an appropriate incentive for the higher level can be introduced. Note that this reintroduces a non-stationarity the data in the replay buffer. For the remaining part of this section we do not consider testing transitions as they are not directly related to the issue we are concerned with.
Dynamic environments. We now consider environments with dynamic elements which are not directly controllable by the agent, for instance flying ball or a moving platform. In this case, choosing the full state space the subgoal space is problematic it would include parts of the state the agent has no control over. Consequently, the higher level would be forced to learn the full dynamics of the environment in order to be able propose feasible subgoals. In such setting it is therefore more appropriate to restrict the subgoal space to the directly controllable part of the state. Formally, assume the state space factorize S S x S into directly controllable part S", e.g. the agent, and a part S corresponding to the rest of the environment [8] 15 M.. For simplicity, assume that 5 does not influence 8 in this section, i.e., p (8" 88)= p(s"c (5,85,a)), A typical choice for subgoal space would then be S i.c. G S as it allows the lower level to focus on controlling the agent alone and allows for transfer to related tasks. However, due to the restriction of the subgoal space, Prop. dope not apply anymore.
In particular, hindsight action relabeling does not result in a stationary state-transition distribution anymore illustrated in Fig. (b). Even though relabeling the action of level according â² -====0 s/c hides the influence of the lower level on the achieved goal, the state of the environment g varies according how long the lower level was in control. This transition time will shrink during the course of training as the lower level tries to optimize shortest path objective. As consequence, the same relabeled state-action pair (st, à' 5 comes with different environmental outcomes sf+r and + depending on the learning progress of the lower level. This makes it impossible for the agent adapt its behavior the environment before the lower level is fully converged. As a consequence, existing subgoal-baze based HRL methods with adaptive temporal abstraction struggle with dynamic environments.
Hierarchical reinforcement learning with timed subgoals
An observation that points to a way out of the non-stationarity dilemma in dynamic environments that the readily controllable part often only sparsely influences the rest of the environment. In the example from the last section, the dynamics of the moving platform in Fig. (b) is not affected by the agent at all. As result, knowing the clapsed time alone completely determines the distribution of sh, no matter how complex its dynamics may be. We therefore propose to let time stand for sf and to condition the lower level on timed subgoal (g", At") where the desired time until achievement O E Noo determines when the lower level is supposed to reach the subgoal state go E 5
Hence, after being assigned timed subgoal at time t, the lower level stays in control until + At This definition of the hierarchy fixes the transition time the higher level sees to T = A Combined with the assumption that 8 evolves independently of 8f and when replacing the action at via hindsight action relabeling as discussed in [Section 2.2] this completely removes the non-stationarity of the SMDP the level is interacting with.

---

If the not directly controllable part of the environment evolves completely inde- pendently of the controllable part, i.e. if (s'c = | .",s"..") and if hindsight action relabeling is used, the transitions in the replay buffer of a higher level assigning timed subgoals to a lower level are consistent with a completely stationary SMDP. Thus, they follow a distribution Pe (8, T,,,, ft) Pt (8, a² T,, |8, à-) where p (s', T,
Proposition 2
T, 88 a+) is time fime-independent.
The proof is given in Suppl. A Intuitively, the von-stationarity is removed because hindsight action relabeling hides the influence of the low-level policy on the state 8 the agent transitions to while fixing the time interval At during which the lower level is in control makes sure that the low-level policy does not affect s²
Of course, the assumption of an environment which is not at all influenced by the agent is restrictive. However, the interactions between agent and environment are often sparse in time (e.g. in the case of racket hitting a ball). The higher level can then learn to identify the situations in which it has to exercise tight control over the agent because it about to influence the environment and align its choice of desired subgoal achievement times to them. It then has full control over the interactions between agent and environment and the episode divided into sequence of time intervals during which the assumption of independent dynamics and consequently also Proposition hoold (see Fig. 2 (a)). From this point on, the transitions added to the replay buffer of the higher level will consistent with stationary SMDP again.
3.1 The HiTS algorithm
In this section, we present Hierarchical reinforcement learning with Timed Subgoals (HiTS), an HRL algorithm for cample-efficien learning on dynamic environments. We consider two-level hierarchy in which the higher level assigns timed subgoals to the lower level as illustrated Fig. (b). For implementation details refer Suppl.
3.1.1 The higher level
The high-level policy π² (. s.g) is conditioned on the state and optionally on the episode goal and outputs a timed subgoal for At, time steps after which the higher level is queried again. The objective of the higher level is to maximize the expected environment return while maintaining temporal abstraction. It therefore receives the cumulative environment reward plus penalty -c < 0 for emitting a subgoal,
(g Ate) G x N The lower level then pursues this timed subgoal
A6-1
r 11
Σ n=0
>" ("((st 0c+n) C.
(4)
Note that for Proposition 2 hold, the reward y should neither depend on the atomic actions a, nor on the state df except for when timed subgoal is achieved.
x!
r!
timed subgoai
a = ((.Ar)-
(1",A.))
(C)))
at
at
4--1
RE++2
x
#
S
action/state
environment
At
A19
4
(a)
(b)
Figure 2: (a) The influence of S on is assumed to be sparse in time so that the higher level can align timed subgoals to it. (b) Execution of the HiTS algorithm over time.
5

---

3.1.2 The lower level
The subtask assigned to the lower level is to achieve the timed subgoal a' = (g), At.). Note that the desired achievement time At, is given relative the current time t, i.e., the goal state go is to be achieved at the time / + A/.- It is therefore decremented in each time step, A before being passed to the policy. We chose this representation as the dynamics of an agent usually do not have an explicit time dependence and consequently time intervals rather than absolute times are relevant to control. In other words, a policy conditioned on this representation of a timed subgoal in combination with a inverinvariant environment is automatically time- inverinvariant well.
A 1,
state is translated into an achieved subgoal by map f S G" In the setting of a factorized state space S = S x S the mapping may simply project onto the directly controllable part S The policy is conditioned on the observation of (e.g. s*) and the desired timed subgoal and defines a density x (- of. g.. Ate) in action space. During execution of the hierarchy, an action af E A is sampled from this distribution and passed on the environment. If the desired time until achievement has run out, i.e., if A0 = O, the higher level is queried for a new subgoal (see Fig. (b)).
During training, the lower level receives a non-zero reward only if it achieves a timed subgoal, i.e., if the achieved subgoal is sufficiently close to the desired subgoal at the desired time of achievement. Hence, the reward in transition a new state 81+1 reads
r = {
if (st+1), = and Ar 0,
(5)
otherwise,
where o: g2 - [0, 1] specifies whether the achieved and the desired subgoal are sufficiently close to each other. Note that when learning the value function of the lower level we consider 8,41 terminal state when A = 0 is reached, i.e., we do not bootstrap and set 70 = O.
3.1.3 Off-policy training and use of hindsight
In order to realize the potential of HRL for sample-efficient learning, past experience should be reused instead of being discarded after each policy update. Hence, we use the off off-policy reinforcement learning algorithm Soft Actor-Critie (SAC) [13] to train the policies on both levels. We address the non-stationarity issue by applying hindsight action relabeling to transitions before storing them in the replay buffer of the higher level.
(6) where g. f (5 A:g) denotes the subgoal the lower level achieved. Note that the desired time until achievement Atf does not have to be replaced it fixed by the higher level by definition. Under the assumption of a controllable part of the state which does not influence the rest of the environment, prrpossiiioneensuureee that the relabeled transitions in the replay buffer are consistent with completely stationary SMDP
(se, af (of Atf), res S1,()) - (sc, at == (o", (eP) (st, at)), st+21))
In practice hindsight goal relabeling according to Eq. i only applied if the desired subgoal was not achieved, i.e., if "(0". gg)) = O. This gives the higher level an idea of how precise the lower level in achieving assigned subgoals while still hiding its failures. Furthermore, while pursuing fixed percentage of timed subgoals, the lower level deterministically outputs the mean of its action distribution. If it still fails to achieve the desired goal, the higher level is penalized. Such testing transitions give the higher level an idea of the current capabilities of the low-level policy and therefore ensure that it assigns feasible subgoals 19. While these two exceptions from hindsight action relabeling reintroduce a non-stationarity into the replay buffer of the higher level, they are necessary to make respect the limitations of the lower level.
As the reward in Eq. 5 is sparse, we use Hindsight Experience Replay (HER) 2 to generalize from achieved to desired timed subgoals the lower level. The resulting hindsight goal transitions based on hindsight action transitions so as to conserve their stationarity property. When choosing an achieved subgoal at n time steps in the future hindsight goal, the low-level transition is relabeled as
0 (st, ag Tt, S1+1, ge A
(st, ag rt, 1, 00 1 (st+m) At, = n)-
To increase sample-efficiency, we also apply conventional HER on the higher level for bbaed environments.

---

(a) Platforms
(b) Drawbridge
(c) Tennis2D
Figure 3: Dynamic environments. (a) To reach the goal, the agent has to trigger the movement of platform the right time. (b) In order not to collide with the drawbridge before it opens, the agent has to time the unfurling of its sails correctly. (c) A tennis ball is to be returned by robot arm to varying goal region.
Experiments
The goal of our experimental evaluation is to compare HiTS with prior subgoal-based methods in terms of sample efficiency and stability of learning. We evaluate on four standard benchmarks as well as three new reinforcement learning environment. that exemplify the challenges introduced by dynamic elements which are beyond the immediate control of the agent (see Fig. 33. The three proposed environments require the agent find the shortest path (in terms of time steps) to the goal, ie.. the reward is -1 in every time step unless the goal was achieved (in which case it is 0). If the agent did not reach the goal after predefined number of time steps. the episode is terminated well.
Platforms. The cile--srooler--kke Platforms environment requires the agent to trigger the movement of platform just at the right time to be able to use it later on to reach the goal. Hence, the timing of the agent's actions has lasting impact on the dynamic elements in the environment which renders credit assignment in terms of primitive actions difficult. The Platforms environment is therefore despite its simplicity - quite challenging for existing state-of-the-ard methods both "flat" and hierarchical.
Drawbridge. The agent in the Drawbridge environment has to unfurl the sails of a sailing ship at the right time to pass a drawbridge immediately after it opened. Note that the agent cannot actively decelerate the ship. It is therefore essential to not accelerate too early in order not collide with the drawbridge and lose all momentum. While this control problem is quite simple, it requires the agent to wait- an ability existing subgoal- HRL methods do not intrinsically have.
Tennis2D. In the Tennis2D environment a two-dimensional robot arm with a racket as an end effector has to return a ball to specified area the ground. As it is only through the contact between the racket and the ball that the agent can influence the outcome of the episode, it is crucial that the agent learns to precisely time the movement of the arm.
4.1 Empirical evaluation and comparison to baselines
We compare HiTS with two hierarchical and one "flat" baseline algorithm. As subgoal- based HRL baseline we consider a two-level Hierarchical Actor-Critic (HAC) [19 hierarchy due to its capacity for concurrent learning and its sample efficiency. HAC uses shortest path objective with the reward specified in Eq. 2 on both levels as well as hindsight action relabeling and HER. As second baseline, consider a two-level HAC hierarchy with observation and a subgoal space that have been augmented with time. The observation is thus given by the state and the time that has passed in the current episode. (s,t)
Nzo. An augmented subgoal (g. f) G N is achieved if the state sf of the agent is sufficiently close to and the current time t is close to the desired achievement time f. The subgoals used by this baseline hierarchy consequently contain information about when they are to be achieved. The underlying HAC algorithm is left completely unchanged, however. We furthermore consider SAC combination with HER as -on-hierarchical baseline.
"The environments comply with OpenAl's gym interface and are available at httts://gituub.commaattuu
lab/HiTS
7

---

(a) UR5Reacher
(b) AntFourRooms
(c) Pendulum
(d) Ball in cup
1.00
1.00
1.00
1000
Sucress rate
0.75
0.75
0.75
retur
750
0.50
0.50
500
0.25
0.25
0.25
250
0.00
0.00
0.00
0.0
0.5
1.0
0.0
0.5
0
steps
le5
Steps
1e6
steps
1e5
steps
1e5
(e) Platforms
(f) Drawbridge
(g) Tennis2D
(h) Subgoal timing
1.00
0.6
100
-700-
mingr- t''l [ms)
return
800
success
0.4
0.25
-900
0.2
25
0.00
1000
0.0
2
0
steps
1e6
steps
le5
steps
1e7
steps 1e7
Level
HITS
HAC
SAC+HER
Level
HiTS
HAC+time
Figure 4: (a)-(g) Results on the environments. We compare HiTS against HAC, HAC with time added to the goal space and SAC. Shaded regions indicate one standard deviation over results obtained with multiple random seeds. (h) Absolute discrepancy between the time ( of contact between ball and racket and the closest subgoal achievement time 1 in an episode of Tennis2D with HiTS. One time step in the environment corresponds to 10 ms.
In order not to bias our comparison by the choice of underlying flat RL algorithm, we use our own implementation of HAC which is based on SAC. Hence, all considered hierarchies use the same flat RL algorithm. Implementation details for HAC and HiTS can be found in Suppi. B Details about training and hyperparameter optimization are given in Suppl. C Note that all results reported in this section were obtained using deterministic policies that output the mean of the action distribution on each level. The performance of the stochastic policies used during training is shown in Suppl. C
Fig. (a), (b) and (c) summarize the results three sparse-reward, long-horizon tasks introduced in 19. Note that our implementation of HAC consistently exceeds the original results reported in 19]
HiTS furthermore outperforms HAC two of these static enviromments HAC designed for. We hypothesize that in some environments the lower level might be able to generalize over A instead of having to learn how speed up movement by trial and error. In the Ball in cup environment 330 the agent has to catch a ball attached to a cup via a string. This environment can be considered dynamic the ball is not under the direct control of the agent. Since the influence of the cup on the ball is not necessarily sparse in time and the reward depends on the state of the cup, the environment violates the assumptions of Proposition] 2 Nevertheless, HiTS able to solve the task slightly faster than the strong SAC baseline while HAC suffers from a considerable variance (see Fig. (d)) Thus, in practice the second-order dynamics of an environment may allow for sufficiently tight control over a continuous interaction between agent and environment with limited number of timed subgoals. In summary, the performance of HiTS is competitive on standard benchmark tasks, even in static environments.
Fig. 4 (e) shows the average success rates of all policy hierarchies over the course of training for the Platforms environment. The SAC baseline fails to make any progress due to the lack of structured exploration and temporal abstraction. The two-level HAC hierarchy, on the other hand, begins to learn how to solve the task but stagnates at an average success rate of around 40%. Interestingly. augmenting the observation and subgoal space with absolute time does not improve the performance of the two-level HAC hierarchy but impedes it instead. As HAC is not aware of the significance of the time component, it continues to pursue an augmented subgoal even if its time component already lies in the past. As a consequence, the agent gets "stuck" on a missed augmented subgoal until the action budget of the lower level is exhausted. As this throws timing off completely and reintroduces a non-stationarity in the induced SMDP, the solutions found by the augmented HAC hierarchy are extremely brittle. Moreover, conditioning the low-level policy on absolute time introduces a spurious explicit time dependence. In contrast to this, HiTS is adapted to the of timed subgoals: It
8

---

conditions the lower level on the time interval that is left until the next timed subgoal is to be achieved. Additionally, it always queries the higher level for a new timed subgoal when this time has run out and can therefore recover from missing timed subgoal. HiTS consequently makes fast progress on the Platforms environment and reaches an asymptotic success rate of around 86%.
A look at the learning progress of individual runs of the two-level HAC hierarchy (see Suppl. C reveals that it does learn solve the task in some cases. However, these solutions typically deteriorate quickly due to the learning progress on the lower level and the resulting non-stationarity of the SMDP as discussed in [ection In contrast to this, the performance of runs using the HiTS hierarchy is much more stable due to the use of timed subgoals as discussed in Section 3
The challenge in the Drawbridge environment is to reach the goal (the end of the river) in the shortest possible time, which requires the right timing in order not to collide with the yet unopened bridge. Fig. f (f) shows the average return of all algorithms a successful episode it is equal to minus the time needed to reach the goal while an unsuccessful episode corresponds to a value of -000 (the maximum episode length). While SAC quickly learns to immediately unfurl the sails, its local exploration in action space never finds the optimal timing. The two-level HAC hierarchy cannot reproduce the ideal behavior of waiting before unfurling the sails after the lower level has become fast at achieving subgoals and therefore stagnates at an even lower return. Increasing the subgoal budget would alleviate this problem but decrease temporal abstraction. Hence, a recursively optimal [4] HAC hierarchy may be far from optimal with respect to the environment MDP if the subgoal space is not equal to the full state space. HiTS does not suffer from this problem as the environment dynamics are independent of the agent's 's state in this case. Conditioning the lower level on time is therefore sufficient for HiTS to learn to time the passage through the drawbridge correctly.
the Drawbridge environment. In
In contrast to the environments discussed so far, controlling the agent in the Tennis2D environment is challenging as actions contain raw torques applied to the joints of the robot arm. Moreover, the trajectory and spin of the ball vary considerably from episode to episode. Nevertheless, HAC initially manages to return a small fraction of the balls to the goal area (see Fig. 4 (g)). Its performance decreases, however, after about 1.5 million time steps as the lower level has become too fast and a short sequence of subgoals cannot reproduce precisely timed movements anymore. As assigning credit for returning a ball to torques is challenging, SAC only learns slowly. The HiTS hierarchy can directly assign credit to timed subgoal, i.e., to what robot state was to be achieved when. Fig. (h) shows how the discrepancy between the moment of contact between ball and racket and the closest achievement time of a timed subgoal decreases during training. The higher level can therefore exercise full control over the robot arm when it matters. Moreover, the alignment of a timed subgoal with the contact between racket and ball implies that the induced SMDP is close to stationary. As consequence, HiTS achieves a performance of around 40% on average within 20 million time steps. Also note that HiTS uses more timed subgoals around the time of contact between racket and ball as shown in Fig. S3 Thus, its temporal abstraction is adapted to the task.
The success rates of HiTS on Platforms and Tennis2D depicted in Fig. (e) and (g) exhibit large variance over random seeds. This can mostly be attributed to the environments themselves in which a small change in the behavior of the agent can have big impact on its performance. In contrast to this, the variance of HiTS on the standard benchmarks shown in Fig. 4 (a)-(d) is much smaller. A schedule for the entropy coefficient target entropy and the learning rate of HiTS could help with achieving proper convergence on the more challenging dynamic environments.
Related work
The key role of abstraction in solving hong-horizon, sparse-reward tasks has been recognized early on in the RL community 28 25 29 The options framework [29 26 formalizes the idea of augmenting the action space with closed-loop actívities that take over control for an extended period of time. The resulting temporal abstraction facilitates credit assignment for policy selecting among options. While options were originally handcrafted or learned separately 4 26). the option-critic architecture 33] jointly learns the parameters of the options and a policy over options, However, to keep up stable temporal abstraction in this approach, regularization is necessary 14). related approach to learning a hierarchy is based on the idea that a high-level controller should have a repertoire of skills to choose from or to modulate 12
10 The set of skills often
9

---

pretrained using an auxiliary reward where diversity is encouraged by an information theoretic term
[ 10.
Alternatively, the lower level of the hierarchy may be trained to reach an assigned subgoal 27
g
26 22] In this setting, the lower level can be rewarded for moving in a specified direction in goal
space 31] for being close to the goal state (23) or for achieving goal state up to tolerance [9]
In the latter case has been achieved or a fixed action budget is exhausted [9]. In contrast to this, using a dense reward
natural query the higher level for a new subgoal only when the current one
usually tied a fixed temporal abstraction scheme [3 The goal space can either be learned
31 24
or predefined using domain knowledge 23 19.
It has been observed in the context of options 229 26 well as subgoal-based methods 23
19 that
the higher level in a hierarchy effectively interacts with a non-stationary SMDP. In order to enable off- off-policy learning from stored high-level transitions, Nachum al. 2 approximately determine high-level actions that are likely to reproduce the stored behavior of the lower level under the current low-level policy. This procedure has to be repeated after each update the low-level policy and introduces noise due to the use of sampling in the approximation. Levy et al. [19] address the non- stationarity issue by hindsight action relabeling as discussed in [Section 2 None of these methods take into account, however, that, when using adaptive temporal abstraction as in [19]. the transition times of the SMDP change over the course of training and consequently introduce an additional source of non non-stationarity which prevents sample-efficiens learning in dynamic environments. Although in Blaes al. [5] the environment contains dynamic objects, they come to rest quickly not manipulated by the agent, such that the non-stationarity issue does not need to be addressed.
As hindsight action relabeling hides the limitations of the current low-level policy, the higher level may learn to choose infeasible subgoals. Levy et al. [19] therefore penalize the higher level when the lower level fails reach subgoal. We adopt this method as it is general and simple. Zhang et al. [33 restrict the subgoal to a k-step adjacent region via an adjacency loss. As the loss is based on an adjacency network distilled from an adjacency matrix, incorporating this approach into HiTS may improve sample efficiency, albeit only on ow-dimensional subgoal spaces as it requires discretization.
In the context of robotics, via- via-points are used specify sequence of configurations robot should move through, often also specifying when these configurations are to be reached [21]. They therefore serve similar purpose as timed subgoals. The difference lies in how they are used. A classic approach in robotics would be to first obtain a controller for the robot, to then specify via-points, interpolate between them, and use the controller to follow the resulting trajectory. Hence, concurrent learning is involved and the non-stationarity problem does not occur.
6 Conclusion
We present an HRL algorithm designed for sample-efficient learning in dynamic environments. In a theoretical analysis. we show how its use of timed subgoals in conjunction with hindsight action relabeling attenuates the non-stationarity problem of HRL even when the lower level is not conditioned on the full state. Moreover, our experiments demonstrate that our method is competitive on a range of standard benchmark tasks and outperforms existing state-of-the-arr baselines in terms of sample complexity and stability on three new challenging dynamic tasks.
The effectiveness of HRL generally depends on the structure of the environment and our method is no exception in this regard. In particular, we consider environments with a directly controllable part which only sparsely influences the rest. This assumption ensures that temporal abstraction is compatible with stable concurrent learning. Furthermore, our practical algorithm still contains minor sources of non- con-stationarity like testing transitions. Nevertheless, our experiments demonstrate that our method performs well even when deviating from the idealized setting.
An interesting direction for future work the detection of interactions between agent and environment and the active alignment of timed subgoats to them. Furthermore, two or more levels which pursue timed subgoals may enable efficient learning on more challenging dynamic long-horizon tasks.
10

---

Acknowledgments and Disclosure of Funding
We would like thank Bernhard Schölkopf, Jan Peters, Alexander Neitz, Giambattista Parascandolo, Diego Agudelo España, Hsiao-Ru Pan, Simon Guist, Sebastian Gomez-Grozalez,, Sebastian Blaes and Pavel Kolev for their valuable feedback.
Georg Martius is a member of the Machine Learning Cluster of Excellence, EXC number 2064/1 Project number 390727645. We acknowledge the support from the German Federal Ministry of Education and Research (BMBF) through the Tübingen Al Center (FKZ: 01I11809BB..
References
[1] T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama. Optuna: A next-generation hyper- parameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2623-2631, 2019.
[2] M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, Welinder, B. McGrew, Tobin, O. P. Abbeel, and W. 7aremba. Hindsight experience replay. In Advances in neural information processing systems, pages 5048-5058, 2017.
[3] P.-L. Bacon, J. Harb, and Precup. The option-critic architecture. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[4] A. G. Barto and S. Mahadevan. Recent advances in hierarchical reinforcement leatfornemmetttaaingggg.. Discrete event dynamic systems, 13(1):41-77, 2003.
[5] S. Blaes, M. Vlastelica, J.-J. Zhu, and G. Martius. Control What You Can: Intrinsically motivated task-planning agent. In Advances in Neural Information Processing Systems (NeurIPS 2019), pages 12520-12531. Curran Associates, Inc., Dec. 2019.
[6] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym, 2016.
[7] C. Daniel, G. Neumann, and J. Peters. Hierarchical relative entropy policy search. In Artificial Intelligence and Statistics, pages 273-281. PMLR, 2012.
[8] Dayan and G. E. Hinton. Feudal reinforcement learning. In Advances in neural information processing systems, pages 271 271,278, 1993.
[9] T. G. Dietterich. Hierarchical reinforcement learning with the maxq value function decomposi- tion. Journal of artificial intelligence research, 13:227-303, 2000.
[10] B. Eysenbach, A. Gupta, Ibarz, and S. Levine. Diversity is all you need: Learning skills without a reward function. In International Conference on Learning Representations, 2019.
[11] C. Florensa, Y. Duan, and P. Abbeel. Stochastic neural networks for hierarchical reinforcement learning, arXiv preprint 10..iv:1004000000
2017.
[12] T. Haarnoja, K. Hartikainen, P. Abbeel, and S. Levine. Latent space policies for hierarchical reinforcement learning. In International Conference on Muchine Learning, pages 1851-1860. PMLR, 2018.
[13] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint 1rXiv:1801.01222 2018.
[14] J. Harb, P.-L. Bacon, M. Klissarov, and D. Precup. When waiting is not option: Learning options with a deliberation cost. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[15) N. Heess, G. Wayne, Y. Tassa, T. Lillicrap, M. Riedmiller, and D. Silver. Learning and transfer of modulated locomotor controllers. arXiv preprint 1rXiv: 2016.
[16] R. Howard. Gemi-markovian decision processes. Proc. Intern. Statist. Inst., page 625-652. 1963.
[17] Q. Hu and W. Yue. Semi-Markov Decision Processes, pages 105-120. Springer US, Boston, MA, 2008. doi: 10.
[18] G. Konidaris and A. Barto. Autonomous shaping: Knowledge transfer in reinforcement learning.
In Proceedings of the 23rd international conference on Machine learning, pages 489 496, 2006.

---

[19] A. Levy, G. Konidaris, R. Platt, and K. Saenko. Learning Mevei-Level Hierarchies with Hindsight. In International Conference on Learning Representations, 2019.
[20] T. P. Lillierap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra. Continuous control with deep reinforcement learning. arXiv preprint
2015.
[21] K. M. Lynch and F. C. Park. Modern Robotics. Cambridge University Press, 2017.
[22] A. McGovem and A. G. Barto, Automatic discovery of subgoals in reinforcement learning using diverse density. In Proceedings of the 18th International Conference on Machine Learning.
pages 361-368, 2001.
[23] O. Nachum, S. S. Gu, H. Lee, and S. Levine. Data-efficient hierarchical reinforcement learning.
In Advances in Neural Information Processing Systems, pages 3303-3313, 2018.
[24] O. Nachum, S. Gu, H. Lee, and S. Levine. Near-optimal representation learning for hierarchical reinforcement learning. In International Conference Learning Representations, 2019.
[25] R. Parr and S. Russell. Reinforcement learning with hierarchies of machines. Advances in neural information processing systems, pages 1043-1049, 1998.
[26] D. Precup. Temporal abstraction in reinforcement learning. University of Massachusetts Amherst, 2000.
[27] Schmidhuber. Learning to generate sub-goals for action sequences. In Artificial neural networks, pages 967-972, 1991.
[28] A. Schwartz and S. Thrun. Finding structure in reinforcement learning. Advances in neural information processing systems, 7:385-392, 1995.
[29] R. S. Sutton, D. Precup, and S. Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 1 11((12))181-2111 1999.
[30] Y. Tassa, S. Tunyasuvunakool, A. Muldal, Y. Doron, Liu, S. Bohez, J. Merel, T. Erez,
T. Lillicrap. and N. Heess. dm control: Software and tasks for continuous control, 2020.
[31] A. S. Vezhnevets, S. Osindero, T. Schaul, N. Heess, M. Jaderberg, D. Silver, and K. Kavukcuoglu. FeUdal networks for hierarchical reinforcement learning. D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Pro- ceedings of Machine Learning Research, pages 3540-3549, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
[32] J. Weng, H. Chen, A. Dubureq, K. You, M. Zhang, D. Yan, H. Su, and J. Zhu. Tianshou. https://gi thub. com/ thu m0lm mol/tianshou 2020.
[33] T. Zhang, S. Guo, Tan, X. Hu, and F. Chen. Generating adjacency-constrained subgoals in hierarchical reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21579-21590. Curran Associates, Inc., 2020.
12


Reviews:
[{"review_id": "neiNZUSOtlM", "reviewer": "Reviewer_Auot", "summary": "The authors introduce HiTS, an HRL algorithm in which the high-level policy communicates not only which goal to achieve to the low-level policy but also when to achieve it. This feature enables the agent to adapt to dynamic environments that require planning over long horizons. The authors also discuss to what extent communicating timed sub-goals results in more stable learning for the high-level policy. The authors show that HiTS successfully learn on a set of 3 benchmarks, that have been designed to be dynamic and require planning, where classical sub-goals HRL method fail to learn stable solutions.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I warmly thank the authors for their work.\n\nSoundness of the claims, significance and novelty of the contribution, and relevance to the NeurIPS community:\n\n- The authors motivate clearly the need for timed sub-goals, when the environment is dynamic, through examples.\n\n- The work is well-positioned with respect to the literature.\n\n- The 3 benchmarks are sound with respect to the problem at hand in this paper. HiTS clearly outperforms HAC in these environments, motivating the need for timed sub-goals in this setting.\n\nLimitations of this work:\n\n- At the beginning of the introduction, the authors argue that to realize the full potential of HRL, it is necessary to enable concurrent learning on all levels of hierarchy and present HiTS as a way to do so. They argue that timed sub-goals reduces the non-stationarity of the induced SMDP and thus stabilize learning for any HRL problem. However, in the rest of the paper, the method seemed to be designed specifically for dynamic environments. I think it would be important either to focus on dynamic environments only or to spend more time validating that timed sub-goals is important for any HRL problem, i.e for environments that require planning over long time horizons but are static.\n\n- In the appendix, the authors show that HiTS is clearly outperformed by HAC on the AntFourRooms environment which interrogates whether timed sub-goals are also important when the environment is not dynamic. It would be interesting to further discuss this point in the paper.\n\n- The three environments might be more carefully detailed in the experimental sections. Notably, the observation space, action space, goal space, and reward functions should be more precisely described.\n\n- The second HAC baseline for which the high-level policy communicates timed sub-goals to the low-level policy remains unclear to me. I do not get precisely what is the difference with HiTS. I think it would be worth allocating space in the paper to precise the difference between the two methods.\n\n- It is also unclear to me how the time interval is communicated between the two levels. Is it under the form of a scalar or a one-hot representation? In general, the different components of the agent and the neural architecture used might be more detailed with maybe explicating figures.\n\nClarity:\n\n- The paper is well written and overall easy to follow.\n\n\nI think that in this form this paper is marginally below the acceptance threshold but I am willing to increase my score if the authors address the limitations I mentioned.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This method does not add limitations or potential negative societal impact to existing reinforcement learning methods. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "mvPyHsY8GmU", "reviewer": "Reviewer_uHJN", "summary": "This paper proposes a new method for HRL in which the higher level chooses both a subgoal and a time at which the subgoal should be achieved (\"Hierarchical RL with Timed Subgoals, or HITS). The main claim of the work is stated early on: \"Hence, the use of timed subgoals extends the class of tasks that can be solved efficiently by subgoal-based HRL methods\".\n\nThis claim is motivated by several elements. First, the paper identifies an issue of non-stationarity in dynamic environments: the higher level's reliance on the lower level's behavior induces a particular kind of non-stationarity; as learning progresses, the lower level behaviors will improve, thereby changing the outcome of the same high level actions. This discrepency motivates the claim that \"all levels in a hierarchy should see transitions that look like they were generated by interacting with a stationary effective environment.\" Alongside this, it is noted that dynamic environments with elements not controlled by the agent are particularly challenging as they further introduce non-stationarity. Second, the paper focuses on a decomposition of state into the controlled and uncontrolled parts of state, which allows for subgoals to concentrate on the controlled aspects of the environment. These two points are examined to motivate timed subgoals alongside hindsight relabeling techniques to form the core of HITS. Otherwise, by my reading, HITS is quite simple (which I take to be a virtue). Three new benchmark domains are introduced that feature time-based reasoning, such as a ship that needs to carefully furl its sail in order to quickly pass through a drawbridge. These domains are chosen to highlight the positive aspects of HITS, and to differentiate what HITS does differently from other HRL methods. The results quite clearly demonstrate that HITS is well suited to solve these domains.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper reads well, and to my knowledge the specific proposal of including a completion-time in the high level is new. The domains introduced showcase the strengths of HITS, but I also worry that they are too focused on the specific characteristics that HITS is developed for. In other words, I believe it would be a useful empirical test to also showcase HITS on more traditional domains to examine the impact that the added timed-subgoals have in general. Do they lead to degenerate solutions? This suggestion feeds into my overall assessment of the paper: the main claim of the work is that timed subgoals can help HRL. I believe the chosen domains and experiments demonstrate that timed subgoals help when certain well chosen properties are present. After reading, I am unclear how big of a problem these non-stationariy issues are in general, and it is unclear how general timed subgoals are as a solution. In more detail:\n\n**originality** As stated, to my knowledge this particular combination is novel. Naturally the paper borrows a lot from Levy et al. 2018, but it is transparent about this fact. There is perhaps some overlap with work on Linear Temporal Logic and Reward Machines in RL, which both focus on learning to solve tasks that involve particular, possibly complex, temporal sequences. See Camacho et al. 2017 (\"LTL and Beyond\") or Littman et al. 2017 (\"Environment-Independent Task Specifications via GLTL\"). I don't believe these need to be cited or discussed in the work, but the insights there might be useful.\n\n**clarity** I found the paper to be relatively clear, though I do believe that the stated propositions are stated too abstractly. I appreciate not getting bogged down by details but it is difficult to infer the precise meaning of these statements without further formalism. For instance, what does \"consistent\" in Prop. 2 mean? What is the nature of the stationary SMDP? Separately, I believe the _precise_ nature of the \"problem\" described in the introduction could be formalised and stated more precisely. Several aspects are mentioned: That the environment contains dynamic elements no controlled by the agent and that the learning dynamics in high & low level induce a particular kind of non-stationarity. I believe honing in on the precise problem would benefit the work. It is hard to tell how general this problem is, as I found the essence of the problem to still be unclear.\n\n**significance** As stated above, my main reaction is that it is unclear how significant the proposed problem is, and thus, how useful or general the proposed solution is. For this reason my assessment is that the significance of the work is on the lower side.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "OVKbmiEssz", "reviewer": "Reviewer_3XHt", "summary": "This paper presents a new framework for subgoal-based HRL where the high-level chooses not only what subgoal to be reached but also when to reach the subgoal, i.e., a timed subgoal, for the lower-level. By emitting such timed subgoals, the non-stationarity of transition times during learning at the high-level can be removed, which is supported by theoretical analysis, and thus, making it possible for stable learning in dynamic environments. Combining timed subgoals with hindsight action relabeling, a practical algorithm HiTS is proposed and it outperforms baseline methods on a set of dynamic environments. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In HRL, the non-stationarity at the high-level learning is a well-known problem that hinders concurrent learning and learning efficiency. The problem gets even worse when learning in dynamic environments as fully analyzed in the paper. The proposed solution, which generates timed subgoals to the lower-level, is a new and interesting idea, highlighting the importance of communication and coordination between the two levels for effective learning in a complex environment. Overall, the paper is well-written and technically sound. However, I feel that some parts of the paper, e.g., Section 3.1, can be better organized and the experimental results could be further refined to improve the clarity and the overall quality of the paper. Please see the list of items below for detailed comments, and I am willing to adjust my evaluation should these problems be addressed or fully discussed. \n\n(1)\tSection 3.1 could be better organized to improve clarity. I spent most of the time understanding all the algorithmic details in section 3.1. It could be better to break down this section into subsections where each subsection highlights and introduces one aspect of the algorithm. More specifically, \n\n1a.\t(line 215-216) says “the lower level receives a non-zero reward only if it achieves a timed subgoal”. This is inconsistent with the equation above line 97, which assigns zero rewards to the lower-level when near the subgoal. \n\n1b.\t(line 233-235) reads “Furthermore, while pursuing … the higher level is penalized.” I feel like this part needs more elaboration. \n\n1c.\t(line 237-239) reads “While these two exceptions … respect the limitations of the lower level”. It would be better to clearly mention that this part is the limitation of the proposed algorithm. \n\n1d.\tIs there any transition function used for $g^0$ from $t$ to $t+1$? It could be added to improve clarity.  \n\n(2)\tPlease see the two comments below regarding experiments: \n\n2a.\tAlthough discussed in the paper, the high variance of HiTS in the experiments does call for further investigation and analysis. How many random seeds are used for generating the results (I don’t think it is mentioned in the paper)? Does that mean the non-stationarity in high-level learning still exists? Is the performance dependent on choosing the right seed? Can this be alleviated by conservative exploration as hypothesized in the paper? \n\n2b.\tSince the three dynamic environments are likely to be new to the readers and they all focus on learning the “right timing”, it worth evaluating and comparing HiTS on commonly-used benchmark environments as well. I would suggest bringing the additional static experiments on UR5Reacher and AntFourRooms back to the main paper, which are more familiar by the readers. Can “increasing the subgoal budget” improve the learning efficiency for HiTS on AntFourRooms? It would be interesting to see and compare results with different budgets, and see how well HiTS can perform on static benchmarks. \n\n(3)\tTo my understanding, timed subgoals highlight the need for communication between high- and lower-levels for concurrent and effective learning. Can other forms of communication (partly) address the non-stationarity issue in practice? Mentioned in (line 338 – 341), generating feasible subgoals seems to be important for learning efficiency. Recently, [1] proposed an algorithm, HRAC, that generates subgoals that are k-step adjacent to the current state, improving the reachability of subgoals at the lower-level. Since the adjacency is learned by sampled trajectory data and updated periodically, this also introduces a form of communication between the two levels. As the lower-level improves, the adjacent region would expand accordingly. What can be missing for applying adjacency constraints in subgoals in dynamic environments? I feel it could be an interesting discussion to add to the paper, highlighting the necessity of timed subgoals and learning timing.   \n\n(4)\tWhat is the rationale behind only assigning positive rewards when reaching the subgoal exactly at $\\Delta t = 0$ (eqn. (4))? What would happen if the agent reached the goal before using up the timesteps? Any bonus? For example, if $\\Delta t = 1$ and the agent reached the subgoal already, one could adjust the data and store $\\Delta t^0_t = \\Delta t^0_t – 1$ in the buffer, indicating the agent reached the goal sooner than expected. What might be wrong with this design, i.e., rewarding the lower-level if reaching the goal within $\\Delta t$ steps?  \n\nMinor Comments:\n\n(1)\t(line 160): I believe should be $t + \\Delta t$ instead of $s + \\Delta t$. \n\n(2)\t(line 191-192): eqn. (3) $r^1(s_t, a^1_t)$? \n\n\n\n----- Update -----\n\nThe authors have addressed my questions in their response and provided additional experiments on static benchmark environments. The results look promising, and I have raised my score accordingly.    \n\n\nRef.:\n[1] Zhang, Tianren, Shangqi Guo, Tian Tan, Xiaolin Hu, and Feng Chen. \"Generating Adjacency-Constrained Subgoals in Hierarchical Reinforcement Learning.\" arXiv preprint arXiv:2006.11485 (2020). \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitation but did not address negative social impact. The proposed algorithm helps improve learning in complex and long-horizon dynamic environments. As an illustrative example, what if the algorithm was used by a malicious user to build a robot? Targeting rewards that lead to some harmful behaviors for a society (in a dynamic environment)? I believe such kind of scenario could be discussed. In addition, what can and should be done to prevent it from happening? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "6OyE9X5vfa2", "reviewer": "Reviewer_z3aR", "summary": "The paper proposes to study HRL with timed goals wherein the high level controller can not only specify subgoals but also the time when it should be reached. The overarching goal of the work is to enable HRL methods to adapt better to non-stationarity. The key contributions of this work are 1) propose the idea of timed subgoals to address the adverse impact of non-stationarity and ever changing low level behaviors on the overall policy, 2) distil these insights into an HRL algorithm and introduce HiTS as the proposed algorithm, 3) introduce tasks where such challenges are seen, and 4) the empirical analysis shows sample-efficient learning which results in stable agents as opposed to existing methods which fail. Finally, the authors also show theoretically the utility of the timed-subgoals in eliminating non-stationarity in the data generating process for the high level controller.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths** :\nThis work tackles a very interesting problem on how HRL algorithms should be designed for changing behaviors at lower levels during training. The dynamic environments bring this problem to a forefront as the low level policies continue to adapt - thus resulting in the high level controller unable to learn effectively either as the transition times might vary. The paper presents new creative ideas to address such challenges through the notion of time-subgoals. While existing methods such as hindsight action relabeling techniques can alleviate this problem for static environments, this work shows that for dynamic environments, action relabeling does not prevent different environment outcomes for slow and fast low-level policies. This is accomplished by restricting the subgoal space to the directly controllable part of the state (sc) , and conditioning the lower level on a timed subgoal, replacing the external component of the state with time.\n \n**Weaknesses**:  \n\n* This approach requires the assumption that the environment dynamics are independent from the agent’s state - many situations do not warrant this assumption. \n* Moreover an additional assumption made is that when replacing the action via hindsight, action relabeling completely removes the non-stationarity of the SMDP the level is interacting with. Would it be possible to relax the first assumption in this framework as it stands? \n \n\n**Empirical Analysis**: \nThe experiments test HiTS sample efficiency and stability on three different tasks including platforms, drawbridge, and tennis 2D. All of these tasks require the agent to be precise in the timing of certain actions. The experiments in Fig 4 show that the proposed algorithm is able to outperform the baselines and give evidence for 1) aided exploration via temporal abstraction and 2) Stability induced via timed subgoals. However, I have the following concerns and questions:  \n\n\n* Re the claim that ”higher level explicit control over the degree of temporal abstraction, giving it more direct access to the tradeoff between a small effective problem horizon and exercising tight control over the agent.” How do you show this in your experiments? Is there an analysis that can support this concretely?  In particular, the phrase tight control over the agent is very loosely used unless I am missing something. It would be useful to rephrase this.\n\n* Re the claim that “The explicit representation of timing greatly facilitates credit assignment in these cases.”  To support this claim, Fig. 5 shows how the discrepancy between the moment of contact between ball and racket and the closest achievement time of a timed subgoal- but it is not very clear to me how this demonstrates the credit is assigned correctly? Can you provide additional analysis to support this claim? It would add value to the paper, if you can show a plot with the ground truth of when a robot state should be achieved vs the one determined by the proposed approach?\n\n* Re “interestingly, augmenting the state, observation and goal spaces with absolute time does not improve the performance of the two-level HAC hierarchy but impedes it instead.” This seems a bit counterintuitive to me atleast. Do you have any insights on why this would hurt HAC as opposed to helping it? \nFor the drawbridge experiment, what happens if we increase the subgoal budget? Does that help HAC perform better?\n \n\n**Writing and Presentation**: The paper is very well written and ideas are clearly explained. I find the presentation of the main ideas, especially motivation very clear.\n\n\n\n**Questions and Misc.**: \n\n* Re “This definition of the hierarchy fixes the transition time the higher level sees \\tau” Is my understanding correct that this would result in fixed subgoal lengths or that each subgoal can still be of variable lengths?\n* Re “ The higher level can then learn to identify the situations in which it has to exercise tight control over the agent because it is about to influence the environment and align its choice of desired subgoal achievement times to them.” How is this done at the higher level precisely? While the details in the Sec 3.1 are clear, it would be great if you can expand on the intuition behind how does the higher level really model the dynamic component of the environment, as that is what translates to specifying the timed-subgoals. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While Sec 3.1 and Sec 4.1 cover limitations, it is hard to find at a first look where limitations are discussed in rigorous detail. I would suggest adding a paragraph in the conclusion section. \n\nI do not see a broader impact statement, I encourage you to write one and add that to the paper.\n", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper tackles hierarchical learning in dynamic environments. Dynamic environments induce non-stationarity from the point of view of higher level policies, as the effect of high-level actions depends on the low-level policies that are learned concurrently. Earlier work has tried to address this by re-labelling past actions. However, in dynamic environments this is not sufficient, as background processes might continue further or less far dependent on how *fast* the lower level policy reaches its goal. The submitted manuscript investigates the use of 'timed sub goals' to address this, having sub-policies attain their goals at a specified time. 

The reviewers are mixed on this submissions, with the reviewers having shifted towards a 'marginal accept' average. The main points by the reviewers are:
- The main ideas are mostly considered relevant, interesting, and original
- The execution of experiments and motivation of design decisions is technically sound. One reviewer wrote that the problem definition could be more precise. 
- The paper is well written
- A main criticism with the original manuscript by a majority of the reviewers was that the chosen experiments insufficiently support the main claims made in the paper. 
- - One of the main points is that the paper aims to address a common problem in hierarchical learning in all kinds of dynamic environments, whereas the experiments focus on very specific problems where precise timing is very important. While these are highly illustrative, they do not make it clear whether the method also brings benefits on problems that are dynamic but do not rely that much on very precise timing. (The paper does show results are competitive on static MDPs, with a small gap to methods specifically for that setting as expected). 
- - furthermore, some concerns exists regarding the paper not being tested on common benchmark, the high variance in results, and the assumptions made.
- - The authors have since provided additional results on more standard settings, with 'HiTS' outperforming 'SAC' on 2 out of 4 environments (with results being practically the same as the baselines on a third environment, 'ball in a cup'). One concern about the additional evaluations is that it is hard to understand what factors cause the difference in performance - e.g., is it really in the timing of the subgoal, or in some other aspect of the difference between methods (e.g. reward structure for lower level policy, ...). Unfortunately, the author's reply came close to the end of the discussion period and so these aspects could not be fully discussed.

Taken together, I think that although the ideas are interesting and original, currently there are still some doubt about the thoroughness of the support of the  claims of the paper.

As an aside, one reviewer brought up an interesting point that the performance of timed subgoals might indicate that some form of communication is needed, but that other types of communication might work as well. It was mentioned as being unclear whether timed subgoal is indeed the best type of communication needed. This seems to be an interesting point for future work, although in the absence of other communication-based strategies of the problem it's not a comparison that I would have expected in the current paper. 
Decision: Accept (Poster)