Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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".

This 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.
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:

**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.

**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.

**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.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: **Strengths** :
This 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.
 
**Weaknesses**:  

* This approach requires the assumption that the environment dynamics are independent from the agent’s state - many situations do not warrant this assumption. 
* 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? 
 

**Empirical Analysis**: 
The 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:  


* 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.

* 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?

* 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? 
For the drawbridge experiment, what happens if we increase the subgoal budget? Does that help HAC perform better?
 

**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.



**Questions and Misc.**: 

* 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?
* 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. 

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. 

I do not see a broader impact statement, I encourage you to write one and add that to the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

(1)	Section 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, 

1a.	(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. 

1b.	(line 233-235) reads “Furthermore, while pursuing … the higher level is penalized.” I feel like this part needs more elaboration. 

1c.	(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. 

1d.	Is there any transition function used for $g^0$ from $t$ to $t+1$? It could be added to improve clarity.  

(2)	Please see the two comments below regarding experiments: 

2a.	Although 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? 

2b.	Since 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. 

(3)	To 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.   

(4)	What 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?  

Minor Comments:

(1)	(line 160): I believe should be $t + \Delta t$ instead of $s + \Delta t$. 

(2)	(line 191-192): eqn. (3) $r^1(s_t, a^1_t)$? 



----- Update -----

The 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.    


Ref.:
[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). 



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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: I warmly thank the authors for their work.

Soundness of the claims, significance and novelty of the contribution, and relevance to the NeurIPS community:

- The authors motivate clearly the need for timed sub-goals, when the environment is dynamic, through examples.

- The work is well-positioned with respect to the literature.

- 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.

Limitations of this work:

- 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.

- 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.

- 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.

- 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.

- 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.

Clarity:

- The paper is well written and overall easy to follow.


I 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.
limitations_and_societal_impact: This method does not add limitations or potential negative societal impact to existing reinforcement learning methods.
review_title: null

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)