Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on the exploration issue for a reinforcement learning (RL) agent in an environment with a long horizon and high-dimensional input, particularly the procedurally generated environment. To address the issue, this work proposes a structured exploration with achievements (SEA) method by discovering the finite and fixed underlying structure in the procedurally generated environment. Finally, experiments were conducted on Crafter and TreeMaze, with results demonstrating its effectiveness in terms of achievement learning, graph recovery, and sub-policy learning and exploration.
strength_and_weaknesses: Strengths:
- Exploration in a complex environment with long horizon and high-dimensional input can be challenging for RL. This is an interesting work where it learns achievements representation in the procedurally generated environment, builds the achievement dependency graph based on clustered achievements, and learn sub-policies for each achievement with the meta-controller. It would be intriguing to the community of representation learning in RL.



Weaknesses:
- The presentation of the paper could be improved. For example, what are the differences between the procedurally generated environment and the partially observable environment? Or are they the same? What is an finite internal achievement system? Does this require the task to be well-defined? What's the difference between the setting of achievement-based environments and "sparse and delayed reward signals" setting in [1]? Is the achievements design equivalent to the subgoal/subtask design? What's the unlock rate? How does the learned representation & clustering performance affect the sub-policy learning? There lacks more details for this.
- The literature review should include some of previous work regarding subgoal/subtask learning with Hierarchical RL, such as [1,2,3]. All the work of [1,2,3] divides a complex task into sub-tasks, but they did in different ways. There are some shared intuitions in common between this work and [1,2,3], such as task decomposition, goal-directed policy, meta-controller, etc. In particularly, [3] used unsupervised learning method for learning the representation and there needs a discussion on the differences.
- Its current novelty is somewhat incremental to me. 


References:
- [1] Kulkarni, T. D., Narasimhan, K., Saeedi, A., & Tenenbaum, J. (2016). Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. Advances in neural information processing systems, 29.
- [2] Lyu, D., Yang, F., Liu, B., & Gustafson, S. (2019, July). SDRL: interpretable and data-efficient deep reinforcement learning leveraging symbolic planning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 2970-2977).
- [3] Rafati, J., & Noelle, D. C. (2019, July). Learning representations in model-free hierarchical reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 10009-10010).
clarity,_quality,_novelty_and_reproducibility: - It feels to me that both the paper writing and clarity could be improved as I mentioned in the main Weaknesses. Regarding the novelty, I feel its contribution is limited.
summary_of_the_review: According to my comments in both the main Weaknesses and the section of Clarity, Quality, Novelty, I feel this is a paper where reasons to reject outweigh reasons to accept. But I would like to change my score if there is a misunderstanding.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a method for learning the “achievement” (i.e. subtask) structure of an environment from offline data, with sparse rewards indicating when achievements are attained. First, an achievement representation is learned using a contrastive-learning type procedure over the transitions where achievements were attained in the offline data. Next, using an achievement classifier constructed from the learned representation, a dependency structure of achievements is built, represented as a DAG. This dependency structure is used to inform more effective exploration over achievements, as opposed to the default random exploration of the meta-controller. The authors demonstrate the efficacy of their approach on tasks within two achievement-oriented environments, relative to baselines that do not take advantage of the achievement structure.
strength_and_weaknesses: Strengths: 

* The motivation is good, and the method is very intuitive given the problem statement. 

* The paper is generally well-written and the method is clearly explained. 

* The chosen evaluation environments are appropriate given the motivation, and the method appears to significantly outperform the baselines, especially on the more challenging (longer-horizon) tasks. 

Weaknesses/questions:

* A number of crucial details are missing (and are not to be found even in the Appendix). For example, the authors state they “use a controller that topologically traverses the dependency graph. Specifically, at the beginning of the episode or upon completion of any achievement, the controller randomly selects a unfinished achievement whose dependent achievements have all been completed. In our implementation, we also bias the selection probability towards a direct child of the last completed achievement to provide continuity.” How is this bias implemented/parameterized? Another example is that $\phi$ does not appear to be discussed in detail; i.e. how it is implemented/parameterized. 

  * Apart from knowing these kinds of implementation details, it would also be useful to see how robust the method is to them in the evaluation section (e.g. varying the hyperparameter controlling how the selection probability is biased). 

* There are a number of crucial missing related works that should be at the very least be discussed, and potentially included in the evaluation section: 

  * [1] This is a highly relevant work with a very similar setting, motivation, and evaluation environments. They use environment “milestone signals” (similar to sparse rewards in this work) to learn an an “affordance classifier” (like the achievement classifier in this work) to improve exploration at the meta-controller level. Even a similar contrastively-learned representation is used, which they dub an “achievement context” (like the achievement representation in this work). Given the striking similarities, adequate discussion of [1] is crucial to understanding the contributions of the current work, and the comparative limitations/benefits.

  * [2] This is just one example of another relevant work that similarly autonomously learns a subtask dependency structure from experience and utilizes it for better performance. The current work lacks comparison to these types of relevant works in the literature. How does the present approach compare to other works that have also thought about subtask dependency structures? What are the limitations/benefits of the present work in comparison?

  * [3] This work is cited, but improperly so—-the authors in the same sentence mention that reward machines must be hand-specified, but this work learns them from experience. A clearer/more faithful explanation of the differences to the present work should be included. 

* The method diagram was more confusing than helpful to me; for example:

  * “Filtered reward” is a phrase that appears nowhere in the text, but it seems to indicate that only achievement-specific rewards are used (as determined by the achievement classifier) to train each subpolicy. 

  * Why is the goal/achievement being passed to the achievement classifier in the diagram? My understanding is that the achievement classifier takes in a transition and outputs which achievements are afforded. 

  * Minor, but the term “goal” is used in the diagram, which is inconsistent with the terminology in the paper (should be “achievement”). 

* In the evaluation there are no comparisons to other HRL approaches, much less other approaches that take advantage of achievement/subtask structure (e.g. [1]). This makes the results less compelling. Without the proper comparisons, it is difficult to judge the contributions of the present work. For example, a simple baseline/ablation would be to perform the clustering to identify achievements, and then use the standard random exploration in the meta-controller, and compare this to the full approach which uses the inferred dependency graph to guide exploration. This would help disentangle the factors leading to performance gains on the evaluation environments. 



[1] Possibility Before Utility: Learning And Using Hierarchical Affordances (Costales et al., 2022)

[2] Meta reinforcement learning with autonomous inference of subtask dependencies (Sohn et al., 2020) 

[3] Learning Reward Machines for Partially Observable Reinforcement Learning (Icarte et al., 2019)


clarity,_quality,_novelty_and_reproducibility: * The paper is generally clearly written. 

* The paper appears to be missing several key details, citations, and comparisons in evaluation, so the quality is questionable. 

* The paper’s novelty is not clear given the missing references and corresponding discussion.

* The paper is reproducible because the code is provided. However, a number of important details appear to be missing from the document. 
summary_of_the_review: The work is well-motivated and generally clearly written, but is missing key details, citations and corresponding discussion, and comparisons/ablations in the evaluation.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes an structured exploration approach by learning the structure of the achievement task in procedural generated environments and using that structure to explicitly control for which achievement to pursue and learning an achievement conditional policies. The paper shows promising results in Crafter and TreeMaze.

strength_and_weaknesses: Strengths: 
This paper introduces to the best of my knowledge a structured exploration strategy based on hard clustering of achievements and uses its learned graph representation to make meaningful exploration. The idea is novel and relevant to the exploration community.
Weaknesses:
The main weakness of this paper is reproducibility since little information is provided regarding the meta controller policies learned (what model is used/architecture choices/ how it was trained/etc).The authors claim the meta controller is biased towards continuing achievements but how exactly is this biasing being done?
How are the nodes related to the clusters 1-1? how are the edges being estimated are they weighted?

clarity,_quality,_novelty_and_reproducibility: The paper is very well written and, it is thorough in its exposition and provides clear and compelling results. It is also novel, however it lacks in reproducibility and could improve from clarifying a few points:
Can the authors clarify what they mean by “removing node i-j can only move node j” to the left “ should it be LEFTMOST(G,j)?
How can the non-causal relations break the exploration?
In the large data regime does having a structural model help or hinder results if the model is not well estimated? Can the authors provide an intuition or ablation to understand the trade-offs of using a structured model.
Can the authors provide an intuition of how to properly select the number of clusters, is this sensitive to the number of clusters? How so?
What is the empirical benefit of using the det penalization?

Minor comments/typos:
What is y in eqr_ in page 4
Then use the build -> then build page 2
summary_of_the_review: This paper provides a meaningful contribution to the exploration community it provides interesting results in procedurally generated environments. The paper could benefit from further clarification on the above points.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper looks at a specific class of RL problems where the reward structure of the underlying MDP can be specified in terms of achievements. The paper proposes a multi-stage method that tries to uncover the structure of the problem, by learning an achievement dependency class, which is then used to learn a meta-controller that can be used to explore the various achievements (by leveraging the dependency relationships between the achievements). The authors also argue for the fact that these structures once learned could be used across various instances that share the same achievement structures.

strength_and_weaknesses: I mostly want to highlight two aspects, how easy it is to receive the assumed trajectories and whether the work is making more assumptions about the achievements than what is listed. 

Trajectories: So one of the underlying assumptions of the method is access to trajectories that reflect the underlying achievement structure. The effectiveness of the method relies on how well these trajectories capture the underlying structure. The work mostly mentions that these trajectories could come from experts or other previously trained agents. However, this is built on the assumption that there exists a small/easy enough instance which shares the same structure, but where the exploration can be performed effectively (or where the expert can give the traces). This need not be true and the simplest problem instance may still be too hard to effectively specify all the trajectories. One possibility the authors might want to consider is, how easy would be for domain experts to directly specify, at least an incomplete version of the achievement dependency graph. This is a common practice in many fields like causal inference and learning. Also if a set of trajectories is available, a possibility that should have been considered was whether you could have used an inverse reinforcement learning algorithm to learn a potentially informative reward function. Provided these reward functions are represented in parametric form, it should be possible to apply them within other instances at least as a way to provide shaping information.

Assumptions about achievement structures: The heuristic algorithm seems to imply that the algorithm would only consider an ordering to be valid if it holds in every trajectory. While this is a reasonable starting point, this would overlook cases when there are disjunctive relationships between parents and children. A common case could be one when a specific fact could be achieved in a different way (For example, you can enter a room by either unlocking the door or by breaking down the door). Similarly the current method also seems to make the assumption that all transitions that correspond to a specific achievement would be equivalent in how good they are with respect to the ease with which future achievements can be reached from the resulting state. This is a common assumption shared by a lot of works that tries to break down the problem into subgoals and then solve subgoals independently. You can look at [1] to see an example of a recent work that tries to address this issue.

[1] Guan, Lin, Sarath Sreedharan, and Subbarao Kambhampati. "Leveraging Approximate Symbolic Models for Reinforcement Learning via Skill Diversity." ICML (2022).

clarity,_quality,_novelty_and_reproducibility: In general the paper is well written and easy to follow. While the work does make some assumptions about the underlying problems, I think the current version serves well as a starting point. In terms of novelty, I am unaware of any methods that address the same problem or provide the same level of flexibility. With that said, the authors should try to expand their related works section to contrast the current method with other approaches that leverages information from symbolic models (apart from [1], there are works like [2],[3] etc..) or works that try to generalize from information learned from simpler domain instances (for example [4]).

[2] Yang, Fangkai, et al. "Peorl: Integrating symbolic planning and hierarchical reinforcement learning for robust decision-making." arXiv preprint arXiv:1804.07779 (2018).

[3] Lee, Junkyu, et al. "AI Planning Annotation for Sample Efficient Reinforcement Learning." arXiv preprint arXiv:2203.00669 (2022).

[4] Groshev, Edward, et al. "Learning generalized reactive policies using deep neural networks." Twenty-Eighth International Conference on Automated Planning and Scheduling. 2018.
summary_of_the_review: Even with all the reservations I mentioned above, in general I am leaning towards accepting the paper. However, I would definitely urge the authors to see if they could include additional experiments that compare against baselines that can actually leverage the traces in some meaningful way (using an IRL-based method for reward shaping signal could be one such way).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper addresses the problem of hard exploration in complex environments with an internal achievement system. The authors propose a novel approach, Structured Exploration with Achievements (SEA), which learns representations of achievements from offline data. SEA is evaluated on procedurally generated environments.

Reviewers initially noted that the paper addresses the very challenging problem of exploration in problems with long horizons and high-dimensional observations in a novel and well-motivated approach. Empirical results were performed on difficult domains that are well matched with the challenges captured in the problem formulation and addressed by the proposed approach.

Reviews noted several open questions and concerns, many of which were addressed during the rebuttal phase. Clarity needed to be improved, e.g., to provide details about the achievement system and the resulting underlying assumptions, as well as aspects of the approach, e.g., the mechanism behind biasing the meta-controller. Questions were raised regarding robustness to hyperparameter choices, and an ablation of algorithmic components was suggested. Finally reviewers noted the need to better place the work in the context of prior work in related areas, in particular hierarchical reinforcement learning (HRL).

Authors addressed many of the concerns. In particular, they added a novel baseline (an adapted version of HAL, an HRL approach) and new ablation study. They provided additional discussion on prior work in the context of HRL methods, clarified aspects of the approach and provided additional experiment details.

Reviewers provided feedback and additional discussion, both with reviewers and internally. While no full consensus among reviewers has been reached, two reviewers are in strong support of accepting the paper based on its novelty and strong empirical results. 

There are some remaining concerns. In particular, the authors are encouraged to further improve the contextualization of their notion of "achievement structure" and how it differs from structural assumptions made in prior work, such as HRL. It is important that readers appreciate where the present work makes, e.g., weaker assumptions than prior work. 

The recommendation is to accept the work based on its novelty and strong empirical contribution. Authors are encouraged to carefully consider all reviewer suggestions in their camera ready version, especially to identify ways to further contextualize the work in the context of prior problem formulations and approaches.
justification_for_why_not_higher_score: The paper presents a promising approach and solid empirical validation. At the same time, its clarity and placement in the context of related work could be improved further. Given these points, acceptance as a spotlight does not seem warrented.
justification_for_why_not_lower_score: Among the reviewers, two strong supporters of the paper make valid points about the novelty and sizable contribution made by the paper.
Decision: Accept: poster